1 /* Emacs style mode select -*- C++ -*-
2 *-----------------------------------------------------------------------------
3 *
4 *
5 * PrBoom: a Doom port merged with LxDoom and LSDLDoom
6 * based on BOOM, a modified and improved DOOM engine
7 * Copyright (C) 1999 by
8 * id Software, Chi Hoang, Lee Killough, Jim Flynn, Rand Phares, Ty Halderman
9 * Copyright (C) 1999-2000 by
10 * Jess Haas, Nicolas Kalkhof, Colin Phipps, Florian Schulze
11 * Copyright 2005, 2006 by
12 * Florian Schulze, Colin Phipps, Neil Stevens, Andrey Budko
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 * You should have received a copy of the GNU General Public License
25 * along with this program; if not, write to the Free Software
26 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
27 * 02111-1307, USA.
28 *
29 * DESCRIPTION:
30 *
31 *---------------------------------------------------------------------
32 */
33
34 /*
35 *
36 ** gl_clipper.cpp
37 **
38 ** Handles visibility checks.
39 ** Loosely based on the JDoom clipper.
40 **
41 **---------------------------------------------------------------------------
42 ** Copyright 2003 Tim Stump
43 ** All rights reserved.
44 **
45 ** Redistribution and use in source and binary forms, with or without
46 ** modification, are permitted provided that the following conditions
47 ** are met:
48 **
49 ** 1. Redistributions of source code must retain the above copyright
50 ** notice, this list of conditions and the following disclaimer.
51 ** 2. Redistributions in binary form must reproduce the above copyright
52 ** notice, this list of conditions and the following disclaimer in the
53 ** documentation and/or other materials provided with the distribution.
54 ** 3. The name of the author may not be used to endorse or promote products
55 ** derived from this software without specific prior written permission.
56 **
57 ** THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
58 ** IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
59 ** OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
60 ** IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
61 ** INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
62 ** NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
63 ** DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
64 ** THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
65 ** (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
66 ** THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
67 **---------------------------------------------------------------------------
68 **
69 */
70
71 #include <math.h>
72 #include "../v_video.h"
73 #include "hw_clip.h"
74 #include "hw_glob.h"
75 #include "../r_main.h"
76 #include "../r_state.h"
77 #include "../tables.h"
78 #include "r_opengl/r_opengl.h"
79
80 #ifdef HAVE_SPHEREFRUSTRUM
81 static GLdouble viewMatrix[16];
82 static GLdouble projMatrix[16];
83 float frustum[6][4];
84 #endif
85
86 typedef struct clipnode_s
87 {
88 struct clipnode_s *prev, *next;
89 angle_t start, end;
90 } clipnode_t;
91
92 clipnode_t *freelist;
93 clipnode_t *clipnodes;
94 clipnode_t *cliphead;
95
96 static clipnode_t * gld_clipnode_GetNew(void);
97 static clipnode_t * gld_clipnode_NewRange(angle_t start, angle_t end);
98 static boolean gld_clipper_IsRangeVisible(angle_t startAngle, angle_t endAngle);
99 static void gld_clipper_AddClipRange(angle_t start, angle_t end);
100 static void gld_clipper_RemoveRange(clipnode_t * range);
101 static void gld_clipnode_Free(clipnode_t *node);
102
gld_clipnode_GetNew(void)103 static clipnode_t * gld_clipnode_GetNew(void)
104 {
105 if (freelist)
106 {
107 clipnode_t * p = freelist;
108 freelist = p->next;
109 return p;
110 }
111 else
112 {
113 return (clipnode_t*)malloc(sizeof(clipnode_t));
114 }
115 }
116
gld_clipnode_NewRange(angle_t start,angle_t end)117 static clipnode_t * gld_clipnode_NewRange(angle_t start, angle_t end)
118 {
119 clipnode_t * c = gld_clipnode_GetNew();
120 c->start = start;
121 c->end = end;
122 c->next = c->prev=NULL;
123 return c;
124 }
125
gld_clipper_SafeCheckRange(angle_t startAngle,angle_t endAngle)126 boolean gld_clipper_SafeCheckRange(angle_t startAngle, angle_t endAngle)
127 {
128 if(startAngle > endAngle)
129 {
130 return (gld_clipper_IsRangeVisible(startAngle, ANGLE_MAX) || gld_clipper_IsRangeVisible(0, endAngle));
131 }
132
133 return gld_clipper_IsRangeVisible(startAngle, endAngle);
134 }
135
gld_clipper_IsRangeVisible(angle_t startAngle,angle_t endAngle)136 static boolean gld_clipper_IsRangeVisible(angle_t startAngle, angle_t endAngle)
137 {
138 clipnode_t *ci;
139 ci = cliphead;
140
141 if (endAngle == 0 && ci && ci->start == 0)
142 return false;
143
144 while (ci != NULL && ci->start < endAngle)
145 {
146 if (startAngle >= ci->start && endAngle <= ci->end)
147 {
148 return false;
149 }
150 ci = ci->next;
151 }
152
153 return true;
154 }
155
gld_clipnode_Free(clipnode_t * node)156 static void gld_clipnode_Free(clipnode_t *node)
157 {
158 node->next = freelist;
159 freelist = node;
160 }
161
gld_clipper_RemoveRange(clipnode_t * range)162 static void gld_clipper_RemoveRange(clipnode_t *range)
163 {
164 if (range == cliphead)
165 {
166 cliphead = cliphead->next;
167 }
168 else
169 {
170 if (range->prev)
171 {
172 range->prev->next = range->next;
173 }
174 if (range->next)
175 {
176 range->next->prev = range->prev;
177 }
178 }
179
180 gld_clipnode_Free(range);
181 }
182
gld_clipper_SafeAddClipRange(angle_t startangle,angle_t endangle)183 void gld_clipper_SafeAddClipRange(angle_t startangle, angle_t endangle)
184 {
185 if(startangle > endangle)
186 {
187 // The range has to added in two parts.
188 gld_clipper_AddClipRange(startangle, ANGLE_MAX);
189 gld_clipper_AddClipRange(0, endangle);
190 }
191 else
192 {
193 // Add the range as usual.
194 gld_clipper_AddClipRange(startangle, endangle);
195 }
196 }
197
gld_clipper_AddClipRange(angle_t start,angle_t end)198 static void gld_clipper_AddClipRange(angle_t start, angle_t end)
199 {
200 clipnode_t *node, *temp, *prevNode, *node2, *delnode;
201
202 if (cliphead)
203 {
204 //check to see if range contains any old ranges
205 node = cliphead;
206 while (node != NULL && node->start < end)
207 {
208 if (node->start >= start && node->end <= end)
209 {
210 temp = node;
211 node = node->next;
212 gld_clipper_RemoveRange(temp);
213 }
214 else
215 {
216 if (node->start <= start && node->end >= end)
217 {
218 return;
219 }
220 else
221 {
222 node = node->next;
223 }
224 }
225 }
226
227 //check to see if range overlaps a range (or possibly 2)
228 node = cliphead;
229 while (node != NULL && node->start <= end)
230 {
231 if (node->end >= start)
232 {
233 // we found the first overlapping node
234 if (node->start > start)
235 {
236 // the new range overlaps with this node's start point
237 node->start = start;
238 }
239 if (node->end < end)
240 {
241 node->end = end;
242 }
243
244 node2 = node->next;
245 while (node2 && node2->start <= node->end)
246 {
247 if (node2->end > node->end)
248 {
249 node->end = node2->end;
250 }
251
252 delnode = node2;
253 node2 = node2->next;
254 gld_clipper_RemoveRange(delnode);
255 }
256 return;
257 }
258 node = node->next;
259 }
260
261 //just add range
262 node = cliphead;
263 prevNode = NULL;
264 temp = gld_clipnode_NewRange(start, end);
265 while (node != NULL && node->start < end)
266 {
267 prevNode = node;
268 node = node->next;
269 }
270 temp->next = node;
271 if (node == NULL)
272 {
273 temp->prev = prevNode;
274 if (prevNode)
275 {
276 prevNode->next = temp;
277 }
278 if (!cliphead)
279 {
280 cliphead = temp;
281 }
282 }
283 else
284 {
285 if (node == cliphead)
286 {
287 cliphead->prev = temp;
288 cliphead = temp;
289 }
290 else
291 {
292 temp->prev = prevNode;
293 prevNode->next = temp;
294 node->prev = temp;
295 }
296 }
297 }
298 else
299 {
300 temp = gld_clipnode_NewRange(start, end);
301 cliphead = temp;
302 return;
303 }
304 }
305
gld_clipper_Clear(void)306 void gld_clipper_Clear(void)
307 {
308 clipnode_t *node = cliphead;
309 clipnode_t *temp;
310
311 while (node != NULL)
312 {
313 temp = node;
314 node = node->next;
315 gld_clipnode_Free(temp);
316 }
317
318 cliphead = NULL;
319 }
320
321 #define RMUL (1.6f/1.333333f)
322
gld_FrustumAngle(angle_t tiltangle)323 angle_t gld_FrustumAngle(angle_t tiltangle)
324 {
325 double floatangle;
326 angle_t a1;
327
328 float tilt = (float)fabs(((double)(int)tiltangle) / ANG1);
329
330 // NEWCLIP TODO: SRB2CBTODO: make a global render_fov for this function
331
332 float render_fov = FIXED_TO_FLOAT(cv_fov.value);
333 float render_fovratio = (float)BASEVIDWIDTH / (float)BASEVIDHEIGHT; // SRB2CBTODO: NEWCLIPTODO: Is this right?
334 float render_multiplier = 64.0f / render_fovratio / RMUL;
335
336 if (tilt > 90.0f)
337 {
338 tilt = 90.0f;
339 }
340
341 // If the pitch is larger than this you can look all around at a FOV of 90
342 if (abs((signed)tiltangle) > 46 * ANG1)
343 return 0xffffffff;
344
345 // ok, this is a gross hack that barely works...
346 // but at least it doesn't overestimate too much...
347 floatangle = 2.0f + (45.0f + (tilt / 1.9f)) * (float)render_fov * 48.0f / render_multiplier / 90.0f;
348 a1 = ANG1 * (int)floatangle;
349 if (a1 >= ANGLE_180)
350 return 0xffffffff;
351 return a1;
352 }
353
354 // SRB2CB I don't think used any of this stuff, let's disable for now since SRB2 probably doesn't want it either
355 // compiler complains about (p)glGetFloatv anyway, in case anyone wants this
356 // only r_opengl.c can use the base gl funcs as it turns out, that's a problem for whoever wants sphere frustum checks
357 // btw to renable define HAVE_SPHEREFRUSTRUM in hw_clip.h
358 #ifdef HAVE_SPHEREFRUSTRUM
359 //
360 // gld_FrustrumSetup
361 //
362
363 #define CALCMATRIX(a, b, c, d, e, f, g, h)\
364 (float)(viewMatrix[a] * projMatrix[b] + \
365 viewMatrix[c] * projMatrix[d] + \
366 viewMatrix[e] * projMatrix[f] + \
367 viewMatrix[g] * projMatrix[h])
368
369 #define NORMALIZE_PLANE(i)\
370 t = (float)sqrt(\
371 frustum[i][0] * frustum[i][0] + \
372 frustum[i][1] * frustum[i][1] + \
373 frustum[i][2] * frustum[i][2]); \
374 frustum[i][0] /= t; \
375 frustum[i][1] /= t; \
376 frustum[i][2] /= t; \
377 frustum[i][3] /= t
378
gld_FrustrumSetup(void)379 void gld_FrustrumSetup(void)
380 {
381 float t;
382 float clip[16];
383
384 pglGetFloatv(GL_PROJECTION_MATRIX, projMatrix);
385 pglGetFloatv(GL_MODELVIEW_MATRIX, viewMatrix);
386
387 clip[0] = CALCMATRIX(0, 0, 1, 4, 2, 8, 3, 12);
388 clip[1] = CALCMATRIX(0, 1, 1, 5, 2, 9, 3, 13);
389 clip[2] = CALCMATRIX(0, 2, 1, 6, 2, 10, 3, 14);
390 clip[3] = CALCMATRIX(0, 3, 1, 7, 2, 11, 3, 15);
391
392 clip[4] = CALCMATRIX(4, 0, 5, 4, 6, 8, 7, 12);
393 clip[5] = CALCMATRIX(4, 1, 5, 5, 6, 9, 7, 13);
394 clip[6] = CALCMATRIX(4, 2, 5, 6, 6, 10, 7, 14);
395 clip[7] = CALCMATRIX(4, 3, 5, 7, 6, 11, 7, 15);
396
397 clip[8] = CALCMATRIX(8, 0, 9, 4, 10, 8, 11, 12);
398 clip[9] = CALCMATRIX(8, 1, 9, 5, 10, 9, 11, 13);
399 clip[10] = CALCMATRIX(8, 2, 9, 6, 10, 10, 11, 14);
400 clip[11] = CALCMATRIX(8, 3, 9, 7, 10, 11, 11, 15);
401
402 clip[12] = CALCMATRIX(12, 0, 13, 4, 14, 8, 15, 12);
403 clip[13] = CALCMATRIX(12, 1, 13, 5, 14, 9, 15, 13);
404 clip[14] = CALCMATRIX(12, 2, 13, 6, 14, 10, 15, 14);
405 clip[15] = CALCMATRIX(12, 3, 13, 7, 14, 11, 15, 15);
406
407 // Right plane
408 frustum[0][0] = clip[ 3] - clip[ 0];
409 frustum[0][1] = clip[ 7] - clip[ 4];
410 frustum[0][2] = clip[11] - clip[ 8];
411 frustum[0][3] = clip[15] - clip[12];
412 NORMALIZE_PLANE(0);
413
414 // Left plane
415 frustum[1][0] = clip[ 3] + clip[ 0];
416 frustum[1][1] = clip[ 7] + clip[ 4];
417 frustum[1][2] = clip[11] + clip[ 8];
418 frustum[1][3] = clip[15] + clip[12];
419 NORMALIZE_PLANE(1);
420
421 // Bottom plane
422 frustum[2][0] = clip[ 3] + clip[ 1];
423 frustum[2][1] = clip[ 7] + clip[ 5];
424 frustum[2][2] = clip[11] + clip[ 9];
425 frustum[2][3] = clip[15] + clip[13];
426 NORMALIZE_PLANE(2);
427
428 // Top plane
429 frustum[3][0] = clip[ 3] - clip[ 1];
430 frustum[3][1] = clip[ 7] - clip[ 5];
431 frustum[3][2] = clip[11] - clip[ 9];
432 frustum[3][3] = clip[15] - clip[13];
433 NORMALIZE_PLANE(3);
434
435 // Far plane
436 frustum[4][0] = clip[ 3] - clip[ 2];
437 frustum[4][1] = clip[ 7] - clip[ 6];
438 frustum[4][2] = clip[11] - clip[10];
439 frustum[4][3] = clip[15] - clip[14];
440 NORMALIZE_PLANE(4);
441
442 // Near plane
443 frustum[5][0] = clip[ 3] + clip[ 2];
444 frustum[5][1] = clip[ 7] + clip[ 6];
445 frustum[5][2] = clip[11] + clip[10];
446 frustum[5][3] = clip[15] + clip[14];
447 NORMALIZE_PLANE(5);
448 }
449
gld_SphereInFrustum(float x,float y,float z,float radius)450 boolean gld_SphereInFrustum(float x, float y, float z, float radius)
451 {
452 int p;
453
454 for (p = 0; p < 4; p++)
455 {
456 if (frustum[p][0] * x +
457 frustum[p][1] * y +
458 frustum[p][2] * z +
459 frustum[p][3] <= -radius)
460 {
461 return false;
462 }
463 }
464 return true;
465 }
466 #endif
467