f5ef9c79b2013eed40027fd9b762ea843f376a5f
[dosdemo] / src / polyclip.c
1 #include <math.h>
2 #include <assert.h>
3 #include "polyclip.h"
4
5 struct ray {
6         float origin[3];
7         float dir[3];
8 };
9
10 static int clip_edge(struct g3d_vertex *poly, int *vnumptr,
11                 const struct g3d_vertex *v0, const struct g3d_vertex *v1,
12                 const struct cplane *plane);
13 static int clip_edge_frustum(struct g3d_vertex *poly, int *vnumptr,
14                 const struct g3d_vertex *v0, const struct g3d_vertex *v1, int fplane);
15 static float distance_signed(float *pos, const struct cplane *plane);
16 static int intersect(const struct ray *ray, const struct cplane *plane, float *t);
17
18
19 int clip_poly(struct g3d_vertex *vout, int *voutnum,
20                 const struct g3d_vertex *vin, int vnum, struct cplane *plane)
21 {
22         int i;
23         int edges_clipped = 0;
24         int out_vnum = 0;
25
26         for(i=0; i<vnum; i++) {
27                 int res = clip_edge(vout, &out_vnum, vin + i, vin + (i + 1) % vnum, plane);
28                 if(res == 0) {
29                         ++edges_clipped;
30                 }
31         }
32
33         if(out_vnum <= 0) {
34                 assert(edges_clipped == 0);
35                 return -1;
36         }
37
38         *voutnum = out_vnum;
39         return edges_clipped > 0 ? 0 : 1;
40 }
41
42
43 int clip_frustum(struct g3d_vertex *vout, int *voutnum,
44                 const struct g3d_vertex *vin, int vnum, int fplane)
45 {
46         int i;
47         int edges_clipped = 0;
48         int out_vnum = 0;
49
50         for(i=0; i<vnum; i++) {
51                 int res = clip_edge_frustum(vout, &out_vnum, vin + i, vin + (i + 1) % vnum, fplane);
52                 if(res == 0) {
53                         ++edges_clipped;
54                 }
55         }
56
57         if(out_vnum <= 0) {
58                 assert(edges_clipped == 0);
59                 return -1;
60         }
61
62         *voutnum = out_vnum;
63         return edges_clipped > 0 ? 0 : 1;
64 }
65
66 #define LERP_VATTR(res, v0, v1, t) \
67         do { \
68                 (res)->nx = (v0)->nx + ((v1)->nx - (v0)->nx) * (t); \
69                 (res)->ny = (v0)->ny + ((v1)->ny - (v0)->ny) * (t); \
70                 (res)->nz = (v0)->nz + ((v1)->nz - (v0)->nz) * (t); \
71                 (res)->u = (v0)->u + ((v1)->u - (v0)->u) * (t); \
72                 (res)->v = (v0)->v + ((v1)->v - (v0)->v) * (t); \
73                 (res)->r = (v0)->r + ((v1)->r - (v0)->r) * (t); \
74                 (res)->g = (v0)->g + ((v1)->g - (v0)->g) * (t); \
75                 (res)->b = (v0)->b + ((v1)->b - (v0)->b) * (t); \
76         } while(0)
77
78
79 /* returns:
80  *  1 -> both inside
81  *  0 -> straddling and clipped
82  * -1 -> both outside
83  *
84  *  also returns the size of the polygon through vnumptr
85  */
86 static int clip_edge(struct g3d_vertex *poly, int *vnumptr,
87                 const struct g3d_vertex *v0, const struct g3d_vertex *v1,
88                 const struct cplane *plane)
89 {
90         float pos0[3], pos1[3];
91         float d0, d1, t;
92         struct ray ray;
93         int i, vnum = *vnumptr;
94
95         pos0[0] = v0->x; pos0[1] = v0->y; pos0[2] = v0->z;
96         pos1[0] = v1->x; pos1[1] = v1->y; pos1[2] = v1->z;
97
98         d0 = distance_signed(pos0, plane);
99         d1 = distance_signed(pos1, plane);
100
101         for(i=0; i<3; i++) {
102                 ray.origin[i] = pos0[i];
103                 ray.dir[i] = pos1[i] - pos0[i];
104         }
105
106         if(d0 >= 0.0) {
107                 /* start inside */
108                 if(d1 >= 0.0) {
109                         /* all inside */
110                         poly[vnum++] = *v1;     /* append v1 */
111                         *vnumptr = vnum;
112                         return 1;
113                 } else {
114                         /* going out */
115                         struct g3d_vertex *vptr = poly + vnum;
116
117                         intersect(&ray, plane, &t);
118
119                         vptr->x = ray.origin[0] + ray.dir[0] * t;
120                         vptr->y = ray.origin[1] + ray.dir[1] * t;
121                         vptr->z = ray.origin[2] + ray.dir[2] * t;
122                         vptr->w = 1.0f;
123
124                         LERP_VATTR(vptr, v0, v1, t);
125                         vnum++; /* append new vertex on the intersection point */
126                 }
127         } else {
128                 /* start outside */
129                 if(d1 >= 0) {
130                         /* going in */
131                         struct g3d_vertex *vptr = poly + vnum;
132
133                         intersect(&ray, plane, &t);
134
135                         vptr->x = ray.origin[0] + ray.dir[0] + t;
136                         vptr->y = ray.origin[1] + ray.dir[1] + t;
137                         vptr->z = ray.origin[2] + ray.dir[2] + t;
138                         vptr->w = 1.0f;
139
140                         LERP_VATTR(vptr, v0, v1, t);
141                         vnum++; /* append new vertex on the intersection point */
142
143                         /* then append v1 ... */
144                         poly[vnum++] = *v1;
145                 } else {
146                         /* all outside */
147                         return -1;
148                 }
149         }
150
151         *vnumptr = vnum;
152         return 0;
153 }
154
155
156 static float distance_signed(float *pos, const struct cplane *plane)
157 {
158         float dx = pos[0] - plane->x;
159         float dy = pos[1] - plane->y;
160         float dz = pos[2] - plane->z;
161         return dx * plane->nx + dy * plane->ny + dz * plane->nz;
162 }
163
164 static int intersect(const struct ray *ray, const struct cplane *plane, float *t)
165 {
166         float orig_pt_dir[3];
167
168         float ndotdir = plane->nx * ray->dir[0] + plane->ny * ray->dir[1] + plane->nz * ray->dir[2];
169         if(fabs(ndotdir) < 1e-4) {
170                 *t = 0.0f;
171                 return 0;
172         }
173
174         orig_pt_dir[0] = plane->x - ray->origin[0];
175         orig_pt_dir[1] = plane->y - ray->origin[1];
176         orig_pt_dir[2] = plane->z - ray->origin[2];
177
178         *t = (plane->nx * orig_pt_dir[0] + plane->ny * orig_pt_dir[1] + plane->nz * orig_pt_dir[2]) / ndotdir;
179         return 1;
180 }
181
182 /* homogeneous frustum clipper helpers */
183
184 static int inside_frustum_plane(const struct g3d_vertex *v, int fplane)
185 {
186         switch(fplane) {
187         case CLIP_LEFT:
188                 return v->x >= -v->w;
189         case CLIP_RIGHT:
190                 return v->x <= v->w;
191         case CLIP_BOTTOM:
192                 return v->y >= -v->w;
193         case CLIP_TOP:
194                 return v->y <= v->w;
195         case CLIP_NEAR:
196                 return v->z >= -v->w;
197         case CLIP_FAR:
198                 return v->z <= v->w;
199         }
200         assert(0);
201         return 0;
202 }
203
204 static float intersect_frustum(const struct g3d_vertex *a, const struct g3d_vertex *b, int fplane)
205 {
206         switch(fplane) {
207         case CLIP_LEFT:
208                 return (-a->w - a->x) / (b->x - a->x + b->w - a->w);
209         case CLIP_RIGHT:
210                 return (a->w - a->x) / (b->x - a->x - b->w + a->w);
211         case CLIP_BOTTOM:
212                 return (-a->w - a->y) / (b->y - a->y + b->w - a->w);
213         case CLIP_TOP:
214                 return (a->w - a->y) / (b->y - a->y - b->w + a->w);
215         case CLIP_NEAR:
216                 return (-a->w - a->z) / (b->z - a->z + b->w - a->w);
217         case CLIP_FAR:
218                 return (a->w - a->z) / (b->z - a->z - b->w + a->w);
219         }
220
221         assert(0);
222         return 0;
223 }
224
225 static int clip_edge_frustum(struct g3d_vertex *poly, int *vnumptr,
226                 const struct g3d_vertex *v0, const struct g3d_vertex *v1, int fplane)
227 {
228         int vnum = *vnumptr;
229         int in0, in1;
230         float t;
231
232         in0 = inside_frustum_plane(v0, fplane);
233         in1 = inside_frustum_plane(v1, fplane);
234
235         if(in0) {
236                 /* start inside */
237                 if(in1) {
238                         /* all inside */
239                         poly[vnum++] = *v1;     /* append v1 */
240                         *vnumptr = vnum;
241                         return 1;
242                 } else {
243                         /* going out */
244                         struct g3d_vertex *vptr = poly + vnum;
245
246                         t = intersect_frustum(v0, v1, fplane);
247
248                         vptr->x = v0->x + (v1->x - v0->x) * t;
249                         vptr->y = v0->y + (v1->y - v0->y) * t;
250                         vptr->z = v0->z + (v1->z - v0->z) * t;
251                         vptr->w = v0->w + (v1->w - v0->w) * t;
252
253                         LERP_VATTR(vptr, v0, v1, t);
254                         ++vnum; /* append new vertex on the intersection point */
255                 }
256         } else {
257                 /* start outside */
258                 if(in1) {
259                         /* going in */
260                         struct g3d_vertex *vptr = poly + vnum;
261
262                         t = intersect_frustum(v0, v1, fplane);
263
264                         vptr->x = v0->x + (v1->x - v0->x) * t;
265                         vptr->y = v0->y + (v1->y - v0->y) * t;
266                         vptr->z = v0->z + (v1->z - v0->z) * t;
267                         vptr->w = v0->w + (v1->w - v0->w) * t;
268
269                         LERP_VATTR(vptr, v0, v1, t);
270                         ++vnum; /* append new vertex on the intersection point */
271
272                         /* then append v1 ... */
273                         poly[vnum++] = *v1;
274                 } else {
275                         /* all outside */
276                         return -1;
277                 }
278         }
279
280         *vnumptr = vnum;
281         return 0;
282 }