2 /*
3 Polygon clipping routines written by Forest Hale and placed into public domain.
4 */
6 #include "quakedef.h"
8 #include <math.h>
9 #include "polygon.h"
11 void PolygonF_QuadForPlane(float *outpoints, float planenormalx, float planenormaly, float planenormalz, float planedist, float quadsize)
12 {
14         if (fabs(planenormalz) > fabs(planenormalx) && fabs(planenormalz) > fabs(planenormaly))
15         {
19         }
20         else
21         {
25         }
26         // d = -DotProduct(quadup, planenormal);
29         quadup[0] += d * planenormalx;
30         quadup[1] += d * planenormaly;
31         quadup[2] += d * planenormalz;
41         // make the points
54 }
56 void PolygonD_QuadForPlane(double *outpoints, double planenormalx, double planenormaly, double planenormalz, double planedist, double quadsize)
57 {
59         if (fabs(planenormalz) > fabs(planenormalx) && fabs(planenormalz) > fabs(planenormaly))
60         {
64         }
65         else
66         {
70         }
71         // d = -DotProduct(quadup, planenormal);
74         quadup[0] += d * planenormalx;
75         quadup[1] += d * planenormaly;
76         quadup[2] += d * planenormalz;
86         // make the points
99 }
101 int PolygonF_Clip(int innumpoints, const float *inpoints, float planenormalx, float planenormaly, float planenormalz, float planedist, float epsilon, int outfrontmaxpoints, float *outfrontpoints)
102 {
103         int i, frontcount = 0;
104         const float *n, *p;
105         float frac, pdist, ndist;
106         if (innumpoints < 1)
107                 return 0;
108         n = inpoints;
109         ndist = n[0] * planenormalx + n[1] * planenormaly + n[2] * planenormalz - planedist;
110         for(i = 0;i < innumpoints;i++)
111         {
112                 p = n;
113                 pdist = ndist;
114                 n = inpoints + ((i + 1) < innumpoints ? (i + 1) : 0) * 3;
115                 ndist = n[0] * planenormalx + n[1] * planenormaly + n[2] * planenormalz - planedist;
116                 if (pdist >= -epsilon)
117                 {
118                         if (frontcount < outfrontmaxpoints)
119                         {
120                                 *outfrontpoints++ = p[0];
121                                 *outfrontpoints++ = p[1];
122                                 *outfrontpoints++ = p[2];
123                         }
124                         frontcount++;
125                 }
126                 if ((pdist > epsilon && ndist < -epsilon) || (pdist < -epsilon && ndist > epsilon))
127                 {
128                         frac = pdist / (pdist - ndist);
129                         if (frontcount < outfrontmaxpoints)
130                         {
131                                 *outfrontpoints++ = p[0] + frac * (n[0] - p[0]);
132                                 *outfrontpoints++ = p[1] + frac * (n[1] - p[1]);
133                                 *outfrontpoints++ = p[2] + frac * (n[2] - p[2]);
134                         }
135                         frontcount++;
136                 }
137         }
138         return frontcount;
139 }
141 int PolygonD_Clip(int innumpoints, const double *inpoints, double planenormalx, double planenormaly, double planenormalz, double planedist, double epsilon, int outfrontmaxpoints, double *outfrontpoints)
142 {
143         int i, frontcount = 0;
144         const double *n, *p;
145         double frac, pdist, ndist;
146         if (innumpoints < 1)
147                 return 0;
148         n = inpoints;
149         ndist = n[0] * planenormalx + n[1] * planenormaly + n[2] * planenormalz - planedist;
150         for(i = 0;i < innumpoints;i++)
151         {
152                 p = n;
153                 pdist = ndist;
154                 n = inpoints + ((i + 1) < innumpoints ? (i + 1) : 0) * 3;
155                 ndist = n[0] * planenormalx + n[1] * planenormaly + n[2] * planenormalz - planedist;
156                 if (pdist >= -epsilon)
157                 {
158                         if (frontcount < outfrontmaxpoints)
159                         {
160                                 *outfrontpoints++ = p[0];
161                                 *outfrontpoints++ = p[1];
162                                 *outfrontpoints++ = p[2];
163                         }
164                         frontcount++;
165                 }
166                 if ((pdist > epsilon && ndist < -epsilon) || (pdist < -epsilon && ndist > epsilon))
167                 {
168                         frac = pdist / (pdist - ndist);
169                         if (frontcount < outfrontmaxpoints)
170                         {
171                                 *outfrontpoints++ = p[0] + frac * (n[0] - p[0]);
172                                 *outfrontpoints++ = p[1] + frac * (n[1] - p[1]);
173                                 *outfrontpoints++ = p[2] + frac * (n[2] - p[2]);
174                         }
175                         frontcount++;
176                 }
177         }
178         return frontcount;
179 }
181 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)
182 {
183         int i, frontcount = 0, backcount = 0, oncount = 0;
184         const float *n, *p;
185         float frac, pdist, ndist;
186         if (innumpoints)
187         {
188                 n = inpoints;
189                 ndist = n[0] * planenormalx + n[1] * planenormaly + n[2] * planenormalz - planedist;
190                 for(i = 0;i < innumpoints;i++)
191                 {
192                         p = n;
193                         pdist = ndist;
194                         n = inpoints + ((i + 1) < innumpoints ? (i + 1) : 0) * 3;
195                         ndist = n[0] * planenormalx + n[1] * planenormaly + n[2] * planenormalz - planedist;
196                         if (pdist >= -epsilon)
197                         {
198                                 if (pdist <= epsilon)
199                                         oncount++;
200                                 if (frontcount < outfrontmaxpoints)
201                                 {
202                                         *outfrontpoints++ = p[0];
203                                         *outfrontpoints++ = p[1];
204                                         *outfrontpoints++ = p[2];
205                                 }
206                                 frontcount++;
207                         }
208                         if (pdist <= epsilon)
209                         {
210                                 if (backcount < outbackmaxpoints)
211                                 {
212                                         *outbackpoints++ = p[0];
213                                         *outbackpoints++ = p[1];
214                                         *outbackpoints++ = p[2];
215                                 }
216                                 backcount++;
217                         }
218                         if ((pdist > epsilon && ndist < -epsilon) || (pdist < -epsilon && ndist > epsilon))
219                         {
220                                 oncount++;
221                                 frac = pdist / (pdist - ndist);
222                                 if (frontcount < outfrontmaxpoints)
223                                 {
224                                         *outfrontpoints++ = p[0] + frac * (n[0] - p[0]);
225                                         *outfrontpoints++ = p[1] + frac * (n[1] - p[1]);
226                                         *outfrontpoints++ = p[2] + frac * (n[2] - p[2]);
227                                 }
228                                 frontcount++;
229                                 if (backcount < outbackmaxpoints)
230                                 {
231                                         *outbackpoints++ = p[0] + frac * (n[0] - p[0]);
232                                         *outbackpoints++ = p[1] + frac * (n[1] - p[1]);
233                                         *outbackpoints++ = p[2] + frac * (n[2] - p[2]);
234                                 }
235                                 backcount++;
236                         }
237                 }
238         }
239         if (neededfrontpoints)
240                 *neededfrontpoints = frontcount;
241         if (neededbackpoints)
242                 *neededbackpoints = backcount;
243         if (oncountpointer)
244                 *oncountpointer = oncount;
245 }
247 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)
248 {
249         int i = 0, frontcount = 0, backcount = 0, oncount = 0;
250         const double *n, *p;
251         double frac, pdist, ndist;
252         if (innumpoints)
253         {
254                 n = inpoints;
255                 ndist = n[0] * planenormalx + n[1] * planenormaly + n[2] * planenormalz - planedist;
256                 for(i = 0;i < innumpoints;i++)
257                 {
258                         p = n;
259                         pdist = ndist;
260                         n = inpoints + ((i + 1) < innumpoints ? (i + 1) : 0) * 3;
261                         ndist = n[0] * planenormalx + n[1] * planenormaly + n[2] * planenormalz - planedist;
262                         if (pdist >= -epsilon)
263                         {
264                                 if (pdist <= epsilon)
265                                         oncount++;
266                                 if (frontcount < outfrontmaxpoints)
267                                 {
268                                         *outfrontpoints++ = p[0];
269                                         *outfrontpoints++ = p[1];
270                                         *outfrontpoints++ = p[2];
271                                 }
272                                 frontcount++;
273                         }
274                         if (pdist <= epsilon)
275                         {
276                                 if (backcount < outbackmaxpoints)
277                                 {
278                                         *outbackpoints++ = p[0];
279                                         *outbackpoints++ = p[1];
280                                         *outbackpoints++ = p[2];
281                                 }
282                                 backcount++;
283                         }
284                         if ((pdist > epsilon && ndist < -epsilon) || (pdist < -epsilon && ndist > epsilon))
285                         {
286                                 oncount++;
287                                 frac = pdist / (pdist - ndist);
288                                 if (frontcount < outfrontmaxpoints)
289                                 {
290                                         *outfrontpoints++ = p[0] + frac * (n[0] - p[0]);
291                                         *outfrontpoints++ = p[1] + frac * (n[1] - p[1]);
292                                         *outfrontpoints++ = p[2] + frac * (n[2] - p[2]);
293                                 }
294                                 frontcount++;
295                                 if (backcount < outbackmaxpoints)
296                                 {
297                                         *outbackpoints++ = p[0] + frac * (n[0] - p[0]);
298                                         *outbackpoints++ = p[1] + frac * (n[1] - p[1]);
299                                         *outbackpoints++ = p[2] + frac * (n[2] - p[2]);
300                                 }
301                                 backcount++;
302                         }
303                 }
304         }
305         if (neededfrontpoints)
306                 *neededfrontpoints = frontcount;
307         if (neededbackpoints)
308                 *neededbackpoints = backcount;
309         if (oncountpointer)
310                 *oncountpointer = oncount;
311 }