1 //----------------------------------------------------------------------------
2 // EDGE Blockmap utility functions
3 //----------------------------------------------------------------------------
4 //
5 // Copyright (c) 1999-2009 The EDGE Team.
6 //
7 // This program is free software; you can redistribute it and/or
8 // modify it under the terms of the GNU General Public License
9 // as published by the Free Software Foundation; either version 2
10 // of the License, or (at your option) any later version.
11 //
12 // This program is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 // GNU General Public License for more details.
16 //
17 //----------------------------------------------------------------------------
18 //
19 // Based on the DOOM source code, released by Id Software under the
20 // following copyright:
21 //
22 // Copyright (C) 1993-1996 by id Software, Inc.
23 //
24 //----------------------------------------------------------------------------
25
26 #include "i_defs.h"
27 #include "i_defs_gl.h" // needed for r_shader.h
28
29 #include <float.h>
30
31 #include <vector>
32 #include <algorithm>
33
34 #include "dm_data.h"
35 #include "dm_defs.h"
36 #include "dm_state.h"
37 #include "m_bbox.h"
38 #include "p_local.h"
39 #include "p_spec.h"
40 #include "r_shader.h"
41 #include "r_state.h"
42 #include "z_zone.h"
43
44
45 // FIXME: have a proper API
46 extern abstract_shader_c *MakeDLightShader(mobj_t *mo);
47 extern abstract_shader_c *MakePlaneGlow(mobj_t *mo);
48
49
50 #define MAXRADIUS 128.0
51
52 // BLOCKMAP
53 //
54 // Created from axis aligned bounding box
55 // of the map, a rectangular array of
56 // blocks of size ...
57 // Used to speed up collision detection
58 // by spatial subdivision in 2D.
59 //
60 // Blockmap size.
61 // 23-6-98 KM Promotion of short * to int *
62 int bmap_width;
63 int bmap_height; // size in mapblocks
64
65 // origin of block map
66 float bmap_orgx;
67 float bmap_orgy;
68
69 typedef std::list<line_t *> linedef_set_t;
70
71 static linedef_set_t **bmap_lines = NULL;
72
73 // for thing chains
74 mobj_t **bmap_things = NULL;
75
76 // for dynamic lights
77 int dlmap_width;
78 int dlmap_height;
79
80 mobj_t **dlmap_things = NULL;
81
82
P_CreateThingBlockMap(void)83 void P_CreateThingBlockMap(void)
84 {
85 bmap_things = new mobj_t* [bmap_width * bmap_height];
86
87 Z_Clear(bmap_things, mobj_t*, bmap_width * bmap_height);
88
89 // compute size of dynamic light blockmap
90 dlmap_width = (bmap_width * BLOCKMAP_UNIT + LIGHTMAP_UNIT-1) / LIGHTMAP_UNIT;
91 dlmap_height = (bmap_height * BLOCKMAP_UNIT + LIGHTMAP_UNIT-1) / LIGHTMAP_UNIT;
92
93 I_Debugf("Blockmap size: %dx%d --> Lightmap size: %dx%x\n",
94 bmap_width, bmap_height, dlmap_width, dlmap_height);
95
96 dlmap_things = new mobj_t* [dlmap_width * dlmap_height];
97
98 Z_Clear(dlmap_things, mobj_t*, dlmap_width * dlmap_height);
99 }
100
P_DestroyBlockMap(void)101 void P_DestroyBlockMap(void)
102 {
103 delete[] bmap_lines; bmap_lines = NULL;
104 delete[] bmap_things; bmap_things = NULL;
105
106 delete[] dlmap_things; dlmap_things = NULL;
107 }
108
109
110 //--------------------------------------------------------------------------
111 //
112 // THING POSITION SETTING
113 //
114
115 // stats
116 #ifdef DEVELOPERS
117 int touchstat_moves;
118 int touchstat_hit;
119 int touchstat_miss;
120 int touchstat_alloc;
121 int touchstat_free;
122 #endif
123
124 // quick-alloc list
125 // FIXME: incorporate into FlushCaches
126 touch_node_t *free_touch_nodes;
127
TouchNodeAlloc(void)128 static inline touch_node_t *TouchNodeAlloc(void)
129 {
130 touch_node_t *tn;
131
132 #ifdef DEVELOPERS
133 touchstat_alloc++;
134 #endif
135
136 if (free_touch_nodes)
137 {
138 tn = free_touch_nodes;
139 free_touch_nodes = tn->mo_next;
140 }
141 else
142 {
143 tn = Z_New(touch_node_t, 1);
144 }
145
146 return tn;
147 }
148
TouchNodeFree(touch_node_t * tn)149 static inline void TouchNodeFree(touch_node_t *tn)
150 {
151 #ifdef DEVELOPERS
152 touchstat_free++;
153 #endif
154
155 // PREV field is ignored in quick-alloc list
156 tn->mo_next = free_touch_nodes;
157 free_touch_nodes = tn;
158 }
159
TouchNodeLinkIntoSector(touch_node_t * tn,sector_t * sec)160 static inline void TouchNodeLinkIntoSector(touch_node_t *tn, sector_t *sec)
161 {
162 tn->sec = sec;
163
164 tn->sec_next = sec->touch_things;
165 tn->sec_prev = NULL;
166
167 if (tn->sec_next)
168 tn->sec_next->sec_prev = tn;
169
170 sec->touch_things = tn;
171 }
172
TouchNodeLinkIntoThing(touch_node_t * tn,mobj_t * mo)173 static inline void TouchNodeLinkIntoThing(touch_node_t *tn, mobj_t *mo)
174 {
175 tn->mo = mo;
176
177 tn->mo_next = mo->touch_sectors;
178 tn->mo_prev = NULL;
179
180 if (tn->mo_next)
181 tn->mo_next->mo_prev = tn;
182
183 mo->touch_sectors = tn;
184 }
185
TouchNodeUnlinkFromSector(touch_node_t * tn)186 static inline void TouchNodeUnlinkFromSector(touch_node_t *tn)
187 {
188 if (tn->sec_next)
189 tn->sec_next->sec_prev = tn->sec_prev;
190
191 if (tn->sec_prev)
192 tn->sec_prev->sec_next = tn->sec_next;
193 else
194 tn->sec->touch_things = tn->sec_next;
195 }
196
TouchNodeUnlinkFromThing(touch_node_t * tn)197 static inline void TouchNodeUnlinkFromThing(touch_node_t *tn)
198 {
199 if (tn->mo_next)
200 tn->mo_next->mo_prev = tn->mo_prev;
201
202 if (tn->mo_prev)
203 tn->mo_prev->mo_next = tn->mo_next;
204 else
205 tn->mo->touch_sectors = tn->mo_next;
206 }
207
208 typedef struct setposbsp_s
209 {
210 mobj_t *thing;
211
212 float bbox[4];
213 }
214 setposbsp_t;
215
216 //
217 // SetPositionBSP
218 //
SetPositionBSP(setposbsp_t * info,int nodenum)219 static void SetPositionBSP(setposbsp_t *info, int nodenum)
220 {
221 touch_node_t *tn;
222 sector_t *sec;
223 subsector_t *sub;
224 seg_t *seg;
225
226 while (! (nodenum & NF_V5_SUBSECTOR))
227 {
228 node_t *nd = nodes + nodenum;
229
230 int side = P_BoxOnDivLineSide(info->bbox, &nd->div);
231
232 // if box touches partition line, we must traverse both sides
233 if (side == -1)
234 {
235 SetPositionBSP(info, nd->children[0]);
236 side = 1;
237 }
238
239 SYS_ASSERT(side == 0 || side == 1);
240
241 nodenum = nd->children[side];
242 }
243
244 // reached a leaf of the BSP. Need to check BBOX against all
245 // linedef segs. This is because we can get false positives, since
246 // we don't actually split the thing's BBOX when it intersects with
247 // a partition line.
248
249 sub = subsectors + (nodenum & ~NF_V5_SUBSECTOR);
250
251 for (seg=sub->segs; seg; seg=seg->sub_next)
252 {
253 divline_t div;
254
255 if (seg->miniseg)
256 continue;
257
258 div.x = seg->v1->x;
259 div.y = seg->v1->y;
260 div.dx = seg->v2->x - div.x;
261 div.dy = seg->v2->y - div.y;
262
263 if (P_BoxOnDivLineSide(info->bbox, &div) == 1)
264 return;
265 }
266
267 // Perform linkage...
268
269 sec = sub->sector;
270
271 #ifdef DEVELOPERS
272 touchstat_miss++;
273 #endif
274
275 for (tn = info->thing->touch_sectors; tn; tn = tn->mo_next)
276 {
277 if (! tn->mo)
278 {
279 // found unused touch node. We reuse it.
280 tn->mo = info->thing;
281
282 if (tn->sec != sec)
283 {
284 TouchNodeUnlinkFromSector(tn);
285 TouchNodeLinkIntoSector(tn, sec);
286 }
287 #ifdef DEVELOPERS
288 else
289 {
290 touchstat_miss--;
291 touchstat_hit++;
292 }
293 #endif
294
295 return;
296 }
297
298 SYS_ASSERT(tn->mo == info->thing);
299
300 // sector already present ?
301 if (tn->sec == sec)
302 return;
303 }
304
305 // need to allocate a new touch node
306 tn = TouchNodeAlloc();
307
308 TouchNodeLinkIntoThing(tn, info->thing);
309 TouchNodeLinkIntoSector(tn, sec);
310 }
311
312 //
313 // P_UnsetThingPosition
314 //
315 // Unlinks a thing from block map and subsector.
316 // On each position change, BLOCKMAP and other
317 // lookups maintaining lists ot things inside
318 // these structures need to be updated.
319 //
320 // -ES- 1999/12/04 Better error checking: Clear prev/next fields.
321 // This catches errors which can occur if the position is unset twice.
322 //
P_UnsetThingPosition(mobj_t * mo)323 void P_UnsetThingPosition(mobj_t * mo)
324 {
325 int blockx;
326 int blocky;
327 int bnum;
328
329 touch_node_t *tn;
330
331 // unlink from subsector
332 if (!(mo->flags & MF_NOSECTOR))
333 {
334 // (inert things don't need to be in subsector list)
335
336 if (mo->snext)
337 {
338 SYS_ASSERT(mo->snext->sprev == mo);
339
340 mo->snext->sprev = mo->sprev;
341 }
342
343 if (mo->sprev)
344 {
345 SYS_ASSERT(mo->sprev->snext == mo);
346
347 mo->sprev->snext = mo->snext;
348 }
349 else
350 {
351 SYS_ASSERT(mo->subsector->thinglist == mo);
352
353 mo->subsector->thinglist = mo->snext;
354 }
355
356 mo->snext = NULL;
357 mo->sprev = NULL;
358 }
359
360 // unlink from touching list.
361 // NOTE: lazy unlinking -- see notes in r_defs.h
362 //
363 for (tn = mo->touch_sectors; tn; tn = tn->mo_next)
364 {
365 tn->mo = NULL;
366 }
367
368 // unlink from blockmap
369 if (!(mo->flags & MF_NOBLOCKMAP))
370 {
371 // inert things don't need to be in blockmap
372 if (mo->bnext)
373 {
374 SYS_ASSERT(mo->bnext->bprev == mo);
375
376 mo->bnext->bprev = mo->bprev;
377 }
378
379 if (mo->bprev)
380 {
381 SYS_ASSERT(mo->bprev->bnext == mo);
382
383 mo->bprev->bnext = mo->bnext;
384 }
385 else
386 {
387 blockx = BLOCKMAP_GET_X(mo->x);
388 blocky = BLOCKMAP_GET_Y(mo->y);
389
390 if (blockx >= 0 && blockx < bmap_width &&
391 blocky >= 0 && blocky < bmap_height)
392 {
393 bnum = blocky * bmap_width + blockx;
394
395 SYS_ASSERT(bmap_things[bnum] == mo);
396
397 bmap_things[bnum] = mo->bnext;
398 }
399 }
400
401 mo->bprev = NULL;
402 mo->bnext = NULL;
403 }
404
405 // unlink from dynamic light blockmap
406 if (mo->info && (mo->info->dlight[0].type != DLITE_None) &&
407 (mo->info->glow_type == GLOW_None))
408 {
409 if (mo->dlnext)
410 {
411 SYS_ASSERT(mo->dlnext->dlprev == mo);
412
413 mo->dlnext->dlprev = mo->dlprev;
414 }
415
416 if (mo->dlprev)
417 {
418 SYS_ASSERT(mo->dlprev->dlnext == mo);
419
420 mo->dlprev->dlnext = mo->dlnext;
421 }
422 else
423 {
424 blockx = LIGHTMAP_GET_X(mo->x);
425 blocky = LIGHTMAP_GET_Y(mo->y);
426
427 if (blockx >= 0 && blockx < dlmap_width &&
428 blocky >= 0 && blocky < dlmap_height)
429 {
430 bnum = blocky * dlmap_width + blockx;
431
432 SYS_ASSERT(dlmap_things[bnum] == mo);
433 dlmap_things[bnum] = mo->dlnext;
434 }
435 }
436
437 mo->dlprev = NULL;
438 mo->dlnext = NULL;
439 }
440
441 // unlink from sector glow list
442 if (mo->info && (mo->info->dlight[0].type != DLITE_None) &&
443 (mo->info->glow_type != GLOW_None))
444 {
445 sector_t *sec = mo->subsector->sector;
446
447 if (mo->dlnext)
448 {
449 SYS_ASSERT(mo->dlnext->dlprev == mo);
450
451 mo->dlnext->dlprev = mo->dlprev;
452 }
453
454 if (mo->dlprev)
455 {
456 SYS_ASSERT(mo->dlprev->dlnext == mo);
457
458 mo->dlprev->dlnext = mo->dlnext;
459 }
460 else
461 {
462 SYS_ASSERT(sec->glow_things == mo);
463
464 sec->glow_things = mo->dlnext;
465 }
466
467 mo->dlprev = NULL;
468 mo->dlnext = NULL;
469 }
470 }
471
472 //
473 // P_UnsetThingFinally
474 //
475 // Call when the thing is about to be removed for good.
476 //
P_UnsetThingFinally(mobj_t * mo)477 void P_UnsetThingFinally(mobj_t * mo)
478 {
479 touch_node_t *tn;
480
481 P_UnsetThingPosition(mo);
482
483 // clear out touch nodes
484
485 while (mo->touch_sectors)
486 {
487 tn = mo->touch_sectors;
488 mo->touch_sectors = tn->mo_next;
489
490 TouchNodeUnlinkFromSector(tn);
491 TouchNodeFree(tn);
492 }
493 }
494
495 //
496 // P_SetThingPosition
497 //
498 // Links a thing into both a block and a subsector
499 // based on it's x y.
500 //
P_SetThingPosition(mobj_t * mo)501 void P_SetThingPosition(mobj_t * mo)
502 {
503 subsector_t *ss;
504 int blockx;
505 int blocky;
506 int bnum;
507
508 setposbsp_t pos;
509 touch_node_t *tn;
510
511 // -ES- 1999/12/04 The position must be unset before it's set again.
512 if (mo->snext || mo->sprev || mo->bnext || mo->bprev)
513 I_Error("INTERNAL ERROR: Double P_SetThingPosition call.");
514
515 SYS_ASSERT(! (mo->dlnext || mo->dlprev));
516
517 // link into subsector
518 ss = R_PointInSubsector(mo->x, mo->y);
519 mo->subsector = ss;
520
521 // determine properties
522 mo->props = R_PointGetProps(ss, mo->z + mo->height/2);
523
524 if (! (mo->flags & MF_NOSECTOR))
525 {
526 mo->snext = ss->thinglist;
527 mo->sprev = NULL;
528
529 if (ss->thinglist)
530 ss->thinglist->sprev = mo;
531
532 ss->thinglist = mo;
533 }
534
535 // link into touching list
536
537 #ifdef DEVELOPERS
538 touchstat_moves++;
539 #endif
540
541 pos.thing = mo;
542 pos.bbox[BOXLEFT] = mo->x - mo->radius;
543 pos.bbox[BOXRIGHT] = mo->x + mo->radius;
544 pos.bbox[BOXBOTTOM] = mo->y - mo->radius;
545 pos.bbox[BOXTOP] = mo->y + mo->radius;
546
547 SetPositionBSP(&pos, root_node);
548
549 // handle any left-over unused touch nodes
550
551 for (tn = mo->touch_sectors; tn && tn->mo; tn = tn->mo_next)
552 { /* nothing here */ }
553
554 if (tn)
555 {
556 if (tn->mo_prev)
557 tn->mo_prev->mo_next = NULL;
558 else
559 mo->touch_sectors = NULL;
560
561 while (tn)
562 {
563 touch_node_t *cur = tn;
564 tn = tn->mo_next;
565
566 SYS_ASSERT(! cur->mo);
567
568 TouchNodeUnlinkFromSector(cur);
569 TouchNodeFree(cur);
570 }
571 }
572
573 #if 0 // PROFILING
574 {
575 static int last_time = 0;
576
577 if ((leveltime - last_time) > 5*TICRATE)
578 {
579 L_WriteDebug("TOUCHSTATS: Mv=%d Ht=%d Ms=%d Al=%d Fr=%d\n",
580 touchstat_moves, touchstat_hit, touchstat_miss,
581 touchstat_alloc, touchstat_free);
582
583 touchstat_moves = touchstat_hit = touchstat_miss =
584 touchstat_alloc = touchstat_free = 0;
585
586 last_time = leveltime;
587 }
588 }
589 #endif
590
591 // link into blockmap
592 if (!(mo->flags & MF_NOBLOCKMAP))
593 {
594 blockx = BLOCKMAP_GET_X(mo->x);
595 blocky = BLOCKMAP_GET_Y(mo->y);
596
597 if (blockx >= 0 && blockx < bmap_width &&
598 blocky >= 0 && blocky < bmap_height)
599 {
600 bnum = blocky * bmap_width + blockx;
601
602 mo->bprev = NULL;
603 mo->bnext = bmap_things[bnum];
604
605 if (bmap_things[bnum])
606 (bmap_things[bnum])->bprev = mo;
607
608 bmap_things[bnum] = mo;
609 }
610 else
611 {
612 // thing is off the map
613 mo->bnext = mo->bprev = NULL;
614 }
615 }
616
617 // link into dynamic light blockmap
618 if (mo->info && (mo->info->dlight[0].type != DLITE_None) &&
619 (mo->info->glow_type == GLOW_None))
620 {
621 blockx = LIGHTMAP_GET_X(mo->x);
622 blocky = LIGHTMAP_GET_Y(mo->y);
623
624 if (blockx >= 0 && blockx < dlmap_width &&
625 blocky >= 0 && blocky < dlmap_height)
626 {
627 bnum = blocky * dlmap_width + blockx;
628
629 mo->dlprev = NULL;
630 mo->dlnext = dlmap_things[bnum];
631
632 if (dlmap_things[bnum])
633 (dlmap_things[bnum])->dlprev = mo;
634
635 dlmap_things[bnum] = mo;
636 }
637 else
638 {
639 // thing is off the map
640 mo->dlnext = mo->dlprev = NULL;
641 }
642 }
643
644 // link into sector glow list
645 if (mo->info && (mo->info->dlight[0].type != DLITE_None) &&
646 (mo->info->glow_type != GLOW_None))
647 {
648 sector_t *sec = mo->subsector->sector;
649
650 mo->dlprev = NULL;
651 mo->dlnext = sec->glow_things;
652
653 sec->glow_things = mo;
654 }
655 }
656
657 //
658 // P_ChangeThingPosition
659 //
660 // New routine to "atomicly" move a thing. Apart from object
661 // construction and destruction, this routine should always be called
662 // when moving a thing, rather than fiddling with the coordinates
663 // directly (or even P_UnsetThingPos/P_SetThingPos pairs).
664 //
P_ChangeThingPosition(mobj_t * mo,float x,float y,float z)665 void P_ChangeThingPosition(mobj_t * mo, float x, float y, float z)
666 {
667 P_UnsetThingPosition(mo);
668 {
669 mo->x = x;
670 mo->y = y;
671 mo->z = z;
672 }
673 P_SetThingPosition(mo);
674 }
675
676 //
677 // P_FreeSectorTouchNodes
678 //
P_FreeSectorTouchNodes(sector_t * sec)679 void P_FreeSectorTouchNodes(sector_t *sec)
680 {
681 touch_node_t *tn;
682
683 for (tn = sec->touch_things; tn; tn = tn->sec_next)
684 TouchNodeFree(tn);
685 }
686
687
688
689 //--------------------------------------------------------------------------
690 //
691 // BLOCK MAP ITERATORS
692 //
693 // For each line/thing in the given mapblock,
694 // call the passed PIT_* function.
695 // If the function returns false,
696 // exit with false without checking anything else.
697 //
698
699 //
700 // P_BlockLinesIterator
701 //
702 // The validcount flags are used to avoid checking lines
703 // that are marked in multiple mapblocks,
704 // so increment validcount before the first call
705 // to P_BlockLinesIterator, then make one or more calls
706 // to it.
707 //
P_BlockLinesIterator(float x1,float y1,float x2,float y2,bool (* func)(line_t *,void *),void * data)708 bool P_BlockLinesIterator(float x1, float y1, float x2, float y2,
709 bool(* func)(line_t *, void *), void *data)
710 {
711 validcount++;
712
713 int lx = BLOCKMAP_GET_X(x1);
714 int ly = BLOCKMAP_GET_Y(y1);
715 int hx = BLOCKMAP_GET_X(x2);
716 int hy = BLOCKMAP_GET_Y(y2);
717
718 lx = MAX(0, lx); hx = MIN(bmap_width-1, hx);
719 ly = MAX(0, ly); hy = MIN(bmap_height-1, hy);
720
721 for (int by = ly; by <= hy; by++)
722 for (int bx = lx; bx <= hx; bx++)
723 {
724 linedef_set_t *lset = bmap_lines[by * bmap_width + bx];
725
726 if (! lset)
727 continue;
728
729 linedef_set_t::iterator LI;
730 for (LI = lset->begin(); LI != lset->end(); LI++)
731 {
732 line_t *ld = *LI;
733
734 // has line already been checked ?
735 if (ld->validcount == validcount)
736 continue;
737
738 ld->validcount = validcount;
739
740 // check whether line touches the given bbox
741 if (ld->bbox[BOXRIGHT] <= x1 || ld->bbox[BOXLEFT] >= x2 ||
742 ld->bbox[BOXTOP] <= y1 || ld->bbox[BOXBOTTOM] >= y2)
743 {
744 continue;
745 }
746
747 if (! func(ld, data))
748 return false;
749 }
750 }
751
752 // everything was checked
753 return true;
754 }
755
756
P_BlockThingsIterator(float x1,float y1,float x2,float y2,bool (* func)(mobj_t *,void *),void * data)757 bool P_BlockThingsIterator(float x1, float y1, float x2, float y2,
758 bool (*func)(mobj_t *, void*), void *data)
759 {
760 // need to expand the source by one block because large
761 // things (radius limited to BLOCKMAP_UNIT) can overlap
762 // into adjacent blocks.
763
764 int lx = BLOCKMAP_GET_X(x1) - 1;
765 int ly = BLOCKMAP_GET_Y(y1) - 1;
766 int hx = BLOCKMAP_GET_X(x2) + 1;
767 int hy = BLOCKMAP_GET_Y(y2) + 1;
768
769 lx = MAX(0, lx); hx = MIN(bmap_width-1, hx);
770 ly = MAX(0, ly); hy = MIN(bmap_height-1, hy);
771
772 for (int by = ly; by <= hy; by++)
773 for (int bx = lx; bx <= hx; bx++)
774 {
775 for (mobj_t *mo = bmap_things[by * bmap_width + bx]; mo; mo = mo->bnext)
776 {
777 // check whether thing touches the given bbox
778 float r = mo->radius;
779
780 if (mo->x + r <= x1 || mo->x - r >= x2 ||
781 mo->y + r <= y1 || mo->y - r >= y2)
782 continue;
783
784 if (! func(mo, data))
785 return false;
786 }
787 }
788
789 return true;
790 }
791
792
P_DynamicLightIterator(float x1,float y1,float z1,float x2,float y2,float z2,void (* func)(mobj_t *,void *),void * data)793 void P_DynamicLightIterator(float x1, float y1, float z1,
794 float x2, float y2, float z2,
795 void (*func)(mobj_t *, void *), void *data)
796 {
797 int lx = LIGHTMAP_GET_X(x1) - 1;
798 int ly = LIGHTMAP_GET_Y(y1) - 1;
799 int hx = LIGHTMAP_GET_X(x2) + 1;
800 int hy = LIGHTMAP_GET_Y(y2) + 1;
801
802 lx = MAX(0, lx); hx = MIN(dlmap_width-1, hx);
803 ly = MAX(0, ly); hy = MIN(dlmap_height-1, hy);
804
805 for (int by = ly; by <= hy; by++)
806 for (int bx = lx; bx <= hx; bx++)
807 {
808 for (mobj_t *mo = dlmap_things[by * dlmap_width + bx]; mo; mo = mo->dlnext)
809 {
810 SYS_ASSERT(mo->state);
811
812 // skip "off" lights
813 if (mo->state->bright <= 0 || mo->dlight.r <= 0)
814 continue;
815
816 // check whether radius touches the given bbox
817 float r = mo->dlight.r;
818
819 if (mo->x + r <= x1 || mo->x - r >= x2 ||
820 mo->y + r <= y1 || mo->y - r >= y2 ||
821 mo->z + r <= z1 || mo->z - r >= z2)
822 continue;
823
824 // create shader if necessary
825 if (! mo->dlight.shader)
826 mo->dlight.shader = MakeDLightShader(mo);
827
828 // mo->dlight.shader->CheckReset();
829
830 func(mo, data);
831 }
832 }
833 }
834
835
P_SectorGlowIterator(sector_t * sec,float x1,float y1,float z1,float x2,float y2,float z2,void (* func)(mobj_t *,void *),void * data)836 void P_SectorGlowIterator(sector_t *sec,
837 float x1, float y1, float z1,
838 float x2, float y2, float z2,
839 void (*func)(mobj_t *, void *), void *data)
840 {
841 for (mobj_t *mo = sec->glow_things; mo; mo = mo->dlnext)
842 {
843 SYS_ASSERT(mo->state);
844
845 // skip "off" lights
846 if (mo->state->bright <= 0 || mo->dlight.r <= 0)
847 continue;
848
849 // check whether radius touches the given bbox
850 float r = mo->dlight.r;
851
852 if (mo->info->glow_type == GLOW_Floor && sec->f_h + r <= z1)
853 continue;
854
855 if (mo->info->glow_type == GLOW_Ceiling && sec->c_h - r >= z1)
856 continue;
857
858 // create shader if necessary
859 if (! mo->dlight.shader)
860 mo->dlight.shader = MakePlaneGlow(mo);
861
862 // mo->dlight.shader->CheckReset();
863
864 func(mo, data);
865 }
866 }
867
868
869 //--------------------------------------------------------------------------
870 //
871 // INTERCEPT ROUTINES
872 //
873
874 static std::vector<intercept_t> intercepts;
875
876 divline_t trace;
877
878
P_InterceptVector(divline_t * v2,divline_t * v1)879 float P_InterceptVector(divline_t * v2, divline_t * v1)
880 {
881 // Returns the fractional intercept point along the first divline.
882 // This is only called by the addthings and addlines traversers.
883
884 float den = (v1->dy * v2->dx) - (v1->dx * v2->dy);
885
886 if (den == 0)
887 return 0; // parallel
888
889 float num = (v1->x - v2->x) * v1->dy + (v2->y - v1->y) * v1->dx;
890
891 return num / den;
892 }
893
894
PIT_AddLineIntercept(line_t * ld)895 static inline void PIT_AddLineIntercept(line_t * ld)
896 {
897 // Looks for lines in the given block
898 // that intercept the given trace
899 // to add to the intercepts list.
900 //
901 // A line is crossed if its endpoints
902 // are on opposite sides of the trace.
903 // Returns true if earlyout and a solid line hit.
904
905 // has line already been checked ?
906 if (ld->validcount == validcount)
907 return;
908
909 ld->validcount = validcount;
910
911 int s1;
912 int s2;
913 float frac;
914 divline_t div;
915
916 div.x = ld->v1->x;
917 div.y = ld->v1->y;
918 div.dx = ld->dx;
919 div.dy = ld->dy;
920
921 // avoid precision problems with two routines
922 if (trace.dx > 16 || trace.dy > 16 || trace.dx < -16 || trace.dy < -16)
923 {
924 s1 = P_PointOnDivlineSide(ld->v1->x, ld->v1->y, &trace);
925 s2 = P_PointOnDivlineSide(ld->v2->x, ld->v2->y, &trace);
926 }
927 else
928 {
929 s1 = P_PointOnDivlineSide(trace.x, trace.y, &div);
930 s2 = P_PointOnDivlineSide(trace.x + trace.dx, trace.y + trace.dy, &div);
931 }
932
933 // line isn't crossed ?
934 if (s1 == s2)
935 return;
936
937 // hit the line
938
939 frac = P_InterceptVector(&trace, &div);
940
941 // out of range?
942 if (frac < 0 || frac > 1)
943 return;
944
945 // Intercept is a simple struct that can be memcpy()'d: Load
946 // up a structure and get into the array
947 intercept_t in;
948
949 in.frac = frac;
950 in.thing = NULL;
951 in.line = ld;
952
953 intercepts.push_back(in);
954 }
955
PIT_AddThingIntercept(mobj_t * thing)956 static inline void PIT_AddThingIntercept(mobj_t * thing)
957 {
958 float x1;
959 float y1;
960 float x2;
961 float y2;
962
963 int s1;
964 int s2;
965
966 bool tracepositive;
967
968 divline_t div;
969
970 float frac;
971
972 tracepositive = (trace.dx >= 0) == (trace.dy >= 0);
973
974 // check a corner to corner crossection for hit
975 if (tracepositive)
976 {
977 x1 = thing->x - thing->radius;
978 y1 = thing->y + thing->radius;
979
980 x2 = thing->x + thing->radius;
981 y2 = thing->y - thing->radius;
982 }
983 else
984 {
985 x1 = thing->x - thing->radius;
986 y1 = thing->y - thing->radius;
987
988 x2 = thing->x + thing->radius;
989 y2 = thing->y + thing->radius;
990 }
991
992 s1 = P_PointOnDivlineSide(x1, y1, &trace);
993 s2 = P_PointOnDivlineSide(x2, y2, &trace);
994
995 // line isn't crossed ?
996 if (s1 == s2)
997 return;
998
999 div.x = x1;
1000 div.y = y1;
1001 div.dx = x2 - x1;
1002 div.dy = y2 - y1;
1003
1004 frac = P_InterceptVector(&trace, &div);
1005
1006 // out of range?
1007 if (frac < 0 || frac > 1)
1008 return;
1009
1010 // Intercept is a simple struct that can be memcpy()'d: Load
1011 // up a structure and get into the array
1012 intercept_t in;
1013
1014 in.frac = frac;
1015 in.thing = thing;
1016 in.line = NULL;
1017
1018 intercepts.push_back(in);
1019 }
1020
1021
1022 struct Compare_Intercept_pred
1023 {
operator ()Compare_Intercept_pred1024 inline bool operator() (const intercept_t& A, const intercept_t& B) const
1025 {
1026 return A.frac < B.frac;
1027 }
1028 };
1029
1030 //
1031 // P_PathTraverse
1032 //
1033 // Traces a line from x1,y1 to x2,y2,
1034 // calling the traverser function for each.
1035 // Returns true if the traverser function returns true
1036 // for all lines.
1037 //
P_PathTraverse(float x1,float y1,float x2,float y2,int flags,bool (* func)(intercept_t *,void *),void * data)1038 bool P_PathTraverse(float x1, float y1, float x2, float y2, int flags,
1039 bool (* func)(intercept_t *, void *), void *data)
1040 {
1041 validcount++;
1042
1043 intercepts.clear();
1044
1045 // don't side exactly on a line
1046 if (fmod(x1 - bmap_orgx, BLOCKMAP_UNIT) == 0)
1047 x1 += 0.1f;
1048
1049 if (fmod(y1 - bmap_orgy, BLOCKMAP_UNIT) == 0)
1050 y1 += 0.1f;
1051
1052 trace.x = x1;
1053 trace.y = y1;
1054 trace.dx = x2 - x1;
1055 trace.dy = y2 - y1;
1056
1057 x1 -= bmap_orgx;
1058 y1 -= bmap_orgy;
1059 x2 -= bmap_orgx;
1060 y2 -= bmap_orgy;
1061
1062 int bx1 = (int)(x1 / BLOCKMAP_UNIT);
1063 int by1 = (int)(y1 / BLOCKMAP_UNIT);
1064 int bx2 = (int)(x2 / BLOCKMAP_UNIT);
1065 int by2 = (int)(y2 / BLOCKMAP_UNIT);
1066
1067 int bx_step;
1068 int by_step;
1069
1070 float xstep;
1071 float ystep;
1072
1073 float partial;
1074
1075 double tmp;
1076
1077
1078 if (bx2 > bx1 && (x2 - x1) > 0.001)
1079 {
1080 bx_step = 1;
1081 partial = 1.0f - modf(x1 / BLOCKMAP_UNIT, &tmp);
1082
1083 ystep = (y2 - y1) / fabs(x2 - x1);
1084 }
1085 else if (bx2 < bx1 && (x2 - x1) < -0.001)
1086 {
1087 bx_step = -1;
1088 partial = modf(x1 / BLOCKMAP_UNIT, &tmp);
1089
1090 ystep = (y2 - y1) / fabs(x2 - x1);
1091 }
1092 else
1093 {
1094 bx_step = 0;
1095 partial = 1.0f;
1096 ystep = 256.0f;
1097 }
1098
1099 float yintercept = y1 / BLOCKMAP_UNIT + partial * ystep;
1100
1101 if (by2 > by1 && (y2 - y1) > 0.001)
1102 {
1103 by_step = 1;
1104 partial = 1.0f - modf(y1 / BLOCKMAP_UNIT, &tmp);
1105
1106 xstep = (x2 - x1) / fabs(y2 - y1);
1107 }
1108 else if (by2 < by1 && (y2 - y1) < -0.001)
1109 {
1110 by_step = -1;
1111 partial = modf(y1 / BLOCKMAP_UNIT, &tmp);
1112
1113 xstep = (x2 - x1) / fabs(y2 - y1);
1114 }
1115 else
1116 {
1117 by_step = 0;
1118 partial = 1.0f;
1119 xstep = 256.0f;
1120 }
1121
1122 float xintercept = x1 / BLOCKMAP_UNIT + partial * xstep;
1123
1124 // Step through map blocks.
1125 // Count is present to prevent a round off error
1126 // from skipping the break.
1127 int bx = bx1;
1128 int by = by1;
1129
1130 for (int count = 0; count < 64; count++)
1131 {
1132 if (0 <= bx && bx < bmap_width &&
1133 0 <= by && by < bmap_height)
1134 {
1135 if (flags & PT_ADDLINES)
1136 {
1137 linedef_set_t *lset = bmap_lines[by * bmap_width + bx];
1138
1139 if (lset)
1140 {
1141 linedef_set_t::iterator LI;
1142 for (LI = lset->begin(); LI != lset->end(); LI++)
1143 {
1144 PIT_AddLineIntercept(*LI);
1145 }
1146 }
1147 }
1148
1149 if (flags & PT_ADDTHINGS)
1150 {
1151 for (mobj_t *mo = bmap_things[by * bmap_width + bx]; mo; mo = mo->bnext)
1152 {
1153 PIT_AddThingIntercept(mo);
1154 }
1155 }
1156 }
1157
1158 if (bx == bx2 && by == by2)
1159 break;
1160
1161 if (by == (int)yintercept)
1162 {
1163 yintercept += ystep;
1164 bx += bx_step;
1165 }
1166 else if (bx == (int)xintercept)
1167 {
1168 xintercept += xstep;
1169 by += by_step;
1170 }
1171 }
1172
1173 // go through the sorted list
1174
1175 if (intercepts.size() == 0)
1176 return true;
1177
1178 std::sort(intercepts.begin(), intercepts.end(),
1179 Compare_Intercept_pred());
1180
1181 std::vector<intercept_t>::iterator I;
1182
1183 for (I = intercepts.begin(); I != intercepts.end(); I++)
1184 {
1185 if (! func(& *I, data))
1186 {
1187 // don't bother going further
1188 return false;
1189 }
1190 }
1191
1192 // everything was traversed
1193 return true;
1194 }
1195
1196
1197 //--------------------------------------------------------------------------
1198 //
1199 // BLOCKMAP GENERATION
1200 //
1201
BlockAdd(int bnum,line_t * ld)1202 static void BlockAdd(int bnum, line_t *ld)
1203 {
1204 if (! bmap_lines[bnum])
1205 bmap_lines[bnum] = new linedef_set_t;
1206
1207 bmap_lines[bnum]->push_back(ld);
1208
1209 // blk_total_lines++;
1210 }
1211
BlockAddLine(int line_num)1212 static void BlockAddLine(int line_num)
1213 {
1214 int i, j;
1215 int x0, y0;
1216 int x1, y1;
1217
1218 line_t *ld = lines + line_num;
1219
1220 int blocknum;
1221
1222 int y_sign;
1223 int x_dist, y_dist;
1224
1225 float slope;
1226
1227 x0 = (int)(ld->v1->x - bmap_orgx);
1228 y0 = (int)(ld->v1->y - bmap_orgy);
1229 x1 = (int)(ld->v2->x - bmap_orgx);
1230 y1 = (int)(ld->v2->y - bmap_orgy);
1231
1232 // swap endpoints if horizontally backward
1233 if (x1 < x0)
1234 {
1235 int temp;
1236
1237 temp = x0; x0 = x1; x1 = temp;
1238 temp = y0; y0 = y1; y1 = temp;
1239 }
1240
1241 SYS_ASSERT(0 <= x0 && (x0 / BLOCKMAP_UNIT) < bmap_width);
1242 SYS_ASSERT(0 <= y0 && (y0 / BLOCKMAP_UNIT) < bmap_height);
1243 SYS_ASSERT(0 <= x1 && (x1 / BLOCKMAP_UNIT) < bmap_width);
1244 SYS_ASSERT(0 <= y1 && (y1 / BLOCKMAP_UNIT) < bmap_height);
1245
1246 // check if this line spans multiple blocks.
1247
1248 x_dist = ABS((x1 / BLOCKMAP_UNIT) - (x0 / BLOCKMAP_UNIT));
1249 y_dist = ABS((y1 / BLOCKMAP_UNIT) - (y0 / BLOCKMAP_UNIT));
1250
1251 y_sign = (y1 >= y0) ? 1 : -1;
1252
1253 // handle the simple cases: same column or same row
1254
1255 blocknum = (y0 / BLOCKMAP_UNIT) * bmap_width + (x0 / BLOCKMAP_UNIT);
1256
1257 if (y_dist == 0)
1258 {
1259 for (i=0; i <= x_dist; i++, blocknum++)
1260 BlockAdd(blocknum, ld);
1261
1262 return;
1263 }
1264
1265 if (x_dist == 0)
1266 {
1267 for (i=0; i <= y_dist; i++, blocknum += y_sign * bmap_width)
1268 BlockAdd(blocknum, ld);
1269
1270 return;
1271 }
1272
1273 // -AJA- 2000/12/09: rewrote the general case
1274
1275 SYS_ASSERT(x1 > x0);
1276
1277 slope = (float)(y1 - y0) / (float)(x1 - x0);
1278
1279 // handle each column of blocks in turn
1280 for (i=0; i <= x_dist; i++)
1281 {
1282 // compute intersection of column with line
1283 int sx = (i==0) ? x0 : (128 * (x0 / 128 + i));
1284 int ex = (i==x_dist) ? x1 : (128 * (x0 / 128 + i) + 127);
1285
1286 int sy = y0 + (int)(slope * (sx - x0));
1287 int ey = y0 + (int)(slope * (ex - x0));
1288
1289 SYS_ASSERT(sx <= ex);
1290
1291 y_dist = ABS((ey / 128) - (sy / 128));
1292
1293 for (j=0; j <= y_dist; j++)
1294 {
1295 blocknum = (sy / 128 + j * y_sign) * bmap_width + (sx / 128);
1296
1297 BlockAdd(blocknum, ld);
1298 }
1299 }
1300 }
1301
1302
P_GenerateBlockMap(int min_x,int min_y,int max_x,int max_y)1303 void P_GenerateBlockMap(int min_x, int min_y, int max_x, int max_y)
1304 {
1305 bmap_orgx = min_x - 8;
1306 bmap_orgy = min_y - 8;
1307 bmap_width = BLOCKMAP_GET_X(max_x) + 1;
1308 bmap_height = BLOCKMAP_GET_Y(max_y) + 1;
1309
1310 int btotal = bmap_width * bmap_height;
1311
1312 L_WriteDebug("GenerateBlockmap: MAP (%d,%d) -> (%d,%d)\n",
1313 min_x, min_y, max_x, max_y);
1314 L_WriteDebug("GenerateBlockmap: BLOCKS %d x %d TOTAL %d\n",
1315 bmap_width, bmap_height, btotal);
1316
1317 // setup blk_cur_lines array. Initially all pointers are NULL, when
1318 // any lines get added then the dynamic array is created.
1319
1320 bmap_lines = new linedef_set_t* [btotal];
1321
1322 Z_Clear(bmap_lines, linedef_set_t *, btotal);
1323
1324 // process each linedef of the map
1325 for (int i=0; i < numlines; i++)
1326 BlockAddLine(i);
1327
1328 // L_WriteDebug("GenerateBlockmap: TOTAL DATA=%d\n", blk_total_lines);
1329 }
1330
1331 //--- editor settings ---
1332 // vi:ts=4:sw=4:noexpandtab
1333