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