3 Polygon clipping routines written by Forest Hale and placed into public domain.
9 void PolygonF_QuadForPlane(float *outpoints, float planenormalx, float planenormaly, float planenormalz, float planedist, float quadsize)
11 float d, quadright[3], quadup[3];
12 if (fabs(planenormalz) > fabs(planenormalx) && fabs(planenormalz) > fabs(planenormaly))
24 // d = -DotProduct(quadup, planenormal);
25 d = -(quadup[0] * planenormalx + quadup[1] * planenormaly + quadup[2] * planenormalz);
26 // VectorMA(quadup, d, planenormal, quadup);
27 quadup[0] += d * planenormalx;
28 quadup[1] += d * planenormaly;
29 quadup[2] += d * planenormalz;
30 // VectorNormalize(quadup);
31 d = (float)(1.0 / sqrt(quadup[0] * quadup[0] + quadup[1] * quadup[1] + quadup[2] * quadup[2]));
35 // CrossProduct(quadup,planenormal,quadright);
36 quadright[0] = quadup[1] * planenormalz - quadup[2] * planenormaly;
37 quadright[1] = quadup[2] * planenormalx - quadup[0] * planenormalz;
38 quadright[2] = quadup[0] * planenormaly - quadup[1] * planenormalx;
40 outpoints[0] = planedist * planenormalx - quadsize * quadright[0] + quadsize * quadup[0];
41 outpoints[1] = planedist * planenormaly - quadsize * quadright[1] + quadsize * quadup[1];
42 outpoints[2] = planedist * planenormalz - quadsize * quadright[2] + quadsize * quadup[2];
43 outpoints[3] = planedist * planenormalx + quadsize * quadright[0] + quadsize * quadup[0];
44 outpoints[4] = planedist * planenormaly + quadsize * quadright[1] + quadsize * quadup[1];
45 outpoints[5] = planedist * planenormalz + quadsize * quadright[2] + quadsize * quadup[2];
46 outpoints[6] = planedist * planenormalx + quadsize * quadright[0] - quadsize * quadup[0];
47 outpoints[7] = planedist * planenormaly + quadsize * quadright[1] - quadsize * quadup[1];
48 outpoints[8] = planedist * planenormalz + quadsize * quadright[2] - quadsize * quadup[2];
49 outpoints[9] = planedist * planenormalx - quadsize * quadright[0] - quadsize * quadup[0];
50 outpoints[10] = planedist * planenormaly - quadsize * quadright[1] - quadsize * quadup[1];
51 outpoints[11] = planedist * planenormalz - quadsize * quadright[2] - quadsize * quadup[2];
54 void PolygonD_QuadForPlane(double *outpoints, double planenormalx, double planenormaly, double planenormalz, double planedist, double quadsize)
56 double d, quadright[3], quadup[3];
57 if (fabs(planenormalz) > fabs(planenormalx) && fabs(planenormalz) > fabs(planenormaly))
69 // d = -DotProduct(quadup, planenormal);
70 d = -(quadup[0] * planenormalx + quadup[1] * planenormaly + quadup[2] * planenormalz);
71 // VectorMA(quadup, d, planenormal, quadup);
72 quadup[0] += d * planenormalx;
73 quadup[1] += d * planenormaly;
74 quadup[2] += d * planenormalz;
75 // VectorNormalize(quadup);
76 d = 1.0 / sqrt(quadup[0] * quadup[0] + quadup[1] * quadup[1] + quadup[2] * quadup[2]);
80 // CrossProduct(quadup,planenormal,quadright);
81 quadright[0] = quadup[1] * planenormalz - quadup[2] * planenormaly;
82 quadright[1] = quadup[2] * planenormalx - quadup[0] * planenormalz;
83 quadright[2] = quadup[0] * planenormaly - quadup[1] * planenormalx;
85 outpoints[0] = planedist * planenormalx - quadsize * quadright[0] + quadsize * quadup[0];
86 outpoints[1] = planedist * planenormaly - quadsize * quadright[1] + quadsize * quadup[1];
87 outpoints[2] = planedist * planenormalz - quadsize * quadright[2] + quadsize * quadup[2];
88 outpoints[3] = planedist * planenormalx + quadsize * quadright[0] + quadsize * quadup[0];
89 outpoints[4] = planedist * planenormaly + quadsize * quadright[1] + quadsize * quadup[1];
90 outpoints[5] = planedist * planenormalz + quadsize * quadright[2] + quadsize * quadup[2];
91 outpoints[6] = planedist * planenormalx + quadsize * quadright[0] - quadsize * quadup[0];
92 outpoints[7] = planedist * planenormaly + quadsize * quadright[1] - quadsize * quadup[1];
93 outpoints[8] = planedist * planenormalz + quadsize * quadright[2] - quadsize * quadup[2];
94 outpoints[9] = planedist * planenormalx - quadsize * quadright[0] - quadsize * quadup[0];
95 outpoints[10] = planedist * planenormaly - quadsize * quadright[1] - quadsize * quadup[1];
96 outpoints[11] = planedist * planenormalz - quadsize * quadright[2] - quadsize * quadup[2];
99 int PolygonF_Clip(int innumpoints, const float *inpoints, float planenormalx, float planenormaly, float planenormalz, float planedist, float epsilon, int outfrontmaxpoints, float *outfrontpoints)
101 int i, frontcount = 0;
103 float frac, pdist, ndist;
107 ndist = n[0] * planenormalx + n[1] * planenormaly + n[2] * planenormalz - planedist;
108 for(i = 0;i < innumpoints;i++)
112 n = inpoints + ((i + 1) < innumpoints ? (i + 1) : 0) * 3;
113 ndist = n[0] * planenormalx + n[1] * planenormaly + n[2] * planenormalz - planedist;
114 if (pdist >= -epsilon)
116 if (frontcount < outfrontmaxpoints)
118 *outfrontpoints++ = p[0];
119 *outfrontpoints++ = p[1];
120 *outfrontpoints++ = p[2];
124 if ((pdist > epsilon && ndist < -epsilon) || (pdist < -epsilon && ndist > epsilon))
126 frac = pdist / (pdist - ndist);
127 if (frontcount < outfrontmaxpoints)
129 *outfrontpoints++ = p[0] + frac * (n[0] - p[0]);
130 *outfrontpoints++ = p[1] + frac * (n[1] - p[1]);
131 *outfrontpoints++ = p[2] + frac * (n[2] - p[2]);
139 int PolygonD_Clip(int innumpoints, const double *inpoints, double planenormalx, double planenormaly, double planenormalz, double planedist, double epsilon, int outfrontmaxpoints, double *outfrontpoints)
141 int i, frontcount = 0;
143 double frac, pdist, ndist;
147 ndist = n[0] * planenormalx + n[1] * planenormaly + n[2] * planenormalz - planedist;
148 for(i = 0;i < innumpoints;i++)
152 n = inpoints + ((i + 1) < innumpoints ? (i + 1) : 0) * 3;
153 ndist = n[0] * planenormalx + n[1] * planenormaly + n[2] * planenormalz - planedist;
154 if (pdist >= -epsilon)
156 if (frontcount < outfrontmaxpoints)
158 *outfrontpoints++ = p[0];
159 *outfrontpoints++ = p[1];
160 *outfrontpoints++ = p[2];
164 if ((pdist > epsilon && ndist < -epsilon) || (pdist < -epsilon && ndist > epsilon))
166 frac = pdist / (pdist - ndist);
167 if (frontcount < outfrontmaxpoints)
169 *outfrontpoints++ = p[0] + frac * (n[0] - p[0]);
170 *outfrontpoints++ = p[1] + frac * (n[1] - p[1]);
171 *outfrontpoints++ = p[2] + frac * (n[2] - p[2]);
179 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)
181 int i, frontcount = 0, backcount = 0, oncount = 0;
183 float frac, pdist, ndist;
187 ndist = n[0] * planenormalx + n[1] * planenormaly + n[2] * planenormalz - planedist;
188 for(i = 0;i < innumpoints;i++)
192 n = inpoints + ((i + 1) < innumpoints ? (i + 1) : 0) * 3;
193 ndist = n[0] * planenormalx + n[1] * planenormaly + n[2] * planenormalz - planedist;
194 if (pdist >= -epsilon)
196 if (pdist <= epsilon)
198 if (frontcount < outfrontmaxpoints)
200 *outfrontpoints++ = p[0];
201 *outfrontpoints++ = p[1];
202 *outfrontpoints++ = p[2];
206 if (pdist <= epsilon)
208 if (backcount < outbackmaxpoints)
210 *outbackpoints++ = p[0];
211 *outbackpoints++ = p[1];
212 *outbackpoints++ = p[2];
216 if ((pdist > epsilon && ndist < -epsilon) || (pdist < -epsilon && ndist > epsilon))
219 frac = pdist / (pdist - ndist);
220 if (frontcount < outfrontmaxpoints)
222 *outfrontpoints++ = p[0] + frac * (n[0] - p[0]);
223 *outfrontpoints++ = p[1] + frac * (n[1] - p[1]);
224 *outfrontpoints++ = p[2] + frac * (n[2] - p[2]);
227 if (backcount < outbackmaxpoints)
229 *outbackpoints++ = p[0] + frac * (n[0] - p[0]);
230 *outbackpoints++ = p[1] + frac * (n[1] - p[1]);
231 *outbackpoints++ = p[2] + frac * (n[2] - p[2]);
237 if (neededfrontpoints)
238 *neededfrontpoints = frontcount;
239 if (neededbackpoints)
240 *neededbackpoints = backcount;
242 *oncountpointer = oncount;
245 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)
247 int i = 0, frontcount = 0, backcount = 0, oncount = 0;
249 double frac, pdist, ndist;
253 ndist = n[0] * planenormalx + n[1] * planenormaly + n[2] * planenormalz - planedist;
254 for(i = 0;i < innumpoints;i++)
258 n = inpoints + ((i + 1) < innumpoints ? (i + 1) : 0) * 3;
259 ndist = n[0] * planenormalx + n[1] * planenormaly + n[2] * planenormalz - planedist;
260 if (pdist >= -epsilon)
262 if (pdist <= epsilon)
264 if (frontcount < outfrontmaxpoints)
266 *outfrontpoints++ = p[0];
267 *outfrontpoints++ = p[1];
268 *outfrontpoints++ = p[2];
272 if (pdist <= epsilon)
274 if (backcount < outbackmaxpoints)
276 *outbackpoints++ = p[0];
277 *outbackpoints++ = p[1];
278 *outbackpoints++ = p[2];
282 if ((pdist > epsilon && ndist < -epsilon) || (pdist < -epsilon && ndist > epsilon))
285 frac = pdist / (pdist - ndist);
286 if (frontcount < outfrontmaxpoints)
288 *outfrontpoints++ = p[0] + frac * (n[0] - p[0]);
289 *outfrontpoints++ = p[1] + frac * (n[1] - p[1]);
290 *outfrontpoints++ = p[2] + frac * (n[2] - p[2]);
293 if (backcount < outbackmaxpoints)
295 *outbackpoints++ = p[0] + frac * (n[0] - p[0]);
296 *outbackpoints++ = p[1] + frac * (n[1] - p[1]);
297 *outbackpoints++ = p[2] + frac * (n[2] - p[2]);
303 if (neededfrontpoints)
304 *neededfrontpoints = frontcount;
305 if (neededbackpoints)
306 *neededbackpoints = backcount;
308 *oncountpointer = oncount;