move two #defined to quakedef.h, and always include quakedef.h first before any other...
[xonotic/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 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)
102 {
103         int i, frontcount = 0, backcount = 0, oncount = 0;
104         const float *n, *p;
105         double frac, pdist, ndist;
106         for (i = 0;i < innumpoints;i++)
107         {
108                 p = inpoints + i * 3;
109                 n = inpoints + ((i + 1) < innumpoints ? (i + 1) : 0) * 3;
110                 pdist = p[0] * planenormalx + p[1] * planenormaly + p[2] * planenormalz - planedist;
111                 ndist = n[0] * planenormalx + n[1] * planenormaly + n[2] * planenormalz - planedist;
112                 if (pdist >= -epsilon)
113                 {
114                         if (pdist <= epsilon)
115                                 oncount++;
116                         if (frontcount < outfrontmaxpoints)
117                         {
118                                 *outfrontpoints++ = p[0];
119                                 *outfrontpoints++ = p[1];
120                                 *outfrontpoints++ = p[2];
121                         }
122                         frontcount++;
123                 }
124                 if (pdist <= epsilon)
125                 {
126                         if (backcount < outbackmaxpoints)
127                         {
128                                 *outbackpoints++ = p[0];
129                                 *outbackpoints++ = p[1];
130                                 *outbackpoints++ = p[2];
131                         }
132                         backcount++;
133                 }
134                 if ((pdist > epsilon && ndist < -epsilon) || (pdist < -epsilon && ndist > epsilon))
135                 {
136                         oncount++;
137                         frac = pdist / (pdist - ndist);
138                         if (frontcount < outfrontmaxpoints)
139                         {
140                                 *outfrontpoints++ = (float)(p[0] + frac * (n[0] - p[0]));
141                                 *outfrontpoints++ = (float)(p[1] + frac * (n[1] - p[1]));
142                                 *outfrontpoints++ = (float)(p[2] + frac * (n[2] - p[2]));
143                         }
144                         frontcount++;
145                         if (backcount < outbackmaxpoints)
146                         {
147                                 *outbackpoints++ = (float)(p[0] + frac * (n[0] - p[0]));
148                                 *outbackpoints++ = (float)(p[1] + frac * (n[1] - p[1]));
149                                 *outbackpoints++ = (float)(p[2] + frac * (n[2] - p[2]));
150                         }
151                         backcount++;
152                 }
153         }
154         if (neededfrontpoints)
155                 *neededfrontpoints = frontcount;
156         if (neededbackpoints)
157                 *neededbackpoints = backcount;
158         if (oncountpointer)
159                 *oncountpointer = oncount;
160 }
161
162 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)
163 {
164         int i, frontcount = 0, backcount = 0, oncount = 0;
165         const double *n, *p;
166         double frac, pdist, ndist;
167         for (i = 0;i < innumpoints;i++)
168         {
169                 p = inpoints + i * 3;
170                 n = inpoints + ((i + 1) < innumpoints ? (i + 1) : 0) * 3;
171                 pdist = p[0] * planenormalx + p[1] * planenormaly + p[2] * planenormalz - planedist;
172                 ndist = n[0] * planenormalx + n[1] * planenormaly + n[2] * planenormalz - planedist;
173                 if (pdist >= -epsilon)
174                 {
175                         if (pdist <= epsilon)
176                                 oncount++;
177                         if (frontcount < outfrontmaxpoints)
178                         {
179                                 *outfrontpoints++ = p[0];
180                                 *outfrontpoints++ = p[1];
181                                 *outfrontpoints++ = p[2];
182                         }
183                         frontcount++;
184                 }
185                 if (pdist <= epsilon)
186                 {
187                         if (backcount < outbackmaxpoints)
188                         {
189                                 *outbackpoints++ = p[0];
190                                 *outbackpoints++ = p[1];
191                                 *outbackpoints++ = p[2];
192                         }
193                         backcount++;
194                 }
195                 if ((pdist > epsilon && ndist < -epsilon) || (pdist < -epsilon && ndist > epsilon))
196                 {
197                         oncount++;
198                         frac = pdist / (pdist - ndist);
199                         if (frontcount < outfrontmaxpoints)
200                         {
201                                 *outfrontpoints++ = p[0] + frac * (n[0] - p[0]);
202                                 *outfrontpoints++ = p[1] + frac * (n[1] - p[1]);
203                                 *outfrontpoints++ = p[2] + frac * (n[2] - p[2]);
204                         }
205                         frontcount++;
206                         if (backcount < outbackmaxpoints)
207                         {
208                                 *outbackpoints++ = p[0] + frac * (n[0] - p[0]);
209                                 *outbackpoints++ = p[1] + frac * (n[1] - p[1]);
210                                 *outbackpoints++ = p[2] + frac * (n[2] - p[2]);
211                         }
212                         backcount++;
213                 }
214         }
215         if (neededfrontpoints)
216                 *neededfrontpoints = frontcount;
217         if (neededbackpoints)
218                 *neededbackpoints = backcount;
219         if (oncountpointer)
220                 *oncountpointer = oncount;
221 }
222