1
//------------------------------------------------------------------------
2
// SEG : Choose the best Seg to use for a node line.
3
//------------------------------------------------------------------------
5
// GL-Friendly Node Builder (C) 2000-2007 Andrew Apted
7
// Based on 'BSP 2.3' by Colin Reed, Lee Killough and others.
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.
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.
19
//------------------------------------------------------------------------
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
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.
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
35
// Rewritten again by Andrew Apted (-AJA-), 1999-2000.
59
#define PRECIOUS_MULTIPLY 100
61
#define SEG_REUSE_THRESHHOLD 200
64
#define DEBUG_PICKNODE 0
66
#define DEBUG_CUTLIST 0
69
typedef struct eval_info_s
84
static intersection_t *quick_alloc_cuts = NULL;
90
static intersection_t *NewIntersection(void)
96
cut = quick_alloc_cuts;
97
quick_alloc_cuts = cut->next;
101
cut = UtilCalloc(sizeof(intersection_t));
108
// FreeQuickAllocCuts
110
void FreeQuickAllocCuts(void)
112
while (quick_alloc_cuts)
114
intersection_t *cut = quick_alloc_cuts;
115
quick_alloc_cuts = cut->next;
125
// Fill in the fields 'angle', 'len', 'pdx', 'pdy', etc...
127
void RecomputeSeg(seg_t *seg)
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;
136
seg->p_length = UtilComputeDist(seg->pdx, seg->pdy);
137
seg->p_angle = UtilComputeAngle(seg->pdx, seg->pdy);
139
if (seg->p_length <= 0)
140
InternalError("Seg %p has zero p_length.", seg);
142
seg->p_perp = seg->psy * seg->pdx - seg->psx * seg->pdy;
143
seg->p_para = -seg->psx * seg->pdx - seg->psy * seg->pdy;
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).
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.
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.
165
static seg_t *SplitSeg(seg_t *old_seg, float_g x, float_g y)
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);
175
PrintDebug("Splitting Miniseg %p at (%1.1f,%1.1f)\n", old_seg, x, y);
178
// update superblock, if needed
180
SplitSegInSuper(old_seg->block, old_seg);
182
new_vert = NewVertexFromSplitSeg(old_seg, x, y);
186
new_seg[0] = old_seg[0];
187
new_seg->next = NULL;
189
old_seg->end = new_vert;
190
RecomputeSeg(old_seg);
192
new_seg->start = new_vert;
193
RecomputeSeg(new_seg);
196
PrintDebug("Splitting Vertex is %04X at (%1.1f,%1.1f)\n",
197
new_vert->index, new_vert->x, new_vert->y);
202
if (old_seg->partner)
205
PrintDebug("Splitting Partner %p\n", old_seg->partner);
208
// update superblock, if needed
209
if (old_seg->partner->block)
210
SplitSegInSuper(old_seg->partner->block, old_seg->partner);
212
new_seg->partner = NewSeg();
215
new_seg->partner[0] = old_seg->partner[0];
217
// IMPORTANT: keep partner relationship valid.
218
new_seg->partner->partner = new_seg;
220
old_seg->partner->start = new_vert;
221
RecomputeSeg(old_seg->partner);
223
new_seg->partner->end = new_vert;
224
RecomputeSeg(new_seg->partner);
227
old_seg->partner->next = new_seg->partner;
235
// ComputeIntersection
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.
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)
247
// horizontal partition against vertical seg
248
if (part->pdy == 0 && cur->pdx == 0)
255
// vertical partition against horizontal seg
256
if (part->pdx == 0 && cur->pdy == 0)
263
// 0 = start, 1 = end
264
ds = perp_c / (perp_c - perp_d);
269
*x = cur->psx + (cur->pdx * ds);
274
*y = cur->psy + (cur->pdy * ds);
281
static void AddIntersection(intersection_t ** cut_list,
282
vertex_t *vert, seg_t *part, boolean_g self_ref)
285
intersection_t *after;
287
/* check if vertex already present */
288
for (cut=(*cut_list); cut; cut=cut->next)
290
if (vert == cut->vertex)
294
/* create new intersection */
295
cut = NewIntersection();
298
cut->along_dist = UtilParallelDist(part, vert->x, vert->y);
299
cut->self_ref = self_ref;
301
cut->before = VertexCheckOpen(vert, -part->pdx, -part->pdy);
302
cut->after = VertexCheckOpen(vert, part->pdx, part->pdy);
304
/* enqueue the new intersection into the list */
306
for (after=(*cut_list); after && after->next; after=after->next)
309
while (after && cut->along_dist < after->along_dist)
313
cut->next = after ? after->next : (*cut_list);
319
after->next->prev = cut;
326
(*cut_list)->prev = cut;
334
// EvalPartitionWorker
336
// Returns TRUE if a "bad seg" was found early.
338
static int EvalPartitionWorker(superblock_t *seg_list, seg_t *part,
339
int best_cost, eval_info_t *info)
344
float_g a, b, fa, fb;
347
int factor = cur_info->factor;
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.
354
num = BoxOnLineSide(seg_list, part);
360
info->real_left += seg_list->real_num;
361
info->mini_left += seg_list->mini_num;
369
info->real_right += seg_list->real_num;
370
info->mini_right += seg_list->mini_num;
375
# define ADD_LEFT() \
377
if (check->linedef) info->real_left += 1; \
378
else info->mini_left += 1; \
381
# define ADD_RIGHT() \
383
if (check->linedef) info->real_right += 1; \
384
else info->mini_right += 1; \
387
/* check partition against all Segs */
389
for (check=seg_list->segs; check; check=check->next)
391
// This is the heart of my pruning idea - it catches
392
// bad segs early on. Killough
394
if (info->cost > best_cost)
397
/* get state of lines' relation to each other */
398
if (check->source_line == part->source_line)
404
a = UtilPerpDist(part, check->psx, check->psy);
405
b = UtilPerpDist(part, check->pex, check->pey);
411
/* check for being on the same line */
412
if (fa <= DIST_EPSILON && fb <= DIST_EPSILON)
414
// this seg runs along the same line as the partition. Check
415
// whether it goes in the same direction or the opposite.
417
if (check->pdx*part->pdx + check->pdy*part->pdy < 0)
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.
435
if (fa <= DIST_EPSILON || fb <= DIST_EPSILON)
437
if (check->linedef && check->linedef->is_precious)
438
info->cost += 40 * factor * PRECIOUS_MULTIPLY;
441
/* check for right side */
442
if (a > -DIST_EPSILON && b > -DIST_EPSILON)
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))
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
461
if (a <= DIST_EPSILON || b <= DIST_EPSILON)
462
qnty = IFFY_LEN / MAX(a, b);
464
qnty = IFFY_LEN / MIN(a, b);
466
info->cost += (int) (100 * factor * (qnty * qnty - 1.0));
470
/* check for left side */
471
if (a < DIST_EPSILON && b < DIST_EPSILON)
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))
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);
489
qnty = IFFY_LEN / -MAX(a, b);
491
info->cost += (int) (70 * factor * (qnty * qnty - 1.0));
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.
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.
505
if (check->linedef && check->linedef->is_precious)
506
info->cost += 100 * factor * PRECIOUS_MULTIPLY;
508
info->cost += 100 * factor;
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
516
if (fa < IFFY_LEN || fb < IFFY_LEN)
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));
526
/* handle sub-blocks recursively */
528
for (num=0; num < 2; num++)
530
if (! seg_list->subs[num])
533
if (EvalPartitionWorker(seg_list->subs[num], part, best_cost, info))
537
/* no "bad seg" was found */
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'.
548
// Returns the computed cost, or a negative value if the seg should be
549
// skipped altogether.
551
static int EvalPartition(superblock_t *seg_list, seg_t *part,
556
/* initialise info structure */
567
if (EvalPartitionWorker(seg_list, part, best_cost, &info))
570
/* make sure there is at least one real seg on each side */
571
if (info.real_left == 0 || info.real_right == 0)
574
PrintDebug("Eval : No real segs on %s%sside\n",
575
info.real_left ? "" : "left ",
576
info.real_right ? "" : "right ");
582
/* increase cost by the difference between left & right */
583
info.cost += 100 * ABS(info.real_left - info.real_right);
585
// -AJA- allow miniseg counts to affect the outcome, but only to a
586
// lesser degree than real segs.
588
info.cost += 50 * ABS(info.mini_left - info.mini_right);
590
// -AJA- Another little twist, here we show a slight preference for
591
// partition lines that lie either purely horizontally or
592
// purely vertically.
594
if (part->pdx != 0 && part->pdy != 0)
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);
608
static seg_t *FindSegFromStaleNode(superblock_t *part_list,
609
node_t *stale_nd, int *stale_opposite)
614
for (part=part_list->segs; part; part = part->next)
618
/* ignore minisegs as partition candidates */
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));
626
if (fa < DIST_EPSILON && fb < DIST_EPSILON)
628
/* OK found it. check if runs in same direction */
630
(*stale_opposite) = (stale_nd->dx * part->pdx +
631
stale_nd->dy * part->pdy < 0) ? 1 : 0;
637
/* handle sub-blocks recursively */
639
for (num=0; num < 2; num++)
641
if (! part_list->subs[num])
644
part = FindSegFromStaleNode(part_list->subs[num], stale_nd,
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)
665
/* use each Seg as partition */
666
for (part=part_list->segs; part; part = part->next)
668
if (cur_comms->cancelled)
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);
678
/* something for the user to look at */
681
if ((*progress % prog_step) == 0)
683
cur_comms->build_pos++;
684
DisplaySetBar(1, cur_comms->build_pos);
685
DisplaySetBar(2, cur_comms->file_pos + cur_comms->build_pos / 100);
688
/* ignore minisegs as partition candidates */
692
cost = EvalPartition(seg_list, part, *best_cost);
694
/* seg unsuitable or too costly ? */
695
if (cost < 0 || cost >= *best_cost)
698
/* we have a new better choice */
701
/* remember which Seg */
707
/* recursively handle sub-blocks */
709
for (num=0; num < 2; num++)
711
if (part_list->subs[num])
712
PickNodeWorker(part_list->subs[num], seg_list, best, best_cost,
713
progress, prog_step);
722
// Find the best seg in the seg_list to use as a partition line.
724
seg_t *PickNode(superblock_t *seg_list, int depth,
725
node_t ** stale_nd, int *stale_opposite)
729
int best_cost=INT_MAX;
736
PrintDebug("PickNode: BEGUN (depth %d)\n", depth);
739
/* compute info for showing progress */
742
static int depth_counts[7] = { 248, 100, 30, 10, 6, 4, 2 };
744
int total = seg_list->real_num + seg_list->mini_num;
746
build_step = depth_counts[depth];
747
prog_step = 1 + ((total - 1) / build_step);
749
if (total / prog_step < build_step)
751
cur_comms->build_pos += build_step - total / prog_step;
752
build_step = total / prog_step;
754
DisplaySetBar(1, cur_comms->build_pos);
755
DisplaySetBar(2, cur_comms->file_pos + cur_comms->build_pos / 100);
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.
766
if (*stale_nd && seg_list->real_num >= SEG_REUSE_THRESHHOLD)
768
best = FindSegFromStaleNode(seg_list, *stale_nd, stale_opposite);
771
PrintDebug("PickNode: Trying stale node %p\n", best);
774
if (best && EvalPartition(seg_list, best, best_cost) < 0)
779
PrintDebug("PickNode: Stale node unsuitable !\n");
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);
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);
801
if (FALSE == PickNodeWorker(seg_list, seg_list, &best, &best_cost,
802
&progress, prog_step))
804
/* hack here : BuildNodes will detect the cancellation */
811
PrintDebug("PickNode: NO BEST FOUND !\n");
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);
821
/* all finished, return best Seg */
829
// Apply the partition line to the given seg, taking the necessary
830
// action (moving it into either the left list, right list, or
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
839
void DivideOneSeg(seg_t *cur, seg_t *part,
840
superblock_t *left_list, superblock_t *right_list,
841
intersection_t ** cut_list)
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);
851
boolean_g self_ref = cur->linedef ? cur->linedef->self_ref : FALSE;
853
if (cur->source_line == part->source_line)
856
/* check for being on the same line */
857
if (fabs(a) <= DIST_EPSILON && fabs(b) <= DIST_EPSILON)
859
AddIntersection(cut_list, cur->start, part, self_ref);
860
AddIntersection(cut_list, cur->end, part, self_ref);
862
// this seg runs along the same line as the partition. check
863
// whether it goes in the same direction or the opposite.
865
if (cur->pdx*part->pdx + cur->pdy*part->pdy < 0)
867
AddSegToSuper(left_list, cur);
871
AddSegToSuper(right_list, cur);
877
/* check for right side */
878
if (a > -DIST_EPSILON && b > -DIST_EPSILON)
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);
885
AddSegToSuper(right_list, cur);
889
/* check for left side */
890
if (a < DIST_EPSILON && b < DIST_EPSILON)
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);
897
AddSegToSuper(left_list, cur);
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.
904
ComputeIntersection(cur, part, a, b, &x, &y);
906
new_seg = SplitSeg(cur, x, y);
908
AddIntersection(cut_list, cur->end, part, self_ref);
912
AddSegToSuper(left_list, cur);
913
AddSegToSuper(right_list, new_seg);
917
AddSegToSuper(right_list, cur);
918
AddSegToSuper(left_list, new_seg);
925
void SeparateSegs(superblock_t *seg_list, seg_t *part,
926
superblock_t *lefts, superblock_t *rights,
927
intersection_t ** cut_list)
931
while (seg_list->segs)
933
seg_t *cur = seg_list->segs;
934
seg_list->segs = cur->next;
938
DivideOneSeg(cur, part, lefts, rights, cut_list);
941
// recursively handle sub-blocks
942
for (num=0; num < 2; num++)
944
superblock_t *A = seg_list->subs[num];
948
SeparateSegs(A, part, lefts, rights, cut_list);
950
if (A->real_num + A->mini_num > 0)
951
InternalError("SeparateSegs: child %d not empty !", num);
954
seg_list->subs[num] = NULL;
958
seg_list->real_num = seg_list->mini_num = 0;
962
static void FindLimitWorker(superblock_t *block, bbox_t *bbox)
967
for (cur=block->segs; cur; cur=cur->next)
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;
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));
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;
985
// recursive handle sub-blocks
987
for (num=0; num < 2; num++)
989
if (block->subs[num])
990
FindLimitWorker(block->subs[num], bbox);
997
// Find the limits from a list of segs, by stepping through the segs
998
// and comparing the vertices at both ends.
1000
void FindLimits(superblock_t *seg_list, bbox_t *bbox)
1002
bbox->minx = bbox->miny = SHRT_MAX;
1003
bbox->maxx = bbox->maxy = SHRT_MIN;
1005
FindLimitWorker(seg_list, bbox);
1012
void AddMinisegs(seg_t *part,
1013
superblock_t *left_list, superblock_t *right_list,
1014
intersection_t *cut_list)
1016
intersection_t *cur, *next;
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);
1027
for (cur=cut_list; cur; cur=cur->next)
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,
1032
cur->before ? cur->before->index : -1,
1033
cur->after ? cur->after->index : -1,
1034
cur->self_ref ? "SELFREF" : "");
1038
// STEP 1: fix problems the intersection list...
1045
float_g len = next->along_dist - cur->along_dist;
1048
InternalError("Bad order in intersect list: %1.3f > %1.3f\n",
1049
cur->along_dist, next->along_dist);
1058
if (len > DIST_EPSILON)
1060
PrintMiniWarn("Skipping very short seg (len=%1.3f) near (%1.1f,%1.1f)\n",
1061
len, cur->vertex->x, cur->vertex->y);
1064
// merge the two intersections into one
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,
1072
next->vertex->x, next->vertex->y,
1073
next->before ? next->before->index : -1,
1074
next->after ? next->after->index : -1);
1077
if (cur->self_ref && !next->self_ref)
1079
if (cur->before && next->before)
1080
cur->before = next->before;
1082
if (cur->after && next->after)
1083
cur->after = next->after;
1085
cur->self_ref = FALSE;
1088
if (!cur->before && next->before)
1089
cur->before = next->before;
1091
if (!cur->after && next->after)
1092
cur->after = next->after;
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" : "");
1102
// free the unused cut
1104
cur->next = next->next;
1106
next->next = quick_alloc_cuts;
1107
quick_alloc_cuts = next;
1112
// STEP 2: find connections in the intersection list...
1114
for (cur = cut_list; cur && cur->next; cur = cur->next)
1118
if (!cur->after && !next->before)
1121
// check for some nasty OPEN/CLOSED or CLOSED/OPEN cases
1122
if (cur->after && !next->before)
1124
if (!cur->self_ref && !cur->after->warned_unclosed)
1126
PrintMiniWarn("Sector #%d is unclosed near (%1.1f,%1.1f)\n",
1128
(cur->vertex->x + next->vertex->x) / 2.0,
1129
(cur->vertex->y + next->vertex->y) / 2.0);
1130
cur->after->warned_unclosed = 1;
1134
else if (!cur->after && next->before)
1136
if (!next->self_ref && !next->before->warned_unclosed)
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;
1147
// righteo, here we have definite open space.
1148
// do a sanity check on the sectors (just for good measure).
1150
if (cur->after != next->before)
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);
1157
// choose the non-self-referencing sector when we can
1158
if (cur->self_ref && !next->self_ref)
1160
cur->after = next->before;
1164
// create the miniseg pair
1168
seg->partner = buddy;
1169
buddy->partner = seg;
1171
seg->start = cur->vertex;
1172
seg->end = next->vertex;
1174
buddy->start = next->vertex;
1175
buddy->end = cur->vertex;
1177
// leave 'linedef' field as NULL.
1178
// leave 'side' as zero too (not needed for minisegs).
1180
seg->sector = buddy->sector = cur->after;
1182
seg->index = buddy->index = -1;
1184
seg->source_line = buddy->source_line = part->linedef;
1187
RecomputeSeg(buddy);
1189
// add the new segs to the appropriate lists
1190
AddSegToSuper(right_list, seg);
1191
AddSegToSuper(left_list, buddy);
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);
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);
1204
// free intersection structures into quick-alloc list
1208
cut_list = cur->next;
1210
cur->next = quick_alloc_cuts;
1211
quick_alloc_cuts = cur;