From c3bb17924a53d7654d9072eb6770a4331a5c021f Mon Sep 17 00:00:00 2001 From: havoc Date: Mon, 31 Dec 2007 16:36:14 +0000 Subject: [PATCH] optimized PolygonF_Divide/PolygonD_Divide functions, now performing only one dot-product per iteration rather than two added PolygonF_Clip/PolygonD_Clip functions which keep only the front side git-svn-id: svn://svn.icculus.org/twilight/trunk/darkplaces@7885 d7cf8633-e32d-0410-b094-e92efae38249 --- polygon.c | 206 +++++++++++++++++++++++++++++++++++++++--------------- polygon.h | 2 + 2 files changed, 150 insertions(+), 58 deletions(-) diff --git a/polygon.c b/polygon.c index a02c032c..11340a8a 100644 --- a/polygon.c +++ b/polygon.c @@ -98,21 +98,23 @@ void PolygonD_QuadForPlane(double *outpoints, double planenormalx, double planen outpoints[11] = planedist * planenormalz - quadsize * quadright[2] - quadsize * quadup[2]; } -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 PolygonF_Clip(int innumpoints, const float *inpoints, float planenormalx, float planenormaly, float planenormalz, float planedist, float epsilon, int outfrontmaxpoints, float *outfrontpoints) { - int i, frontcount = 0, backcount = 0, oncount = 0; + int i, frontcount = 0; const float *n, *p; - double frac, pdist, ndist; - for (i = 0;i < innumpoints;i++) + float frac, pdist, ndist; + if (innumpoints < 1) + return 0; + n = inpoints; + ndist = n[0] * planenormalx + n[1] * planenormaly + n[2] * planenormalz - planedist; + for(i = 0;i < innumpoints;i++) { - p = inpoints + i * 3; + p = n; + pdist = ndist; n = inpoints + ((i + 1) < innumpoints ? (i + 1) : 0) * 3; - pdist = p[0] * planenormalx + p[1] * planenormaly + p[2] * planenormalz - planedist; ndist = n[0] * planenormalx + n[1] * planenormaly + n[2] * planenormalz - planedist; if (pdist >= -epsilon) { - if (pdist <= epsilon) - oncount++; if (frontcount < outfrontmaxpoints) { *outfrontpoints++ = p[0]; @@ -121,59 +123,38 @@ void PolygonF_Divide(int innumpoints, const float *inpoints, float planenormalx, } 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++ = (float)(p[0] + frac * (n[0] - p[0])); - *outfrontpoints++ = (float)(p[1] + frac * (n[1] - p[1])); - *outfrontpoints++ = (float)(p[2] + frac * (n[2] - p[2])); + *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++ = (float)(p[0] + frac * (n[0] - p[0])); - *outbackpoints++ = (float)(p[1] + frac * (n[1] - p[1])); - *outbackpoints++ = (float)(p[2] + frac * (n[2] - p[2])); - } - backcount++; } } - if (neededfrontpoints) - *neededfrontpoints = frontcount; - if (neededbackpoints) - *neededbackpoints = backcount; - if (oncountpointer) - *oncountpointer = oncount; + return frontcount; } -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 PolygonD_Clip(int innumpoints, const double *inpoints, double planenormalx, double planenormaly, double planenormalz, double planedist, double epsilon, int outfrontmaxpoints, double *outfrontpoints) { - int i, frontcount = 0, backcount = 0, oncount = 0; + int i, frontcount = 0; const double *n, *p; double frac, pdist, ndist; - for (i = 0;i < innumpoints;i++) + if (innumpoints < 1) + return 0; + n = inpoints; + ndist = n[0] * planenormalx + n[1] * planenormaly + n[2] * planenormalz - planedist; + for(i = 0;i < innumpoints;i++) { - p = inpoints + i * 3; + p = n; + pdist = ndist; n = inpoints + ((i + 1) < innumpoints ? (i + 1) : 0) * 3; - pdist = p[0] * planenormalx + p[1] * planenormaly + p[2] * planenormalz - planedist; ndist = n[0] * planenormalx + n[1] * planenormaly + n[2] * planenormalz - planedist; if (pdist >= -epsilon) { - if (pdist <= epsilon) - oncount++; if (frontcount < outfrontmaxpoints) { *outfrontpoints++ = p[0]; @@ -182,19 +163,8 @@ void PolygonD_Divide(int innumpoints, const double *inpoints, double planenormal } 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) { @@ -203,13 +173,133 @@ void PolygonD_Divide(int innumpoints, const double *inpoints, double planenormal *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) + { + if (backcount < outbackmaxpoints) + { + *outbackpoints++ = p[0]; + *outbackpoints++ = p[1]; + *outbackpoints++ = p[2]; + } + backcount++; + } + if ((pdist > epsilon && ndist < -epsilon) || (pdist < -epsilon && ndist > 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]); + 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++; } } if (neededfrontpoints) diff --git a/polygon.h b/polygon.h index 21537f8b..e8bf2e81 100644 --- a/polygon.h +++ b/polygon.h @@ -8,6 +8,8 @@ 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); void PolygonD_QuadForPlane(double *outpoints, double planenormalx, double planenormaly, double planenormalz, double planedist, double quadsize); +int PolygonF_Clip(int innumpoints, const float *inpoints, float planenormalx, float planenormaly, float planenormalz, float planedist, float epsilon, int outfrontmaxpoints, float *outfrontpoints); +int PolygonD_Clip(int innumpoints, const double *inpoints, double planenormalx, double planenormaly, double planenormalz, double planedist, double epsilon, int outfrontmaxpoints, double *outfrontpoints); 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); 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); -- 2.39.2