« back to all changes in this revision
Viewing changes to src/seg.c
- browse files at revision 3
- compare with another revision
- download diff
- download tarball
- view history from revision 3
- Committer: Bazaar Package Importer
- Author(s): Darren Salt
- Date: 2008-01-30 13:33:49 UTC
- mfrom: (1.1.1 upstream)
- Revision ID: james.westby@ubuntu.com-20080130133349-kgojg33vyiu8xbvp
Tags: 2.24-1
* New upstream release.
* Bumped the lib soname and the library package name due to one silly
little binary incompatibility caused by changes in an exported struct.
(Safe; nothing else currently in the archive has ever used libglbsp2.)
* Removed my patches since they're all applied upstream.
* Updated the list of documentation files.
* Build-time changes:
- Switched from dh_movefiles to dh_install.
- Updated my makefile to cope with upstream changes.
- Corrected for debian-rules-ignores-make-clean-error.
- Corrected for substvar-source-version-is-deprecated.
- Link libglbsp, rather than glbsp, with libm and libz.
* Fixed shlibdeps. (Closes: #460387)
* Bumped standards version to 3.7.3 (no other changes).
* Bumped the lib soname and the library package name due to one silly
little binary incompatibility caused by changes in an exported struct.
(Safe; nothing else currently in the archive has ever used libglbsp2.)
* Removed my patches since they're all applied upstream.
* Updated the list of documentation files.
* Build-time changes:
- Switched from dh_movefiles to dh_install.
- Updated my makefile to cope with upstream changes.
- Corrected for debian-rules-ignores-make-clean-error.
- Corrected for substvar-source-version-is-deprecated.
- Link libglbsp, rather than glbsp, with libm and libz.
* Fixed shlibdeps. (Closes: #460387)
* Bumped standards version to 3.7.3 (no other changes).
- files added:
- AUTHORS.txt
- gui
- gui/glBSPX.app
- gui/glBSPX.app/Contents
- gui/glBSPX.app/Contents/Resources
- nodeview
- old_stuff
- patches
- patches/fltk_win32
- patches/fltk_win32/devcpp
- patches/fltk_win32/src
- src
- files removed:
- Cmdline.dev
- debian/patches
- fltk
- fltk/glBSPX.app
- fltk/glBSPX.app/Contents
- fltk/glBSPX.app/Contents/Resources
- files modified:
- CHANGES.txt
added
removed
src/seg.c
1
//------------------------------------------------------------------------
2
// SEG : Choose the best Seg to use for a node line.
3
//------------------------------------------------------------------------
4
//
5
// GL-Friendly Node Builder (C) 2000-2007 Andrew Apted
6
//
7
// Based on 'BSP 2.3' by Colin Reed, Lee Killough and others.
8
//
9
// This program is free software; you can redistribute it and/or
10
// modify it under the terms of the GNU General Public License
11
// as published by the Free Software Foundation; either version 2
12
// of the License, or (at your option) any later version.
13
//
14
// This program is distributed in the hope that it will be useful,
15
// but WITHOUT ANY WARRANTY; without even the implied warranty of
16
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17
// GNU General Public License for more details.
18
//
19
//------------------------------------------------------------------------
20
//
21
// To be able to divide the nodes down, this routine must decide which
22
// is the best Seg to use as a nodeline. It does this by selecting the
23
// line with least splits and has least difference of Segs on either
24
// side of it.
25
//
26
// Credit to Raphael Quinet and DEU, this routine is a copy of the
27
// nodeline picker used in DEU5beta. I am using this method because
28
// the method I originally used was not so good.
29
//
30
// Rewritten by Lee Killough to significantly improve performance,
31
// while not affecting results one bit in >99% of cases (some tiny
32
// differences due to roundoff error may occur, but they are
33
// insignificant).
34
//
35
// Rewritten again by Andrew Apted (-AJA-), 1999-2000.
36
//
37
38
#include "system.h"
39
40
#include <stdio.h>
41
#include <stdlib.h>
42
#include <string.h>
43
#include <stdarg.h>
44
#include <ctype.h>
45
#include <math.h>
46
#include <limits.h>
47
#include <assert.h>
48
49
#include "analyze.h"
50
#include "blockmap.h"
51
#include "level.h"
52
#include "node.h"
53
#include "seg.h"
54
#include "structs.h"
55
#include "util.h"
56
#include "wad.h"
57
58
59
#define PRECIOUS_MULTIPLY 100
60
61
#define SEG_REUSE_THRESHHOLD 200
62
63
64
#define DEBUG_PICKNODE 0
65
#define DEBUG_SPLIT 0
66
#define DEBUG_CUTLIST 0
67
68
69
typedef struct eval_info_s
70
{
71
int cost;
72
int splits;
73
int iffy;
74
int near_miss;
75
76
int real_left;
77
int real_right;
78
int mini_left;
79
int mini_right;
80
}
81
eval_info_t;
82
83
84
static intersection_t *quick_alloc_cuts = NULL;
85
86
87
//
88
// NewIntersection
89
//
90
static intersection_t *NewIntersection(void)
91
{
92
intersection_t *cut;
93
94
if (quick_alloc_cuts)
95
{
96
cut = quick_alloc_cuts;
97
quick_alloc_cuts = cut->next;
98
}
99
else
100
{
101
cut = UtilCalloc(sizeof(intersection_t));
102
}
103
104
return cut;
105
}
106
107
//
108
// FreeQuickAllocCuts
109
//
110
void FreeQuickAllocCuts(void)
111
{
112
while (quick_alloc_cuts)
113
{
114
intersection_t *cut = quick_alloc_cuts;
115
quick_alloc_cuts = cut->next;
116
117
UtilFree(cut);
118
}
119
}
120
121
122
//
123
// RecomputeSeg
124
//
125
// Fill in the fields 'angle', 'len', 'pdx', 'pdy', etc...
126
//
127
void RecomputeSeg(seg_t *seg)
128
{
129
seg->psx = seg->start->x;
130
seg->psy = seg->start->y;
131
seg->pex = seg->end->x;
132
seg->pey = seg->end->y;
133
seg->pdx = seg->pex - seg->psx;
134
seg->pdy = seg->pey - seg->psy;
135
136
seg->p_length = UtilComputeDist(seg->pdx, seg->pdy);
137
seg->p_angle = UtilComputeAngle(seg->pdx, seg->pdy);
138
139
if (seg->p_length <= 0)
140
InternalError("Seg %p has zero p_length.", seg);
141
142
seg->p_perp = seg->psy * seg->pdx - seg->psx * seg->pdy;
143
seg->p_para = -seg->psx * seg->pdx - seg->psy * seg->pdy;
144
}
145
146
147
//
148
// SplitSeg
149
//
150
// -AJA- Splits the given seg at the point (x,y). The new seg is
151
// returned. The old seg is shortened (the original start
152
// vertex is unchanged), whereas the new seg becomes the cut-off
153
// tail (keeping the original end vertex).
154
//
155
// If the seg has a partner, than that partner is also split.
156
// NOTE WELL: the new piece of the partner seg is inserted into
157
// the same list as the partner seg (and after it) -- thus ALL
158
// segs (except the one we are currently splitting) must exist
159
// on a singly-linked list somewhere.
160
//
161
// Note: we must update the count values of any superblock that
162
// contains the seg (and/or partner), so that future processing
163
// is not fucked up by incorrect counts.
164
//
165
static seg_t *SplitSeg(seg_t *old_seg, float_g x, float_g y)
166
{
167
seg_t *new_seg;
168
vertex_t *new_vert;
169
170
# if DEBUG_SPLIT
171
if (old_seg->linedef)
172
PrintDebug("Splitting Linedef %d (%p) at (%1.1f,%1.1f)\n",
173
old_seg->linedef->index, old_seg, x, y);
174
else
175
PrintDebug("Splitting Miniseg %p at (%1.1f,%1.1f)\n", old_seg, x, y);
176
# endif
177
178
// update superblock, if needed
179
if (old_seg->block)
180
SplitSegInSuper(old_seg->block, old_seg);
181
182
new_vert = NewVertexFromSplitSeg(old_seg, x, y);
183
new_seg = NewSeg();
184
185
// copy seg info
186
new_seg[0] = old_seg[0];
187
new_seg->next = NULL;
188
189
old_seg->end = new_vert;
190
RecomputeSeg(old_seg);
191
192
new_seg->start = new_vert;
193
RecomputeSeg(new_seg);
194
195
# if DEBUG_SPLIT
196
PrintDebug("Splitting Vertex is %04X at (%1.1f,%1.1f)\n",
197
new_vert->index, new_vert->x, new_vert->y);
198
# endif
199
200
// handle partners
201
202
if (old_seg->partner)
203
{
204
# if DEBUG_SPLIT
205
PrintDebug("Splitting Partner %p\n", old_seg->partner);
206
# endif
207
208
// update superblock, if needed
209
if (old_seg->partner->block)
210
SplitSegInSuper(old_seg->partner->block, old_seg->partner);
211
212
new_seg->partner = NewSeg();
213
214
// copy seg info
215
new_seg->partner[0] = old_seg->partner[0];
216
217
// IMPORTANT: keep partner relationship valid.
218
new_seg->partner->partner = new_seg;
219
220
old_seg->partner->start = new_vert;
221
RecomputeSeg(old_seg->partner);
222
223
new_seg->partner->end = new_vert;
224
RecomputeSeg(new_seg->partner);
225
226
// link it into list
227
old_seg->partner->next = new_seg->partner;
228
}
229
230
return new_seg;
231
}
232
233
234
//
235
// ComputeIntersection
236
//
237
// -AJA- In the quest for slime-trail annihilation :->, this routine
238
// calculates the intersection location between the current seg
239
// and the partitioning seg, and takes advantage of some common
240
// situations like horizontal/vertical lines.
241
//
242
static INLINE_G void ComputeIntersection(seg_t *cur, seg_t *part,
243
float_g perp_c, float_g perp_d, float_g *x, float_g *y)
244
{
245
double ds;
246
247
// horizontal partition against vertical seg
248
if (part->pdy == 0 && cur->pdx == 0)
249
{
250
*x = cur->psx;
251
*y = part->psy;
252
return;
253
}
254
255
// vertical partition against horizontal seg
256
if (part->pdx == 0 && cur->pdy == 0)
257
{
258
*x = part->psx;
259
*y = cur->psy;
260
return;
261
}
262
263
// 0 = start, 1 = end
264
ds = perp_c / (perp_c - perp_d);
265
266
if (cur->pdx == 0)
267
*x = cur->psx;
268
else
269
*x = cur->psx + (cur->pdx * ds);
270
271
if (cur->pdy == 0)
272
*y = cur->psy;
273
else
274
*y = cur->psy + (cur->pdy * ds);
275
}
276
277
278
//
279
// AddIntersection
280
//
281
static void AddIntersection(intersection_t ** cut_list,
282
vertex_t *vert, seg_t *part, boolean_g self_ref)
283
{
284
intersection_t *cut;
285
intersection_t *after;
286
287
/* check if vertex already present */
288
for (cut=(*cut_list); cut; cut=cut->next)
289
{
290
if (vert == cut->vertex)
291
return;
292
}
293
294
/* create new intersection */
295
cut = NewIntersection();
296
297
cut->vertex = vert;
298
cut->along_dist = UtilParallelDist(part, vert->x, vert->y);
299
cut->self_ref = self_ref;
300
301
cut->before = VertexCheckOpen(vert, -part->pdx, -part->pdy);
302
cut->after = VertexCheckOpen(vert, part->pdx, part->pdy);
303
304
/* enqueue the new intersection into the list */
305
306
for (after=(*cut_list); after && after->next; after=after->next)
307
{ }
308
309
while (after && cut->along_dist < after->along_dist)
310
after = after->prev;
311
312
/* link it in */
313
cut->next = after ? after->next : (*cut_list);
314
cut->prev = after;
315
316
if (after)
317
{
318
if (after->next)
319
after->next->prev = cut;
320
321
after->next = cut;
322
}
323
else
324
{
325
if (*cut_list)
326
(*cut_list)->prev = cut;
327
328
(*cut_list) = cut;
329
}
330
}
331
332
333
//
334
// EvalPartitionWorker
335
//
336
// Returns TRUE if a "bad seg" was found early.
337
//
338
static int EvalPartitionWorker(superblock_t *seg_list, seg_t *part,
339
int best_cost, eval_info_t *info)
340
{
341
seg_t *check;
342
343
float_g qnty;
344
float_g a, b, fa, fb;
345
346
int num;
347
int factor = cur_info->factor;
348
349
// -AJA- this is the heart of my superblock idea, it tests the
350
// _whole_ block against the partition line to quickly handle
351
// all the segs within it at once. Only when the partition
352
// line intercepts the box do we need to go deeper into it.
353
354
num = BoxOnLineSide(seg_list, part);
355
356
if (num < 0)
357
{
358
// LEFT
359
360
info->real_left += seg_list->real_num;
361
info->mini_left += seg_list->mini_num;
362
363
return FALSE;
364
}
365
else if (num > 0)
366
{
367
// RIGHT
368
369
info->real_right += seg_list->real_num;
370
info->mini_right += seg_list->mini_num;
371
372
return FALSE;
373
}
374
375
# define ADD_LEFT() \
376
do { \
377
if (check->linedef) info->real_left += 1; \
378
else info->mini_left += 1; \
379
} while (0)
380
381
# define ADD_RIGHT() \
382
do { \
383
if (check->linedef) info->real_right += 1; \
384
else info->mini_right += 1; \
385
} while (0)
386
387
/* check partition against all Segs */
388
389
for (check=seg_list->segs; check; check=check->next)
390
{
391
// This is the heart of my pruning idea - it catches
392
// bad segs early on. Killough
393
394
if (info->cost > best_cost)
395
return TRUE;
396
397
/* get state of lines' relation to each other */
398
if (check->source_line == part->source_line)
399
{
400
a = b = fa = fb = 0;
401
}
402
else
403
{
404
a = UtilPerpDist(part, check->psx, check->psy);
405
b = UtilPerpDist(part, check->pex, check->pey);
406
407
fa = fabs(a);
408
fb = fabs(b);
409
}
410
411
/* check for being on the same line */
412
if (fa <= DIST_EPSILON && fb <= DIST_EPSILON)
413
{
414
// this seg runs along the same line as the partition. Check
415
// whether it goes in the same direction or the opposite.
416
417
if (check->pdx*part->pdx + check->pdy*part->pdy < 0)
418
{
419
ADD_LEFT();
420
}
421
else
422
{
423
ADD_RIGHT();
424
}
425
426
continue;
427
}
428
429
// -AJA- check for passing through a vertex. Normally this is fine
430
// (even ideal), but the vertex could on a sector that we
431
// DONT want to split, and the normal linedef-based checks
432
// may fail to detect the sector being cut in half. Thanks
433
// to Janis Legzdinsh for spotting this obscure bug.
434
435
if (fa <= DIST_EPSILON || fb <= DIST_EPSILON)
436
{
437
if (check->linedef && check->linedef->is_precious)
438
info->cost += 40 * factor * PRECIOUS_MULTIPLY;
439
}
440
441
/* check for right side */
442
if (a > -DIST_EPSILON && b > -DIST_EPSILON)
443
{
444
ADD_RIGHT();
445
446
/* check for a near miss */
447
if ((a >= IFFY_LEN && b >= IFFY_LEN) ||
448
(a <= DIST_EPSILON && b >= IFFY_LEN) ||
449
(b <= DIST_EPSILON && a >= IFFY_LEN))
450
{
451
continue;
452
}
453
454
info->near_miss++;
455
456
// -AJA- near misses are bad, since they have the potential to
457
// cause really short minisegs to be created in future
458
// processing. Thus the closer the near miss, the higher
459
// the cost.
460
461
if (a <= DIST_EPSILON || b <= DIST_EPSILON)
462
qnty = IFFY_LEN / MAX(a, b);
463
else
464
qnty = IFFY_LEN / MIN(a, b);
465
466
info->cost += (int) (100 * factor * (qnty * qnty - 1.0));
467
continue;
468
}
469
470
/* check for left side */
471
if (a < DIST_EPSILON && b < DIST_EPSILON)
472
{
473
ADD_LEFT();
474
475
/* check for a near miss */
476
if ((a <= -IFFY_LEN && b <= -IFFY_LEN) ||
477
(a >= -DIST_EPSILON && b <= -IFFY_LEN) ||
478
(b >= -DIST_EPSILON && a <= -IFFY_LEN))
479
{
480
continue;
481
}
482
483
info->near_miss++;
484
485
// the closer the miss, the higher the cost (see note above)
486
if (a >= -DIST_EPSILON || b >= -DIST_EPSILON)
487
qnty = IFFY_LEN / -MIN(a, b);
488
else
489
qnty = IFFY_LEN / -MAX(a, b);
490
491
info->cost += (int) (70 * factor * (qnty * qnty - 1.0));
492
continue;
493
}
494
495
// When we reach here, we have a and b non-zero and opposite sign,
496
// hence this seg will be split by the partition line.
497
498
info->splits++;
499
500
// If the linedef associated with this seg has a tag >= 900, treat
501
// it as precious; i.e. don't split it unless all other options
502
// are exhausted. This is used to protect deep water and invisible
503
// lifts/stairs from being messed up accidentally by splits.
504
505
if (check->linedef && check->linedef->is_precious)
506
info->cost += 100 * factor * PRECIOUS_MULTIPLY;
507
else
508
info->cost += 100 * factor;
509
510
// -AJA- check if the split point is very close to one end, which
511
// is quite an undesirable situation (producing really short
512
// segs). This is perhaps _one_ source of those darn slime
513
// trails. Hence the name "IFFY segs", and a rather hefty
514
// surcharge :->.
515
516
if (fa < IFFY_LEN || fb < IFFY_LEN)
517
{
518
info->iffy++;
519
520
// the closer to the end, the higher the cost
521
qnty = IFFY_LEN / MIN(fa, fb);
522
info->cost += (int) (140 * factor * (qnty * qnty - 1.0));
523
}
524
}
525
526
/* handle sub-blocks recursively */
527
528
for (num=0; num < 2; num++)
529
{
530
if (! seg_list->subs[num])
531
continue;
532
533
if (EvalPartitionWorker(seg_list->subs[num], part, best_cost, info))
534
return TRUE;
535
}
536
537
/* no "bad seg" was found */
538
return FALSE;
539
}
540
541
//
542
// EvalPartition
543
//
544
// -AJA- Evaluate a partition seg & determine the cost, taking into
545
// account the number of splits, difference between left &
546
// right, and linedefs that are tagged 'precious'.
547
//
548
// Returns the computed cost, or a negative value if the seg should be
549
// skipped altogether.
550
//
551
static int EvalPartition(superblock_t *seg_list, seg_t *part,
552
int best_cost)
553
{
554
eval_info_t info;
555
556
/* initialise info structure */
557
info.cost = 0;
558
info.splits = 0;
559
info.iffy = 0;
560
info.near_miss = 0;
561
562
info.real_left = 0;
563
info.real_right = 0;
564
info.mini_left = 0;
565
info.mini_right = 0;
566
567
if (EvalPartitionWorker(seg_list, part, best_cost, &info))
568
return -1;
569
570
/* make sure there is at least one real seg on each side */
571
if (info.real_left == 0 || info.real_right == 0)
572
{
573
# if DEBUG_PICKNODE
574
PrintDebug("Eval : No real segs on %s%sside\n",
575
info.real_left ? "" : "left ",
576
info.real_right ? "" : "right ");
577
# endif
578
579
return -1;
580
}
581
582
/* increase cost by the difference between left & right */
583
info.cost += 100 * ABS(info.real_left - info.real_right);
584
585
// -AJA- allow miniseg counts to affect the outcome, but only to a
586
// lesser degree than real segs.
587
588
info.cost += 50 * ABS(info.mini_left - info.mini_right);
589
590
// -AJA- Another little twist, here we show a slight preference for
591
// partition lines that lie either purely horizontally or
592
// purely vertically.
593
594
if (part->pdx != 0 && part->pdy != 0)
595
info.cost += 25;
596
597
# if DEBUG_PICKNODE
598
PrintDebug("Eval %p: splits=%d iffy=%d near=%d left=%d+%d right=%d+%d "
599
"cost=%d.%02d\n", part, info.splits, info.iffy, info.near_miss,
600
info.real_left, info.mini_left, info.real_right, info.mini_right,
601
info.cost / 100, info.cost % 100);
602
# endif
603
604
return info.cost;
605
}
606
607
608
static seg_t *FindSegFromStaleNode(superblock_t *part_list,
609
node_t *stale_nd, int *stale_opposite)
610
{
611
seg_t *part;
612
int num;
613
614
for (part=part_list->segs; part; part = part->next)
615
{
616
float_g fa, fb;
617
618
/* ignore minisegs as partition candidates */
619
if (! part->linedef)
620
continue;
621
622
fa = fabs(UtilPerpDist(part, stale_nd->x, stale_nd->y));
623
fb = fabs(UtilPerpDist(part, stale_nd->x + stale_nd->dx,
624
stale_nd->y + stale_nd->dy));
625
626
if (fa < DIST_EPSILON && fb < DIST_EPSILON)
627
{
628
/* OK found it. check if runs in same direction */
629
630
(*stale_opposite) = (stale_nd->dx * part->pdx +
631
stale_nd->dy * part->pdy < 0) ? 1 : 0;
632
633
return part;
634
}
635
}
636
637
/* handle sub-blocks recursively */
638
639
for (num=0; num < 2; num++)
640
{
641
if (! part_list->subs[num])
642
continue;
643
644
part = FindSegFromStaleNode(part_list->subs[num], stale_nd,
645
stale_opposite);
646
647
if (part)
648
return part;
649
}
650
651
return NULL;
652
}
653
654
655
/* returns FALSE if cancelled */
656
static int PickNodeWorker(superblock_t *part_list,
657
superblock_t *seg_list, seg_t ** best, int *best_cost,
658
int *progress, int prog_step)
659
{
660
seg_t *part;
661
662
int num;
663
int cost;
664
665
/* use each Seg as partition */
666
for (part=part_list->segs; part; part = part->next)
667
{
668
if (cur_comms->cancelled)
669
return FALSE;
670
671
# if DEBUG_PICKNODE
672
PrintDebug("PickNode: %sSEG %p sector=%d (%1.1f,%1.1f) -> (%1.1f,%1.1f)\n",
673
part->linedef ? "" : "MINI", part,
674
part->sector ? part->sector->index : -1,
675
part->start->x, part->start->y, part->end->x, part->end->y);
676
# endif
677
678
/* something for the user to look at */
679
(*progress) += 1;
680
681
if ((*progress % prog_step) == 0)
682
{
683
cur_comms->build_pos++;
684
DisplaySetBar(1, cur_comms->build_pos);
685
DisplaySetBar(2, cur_comms->file_pos + cur_comms->build_pos / 100);
686
}
687
688
/* ignore minisegs as partition candidates */
689
if (! part->linedef)
690
continue;
691
692
cost = EvalPartition(seg_list, part, *best_cost);
693
694
/* seg unsuitable or too costly ? */
695
if (cost < 0 || cost >= *best_cost)
696
continue;
697
698
/* we have a new better choice */
699
(*best_cost) = cost;
700
701
/* remember which Seg */
702
(*best) = part;
703
}
704
705
DisplayTicker();
706
707
/* recursively handle sub-blocks */
708
709
for (num=0; num < 2; num++)
710
{
711
if (part_list->subs[num])
712
PickNodeWorker(part_list->subs[num], seg_list, best, best_cost,
713
progress, prog_step);
714
}
715
716
return TRUE;
717
}
718
719
//
720
// PickNode
721
//
722
// Find the best seg in the seg_list to use as a partition line.
723
//
724
seg_t *PickNode(superblock_t *seg_list, int depth,
725
node_t ** stale_nd, int *stale_opposite)
726
{
727
seg_t *best=NULL;
728
729
int best_cost=INT_MAX;
730
731
int progress=0;
732
int prog_step=1<<24;
733
int build_step=0;
734
735
# if DEBUG_PICKNODE
736
PrintDebug("PickNode: BEGUN (depth %d)\n", depth);
737
# endif
738
739
/* compute info for showing progress */
740
if (depth <= 6)
741
{
742
static int depth_counts[7] = { 248, 100, 30, 10, 6, 4, 2 };
743
744
int total = seg_list->real_num + seg_list->mini_num;
745
746
build_step = depth_counts[depth];
747
prog_step = 1 + ((total - 1) / build_step);
748
749
if (total / prog_step < build_step)
750
{
751
cur_comms->build_pos += build_step - total / prog_step;
752
build_step = total / prog_step;
753
754
DisplaySetBar(1, cur_comms->build_pos);
755
DisplaySetBar(2, cur_comms->file_pos + cur_comms->build_pos / 100);
756
}
757
}
758
759
DisplayTicker();
760
761
/* -AJA- another (optional) optimisation, when building just the GL
762
* nodes. We assume that the original nodes are reasonably
763
* good choices, and re-use them as much as possible, saving
764
* *heaps* of time on really large levels.
765
*/
766
if (*stale_nd && seg_list->real_num >= SEG_REUSE_THRESHHOLD)
767
{
768
best = FindSegFromStaleNode(seg_list, *stale_nd, stale_opposite);
769
770
# if DEBUG_PICKNODE
771
PrintDebug("PickNode: Trying stale node %p\n", best);
772
# endif
773
774
if (best && EvalPartition(seg_list, best, best_cost) < 0)
775
{
776
best = NULL;
777
778
# if DEBUG_PICKNODE
779
PrintDebug("PickNode: Stale node unsuitable !\n");
780
# endif
781
}
782
783
if (best)
784
{
785
/* update progress */
786
cur_comms->build_pos += build_step;
787
DisplaySetBar(1, cur_comms->build_pos);
788
DisplaySetBar(2, cur_comms->file_pos + cur_comms->build_pos / 100);
789
790
# if DEBUG_PICKNODE
791
PrintDebug("PickNode: Using Stale node (%1.1f,%1.1f) -> (%1.1f,%1.1f)\n",
792
best->start->x, best->start->y, best->end->x, best->end->y);
793
# endif
794
795
return best;
796
}
797
}
798
799
(*stale_nd) = NULL;
800
801
if (FALSE == PickNodeWorker(seg_list, seg_list, &best, &best_cost,
802
&progress, prog_step))
803
{
804
/* hack here : BuildNodes will detect the cancellation */
805
return NULL;
806
}
807
808
# if DEBUG_PICKNODE
809
if (! best)
810
{
811
PrintDebug("PickNode: NO BEST FOUND !\n");
812
}
813
else
814
{
815
PrintDebug("PickNode: Best has score %d.%02d (%1.1f,%1.1f) -> (%1.1f,%1.1f)\n",
816
best_cost / 100, best_cost % 100, best->start->x, best->start->y,
817
best->end->x, best->end->y);
818
}
819
# endif
820
821
/* all finished, return best Seg */
822
return best;
823
}
824
825
826
//
827
// DivideOneSeg
828
//
829
// Apply the partition line to the given seg, taking the necessary
830
// action (moving it into either the left list, right list, or
831
// splitting it).
832
//
833
// -AJA- I have rewritten this routine based on the EvalPartition
834
// routine above (which I've also reworked, heavily). I think
835
// it is important that both these routines follow the exact
836
// same logic when determining which segs should go left, right
837
// or be split.
838
//
839
void DivideOneSeg(seg_t *cur, seg_t *part,
840
superblock_t *left_list, superblock_t *right_list,
841
intersection_t ** cut_list)
842
{
843
seg_t *new_seg;
844
845
float_g x, y;
846
847
/* get state of lines' relation to each other */
848
float_g a = UtilPerpDist(part, cur->psx, cur->psy);
849
float_g b = UtilPerpDist(part, cur->pex, cur->pey);
850
851
boolean_g self_ref = cur->linedef ? cur->linedef->self_ref : FALSE;
852
853
if (cur->source_line == part->source_line)
854
a = b = 0;
855
856
/* check for being on the same line */
857
if (fabs(a) <= DIST_EPSILON && fabs(b) <= DIST_EPSILON)
858
{
859
AddIntersection(cut_list, cur->start, part, self_ref);
860
AddIntersection(cut_list, cur->end, part, self_ref);
861
862
// this seg runs along the same line as the partition. check
863
// whether it goes in the same direction or the opposite.
864
865
if (cur->pdx*part->pdx + cur->pdy*part->pdy < 0)
866
{
867
AddSegToSuper(left_list, cur);
868
}
869
else
870
{
871
AddSegToSuper(right_list, cur);
872
}
873
874
return;
875
}
876
877
/* check for right side */
878
if (a > -DIST_EPSILON && b > -DIST_EPSILON)
879
{
880
if (a < DIST_EPSILON)
881
AddIntersection(cut_list, cur->start, part, self_ref);
882
else if (b < DIST_EPSILON)
883
AddIntersection(cut_list, cur->end, part, self_ref);
884
885
AddSegToSuper(right_list, cur);
886
return;
887
}
888
889
/* check for left side */
890
if (a < DIST_EPSILON && b < DIST_EPSILON)
891
{
892
if (a > -DIST_EPSILON)
893
AddIntersection(cut_list, cur->start, part, self_ref);
894
else if (b > -DIST_EPSILON)
895
AddIntersection(cut_list, cur->end, part, self_ref);
896
897
AddSegToSuper(left_list, cur);
898
return;
899
}
900
901
// when we reach here, we have a and b non-zero and opposite sign,
902
// hence this seg will be split by the partition line.
903
904
ComputeIntersection(cur, part, a, b, &x, &y);
905
906
new_seg = SplitSeg(cur, x, y);
907
908
AddIntersection(cut_list, cur->end, part, self_ref);
909
910
if (a < 0)
911
{
912
AddSegToSuper(left_list, cur);
913
AddSegToSuper(right_list, new_seg);
914
}
915
else
916
{
917
AddSegToSuper(right_list, cur);
918
AddSegToSuper(left_list, new_seg);
919
}
920
}
921
922
//
923
// SeparateSegs
924
//
925
void SeparateSegs(superblock_t *seg_list, seg_t *part,
926
superblock_t *lefts, superblock_t *rights,
927
intersection_t ** cut_list)
928
{
929
int num;
930
931
while (seg_list->segs)
932
{
933
seg_t *cur = seg_list->segs;
934
seg_list->segs = cur->next;
935
936
cur->block = NULL;
937
938
DivideOneSeg(cur, part, lefts, rights, cut_list);
939
}
940
941
// recursively handle sub-blocks
942
for (num=0; num < 2; num++)
943
{
944
superblock_t *A = seg_list->subs[num];
945
946
if (A)
947
{
948
SeparateSegs(A, part, lefts, rights, cut_list);
949
950
if (A->real_num + A->mini_num > 0)
951
InternalError("SeparateSegs: child %d not empty !", num);
952
953
FreeSuper(A);
954
seg_list->subs[num] = NULL;
955
}
956
}
957
958
seg_list->real_num = seg_list->mini_num = 0;
959
}
960
961
962
static void FindLimitWorker(superblock_t *block, bbox_t *bbox)
963
{
964
seg_t *cur;
965
int num;
966
967
for (cur=block->segs; cur; cur=cur->next)
968
{
969
float_g x1 = cur->start->x;
970
float_g y1 = cur->start->y;
971
float_g x2 = cur->end->x;
972
float_g y2 = cur->end->y;
973
974
int lx = (int) floor(MIN(x1, x2));
975
int ly = (int) floor(MIN(y1, y2));
976
int hx = (int) ceil(MAX(x1, x2));
977
int hy = (int) ceil(MAX(y1, y2));
978
979
if (lx < bbox->minx) bbox->minx = lx;
980
if (ly < bbox->miny) bbox->miny = ly;
981
if (hx > bbox->maxx) bbox->maxx = hx;
982
if (hy > bbox->maxy) bbox->maxy = hy;
983
}
984
985
// recursive handle sub-blocks
986
987
for (num=0; num < 2; num++)
988
{
989
if (block->subs[num])
990
FindLimitWorker(block->subs[num], bbox);
991
}
992
}
993
994
//
995
// FindLimits
996
//
997
// Find the limits from a list of segs, by stepping through the segs
998
// and comparing the vertices at both ends.
999
//
1000
void FindLimits(superblock_t *seg_list, bbox_t *bbox)
1001
{
1002
bbox->minx = bbox->miny = SHRT_MAX;
1003
bbox->maxx = bbox->maxy = SHRT_MIN;
1004
1005
FindLimitWorker(seg_list, bbox);
1006
}
1007
1008
1009
//
1010
// AddMinisegs
1011
//
1012
void AddMinisegs(seg_t *part,
1013
superblock_t *left_list, superblock_t *right_list,
1014
intersection_t *cut_list)
1015
{
1016
intersection_t *cur, *next;
1017
seg_t *seg, *buddy;
1018
1019
if (! cut_list)
1020
return;
1021
1022
# if DEBUG_CUTLIST
1023
PrintDebug("CUT LIST:\n");
1024
PrintDebug("PARTITION: (%1.1f,%1.1f) += (%1.1f,%1.1f)\n",
1025
part->psx, part->psy, part->pdx, part->pdy);
1026
1027
for (cur=cut_list; cur; cur=cur->next)
1028
{
1029
PrintDebug(" Vertex %8X (%1.1f,%1.1f) Along %1.2f [%d/%d] %s\n",
1030
cur->vertex->index, cur->vertex->x, cur->vertex->y,
1031
cur->along_dist,
1032
cur->before ? cur->before->index : -1,
1033
cur->after ? cur->after->index : -1,
1034
cur->self_ref ? "SELFREF" : "");
1035
}
1036
# endif
1037
1038
// STEP 1: fix problems the intersection list...
1039
1040
cur = cut_list;
1041
next = cur->next;
1042
1043
while (cur && next)
1044
{
1045
float_g len = next->along_dist - cur->along_dist;
1046
1047
if (len < -0.1)
1048
InternalError("Bad order in intersect list: %1.3f > %1.3f\n",
1049
cur->along_dist, next->along_dist);
1050
1051
if (len > 0.2)
1052
{
1053
cur = next;
1054
next = cur->next;
1055
continue;
1056
}
1057
1058
if (len > DIST_EPSILON)
1059
{
1060
PrintMiniWarn("Skipping very short seg (len=%1.3f) near (%1.1f,%1.1f)\n",
1061
len, cur->vertex->x, cur->vertex->y);
1062
}
1063
1064
// merge the two intersections into one
1065
1066
# if DEBUG_CUTLIST
1067
PrintDebug("Merging cut (%1.0f,%1.0f) [%d/%d] with %p (%1.0f,%1.0f) [%d/%d]\n",
1068
cur->vertex->x, cur->vertex->y,
1069
cur->before ? cur->before->index : -1,
1070
cur->after ? cur->after->index : -1,
1071
next->vertex,
1072
next->vertex->x, next->vertex->y,
1073
next->before ? next->before->index : -1,
1074
next->after ? next->after->index : -1);
1075
# endif
1076
1077
if (cur->self_ref && !next->self_ref)
1078
{
1079
if (cur->before && next->before)
1080
cur->before = next->before;
1081
1082
if (cur->after && next->after)
1083
cur->after = next->after;
1084
1085
cur->self_ref = FALSE;
1086
}
1087
1088
if (!cur->before && next->before)
1089
cur->before = next->before;
1090
1091
if (!cur->after && next->after)
1092
cur->after = next->after;
1093
1094
# if DEBUG_CUTLIST
1095
PrintDebug("---> merged (%1.0f,%1.0f) [%d/%d] %s\n",
1096
cur->vertex->x, cur->vertex->y,
1097
cur->before ? cur->before->index : -1,
1098
cur->after ? cur->after->index : -1,
1099
cur->self_ref ? "SELFREF" : "");
1100
# endif
1101
1102
// free the unused cut
1103
1104
cur->next = next->next;
1105
1106
next->next = quick_alloc_cuts;
1107
quick_alloc_cuts = next;
1108
1109
next = cur->next;
1110
}
1111
1112
// STEP 2: find connections in the intersection list...
1113
1114
for (cur = cut_list; cur && cur->next; cur = cur->next)
1115
{
1116
next = cur->next;
1117
1118
if (!cur->after && !next->before)
1119
continue;
1120
1121
// check for some nasty OPEN/CLOSED or CLOSED/OPEN cases
1122
if (cur->after && !next->before)
1123
{
1124
if (!cur->self_ref && !cur->after->warned_unclosed)
1125
{
1126
PrintMiniWarn("Sector #%d is unclosed near (%1.1f,%1.1f)\n",
1127
cur->after->index,
1128
(cur->vertex->x + next->vertex->x) / 2.0,
1129
(cur->vertex->y + next->vertex->y) / 2.0);
1130
cur->after->warned_unclosed = 1;
1131
}
1132
continue;
1133
}
1134
else if (!cur->after && next->before)
1135
{
1136
if (!next->self_ref && !next->before->warned_unclosed)
1137
{
1138
PrintMiniWarn("Sector #%d is unclosed near (%1.1f,%1.1f)\n",
1139
next->before->index,
1140
(cur->vertex->x + next->vertex->x) / 2.0,
1141
(cur->vertex->y + next->vertex->y) / 2.0);
1142
next->before->warned_unclosed = 1;
1143
}
1144
continue;
1145
}
1146
1147
// righteo, here we have definite open space.
1148
// do a sanity check on the sectors (just for good measure).
1149
1150
if (cur->after != next->before)
1151
{
1152
if (!cur->self_ref && !next->self_ref)
1153
PrintMiniWarn("Sector mismatch: #%d (%1.1f,%1.1f) != #%d (%1.1f,%1.1f)\n",
1154
cur->after->index, cur->vertex->x, cur->vertex->y,
1155
next->before->index, next->vertex->x, next->vertex->y);
1156
1157
// choose the non-self-referencing sector when we can
1158
if (cur->self_ref && !next->self_ref)
1159
{
1160
cur->after = next->before;
1161
}
1162
}
1163
1164
// create the miniseg pair
1165
seg = NewSeg();
1166
buddy = NewSeg();
1167
1168
seg->partner = buddy;
1169
buddy->partner = seg;
1170
1171
seg->start = cur->vertex;
1172
seg->end = next->vertex;
1173
1174
buddy->start = next->vertex;
1175
buddy->end = cur->vertex;
1176
1177
// leave 'linedef' field as NULL.
1178
// leave 'side' as zero too (not needed for minisegs).
1179
1180
seg->sector = buddy->sector = cur->after;
1181
1182
seg->index = buddy->index = -1;
1183
1184
seg->source_line = buddy->source_line = part->linedef;
1185
1186
RecomputeSeg(seg);
1187
RecomputeSeg(buddy);
1188
1189
// add the new segs to the appropriate lists
1190
AddSegToSuper(right_list, seg);
1191
AddSegToSuper(left_list, buddy);
1192
1193
# if DEBUG_CUTLIST
1194
PrintDebug("AddMiniseg: %p RIGHT sector %d (%1.1f,%1.1f) -> (%1.1f,%1.1f)\n",
1195
seg, seg->sector ? seg->sector->index : -1,
1196
seg->start->x, seg->start->y, seg->end->x, seg->end->y);
1197
1198
PrintDebug("AddMiniseg: %p LEFT sector %d (%1.1f,%1.1f) -> (%1.1f,%1.1f)\n",
1199
buddy, buddy->sector ? buddy->sector->index : -1,
1200
buddy->start->x, buddy->start->y, buddy->end->x, buddy->end->y);
1201
# endif
1202
}
1203
1204
// free intersection structures into quick-alloc list
1205
while (cut_list)
1206
{
1207
cur = cut_list;
1208
cut_list = cur->next;
1209
1210
cur->next = quick_alloc_cuts;
1211
quick_alloc_cuts = cur;
1212
}
1213
}
1214
Loggerhead is a web-based interface for Breezy
Version: 2.0.1