11 static int clip_edge(struct g3d_vertex *poly, int *vnumptr,
12 const struct g3d_vertex *v0, const struct g3d_vertex *v1,
13 const struct cplane *plane);
14 static int check_clip_edge(const struct g3d_vertex *v0,
15 const struct g3d_vertex *v1, const struct cplane *plane);
16 static int clip_edge_frustum(struct g3d_vertex *poly, int *vnumptr,
17 const struct g3d_vertex *v0, const struct g3d_vertex *v1, int fplane);
18 static float distance_signed(float *pos, const struct cplane *plane);
19 static int intersect(const struct ray *ray, const struct cplane *plane, float *t);
20 static int inside_frustum_plane(const struct g3d_vertex *v, int fplane);
23 int clip_poly(struct g3d_vertex *vout, int *voutnum,
24 const struct g3d_vertex *vin, int vnum, struct cplane *plane)
27 int edges_clipped = 0;
31 for(i=0; i<vnum; i++) {
33 if(nextidx >= vnum) nextidx = 0;
34 res = clip_edge(vout, voutnum, vin + i, vin + nextidx, plane);
41 assert(edges_clipped == 0);
45 return edges_clipped > 0 ? 0 : 1;
48 int check_clip_poly(const struct g3d_vertex *v, int vnum, struct cplane *plane)
50 int i, nextidx, res = 0;
51 int edges_clipped = 0;
53 for(i=0; i<vnum; i++) {
55 if(nextidx >= vnum) nextidx = 0;
56 res = check_clip_edge(v + i, v + nextidx, plane);
61 return edges_clipped ? 0 : res;
64 int clip_frustum(struct g3d_vertex *vout, int *voutnum,
65 const struct g3d_vertex *vin, int vnum, int fplane)
68 int edges_clipped = 0;
71 /* special case: point clipping */
72 return inside_frustum_plane(vin, fplane) ? 1 : -1;
77 for(i=0; i<vnum; i++) {
79 if(nextidx >= vnum) nextidx = 0;
80 res = clip_edge_frustum(vout, voutnum, vin + i, vin + nextidx, fplane);
87 assert(edges_clipped == 0);
91 return edges_clipped > 0 ? 0 : 1;
94 #define LERP_VATTR(res, v0, v1, t) \
96 (res)->nx = (v0)->nx + ((v1)->nx - (v0)->nx) * (t); \
97 (res)->ny = (v0)->ny + ((v1)->ny - (v0)->ny) * (t); \
98 (res)->nz = (v0)->nz + ((v1)->nz - (v0)->nz) * (t); \
99 (res)->u = (v0)->u + ((v1)->u - (v0)->u) * (t); \
100 (res)->v = (v0)->v + ((v1)->v - (v0)->v) * (t); \
101 (res)->l = (v0)->l + ((v1)->l - (v0)->l) * (t); \
102 (res)->a = (v0)->a + ((v1)->a - (v0)->a) * (t); \
108 * 0 -> straddling and clipped
111 * also returns the size of the polygon through vnumptr
113 static int clip_edge(struct g3d_vertex *poly, int *vnumptr,
114 const struct g3d_vertex *v0, const struct g3d_vertex *v1,
115 const struct cplane *plane)
117 float pos0[3], pos1[3];
120 int i, vnum = *vnumptr;
122 pos0[0] = v0->x; pos0[1] = v0->y; pos0[2] = v0->z;
123 pos1[0] = v1->x; pos1[1] = v1->y; pos1[2] = v1->z;
125 d0 = distance_signed(pos0, plane);
126 d1 = distance_signed(pos1, plane);
129 ray.origin[i] = pos0[i];
130 ray.dir[i] = pos1[i] - pos0[i];
137 poly[vnum++] = *v1; /* append v1 */
142 struct g3d_vertex *vptr = poly + vnum;
144 intersect(&ray, plane, &t);
146 vptr->x = ray.origin[0] + ray.dir[0] * t;
147 vptr->y = ray.origin[1] + ray.dir[1] * t;
148 vptr->z = ray.origin[2] + ray.dir[2] * t;
151 LERP_VATTR(vptr, v0, v1, t);
152 vnum++; /* append new vertex on the intersection point */
158 struct g3d_vertex *vptr = poly + vnum;
160 intersect(&ray, plane, &t);
162 vptr->x = ray.origin[0] + ray.dir[0] * t;
163 vptr->y = ray.origin[1] + ray.dir[1] * t;
164 vptr->z = ray.origin[2] + ray.dir[2] * t;
167 LERP_VATTR(vptr, v0, v1, t);
168 vnum++; /* append new vertex on the intersection point */
170 /* then append v1 ... */
182 /* same as above, but only checks for clipping and classifies the edge */
183 static int check_clip_edge(const struct g3d_vertex *v0,
184 const struct g3d_vertex *v1, const struct cplane *plane)
186 float pos0[3], pos1[3];
189 pos0[0] = v0->x; pos0[1] = v0->y; pos0[2] = v0->z;
190 pos1[0] = v1->x; pos1[1] = v1->y; pos1[2] = v1->z;
192 d0 = distance_signed(pos0, plane);
193 d1 = distance_signed(pos1, plane);
195 if(d0 > 0.0f && d1 > 0.0f) {
198 if(d0 < 0.0f && d1 < 0.0f) {
204 static float distance_signed(float *pos, const struct cplane *plane)
206 float dx = pos[0] - plane->x;
207 float dy = pos[1] - plane->y;
208 float dz = pos[2] - plane->z;
209 return dx * plane->nx + dy * plane->ny + dz * plane->nz;
212 static int intersect(const struct ray *ray, const struct cplane *plane, float *t)
214 float orig_pt_dir[3];
216 float ndotdir = plane->nx * ray->dir[0] + plane->ny * ray->dir[1] + plane->nz * ray->dir[2];
217 if(fabs(ndotdir) < 1e-6) {
222 orig_pt_dir[0] = plane->x - ray->origin[0];
223 orig_pt_dir[1] = plane->y - ray->origin[1];
224 orig_pt_dir[2] = plane->z - ray->origin[2];
226 *t = (plane->nx * orig_pt_dir[0] + plane->ny * orig_pt_dir[1] + plane->nz * orig_pt_dir[2]) / ndotdir;
230 /* homogeneous frustum clipper helpers */
232 static int inside_frustum_plane(const struct g3d_vertex *v, int fplane)
236 return v->x >= -v->w;
240 return v->y >= -v->w;
244 return v->z >= -v->w;
252 static float intersect_frustum(const struct g3d_vertex *a, const struct g3d_vertex *b, int fplane)
256 return (-a->w - a->x) / (b->x - a->x + b->w - a->w);
258 return (a->w - a->x) / (b->x - a->x - b->w + a->w);
260 return (-a->w - a->y) / (b->y - a->y + b->w - a->w);
262 return (a->w - a->y) / (b->y - a->y - b->w + a->w);
264 return (-a->w - a->z) / (b->z - a->z + b->w - a->w);
266 return (a->w - a->z) / (b->z - a->z - b->w + a->w);
273 static int clip_edge_frustum(struct g3d_vertex *poly, int *vnumptr,
274 const struct g3d_vertex *v0, const struct g3d_vertex *v1, int fplane)
280 in0 = inside_frustum_plane(v0, fplane);
281 in1 = inside_frustum_plane(v1, fplane);
287 poly[vnum++] = *v1; /* append v1 */
292 struct g3d_vertex *vptr = poly + vnum;
294 t = intersect_frustum(v0, v1, fplane);
296 vptr->x = v0->x + (v1->x - v0->x) * t;
297 vptr->y = v0->y + (v1->y - v0->y) * t;
298 vptr->z = v0->z + (v1->z - v0->z) * t;
299 vptr->w = v0->w + (v1->w - v0->w) * t;
301 LERP_VATTR(vptr, v0, v1, t);
302 ++vnum; /* append new vertex on the intersection point */
308 struct g3d_vertex *vptr = poly + vnum;
310 t = intersect_frustum(v0, v1, fplane);
312 vptr->x = v0->x + (v1->x - v0->x) * t;
313 vptr->y = v0->y + (v1->y - v0->y) * t;
314 vptr->z = v0->z + (v1->z - v0->z) * t;
315 vptr->w = v0->w + (v1->w - v0->w) * t;
317 LERP_VATTR(vptr, v0, v1, t);
318 ++vnum; /* append new vertex on the intersection point */
320 /* then append v1 ... */