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 static int inside_frustum_plane(const struct g3d_vertex *v, int fplane);
20 int clip_poly(struct g3d_vertex *vout, int *voutnum,
21 const struct g3d_vertex *vin, int vnum, struct cplane *plane)
24 int edges_clipped = 0;
27 for(i=0; i<vnum; i++) {
28 int res = clip_edge(vout, &out_vnum, vin + i, vin + (i + 1) % vnum, plane);
35 assert(edges_clipped == 0);
40 return edges_clipped > 0 ? 0 : 1;
44 int clip_frustum(struct g3d_vertex *vout, int *voutnum,
45 const struct g3d_vertex *vin, int vnum, int fplane)
48 int edges_clipped = 0;
52 /* special case: point clipping */
53 return inside_frustum_plane(vin, fplane) ? 1 : -1;
56 for(i=0; i<vnum; i++) {
57 int res = clip_edge_frustum(vout, &out_vnum, vin + i, vin + (i + 1) % vnum, fplane);
64 assert(edges_clipped == 0);
69 return edges_clipped > 0 ? 0 : 1;
72 #define LERP_VATTR(res, v0, v1, t) \
74 (res)->nx = (v0)->nx + ((v1)->nx - (v0)->nx) * (t); \
75 (res)->ny = (v0)->ny + ((v1)->ny - (v0)->ny) * (t); \
76 (res)->nz = (v0)->nz + ((v1)->nz - (v0)->nz) * (t); \
77 (res)->u = (v0)->u + ((v1)->u - (v0)->u) * (t); \
78 (res)->v = (v0)->v + ((v1)->v - (v0)->v) * (t); \
79 (res)->r = (v0)->r + ((v1)->r - (v0)->r) * (t); \
80 (res)->g = (v0)->g + ((v1)->g - (v0)->g) * (t); \
81 (res)->b = (v0)->b + ((v1)->b - (v0)->b) * (t); \
87 * 0 -> straddling and clipped
90 * also returns the size of the polygon through vnumptr
92 static int clip_edge(struct g3d_vertex *poly, int *vnumptr,
93 const struct g3d_vertex *v0, const struct g3d_vertex *v1,
94 const struct cplane *plane)
96 float pos0[3], pos1[3];
99 int i, vnum = *vnumptr;
101 pos0[0] = v0->x; pos0[1] = v0->y; pos0[2] = v0->z;
102 pos1[0] = v1->x; pos1[1] = v1->y; pos1[2] = v1->z;
104 d0 = distance_signed(pos0, plane);
105 d1 = distance_signed(pos1, plane);
108 ray.origin[i] = pos0[i];
109 ray.dir[i] = pos1[i] - pos0[i];
116 poly[vnum++] = *v1; /* append v1 */
121 struct g3d_vertex *vptr = poly + vnum;
123 intersect(&ray, plane, &t);
125 vptr->x = ray.origin[0] + ray.dir[0] * t;
126 vptr->y = ray.origin[1] + ray.dir[1] * t;
127 vptr->z = ray.origin[2] + ray.dir[2] * t;
130 LERP_VATTR(vptr, v0, v1, t);
131 vnum++; /* append new vertex on the intersection point */
137 struct g3d_vertex *vptr = poly + vnum;
139 intersect(&ray, plane, &t);
141 vptr->x = ray.origin[0] + ray.dir[0] + t;
142 vptr->y = ray.origin[1] + ray.dir[1] + t;
143 vptr->z = ray.origin[2] + ray.dir[2] + t;
146 LERP_VATTR(vptr, v0, v1, t);
147 vnum++; /* append new vertex on the intersection point */
149 /* then append v1 ... */
162 static float distance_signed(float *pos, const struct cplane *plane)
164 float dx = pos[0] - plane->x;
165 float dy = pos[1] - plane->y;
166 float dz = pos[2] - plane->z;
167 return dx * plane->nx + dy * plane->ny + dz * plane->nz;
170 static int intersect(const struct ray *ray, const struct cplane *plane, float *t)
172 float orig_pt_dir[3];
174 float ndotdir = plane->nx * ray->dir[0] + plane->ny * ray->dir[1] + plane->nz * ray->dir[2];
175 if(fabs(ndotdir) < 1e-4) {
180 orig_pt_dir[0] = plane->x - ray->origin[0];
181 orig_pt_dir[1] = plane->y - ray->origin[1];
182 orig_pt_dir[2] = plane->z - ray->origin[2];
184 *t = (plane->nx * orig_pt_dir[0] + plane->ny * orig_pt_dir[1] + plane->nz * orig_pt_dir[2]) / ndotdir;
188 /* homogeneous frustum clipper helpers */
190 static int inside_frustum_plane(const struct g3d_vertex *v, int fplane)
194 return v->x >= -v->w;
198 return v->y >= -v->w;
202 return v->z >= -v->w;
210 static float intersect_frustum(const struct g3d_vertex *a, const struct g3d_vertex *b, int fplane)
214 return (-a->w - a->x) / (b->x - a->x + b->w - a->w);
216 return (a->w - a->x) / (b->x - a->x - b->w + a->w);
218 return (-a->w - a->y) / (b->y - a->y + b->w - a->w);
220 return (a->w - a->y) / (b->y - a->y - b->w + a->w);
222 return (-a->w - a->z) / (b->z - a->z + b->w - a->w);
224 return (a->w - a->z) / (b->z - a->z - b->w + a->w);
231 static int clip_edge_frustum(struct g3d_vertex *poly, int *vnumptr,
232 const struct g3d_vertex *v0, const struct g3d_vertex *v1, int fplane)
238 in0 = inside_frustum_plane(v0, fplane);
239 in1 = inside_frustum_plane(v1, fplane);
245 poly[vnum++] = *v1; /* append v1 */
250 struct g3d_vertex *vptr = poly + vnum;
252 t = intersect_frustum(v0, v1, fplane);
254 vptr->x = v0->x + (v1->x - v0->x) * t;
255 vptr->y = v0->y + (v1->y - v0->y) * t;
256 vptr->z = v0->z + (v1->z - v0->z) * t;
257 vptr->w = v0->w + (v1->w - v0->w) * t;
259 LERP_VATTR(vptr, v0, v1, t);
260 ++vnum; /* append new vertex on the intersection point */
266 struct g3d_vertex *vptr = poly + vnum;
268 t = intersect_frustum(v0, v1, fplane);
270 vptr->x = v0->x + (v1->x - v0->x) * t;
271 vptr->y = v0->y + (v1->y - v0->y) * t;
272 vptr->z = v0->z + (v1->z - v0->z) * t;
273 vptr->w = v0->w + (v1->w - v0->w) * t;
275 LERP_VATTR(vptr, v0, v1, t);
276 ++vnum; /* append new vertex on the intersection point */
278 /* then append v1 ... */