optimized PolygonF_Divide/PolygonD_Divide functions, now performing only
[divverent/darkplaces.git] / polygon.c
1
2 /*
3 Polygon clipping routines written by Forest Hale and placed into public domain.
4 */
5
6 #include "quakedef.h"
7
8 #include <math.h>
9 #include "polygon.h"
10
11 void PolygonF_QuadForPlane(float *outpoints, float planenormalx, float planenormaly, float planenormalz, float planedist, float quadsize)
12 {
13         float d, quadright[3], quadup[3];
14         if (fabs(planenormalz) > fabs(planenormalx) && fabs(planenormalz) > fabs(planenormaly))
15         {
16                 quadup[0] = 1;
17                 quadup[1] = 0;
18                 quadup[2] = 0;
19         }
20         else
21         {
22                 quadup[0] = 0;
23                 quadup[1] = 0;
24                 quadup[2] = 1;
25         }
26         // d = -DotProduct(quadup, planenormal);
27         d = -(quadup[0] * planenormalx + quadup[1] * planenormaly + quadup[2] * planenormalz);
28         // VectorMA(quadup, d, planenormal, quadup);
29         quadup[0] += d * planenormalx;
30         quadup[1] += d * planenormaly;
31         quadup[2] += d * planenormalz;
32         // VectorNormalize(quadup);
33         d = (float)(1.0 / sqrt(quadup[0] * quadup[0] + quadup[1] * quadup[1] + quadup[2] * quadup[2]));
34         quadup[0] *= d;
35         quadup[1] *= d;
36         quadup[2] *= d;
37         // CrossProduct(quadup,planenormal,quadright);
38         quadright[0] = quadup[1] * planenormalz - quadup[2] * planenormaly;
39         quadright[1] = quadup[2] * planenormalx - quadup[0] * planenormalz;
40         quadright[2] = quadup[0] * planenormaly - quadup[1] * planenormalx;
41         // make the points
42         outpoints[0] = planedist * planenormalx - quadsize * quadright[0] + quadsize * quadup[0];
43         outpoints[1] = planedist * planenormaly - quadsize * quadright[1] + quadsize * quadup[1];
44         outpoints[2] = planedist * planenormalz - quadsize * quadright[2] + quadsize * quadup[2];
45         outpoints[3] = planedist * planenormalx + quadsize * quadright[0] + quadsize * quadup[0];
46         outpoints[4] = planedist * planenormaly + quadsize * quadright[1] + quadsize * quadup[1];
47         outpoints[5] = planedist * planenormalz + quadsize * quadright[2] + quadsize * quadup[2];
48         outpoints[6] = planedist * planenormalx + quadsize * quadright[0] - quadsize * quadup[0];
49         outpoints[7] = planedist * planenormaly + quadsize * quadright[1] - quadsize * quadup[1];
50         outpoints[8] = planedist * planenormalz + quadsize * quadright[2] - quadsize * quadup[2];
51         outpoints[9] = planedist * planenormalx - quadsize * quadright[0] - quadsize * quadup[0];
52         outpoints[10] = planedist * planenormaly - quadsize * quadright[1] - quadsize * quadup[1];
53         outpoints[11] = planedist * planenormalz - quadsize * quadright[2] - quadsize * quadup[2];
54 }
55
56 void PolygonD_QuadForPlane(double *outpoints, double planenormalx, double planenormaly, double planenormalz, double planedist, double quadsize)
57 {
58         double d, quadright[3], quadup[3];
59         if (fabs(planenormalz) > fabs(planenormalx) && fabs(planenormalz) > fabs(planenormaly))
60         {
61                 quadup[0] = 1;
62                 quadup[1] = 0;
63                 quadup[2] = 0;
64         }
65         else
66         {
67                 quadup[0] = 0;
68                 quadup[1] = 0;
69                 quadup[2] = 1;
70         }
71         // d = -DotProduct(quadup, planenormal);
72         d = -(quadup[0] * planenormalx + quadup[1] * planenormaly + quadup[2] * planenormalz);
73         // VectorMA(quadup, d, planenormal, quadup);
74         quadup[0] += d * planenormalx;
75         quadup[1] += d * planenormaly;
76         quadup[2] += d * planenormalz;
77         // VectorNormalize(quadup);
78         d = 1.0 / sqrt(quadup[0] * quadup[0] + quadup[1] * quadup[1] + quadup[2] * quadup[2]);
79         quadup[0] *= d;
80         quadup[1] *= d;
81         quadup[2] *= d;
82         // CrossProduct(quadup,planenormal,quadright);
83         quadright[0] = quadup[1] * planenormalz - quadup[2] * planenormaly;
84         quadright[1] = quadup[2] * planenormalx - quadup[0] * planenormalz;
85         quadright[2] = quadup[0] * planenormaly - quadup[1] * planenormalx;
86         // make the points
87         outpoints[0] = planedist * planenormalx - quadsize * quadright[0] + quadsize * quadup[0];
88         outpoints[1] = planedist * planenormaly - quadsize * quadright[1] + quadsize * quadup[1];
89         outpoints[2] = planedist * planenormalz - quadsize * quadright[2] + quadsize * quadup[2];
90         outpoints[3] = planedist * planenormalx + quadsize * quadright[0] + quadsize * quadup[0];
91         outpoints[4] = planedist * planenormaly + quadsize * quadright[1] + quadsize * quadup[1];
92         outpoints[5] = planedist * planenormalz + quadsize * quadright[2] + quadsize * quadup[2];
93         outpoints[6] = planedist * planenormalx + quadsize * quadright[0] - quadsize * quadup[0];
94         outpoints[7] = planedist * planenormaly + quadsize * quadright[1] - quadsize * quadup[1];
95         outpoints[8] = planedist * planenormalz + quadsize * quadright[2] - quadsize * quadup[2];
96         outpoints[9] = planedist * planenormalx - quadsize * quadright[0] - quadsize * quadup[0];
97         outpoints[10] = planedist * planenormaly - quadsize * quadright[1] - quadsize * quadup[1];
98         outpoints[11] = planedist * planenormalz - quadsize * quadright[2] - quadsize * quadup[2];
99 }
100
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 }
140
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 }
180
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 }
246
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 }
312