1 //------------------------------------------------------------------------
2 // SECTOR SUBDIVISION
3 //------------------------------------------------------------------------
4 //
5 // Eureka DOOM Editor
6 //
7 // Copyright (C) 2006-2020 Andrew Apted
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 #include "main.h"
22
23 #include <algorithm>
24
25 #include "e_basis.h"
26 #include "e_hover.h"
27 #include "m_game.h"
28 #include "r_subdiv.h"
29
30
31 /* This file contains code for subdividing map sectors into a set
32 of polygons, and also the logic for caching these subdivisions
33 and rebuilding them whenever necessary.
34 */
35
36
sector_subdivision_c()37 sector_subdivision_c::sector_subdivision_c() :
38 polygons()
39 { }
40
~sector_subdivision_c()41 sector_subdivision_c::~sector_subdivision_c()
42 { }
43
Clear()44 void sector_subdivision_c::Clear()
45 {
46 polygons.clear();
47 }
48
49
AddPolygon(float lx1,float lx2,float low_y,float hx1,float hx2,float high_y)50 void sector_subdivision_c::AddPolygon(float lx1, float lx2, float low_y,
51 float hx1, float hx2, float high_y)
52 {
53 // determine if low or high are a single vertex
54 bool l_single = fabs(lx2 - lx1) < 0.2;
55 bool h_single = fabs(hx2 - hx1) < 0.2;
56
57 // skip a degenerate polygon
58 if (l_single && h_single)
59 return;
60
61 sector_polygon_t poly;
62
63 poly.count = (l_single || h_single) ? 3 : 4;
64
65 // add vertices in clockwise order
66 int pos = 0;
67
68 poly.mx[pos] = lx1;
69 poly.my[pos] = low_y;
70 pos++;
71
72 poly.mx[pos] = hx1;
73 poly.my[pos] = high_y;
74 pos++;
75
76 if (! h_single)
77 {
78 poly.mx[pos] = hx2;
79 poly.my[pos] = high_y;
80 pos++;
81 }
82
83 if (! l_single)
84 {
85 poly.mx[pos] = lx2;
86 poly.my[pos] = low_y;
87 pos++;
88 }
89
90 polygons.push_back(poly);
91 }
92
93
94 // this represents a segment of a linedef bounding a sector.
95 struct sector_edge_t
96 {
97 const LineDef * line;
98
99 // coordinates of line, possibly flipped.
100 // we always have: y1 <= y2.
101 int x1, y1;
102 int x2, y2;
103
104 // has the line been flipped (coordinates were swapped) ?
105 short flipped;
106
107 // what side this edge faces (SIDE_LEFT or SIDE_RIGHT)
108 short side;
109
110 // comparison for CMP_X
111 float cmp_x;
112
CalcXsector_edge_t113 float CalcX(float y) const
114 {
115 return x1 + (x2 - x1) * (float)(y - y1) / (float)(y2 - y1);
116 }
117
118 struct CMP_Y
119 {
operator ()sector_edge_t::CMP_Y120 inline bool operator() (const sector_edge_t &A, const sector_edge_t& B) const
121 {
122 // NULL not allowed here
123
124 return A.y1 < B.y1;
125 }
126 };
127
128 struct CMP_X
129 {
operator ()sector_edge_t::CMP_X130 inline bool operator() (const sector_edge_t *A, const sector_edge_t *B) const
131 {
132 // NULL is always > than a valid pointer
133
134 if (A == NULL)
135 return false;
136
137 if (B == NULL)
138 return true;
139
140 return A->cmp_x < B->cmp_x;
141 }
142 };
143 };
144
145
146 struct sector_extra_info_t
147 {
148 // these are < 0 when the sector has no lines
149 int first_line;
150 int last_line;
151
152 // these are random junk when sector has no lines
153 double bound_x1, bound_x2;
154 double bound_y1, bound_y2;
155
156 sector_subdivision_c sub;
157
158 sector_3dfloors_c floors;
159
160 // true when polygons have been built for this sector.
161 bool built;
162
Clearsector_extra_info_t163 void Clear()
164 {
165 first_line = last_line = -1;
166
167 bound_x1 = 32767;
168 bound_y1 = 32767;
169 bound_x2 = -32767;
170 bound_y2 = -32767;
171
172 sub.Clear();
173 floors.Clear();
174
175 built = false;
176 }
177
AddLinesector_extra_info_t178 void AddLine(int n)
179 {
180 if (first_line < 0 || first_line > n)
181 first_line = n;
182
183 if (last_line < n)
184 last_line = n;
185 }
186
AddVertexsector_extra_info_t187 void AddVertex(const Vertex *V)
188 {
189 bound_x1 = MIN(bound_x1, V->x());
190 bound_y1 = MIN(bound_y1, V->y());
191
192 bound_x2 = MAX(bound_x2, V->x());
193 bound_y2 = MAX(bound_y2, V->y());
194 }
195 };
196
197
198 class sector_info_cache_c
199 {
200 public:
201 int total;
202
203 std::vector<sector_extra_info_t> infos;
204
205 public:
sector_info_cache_c()206 sector_info_cache_c() : total(-1), infos()
207 { }
208
~sector_info_cache_c()209 ~sector_info_cache_c()
210 { }
211
212 public:
Update()213 void Update()
214 {
215 if (total != NumSectors)
216 {
217 total = NumSectors;
218
219 infos.resize((size_t) total);
220
221 Rebuild();
222 }
223 }
224
Rebuild()225 void Rebuild()
226 {
227 int sec;
228
229 for (sec = 0 ; sec < total ; sec++)
230 {
231 const Sector *S = Sectors[sec];
232
233 infos[sec].Clear();
234 infos[sec].floors.f_plane.Init(S->floorh);
235 infos[sec].floors.c_plane.Init(S->ceilh);
236 }
237
238 for (int n = 0 ; n < NumLineDefs ; n++)
239 {
240 const LineDef *L = LineDefs[n];
241
242 CheckBoom242(L);
243 CheckExtraFloor(L, n);
244 CheckLineSlope(L);
245
246 for (int side = 0 ; side < 2 ; side++)
247 {
248 int sd_num = side ? L->left : L->right;
249 if (sd_num < 0)
250 continue;
251
252 sec = SideDefs[sd_num]->sector;
253
254 sector_extra_info_t& info = infos[sec];
255
256 info.AddLine(n);
257
258 info.AddVertex(L->Start());
259 info.AddVertex(L->End());
260 }
261 }
262
263 for (int n = 0 ; n < NumThings ; n++)
264 {
265 CheckSlopeThing(Things[n]);
266 }
267 for (int n = 0 ; n < NumThings ; n++)
268 {
269 CheckSlopeCopyThing(Things[n]);
270 }
271
272 for (int n = 0 ; n < NumLineDefs ; n++)
273 {
274 CheckPlaneCopy(LineDefs[n]);
275 }
276 }
277
CheckBoom242(const LineDef * L)278 void CheckBoom242(const LineDef *L)
279 {
280 if (Features.gen_types && (L->type == 242 || L->type == 280))
281 { /* ok */ }
282 else if (Level_format != MAPF_Doom && L->type == 209)
283 { /* ok */ }
284 else
285 return;
286
287 if (L->tag <= 0 || L->right < 0)
288 return;
289
290 int dummy_sec = L->Right()->sector;
291
292 for (int n = 0 ; n < NumSectors ; n++)
293 {
294 if (Sectors[n]->tag == L->tag)
295 infos[n].floors.heightsec = dummy_sec;
296 }
297 }
298
CheckExtraFloor(const LineDef * L,int ld_num)299 void CheckExtraFloor(const LineDef *L, int ld_num)
300 {
301 if (L->tag <= 0 || L->right < 0)
302 return;
303
304 int flags = -1;
305 int sec_tag = L->tag;
306
307 // EDGE style
308 if (Level_format == MAPF_Doom && (Features.extra_floors & 1))
309 {
310 switch (L->type)
311 {
312 case 400: flags = 0; break;
313 case 401: flags = EXFL_UPPER; break;
314 case 402: flags = EXFL_LOWER; break;
315 case 403: flags = EXFL_BOTTOM; break; // liquid
316 case 413: flags = EXFL_BOTTOM; break; // thin and solid
317
318 case 404: case 405: case 406: case 407: case 408: // liquid
319 case 414: case 415: case 416: case 417: // thin and solid
320 flags = EXFL_BOTTOM | EXFL_TRANSLUC;
321 break;
322
323 default: break;
324 }
325 }
326
327 // Legacy style
328 if (Level_format == MAPF_Doom && (Features.extra_floors & 2))
329 {
330 switch (L->type)
331 {
332 case 281: flags = 0; break;
333 case 289: flags = 0; break;
334 case 300: flags = EXFL_TRANSLUC; break;
335 case 301: flags = EXFL_TOP | EXFL_TRANSLUC; break;
336 case 304: flags = EXFL_TOP; break;
337 case 306: flags = EXFL_TOP | EXFL_TRANSLUC; break; // invisible floor
338
339 default: break;
340 }
341 }
342
343 // ZDoom style
344 if (Level_format != MAPF_Doom && (Features.extra_floors & 4))
345 {
346 if (L->type != 160)
347 return;
348
349 flags = 0;
350
351 if ((L->arg2 & 3) == 0)
352 flags |= EXFL_VAVOOM;
353
354 if (L->arg3 & 8) flags |= EXFL_TOP;
355 if (L->arg3 & 16) flags |= EXFL_UPPER;
356 if (L->arg3 & 32) flags |= EXFL_LOWER;
357
358 if ((L->arg2 & 8) == 0)
359 sec_tag |= (L->arg5 << 8);
360 }
361
362 if (flags < 0)
363 return;
364
365 extrafloor_c EF;
366
367 EF.ld = ld_num;
368 EF.sd = L->right;
369 EF.flags = flags;
370
371 // find all matching sectors
372 for (int n = 0 ; n < NumSectors ; n++)
373 {
374 if (Sectors[n]->tag == sec_tag)
375 infos[n].floors.floors.push_back(EF);
376 }
377 }
378
CheckLineSlope(const LineDef * L)379 void CheckLineSlope(const LineDef *L)
380 {
381 // EDGE style
382 if (Level_format == MAPF_Doom && (Features.slopes & 1))
383 {
384 switch (L->type)
385 {
386 case 567: PlaneAlign(L, 2, 0); break;
387 case 568: PlaneAlign(L, 0, 2); break;
388 case 569: PlaneAlign(L, 2, 2); break;
389 default: break;
390 }
391 }
392
393 // Eternity style
394 if (Level_format == MAPF_Doom && (Features.slopes & 2))
395 {
396 switch (L->type)
397 {
398 case 386: PlaneAlign(L, 1, 0); break;
399 case 387: PlaneAlign(L, 0, 1); break;
400 case 388: PlaneAlign(L, 1, 1); break;
401 case 389: PlaneAlign(L, 2, 0); break;
402 case 390: PlaneAlign(L, 0, 2); break;
403 case 391: PlaneAlign(L, 2, 2); break;
404 case 392: PlaneAlign(L, 2, 1); break;
405 case 393: PlaneAlign(L, 1, 2); break;
406 default: break;
407 }
408 }
409
410 // Odamex and ZDoom style
411 if (Level_format == MAPF_Doom && (Features.slopes & 4))
412 {
413 switch (L->type)
414 {
415 case 340: PlaneAlign(L, 1, 0); break;
416 case 341: PlaneAlign(L, 0, 1); break;
417 case 342: PlaneAlign(L, 1, 1); break;
418 case 343: PlaneAlign(L, 2, 0); break;
419 case 344: PlaneAlign(L, 0, 2); break;
420 case 345: PlaneAlign(L, 2, 2); break;
421 case 346: PlaneAlign(L, 2, 1); break;
422 case 347: PlaneAlign(L, 1, 2); break;
423 default: break;
424 }
425 }
426
427 // ZDoom (in hexen format)
428 if (Level_format != MAPF_Doom && (Features.slopes & 8))
429 {
430 if (L->type == 181)
431 PlaneAlign(L, L->tag, L->arg2);
432 }
433 }
434
CheckPlaneCopy(const LineDef * L)435 void CheckPlaneCopy(const LineDef *L)
436 {
437 // Eternity style
438 if (Level_format == MAPF_Doom && (Features.slopes & 2))
439 {
440 switch (L->type)
441 {
442 case 394: PlaneCopy(L, L->tag, 0, 0, 0, 0); break;
443 case 395: PlaneCopy(L, 0, L->tag, 0, 0, 0); break;
444 case 396: PlaneCopy(L, L->tag, L->tag, 0, 0, 0); break;
445 default: break;
446 }
447 }
448
449 // ZDoom (in hexen format)
450 if (Level_format != MAPF_Doom && (Features.slopes & 8))
451 {
452 if (L->type == 118)
453 PlaneCopy(L, L->tag, L->arg2, L->arg3, L->arg4, L->arg5);
454 }
455 }
456
CheckSlopeThing(const Thing * T)457 void CheckSlopeThing(const Thing *T)
458 {
459 if (Level_format != MAPF_Doom && (Features.slopes & 16))
460 {
461 switch (T->type)
462 {
463 // TODO 1500, 1501 Vavoom style
464 // TODO 1504, 1505 Vertex height (triangle sectors)
465 // TODO 9500, 9501 Line slope things
466
467 case 9502: PlaneTiltByThing(T, 0); break;
468 case 9503: PlaneTiltByThing(T, 1); break;
469 default: break;
470 }
471 }
472 }
473
CheckSlopeCopyThing(const Thing * T)474 void CheckSlopeCopyThing(const Thing *T)
475 {
476 if (Level_format != MAPF_Doom && (Features.slopes & 16))
477 {
478 switch (T->type)
479 {
480 case 9510: PlaneCopyFromThing(T, 0); break;
481 case 9511: PlaneCopyFromThing(T, 1); break;
482 default: break;
483 }
484 }
485 }
486
PlaneAlign(const LineDef * L,int floor_mode,int ceil_mode)487 void PlaneAlign(const LineDef *L, int floor_mode, int ceil_mode)
488 {
489 if (L->left < 0 || L->right < 0)
490 return;
491
492 // support undocumented special case from ZDoom
493 if (ceil_mode == 0 && (floor_mode & 0x0C) != 0)
494 ceil_mode = (floor_mode >> 2);
495
496 switch (floor_mode & 3)
497 {
498 case 1: PlaneAlignPart(L, SIDE_RIGHT, 0 /* floor */); break;
499 case 2: PlaneAlignPart(L, SIDE_LEFT, 0); break;
500 default: break;
501 }
502
503 switch (ceil_mode & 3)
504 {
505 case 1: PlaneAlignPart(L, SIDE_RIGHT, 1 /* ceil */); break;
506 case 2: PlaneAlignPart(L, SIDE_LEFT, 1); break;
507 default: break;
508 }
509 }
510
PlaneAlignPart(const LineDef * L,int side,int plane)511 void PlaneAlignPart(const LineDef *L, int side, int plane)
512 {
513 int sec_num = L->WhatSector(side);
514 const Sector *front = Sectors[L->WhatSector(side)];
515 const Sector *back = Sectors[L->WhatSector(-side)];
516
517 // find a vertex belonging to sector and is far from the line
518 const Vertex *v = NULL;
519 double best_dist = 0.1;
520
521 double lx1 = L->Start()->x();
522 double ly1 = L->Start()->y();
523 double lx2 = L->End()->x();
524 double ly2 = L->End()->y();
525
526 if (side < 0)
527 {
528 std::swap(lx1, lx2);
529 std::swap(ly1, ly2);
530 }
531
532 for (int n = 0 ; n < NumLineDefs ; n++)
533 {
534 const LineDef *L2 = LineDefs[n];
535 if (L2->TouchesSector(sec_num))
536 {
537 for (int pass = 0 ; pass < 2 ; pass++)
538 {
539 const Vertex *v2 = pass ? L2->End() : L2->Start();
540 double dist = PerpDist(v2->x(), v2->y(), lx1,ly1, lx2,ly2);
541
542 if (dist > best_dist)
543 {
544 v = v2;
545 best_dist = dist;
546 }
547 }
548 }
549 }
550
551 if (v == NULL)
552 return;
553
554 // compute point at 90 degrees to the linedef
555 double ldx = (ly2 - ly1);
556 double ldy = (lx1 - lx2);
557 double ldh = hypot(ldx, ldy);
558
559 double vx = lx1 + ldx * best_dist / ldh;
560 double vy = ly1 + ldy * best_dist / ldh;
561
562 if (plane > 0)
563 { // ceiling
564 SlopeFromLine(infos[sec_num].floors.c_plane,
565 lx1, ly1, back->ceilh, vx, vy, front->ceilh);
566 }
567 else
568 { // floor
569 SlopeFromLine(infos[sec_num].floors.f_plane,
570 lx1, ly1, back->floorh, vx, vy, front->floorh);
571 }
572 }
573
PlaneCopy(const LineDef * L,int f1_tag,int c1_tag,int f2_tag,int c2_tag,int share)574 void PlaneCopy(const LineDef *L, int f1_tag, int c1_tag, int f2_tag, int c2_tag, int share)
575 {
576 for (int n = 0 ; n < NumSectors ; n++)
577 {
578 if (f1_tag > 0 && Sectors[n]->tag == f1_tag && L->Right())
579 {
580 infos[L->Right()->sector].floors.f_plane.Copy(infos[n].floors.f_plane);
581 f1_tag = 0;
582 }
583 if (c1_tag > 0 && Sectors[n]->tag == c1_tag && L->Right())
584 {
585 infos[L->Right()->sector].floors.c_plane.Copy(infos[n].floors.c_plane);
586 c1_tag = 0;
587 }
588
589 if (f2_tag > 0 && Sectors[n]->tag == f2_tag && L->Left())
590 {
591 infos[L->Left()->sector].floors.f_plane.Copy(infos[n].floors.f_plane);
592 f2_tag = 0;
593 }
594 if (c2_tag > 0 && Sectors[n]->tag == c2_tag && L->Left())
595 {
596 infos[L->Left()->sector].floors.c_plane.Copy(infos[n].floors.c_plane);
597 c2_tag = 0;
598 }
599 }
600
601 if (L->left >= 0 && L->right >= 0)
602 {
603 int front_sec = L->Right()->sector;
604 int back_sec = L->Left()->sector;
605
606 switch (share & 3)
607 {
608 case 1: infos[ back_sec].floors.f_plane.Copy(infos[front_sec].floors.f_plane); break;
609 case 2: infos[front_sec].floors.f_plane.Copy(infos[ back_sec].floors.f_plane); break;
610 default: break;
611 }
612
613 switch (share & 12)
614 {
615 case 4: infos[ back_sec].floors.c_plane.Copy(infos[front_sec].floors.c_plane); break;
616 case 8: infos[front_sec].floors.c_plane.Copy(infos[ back_sec].floors.c_plane); break;
617 default: break;
618 }
619 }
620 }
621
PlaneCopyFromThing(const Thing * T,int plane)622 void PlaneCopyFromThing(const Thing *T, int plane)
623 {
624 if (T->arg1 == 0)
625 return;
626
627 // find sector containing the thing
628 Objid o;
629 GetNearObject(o, OBJ_SECTORS, T->x(), T->y());
630
631 if (!o.valid())
632 return;
633
634 for (int n = 0 ; n < NumSectors ; n++)
635 {
636 if (Sectors[n]->tag == T->arg1)
637 {
638 if (plane > 0)
639 infos[o.num].floors.c_plane.Copy(infos[n].floors.c_plane);
640 else
641 infos[o.num].floors.f_plane.Copy(infos[n].floors.f_plane);
642
643 return;
644 }
645 }
646 }
647
PlaneTiltByThing(const Thing * T,int plane)648 void PlaneTiltByThing(const Thing *T, int plane)
649 {
650 double tx = T->x();
651 double ty = T->y();
652
653 // find sector containing the thing
654 Objid o;
655 GetNearObject(o, OBJ_SECTORS, tx, ty);
656
657 if (!o.valid())
658 return;
659
660 sector_3dfloors_c *ex = &infos[o.num].floors;
661
662 double tz = ex->PlaneZ(plane ? -1 : +1, tx, ty) + T->h();
663
664 // vector for direction of thing
665 double tdx = cos(T->angle * M_PI / 180.0);
666 double tdy = sin(T->angle * M_PI / 180.0);
667
668 // get slope angle.
669 // when arg1 < 90, a point on plane in front of thing has lower Z.
670 int slope_ang = T->arg1 - 90;
671 slope_ang = CLAMP(-89, slope_ang, 89);
672
673 double az = sin(slope_ang * M_PI / 180.0);
674
675 // FIXME support tilting an existing slope
676 #if 1
677 tdx *= 128.0;
678 tdy *= 128.0;
679 az *= 128.0;
680
681 if (plane > 0)
682 SlopeFromLine(ex->c_plane, tx,ty,tz, tx+tdx, ty+tdy, tz+az);
683 else
684 SlopeFromLine(ex->f_plane, tx,ty,tz, tx+tdx, ty+tdy, tz+az);
685 #else
686 // get normal of existing plane
687 double nx, ny, nz;
688 if (plane == 0)
689 {
690 ex->f_plane.GetNormal(nx, ny, nz);
691 }
692 else
693 {
694 ex->c_plane.GetNormal(nx, ny, nz);
695 nx = -nx; ny = -ny; nz = -nz;
696 }
697 #endif
698 }
699
SlopeFromLine(slope_plane_c & pl,double x1,double y1,double z1,double x2,double y2,double z2)700 void SlopeFromLine(slope_plane_c& pl, double x1, double y1, double z1,
701 double x2, double y2, double z2)
702 {
703 double dx = x2 - x1;
704 double dy = y2 - y1;
705 double dz = z2 - z1;
706
707 if (fabs(dz) < 0.5)
708 return;
709
710 // make (dx dy) be a unit vector
711 double dlen = hypot(dx, dy);
712 dx /= dlen;
713 dy /= dlen;
714
715 // we want SlopeZ() to compute z1 at (x1 y1) and z2 at (x2 y2).
716 // assume xm = (dx * A) and ym = (dy * A) and zadd = B
717 // that leads to two simultaneous equations:
718 // x1 * dx * A + y1 * dy * A + B = z1
719 // x2 * dx * A + y2 * dy * A + B = z2
720 // which we need to solve for A and B....
721
722 double E = (x1 * dx + y1 * dy);
723 double F = (x2 * dx + y2 * dy);
724
725 double A = (z2 -z1) / (F - E);
726 double B = z1 - A * E;
727
728 pl.xm = dx * A;
729 pl.ym = dy * A;
730 pl.zadd = B;
731 pl.sloped = true;
732 }
733 };
734
735 static sector_info_cache_c sector_info_cache;
736
737
R_SubdivideSector(int num,sector_extra_info_t & exinfo)738 static void R_SubdivideSector(int num, sector_extra_info_t& exinfo)
739 {
740 if (exinfo.first_line < 0)
741 return;
742
743 /* DEBUG
744 fprintf(stderr, "R_SubdivideSector %d\n", num);
745 */
746
747 /*** Part 1 : visit linedefs and create edges ***/
748
749 std::vector<sector_edge_t> edgelist;
750
751 for (int n = exinfo.first_line ; n <= exinfo.last_line ; n++)
752 {
753 const LineDef *L = LineDefs[n];
754
755 if (! L->TouchesSector(num))
756 continue;
757
758 // ignore 2S lines with same sector on both sides
759 if (L->WhatSector(SIDE_LEFT) == L->WhatSector(SIDE_RIGHT))
760 continue;
761
762 sector_edge_t edge;
763
764 edge.x1 = L->Start()->x();
765 edge.y1 = L->Start()->y();
766 edge.x2 = L->End()->x();
767 edge.y2 = L->End()->y();
768
769 // skip purely horizontal lines
770 if (edge.y1 == edge.y2)
771 continue;
772
773 edge.line = L;
774 edge.flipped = 0;
775
776 if (edge.y1 > edge.y2)
777 {
778 std::swap(edge.x1, edge.x2);
779 std::swap(edge.y1, edge.y2);
780
781 edge.flipped = 1;
782 }
783
784 // compute side
785 bool is_right = (L->WhatSector(SIDE_RIGHT) == num);
786
787 if (edge.flipped)
788 is_right = !is_right;
789
790 edge.side = is_right ? SIDE_RIGHT : SIDE_LEFT;
791
792 /* DEBUG
793 fprintf(stderr, "Line %d mapped coords (%d %d) .. (%d %d) flipped:%d sec:%d/%d\n",
794 n, edge.x1, edge.y1, edge.x2, edge.y2, edge.flipped,
795 L->WhatSector(SIDE_RIGHT), L->WhatSector(SIDE_LEFT));
796 */
797
798 // add the edge
799 edgelist.push_back(edge);
800 }
801
802 if (edgelist.empty())
803 return;
804
805 // sort edges into vertical order (using 'y1' field)
806
807 std::sort(edgelist.begin(), edgelist.end(), sector_edge_t::CMP_Y());
808
809
810 /*** Part 2 : traverse edge list and create trapezoids ***/
811
812 std::vector<sector_edge_t *> active_edges;
813
814 if (edgelist.empty())
815 return;
816
817 unsigned int pos = 0;
818
819 // this Y is minimal (guaranteed by sorting the edgelist)
820 int low_y = edgelist[pos].y1;
821
822 for (;;)
823 {
824 // remove old edges from active list
825 for (unsigned int i = 0 ; i < active_edges.size() ; i++)
826 {
827 sector_edge_t *A = active_edges[i];
828
829 if (A != NULL && A->y2 <= low_y)
830 active_edges[i] = NULL;
831 }
832
833 // add new edges to active list
834 for ( ; pos < edgelist.size() && edgelist[pos].y1 == low_y ; pos++)
835 {
836 active_edges.push_back(&edgelist[pos]);
837 }
838
839 // find next highest Y
840 int high_y = (1 << 30);
841 int active_num = 0;
842
843 if (pos < edgelist.size())
844 high_y = edgelist[pos].y1;
845
846 for (unsigned int k = 0 ; k < active_edges.size() ; k++)
847 {
848 sector_edge_t *A = active_edges[k];
849
850 if (A != NULL)
851 {
852 active_num++;
853
854 if (A->y1 > low_y) high_y = MIN(high_y, A->y1);
855 if (A->y2 > low_y) high_y = MIN(high_y, A->y2);
856 }
857 }
858
859 /* DEBUG
860 fprintf(stderr, " active_num:%d low_y:%d high_y:%d\n", active_num, low_y, high_y);
861 */
862 if (active_num == 0)
863 {
864 while (pos < edgelist.size() && edgelist[pos].y1 <= low_y)
865 pos++;
866
867 // terminating condition : no more rows
868 if (pos >= edgelist.size())
869 break;
870
871 low_y = edgelist[pos].y1;
872 continue;
873 }
874
875 // compute a comparison X coordinate for each active edge
876 float mid_y = low_y + (high_y - low_y) * 0.5;
877
878 for (unsigned int k = 0 ; k < active_edges.size() ; k++)
879 {
880 sector_edge_t *A = active_edges[k];
881
882 if (A != NULL)
883 A->cmp_x = A->CalcX(mid_y);
884 }
885
886 // sort edges horizontally
887 std::sort(active_edges.begin(), active_edges.end(), sector_edge_t::CMP_X());
888
889 // remove NULLs
890 while (active_edges.size() > 0 && active_edges.back() == NULL)
891 active_edges.pop_back();
892
893 // visit pairs of edges
894 for (unsigned int i = 1 ; i < active_edges.size() ; i++)
895 {
896 const sector_edge_t * E1 = active_edges[i - 1];
897 const sector_edge_t * E2 = active_edges[i];
898 #if 1
899 if (E1 == NULL || E2 == NULL)
900 BugError("RenderSector: did not delete NULLs properly!\n");
901 #endif
902
903 /* DEBUG
904 fprintf(stderr, "E1 @ x=%1.2f side=%d | E2 @ x=%1.2f side=%d\n",
905 E1->cmp_x, E1->side, E2->cmp_x, E2->side);
906 */
907
908 if (! (E1->side == SIDE_RIGHT && E2->side == SIDE_LEFT))
909 continue;
910
911 // treat lines without a right side as dead
912 // [ NOTE that we don't ignore them ]
913 if (E1->line->right < 0) continue;
914 if (E2->line->right < 0) continue;
915
916 float lx1 = E1->CalcX(low_y);
917 float hx1 = E1->CalcX(high_y);
918
919 float lx2 = E2->CalcX(low_y);
920 float hx2 = E2->CalcX(high_y);
921
922 exinfo.sub.AddPolygon(lx1, lx2, low_y, hx1, hx2, high_y);
923 }
924
925 // ok, repeat process for next row
926 low_y = high_y;
927 }
928 }
929
930
Subdiv_InvalidateAll()931 void Subdiv_InvalidateAll()
932 {
933 // invalidate everything
934 sector_info_cache.total = -1;
935 }
936
937
Subdiv_SectorOnScreen(int num,double map_lx,double map_ly,double map_hx,double map_hy)938 bool Subdiv_SectorOnScreen(int num, double map_lx, double map_ly, double map_hx, double map_hy)
939 {
940 sector_info_cache.Update();
941
942 sector_extra_info_t& exinfo = sector_info_cache.infos[num];
943
944 if (exinfo.bound_x1 > map_hx || exinfo.bound_x2 < map_lx ||
945 exinfo.bound_y1 > map_hy || exinfo.bound_y2 < map_ly)
946 {
947 // sector is off-screen
948 return false;
949 }
950
951 return true;
952 }
953
954
Subdiv_PolygonsForSector(int num)955 sector_subdivision_c *Subdiv_PolygonsForSector(int num)
956 {
957 sector_info_cache.Update();
958
959 sector_extra_info_t& exinfo = sector_info_cache.infos[num];
960
961 if (! exinfo.built)
962 {
963 R_SubdivideSector(num, exinfo);
964 exinfo.built = true;
965 }
966
967 return &exinfo.sub;
968 }
969
970
971 //------------------------------------------------------------------------
972 // 3D Floor and Slope stuff
973 //------------------------------------------------------------------------
974
sector_3dfloors_c()975 sector_3dfloors_c::sector_3dfloors_c() :
976 heightsec(-1)
977 { }
978
~sector_3dfloors_c()979 sector_3dfloors_c::~sector_3dfloors_c()
980 { }
981
982
Clear()983 void sector_3dfloors_c::Clear()
984 {
985 heightsec = -1;
986 floors.clear();
987 f_plane.Init(-2);
988 c_plane.Init(-1);
989 }
990
991
extrafloor_c()992 extrafloor_c::extrafloor_c() : ld(-1), sd(-1), flags(0)
993 { }
994
~extrafloor_c()995 extrafloor_c::~extrafloor_c()
996 { }
997
998
slope_plane_c()999 slope_plane_c::slope_plane_c() : sloped(false), xm(0), ym(0), zadd(0)
1000 { }
1001
~slope_plane_c()1002 slope_plane_c::~slope_plane_c()
1003 { }
1004
Init(float height)1005 void slope_plane_c::Init(float height)
1006 {
1007 sloped = false;
1008 xm = ym = 0;
1009 zadd = height;
1010 }
1011
Copy(const slope_plane_c & other)1012 void slope_plane_c::Copy(const slope_plane_c& other)
1013 {
1014 sloped = other.sloped;
1015 xm = other.xm;
1016 ym = other.ym;
1017 zadd = other.zadd;
1018 }
1019
1020
Subdiv_3DFloorsForSector(int num)1021 sector_3dfloors_c *Subdiv_3DFloorsForSector(int num)
1022 {
1023 sector_info_cache.Update();
1024
1025 sector_extra_info_t& exinfo = sector_info_cache.infos[num];
1026
1027 return &exinfo.floors;
1028 }
1029
1030 //--- editor settings ---
1031 // vi:ts=4:sw=4:noexpandtab
1032