+#include <stdio.h>
#include <math.h>
#include <assert.h>
#include "polyclip.h"
static int clip_edge(struct g3d_vertex *poly, int *vnumptr,
const struct g3d_vertex *v0, const struct g3d_vertex *v1,
const struct cplane *plane);
+static int check_clip_edge(const struct g3d_vertex *v0,
+ const struct g3d_vertex *v1, const struct cplane *plane);
+static int clip_edge_frustum(struct g3d_vertex *poly, int *vnumptr,
+ const struct g3d_vertex *v0, const struct g3d_vertex *v1, int fplane);
static float distance_signed(float *pos, const struct cplane *plane);
static int intersect(const struct ray *ray, const struct cplane *plane, float *t);
+static int inside_frustum_plane(const struct g3d_vertex *v, int fplane);
int clip_poly(struct g3d_vertex *vout, int *voutnum,
const struct g3d_vertex *vin, int vnum, struct cplane *plane)
{
- int i;
+ int i, nextidx, res;
int edges_clipped = 0;
- int out_vnum = 0;
+
+ *voutnum = 0;
for(i=0; i<vnum; i++) {
- int res = clip_edge(vout, &out_vnum, vin + i, vin + (i + 1) % vnum, plane);
+ nextidx = i + 1;
+ if(nextidx >= vnum) nextidx = 0;
+ res = clip_edge(vout, voutnum, vin + i, vin + nextidx, plane);
if(res == 0) {
- edges_clipped++;
+ ++edges_clipped;
}
}
- if(out_vnum <= 0) {
+ if(*voutnum <= 0) {
+ assert(edges_clipped == 0);
+ return -1;
+ }
+
+ return edges_clipped > 0 ? 0 : 1;
+}
+
+int check_clip_poly(const struct g3d_vertex *v, int vnum, struct cplane *plane)
+{
+ int i, nextidx, res;
+ int edges_clipped = 0;
+
+ for(i=0; i<vnum; i++) {
+ nextidx = i + 1;
+ if(nextidx >= vnum) nextidx = 0;
+ res = check_clip_edge(v + i, v + nextidx, plane);
+ if(res == 0) {
+ ++edges_clipped;
+ }
+ }
+ return edges_clipped ? 0 : res;
+}
+
+int clip_frustum(struct g3d_vertex *vout, int *voutnum,
+ const struct g3d_vertex *vin, int vnum, int fplane)
+{
+ int i, nextidx, res;
+ int edges_clipped = 0;
+
+ if(vnum == 1) {
+ /* special case: point clipping */
+ return inside_frustum_plane(vin, fplane) ? 1 : -1;
+ }
+
+ *voutnum = 0;
+
+ for(i=0; i<vnum; i++) {
+ nextidx = i + 1;
+ if(nextidx >= vnum) nextidx = 0;
+ res = clip_edge_frustum(vout, voutnum, vin + i, vin + nextidx, fplane);
+ if(res == 0) {
+ ++edges_clipped;
+ }
+ }
+
+ if(*voutnum <= 0) {
assert(edges_clipped == 0);
return -1;
}
- *voutnum = out_vnum;
return edges_clipped > 0 ? 0 : 1;
}
intersect(&ray, plane, &t);
- vptr->x = ray.origin[0] + ray.dir[0] + t;
- vptr->y = ray.origin[1] + ray.dir[1] + t;
- vptr->z = ray.origin[2] + ray.dir[2] + t;
+ vptr->x = ray.origin[0] + ray.dir[0] * t;
+ vptr->y = ray.origin[1] + ray.dir[1] * t;
+ vptr->z = ray.origin[2] + ray.dir[2] * t;
vptr->w = 1.0f;
LERP_VATTR(vptr, v0, v1, t);
return 0;
}
+/* same as above, but only checks for clipping and classifies the edge */
+static int check_clip_edge(const struct g3d_vertex *v0,
+ const struct g3d_vertex *v1, const struct cplane *plane)
+{
+ float pos0[3], pos1[3];
+ float d0, d1;
+
+ pos0[0] = v0->x; pos0[1] = v0->y; pos0[2] = v0->z;
+ pos1[0] = v1->x; pos1[1] = v1->y; pos1[2] = v1->z;
+
+ d0 = distance_signed(pos0, plane);
+ d1 = distance_signed(pos1, plane);
+
+ if(d0 > 0.0f && d1 > 0.0f) {
+ return 1;
+ }
+ if(d0 < 0.0f && d1 < 0.0f) {
+ return -1;
+ }
+ return 0;
+}
static float distance_signed(float *pos, const struct cplane *plane)
{
float orig_pt_dir[3];
float ndotdir = plane->nx * ray->dir[0] + plane->ny * ray->dir[1] + plane->nz * ray->dir[2];
- if(fabs(ndotdir) < 1e-4) {
+ if(fabs(ndotdir) < 1e-6) {
*t = 0.0f;
return 0;
}
*t = (plane->nx * orig_pt_dir[0] + plane->ny * orig_pt_dir[1] + plane->nz * orig_pt_dir[2]) / ndotdir;
return 1;
}
+
+/* homogeneous frustum clipper helpers */
+
+static int inside_frustum_plane(const struct g3d_vertex *v, int fplane)
+{
+ switch(fplane) {
+ case CLIP_LEFT:
+ return v->x >= -v->w;
+ case CLIP_RIGHT:
+ return v->x <= v->w;
+ case CLIP_BOTTOM:
+ return v->y >= -v->w;
+ case CLIP_TOP:
+ return v->y <= v->w;
+ case CLIP_NEAR:
+ return v->z >= -v->w;
+ case CLIP_FAR:
+ return v->z <= v->w;
+ }
+ assert(0);
+ return 0;
+}
+
+static float intersect_frustum(const struct g3d_vertex *a, const struct g3d_vertex *b, int fplane)
+{
+ switch(fplane) {
+ case CLIP_LEFT:
+ return (-a->w - a->x) / (b->x - a->x + b->w - a->w);
+ case CLIP_RIGHT:
+ return (a->w - a->x) / (b->x - a->x - b->w + a->w);
+ case CLIP_BOTTOM:
+ return (-a->w - a->y) / (b->y - a->y + b->w - a->w);
+ case CLIP_TOP:
+ return (a->w - a->y) / (b->y - a->y - b->w + a->w);
+ case CLIP_NEAR:
+ return (-a->w - a->z) / (b->z - a->z + b->w - a->w);
+ case CLIP_FAR:
+ return (a->w - a->z) / (b->z - a->z - b->w + a->w);
+ }
+
+ assert(0);
+ return 0;
+}
+
+static int clip_edge_frustum(struct g3d_vertex *poly, int *vnumptr,
+ const struct g3d_vertex *v0, const struct g3d_vertex *v1, int fplane)
+{
+ int vnum = *vnumptr;
+ int in0, in1;
+ float t;
+
+ in0 = inside_frustum_plane(v0, fplane);
+ in1 = inside_frustum_plane(v1, fplane);
+
+ if(in0) {
+ /* start inside */
+ if(in1) {
+ /* all inside */
+ poly[vnum++] = *v1; /* append v1 */
+ *vnumptr = vnum;
+ return 1;
+ } else {
+ /* going out */
+ struct g3d_vertex *vptr = poly + vnum;
+
+ t = intersect_frustum(v0, v1, fplane);
+
+ vptr->x = v0->x + (v1->x - v0->x) * t;
+ vptr->y = v0->y + (v1->y - v0->y) * t;
+ vptr->z = v0->z + (v1->z - v0->z) * t;
+ vptr->w = v0->w + (v1->w - v0->w) * t;
+
+ LERP_VATTR(vptr, v0, v1, t);
+ ++vnum; /* append new vertex on the intersection point */
+ }
+ } else {
+ /* start outside */
+ if(in1) {
+ /* going in */
+ struct g3d_vertex *vptr = poly + vnum;
+
+ t = intersect_frustum(v0, v1, fplane);
+
+ vptr->x = v0->x + (v1->x - v0->x) * t;
+ vptr->y = v0->y + (v1->y - v0->y) * t;
+ vptr->z = v0->z + (v1->z - v0->z) * t;
+ vptr->w = v0->w + (v1->w - v0->w) * t;
+
+ LERP_VATTR(vptr, v0, v1, t);
+ ++vnum; /* append new vertex on the intersection point */
+
+ /* then append v1 ... */
+ poly[vnum++] = *v1;
+ } else {
+ /* all outside */
+ return -1;
+ }
+ }
+
+ *vnumptr = vnum;
+ return 0;
+}