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