2 //**************************************************************************
10 //**************************************************************************
12 // HEADER FILES ------------------------------------------------------------
22 //#include "i_ptimer.h"
24 // MACROS ------------------------------------------------------------------
26 #define MAXCLIPNODES 128 // We can have this many nodes at once.
28 // TYPES -------------------------------------------------------------------
30 // EXTERNAL FUNCTION PROTOTYPES --------------------------------------------
32 // PUBLIC FUNCTION PROTOTYPES ----------------------------------------------
34 // PRIVATE FUNCTION PROTOTYPES ---------------------------------------------
36 // EXTERNAL DATA DECLARATIONS ----------------------------------------------
40 //extern __int64 clippercount;
41 //extern perfclock_t clipperclock;
43 // PUBLIC DATA DEFINITIONS -------------------------------------------------
45 clipnode_t *clipnodes; // The list of clipnodes.
46 clipnode_t *cliphead; // The head node.
50 // PRIVATE DATA DEFINITIONS ------------------------------------------------
52 // CODE --------------------------------------------------------------------
54 static void C_CountNodes()
58 for(i=0, ci=cliphead; ci; i++, ci=ci->next);
59 if(i > maxnumnodes) maxnumnodes = i;
64 clipnodes = Z_Malloc(sizeof(clipnode_t)*MAXCLIPNODES, PU_STATIC, 0);
69 memset(clipnodes, 0, sizeof(clipnode_t)*MAXCLIPNODES);
73 // Finds the first unused clip node.
74 static clipnode_t *C_NewRange(binangle stAng, binangle endAng)
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.
89 static void C_RemoveRange(clipnode_t *crange)
91 if(!crange->used) I_Error("Tried to remove an unused range.\n");
93 // If this is the head, move it.
94 if(cliphead == crange) cliphead = crange->next;
97 if(crange->prev) crange->prev->next = crange->next;
98 if(crange->next) crange->next->prev = crange->prev;
99 crange->prev = crange->next = 0;
102 static void C_AddRange(binangle startAngle, binangle endAngle)
104 clipnode_t *ci, *crange;
106 //printf( "=== C_AddRange(%x,%x):\n",startAngle,endAngle);
107 if(startAngle == endAngle)
109 //printf( " range has no length, skipping\n");
112 // There are previous ranges. Check that the new range isn't contained
114 for(ci=cliphead; ci; ci=ci->next)
116 //printf( " %p: %4x => %4x (%d)\n",ci,ci->start,ci->end,ci->used);
117 if(startAngle >= ci->start && endAngle <= ci->end)
119 //printf( " range already exists\n");
120 return; // The new range already exists.
122 //printf( "loop1\n");
124 I_Error("%p linked to itself: %x => %x\n",ci,ci->start,ci->end);*/
127 // Now check if any of the old ranges are contained by the new one.
128 for(ci=cliphead; ci;)
130 //printf( "loop2\n");
131 if(ci->start >= startAngle && ci->end <= endAngle)
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.
137 C_RemoveRange(crange);
138 //if(!ci) ci = cliphead;
145 // If there is no head, this will be the first range.
148 cliphead = C_NewRange(startAngle, endAngle);
149 //printf( " new head node added, %x => %x\n", cliphead->start, cliphead->end);
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)
158 //printf( "loop3\n");
159 if(ci->start >= startAngle && ci->start <= endAngle)
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);
169 // Check an overlapping end.
170 if(ci->end >= startAngle && ci->end <= endAngle)
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);
179 //printf( " no next, adjusting end (now %x => %x)\n",ci->start,ci->end);
184 if(/*crange->start >= startAngle && */crange->start <= endAngle)
186 // Hello! A fusion will commence. Ci will eat the new
188 ci->end = crange->end;
189 //printf( " merging with the next (%x => %x)\n",crange->start,crange->end);
190 C_RemoveRange(crange);
195 // No overlapping: the same, normal case.
197 //printf( " not merger w/next, ci is now %x => %x\n",ci->start,ci->end);
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
208 // OPTIMIZE: Why not search this during the last loop?
210 //printf( " range doesn't overlap old ones:\n");
212 for(ci=cliphead; ci; ci=ci->next)
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.
221 //printf( " no suitable new spot, adding to head\n");
222 // We have a new head node.
224 cliphead = C_NewRange(startAngle, endAngle);
225 cliphead->next = crange;
226 crange->prev = cliphead;
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;
243 for(ci=cliphead; ci; ci=ci->next)
248 I_Error("Cliphead->prev != 0.\n");
250 // Confirm that the links to prev and next are OK.
253 if(ci->prev->next != ci)
254 I_Error("Prev->next != this\n");
256 else if(ci != cliphead) I_Error("prev == null, this isn't cliphead.\n");
260 if(ci->next->prev != ci)
261 I_Error("Next->prev != this\n");
264 printf( " %p: %04x => %04x ", ci, ci->start, ci->end);
266 printf( "(gap: %d)\n", ci->start-ci->prev->end);
272 void C_SafeAddRange(binangle startAngle, binangle endAngle)
274 binangle angLen = endAngle-startAngle;
276 //printf( "Adding range %x => %x...\n", startAngle, endAngle);
278 // Check if the range is valid.
279 if(!angLen || angLen > BANG_180) return;
281 // The range may still wrap around.
282 if((int)startAngle+(int)angLen > BANG_MAX)
284 // printf( " adding in two parts\n");
285 // The range has to added in two parts.
286 C_AddRange(startAngle, BANG_MAX);
288 C_AddRange(0, endAngle);
293 // printf( " adding normally\n");
294 // Add the range as usual.
295 C_AddRange(startAngle, endAngle);
298 //C_CountNodes(); // Just development info.
302 // Add a segment relative to the current viewpoint.
303 void C_AddViewRelSeg(float x1, float y1, float x2, float y2)
305 float dx1 = x1-vx, dy1 = y1-vz, dx2 = x2-vx, dy2 = y2-vz;
306 // __int64 pstart, pend;
308 // QueryPerformanceCounter((LARGE_INTEGER*)&pstart);
309 //PC_Start(&clipperclock);
311 C_SafeAddRange(bamsAtan2((int)(dy2*10), (int)(dx2*10)),
312 bamsAtan2((int)(dy1*10), (int)(dx1*10)));
314 //QueryPerformanceCounter((LARGE_INTEGER*)&pend);
315 //clippercount += pend-pstart;
316 //PC_Stop(&clipperclock);
319 // The specified range must be safe!
320 static int C_IsRangeVisible(binangle startAngle, binangle endAngle)
324 for(ci=cliphead; ci; ci=ci->next)
325 if(startAngle >= ci->start && endAngle <= ci->end)
327 // No node fully contained the specified range.
331 // Returns 1 if the range is not entirely clipped.
332 static int C_SafeCheckRange(binangle startAngle, binangle endAngle)
334 binangle angLen = endAngle - startAngle;
336 // Check that the range is valid.
337 if(!angLen || angLen >= BANG_180) return 0;
338 if((int)startAngle+(int)angLen > BANG_MAX)
340 // The range wraps around.
341 return (C_IsRangeVisible(startAngle, BANG_MAX)
342 || C_IsRangeVisible(0, endAngle));
344 return C_IsRangeVisible(startAngle, endAngle);
347 int C_CheckViewRelSeg(float x1, float y1, float x2, float y2)
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)));
354 // Returns 1 if the specified angle is visible.
355 int C_IsAngleVisible(binangle bang)
359 for(ci=cliphead; ci; ci=ci->next)
360 if(bang > ci->start && bang < ci->end) return 0;
361 // No one clipped this angle.
365 clipnode_t *C_AngleClippedBy(binangle bang)
369 for(ci=cliphead; ci; ci=ci->next)
370 if(bang > ci->start && bang < ci->end) return ci;
371 // No one clipped this angle.
375 // Returns 1 if the subsector might be visible.
376 int C_CheckSubsector(subsector_t *ssec)
379 // clipnode_t *cnode=0;
380 binangle *anglist = _alloca(sizeof(binangle)*ssec->numedgeverts);
382 // extern perfclock_t miscclock;
384 //PC_Start(&miscclock);
385 for(i=0; i<ssec->numedgeverts; i++) // Check all corners.
387 fvertex_t *vtx = ssec->edgeverts+i;
388 /* clipnode_t *clipper = C_AngleClippedBy(bamsAtan2((int)((vtx->y - vz)*10),
389 (int)((vtx->x - vx)*10)));
390 // If no one clipped the angle, there is a visible portion.
391 if(!clipper) return 1;
394 else if(cnode != clipper)
397 anglist[i] = bamsAtan2((int)((vtx->y - vz)*100), (int)((vtx->x - vx)*100));
400 minAngle = maxAngle = anglist[i];
403 if(anglist[i] < minAngle) minAngle = anglist[i];
404 if(anglist[i] > maxAngle) maxAngle = anglist[i];
407 //PC_Stop(&miscclock);
408 // Check each of the ranges defined by the edges.
409 for(i=0; i<ssec->numedgeverts-1; i++)
414 // The last edge won't be checked. This is because the edges
415 // define a closed, convex polygon and the last edge's range is
416 // always already covered by the previous edges. (Right?)
418 //if(end == ssec->numedgeverts) end = 0; // Back to beginning.
420 // If even one of the edges is not contained by a clipnode,
421 // the subsector is at least partially visible.
423 angLen = anglist[end] - anglist[i];
425 if(angLen == BANG_180) continue; // We can't check this.
427 // Choose the start and end points so that length is < 180.
428 if(angLen < BANG_180)
430 if(C_SafeCheckRange(anglist[i], anglist[end])) return 1;
434 if(C_SafeCheckRange(anglist[end], anglist[i])) return 1;
437 // All the edges were clipped totally away.
446 /*if(maxAngle-minAngle > BANG_180) // Does wraparound happen?
448 // First the angles must be sorted (min -> max).
449 qsort(anglist, ssec->numedgeverts, sizeof(binangle), AngleSorter);
450 // Let's find the section that's over 180 degrees.
451 // Check all but the last edge.
452 for(i=0; i<ssec->numedgeverts-1; i++)
455 if(anglist[end]-anglist[i] > BANG_180)
457 // This is the long edge.
458 return (!C_IsRangeContained(0, anglist[i]) &&
459 !C_IsRangeContained(anglist[end], BANG_MAX));
462 for(i=0; i<ssec->numedgeverts; i++)
463 printf( "anglist[%d] = %x\n", i, anglist[i]);
464 I_Error("C_CheckSubsector: (wraparound) Can't find long edge.\n");
465 return 0; // Keep the compiler happy.
469 // The range is OK, check it out.
470 return (!C_IsRangeContained(minAngle, maxAngle));
472 /*static int AngleSorter(const binangle *elem1, const binangle *elem2)
474 if(*elem1 > *elem2) return 1;
475 if(*elem1 < *elem2) return -1;