X-Git-Url: http://git.xonotic.org/?a=blobdiff_plain;f=polygon.c;h=99ceb0b9d7680abecec324bd44d4d66429aaa013;hb=086c6c4f1ccdafa4e305eb0903f5570361594c20;hp=8133dce3dbd0e99d26dbf705a0b63498c723b12c;hpb=2824a71dcb6cb3568f87b9a3dae340c342865669;p=xonotic%2Fdarkplaces.git diff --git a/polygon.c b/polygon.c index 8133dce3..99ceb0b9 100644 --- a/polygon.c +++ b/polygon.c @@ -9,7 +9,7 @@ Polygon clipping routines written by Forest Hale and placed into public domain. void PolygonF_QuadForPlane(float *outpoints, float planenormalx, float planenormaly, float planenormalz, float planedist, float quadsize) { float d, quadright[3], quadup[3]; - if (planenormalz > planenormalx && planenormalz > planenormaly) + if (fabs(planenormalz) > fabs(planenormalx) && fabs(planenormalz) > fabs(planenormaly)) { quadup[0] = 1; quadup[1] = 0; @@ -25,10 +25,10 @@ void PolygonF_QuadForPlane(float *outpoints, float planenormalx, float planenorm d = -(quadup[0] * planenormalx + quadup[1] * planenormaly + quadup[2] * planenormalz); // VectorMA(quadup, d, planenormal, quadup); quadup[0] += d * planenormalx; - quadup[1] += d * planenormalx; - quadup[2] += d * planenormalx; + quadup[1] += d * planenormaly; + quadup[2] += d * planenormalz; // VectorNormalize(quadup); - d = 1.0 / sqrt(quadup[0] * quadup[0] + quadup[1] * quadup[1] + quadup[2] * quadup[2]); + d = (float)(1.0 / sqrt(quadup[0] * quadup[0] + quadup[1] * quadup[1] + quadup[2] * quadup[2])); quadup[0] *= d; quadup[1] *= d; quadup[2] *= d; @@ -54,7 +54,7 @@ void PolygonF_QuadForPlane(float *outpoints, float planenormalx, float planenorm void PolygonD_QuadForPlane(double *outpoints, double planenormalx, double planenormaly, double planenormalz, double planedist, double quadsize) { double d, quadright[3], quadup[3]; - if (planenormalz > planenormalx && planenormalz > planenormaly) + if (fabs(planenormalz) > fabs(planenormalx) && fabs(planenormalz) > fabs(planenormaly)) { quadup[0] = 1; quadup[1] = 0; @@ -70,8 +70,8 @@ void PolygonD_QuadForPlane(double *outpoints, double planenormalx, double planen d = -(quadup[0] * planenormalx + quadup[1] * planenormaly + quadup[2] * planenormalz); // VectorMA(quadup, d, planenormal, quadup); quadup[0] += d * planenormalx; - quadup[1] += d * planenormalx; - quadup[2] += d * planenormalx; + quadup[1] += d * planenormaly; + quadup[2] += d * planenormalz; // VectorNormalize(quadup); d = 1.0 / sqrt(quadup[0] * quadup[0] + quadup[1] * quadup[1] + quadup[2] * quadup[2]); quadup[0] *= d; @@ -96,18 +96,20 @@ void PolygonD_QuadForPlane(double *outpoints, double planenormalx, double planen outpoints[11] = planedist * planenormalz - quadsize * quadright[2] - quadsize * quadup[2]; } -void PolygonF_Divide(unsigned int innumpoints, const float *inpoints, float planenormalx, float planenormaly, float planenormalz, float planedist, float epsilon, unsigned int outfrontmaxpoints, float *outfrontpoints, unsigned int *neededfrontpoints, unsigned int outbackmaxpoints, float *outbackpoints, unsigned int *neededbackpoints) +int PolygonF_Clip(int innumpoints, const float *inpoints, float planenormalx, float planenormaly, float planenormalz, float planedist, float epsilon, int outfrontmaxpoints, float *outfrontpoints) { - unsigned int i, frontcount, backcount; + int i, frontcount = 0; const float *n, *p; float frac, pdist, ndist; - frontcount = 0; - backcount = 0; - p = inpoints + (innumpoints - 1) * 3; + if (innumpoints < 1) + return 0; n = inpoints; - pdist = p[0] * planenormalx + p[1] * planenormaly + p[2] * planenormalz - planedist; - for (i = 0;i < innumpoints;i++) + ndist = n[0] * planenormalx + n[1] * planenormaly + n[2] * planenormalz - planedist; + for(i = 0;i < innumpoints;i++) { + p = n; + pdist = ndist; + n = inpoints + ((i + 1) < innumpoints ? (i + 1) : 0) * 3; ndist = n[0] * planenormalx + n[1] * planenormaly + n[2] * planenormalz - planedist; if (pdist >= -epsilon) { @@ -119,16 +121,6 @@ void PolygonF_Divide(unsigned int innumpoints, const float *inpoints, float plan } frontcount++; } - if (pdist <= epsilon) - { - if (backcount < outbackmaxpoints) - { - *outbackpoints++ = p[0]; - *outbackpoints++ = p[1]; - *outbackpoints++ = p[2]; - } - backcount++; - } if ((pdist > epsilon && ndist < -epsilon) || (pdist < -epsilon && ndist > epsilon)) { frac = pdist / (pdist - ndist); @@ -139,36 +131,25 @@ void PolygonF_Divide(unsigned int innumpoints, const float *inpoints, float plan *outfrontpoints++ = p[2] + frac * (n[2] - p[2]); } frontcount++; - if (backcount < outbackmaxpoints) - { - *outbackpoints++ = p[0] + frac * (n[0] - p[0]); - *outbackpoints++ = p[1] + frac * (n[1] - p[1]); - *outbackpoints++ = p[2] + frac * (n[2] - p[2]); - } - backcount++; } - p = n; - n += 3; - pdist = ndist; } - if (neededfrontpoints) - *neededfrontpoints = frontcount; - if (neededbackpoints) - *neededbackpoints = backcount; + return frontcount; } -void PolygonD_Divide(unsigned int innumpoints, const double *inpoints, double planenormalx, double planenormaly, double planenormalz, double planedist, double epsilon, unsigned int outfrontmaxpoints, double *outfrontpoints, unsigned int *neededfrontpoints, unsigned int outbackmaxpoints, double *outbackpoints, unsigned int *neededbackpoints) +int PolygonD_Clip(int innumpoints, const double *inpoints, double planenormalx, double planenormaly, double planenormalz, double planedist, double epsilon, int outfrontmaxpoints, double *outfrontpoints) { - unsigned int i, frontcount, backcount; + int i, frontcount = 0; const double *n, *p; double frac, pdist, ndist; - frontcount = 0; - backcount = 0; - p = inpoints + (innumpoints - 1) * 3; + if (innumpoints < 1) + return 0; n = inpoints; - pdist = p[0] * planenormalx + p[1] * planenormaly + p[2] * planenormalz - planedist; - for (i = 0;i < innumpoints;i++) + ndist = n[0] * planenormalx + n[1] * planenormaly + n[2] * planenormalz - planedist; + for(i = 0;i < innumpoints;i++) { + p = n; + pdist = ndist; + n = inpoints + ((i + 1) < innumpoints ? (i + 1) : 0) * 3; ndist = n[0] * planenormalx + n[1] * planenormaly + n[2] * planenormalz - planedist; if (pdist >= -epsilon) { @@ -180,16 +161,6 @@ void PolygonD_Divide(unsigned int innumpoints, const double *inpoints, double pl } frontcount++; } - if (pdist <= epsilon) - { - if (backcount < outbackmaxpoints) - { - *outbackpoints++ = p[0]; - *outbackpoints++ = p[1]; - *outbackpoints++ = p[2]; - } - backcount++; - } if ((pdist > epsilon && ndist < -epsilon) || (pdist < -epsilon && ndist > epsilon)) { frac = pdist / (pdist - ndist); @@ -200,21 +171,140 @@ void PolygonD_Divide(unsigned int innumpoints, const double *inpoints, double pl *outfrontpoints++ = p[2] + frac * (n[2] - p[2]); } frontcount++; - if (backcount < outbackmaxpoints) + } + } + return frontcount; +} + +void PolygonF_Divide(int innumpoints, const float *inpoints, float planenormalx, float planenormaly, float planenormalz, float planedist, float epsilon, int outfrontmaxpoints, float *outfrontpoints, int *neededfrontpoints, int outbackmaxpoints, float *outbackpoints, int *neededbackpoints, int *oncountpointer) +{ + int i, frontcount = 0, backcount = 0, oncount = 0; + const float *n, *p; + float frac, pdist, ndist; + if (innumpoints) + { + n = inpoints; + ndist = n[0] * planenormalx + n[1] * planenormaly + n[2] * planenormalz - planedist; + for(i = 0;i < innumpoints;i++) + { + p = n; + pdist = ndist; + n = inpoints + ((i + 1) < innumpoints ? (i + 1) : 0) * 3; + ndist = n[0] * planenormalx + n[1] * planenormaly + n[2] * planenormalz - planedist; + if (pdist >= -epsilon) + { + if (pdist <= epsilon) + oncount++; + if (frontcount < outfrontmaxpoints) + { + *outfrontpoints++ = p[0]; + *outfrontpoints++ = p[1]; + *outfrontpoints++ = p[2]; + } + frontcount++; + } + if (pdist <= epsilon) { - *outbackpoints++ = p[0] + frac * (n[0] - p[0]); - *outbackpoints++ = p[1] + frac * (n[1] - p[1]); - *outbackpoints++ = p[2] + frac * (n[2] - p[2]); + if (backcount < outbackmaxpoints) + { + *outbackpoints++ = p[0]; + *outbackpoints++ = p[1]; + *outbackpoints++ = p[2]; + } + backcount++; + } + if ((pdist > epsilon && ndist < -epsilon) || (pdist < -epsilon && ndist > epsilon)) + { + oncount++; + frac = pdist / (pdist - ndist); + if (frontcount < outfrontmaxpoints) + { + *outfrontpoints++ = p[0] + frac * (n[0] - p[0]); + *outfrontpoints++ = p[1] + frac * (n[1] - p[1]); + *outfrontpoints++ = p[2] + frac * (n[2] - p[2]); + } + frontcount++; + if (backcount < outbackmaxpoints) + { + *outbackpoints++ = p[0] + frac * (n[0] - p[0]); + *outbackpoints++ = p[1] + frac * (n[1] - p[1]); + *outbackpoints++ = p[2] + frac * (n[2] - p[2]); + } + backcount++; + } + } + } + if (neededfrontpoints) + *neededfrontpoints = frontcount; + if (neededbackpoints) + *neededbackpoints = backcount; + if (oncountpointer) + *oncountpointer = oncount; +} + +void PolygonD_Divide(int innumpoints, const double *inpoints, double planenormalx, double planenormaly, double planenormalz, double planedist, double epsilon, int outfrontmaxpoints, double *outfrontpoints, int *neededfrontpoints, int outbackmaxpoints, double *outbackpoints, int *neededbackpoints, int *oncountpointer) +{ + int i = 0, frontcount = 0, backcount = 0, oncount = 0; + const double *n, *p; + double frac, pdist, ndist; + if (innumpoints) + { + n = inpoints; + ndist = n[0] * planenormalx + n[1] * planenormaly + n[2] * planenormalz - planedist; + for(i = 0;i < innumpoints;i++) + { + p = n; + pdist = ndist; + n = inpoints + ((i + 1) < innumpoints ? (i + 1) : 0) * 3; + ndist = n[0] * planenormalx + n[1] * planenormaly + n[2] * planenormalz - planedist; + if (pdist >= -epsilon) + { + if (pdist <= epsilon) + oncount++; + if (frontcount < outfrontmaxpoints) + { + *outfrontpoints++ = p[0]; + *outfrontpoints++ = p[1]; + *outfrontpoints++ = p[2]; + } + frontcount++; + } + if (pdist <= epsilon) + { + if (backcount < outbackmaxpoints) + { + *outbackpoints++ = p[0]; + *outbackpoints++ = p[1]; + *outbackpoints++ = p[2]; + } + backcount++; + } + if ((pdist > epsilon && ndist < -epsilon) || (pdist < -epsilon && ndist > epsilon)) + { + oncount++; + frac = pdist / (pdist - ndist); + if (frontcount < outfrontmaxpoints) + { + *outfrontpoints++ = p[0] + frac * (n[0] - p[0]); + *outfrontpoints++ = p[1] + frac * (n[1] - p[1]); + *outfrontpoints++ = p[2] + frac * (n[2] - p[2]); + } + frontcount++; + if (backcount < outbackmaxpoints) + { + *outbackpoints++ = p[0] + frac * (n[0] - p[0]); + *outbackpoints++ = p[1] + frac * (n[1] - p[1]); + *outbackpoints++ = p[2] + frac * (n[2] - p[2]); + } + backcount++; } - backcount++; } - p = n; - n += 3; - pdist = ndist; } if (neededfrontpoints) *neededfrontpoints = frontcount; if (neededbackpoints) *neededbackpoints = backcount; + if (oncountpointer) + *oncountpointer = oncount; }