This graph shows which files directly or indirectly include this file:
Go to the source code of this file.
|
|
|
|
|
|
|
||||||||||||||||
|
Definition at line 650 of file cm_polylib.c. References AllocWinding(), Com_Memcpy(), CopyWinding(), CrossProduct(), d, DotProduct, FreeWinding(), i, j, k, memcpy(), winding_t::numpoints, winding_t::p, p, qboolean, vec3_t, VectorCopy, VectorNormalize(), VectorNormalize2(), VectorSubtract, and w. Referenced by ClipSideIntoTree_r(). 00650 {
00651 int i, j, k;
00652 float *p, *copy;
00653 vec3_t dir;
00654 float d;
00655 int numHullPoints, numNew;
00656 vec3_t hullPoints[MAX_HULL_POINTS];
00657 vec3_t newHullPoints[MAX_HULL_POINTS];
00658 vec3_t hullDirs[MAX_HULL_POINTS];
00659 qboolean hullSide[MAX_HULL_POINTS];
00660 qboolean outside;
00661
00662 if ( !*hull ) {
00663 *hull = CopyWinding( w );
00664 return;
00665 }
00666
00667 numHullPoints = (*hull)->numpoints;
00668 Com_Memcpy( hullPoints, (*hull)->p, numHullPoints * sizeof(vec3_t) );
00669
00670 for ( i = 0 ; i < w->numpoints ; i++ ) {
00671 p = w->p[i];
00672
00673 // calculate hull side vectors
00674 for ( j = 0 ; j < numHullPoints ; j++ ) {
00675 k = ( j + 1 ) % numHullPoints;
00676
00677 VectorSubtract( hullPoints[k], hullPoints[j], dir );
00678 VectorNormalize2( dir, dir );
00679 CrossProduct( normal, dir, hullDirs[j] );
00680 }
00681
00682 outside = qfalse;
00683 for ( j = 0 ; j < numHullPoints ; j++ ) {
00684 VectorSubtract( p, hullPoints[j], dir );
00685 d = DotProduct( dir, hullDirs[j] );
00686 if ( d >= ON_EPSILON ) {
00687 outside = qtrue;
00688 }
00689 if ( d >= -ON_EPSILON ) {
00690 hullSide[j] = qtrue;
00691 } else {
00692 hullSide[j] = qfalse;
00693 }
00694 }
00695
00696 // if the point is effectively inside, do nothing
00697 if ( !outside ) {
00698 continue;
00699 }
00700
00701 // find the back side to front side transition
00702 for ( j = 0 ; j < numHullPoints ; j++ ) {
00703 if ( !hullSide[ j % numHullPoints ] && hullSide[ (j + 1) % numHullPoints ] ) {
00704 break;
00705 }
00706 }
00707 if ( j == numHullPoints ) {
00708 continue;
00709 }
00710
00711 // insert the point here
00712 VectorCopy( p, newHullPoints[0] );
00713 numNew = 1;
00714
00715 // copy over all points that aren't double fronts
00716 j = (j+1)%numHullPoints;
00717 for ( k = 0 ; k < numHullPoints ; k++ ) {
00718 if ( hullSide[ (j+k) % numHullPoints ] && hullSide[ (j+k+1) % numHullPoints ] ) {
00719 continue;
00720 }
00721 copy = hullPoints[ (j+k+1) % numHullPoints ];
00722 VectorCopy( copy, newHullPoints[numNew] );
00723 numNew++;
00724 }
00725
00726 numHullPoints = numNew;
00727 Com_Memcpy( hullPoints, newHullPoints, numHullPoints * sizeof(vec3_t) );
00728 }
00729
00730 FreeWinding( *hull );
00731 w = AllocWinding( numHullPoints );
00732 w->numpoints = numHullPoints;
00733 *hull = w;
00734 Com_Memcpy( w->p, hullPoints, numHullPoints * sizeof(vec3_t) );
00735 }
|
Here is the call graph for this function:
|
|
Definition at line 69 of file l_poly.c. 00070 {
00071 winding_t *w;
00072 int s;
00073
00074 s = sizeof(vec_t)*3*points + sizeof(int);
00075 w = GetMemory(s);
00076 memset(w, 0, s);
00077
00078 if (numthreads == 1)
00079 {
00080 c_winding_allocs++;
00081 c_winding_points += points;
00082 c_active_windings++;
00083 if (c_active_windings > c_peak_windings)
00084 c_peak_windings = c_active_windings;
00085 c_windingmemory += MemorySize(w);
00086 if (c_windingmemory > c_peak_windingmemory)
00087 c_peak_windingmemory = c_windingmemory;
00088 } //end if
00089 return w;
00090 } //end of the function AllocWinding
|
|
||||||||||||
|
Definition at line 251 of file l_poly.c. 00252 {
00253 int i, x;
00254 vec_t max, v;
00255 vec3_t org, vright, vup;
00256 winding_t *w;
00257
00258 // find the major axis
00259
00260 max = -BOGUS_RANGE;
00261 x = -1;
00262 for (i=0 ; i<3; i++)
00263 {
00264 v = fabs(normal[i]);
00265 if (v > max)
00266 {
00267 x = i;
00268 max = v;
00269 }
00270 }
00271 if (x==-1)
00272 Error ("BaseWindingForPlane: no axis found");
00273
00274 VectorCopy (vec3_origin, vup);
00275 switch (x)
00276 {
00277 case 0:
00278 case 1:
00279 vup[2] = 1;
00280 break;
00281 case 2:
00282 vup[0] = 1;
00283 break;
00284 }
00285
00286 v = DotProduct (vup, normal);
00287 VectorMA (vup, -v, normal, vup);
00288 VectorNormalize (vup);
00289
00290 VectorScale (normal, dist, org);
00291
00292 CrossProduct (vup, normal, vright);
00293
00294 VectorScale (vup, BOGUS_RANGE, vup);
00295 VectorScale (vright, BOGUS_RANGE, vright);
00296
00297 // project a really big axis aligned box onto the plane
00298 w = AllocWinding (4);
00299
00300 VectorSubtract (org, vright, w->p[0]);
00301 VectorAdd (w->p[0], vup, w->p[0]);
00302
00303 VectorAdd (org, vright, w->p[1]);
00304 VectorAdd (w->p[1], vup, w->p[1]);
00305
00306 VectorAdd (org, vright, w->p[2]);
00307 VectorSubtract (w->p[2], vup, w->p[2]);
00308
00309 VectorSubtract (org, vright, w->p[3]);
00310 VectorSubtract (w->p[3], vup, w->p[3]);
00311
00312 w->numpoints = 4;
00313
00314 return w;
00315 }
|
|
|
Definition at line 595 of file l_poly.c. References BOGUS_RANGE, CrossProduct(), d, DotProduct, Error(), i, j, MAX_WORLD_COORD, winding_t::numpoints, ON_EPSILON, winding_t::p, p2, vec3_t, vec_t, VectorLength(), VectorNormalize(), VectorSubtract, w, WindingArea(), and WindingPlane(). 00596 {
00597 int i, j;
00598 vec_t *p1, *p2;
00599 vec_t d, edgedist;
00600 vec3_t dir, edgenormal, facenormal;
00601 vec_t area;
00602 vec_t facedist;
00603
00604 if (w->numpoints < 3)
00605 Error ("CheckWinding: %i points",w->numpoints);
00606
00607 area = WindingArea(w);
00608 if (area < 1)
00609 Error ("CheckWinding: %f area", area);
00610
00611 WindingPlane (w, facenormal, &facedist);
00612
00613 for (i=0 ; i<w->numpoints ; i++)
00614 {
00615 p1 = w->p[i];
00616
00617 for (j=0 ; j<3 ; j++)
00618 if (p1[j] > BOGUS_RANGE || p1[j] < -BOGUS_RANGE)
00619 Error ("CheckWinding: BUGUS_RANGE: %f",p1[j]);
00620
00621 j = i+1 == w->numpoints ? 0 : i+1;
00622
00623 // check the point is on the face plane
00624 d = DotProduct (p1, facenormal) - facedist;
00625 if (d < -ON_EPSILON || d > ON_EPSILON)
00626 Error ("CheckWinding: point off plane");
00627
00628 // check the edge isnt degenerate
00629 p2 = w->p[j];
00630 VectorSubtract (p2, p1, dir);
00631
00632 if (VectorLength (dir) < ON_EPSILON)
00633 Error ("CheckWinding: degenerate edge");
00634
00635 CrossProduct (facenormal, dir, edgenormal);
00636 VectorNormalize (edgenormal);
00637 edgedist = DotProduct (p1, edgenormal);
00638 edgedist += ON_EPSILON;
00639
00640 // all other points must be on front side
00641 for (j=0 ; j<w->numpoints ; j++)
00642 {
00643 if (j == i)
00644 continue;
00645 d = DotProduct (w->p[j], edgenormal);
00646 if (d > edgedist)
00647 Error ("CheckWinding: non-convex");
00648 }
00649 }
00650 }
|
Here is the call graph for this function:
|
||||||||||||||||
|
Definition at line 577 of file l_poly.c. References b, ClipWindingEpsilon(), f, FreeWinding(), in, and ON_EPSILON. 00578 {
00579 winding_t *f, *b;
00580
00581 ClipWindingEpsilon (in, normal, dist, ON_EPSILON, &f, &b);
00582 FreeWinding (in);
00583 if (b)
00584 FreeWinding (b);
00585 return f;
00586 }
|
Here is the call graph for this function:
|
||||||||||||||||||||
|
Definition at line 471 of file l_poly.c. References AllocWinding(), DotProduct, Error(), f, FreeWinding(), i, in, j, MAX_POINTS_ON_WINDING, winding_t::numpoints, winding_t::p, p2, SIDE_ON, vec3_t, vec_t, and VectorCopy. Referenced by AAS_CreateCurveBrushes(), AAS_FixMapBrush(), AAS_MakeBrushWindings(), AAS_SplitWinding(), BaseWindingForNode(), BSPBrushWindings(), CM_AddFacetBevels(), CM_DrawDebugSurface(), CM_ValidateFacet(), CreateBrushWindings(), HL_FaceOnWinding(), HL_SplitBrush(), MakeBrushWindings(), MakeHeadnodePortals(), MakeNodePortal(), Q1_FaceOnWinding(), Q1_SplitBrush(), Q2_BrushSideWinding(), Q2_FaceOnWinding(), Q3_BrushSideWinding(), Q3_FaceOnWinding(), Sin_BrushSideWinding(), Sin_FaceOnWinding(), and SplitBrush(). 00472 {
00473 winding_t *in;
00474 vec_t dists[MAX_POINTS_ON_WINDING+4];
00475 int sides[MAX_POINTS_ON_WINDING+4];
00476 int counts[3];
00477 //MrElusive: DOH can't use statics when unsing multithreading!!!
00478 vec_t dot; // VC 4.2 optimizer bug if not static
00479 int i, j;
00480 vec_t *p1, *p2;
00481 vec3_t mid;
00482 winding_t *f;
00483 int maxpts;
00484
00485 in = *inout;
00486 counts[0] = counts[1] = counts[2] = 0;
00487
00488 // determine sides for each point
00489 for (i=0 ; i<in->numpoints ; i++)
00490 {
00491 dot = DotProduct (in->p[i], normal);
00492 dot -= dist;
00493 dists[i] = dot;
00494 if (dot > epsilon)
00495 sides[i] = SIDE_FRONT;
00496 else if (dot < -epsilon)
00497 sides[i] = SIDE_BACK;
00498 else
00499 {
00500 sides[i] = SIDE_ON;
00501 }
00502 counts[sides[i]]++;
00503 }
00504 sides[i] = sides[0];
00505 dists[i] = dists[0];
00506
00507 if (!counts[0])
00508 {
00509 FreeWinding (in);
00510 *inout = NULL;
00511 return;
00512 }
00513 if (!counts[1])
00514 return; // inout stays the same
00515
00516 maxpts = in->numpoints+4; // cant use counts[0]+2 because
00517 // of fp grouping errors
00518
00519 f = AllocWinding (maxpts);
00520
00521 for (i=0 ; i<in->numpoints ; i++)
00522 {
00523 p1 = in->p[i];
00524
00525 if (sides[i] == SIDE_ON)
00526 {
00527 VectorCopy (p1, f->p[f->numpoints]);
00528 f->numpoints++;
00529 continue;
00530 }
00531
00532 if (sides[i] == SIDE_FRONT)
00533 {
00534 VectorCopy (p1, f->p[f->numpoints]);
00535 f->numpoints++;
00536 }
00537
00538 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
00539 continue;
00540
00541 // generate a split point
00542 p2 = in->p[(i+1)%in->numpoints];
00543
00544 dot = dists[i] / (dists[i]-dists[i+1]);
00545 for (j=0 ; j<3 ; j++)
00546 { // avoid round off error when possible
00547 if (normal[j] == 1)
00548 mid[j] = dist;
00549 else if (normal[j] == -1)
00550 mid[j] = -dist;
00551 else
00552 mid[j] = p1[j] + dot*(p2[j]-p1[j]);
00553 }
00554
00555 VectorCopy (mid, f->p[f->numpoints]);
00556 f->numpoints++;
00557 }
00558
00559 if (f->numpoints > maxpts)
00560 Error ("ClipWinding: points exceeded estimate");
00561 if (f->numpoints > MAX_POINTS_ON_WINDING)
00562 Error ("ClipWinding: MAX_POINTS_ON_WINDING");
00563
00564 FreeWinding (in);
00565 *inout = f;
00566 }
|
Here is the call graph for this function:
|
||||||||||||||||||||||||||||
|
Definition at line 358 of file l_poly.c. 00360 {
00361 vec_t dists[MAX_POINTS_ON_WINDING+4];
00362 int sides[MAX_POINTS_ON_WINDING+4];
00363 int counts[3];
00364 //MrElusive: DOH can't use statics when unsing multithreading!!!
00365 vec_t dot; // VC 4.2 optimizer bug if not static
00366 int i, j;
00367 vec_t *p1, *p2;
00368 vec3_t mid;
00369 winding_t *f, *b;
00370 int maxpts;
00371
00372 counts[0] = counts[1] = counts[2] = 0;
00373
00374 // determine sides for each point
00375 for (i=0 ; i<in->numpoints ; i++)
00376 {
00377 dot = DotProduct (in->p[i], normal);
00378 dot -= dist;
00379 dists[i] = dot;
00380 if (dot > epsilon)
00381 sides[i] = SIDE_FRONT;
00382 else if (dot < -epsilon)
00383 sides[i] = SIDE_BACK;
00384 else
00385 {
00386 sides[i] = SIDE_ON;
00387 }
00388 counts[sides[i]]++;
00389 }
00390 sides[i] = sides[0];
00391 dists[i] = dists[0];
00392
00393 *front = *back = NULL;
00394
00395 if (!counts[0])
00396 {
00397 *back = CopyWinding (in);
00398 return;
00399 }
00400 if (!counts[1])
00401 {
00402 *front = CopyWinding (in);
00403 return;
00404 }
00405
00406 maxpts = in->numpoints+4; // cant use counts[0]+2 because
00407 // of fp grouping errors
00408
00409 *front = f = AllocWinding (maxpts);
00410 *back = b = AllocWinding (maxpts);
00411
00412 for (i=0 ; i<in->numpoints ; i++)
00413 {
00414 p1 = in->p[i];
00415
00416 if (sides[i] == SIDE_ON)
00417 {
00418 VectorCopy (p1, f->p[f->numpoints]);
00419 f->numpoints++;
00420 VectorCopy (p1, b->p[b->numpoints]);
00421 b->numpoints++;
00422 continue;
00423 }
00424
00425 if (sides[i] == SIDE_FRONT)
00426 {
00427 VectorCopy (p1, f->p[f->numpoints]);
00428 f->numpoints++;
00429 }
00430 if (sides[i] == SIDE_BACK)
00431 {
00432 VectorCopy (p1, b->p[b->numpoints]);
00433 b->numpoints++;
00434 }
00435
00436 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
00437 continue;
00438
00439 // generate a split point
00440 p2 = in->p[(i+1)%in->numpoints];
00441
00442 dot = dists[i] / (dists[i]-dists[i+1]);
00443 for (j=0 ; j<3 ; j++)
00444 { // avoid round off error when possible
00445 if (normal[j] == 1)
00446 mid[j] = dist;
00447 else if (normal[j] == -1)
00448 mid[j] = -dist;
00449 else
00450 mid[j] = p1[j] + dot*(p2[j]-p1[j]);
00451 }
00452
00453 VectorCopy (mid, f->p[f->numpoints]);
00454 f->numpoints++;
00455 VectorCopy (mid, b->p[b->numpoints]);
00456 b->numpoints++;
00457 }
00458
00459 if (f->numpoints > maxpts || b->numpoints > maxpts)
00460 Error ("ClipWinding: points exceeded estimate");
00461 if (f->numpoints > MAX_POINTS_ON_WINDING || b->numpoints > MAX_POINTS_ON_WINDING)
00462 Error ("ClipWinding: MAX_POINTS_ON_WINDING");
00463 }
|
|
|
Definition at line 322 of file l_poly.c. 00323 {
00324 int size;
00325 winding_t *c;
00326
00327 c = AllocWinding (w->numpoints);
00328 size = (int)((winding_t *)0)->p[w->numpoints];
00329 memcpy (c, w, size);
00330 return c;
00331 }
|
|
|
Definition at line 92 of file l_poly.c. 00093 {
00094 if (*(unsigned *)w == 0xdeaddead)
00095 Error ("FreeWinding: freed a freed winding");
00096
00097 if (numthreads == 1)
00098 {
00099 c_active_windings--;
00100 c_windingmemory -= MemorySize(w);
00101 } //end if
00102
00103 *(unsigned *)w = 0xdeaddead;
00104
00105 FreeMemory(w);
00106 } //end of the function FreeWinding
|
|
|
Definition at line 45 of file l_poly.c. References i, winding_t::numpoints, winding_t::p, printf(), and w. Referenced by PrintBrush(). 00046 {
00047 int i;
00048 for (i=0 ; i<w->numpoints ; i++)
00049 printf ("(%5.3f, %5.3f, %5.3f)\n",w->p[i][0], w->p[i][1],w->p[i][2]);
00050 }
|
Here is the call graph for this function:
|
|
Definition at line 129 of file l_poly.c. References c_removed, DotProduct, Error(), i, j, k, memcpy(), winding_t::numpoints, numthreads, winding_t::p, p, v1, v2, vec3_t, VectorCopy, VectorNormalize(), VectorSubtract, and w. Referenced by AAS_RemoveAreaFaceColinearPoints(), and MergeWindings(). 00130 {
00131 int i, j, k;
00132 vec3_t v1, v2;
00133 int nump;
00134 vec3_t p[MAX_POINTS_ON_WINDING];
00135
00136 nump = 0;
00137 for (i=0 ; i<w->numpoints ; i++)
00138 {
00139 j = (i+1)%w->numpoints;
00140 k = (i+w->numpoints-1)%w->numpoints;
00141 VectorSubtract (w->p[j], w->p[i], v1);
00142 VectorSubtract (w->p[i], w->p[k], v2);
00143 VectorNormalize(v1);
00144 VectorNormalize(v2);
00145 if (DotProduct(v1, v2) < 0.999)
00146 {
00147 if (nump >= MAX_POINTS_ON_WINDING)
00148 Error("RemoveColinearPoints: MAX_POINTS_ON_WINDING");
00149 VectorCopy (w->p[i], p[nump]);
00150 nump++;
00151 }
00152 }
00153
00154 if (nump == w->numpoints)
00155 return;
00156
00157 if (numthreads == 1)
00158 c_removed += w->numpoints - nump;
00159 w->numpoints = nump;
00160 memcpy (w->p, p, nump*sizeof(p[0]));
00161 }
|
Here is the call graph for this function:
|
|
Definition at line 338 of file l_poly.c. 00339 {
00340 int i;
00341 winding_t *c;
00342
00343 c = AllocWinding (w->numpoints);
00344 for (i=0 ; i<w->numpoints ; i++)
00345 {
00346 VectorCopy (w->p[w->numpoints-1-i], c->p[i]);
00347 }
00348 c->numpoints = w->numpoints;
00349 return c;
00350 }
|
|
|
Definition at line 190 of file l_poly.c. 00191 {
00192 int i;
00193 vec3_t d1, d2, cross;
00194 vec_t total;
00195
00196 total = 0;
00197 for (i=2 ; i<w->numpoints ; i++)
00198 {
00199 VectorSubtract (w->p[i-1], w->p[0], d1);
00200 VectorSubtract (w->p[i], w->p[0], d2);
00201 CrossProduct (d1, d2, cross);
00202 total += 0.5 * VectorLength ( cross );
00203 }
00204 return total;
00205 }
|
|
||||||||||||||||
|
Definition at line 207 of file l_poly.c. 00208 {
00209 vec_t v;
00210 int i,j;
00211
00212 mins[0] = mins[1] = mins[2] = 99999;
00213 maxs[0] = maxs[1] = maxs[2] = -99999;
00214
00215 for (i=0 ; i<w->numpoints ; i++)
00216 {
00217 for (j=0 ; j<3 ; j++)
00218 {
00219 v = w->p[i][j];
00220 if (v < mins[j])
00221 mins[j] = v;
00222 if (v > maxs[j])
00223 maxs[j] = v;
00224 }
00225 }
00226 }
|
|
||||||||||||
|
Definition at line 233 of file l_poly.c. 00234 {
00235 int i;
00236 float scale;
00237
00238 VectorCopy (vec3_origin, center);
00239 for (i=0 ; i<w->numpoints ; i++)
00240 VectorAdd (w->p[i], center, center);
00241
00242 scale = 1.0/w->numpoints;
00243 VectorScale (center, scale, center);
00244 }
|
|
||||||||||||||||
|
Definition at line 658 of file l_poly.c. References d, DotProduct, i, winding_t::numpoints, winding_t::p, qboolean, vec_t, and w. Referenced by BuildFaceTree_r(), and SelectSplitPlaneNum(). 00659 {
00660 qboolean front, back;
00661 int i;
00662 vec_t d;
00663
00664 front = false;
00665 back = false;
00666 for (i=0 ; i<w->numpoints ; i++)
00667 {
00668 d = DotProduct (w->p[i], normal) - dist;
00669 if (d < -ON_EPSILON)
00670 {
00671 if (front)
00672 return SIDE_CROSS;
00673 back = true;
00674 continue;
00675 }
00676 if (d > ON_EPSILON)
00677 {
00678 if (back)
00679 return SIDE_CROSS;
00680 front = true;
00681 continue;
00682 }
00683 }
00684
00685 if (back)
00686 return SIDE_BACK;
00687 if (front)
00688 return SIDE_FRONT;
00689 return SIDE_ON;
00690 }
|
|
||||||||||||||||
|
Definition at line 168 of file l_poly.c. References CrossProduct(), DotProduct, i, winding_t::numpoints, winding_t::p, v1, v2, vec3_t, VectorLength(), VectorNormalize(), VectorSubtract, and w. Referenced by AAS_CheckArea(), AAS_CheckFaceWindingPlane(), AAS_FlipAreaFaces(), CheckWinding(), WindingError(), and WritePortalFile_r(). 00169 {
00170 vec3_t v1, v2;
00171 int i;
00172
00173 //find two vectors each longer than 0.5 units
00174 for (i = 0; i < w->numpoints; i++)
00175 {
00176 VectorSubtract(w->p[(i+1) % w->numpoints], w->p[i], v1);
00177 VectorSubtract(w->p[(i+2) % w->numpoints], w->p[i], v2);
00178 if (VectorLength(v1) > 0.5 && VectorLength(v2) > 0.5) break;
00179 } //end for
00180 CrossProduct(v2, v1, normal);
00181 VectorNormalize(normal);
00182 *dist = DotProduct(w->p[0], normal);
00183 } //end of the function WindingPlane
|
Here is the call graph for this function:
1.3.9.1