1 /*
2 ** nodebuild_utility.cpp
3 **
4 ** Miscellaneous node builder utility functions.
5 **
6 **---------------------------------------------------------------------------
7 ** Copyright 2002-2006 Randy Heit
8 ** All rights reserved.
9 **
10 ** Redistribution and use in source and binary forms, with or without
11 ** modification, are permitted provided that the following conditions
12 ** are met:
13 **
14 ** 1. Redistributions of source code must retain the above copyright
15 ** notice, this list of conditions and the following disclaimer.
16 ** 2. Redistributions in binary form must reproduce the above copyright
17 ** notice, this list of conditions and the following disclaimer in the
18 ** documentation and/or other materials provided with the distribution.
19 ** 3. The name of the author may not be used to endorse or promote products
20 ** derived from this software without specific prior written permission.
21 ** 4. When not used as part of ZDoom or a ZDoom derivative, this code will be
22 ** covered by the terms of the GNU General Public License as published by
23 ** the Free Software Foundation; either version 2 of the License, or (at
24 ** your option) any later version.
25 **
26 ** THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
27 ** IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
28 ** OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
29 ** IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
30 ** INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
31 ** NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
32 ** DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
33 ** THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
34 ** (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
35 ** THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
36 **---------------------------------------------------------------------------
37 **
38 */
39
40 #include <stdlib.h>
41 #ifdef _MSC_VER
42 #include <malloc.h>
43 #endif
44 #include <string.h>
45 #include <stdio.h>
46
47 #include "nodebuild.h"
48 #include "templates.h"
49 #include "m_bbox.h"
50 #include "i_system.h"
51 #include "po_man.h"
52 #include "r_state.h"
53
54 static const int PO_LINE_START = 1;
55 static const int PO_LINE_EXPLICIT = 5;
56
57 #if 0
58 #define D(x) x
59 #else
60 #define D(x) do{}while(0)
61 #endif
62
63 #if 0
64 #define P(x) x
65 #else
66 #define P(x) do{}while(0)
67 #endif
68
PointToAngle(fixed_t x,fixed_t y)69 angle_t FNodeBuilder::PointToAngle (fixed_t x, fixed_t y)
70 {
71 const double rad2bam = double(1<<30) / M_PI;
72 #if defined __APPLE__ && !defined __llvm__
73 // Work-around for vectorization issue in Apple's GCC 4.x
74 // See https://gcc.gnu.org/wiki/Math_Optimization_Flags for details
75 long double ang = atan2l (double(y), double(x));
76 #else // !__APPLE__ || __llvm__
77 double ang = atan2 (double(y), double(x));
78 #endif // __APPLE__ && !__llvm__
79 // Convert to signed first since negative double to unsigned is undefined.
80 return angle_t(int(ang * rad2bam)) << 1;
81 }
82
FindUsedVertices(vertex_t * oldverts,int max)83 void FNodeBuilder::FindUsedVertices (vertex_t *oldverts, int max)
84 {
85 int *map = new int[max];
86 int i;
87 FPrivVert newvert;
88
89 memset (&map[0], -1, sizeof(int)*max);
90
91 for (i = 0; i < Level.NumLines; ++i)
92 {
93 ptrdiff_t v1 = Level.Lines[i].v1 - oldverts;
94 ptrdiff_t v2 = Level.Lines[i].v2 - oldverts;
95
96 if (map[v1] == -1)
97 {
98 newvert.x = oldverts[v1].x;
99 newvert.y = oldverts[v1].y;
100 map[v1] = VertexMap->SelectVertexExact (newvert);
101 }
102 if (map[v2] == -1)
103 {
104 newvert.x = oldverts[v2].x;
105 newvert.y = oldverts[v2].y;
106 map[v2] = VertexMap->SelectVertexExact (newvert);
107 }
108
109 Level.Lines[i].v1 = (vertex_t *)(size_t)map[v1];
110 Level.Lines[i].v2 = (vertex_t *)(size_t)map[v2];
111 }
112 OldVertexTable = map;
113 }
114
115 // Retrieves the original vertex -> current vertex table.
116 // Doing so prevents the node builder from freeing it.
117
GetOldVertexTable()118 const int *FNodeBuilder::GetOldVertexTable()
119 {
120 int *table = OldVertexTable;
121 OldVertexTable = NULL;
122 return table;
123 }
124
125 // For every sidedef in the map, create a corresponding seg.
126
MakeSegsFromSides()127 void FNodeBuilder::MakeSegsFromSides ()
128 {
129 int i, j;
130
131 if (Level.NumLines == 0)
132 {
133 I_Error ("Map is empty.\n");
134 }
135
136 for (i = 0; i < Level.NumLines; ++i)
137 {
138 if (Level.Lines[i].sidedef[0] != NULL)
139 {
140 CreateSeg (i, 0);
141 }
142 else
143 {
144 Printf ("Linedef %d does not have a front side.\n", i);
145 }
146
147 if (Level.Lines[i].sidedef[1] != NULL)
148 {
149 j = CreateSeg (i, 1);
150 if (Level.Lines[i].sidedef[0] != NULL)
151 {
152 Segs[j-1].partner = j;
153 Segs[j].partner = j-1;
154 }
155 }
156 }
157 }
158
CreateSeg(int linenum,int sidenum)159 int FNodeBuilder::CreateSeg (int linenum, int sidenum)
160 {
161 FPrivSeg seg;
162 int segnum;
163
164 seg.next = DWORD_MAX;
165 seg.loopnum = 0;
166 seg.partner = DWORD_MAX;
167 seg.hashnext = NULL;
168 seg.planefront = false;
169 seg.planenum = DWORD_MAX;
170 seg.storedseg = DWORD_MAX;
171
172 if (sidenum == 0)
173 { // front
174 seg.frontsector = Level.Lines[linenum].frontsector;
175 seg.backsector = Level.Lines[linenum].backsector;
176 seg.v1 = (int)(size_t)Level.Lines[linenum].v1;
177 seg.v2 = (int)(size_t)Level.Lines[linenum].v2;
178 }
179 else
180 { // back
181 seg.frontsector = Level.Lines[linenum].backsector;
182 seg.backsector = Level.Lines[linenum].frontsector;
183 seg.v2 = (int)(size_t)Level.Lines[linenum].v1;
184 seg.v1 = (int)(size_t)Level.Lines[linenum].v2;
185 }
186 seg.linedef = linenum;
187 side_t *sd = Level.Lines[linenum].sidedef[sidenum];
188 seg.sidedef = sd != NULL? int(sd - sides) : int(NO_SIDE);
189 seg.nextforvert = Vertices[seg.v1].segs;
190 seg.nextforvert2 = Vertices[seg.v2].segs2;
191
192 segnum = (int)Segs.Push (seg);
193 Vertices[seg.v1].segs = segnum;
194 Vertices[seg.v2].segs2 = segnum;
195 D(Printf(PRINT_LOG, "Seg %4d: From line %d, side %s (%5d,%5d)-(%5d,%5d) [%08x,%08x]-[%08x,%08x]\n", segnum, linenum, sidenum ? "back " : "front",
196 Vertices[seg.v1].x>>16, Vertices[seg.v1].y>>16, Vertices[seg.v2].x>>16, Vertices[seg.v2].y>>16,
197 Vertices[seg.v1].x, Vertices[seg.v1].y, Vertices[seg.v2].x, Vertices[seg.v2].y));
198
199 return segnum;
200 }
201
202 // For every seg, create FPrivSegs and FPrivVerts.
203
AddSegs(seg_t * segs,int numsegs)204 void FNodeBuilder::AddSegs(seg_t *segs, int numsegs)
205 {
206 assert(numsegs > 0);
207
208 for (int i = 0; i < numsegs; ++i)
209 {
210 FPrivSeg seg;
211 FPrivVert vert;
212 int segnum;
213
214 seg.next = DWORD_MAX;
215 seg.loopnum = 0;
216 seg.partner = DWORD_MAX;
217 seg.hashnext = NULL;
218 seg.planefront = false;
219 seg.planenum = DWORD_MAX;
220 seg.storedseg = DWORD_MAX;
221
222 seg.frontsector = segs[i].frontsector;
223 seg.backsector = segs[i].backsector;
224 vert.x = segs[i].v1->x;
225 vert.y = segs[i].v1->y;
226 seg.v1 = VertexMap->SelectVertexExact(vert);
227 vert.x = segs[i].v2->x;
228 vert.y = segs[i].v2->y;
229 seg.v2 = VertexMap->SelectVertexExact(vert);
230 seg.linedef = int(segs[i].linedef - Level.Lines);
231 seg.sidedef = segs[i].sidedef != NULL ? int(segs[i].sidedef - Level.Sides) : int(NO_SIDE);
232 seg.nextforvert = Vertices[seg.v1].segs;
233 seg.nextforvert2 = Vertices[seg.v2].segs2;
234
235 segnum = (int)Segs.Push(seg);
236 Vertices[seg.v1].segs = segnum;
237 Vertices[seg.v2].segs2 = segnum;
238 }
239 }
240
AddPolySegs(FPolySeg * segs,int numsegs)241 void FNodeBuilder::AddPolySegs(FPolySeg *segs, int numsegs)
242 {
243 assert(numsegs > 0);
244
245 for (int i = 0; i < numsegs; ++i)
246 {
247 FPrivSeg seg;
248 FPrivVert vert;
249 int segnum;
250
251 seg.next = DWORD_MAX;
252 seg.loopnum = 0;
253 seg.partner = DWORD_MAX;
254 seg.hashnext = NULL;
255 seg.planefront = false;
256 seg.planenum = DWORD_MAX;
257 seg.storedseg = DWORD_MAX;
258
259 side_t *side = segs[i].wall;
260 assert(side != NULL);
261
262 seg.frontsector = side->sector;
263 seg.backsector = side->linedef->frontsector == side->sector ? side->linedef->backsector : side->linedef->frontsector;
264 vert.x = segs[i].v1.x;
265 vert.y = segs[i].v1.y;
266 seg.v1 = VertexMap->SelectVertexExact(vert);
267 vert.x = segs[i].v2.x;
268 vert.y = segs[i].v2.y;
269 seg.v2 = VertexMap->SelectVertexExact(vert);
270 seg.linedef = int(side->linedef - Level.Lines);
271 seg.sidedef = int(side - Level.Sides);
272 seg.nextforvert = Vertices[seg.v1].segs;
273 seg.nextforvert2 = Vertices[seg.v2].segs2;
274
275 segnum = (int)Segs.Push(seg);
276 Vertices[seg.v1].segs = segnum;
277 Vertices[seg.v2].segs2 = segnum;
278 }
279 }
280
281
282 // Group colinear segs together so that only one seg per line needs to be checked
283 // by SelectSplitter().
284
GroupSegPlanes()285 void FNodeBuilder::GroupSegPlanes ()
286 {
287 const int bucketbits = 12;
288 FPrivSeg *buckets[1<<bucketbits] = { 0 };
289 int i, planenum;
290
291 for (i = 0; i < (int)Segs.Size(); ++i)
292 {
293 FPrivSeg *seg = &Segs[i];
294 seg->next = i+1;
295 seg->hashnext = NULL;
296 }
297
298 Segs[Segs.Size()-1].next = DWORD_MAX;
299
300 for (i = planenum = 0; i < (int)Segs.Size(); ++i)
301 {
302 FPrivSeg *seg = &Segs[i];
303 fixed_t x1 = Vertices[seg->v1].x;
304 fixed_t y1 = Vertices[seg->v1].y;
305 fixed_t x2 = Vertices[seg->v2].x;
306 fixed_t y2 = Vertices[seg->v2].y;
307 angle_t ang = PointToAngle (x2 - x1, y2 - y1);
308
309 if (ang >= 1u<<31)
310 ang += 1u<<31;
311
312 FPrivSeg *check = buckets[ang >>= 31-bucketbits];
313
314 while (check != NULL)
315 {
316 fixed_t cx1 = Vertices[check->v1].x;
317 fixed_t cy1 = Vertices[check->v1].y;
318 fixed_t cdx = Vertices[check->v2].x - cx1;
319 fixed_t cdy = Vertices[check->v2].y - cy1;
320 if (PointOnSide (x1, y1, cx1, cy1, cdx, cdy) == 0 &&
321 PointOnSide (x2, y2, cx1, cy1, cdx, cdy) == 0)
322 {
323 break;
324 }
325 check = check->hashnext;
326 }
327 if (check != NULL)
328 {
329 seg->planenum = check->planenum;
330 const FSimpleLine *line = &Planes[seg->planenum];
331 if (line->dx != 0)
332 {
333 if ((line->dx > 0 && x2 > x1) || (line->dx < 0 && x2 < x1))
334 {
335 seg->planefront = true;
336 }
337 else
338 {
339 seg->planefront = false;
340 }
341 }
342 else
343 {
344 if ((line->dy > 0 && y2 > y1) || (line->dy < 0 && y2 < y1))
345 {
346 seg->planefront = true;
347 }
348 else
349 {
350 seg->planefront = false;
351 }
352 }
353 }
354 else
355 {
356 seg->hashnext = buckets[ang];
357 buckets[ang] = seg;
358 seg->planenum = planenum++;
359 seg->planefront = true;
360
361 FSimpleLine pline = { Vertices[seg->v1].x,
362 Vertices[seg->v1].y,
363 Vertices[seg->v2].x - Vertices[seg->v1].x,
364 Vertices[seg->v2].y - Vertices[seg->v1].y };
365 Planes.Push (pline);
366 }
367 }
368
369 D(Printf ("%d planes from %d segs\n", planenum, Segs.Size()));
370
371 PlaneChecked.Reserve ((planenum + 7) / 8);
372 }
373
374 // Just create one plane per seg. Should be good enough for mini BSPs.
GroupSegPlanesSimple()375 void FNodeBuilder::GroupSegPlanesSimple()
376 {
377 Planes.Resize(Segs.Size());
378 for (int i = 0; i < (int)Segs.Size(); ++i)
379 {
380 FPrivSeg *seg = &Segs[i];
381 FSimpleLine *pline = &Planes[i];
382 seg->next = i+1;
383 seg->hashnext = NULL;
384 seg->planenum = i;
385 seg->planefront = true;
386 pline->x = Vertices[seg->v1].x;
387 pline->y = Vertices[seg->v1].y;
388 pline->dx = Vertices[seg->v2].x - Vertices[seg->v1].x;
389 pline->dy = Vertices[seg->v2].y - Vertices[seg->v1].y;
390 }
391 Segs.Last().next = DWORD_MAX;
392 PlaneChecked.Reserve((Segs.Size() + 7) / 8);
393 }
394
395 // Find "loops" of segs surrounding polyobject's origin. Note that a polyobject's origin
396 // is not solely defined by the polyobject's anchor, but also by the polyobject itself.
397 // For the split avoidance to work properly, you must have a convex, complete loop of
398 // segs surrounding the polyobject origin. All the maps in hexen.wad have complete loops of
399 // segs around their polyobjects, but they are not all convex: The doors at the start of MAP01
400 // and some of the pillars in MAP02 that surround the entrance to MAP06 are not convex.
401 // Heuristic() uses some special weighting to make these cases work properly.
402
FindPolyContainers(TArray<FPolyStart> & spots,TArray<FPolyStart> & anchors)403 void FNodeBuilder::FindPolyContainers (TArray<FPolyStart> &spots, TArray<FPolyStart> &anchors)
404 {
405 int loop = 1;
406
407 for (unsigned int i = 0; i < spots.Size(); ++i)
408 {
409 FPolyStart *spot = &spots[i];
410 fixed_t bbox[4];
411
412 if (GetPolyExtents (spot->polynum, bbox))
413 {
414 FPolyStart *anchor = NULL;
415
416 unsigned int j;
417
418 for (j = 0; j < anchors.Size(); ++j)
419 {
420 anchor = &anchors[j];
421 if (anchor->polynum == spot->polynum)
422 {
423 break;
424 }
425 }
426
427 if (j < anchors.Size())
428 {
429 vertex_t mid;
430 vertex_t center;
431
432 mid.x = bbox[BOXLEFT] + (bbox[BOXRIGHT]-bbox[BOXLEFT])/2;
433 mid.y = bbox[BOXBOTTOM] + (bbox[BOXTOP]-bbox[BOXBOTTOM])/2;
434
435 center.x = mid.x - anchor->x + spot->x;
436 center.y = mid.y - anchor->y + spot->y;
437
438 // Scan right for the seg closest to the polyobject's center after it
439 // gets moved to its start spot.
440 fixed_t closestdist = FIXED_MAX;
441 unsigned int closestseg = UINT_MAX;
442
443 P(Printf ("start %d,%d -- center %d, %d\n", spot->x>>16, spot->y>>16, center.x>>16, center.y>>16));
444
445 for (unsigned int j = 0; j < Segs.Size(); ++j)
446 {
447 FPrivSeg *seg = &Segs[j];
448 FPrivVert *v1 = &Vertices[seg->v1];
449 FPrivVert *v2 = &Vertices[seg->v2];
450 fixed_t dy = v2->y - v1->y;
451
452 if (dy == 0)
453 { // Horizontal, so skip it
454 continue;
455 }
456 if ((v1->y < center.y && v2->y < center.y) || (v1->y > center.y && v2->y > center.y))
457 { // Not crossed
458 continue;
459 }
460
461 fixed_t dx = v2->x - v1->x;
462
463 if (PointOnSide (center.x, center.y, v1->x, v1->y, dx, dy) <= 0)
464 {
465 fixed_t t = DivScale30 (center.y - v1->y, dy);
466 fixed_t sx = v1->x + MulScale30 (dx, t);
467 fixed_t dist = sx - spot->x;
468
469 if (dist < closestdist && dist >= 0)
470 {
471 closestdist = dist;
472 closestseg = (long)j;
473 }
474 }
475 }
476 if (closestseg != UINT_MAX)
477 {
478 loop = MarkLoop (closestseg, loop);
479 P(Printf ("Found polyobj in sector %d (loop %d)\n", Segs[closestseg].frontsector,
480 Segs[closestseg].loopnum));
481 }
482 }
483 }
484 }
485 }
486
MarkLoop(DWORD firstseg,int loopnum)487 int FNodeBuilder::MarkLoop (DWORD firstseg, int loopnum)
488 {
489 DWORD seg;
490 sector_t *sec = Segs[firstseg].frontsector;
491
492 if (Segs[firstseg].loopnum != 0)
493 { // already marked
494 return loopnum;
495 }
496
497 seg = firstseg;
498
499 do
500 {
501 FPrivSeg *s1 = &Segs[seg];
502
503 s1->loopnum = loopnum;
504
505 P(Printf ("Mark seg %d (%d,%d)-(%d,%d)\n", seg,
506 Vertices[s1->v1].x>>16, Vertices[s1->v1].y>>16,
507 Vertices[s1->v2].x>>16, Vertices[s1->v2].y>>16));
508
509 DWORD bestseg = DWORD_MAX;
510 DWORD tryseg = Vertices[s1->v2].segs;
511 angle_t bestang = ANGLE_MAX;
512 angle_t ang1 = PointToAngle (Vertices[s1->v2].x - Vertices[s1->v1].x,
513 Vertices[s1->v2].y - Vertices[s1->v1].y);
514
515 while (tryseg != DWORD_MAX)
516 {
517 FPrivSeg *s2 = &Segs[tryseg];
518
519 if (s2->frontsector == sec)
520 {
521 angle_t ang2 = PointToAngle (Vertices[s2->v1].x - Vertices[s2->v2].x,
522 Vertices[s2->v1].y - Vertices[s2->v2].y);
523 angle_t angdiff = ang2 - ang1;
524
525 if (angdiff < bestang && angdiff > 0)
526 {
527 bestang = angdiff;
528 bestseg = tryseg;
529 }
530 }
531 tryseg = s2->nextforvert;
532 }
533
534 seg = bestseg;
535 } while (seg != DWORD_MAX && Segs[seg].loopnum == 0);
536
537 return loopnum + 1;
538 }
539
540 // Find the bounding box for a specific polyobject.
541
GetPolyExtents(int polynum,fixed_t bbox[4])542 bool FNodeBuilder::GetPolyExtents (int polynum, fixed_t bbox[4])
543 {
544 unsigned int i;
545
546 bbox[BOXLEFT] = bbox[BOXBOTTOM] = FIXED_MAX;
547 bbox[BOXRIGHT] = bbox[BOXTOP] = FIXED_MIN;
548
549 // Try to find a polyobj marked with a start line
550 for (i = 0; i < Segs.Size(); ++i)
551 {
552 if (Level.Lines[Segs[i].linedef].special == PO_LINE_START &&
553 Level.Lines[Segs[i].linedef].args[0] == polynum)
554 {
555 break;
556 }
557 }
558
559 if (i < Segs.Size())
560 {
561 vertex_t start;
562 unsigned int vert;
563 unsigned int count = 0;
564
565 vert = Segs[i].v1;
566
567 start.x = Vertices[vert].x;
568 start.y = Vertices[vert].y;
569
570 do
571 {
572 AddSegToBBox (bbox, &Segs[i]);
573 vert = Segs[i].v2;
574 i = Vertices[vert].segs;
575 count++; // to prevent endless loops. Stop when this reaches the number of segs.
576 } while (i != DWORD_MAX && (Vertices[vert].x != start.x || Vertices[vert].y != start.y) && count < Segs.Size());
577
578 return true;
579 }
580
581 // Try to find a polyobj marked with explicit lines
582 bool found = false;
583
584 for (i = 0; i < Segs.Size(); ++i)
585 {
586 if (Level.Lines[Segs[i].linedef].special == PO_LINE_EXPLICIT &&
587 Level.Lines[Segs[i].linedef].args[0] == polynum)
588 {
589 AddSegToBBox (bbox, &Segs[i]);
590 found = true;
591 }
592 }
593 return found;
594 }
595
AddSegToBBox(fixed_t bbox[4],const FPrivSeg * seg)596 void FNodeBuilder::AddSegToBBox (fixed_t bbox[4], const FPrivSeg *seg)
597 {
598 FPrivVert *v1 = &Vertices[seg->v1];
599 FPrivVert *v2 = &Vertices[seg->v2];
600
601 if (v1->x < bbox[BOXLEFT]) bbox[BOXLEFT] = v1->x;
602 if (v1->x > bbox[BOXRIGHT]) bbox[BOXRIGHT] = v1->x;
603 if (v1->y < bbox[BOXBOTTOM]) bbox[BOXBOTTOM] = v1->y;
604 if (v1->y > bbox[BOXTOP]) bbox[BOXTOP] = v1->y;
605
606 if (v2->x < bbox[BOXLEFT]) bbox[BOXLEFT] = v2->x;
607 if (v2->x > bbox[BOXRIGHT]) bbox[BOXRIGHT] = v2->x;
608 if (v2->y < bbox[BOXBOTTOM]) bbox[BOXBOTTOM] = v2->y;
609 if (v2->y > bbox[BOXTOP]) bbox[BOXTOP] = v2->y;
610 }
611
FindMapBounds()612 void FNodeBuilder::FLevel::FindMapBounds ()
613 {
614 fixed_t minx, maxx, miny, maxy;
615
616 minx = maxx = Vertices[0].x;
617 miny = maxy = Vertices[0].y;
618
619 for (int i = 1; i < NumVertices; ++i)
620 {
621 if (Vertices[i].x < minx) minx = Vertices[i].x;
622 else if (Vertices[i].x > maxx) maxx = Vertices[i].x;
623 if (Vertices[i].y < miny) miny = Vertices[i].y;
624 else if (Vertices[i].y > maxy) maxy = Vertices[i].y;
625 }
626
627 MinX = minx;
628 MinY = miny;
629 MaxX = maxx;
630 MaxY = maxy;
631 }
632
~IVertexMap()633 FNodeBuilder::IVertexMap::~IVertexMap()
634 {
635 }
636
FVertexMap(FNodeBuilder & builder,fixed_t minx,fixed_t miny,fixed_t maxx,fixed_t maxy)637 FNodeBuilder::FVertexMap::FVertexMap (FNodeBuilder &builder,
638 fixed_t minx, fixed_t miny, fixed_t maxx, fixed_t maxy)
639 : MyBuilder(builder)
640 {
641 MinX = minx;
642 MinY = miny;
643 BlocksWide = int(((double(maxx) - minx + 1) + (BLOCK_SIZE - 1)) / BLOCK_SIZE);
644 BlocksTall = int(((double(maxy) - miny + 1) + (BLOCK_SIZE - 1)) / BLOCK_SIZE);
645 MaxX = MinX + BlocksWide * BLOCK_SIZE - 1;
646 MaxY = MinY + BlocksTall * BLOCK_SIZE - 1;
647 VertexGrid = new TArray<int>[BlocksWide * BlocksTall];
648 }
649
~FVertexMap()650 FNodeBuilder::FVertexMap::~FVertexMap ()
651 {
652 delete[] VertexGrid;
653 }
654
SelectVertexExact(FNodeBuilder::FPrivVert & vert)655 int FNodeBuilder::FVertexMap::SelectVertexExact (FNodeBuilder::FPrivVert &vert)
656 {
657 TArray<int> &block = VertexGrid[GetBlock (vert.x, vert.y)];
658 FPrivVert *vertices = &MyBuilder.Vertices[0];
659 unsigned int i;
660
661 for (i = 0; i < block.Size(); ++i)
662 {
663 if (vertices[block[i]].x == vert.x && vertices[block[i]].y == vert.y)
664 {
665 return block[i];
666 }
667 }
668
669 // Not present: add it!
670 return InsertVertex (vert);
671 }
672
SelectVertexClose(FNodeBuilder::FPrivVert & vert)673 int FNodeBuilder::FVertexMap::SelectVertexClose (FNodeBuilder::FPrivVert &vert)
674 {
675 TArray<int> &block = VertexGrid[GetBlock (vert.x, vert.y)];
676 FPrivVert *vertices = &MyBuilder.Vertices[0];
677 unsigned int i;
678
679 for (i = 0; i < block.Size(); ++i)
680 {
681 #if VERTEX_EPSILON <= 1
682 if (vertices[block[i]].x == vert.x && vertices[block[i]].y == vert.y)
683 #else
684 if (abs(vertices[block[i]].x - vert.x) < VERTEX_EPSILON &&
685 abs(vertices[block[i]].y - vert.y) < VERTEX_EPSILON)
686 #endif
687 {
688 return block[i];
689 }
690 }
691
692 // Not present: add it!
693 return InsertVertex (vert);
694 }
695
InsertVertex(FNodeBuilder::FPrivVert & vert)696 int FNodeBuilder::FVertexMap::InsertVertex (FNodeBuilder::FPrivVert &vert)
697 {
698 int vertnum;
699
700 vert.segs = DWORD_MAX;
701 vert.segs2 = DWORD_MAX;
702 vertnum = (int)MyBuilder.Vertices.Push (vert);
703
704 // If a vertex is near a block boundary, then it will be inserted on
705 // both sides of the boundary so that SelectVertexClose can find
706 // it by checking in only one block.
707 fixed_t minx = MAX (MinX, vert.x - VERTEX_EPSILON);
708 fixed_t maxx = MIN (MaxX, vert.x + VERTEX_EPSILON);
709 fixed_t miny = MAX (MinY, vert.y - VERTEX_EPSILON);
710 fixed_t maxy = MIN (MaxY, vert.y + VERTEX_EPSILON);
711
712 int blk[4] =
713 {
714 GetBlock (minx, miny),
715 GetBlock (maxx, miny),
716 GetBlock (minx, maxy),
717 GetBlock (maxx, maxy)
718 };
719 unsigned int blkcount[4] =
720 {
721 VertexGrid[blk[0]].Size(),
722 VertexGrid[blk[1]].Size(),
723 VertexGrid[blk[2]].Size(),
724 VertexGrid[blk[3]].Size()
725 };
726 for (int i = 0; i < 4; ++i)
727 {
728 if (VertexGrid[blk[i]].Size() == blkcount[i])
729 {
730 VertexGrid[blk[i]].Push (vertnum);
731 }
732 }
733
734 return vertnum;
735 }
736
FVertexMapSimple(FNodeBuilder & builder)737 FNodeBuilder::FVertexMapSimple::FVertexMapSimple(FNodeBuilder &builder)
738 : MyBuilder(builder)
739 {
740 }
741
SelectVertexExact(FNodeBuilder::FPrivVert & vert)742 int FNodeBuilder::FVertexMapSimple::SelectVertexExact(FNodeBuilder::FPrivVert &vert)
743 {
744 FPrivVert *verts = &MyBuilder.Vertices[0];
745 unsigned int stop = MyBuilder.Vertices.Size();
746
747 for (unsigned int i = 0; i < stop; ++i)
748 {
749 if (verts[i].x == vert.x && verts[i].y == vert.y)
750 {
751 return i;
752 }
753 }
754 // Not present: add it!
755 return InsertVertex(vert);
756 }
757
SelectVertexClose(FNodeBuilder::FPrivVert & vert)758 int FNodeBuilder::FVertexMapSimple::SelectVertexClose(FNodeBuilder::FPrivVert &vert)
759 {
760 FPrivVert *verts = &MyBuilder.Vertices[0];
761 unsigned int stop = MyBuilder.Vertices.Size();
762
763 for (unsigned int i = 0; i < stop; ++i)
764 {
765 #if VERTEX_EPSILON <= 1
766 if (verts[i].x == vert.x && verts[i].y == y)
767 #else
768 if (abs(verts[i].x - vert.x) < VERTEX_EPSILON &&
769 abs(verts[i].y - vert.y) < VERTEX_EPSILON)
770 #endif
771 {
772 return i;
773 }
774 }
775 // Not present: add it!
776 return InsertVertex (vert);
777 }
778
InsertVertex(FNodeBuilder::FPrivVert & vert)779 int FNodeBuilder::FVertexMapSimple::InsertVertex (FNodeBuilder::FPrivVert &vert)
780 {
781 vert.segs = DWORD_MAX;
782 vert.segs2 = DWORD_MAX;
783 return (int)MyBuilder.Vertices.Push (vert);
784 }
785