osezer patch 009
[theoddone33/hhexen.git] / opengl / ogl_clip.c
1
2 //**************************************************************************
3 //**
4 //** OGL_CLIP.C
5 //**
6 //** Version:           1.0
7 //** Last Build:        -?-
8 //** Author:            jk
9 //**
10 //**************************************************************************
11
12 // HEADER FILES ------------------------------------------------------------
13
14 #ifdef __WIN32__
15 #include <windows.h>
16 #endif
17 #include <stdlib.h>
18 #include "h2def.h"
19 #include "r_local.h"
20 #include "m_bams.h"
21 #include "ogl_def.h"
22 //#include "i_ptimer.h"
23
24 // MACROS ------------------------------------------------------------------
25
26 #define MAXCLIPNODES    128             // We can have this many nodes at once.
27
28 // TYPES -------------------------------------------------------------------
29
30 // EXTERNAL FUNCTION PROTOTYPES --------------------------------------------
31
32 // PUBLIC FUNCTION PROTOTYPES ----------------------------------------------
33
34 // PRIVATE FUNCTION PROTOTYPES ---------------------------------------------
35
36 // EXTERNAL DATA DECLARATIONS ----------------------------------------------
37
38 extern float vx, vz;
39
40 //extern __int64 clippercount;
41 //extern perfclock_t clipperclock;
42
43 // PUBLIC DATA DEFINITIONS -------------------------------------------------
44
45 clipnode_t *clipnodes;  // The list of clipnodes.
46 clipnode_t *cliphead;   // The head node.
47
48 int maxnumnodes=0;              
49
50 // PRIVATE DATA DEFINITIONS ------------------------------------------------
51
52 // CODE --------------------------------------------------------------------
53 /*
54 static void C_CountNodes()
55 {
56         int     i;
57         clipnode_t *ci;
58         for(i=0, ci=cliphead; ci; i++, ci=ci->next);
59         if(i > maxnumnodes) maxnumnodes = i;
60 }
61 */
62 void C_Init()
63 {
64         clipnodes = Z_Malloc(sizeof(clipnode_t)*MAXCLIPNODES, PU_STATIC, 0);
65 }
66
67 void C_ClearRanges()
68 {
69         memset(clipnodes, 0, sizeof(clipnode_t)*MAXCLIPNODES);
70         cliphead = 0;
71 }
72
73 // Finds the first unused clip node.
74 static clipnode_t *C_NewRange(binangle stAng, binangle endAng)  
75 {
76         int                     i;
77         clipnode_t      *cnode;
78
79         for(i=0; i<MAXCLIPNODES; i++) if(!clipnodes[i].used) break;
80         if(i==MAXCLIPNODES-1) I_Error("C_NewRange: Out of clipnodes (max %d).\n", MAXCLIPNODES);
81         // Initialize the node.
82         cnode = clipnodes+i;
83         cnode->used = 1;
84         cnode->start = stAng;
85         cnode->end = endAng;
86         return cnode;
87 }
88
89 static void C_RemoveRange(clipnode_t *crange)
90 {
91         if(!crange->used) I_Error("Tried to remove an unused range.\n");
92
93         // If this is the head, move it.
94         if(cliphead == crange) cliphead = crange->next;
95
96         crange->used = 0;
97         if(crange->prev) crange->prev->next = crange->next;
98         if(crange->next) crange->next->prev = crange->prev;
99         crange->prev = crange->next = 0;
100 }
101
102 static void C_AddRange(binangle startAngle, binangle endAngle)
103 {
104         clipnode_t      *ci, *crange;
105
106         //printf( "=== C_AddRange(%x,%x):\n",startAngle,endAngle);
107         if(startAngle == endAngle)
108         {
109                 //printf( "  range has no length, skipping\n");
110                 return;
111         }
112         // There are previous ranges. Check that the new range isn't contained
113         // by any of them.
114         for(ci=cliphead; ci; ci=ci->next)
115         {
116                 //printf( "      %p: %4x => %4x (%d)\n",ci,ci->start,ci->end,ci->used);
117                 if(startAngle >= ci->start && endAngle <= ci->end)
118                 {
119                         //printf( "  range already exists\n");
120                         return; // The new range already exists.
121                 }
122                 //printf( "loop1\n");
123                 /*if(ci == ci->next)
124                         I_Error("%p linked to itself: %x => %x\n",ci,ci->start,ci->end);*/
125         }
126
127         // Now check if any of the old ranges are contained by the new one.
128         for(ci=cliphead; ci;)
129         {
130                 //printf( "loop2\n");
131                 if(ci->start >= startAngle && ci->end <= endAngle)
132                 {
133                         crange = ci;
134                         //printf( "  removing contained range %x => %x\n",crange->start,crange->end);
135                         // We must do this in order to keep the loop from breaking.
136                         ci = ci->next;  
137                         C_RemoveRange(crange);
138                         //if(!ci) ci = cliphead;
139                         //if(!ci) break;
140                         continue;
141                 }       
142                 ci = ci->next;
143         }
144
145         // If there is no head, this will be the first range.
146         if(!cliphead)
147         {
148                 cliphead = C_NewRange(startAngle, endAngle);
149                 //printf( "  new head node added, %x => %x\n", cliphead->start, cliphead->end);
150                 return;
151         }
152
153         // Now it is possible that the new range overlaps one or two old ranges.
154         // If two are overlapped, they are consecutive. First we'll try to find
155         // a range that overlaps the beginning.
156         for(ci=cliphead; ci; ci=ci->next)
157         {
158                 //printf( "loop3\n");
159                 if(ci->start >= startAngle && ci->start <= endAngle)
160                 {
161                         // New range's end and ci's beginning overlap. ci's end is outside.
162                         // Otherwise it would have been already removed.
163                         // It suffices to adjust ci.
164                         //printf( "  overlapping beginning with %x => %x, ",ci->start,ci->end);
165                         ci->start = startAngle;
166                         //printf( "adjusting ci to %x => %x\n",ci->start,ci->end);
167                         return;
168                 }
169                 // Check an overlapping end.
170                 if(ci->end >= startAngle && ci->end <= endAngle)
171                 {
172                         // Now it's possible that the ci->next's beginning overlaps the new
173                         // range's end. In that case there will be a merger.
174                         //printf( "  overlapping end with %x => %x:\n",ci->start,ci->end);
175                         crange = ci->next;
176                         if(!crange)
177                         {
178                                 ci->end = endAngle;
179                                 //printf( "    no next, adjusting end (now %x => %x)\n",ci->start,ci->end);
180                                 return;
181                         }
182                         else
183                         {
184                                 if(/*crange->start >= startAngle && */crange->start <= endAngle)
185                                 {
186                                         // Hello! A fusion will commence. Ci will eat the new
187                                         // range AND crange.
188                                         ci->end = crange->end;
189                                         //printf( "    merging with the next (%x => %x)\n",crange->start,crange->end);
190                                         C_RemoveRange(crange);
191                                         return;
192                                 }
193                                 else
194                                 {
195                                         // No overlapping: the same, normal case.
196                                         ci->end = endAngle;
197                                         //printf( "    not merger w/next, ci is now %x => %x\n",ci->start,ci->end);
198                                         return;
199                                 }
200                         }
201                 }
202         }
203         
204         // Still here? Now we know for sure that the range is disconnected from
205         // the others. We still need to find a good place for it. Crange will mark
206         // the spot. 
207         
208         // OPTIMIZE: Why not search this during the last loop?
209
210         //printf( "  range doesn't overlap old ones:\n");
211         crange = 0;
212         for(ci=cliphead; ci; ci=ci->next)
213         {
214         //      //printf( "loop4\n");
215                 if(ci->start < endAngle) // Is this a suitable spot?
216                         crange = ci; // Add after this one.
217                 else break;     // We're done.
218         }
219         if(!crange)
220         {
221                 //printf( "    no suitable new spot, adding to head\n");
222                 // We have a new head node.
223                 crange = cliphead;
224                 cliphead = C_NewRange(startAngle, endAngle);
225                 cliphead->next = crange;
226                 crange->prev = cliphead;
227                 return;
228         }
229         //printf("  spot found, adding after %x => %x\n",crange->start,crange->end);
230         // Add the new range after crange.
231         ci = C_NewRange(startAngle, endAngle);
232         ci->next = crange->next;
233         if(ci->next) ci->next->prev = ci;
234         ci->prev = crange;
235         crange->next = ci;
236 }
237
238 void C_Ranger()
239 {
240         clipnode_t *ci;
241
242         printf("Ranger:\n");
243         for(ci=cliphead; ci; ci=ci->next)
244         {
245                 if(ci==cliphead)
246                 {
247                         if(ci->prev != 0)
248                                 I_Error("Cliphead->prev != 0.\n");
249                 }
250                 // Confirm that the links to prev and next are OK.
251                 if(ci->prev)
252                 {
253                         if(ci->prev->next != ci)
254                                 I_Error("Prev->next != this\n");
255                 }
256                 else if(ci != cliphead) I_Error("prev == null, this isn't cliphead.\n");
257
258                 if(ci->next)
259                 {
260                         if(ci->next->prev != ci)
261                                 I_Error("Next->prev != this\n");
262                 }
263
264                 printf( "  %p: %04x => %04x ", ci, ci->start, ci->end);
265                 if(ci->prev)
266                         printf( "(gap: %d)\n", ci->start-ci->prev->end);
267                 else
268                         printf( "\n");
269         }
270 }
271
272 void C_SafeAddRange(binangle startAngle, binangle endAngle)
273 {
274         binangle angLen = endAngle-startAngle;
275
276         //printf( "Adding range %x => %x...\n", startAngle, endAngle);
277
278         // Check if the range is valid.
279         if(!angLen || angLen > BANG_180) return;
280
281         // The range may still wrap around.
282         if((int)startAngle+(int)angLen > BANG_MAX)
283         {
284         //      printf( "    adding in two parts\n");
285                 // The range has to added in two parts.
286                 C_AddRange(startAngle, BANG_MAX);
287                 //C_Ranger();
288                 C_AddRange(0, endAngle);
289                 //C_Ranger();
290         }
291         else
292         {
293         //      printf( "    adding normally\n");
294                 // Add the range as usual.
295                 C_AddRange(startAngle, endAngle);
296                 //C_Ranger();
297         }
298         //C_CountNodes();       // Just development info.
299         //C_Ranger();
300 }
301
302 // Add a segment relative to the current viewpoint.
303 void C_AddViewRelSeg(float x1, float y1, float x2, float y2)
304 {
305         float dx1 = x1-vx, dy1 = y1-vz, dx2 = x2-vx, dy2 = y2-vz;
306 //      __int64 pstart, pend;
307
308 //      QueryPerformanceCounter((LARGE_INTEGER*)&pstart);
309         //PC_Start(&clipperclock);
310
311         C_SafeAddRange(bamsAtan2((int)(dy2*10), (int)(dx2*10)), 
312                 bamsAtan2((int)(dy1*10), (int)(dx1*10)));
313
314         //QueryPerformanceCounter((LARGE_INTEGER*)&pend);
315         //clippercount += pend-pstart;
316         //PC_Stop(&clipperclock);
317 }
318
319 // The specified range must be safe!
320 static int C_IsRangeVisible(binangle startAngle, binangle endAngle)
321 {
322         clipnode_t      *ci;
323         
324         for(ci=cliphead; ci; ci=ci->next)
325                 if(startAngle >= ci->start && endAngle <= ci->end)
326                         return 0;
327         // No node fully contained the specified range.
328         return 1;
329 }
330
331 // Returns 1 if the range is not entirely clipped.
332 static int C_SafeCheckRange(binangle startAngle, binangle endAngle)
333 {
334         binangle angLen = endAngle - startAngle;
335
336         // Check that the range is valid.
337         if(!angLen || angLen >= BANG_180) return 0;
338         if((int)startAngle+(int)angLen > BANG_MAX)
339         {
340                 // The range wraps around.
341                 return (C_IsRangeVisible(startAngle, BANG_MAX) 
342                         || C_IsRangeVisible(0, endAngle));
343         }
344         return C_IsRangeVisible(startAngle, endAngle);
345 }
346
347 int C_CheckViewRelSeg(float x1, float y1, float x2, float y2)
348 {
349         float dx1 = x1-vx, dy1 = y1-vz, dx2 = x2-vx, dy2 = y2-vz;
350         return C_SafeCheckRange(bamsAtan2((int)(dy2*10), (int)(dx2*10)), 
351                 bamsAtan2((int)(dy1*10), (int)(dx1*10)));
352 }
353
354 // Returns 1 if the specified angle is visible.
355 int C_IsAngleVisible(binangle bang)
356 {
357         clipnode_t      *ci;
358
359         for(ci=cliphead; ci; ci=ci->next)
360                 if(bang > ci->start && bang < ci->end) return 0;
361         // No one clipped this angle.
362         return 1;
363 }
364
365 clipnode_t *C_AngleClippedBy(binangle bang)
366 {
367         clipnode_t      *ci;
368
369         for(ci=cliphead; ci; ci=ci->next)
370                 if(bang > ci->start && bang < ci->end) return ci;
371         // No one clipped this angle.
372         return 0;
373 }
374
375 // Returns 1 if the subsector might be visible.
376 int C_CheckSubsector(subsector_t *ssec)
377 {
378         int                     i;
379 //      clipnode_t      *cnode=0;
380         binangle        *anglist = (binangle*)malloc(sizeof(binangle)*ssec->numedgeverts);
381
382         if (anglist == NULL) I_Error ("Couldn't allocate memory");
383 //      extern perfclock_t miscclock;
384
385         //PC_Start(&miscclock);
386         for(i=0; i<ssec->numedgeverts; i++)     // Check all corners.
387         {
388                 fvertex_t *vtx = ssec->edgeverts+i;
389 /*              clipnode_t *clipper = C_AngleClippedBy(bamsAtan2((int)((vtx->y - vz)*10), 
390                         (int)((vtx->x - vx)*10)));
391                 // If no one clipped the angle, there is a visible portion.
392                 if(!clipper) return 1;
393                 if(!cnode) 
394                         cnode = clipper;
395                 else if(cnode != clipper) 
396                         return 1;*/
397                 
398                 anglist[i] = bamsAtan2((int)((vtx->y - vz)*100), (int)((vtx->x - vx)*100));
399                 
400                 /*if(!i)
401                         minAngle = maxAngle = anglist[i];
402                 else
403                 {
404                         if(anglist[i] < minAngle) minAngle = anglist[i];
405                         if(anglist[i] > maxAngle) maxAngle = anglist[i];
406                 }*/
407         }
408         //PC_Stop(&miscclock);
409         // Check each of the ranges defined by the edges.
410         for(i=0; i<ssec->numedgeverts-1; i++)
411         {
412                 int end = i+1;
413                 binangle angLen;
414
415                 // The last edge won't be checked. This is because the edges
416                 // define a closed, convex polygon and the last edge's range is 
417                 // always already covered by the previous edges. (Right?)
418                 
419                 //if(end == ssec->numedgeverts) end = 0;        // Back to beginning.
420
421                 // If even one of the edges is not contained by a clipnode, 
422                 // the subsector is at least partially visible.
423
424                 angLen = anglist[end] - anglist[i];
425                 
426                 if(angLen == BANG_180) continue;        // We can't check this.
427
428                 // Choose the start and end points so that length is < 180.
429                 if(angLen < BANG_180)
430                 {
431                         if(C_SafeCheckRange(anglist[i], anglist[end])) { free(anglist); return 1; }
432                 }
433                 else
434                 {
435                         if(C_SafeCheckRange(anglist[end], anglist[i])) { free(anglist); return 1; }
436                 }
437         }
438         // All the edges were clipped totally away.
439         free (anglist);
440         return 0;
441 /*
442 truexit:
443         PC_Stop(&miscclock);
444         return 1;*/
445
446         
447
448         /*if(maxAngle-minAngle > BANG_180)      // Does wraparound happen?
449         {
450                 // First the angles must be sorted (min -> max).
451                 qsort(anglist, ssec->numedgeverts, sizeof(binangle), AngleSorter);
452                 // Let's find the section that's over 180 degrees.
453                 // Check all but the last edge.
454                 for(i=0; i<ssec->numedgeverts-1; i++)
455                 {
456                         int end = i+1;
457                         if(anglist[end]-anglist[i] > BANG_180)
458                         {
459                                 // This is the long edge.
460                                 return (!C_IsRangeContained(0, anglist[i]) && 
461                                         !C_IsRangeContained(anglist[end], BANG_MAX));
462                         }
463                 }               
464                 for(i=0; i<ssec->numedgeverts; i++)
465                         printf( "anglist[%d] = %x\n", i, anglist[i]);
466                 I_Error("C_CheckSubsector: (wraparound) Can't find long edge.\n");
467                 return 0;       // Keep the compiler happy.
468         }
469         else
470         {
471                 // The range is OK, check it out.
472                 return (!C_IsRangeContained(minAngle, maxAngle));
473         }*/
474 /*static int AngleSorter(const binangle *elem1, const binangle *elem2)
475 {
476         if(*elem1 > *elem2) return 1;
477         if(*elem1 < *elem2) return -1;
478         return 0;
479 }
480 */
481
482 }
483