1 //**************************************************************************
2 //**
3 //** ## ## ## ## ## #### #### ### ###
4 //** ## ## ## ## ## ## ## ## ## ## #### ####
5 //** ## ## ## ## ## ## ## ## ## ## ## ## ## ##
6 //** ## ## ######## ## ## ## ## ## ## ## ### ##
7 //** ### ## ## ### ## ## ## ## ## ##
8 //** # ## ## # #### #### ## ##
9 //**
10 //** $Id: p_clip.cpp 4297 2010-06-03 22:49:00Z firebrand_kh $
11 //**
12 //** Copyright (C) 1999-2006 Jānis Legzdiņš
13 //**
14 //** This program is free software; you can redistribute it and/or
15 //** modify it under the terms of the GNU General Public License
16 //** as published by the Free Software Foundation; either version 2
17 //** of the License, or (at your option) any later version.
18 //**
19 //** This program is distributed in the hope that it will be useful,
20 //** but WITHOUT ANY WARRANTY; without even the implied warranty of
21 //** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22 //** GNU General Public License for more details.
23 //**
24 //**************************************************************************
25
26 // HEADER FILES ------------------------------------------------------------
27
28 #include "gamedefs.h"
29
30 // MACROS ------------------------------------------------------------------
31
32 // TYPES -------------------------------------------------------------------
33
34 struct VViewClipper::VClipNode
35 {
36 float From;
37 float To;
38 VClipNode* Prev;
39 VClipNode* Next;
40 };
41
42 // EXTERNAL FUNCTION PROTOTYPES --------------------------------------------
43
44 // PUBLIC FUNCTION PROTOTYPES ----------------------------------------------
45
46 // PRIVATE FUNCTION PROTOTYPES ---------------------------------------------
47
48 // EXTERNAL DATA DECLARATIONS ----------------------------------------------
49
50 // PUBLIC DATA DEFINITIONS -------------------------------------------------
51
52 // PRIVATE DATA DEFINITIONS ------------------------------------------------
53
54 // CODE --------------------------------------------------------------------
55
56 //==========================================================================
57 //
58 // VViewClipper::VViewClipper
59 //
60 //==========================================================================
61
VViewClipper()62 VViewClipper::VViewClipper()
63 : FreeClipNodes(NULL)
64 , ClipHead(NULL)
65 , ClipTail(NULL)
66 {
67 }
68
69 //==========================================================================
70 //
71 // VViewClipper::~VViewClipper
72 //
73 //==========================================================================
74
~VViewClipper()75 VViewClipper::~VViewClipper()
76 {
77 guard(VViewClipper::~VViewClipper);
78 ClearClipNodes(TVec(), NULL);
79 VClipNode* Node = FreeClipNodes;
80 while (Node)
81 {
82 VClipNode* Next = Node->Next;
83 delete Node;
84 Node = NULL;
85 Node = Next;
86 }
87 unguard;
88 }
89
90 //==========================================================================
91 //
92 // VViewClipper::NewClipNode
93 //
94 //==========================================================================
95
NewClipNode()96 VViewClipper::VClipNode* VViewClipper::NewClipNode()
97 {
98 guard(VViewClipper::NewClipNode);
99 VClipNode* Ret = FreeClipNodes;
100 if (Ret)
101 {
102 FreeClipNodes = Ret->Next;
103 }
104 else
105 {
106 Ret = new VClipNode();
107 }
108 return Ret;
109 unguard;
110 }
111
112 //==========================================================================
113 //
114 // VViewClipper::RemoveClipNode
115 //
116 //==========================================================================
117
RemoveClipNode(VViewClipper::VClipNode * Node)118 void VViewClipper::RemoveClipNode(VViewClipper::VClipNode* Node)
119 {
120 guard(VViewClipper::RemoveClipNode);
121 if (Node->Next)
122 {
123 Node->Next->Prev = Node->Prev;
124 }
125 if (Node->Prev)
126 {
127 Node->Prev->Next = Node->Next;
128 }
129 if (Node == ClipHead)
130 {
131 ClipHead = Node->Next;
132 }
133 if (Node == ClipTail)
134 {
135 ClipTail = Node->Prev;
136 }
137 Node->Next = FreeClipNodes;
138 FreeClipNodes = Node;
139 unguard;
140 }
141
142 //==========================================================================
143 //
144 // VViewClipper::ClearClipNodes
145 //
146 //==========================================================================
147
ClearClipNodes(const TVec & AOrigin,VLevel * ALevel)148 void VViewClipper::ClearClipNodes(const TVec& AOrigin, VLevel* ALevel)
149 {
150 guard(VViewClipper::ClearClipNodes);
151 if (ClipHead)
152 {
153 ClipTail->Next = FreeClipNodes;
154 FreeClipNodes = ClipHead;
155 }
156 ClipHead = NULL;
157 ClipTail = NULL;
158 Origin = AOrigin;
159 Level = ALevel;
160 unguard;
161 }
162
163 //==========================================================================
164 //
165 // VViewClipper::ClipInitFrustrumRange
166 //
167 //==========================================================================
168
ClipInitFrustrumRange(const TAVec & viewangles,const TVec & viewforward,const TVec & viewright,const TVec & viewup,float fovx,float fovy)169 void VViewClipper::ClipInitFrustrumRange(const TAVec& viewangles,
170 const TVec& viewforward, const TVec& viewright, const TVec& viewup,
171 float fovx, float fovy)
172 {
173 guard(VViewClipper::ClipInitFrustrumRange);
174 check(!ClipHead);
175
176 if (viewforward.z > 0.9 || viewforward.z < -0.9)
177 {
178 // Looking up or down, can see behind.
179 return;
180 }
181
182 TVec Pts[4];
183 TVec TransPts[4];
184 Pts[0] = TVec(1, fovx, fovy);
185 Pts[1] = TVec(1, fovx, -fovy);
186 Pts[2] = TVec(1, -fovx, fovy);
187 Pts[3] = TVec(1, -fovx, -fovy);
188 TVec clipforward = Normalise(TVec(viewforward.x, viewforward.y, 0.0));
189 float d1 = 0;
190 float d2 = 0;
191 for (int i = 0; i < 4; i++)
192 {
193 TransPts[i].x = Pts[i].y * viewright.x + Pts[i].z * viewup.x + Pts[i].x * viewforward.x;
194 TransPts[i].y = Pts[i].y * viewright.y + Pts[i].z * viewup.y + Pts[i].x * viewforward.y;
195 TransPts[i].z = Pts[i].y * viewright.z + Pts[i].z * viewup.z + Pts[i].x * viewforward.z;
196 if (DotProduct(TransPts[i], clipforward) <= 0)
197 {
198 // Player can see behind.
199 return;
200 }
201 float a = matan(TransPts[i].y, TransPts[i].x);
202 if (a < 0)
203 a += 360.0;
204 float d = AngleMod180(a - viewangles.yaw);
205 if (d1 > d)
206 d1 = d;
207 if (d2 < d)
208 d2 = d;
209 }
210 float a1 = AngleMod(viewangles.yaw + d1);
211 float a2 = AngleMod(viewangles.yaw + d2);
212 if (a1 > a2)
213 {
214 ClipHead = NewClipNode();
215 ClipTail = ClipHead;
216 ClipHead->From = a2;
217 ClipHead->To = a1;
218 ClipHead->Prev = NULL;
219 ClipHead->Next = NULL;
220 }
221 else
222 {
223 ClipHead = NewClipNode();
224 ClipHead->From = 0.0;
225 ClipHead->To = a1;
226 ClipTail = NewClipNode();
227 ClipTail->From = a2;
228 ClipTail->To = 360.0;
229 ClipHead->Prev = NULL;
230 ClipHead->Next = ClipTail;
231 ClipTail->Prev = ClipHead;
232 ClipTail->Next = NULL;
233 }
234 unguard;
235 }
236
237 //==========================================================================
238 //
239 // VViewClipper::ClipToRanges
240 //
241 //==========================================================================
242
ClipToRanges(const VViewClipper & Range)243 void VViewClipper::ClipToRanges(const VViewClipper& Range)
244 {
245 guard(VViewClipper::ClipToRanges);
246 if (!Range.ClipHead)
247 {
248 // No ranges, everything is clipped away.
249 DoAddClipRange(0.0, 360.0);
250 return;
251 }
252
253 // Add head and tail ranges.
254 if (Range.ClipHead->From > 0.0)
255 {
256 DoAddClipRange(0.0, Range.ClipHead->From);
257 }
258 if (Range.ClipTail->To < 360.0)
259 {
260 DoAddClipRange(Range.ClipTail->To, 360.0);
261 }
262
263 // Add middle ranges.
264 for (VClipNode* N = Range.ClipHead; N->Next; N = N->Next)
265 {
266 DoAddClipRange(N->To, N->Next->From);
267 }
268 unguard;
269 }
270
271 //==========================================================================
272 //
273 // VViewClipper::DoAddClipRange
274 //
275 //==========================================================================
276
DoAddClipRange(float From,float To)277 void VViewClipper::DoAddClipRange(float From, float To)
278 {
279 guard(VViewClipper::DoAddClipRange);
280 if (!ClipHead)
281 {
282 ClipHead = NewClipNode();
283 ClipTail = ClipHead;
284 ClipHead->From = From;
285 ClipHead->To = To;
286 ClipHead->Prev = NULL;
287 ClipHead->Next = NULL;
288 return;
289 }
290
291 for (VClipNode* Node = ClipHead; Node; Node = Node->Next)
292 {
293 if (Node->To < From)
294 {
295 // Before this range.
296 continue;
297 }
298
299 if (To < Node->From)
300 {
301 // Insert a new clip range before current one.
302 VClipNode* N = NewClipNode();
303 N->From = From;
304 N->To = To;
305 N->Prev = Node->Prev;
306 N->Next = Node;
307 if (Node->Prev)
308 {
309 Node->Prev->Next = N;
310 }
311 else
312 {
313 ClipHead = N;
314 }
315 Node->Prev = N;
316 return;
317 }
318
319 if (Node->From <= From && Node->To >= To)
320 {
321 // It contains this range.
322 return;
323 }
324
325 if (From < Node->From)
326 {
327 // Extend start of the current range.
328 Node->From = From;
329 }
330 if (To <= Node->To)
331 {
332 // End is included, so we are done here.
333 return;
334 }
335
336 // Merge with following nodes if needed.
337 while (Node->Next && Node->Next->From <= To)
338 {
339 Node->To = Node->Next->To;
340 RemoveClipNode(Node->Next);
341 }
342 if (To > Node->To)
343 {
344 // Extend end.
345 Node->To = To;
346 }
347 // We are done here.
348 return;
349 }
350
351 // If we are here it means it's a new range at the end.
352 VClipNode* NewTail = NewClipNode();
353 NewTail->From = From;
354 NewTail->To = To;
355 NewTail->Prev = ClipTail;
356 NewTail->Next = NULL;
357 ClipTail->Next = NewTail;
358 ClipTail = NewTail;
359 unguard;
360 }
361
362 //==========================================================================
363 //
364 // VViewClipper::AddClipRange
365 //
366 //==========================================================================
367
AddClipRange(float From,float To)368 void VViewClipper::AddClipRange(float From, float To)
369 {
370 guard(VViewClipper::AddClipRange);
371 if (From > To)
372 {
373 DoAddClipRange(0.0, To);
374 DoAddClipRange(From, 360.0);
375 }
376 else
377 {
378 DoAddClipRange(From, To);
379 }
380 unguard;
381 }
382
383 //==========================================================================
384 //
385 // VViewClipper::DoIsRangeVisible
386 //
387 //==========================================================================
388
DoIsRangeVisible(float From,float To)389 bool VViewClipper::DoIsRangeVisible(float From, float To)
390 {
391 guard(VViewClipper::DoIsRangeVisible);
392 for (VClipNode* N = ClipHead; N; N = N->Next)
393 {
394 if (From >= N->From && To <= N->To)
395 {
396 return false;
397 }
398 }
399 return true;
400 unguard;
401 }
402
403 //==========================================================================
404 //
405 // VViewClipper::IsRangeVisible
406 //
407 //==========================================================================
408
IsRangeVisible(float From,float To)409 bool VViewClipper::IsRangeVisible(float From, float To)
410 {
411 guard(VViewClipper::IsRangeVisible);
412 if (From > To)
413 {
414 return DoIsRangeVisible(0.0, To) || DoIsRangeVisible(From, 360.0);
415 }
416 else
417 {
418 return DoIsRangeVisible(From, To);
419 }
420 unguard;
421 }
422
423 //==========================================================================
424 //
425 // VViewClipper::ClipIsFull
426 //
427 //==========================================================================
428
ClipIsFull()429 bool VViewClipper::ClipIsFull()
430 {
431 guard(VViewClipper::ClipIsFull);
432 return ClipHead && ClipHead->From == 0.0 && ClipHead->To == 360.0;
433 unguard;
434 }
435
436 //==========================================================================
437 //
438 // VViewClipper::PointToClipAngle
439 //
440 //==========================================================================
441
PointToClipAngle(const TVec & Pt)442 float VViewClipper::PointToClipAngle(const TVec& Pt)
443 {
444 float Ret = matan(Pt.y - Origin.y, Pt.x - Origin.x);
445 if (Ret < 0)
446 Ret += 360.0;
447 return Ret;
448 }
449
450 //==========================================================================
451 //
452 // VViewClipper::ClipIsBBoxVisible
453 //
454 //==========================================================================
455
ClipIsBBoxVisible(float * BBox)456 bool VViewClipper::ClipIsBBoxVisible(float* BBox)
457 {
458 guard(VViewClipper::ClipIsBBoxVisible);
459 if (!ClipHead)
460 {
461 // No clip nodes yet.
462 return true;
463 }
464 if (BBox[0] <= Origin.x && BBox[3] >= Origin.x &&
465 BBox[1] <= Origin.y && BBox[4] >= Origin.y)
466 {
467 // Viewer is inside the box.
468 return true;
469 }
470
471 TVec v1;
472 TVec v2;
473 if (BBox[0] > Origin.x)
474 {
475 if (BBox[1] > Origin.y)
476 {
477 v1.x = BBox[3];
478 v1.y = BBox[1];
479 v2.x = BBox[0];
480 v2.y = BBox[4];
481 }
482 else if (BBox[4] < Origin.y)
483 {
484 v1.x = BBox[0];
485 v1.y = BBox[1];
486 v2.x = BBox[3];
487 v2.y = BBox[4];
488 }
489 else
490 {
491 v1.x = BBox[0];
492 v1.y = BBox[1];
493 v2.x = BBox[0];
494 v2.y = BBox[4];
495 }
496 }
497 else if (BBox[3] < Origin.x)
498 {
499 if (BBox[1] > Origin.y)
500 {
501 v1.x = BBox[3];
502 v1.y = BBox[4];
503 v2.x = BBox[0];
504 v2.y = BBox[1];
505 }
506 else if (BBox[4] < Origin.y)
507 {
508 v1.x = BBox[0];
509 v1.y = BBox[4];
510 v2.x = BBox[3];
511 v2.y = BBox[1];
512 }
513 else
514 {
515 v1.x = BBox[3];
516 v1.y = BBox[4];
517 v2.x = BBox[3];
518 v2.y = BBox[1];
519 }
520 }
521 else
522 {
523 if (BBox[1] > Origin.y)
524 {
525 v1.x = BBox[3];
526 v1.y = BBox[1];
527 v2.x = BBox[0];
528 v2.y = BBox[1];
529 }
530 else
531 {
532 v1.x = BBox[0];
533 v1.y = BBox[4];
534 v2.x = BBox[3];
535 v2.y = BBox[4];
536 }
537 }
538 return IsRangeVisible(PointToClipAngle(v1), PointToClipAngle(v2));
539 unguard;
540 }
541
542 //==========================================================================
543 //
544 // VViewClipper::ClipCheckSubsector
545 //
546 //==========================================================================
547
ClipCheckSubsector(subsector_t * Sub)548 bool VViewClipper::ClipCheckSubsector(subsector_t* Sub)
549 {
550 guard(VViewClipper::ClipCheckSubsector);
551 if (!ClipHead)
552 {
553 return true;
554 }
555 for (int i = 0; i < Sub->numlines; i++)
556 {
557 seg_t* line = &Level->Segs[Sub->firstline + i];
558
559 float dist = DotProduct(Origin, line->normal) - line->dist;
560 if (dist <= 0)
561 {
562 // Viewer is in back side or on plane
563 continue;
564 }
565
566 if (IsRangeVisible(PointToClipAngle(*line->v2),
567 PointToClipAngle(*line->v1)))
568 {
569 return true;
570 }
571 }
572 return false;
573 unguard;
574 }
575
576 //==========================================================================
577 //
578 // VViewClipper::ClipAddSubsectorSegs
579 //
580 //==========================================================================
581
ClipAddSubsectorSegs(subsector_t * Sub,TPlane * Mirror)582 void VViewClipper::ClipAddSubsectorSegs(subsector_t* Sub, TPlane* Mirror)
583 {
584 guard(VViewClipper::ClipAddSubsectorSegs);
585 for (int i = 0; i < Sub->numlines; i++)
586 {
587 seg_t* line = &Level->Segs[Sub->firstline + i];
588 if (line->backsector || !line->linedef)
589 {
590 // Miniseg or two-sided line.
591 continue;
592 }
593
594 float dist = DotProduct(Origin, line->normal) - line->dist;
595 if (dist <= 0)
596 {
597 // Viewer is in back side or on plane
598 continue;
599 }
600
601 TVec v1 = *line->v1;
602 TVec v2 = *line->v2;
603 if (Mirror)
604 {
605 // Clip seg with mirror plane.
606 float Dist1 = DotProduct(v1, Mirror->normal) - Mirror->dist;
607 float Dist2 = DotProduct(v2, Mirror->normal) - Mirror->dist;
608 if (Dist1 <= 0 && Dist2 <= 0)
609 {
610 continue;
611 }
612 if (Dist1 > 0 && Dist2 < 0)
613 {
614 v2 = v1 + (v2 - v1) * Dist1 / (Dist1 - Dist2);
615 }
616 else if (Dist2 > 0 && Dist1 < 0)
617 {
618 v1 = v2 + (v1 - v2) * Dist2 / (Dist2 - Dist1);
619 }
620 }
621
622 AddClipRange(PointToClipAngle(v2), PointToClipAngle(v1));
623 }
624
625 if (Sub->poly)
626 {
627 seg_t** polySeg = Sub->poly->segs;
628 for (int polyCount = Sub->poly->numsegs; polyCount--; polySeg++)
629 {
630 seg_t* line = *polySeg;
631 if (line->backsector || !line->linedef)
632 {
633 // Miniseg or two-sided line.
634 continue;
635 }
636
637 float dist = DotProduct(Origin, line->normal) - line->dist;
638 if (dist <= 0)
639 {
640 // Viewer is in back side or on plane
641 continue;
642 }
643
644 TVec v1 = *line->v1;
645 TVec v2 = *line->v2;
646
647 AddClipRange(PointToClipAngle(v2), PointToClipAngle(v1));
648 }
649 }
650 unguard;
651 }
652