#include <malloc.h>
#include "l_cmd.h"
#include "l_math.h"
#include "l_poly.h"
#include "l_log.h"
#include "l_mem.h"
Include dependency graph for l_poly.c:
Go to the source code of this file.
|
|
Definition at line 30 of file l_poly.c. Referenced by BaseWindingForPlane(), CheckWinding(), Winding_BaseForPlane(), Winding_IsHuge(), WindingError(), and WindingIsHuge(). |
|
|
|
|
|
Definition at line 1080 of file l_poly.c. Referenced by PointOnWinding(). |
|
|
|
|
|
Definition at line 118 of file l_poly.c. 00119 {
00120 return c_active_windings;
00121 } //end of the function ActiveWindings
|
|
||||||||||||||||
|
Definition at line 1043 of file l_poly.c. References AllocWinding(), Error(), i, j, winding_t::numpoints, winding_t::p, point, VectorCopy, and w. Referenced by AAS_MeltFaceWinding(). 01044 {
01045 int i, j;
01046 winding_t *neww;
01047
01048 if (spot > w->numpoints)
01049 {
01050 Error("AddWindingPoint: num > w->numpoints");
01051 } //end if
01052 if (spot < 0)
01053 {
01054 Error("AddWindingPoint: num < 0");
01055 } //end if
01056 neww = AllocWinding(w->numpoints + 1);
01057 neww->numpoints = w->numpoints + 1;
01058 for (i = 0, j = 0; i < neww->numpoints; i++)
01059 {
01060 if (i == spot)
01061 {
01062 VectorCopy(point, neww->p[i]);
01063 } //end if
01064 else
01065 {
01066 VectorCopy(w->p[j], neww->p[i]);
01067 j++;
01068 } //end else
01069 } //end for
01070 return neww;
01071 } //end of the function AddWindingPoint
|
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. 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 }
|
|
||||||||||||||||
|
Definition at line 577 of file l_poly.c. 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 }
|
|
||||||||||||||||||||
|
Definition at line 471 of file l_poly.c. 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 }
|
|
||||||||||||||||||||||||||||
|
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 1130 of file l_poly.c. References CrossProduct(), DotProduct, i, i2, j, j2, Log_Write(), n, winding_t::numpoints, winding_t::p, v1, v2, vec3_t, VectorCopy, VectorLength(), VectorNegate, VectorNormalize(), and VectorSubtract. Referenced by AAS_FindBestAreaSplitPlane(). 01132 {
01133 int i, i2, j, j2, n;
01134 int sides1[3], sides2[3];
01135 float dist1, dist2, dot, diff;
01136 vec3_t normal1, normal2;
01137 vec3_t v1, v2;
01138
01139 for (i = 0; i < w1->numpoints; i++)
01140 {
01141 i2 = (i+1) % w1->numpoints;
01142 //
01143 VectorSubtract(w1->p[i2], w1->p[i], v1);
01144 if (VectorLength(v1) < 0.1)
01145 {
01146 //Log_Write("FindPlaneSeperatingWindings: winding1 with degenerate edge\r\n");
01147 continue;
01148 } //end if
01149 CrossProduct(v1, dir, normal1);
01150 VectorNormalize(normal1);
01151 dist1 = DotProduct(normal1, w1->p[i]);
01152 //
01153 for (j = 0; j < w2->numpoints; j++)
01154 {
01155 j2 = (j+1) % w2->numpoints;
01156 //
01157 VectorSubtract(w2->p[j2], w2->p[j], v2);
01158 if (VectorLength(v2) < 0.1)
01159 {
01160 //Log_Write("FindPlaneSeperatingWindings: winding2 with degenerate edge\r\n");
01161 continue;
01162 } //end if
01163 CrossProduct(v2, dir, normal2);
01164 VectorNormalize(normal2);
01165 dist2 = DotProduct(normal2, w2->p[j]);
01166 //
01167 diff = dist1 - dist2;
01168 if (diff < -0.1 || diff > 0.1)
01169 {
01170 dist2 = -dist2;
01171 VectorNegate(normal2, normal2);
01172 diff = dist1 - dist2;
01173 if (diff < -0.1 || diff > 0.1) continue;
01174 } //end if
01175 //check if the normal vectors are equal
01176 for (n = 0; n < 3; n++)
01177 {
01178 diff = normal1[n] - normal2[n];
01179 if (diff < -0.0001 || diff > 0.0001) break;
01180 } //end for
01181 if (n != 3) continue;
01182 //check on which side of the seperating plane the points of
01183 //the first winding are
01184 sides1[0] = sides1[1] = sides1[2] = 0;
01185 for (n = 0; n < w1->numpoints; n++)
01186 {
01187 dot = DotProduct(w1->p[n], normal1) - dist1;
01188 if (dot > 0.1) sides1[0]++;
01189 else if (dot < -0.1) sides1[1]++;
01190 else sides1[2]++;
01191 } //end for
01192 //check on which side of the seperating plane the points of
01193 //the second winding are
01194 sides2[0] = sides2[1] = sides2[2] = 0;
01195 for (n = 0; n < w2->numpoints; n++)
01196 {
01197 //used normal1 and dist1 (they are equal to normal2 and dist2)
01198 dot = DotProduct(w2->p[n], normal1) - dist1;
01199 if (dot > 0.1) sides2[0]++;
01200 else if (dot < -0.1) sides2[1]++;
01201 else sides2[2]++;
01202 } //end for
01203 //if the first winding has points at both sides
01204 if (sides1[0] && sides1[1])
01205 {
01206 Log_Write("FindPlaneSeperatingWindings: winding1 non-convex\r\n");
01207 continue;
01208 } //end if
01209 //if the second winding has points at both sides
01210 if (sides2[0] && sides2[1])
01211 {
01212 Log_Write("FindPlaneSeperatingWindings: winding2 non-convex\r\n");
01213 continue;
01214 } //end if
01215 //
01216 if ((!sides1[0] && !sides1[1]) || (!sides2[0] && !sides2[1]))
01217 {
01218 //don't use one of the winding planes as the seperating plane
01219 continue;
01220 } //end if
01221 //the windings must be at different sides of the seperating plane
01222 if ((!sides1[0] && !sides2[1]) || (!sides1[1] && !sides2[0]))
01223 {
01224 VectorCopy(normal1, normal);
01225 *dist = dist1;
01226 return true;
01227 } //end if
01228 } //end for
01229 } //end for
01230 return false;
01231 } //end of the function FindPlaneSeperatingWindings
|
Here is the call graph for this function:
|
|
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 813 of file l_poly.c. References AllocWinding(), CrossProduct(), DotProduct, i, j, Log_Print(), MAX_POINTS_ON_WINDING, memcpy(), n, winding_t::numpoints, winding_t::p, RemoveColinearPoints(), RemoveEqualPoints(), SIDE_BACK, SIDE_FRONT, v, vec3_t, VectorCopy, VectorLength(), VectorNormalize(), and VectorSubtract. Referenced by AAS_MergePlaneFaces(), and AAS_TryMergeFaces(). 00814 {
00815 winding_t *neww;
00816 float dist;
00817 int i, j, n, found, insertafter;
00818 int sides[MAX_POINTS_ON_WINDING+4];
00819 vec3_t newp[MAX_POINTS_ON_WINDING+4];
00820 int numpoints;
00821 vec3_t edgevec, sepnormal, v;
00822
00823 RemoveEqualPoints(w1, 0.2);
00824 numpoints = w1->numpoints;
00825 memcpy(newp, w1->p, w1->numpoints * sizeof(vec3_t));
00826 //
00827 for (i = 0; i < w2->numpoints; i++)
00828 {
00829 VectorCopy(w2->p[i], v);
00830 for (j = 0; j < numpoints; j++)
00831 {
00832 VectorSubtract(newp[(j+1)%numpoints],
00833 newp[(j)%numpoints], edgevec);
00834 CrossProduct(edgevec, planenormal, sepnormal);
00835 VectorNormalize(sepnormal);
00836 if (VectorLength(sepnormal) < 0.9)
00837 {
00838 //remove the point from the new winding
00839 for (n = j; n < numpoints-1; n++)
00840 {
00841 VectorCopy(newp[n+1], newp[n]);
00842 sides[n] = sides[n+1];
00843 } //end for
00844 numpoints--;
00845 j--;
00846 Log_Print("MergeWindings: degenerate edge on winding %f %f %f\n", sepnormal[0],
00847 sepnormal[1],
00848 sepnormal[2]);
00849 continue;
00850 } //end if
00851 dist = DotProduct(newp[(j)%numpoints], sepnormal);
00852 if (DotProduct(v, sepnormal) - dist < -0.1) sides[j] = SIDE_BACK;
00853 else sides[j] = SIDE_FRONT;
00854 } //end for
00855 //remove all unnecesary points
00856 for (j = 0; j < numpoints;)
00857 {
00858 if (sides[j] == SIDE_BACK
00859 && sides[(j+1)%numpoints] == SIDE_BACK)
00860 {
00861 //remove the point from the new winding
00862 for (n = (j+1)%numpoints; n < numpoints-1; n++)
00863 {
00864 VectorCopy(newp[n+1], newp[n]);
00865 sides[n] = sides[n+1];
00866 } //end for
00867 numpoints--;
00868 } //end if
00869 else
00870 {
00871 j++;
00872 } //end else
00873 } //end for
00874 //
00875 found = false;
00876 for (j = 0; j < numpoints; j++)
00877 {
00878 if (sides[j] == SIDE_FRONT
00879 && sides[(j+1)%numpoints] == SIDE_BACK)
00880 {
00881 if (found) Log_Print("Warning: MergeWindings: front to back found twice\n");
00882 found = true;
00883 } //end if
00884 } //end for
00885 //
00886 for (j = 0; j < numpoints; j++)
00887 {
00888 if (sides[j] == SIDE_FRONT
00889 && sides[(j+1)%numpoints] == SIDE_BACK)
00890 {
00891 insertafter = (j+1)%numpoints;
00892 //insert the new point after j+1
00893 for (n = numpoints-1; n > insertafter; n--)
00894 {
00895 VectorCopy(newp[n], newp[n+1]);
00896 } //end for
00897 numpoints++;
00898 VectorCopy(v, newp[(insertafter+1)%numpoints]);
00899 break;
00900 } //end if
00901 } //end for
00902 } //end for
00903 neww = AllocWinding(numpoints);
00904 neww->numpoints = numpoints;
00905 memcpy(neww->p, newp, numpoints * sizeof(vec3_t));
00906 RemoveColinearPoints(neww);
00907 return neww;
00908 } //end of the function MergeWindings
|
Here is the call graph for this function:
|
||||||||||||||||||||||||
|
Definition at line 1082 of file l_poly.c. References CrossProduct(), DotProduct, i, j, MELT_ON_EPSILON, winding_t::numpoints, winding_t::p, point, v1, v2, vec3_t, VectorNormalize(), VectorSubtract, and w. Referenced by AAS_MeltFaceWinding(). 01083 {
01084 int i, j;
01085 vec3_t v1, v2;
01086 vec3_t edgenormal, edgevec;
01087 float edgedist, dot;
01088
01089 *spot = 0;
01090 //the point must be on the winding plane
01091 dot = DotProduct(point, normal) - dist;
01092 if (dot < -MELT_ON_EPSILON || dot > MELT_ON_EPSILON) return false;
01093 //
01094 for (i = 0; i < w->numpoints; i++)
01095 {
01096 j = (i+1) % w->numpoints;
01097 //get a plane orthogonal to the winding plane through the edge
01098 VectorSubtract(w->p[j], w->p[i], edgevec);
01099 CrossProduct(normal, edgevec, edgenormal);
01100 VectorNormalize(edgenormal);
01101 edgedist = DotProduct(edgenormal, w->p[i]);
01102 //point must be not too far from the plane
01103 dot = DotProduct(point, edgenormal) - edgedist;
01104 if (dot < -MELT_ON_EPSILON || dot > MELT_ON_EPSILON) continue;
01105 //vector from first point of winding to the point to test
01106 VectorSubtract(point, w->p[i], v1);
01107 //vector from second point of winding to the point to test
01108 VectorSubtract(point, w->p[j], v2);
01109 //if the length of the vector is not larger than 0.5 units then
01110 //the point is assumend to be the same as one of the winding points
01111 if (VectorNormalize(v1) < 0.5) return false;
01112 if (VectorNormalize(v2) < 0.5) return false;
01113 //point must be between the two winding points
01114 //(the two vectors must be directed towards each other, and on the
01115 //same straight line)
01116 if (DotProduct(v1, v2) < -0.99)
01117 {
01118 *spot = i + 1;
01119 return true;
01120 } //end if
01121 } //end for
01122 return false;
01123 } //end of the function PointOnWinding
|
Here is the call graph for this function:
|
|
Definition at line 45 of file l_poly.c. 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 }
|
|
|
Definition at line 129 of file l_poly.c. 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 }
|
|
||||||||||||
|
Definition at line 1008 of file l_poly.c. References Error(), i, memcpy(), winding_t::numpoints, p, winding_t::p, v, vec3_t, VectorCopy, VectorLength(), VectorSubtract, and w. Referenced by MergeWindings(). 01009 {
01010 int i, nump;
01011 vec3_t v;
01012 vec3_t p[MAX_POINTS_ON_WINDING];
01013
01014 VectorCopy(w->p[0], p[0]);
01015 nump = 1;
01016 for (i = 1; i < w->numpoints; i++)
01017 {
01018 VectorSubtract(w->p[i], p[nump-1], v);
01019 if (VectorLength(v) > epsilon)
01020 {
01021 if (nump >= MAX_POINTS_ON_WINDING)
01022 Error("RemoveColinearPoints: MAX_POINTS_ON_WINDING");
01023 VectorCopy (w->p[i], p[nump]);
01024 nump++;
01025 } //end if
01026 } //end for
01027
01028 if (nump == w->numpoints)
01029 return;
01030
01031 w->numpoints = nump;
01032 memcpy(w->p, p, nump * sizeof(p[0]));
01033 } //end of the function RemoveEqualPoints
|
Here is the call graph for this function:
|
|
Definition at line 53 of file l_poly.c. References c_active_windings, c_peak_windingmemory, c_peak_windings, c_winding_allocs, c_winding_points, c_windingmemory, strcpy(), and windingerror. 00054 {
00055 c_active_windings = 0;
00056 c_peak_windings = 0;
00057 c_winding_allocs = 0;
00058 c_winding_points = 0;
00059 c_windingmemory = 0;
00060 c_peak_windingmemory = 0;
00061
00062 strcpy(windingerror, "");
00063 } //end of the function ResetWindings
|
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 710 of file l_poly.c. 00711 {
00712 vec_t *p1, *p2, *p3, *p4, *back;
00713 winding_t *newf;
00714 int i, j, k, l;
00715 vec3_t normal, delta;
00716 vec_t dot;
00717 qboolean keep1, keep2;
00718
00719
00720 //
00721 // find a common edge
00722 //
00723 p1 = p2 = NULL; // stop compiler warning
00724 j = 0; //
00725
00726 for (i = 0; i < f1->numpoints; i++)
00727 {
00728 p1 = f1->p[i];
00729 p2 = f1->p[(i+1) % f1->numpoints];
00730 for (j = 0; j < f2->numpoints; j++)
00731 {
00732 p3 = f2->p[j];
00733 p4 = f2->p[(j+1) % f2->numpoints];
00734 for (k = 0; k < 3; k++)
00735 {
00736 if (fabs(p1[k] - p4[k]) > 0.1)//EQUAL_EPSILON) //ME
00737 break;
00738 if (fabs(p2[k] - p3[k]) > 0.1)//EQUAL_EPSILON) //ME
00739 break;
00740 } //end for
00741 if (k==3)
00742 break;
00743 } //end for
00744 if (j < f2->numpoints)
00745 break;
00746 } //end for
00747
00748 if (i == f1->numpoints)
00749 return NULL; // no matching edges
00750
00751 //
00752 // check slope of connected lines
00753 // if the slopes are colinear, the point can be removed
00754 //
00755 back = f1->p[(i+f1->numpoints-1)%f1->numpoints];
00756 VectorSubtract (p1, back, delta);
00757 CrossProduct (planenormal, delta, normal);
00758 VectorNormalize (normal);
00759
00760 back = f2->p[(j+2)%f2->numpoints];
00761 VectorSubtract (back, p1, delta);
00762 dot = DotProduct (delta, normal);
00763 if (dot > CONTINUOUS_EPSILON)
00764 return NULL; // not a convex polygon
00765 keep1 = (qboolean)(dot < -CONTINUOUS_EPSILON);
00766
00767 back = f1->p[(i+2)%f1->numpoints];
00768 VectorSubtract (back, p2, delta);
00769 CrossProduct (planenormal, delta, normal);
00770 VectorNormalize (normal);
00771
00772 back = f2->p[(j+f2->numpoints-1)%f2->numpoints];
00773 VectorSubtract (back, p2, delta);
00774 dot = DotProduct (delta, normal);
00775 if (dot > CONTINUOUS_EPSILON)
00776 return NULL; // not a convex polygon
00777 keep2 = (qboolean)(dot < -CONTINUOUS_EPSILON);
00778
00779 //
00780 // build the new polygon
00781 //
00782 newf = AllocWinding (f1->numpoints + f2->numpoints);
00783
00784 // copy first polygon
00785 for (k=(i+1)%f1->numpoints ; k != i ; k=(k+1)%f1->numpoints)
00786 {
00787 if (k==(i+1)%f1->numpoints && !keep2)
00788 continue;
00789
00790 VectorCopy (f1->p[k], newf->p[newf->numpoints]);
00791 newf->numpoints++;
00792 }
00793
00794 // copy second polygon
00795 for (l= (j+1)%f2->numpoints ; l != j ; l=(l+1)%f2->numpoints)
00796 {
00797 if (l==(j+1)%f2->numpoints && !keep1)
00798 continue;
00799 VectorCopy (f2->p[l], newf->p[newf->numpoints]);
00800 newf->numpoints++;
00801 }
00802
00803 return newf;
00804 }
|
|
|
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 925 of file l_poly.c. References BOGUS_RANGE, CrossProduct(), d, DotProduct, i, j, winding_t::numpoints, ON_EPSILON, winding_t::p, p2, sprintf(), vec3_t, vec_t, VectorLength(), VectorNormalize(), VectorSubtract, w, WindingArea(), windingerror, and WindingPlane(). Referenced by AAS_CheckArea(), MarkBrushBevels(), Q2_FixTextureReferences(), Q3_FindVisibleBrushSides(), and Sin_FixTextureReferences(). 00926 {
00927 int i, j;
00928 vec_t *p1, *p2;
00929 vec_t d, edgedist;
00930 vec3_t dir, edgenormal, facenormal;
00931 vec_t area;
00932 vec_t facedist;
00933
00934 if (w->numpoints < 3)
00935 {
00936 sprintf(windingerror, "winding %i points", w->numpoints);
00937 return WE_NOTENOUGHPOINTS;
00938 } //end if
00939
00940 area = WindingArea(w);
00941 if (area < 1)
00942 {
00943 sprintf(windingerror, "winding %f area", area);
00944 return WE_SMALLAREA;
00945 } //end if
00946
00947 WindingPlane (w, facenormal, &facedist);
00948
00949 for (i=0 ; i<w->numpoints ; i++)
00950 {
00951 p1 = w->p[i];
00952
00953 for (j=0 ; j<3 ; j++)
00954 {
00955 if (p1[j] > BOGUS_RANGE || p1[j] < -BOGUS_RANGE)
00956 {
00957 sprintf(windingerror, "winding point %d BUGUS_RANGE \'%f %f %f\'", j, p1[0], p1[1], p1[2]);
00958 return WE_POINTBOGUSRANGE;
00959 } //end if
00960 } //end for
00961
00962 j = i+1 == w->numpoints ? 0 : i+1;
00963
00964 // check the point is on the face plane
00965 d = DotProduct (p1, facenormal) - facedist;
00966 if (d < -ON_EPSILON || d > ON_EPSILON)
00967 {
00968 sprintf(windingerror, "winding point %d off plane", i);
00969 return WE_POINTOFFPLANE;
00970 } //end if
00971
00972 // check the edge isnt degenerate
00973 p2 = w->p[j];
00974 VectorSubtract (p2, p1, dir);
00975
00976 if (VectorLength (dir) < ON_EPSILON)
00977 {
00978 sprintf(windingerror, "winding degenerate edge %d-%d", i, j);
00979 return WE_DEGENERATEEDGE;
00980 } //end if
00981
00982 CrossProduct (facenormal, dir, edgenormal);
00983 VectorNormalize (edgenormal);
00984 edgedist = DotProduct (p1, edgenormal);
00985 edgedist += ON_EPSILON;
00986
00987 // all other points must be on front side
00988 for (j=0 ; j<w->numpoints ; j++)
00989 {
00990 if (j == i)
00991 continue;
00992 d = DotProduct (w->p[j], edgenormal);
00993 if (d > edgedist)
00994 {
00995 sprintf(windingerror, "winding non-convex");
00996 return WE_NONCONVEX;
00997 } //end if
00998 } //end for
00999 } //end for
01000 return WE_NONE;
01001 } //end of the function WindingError
|
Here is the call graph for this function:
|
|
Definition at line 915 of file l_poly.c. Referenced by AAS_CheckArea(), and MarkBrushBevels(). 00916 {
00917 return windingerror;
00918 } //end of the function WindingErrorString
|
|
|
Definition at line 108 of file l_poly.c. Referenced by BuildTree_r(), BuildTreeThread(), and MakeTreePortals(). 00109 {
00110 return c_windingmemory;
00111 } //end of the function WindingMemory
|
|
||||||||||||||||
|
Definition at line 658 of file l_poly.c. 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 113 of file l_poly.c. 00114 {
00115 return c_peak_windingmemory;
00116 } //end of the function WindingPeakMemory
|
|
||||||||||||||||
|
Definition at line 168 of file l_poly.c. 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
|
|
||||||||||||||||||||||||||||
|
Definition at line 1240 of file l_poly.c. References DotProduct, i, winding_t::numpoints, and winding_t::p. Referenced by AAS_FixMapBrush(), AAS_MakeBrushWindings(), CheckBSPBrush(), and TryMergeBrushes(). 01243 {
01244 int i;
01245
01246 if (!w1 || !w2) return false;
01247
01248 //check if one of the points of face1 is at the back of the plane of face2
01249 for (i = 0; i < w1->numpoints; i++)
01250 {
01251 if (DotProduct(normal2, w1->p[i]) - dist2 > WCONVEX_EPSILON) return true;
01252 } //end for
01253 //check if one of the points of face2 is at the back of the plane of face1
01254 for (i = 0; i < w2->numpoints; i++)
01255 {
01256 if (DotProduct(normal1, w2->p[i]) - dist1 > WCONVEX_EPSILON) return true;
01257 } //end for
01258
01259 return false;
01260 } //end of the function WindingsNonConvex
|
|
|
Definition at line 36 of file l_poly.c. Referenced by AllocWinding(), FreeWinding(), and ResetWindings(). |
|
|
Definition at line 41 of file l_poly.c. Referenced by AllocWinding(), and ResetWindings(). |
|
|
Definition at line 37 of file l_poly.c. Referenced by AllocWinding(), and ResetWindings(). |
|
|
Definition at line 127 of file l_poly.c. Referenced by RemoveColinearPoints(). |
|
|
Definition at line 38 of file l_poly.c. Referenced by AllocWinding(), and ResetWindings(). |
|
|
Definition at line 39 of file l_poly.c. Referenced by AllocWinding(), and ResetWindings(). |
|
|
Definition at line 40 of file l_poly.c. Referenced by AllocWinding(), FreeWinding(), and ResetWindings(). |
|
|
Definition at line 1356 of file l_threads.c. Referenced by AllocBrush(), AllocNode(), AllocPortal(), AllocWinding(), BrushBSP(), BuildTree(), BuildTree_r(), BuildTreeThread(), FreeBrush(), FreePortal(), FreeTree_r(), FreeWinding(), LightMain(), main(), RemoveColinearPoints(), RunThreadsOnIndividual(), SelectSplitSide(), SunToPoint(), ThreadSetDefault(), TraceAgainstSurface(), TraceLine(), TraceLtm(), Tree_Free_r(), VisMain(), VLightMain(), and VSoundMain(). |
|
|
Definition at line 43 of file l_poly.c. Referenced by ResetWindings(), and WindingError(). |
1.3.9.1