1 // SONIC ROBO BLAST 2
2 //-----------------------------------------------------------------------------
3 // Copyright (C) 1998-2000 by DooM Legacy Team.
4 //
5 // This program is free software distributed under the
6 // terms of the GNU General Public License, version 2.
7 // See the 'LICENSE' file for more details.
8 //-----------------------------------------------------------------------------
9 /// \file hw_bsp.c
10 /// \brief convert SRB2 map
11
12 #include "../doomdef.h"
13 #include "../doomstat.h"
14 #ifdef HWRENDER
15 #include "hw_glob.h"
16 #include "../r_local.h"
17 #include "../z_zone.h"
18 #include "../console.h"
19 #include "../v_video.h"
20 #include "../m_menu.h"
21 #include "../i_system.h"
22 #include "../m_argv.h"
23 #include "../i_video.h"
24 #include "../w_wad.h"
25 #include "../p_setup.h" // levelfadecol
26
27 // --------------------------------------------------------------------------
28 // This is global data for planes rendering
29 // --------------------------------------------------------------------------
30
31 extrasubsector_t *extrasubsectors = NULL;
32
33 // newsubsectors are subsectors without segs, added for the plane polygons
34 #define NEWSUBSECTORS 50
35 static size_t totsubsectors;
36 size_t addsubsector;
37
38 typedef struct
39 {
40 float x, y;
41 float dx, dy;
42 } fdivline_t;
43
44 // ==========================================================================
45 // FLOOR & CEILING CONVEX POLYS GENERATION
46 // ==========================================================================
47
48 //debug counters
49 static INT32 nobackpoly = 0;
50 static INT32 skipcut = 0;
51 static INT32 totalsubsecpolys = 0;
52
53 // --------------------------------------------------------------------------
54 // Polygon fast alloc / free
55 // --------------------------------------------------------------------------
56 //hurdler: quick fix for those who wants to play with larger wad
57
58 #define ZPLANALLOC
59 #ifndef ZPLANALLOC
60 //#define POLYPOOLSIZE 1024000 // may be much over what is needed
61 /// \todo check out how much is used
62 static size_t POLYPOOLSIZE = 1024000;
63
64 static UINT8 *gl_polypool = NULL;
65 static UINT8 *gl_ppcurrent;
66 static size_t gl_ppfree;
67 #endif
68
69 // only between levels, clear poly pool
HWR_ClearPolys(void)70 static void HWR_ClearPolys(void)
71 {
72 #ifndef ZPLANALLOC
73 gl_ppcurrent = gl_polypool;
74 gl_ppfree = POLYPOOLSIZE;
75 #endif
76 }
77
78 // allocate pool for fast alloc of polys
HWR_InitPolyPool(void)79 void HWR_InitPolyPool(void)
80 {
81 #ifndef ZPLANALLOC
82 INT32 pnum;
83
84 //hurdler: quick fix for those who wants to play with larger wad
85 if ((pnum = M_CheckParm("-polypoolsize")))
86 POLYPOOLSIZE = atoi(myargv[pnum+1])*1024; // (in kb)
87
88 CONS_Debug(DBG_RENDER, "HWR_InitPolyPool(): allocating %d bytes\n", POLYPOOLSIZE);
89 gl_polypool = malloc(POLYPOOLSIZE);
90 if (!gl_polypool)
91 I_Error("HWR_InitPolyPool(): couldn't malloc polypool\n");
92 HWR_ClearPolys();
93 #endif
94 }
95
HWR_FreePolyPool(void)96 void HWR_FreePolyPool(void)
97 {
98 #ifndef ZPLANALLOC
99 if (gl_polypool)
100 free(gl_polypool);
101 gl_polypool = NULL;
102 #endif
103 }
104
HWR_AllocPoly(INT32 numpts)105 static poly_t *HWR_AllocPoly(INT32 numpts)
106 {
107 poly_t *p;
108 size_t size = sizeof (poly_t) + sizeof (polyvertex_t) * numpts;
109 #ifdef ZPLANALLOC
110 p = Z_Malloc(size, PU_HWRPLANE, NULL);
111 #else
112 #ifdef PARANOIA
113 if (!gl_polypool)
114 I_Error("Used gl_polypool without init!\n");
115 if (!gl_ppcurrent)
116 I_Error("gl_ppcurrent == NULL!\n");
117 #endif
118
119 if (gl_ppfree < size)
120 I_Error("HWR_AllocPoly(): no more memory %u bytes left, %u bytes needed\n\n%s\n",
121 gl_ppfree, size, "You can try the param -polypoolsize 2048 (or higher if needed)");
122
123 p = (poly_t *)gl_ppcurrent;
124 gl_ppcurrent += size;
125 gl_ppfree -= size;
126 #endif
127 p->numpts = numpts;
128 return p;
129 }
130
HWR_AllocVertex(void)131 static polyvertex_t *HWR_AllocVertex(void)
132 {
133 polyvertex_t *p;
134 size_t size = sizeof (polyvertex_t);
135 #ifdef ZPLANALLOC
136 p = Z_Malloc(size, PU_HWRPLANE, NULL);
137 #else
138 if (gl_ppfree < size)
139 I_Error("HWR_AllocVertex(): no more memory %u bytes left, %u bytes needed\n\n%s\n",
140 gl_ppfree, size, "You can try the param -polypoolsize 2048 (or higher if needed)");
141
142 p = (polyvertex_t *)gl_ppcurrent;
143 gl_ppcurrent += size;
144 gl_ppfree -= size;
145 #endif
146 return p;
147 }
148
149 /// \todo polygons should be freed in reverse order for efficiency,
150 /// for now don't free because it doesn't free in reverse order
HWR_FreePoly(poly_t * poly)151 static void HWR_FreePoly(poly_t *poly)
152 {
153 #ifdef ZPLANALLOC
154 Z_Free(poly);
155 #else
156 const size_t size = sizeof (poly_t) + sizeof (polyvertex_t) * poly->numpts;
157 memset(poly, 0x00, size);
158 //mempoly -= polysize;
159 #endif
160 }
161
162
163 // Return interception along bsp line,
164 // with the polygon segment
165 //
166 static float bspfrac;
fracdivline(fdivline_t * bsp,polyvertex_t * v1,polyvertex_t * v2)167 static polyvertex_t *fracdivline(fdivline_t *bsp, polyvertex_t *v1,
168 polyvertex_t *v2)
169 {
170 static polyvertex_t pt;
171 double frac;
172 double num;
173 double den;
174 double v1x,v1y,v1dx,v1dy;
175 double v2x,v2y,v2dx,v2dy;
176
177 // a segment of a polygon
178 v1x = v1->x;
179 v1y = v1->y;
180 v1dx = v2->x - v1->x;
181 v1dy = v2->y - v1->y;
182
183 // the bsp partition line
184 v2x = bsp->x;
185 v2y = bsp->y;
186 v2dx = bsp->dx;
187 v2dy = bsp->dy;
188
189 den = v2dy*v1dx - v2dx*v1dy;
190 if (fabsf((float)den) < 1.0E-36f) // avoid checking exactly for 0.0
191 return NULL; // parallel
192
193 // first check the frac along the polygon segment,
194 // (do not accept hit with the extensions)
195 num = (v2x - v1x)*v2dy + (v1y - v2y)*v2dx;
196 frac = num / den;
197 if (frac < 0.0l || frac > 1.0l)
198 return NULL;
199
200 // now get the frac along the BSP line
201 // which is useful to determine what is left, what is right
202 num = (v2x - v1x)*v1dy + (v1y - v2y)*v1dx;
203 frac = num / den;
204 bspfrac = (float)frac;
205
206
207 // find the interception point along the partition line
208 pt.x = (float)(v2x + v2dx*frac);
209 pt.y = (float)(v2y + v2dy*frac);
210
211 return &pt;
212 }
213
214 // if two vertice coords have a x and/or y difference
215 // of less or equal than 1 FRACUNIT, they are considered the same
216 // point. Note: hardcoded value, 1.0f could be anything else.
SameVertice(polyvertex_t * p1,polyvertex_t * p2)217 static boolean SameVertice (polyvertex_t *p1, polyvertex_t *p2)
218 {
219 #if 0
220 float diff;
221 diff = p2->x - p1->x;
222 if (diff < -1.5f || diff > 1.5f)
223 return false;
224 diff = p2->y - p1->y;
225 if (diff < -1.5f || diff > 1.5f)
226 return false;
227 #elif 0
228 if (p1->x != p2->x)
229 return false;
230 if (p1->y != p2->y)
231 return false;
232 #elif 0
233 if (fabsf( p2->x - p1->x ) > 1.0E-36f )
234 return false;
235 if (fabsf( p2->y - p1->y ) > 1.0E-36f )
236 return false;
237 #else
238 #define DIVLINE_VERTEX_DIFF 0.45f
239 float ep = DIVLINE_VERTEX_DIFF;
240 if (fabsf( p2->x - p1->x ) > ep )
241 return false;
242 if (fabsf( p2->y - p1->y ) > ep )
243 return false;
244 #endif
245 // p1 and p2 are considered the same vertex
246 return true;
247 }
248
249
250 // split a _CONVEX_ polygon in two convex polygons
251 // outputs:
252 // frontpoly : polygon on right side of bsp line
253 // backpoly : polygon on left side
254 //
SplitPoly(fdivline_t * bsp,poly_t * poly,poly_t ** frontpoly,poly_t ** backpoly)255 static void SplitPoly (fdivline_t *bsp, //splitting parametric line
256 poly_t *poly, //the convex poly we split
257 poly_t **frontpoly, //return one poly here
258 poly_t **backpoly) //return the other here
259 {
260 INT32 i,j;
261 polyvertex_t *pv;
262
263 INT32 ps = -1,pe = -1;
264 INT32 nptfront,nptback;
265 polyvertex_t vs = {0,0,0};
266 polyvertex_t ve = {0,0,0};
267 polyvertex_t lastpv = {0,0,0};
268 float fracs = 0.0f,frace = 0.0f; //used to tell which poly is on
269 // the front side of the bsp partition line
270 INT32 psonline = 0, peonline = 0;
271
272 for (i = 0; i < poly->numpts; i++)
273 {
274 j = i + 1;
275 if (j == poly->numpts) j = 0;
276
277 // start & end points
278 pv = fracdivline(bsp, &poly->pts[i], &poly->pts[j]);
279
280 if (pv == NULL)
281 continue;
282
283 if (ps < 0)
284 {
285 // first point
286 ps = i;
287 vs = *pv;
288 fracs = bspfrac;
289 }
290 else
291 {
292 //the partition line traverse a junction between two segments
293 // or the two points are so close, they can be considered as one
294 // thus, don't accept, since split 2 must be another vertex
295 if (SameVertice(pv, &lastpv))
296 {
297 if (pe < 0)
298 {
299 ps = i;
300 psonline = 1;
301 }
302 else
303 {
304 pe = i;
305 peonline = 1;
306 }
307 }
308 else
309 {
310 if (pe < 0)
311 {
312 pe = i;
313 ve = *pv;
314 frace = bspfrac;
315 }
316 else
317 {
318 // a frac, not same vertice as last one
319 // we already got pt2 so pt 2 is not on the line,
320 // so we probably got back to the start point
321 // which is on the line
322 if (SameVertice(pv, &vs))
323 psonline = 1;
324 break;
325 }
326 }
327 }
328
329 // remember last point intercept to detect identical points
330 lastpv = *pv;
331 }
332
333 // no split: the partition line is either parallel and
334 // aligned with one of the poly segments, or the line is totally
335 // out of the polygon and doesn't traverse it (happens if the bsp
336 // is fooled by some trick where the sidedefs don't point to
337 // the right sectors)
338 if (ps < 0)
339 {
340 //I_Error("SplitPoly: did not split polygon (%d %d)\n"
341 // "debugpos %d",ps,pe,debugpos);
342
343 // this eventually happens with 'broken' BSP's that accept
344 // linedefs where each side point the same sector, that is:
345 // the deep water effect with the original Doom
346
347 /// \todo make sure front poly is to front of partition line?
348
349 *frontpoly = poly;
350 *backpoly = NULL;
351 return;
352 }
353
354 if (pe < 0)
355 {
356 //I_Error("SplitPoly: only one point for split line (%d %d)", ps, pe);
357 *frontpoly = poly;
358 *backpoly = NULL;
359 return;
360 }
361 if (pe <= ps)
362 I_Error("SplitPoly: invalid splitting line (%d %d)", ps, pe);
363
364 // number of points on each side, _not_ counting those
365 // that may lie just one the line
366 nptback = pe - ps - peonline;
367 nptfront = poly->numpts - peonline - psonline - nptback;
368
369 if (nptback > 0)
370 *backpoly = HWR_AllocPoly(2 + nptback);
371 else
372 *backpoly = NULL;
373 if (nptfront > 0)
374 *frontpoly = HWR_AllocPoly(2 + nptfront);
375 else
376 *frontpoly = NULL;
377
378 // generate FRONT poly
379 if (*frontpoly)
380 {
381 pv = (*frontpoly)->pts;
382 *pv++ = vs;
383 *pv++ = ve;
384 i = pe;
385 do
386 {
387 if (++i == poly->numpts)
388 i = 0;
389 *pv++ = poly->pts[i];
390 } while (i != ps && --nptfront);
391 }
392
393 // generate BACK poly
394 if (*backpoly)
395 {
396 pv = (*backpoly)->pts;
397 *pv++ = ve;
398 *pv++ = vs;
399 i = ps;
400 do
401 {
402 if (++i == poly->numpts)
403 i = 0;
404 *pv++ = poly->pts[i];
405 } while (i != pe && --nptback);
406 }
407
408 // make sure frontpoly is the one on the 'right' side
409 // of the partition line
410 if (fracs > frace)
411 {
412 poly_t *swappoly;
413 swappoly = *backpoly;
414 *backpoly = *frontpoly;
415 *frontpoly = swappoly;
416 }
417
418 HWR_FreePoly (poly);
419 }
420
421
422 // use each seg of the poly as a partition line, keep only the
423 // part of the convex poly to the front of the seg (that is,
424 // the part inside the sector), the part behind the seg, is
425 // the void space and is cut out
426 //
CutOutSubsecPoly(seg_t * lseg,INT32 count,poly_t * poly)427 static poly_t *CutOutSubsecPoly(seg_t *lseg, INT32 count, poly_t *poly)
428 {
429 INT32 i, j;
430
431 polyvertex_t *pv;
432
433 INT32 nump = 0, ps, pe;
434 polyvertex_t vs = {0, 0, 0}, ve = {0, 0, 0},
435 p1 = {0, 0, 0}, p2 = {0, 0, 0};
436 float fracs = 0.0f;
437
438 fdivline_t cutseg; // x, y, dx, dy as start of node_t struct
439
440 poly_t *temppoly;
441
442 // for each seg of the subsector
443 for (; count--; lseg++)
444 {
445 line_t *line = lseg->linedef;
446
447 if (lseg->glseg)
448 continue;
449
450 //x,y,dx,dy (like a divline)
451 p1.x = FIXED_TO_FLOAT(lseg->side ? line->v2->x : line->v1->x);
452 p1.y = FIXED_TO_FLOAT(lseg->side ? line->v2->y : line->v1->y);
453 p2.x = FIXED_TO_FLOAT(lseg->side ? line->v1->x : line->v2->x);
454 p2.y = FIXED_TO_FLOAT(lseg->side ? line->v1->y : line->v2->y);
455
456 cutseg.x = p1.x;
457 cutseg.y = p1.y;
458 cutseg.dx = p2.x - p1.x;
459 cutseg.dy = p2.y - p1.y;
460
461 // see if it cuts the convex poly
462 ps = -1;
463 pe = -1;
464 for (i = 0; i < poly->numpts; i++)
465 {
466 j = i + 1;
467 if (j == poly->numpts)
468 j = 0;
469
470 pv = fracdivline(&cutseg, &poly->pts[i], &poly->pts[j]);
471
472 if (pv == NULL)
473 continue;
474
475 if (ps < 0)
476 {
477 ps = i;
478 vs = *pv;
479 fracs = bspfrac;
480 }
481 else
482 {
483 //frac 1 on previous segment,
484 // 0 on the next,
485 //the split line goes through one of the convex poly
486 // vertices, happens quite often since the convex
487 // poly is already adjacent to the subsector segs
488 // on most borders
489 if (SameVertice(pv, &vs))
490 continue;
491
492 if (fracs <= bspfrac)
493 {
494 nump = 2 + poly->numpts - (i-ps);
495 pe = ps;
496 ps = i;
497 ve = *pv;
498 }
499 else
500 {
501 nump = 2 + (i-ps);
502 pe = i;
503 ve = vs;
504 vs = *pv;
505 }
506 //found 2nd point
507 break;
508 }
509 }
510
511 // there was a split
512 if (ps >= 0)
513 {
514 //need 2 points
515 if (pe >= 0)
516 {
517 // generate FRONT poly
518 temppoly = HWR_AllocPoly(nump);
519 pv = temppoly->pts;
520 *pv++ = vs;
521 *pv++ = ve;
522 do
523 {
524 if (++ps == poly->numpts)
525 ps = 0;
526 *pv++ = poly->pts[ps];
527 } while (ps != pe);
528 HWR_FreePoly(poly);
529 poly = temppoly;
530 }
531 //hmmm... maybe we should NOT accept this, but this happens
532 // only when the cut is not needed it seems (when the cut
533 // line is aligned to one of the borders of the poly, and
534 // only some times..)
535 else
536 skipcut++;
537 // I_Error("CutOutPoly: only one point for split line (%d %d) %d", ps, pe, debugpos);
538 }
539 }
540 return poly;
541 }
542
543 // At this point, the poly should be convex and the exact
544 // layout of the subsector, it is not always the case,
545 // so continue to cut off the poly into smaller parts with
546 // each seg of the subsector.
547 //
HWR_SubsecPoly(INT32 num,poly_t * poly)548 static inline void HWR_SubsecPoly(INT32 num, poly_t *poly)
549 {
550 INT16 count;
551 subsector_t *sub;
552 seg_t *lseg;
553
554 sub = &subsectors[num];
555 count = sub->numlines;
556 lseg = &segs[sub->firstline];
557
558 if (poly)
559 {
560 poly = CutOutSubsecPoly (lseg,count,poly);
561 totalsubsecpolys++;
562 //extra data for this subsector
563 extrasubsectors[num].planepoly = poly;
564 }
565 }
566
567 // the bsp divline have not enouth presition
568 // search for the segs source of this divline
SearchDivline(node_t * bsp,fdivline_t * divline)569 static inline void SearchDivline(node_t *bsp, fdivline_t *divline)
570 {
571 divline->x = FIXED_TO_FLOAT(bsp->x);
572 divline->y = FIXED_TO_FLOAT(bsp->y);
573 divline->dx = FIXED_TO_FLOAT(bsp->dx);
574 divline->dy = FIXED_TO_FLOAT(bsp->dy);
575 }
576
577 #ifdef HWR_LOADING_SCREEN
578 //Hurdler: implement a loading status
579 static size_t ls_count = 0;
580 static UINT8 ls_percent = 0;
581
loading_status(void)582 static void loading_status(void)
583 {
584 char s[16];
585 int x, y;
586
587 I_OsPolling();
588 CON_Drawer();
589 sprintf(s, "%d%%", (++ls_percent)<<1);
590 x = BASEVIDWIDTH/2;
591 y = BASEVIDHEIGHT/2;
592 V_DrawFill(0, 0, BASEVIDWIDTH, BASEVIDHEIGHT, 31); // Black background to match fade in effect
593 //V_DrawPatchFill(W_CachePatchName("SRB2BACK",PU_CACHE)); // SRB2 background, ehhh too bright.
594 M_DrawTextBox(x-58, y-8, 13, 1);
595 V_DrawString(x-50, y, V_YELLOWMAP, "Loading...");
596 V_DrawRightAlignedString(x+50, y, V_YELLOWMAP, s);
597
598 // Is this really necessary at this point..?
599 V_DrawCenteredString(BASEVIDWIDTH/2, 40, V_YELLOWMAP, "OPENGL MODE IS INCOMPLETE AND MAY");
600 V_DrawCenteredString(BASEVIDWIDTH/2, 50, V_YELLOWMAP, "NOT DISPLAY SOME SURFACES.");
601 V_DrawCenteredString(BASEVIDWIDTH/2, 70, V_YELLOWMAP, "USE AT SONIC'S RISK.");
602
603 I_UpdateNoVsync();
604 }
605 #endif
606
607 // poly : the convex polygon that encloses all child subsectors
WalkBSPNode(INT32 bspnum,poly_t * poly,UINT16 * leafnode,fixed_t * bbox)608 static void WalkBSPNode(INT32 bspnum, poly_t *poly, UINT16 *leafnode, fixed_t *bbox)
609 {
610 node_t *bsp;
611 poly_t *backpoly, *frontpoly;
612 fdivline_t fdivline;
613 polyvertex_t *pt;
614 INT32 i;
615
616 // Found a subsector?
617 if (bspnum & NF_SUBSECTOR)
618 {
619 if (bspnum == -1)
620 {
621 // BP: i think this code is useless and wrong because
622 // - bspnum==-1 happens only when numsubsectors == 0
623 // - it can't happens in bsp recursive call since bspnum is a INT32 and children is UINT16
624 // - the BSP is complet !! (there just can have subsector without segs) (i am not sure of this point)
625
626 // do we have a valid polygon ?
627 if (poly && poly->numpts > 2)
628 {
629 CONS_Debug(DBG_RENDER, "Adding a new subsector\n");
630 if (addsubsector == numsubsectors + NEWSUBSECTORS)
631 I_Error("WalkBSPNode: not enough addsubsectors\n");
632 else if (addsubsector > 0x7fff)
633 I_Error("WalkBSPNode: addsubsector > 0x7fff\n");
634 *leafnode = (UINT16)((UINT16)addsubsector | NF_SUBSECTOR);
635 extrasubsectors[addsubsector].planepoly = poly;
636 addsubsector++;
637 }
638
639 //add subsectors without segs here?
640 //HWR_SubsecPoly(0, NULL);
641 }
642 else
643 {
644 HWR_SubsecPoly(bspnum & ~NF_SUBSECTOR, poly);
645
646 //Hurdler: implement a loading status
647 #ifdef HWR_LOADING_SCREEN
648 if (ls_count-- <= 0)
649 {
650 ls_count = numsubsectors/50;
651 loading_status();
652 }
653 #endif
654 }
655 M_ClearBox(bbox);
656 poly = extrasubsectors[bspnum & ~NF_SUBSECTOR].planepoly;
657
658 for (i = 0, pt = poly->pts; i < poly->numpts; i++,pt++)
659 M_AddToBox(bbox, FLOAT_TO_FIXED(pt->x), FLOAT_TO_FIXED(pt->y));
660
661 return;
662 }
663
664 bsp = &nodes[bspnum];
665 SearchDivline(bsp, &fdivline);
666 SplitPoly(&fdivline, poly, &frontpoly, &backpoly);
667 poly = NULL;
668
669 //debug
670 if (!backpoly)
671 nobackpoly++;
672
673 // Recursively divide front space.
674 if (frontpoly)
675 {
676 WalkBSPNode(bsp->children[0], frontpoly, &bsp->children[0],bsp->bbox[0]);
677
678 // copy child bbox
679 M_Memcpy(bbox, bsp->bbox[0], 4*sizeof (fixed_t));
680 }
681 else
682 I_Error("WalkBSPNode: no front poly?");
683
684 // Recursively divide back space.
685 if (backpoly)
686 {
687 // Correct back bbox to include floor/ceiling convex polygon
688 WalkBSPNode(bsp->children[1], backpoly, &bsp->children[1], bsp->bbox[1]);
689
690 // enlarge bbox with second child
691 M_AddToBox(bbox, bsp->bbox[1][BOXLEFT ],
692 bsp->bbox[1][BOXTOP ]);
693 M_AddToBox(bbox, bsp->bbox[1][BOXRIGHT ],
694 bsp->bbox[1][BOXBOTTOM]);
695 }
696 }
697
698 // FIXME: use Z_Malloc() STATIC ?
HWR_FreeExtraSubsectors(void)699 void HWR_FreeExtraSubsectors(void)
700 {
701 if (extrasubsectors)
702 free(extrasubsectors);
703 extrasubsectors = NULL;
704 }
705
706 #define MAXDIST 1.5f
707 // BP: can't move vertex: DON'T change polygon geometry! (convex)
708 //#define MOVEVERTEX
PointInSeg(polyvertex_t * a,polyvertex_t * v1,polyvertex_t * v2)709 static boolean PointInSeg(polyvertex_t *a,polyvertex_t *v1,polyvertex_t *v2)
710 {
711 register float ax,ay,bx,by,cx,cy,d,norm;
712 register polyvertex_t *p;
713
714 // check bbox of the seg first
715 if (v1->x > v2->x)
716 {
717 p = v1;
718 v1 = v2;
719 v2 = p;
720 }
721
722 if (a->x < v1->x-MAXDIST || a->x > v2->x+MAXDIST)
723 return false;
724
725 if (v1->y > v2->y)
726 {
727 p = v1;
728 v1 = v2;
729 v2 = p;
730 }
731 if (a->y < v1->y-MAXDIST || a->y > v2->y+MAXDIST)
732 return false;
733
734 // v1 = origine
735 ax= v2->x-v1->x;
736 ay= v2->y-v1->y;
737 norm = (float)hypot(ax, ay);
738 ax /= norm;
739 ay /= norm;
740 bx = a->x-v1->x;
741 by = a->y-v1->y;
742 //d = a.b
743 d =ax*bx+ay*by;
744 // bound of the seg
745 if (d < 0 || d > norm)
746 return false;
747 //c = d.1a-b
748 cx = ax*d-bx;
749 cy = ay*d-by;
750 #ifdef MOVEVERTEX
751 if (cx*cx+cy*cy <= MAXDIST*MAXDIST)
752 {
753 // ajust a little the point position
754 a->x = ax*d+v1->x;
755 a->y = ay*d+v1->y;
756 // anyway the correction is not enouth
757 return true;
758 }
759 return false;
760 #else
761 return cx*cx+cy*cy <= MAXDIST*MAXDIST;
762 #endif
763 }
764
765 static INT32 numsplitpoly;
766
SearchSegInBSP(INT32 bspnum,polyvertex_t * p,poly_t * poly)767 static void SearchSegInBSP(INT32 bspnum,polyvertex_t *p,poly_t *poly)
768 {
769 poly_t *q;
770 INT32 j,k;
771
772 if (bspnum & NF_SUBSECTOR)
773 {
774 if (bspnum != -1)
775 {
776 bspnum &= ~NF_SUBSECTOR;
777 q = extrasubsectors[bspnum].planepoly;
778 if (poly == q || !q)
779 return;
780 for (j = 0; j < q->numpts; j++)
781 {
782 k = j+1;
783 if (k == q->numpts) k = 0;
784 if (!SameVertice(p, &q->pts[j])
785 && !SameVertice(p, &q->pts[k])
786 && PointInSeg(p, &q->pts[j],
787 &q->pts[k]))
788 {
789 poly_t *newpoly = HWR_AllocPoly(q->numpts+1);
790 INT32 n;
791
792 for (n = 0; n <= j; n++)
793 newpoly->pts[n] = q->pts[n];
794 newpoly->pts[k] = *p;
795 for (n = k+1; n < newpoly->numpts; n++)
796 newpoly->pts[n] = q->pts[n-1];
797 numsplitpoly++;
798 extrasubsectors[bspnum].planepoly =
799 newpoly;
800 HWR_FreePoly(q);
801 return;
802 }
803 }
804 }
805 return;
806 }
807
808 if ((FIXED_TO_FLOAT(nodes[bspnum].bbox[0][BOXBOTTOM])-MAXDIST <= p->y) &&
809 (FIXED_TO_FLOAT(nodes[bspnum].bbox[0][BOXTOP ])+MAXDIST >= p->y) &&
810 (FIXED_TO_FLOAT(nodes[bspnum].bbox[0][BOXLEFT ])-MAXDIST <= p->x) &&
811 (FIXED_TO_FLOAT(nodes[bspnum].bbox[0][BOXRIGHT ])+MAXDIST >= p->x))
812 SearchSegInBSP(nodes[bspnum].children[0],p,poly);
813
814 if ((FIXED_TO_FLOAT(nodes[bspnum].bbox[1][BOXBOTTOM])-MAXDIST <= p->y) &&
815 (FIXED_TO_FLOAT(nodes[bspnum].bbox[1][BOXTOP ])+MAXDIST >= p->y) &&
816 (FIXED_TO_FLOAT(nodes[bspnum].bbox[1][BOXLEFT ])-MAXDIST <= p->x) &&
817 (FIXED_TO_FLOAT(nodes[bspnum].bbox[1][BOXRIGHT ])+MAXDIST >= p->x))
818 SearchSegInBSP(nodes[bspnum].children[1],p,poly);
819 }
820
821 // search for T-intersection problem
822 // BP : It can be mush more faster doing this at the same time of the splitpoly
823 // but we must use a different structure : polygone pointing on segs
824 // segs pointing on polygone and on vertex (too mush complicated, well not
825 // realy but i am soo lasy), the methode discibed is also better for segs presition
SolveTProblem(void)826 static INT32 SolveTProblem(void)
827 {
828 poly_t *p;
829 INT32 i;
830 size_t l;
831
832 if (cv_glsolvetjoin.value == 0)
833 return 0;
834
835 CONS_Debug(DBG_RENDER, "Solving T-joins. This may take a while. Please wait...\n");
836 #ifdef HWR_LOADING_SCREEN
837 CON_Drawer(); //let the user know what we are doing
838 I_FinishUpdate(); // page flip or blit buffer
839 #endif
840
841 numsplitpoly = 0;
842
843 for (l = 0; l < addsubsector; l++)
844 {
845 p = extrasubsectors[l].planepoly;
846 if (p)
847 for (i = 0; i < p->numpts; i++)
848 SearchSegInBSP((INT32)numnodes-1, &p->pts[i], p);
849 }
850 //CONS_Debug(DBG_RENDER, "numsplitpoly %d\n", numsplitpoly);
851 return numsplitpoly;
852 }
853
854 #define NEARDIST (0.75f)
855 #define MYMAX (10000000000000.0f)
856
857 /* Adjust true segs (from the segs lump) to be exactely the same as
858 * plane polygone segs
859 * This also convert fixed_t point of segs in float (in moste case
860 * it share the same vertice
861 */
AdjustSegs(void)862 static void AdjustSegs(void)
863 {
864 size_t i, count;
865 INT32 j;
866 seg_t *lseg;
867 poly_t *p;
868 INT32 v1found = 0, v2found = 0;
869 float nearv1, nearv2;
870
871 for (i = 0; i < numsubsectors; i++)
872 {
873 count = subsectors[i].numlines;
874 lseg = &segs[subsectors[i].firstline];
875 p = extrasubsectors[i].planepoly;
876 //if (!p)
877 //continue;
878 for (; count--; lseg++)
879 {
880 float distv1,distv2,tmp;
881 nearv1 = nearv2 = MYMAX;
882
883 // Don't touch polyobject segs. We'll compensate
884 // for this when we go about drawing them.
885 if (lseg->polyseg)
886 continue;
887
888 if (p) {
889 for (j = 0; j < p->numpts; j++)
890 {
891 distv1 = p->pts[j].x - FIXED_TO_FLOAT(lseg->v1->x);
892 tmp = p->pts[j].y - FIXED_TO_FLOAT(lseg->v1->y);
893 distv1 = distv1*distv1+tmp*tmp;
894 if (distv1 <= nearv1)
895 {
896 v1found = j;
897 nearv1 = distv1;
898 }
899 // the same with v2
900 distv2 = p->pts[j].x - FIXED_TO_FLOAT(lseg->v2->x);
901 tmp = p->pts[j].y - FIXED_TO_FLOAT(lseg->v2->y);
902 distv2 = distv2*distv2+tmp*tmp;
903 if (distv2 <= nearv2)
904 {
905 v2found = j;
906 nearv2 = distv2;
907 }
908 }
909 }
910 if (p && nearv1 <= NEARDIST*NEARDIST)
911 // share vertice with segs
912 lseg->pv1 = &(p->pts[v1found]);
913 else
914 {
915 // BP: here we can do better, using PointInSeg and compute
916 // the right point position also split a polygone side to
917 // solve a T-intersection, but too mush work
918
919 // convert fixed vertex to float vertex
920 polyvertex_t *pv = HWR_AllocVertex();
921 pv->x = FIXED_TO_FLOAT(lseg->v1->x);
922 pv->y = FIXED_TO_FLOAT(lseg->v1->y);
923 lseg->pv1 = pv;
924 }
925 if (p && nearv2 <= NEARDIST*NEARDIST)
926 lseg->pv2 = &(p->pts[v2found]);
927 else
928 {
929 polyvertex_t *pv = HWR_AllocVertex();
930 pv->x = FIXED_TO_FLOAT(lseg->v2->x);
931 pv->y = FIXED_TO_FLOAT(lseg->v2->y);
932 lseg->pv2 = pv;
933 }
934
935 // recompute length
936 {
937 float x,y;
938 x = ((polyvertex_t *)lseg->pv2)->x - ((polyvertex_t *)lseg->pv1)->x
939 + FIXED_TO_FLOAT(FRACUNIT/2);
940 y = ((polyvertex_t *)lseg->pv2)->y - ((polyvertex_t *)lseg->pv1)->y
941 + FIXED_TO_FLOAT(FRACUNIT/2);
942 lseg->flength = (float)hypot(x, y);
943 // BP: debug see this kind of segs
944 //if (nearv2 > NEARDIST*NEARDIST || nearv1 > NEARDIST*NEARDIST)
945 // lseg->length = 1;
946 }
947 }
948 }
949 }
950
951
952 // call this routine after the BSP of a Doom wad file is loaded,
953 // and it will generate all the convex polys for the hardware renderer
HWR_CreatePlanePolygons(INT32 bspnum)954 void HWR_CreatePlanePolygons(INT32 bspnum)
955 {
956 poly_t *rootp;
957 polyvertex_t *rootpv;
958 size_t i;
959 fixed_t rootbbox[4];
960
961 CONS_Debug(DBG_RENDER, "Creating polygons, please wait...\n");
962 #ifdef HWR_LOADING_SCREEN
963 ls_count = ls_percent = 0; // reset the loading status
964 CON_Drawer(); //let the user know what we are doing
965 I_FinishUpdate(); // page flip or blit buffer
966 #endif
967
968 HWR_ClearPolys();
969
970 // find min/max boundaries of map
971 //CONS_Debug(DBG_RENDER, "Looking for boundaries of map...\n");
972 M_ClearBox(rootbbox);
973 for (i = 0;i < numvertexes; i++)
974 M_AddToBox(rootbbox, vertexes[i].x, vertexes[i].y);
975
976 //CONS_Debug(DBG_RENDER, "Generating subsector polygons... %d subsectors\n", numsubsectors);
977
978 HWR_FreeExtraSubsectors();
979 // allocate extra data for each subsector present in map
980 totsubsectors = numsubsectors + NEWSUBSECTORS;
981 extrasubsectors = calloc(totsubsectors, sizeof (*extrasubsectors));
982 if (extrasubsectors == NULL)
983 I_Error("couldn't malloc extrasubsectors totsubsectors %s\n", sizeu1(totsubsectors));
984
985 // allocate table for back to front drawing of subsectors
986 /*gl_drawsubsectors = (INT16 *)malloc(sizeof (*gl_drawsubsectors) * totsubsectors);
987 if (!gl_drawsubsectors)
988 I_Error("couldn't malloc gl_drawsubsectors\n");*/
989
990 // number of the first new subsector that might be added
991 addsubsector = numsubsectors;
992
993 // construct the initial convex poly that encloses the full map
994 rootp = HWR_AllocPoly(4);
995 rootpv = rootp->pts;
996
997 rootpv->x = FIXED_TO_FLOAT(rootbbox[BOXLEFT ]);
998 rootpv->y = FIXED_TO_FLOAT(rootbbox[BOXBOTTOM]); //lr
999 rootpv++;
1000 rootpv->x = FIXED_TO_FLOAT(rootbbox[BOXLEFT ]);
1001 rootpv->y = FIXED_TO_FLOAT(rootbbox[BOXTOP ]); //ur
1002 rootpv++;
1003 rootpv->x = FIXED_TO_FLOAT(rootbbox[BOXRIGHT ]);
1004 rootpv->y = FIXED_TO_FLOAT(rootbbox[BOXTOP ]); //ul
1005 rootpv++;
1006 rootpv->x = FIXED_TO_FLOAT(rootbbox[BOXRIGHT ]);
1007 rootpv->y = FIXED_TO_FLOAT(rootbbox[BOXBOTTOM]); //ll
1008 rootpv++;
1009
1010 WalkBSPNode(bspnum, rootp, NULL,rootbbox);
1011
1012 i = SolveTProblem();
1013 //CONS_Debug(DBG_RENDER, "%d point divides a polygon line\n",i);
1014 AdjustSegs();
1015
1016 //debug debug..
1017 //if (nobackpoly)
1018 // CONS_Debug(DBG_RENDER, "no back polygon %u times\n",nobackpoly);
1019 //"(should happen only with the deep water trick)"
1020 //if (skipcut)
1021 // CONS_Debug(DBG_RENDER, "%u cuts were skipped because of only one point\n",skipcut);
1022
1023 //CONS_Debug(DBG_RENDER, "done: %u total subsector convex polygons\n", totalsubsecpolys);
1024 }
1025
1026 #endif //HWRENDER
1027