major bsp bugs fixed

[dosdemo] / src / polyclip.c

diff --git a/src/polyclip.c b/src/polyclip.c
index 9ef8e95..67e1c83 100644 (file)
--- a/src/polyclip.c
+++ b/src/polyclip.c
@@ -1,3 +1,4 @@
+#include <stdio.h>
 #include <math.h>
 #include <assert.h>
 #include "polyclip.h"
@@ -10,21 +11,57 @@ struct ray {
 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 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;
 
        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, &out_vnum, vin + i, vin + nextidx, plane);
                if(res == 0) {
-                       edges_clipped++;
+                       ++edges_clipped;
+               }
+       }
+
+       if(out_vnum <= 0) {
+               assert(edges_clipped == 0);
+               return -1;
+       }
+
+       *voutnum = out_vnum;
+       return edges_clipped > 0 ? 0 : 1;
+}
+
+
+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;
+       int out_vnum = 0;
+
+       if(vnum == 1) {
+               /* special case: point clipping */
+               return inside_frustum_plane(vin, fplane) ? 1 : -1;
+       }
+
+       for(i=0; i<vnum; i++) {
+               nextidx = i + 1;
+               if(nextidx >= vnum) nextidx = 0;
+               res = clip_edge_frustum(vout, &out_vnum, vin + i, vin + nextidx, fplane);
+               if(res == 0) {
+                       ++edges_clipped;
                }
        }
 
@@ -106,9 +143,9 @@ static int clip_edge(struct g3d_vertex *poly, int *vnumptr,
 
                        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);
@@ -140,7 +177,7 @@ static int intersect(const struct ray *ray, const struct cplane *plane, float *t
        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;
        }
@@ -152,3 +189,105 @@ static int intersect(const struct ray *ray, const struct cplane *plane, float *t
        *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;
+}