1.1 --- a/src/scene.cc	Sun Sep 12 00:19:04 2010 +0100
     1.2 +++ b/src/scene.cc	Sun Sep 12 07:27:12 2010 +0100
     1.3 @@ -1,10 +1,12 @@
     1.4  #include <stdlib.h>
     1.5 +#include <string.h>
     1.6  #include <math.h>
     1.7  #include <float.h>
     1.8  #include <assert.h>
     1.9  #include <map>
    1.10  #include "scene.h"
    1.11  #include "ogl.h"
    1.12 +#include "vector.h"
    1.13  
    1.14  #define CHECK_AABB(aabb)	\
    1.15  	assert(aabb.max[0] >= aabb.min[0] && aabb.max[1] >= aabb.min[1] && aabb.max[2] >= aabb.min[2])
    1.16 @@ -20,7 +22,8 @@
    1.17  static float eval_cost(const Face *faces, const int *face_idx, int num_faces, const AABBox &aabb, int axis);
    1.18  static void free_kdtree(KDNode *node);
    1.19  static void print_item_counts(const KDNode *node, int level);
    1.20 -static int split_face(const Face *inface, int axis, Face *face1, Face *face2);
    1.21 +static int clip_face(const Face &inface, float splitpos, int axis, int sign, Face *faces);
    1.22 +static float calc_sq_area(const Vector3 &a, const Vector3 &b, const Vector3 &c);
    1.23  
    1.24  
    1.25  static int accel_param[NUM_ACCEL_PARAMS] = {
    1.26 @@ -38,25 +41,6 @@
    1.27  }
    1.28  
    1.29  
    1.30 -#define FEQ(a, b)	(fabs((a) - (b)) < 1e-8)
    1.31 -bool Face::operator ==(const Face &f) const
    1.32 -{
    1.33 -	for(int i=0; i<3; i++) {
    1.34 -		for(int j=0; j<3; j++) {
    1.35 -			if(!FEQ(v[i].pos[j], f.v[i].pos[j])) {
    1.36 -				return false;
    1.37 -			}
    1.38 -			if(!FEQ(v[i].normal[j], f.v[i].normal[j])) {
    1.39 -				return false;
    1.40 -			}
    1.41 -		}
    1.42 -		if(!FEQ(normal[i], f.normal[i])) {
    1.43 -			return false;
    1.44 -		}
    1.45 -	}
    1.46 -	return true;
    1.47 -}
    1.48 -
    1.49  float AABBox::calc_surface_area() const
    1.50  {
    1.51  	float area1 = (max[0] - min[0]) * (max[1] - min[1]);
    1.52 @@ -590,31 +574,122 @@
    1.53  	print_item_counts(node->left, level + 1);
    1.54  	print_item_counts(node->right, level + 1);
    1.55  }
    1.56 -/*
    1.57 -#define SWAP(a, b, type)	\
    1.58 +
    1.59 +#define SGN(x)		((x) >= 0 ? 1 : -1)
    1.60 +#define INSIDE(x)	(SGN((x) - (splitpos)) == sign)
    1.61 +#define OUTSIDE(x)	(!INSIDE(x))
    1.62 +
    1.63 +#define LERPV3(res, a, b, t) \
    1.64  	do { \
    1.65 -		type tmp = a; \
    1.66 -		a = b; \
    1.67 -		b = tmp; \
    1.68 +		(res)[0] = (a)[0] + ((b)[0] - (a)[0]) * (t); \
    1.69 +		(res)[1] = (a)[1] + ((b)[1] - (a)[1]) * (t); \
    1.70 +		(res)[2] = (a)[2] + ((b)[2] - (a)[2]) * (t); \
    1.71  	} while(0)
    1.72  
    1.73 -static bool clip_face(const Face *inface, float splitpos, int axis, Face *face1, Face *face2)
    1.74 +#define NORMALIZE(v)	\
    1.75 +	do { \
    1.76 +		float mag = (float)sqrt((v)[0] * (v)[0] + (v)[1] * (v)[1] + (v)[2] * (v)[2]); \
    1.77 +		(v)[0] /= mag; \
    1.78 +		(v)[1] /= mag; \
    1.79 +		(v)[2] /= mag; \
    1.80 +	} while(0)
    1.81 +
    1.82 +static int clip_face(const Face &inface, float splitpos, int axis, int sign, Face *faces)
    1.83  {
    1.84 -	assert(inface && face1 && face2);
    1.85 -	assert(inface != face1 && inface != face2);
    1.86  	assert(axis >= 0 && axis < 3);
    1.87  
    1.88  	std::vector<Vertex> verts;
    1.89 +	bool clipped = false;
    1.90  
    1.91 -	// find the edges that must be split
    1.92  	for(int i=0; i<3; i++) {
    1.93 -		verts.push_back(inface->v[i]);
    1.94 +		const Vertex *vstart = inface.v + i;
    1.95 +		const Vertex *vend = inface.v + ((i + 1) % 3);
    1.96  
    1.97 -		float start = inface->v[i].pos[axis];
    1.98 -		float end = inface->v[(i + 1) % 3].pos[axis];
    1.99 +		float start = vstart->pos[axis];
   1.100 +		float end = vend->pos[axis];
   1.101  
   1.102 -		if((splitpos >= start && splitpos < end) || (splitpos >= end && splitpos < start)) {
   1.103 +		if(OUTSIDE(start) && INSIDE(end)) {
   1.104 +			float t = (splitpos - start) / (end - start);
   1.105  
   1.106 +			Vertex newv;
   1.107 +			memset(&newv, 0, sizeof newv);
   1.108 +			LERPV3(newv.pos, vstart->pos, vend->pos, t);
   1.109 +			LERPV3(newv.normal, vstart->normal, vend->normal, t);
   1.110 +			LERPV3(newv.tex, vstart->tex, vend->tex, t);
   1.111 +			NORMALIZE(newv.normal);
   1.112 +
   1.113 +			verts.push_back(newv);
   1.114 +			clipped = true;
   1.115 +
   1.116 +		} else if(INSIDE(start) && INSIDE(end)) {
   1.117 +			verts.push_back(inface.v[i]);
   1.118 +		} else if(INSIDE(start) && OUTSIDE(end)) {
   1.119 +			verts.push_back(inface.v[i]);
   1.120 +
   1.121 +			float t = (splitpos - start) / (end - start);
   1.122 +
   1.123 +			Vertex newv;
   1.124 +			memset(&newv, 0, sizeof newv);
   1.125 +			LERPV3(newv.pos, vstart->pos, vend->pos, t);
   1.126 +			LERPV3(newv.normal, vstart->normal, vend->normal, t);
   1.127 +			LERPV3(newv.tex, vstart->tex, vend->tex, t);
   1.128 +			NORMALIZE(newv.normal);
   1.129 +
   1.130 +			verts.push_back(newv);
   1.131 +			clipped = true;
   1.132  		}
   1.133  	}
   1.134 -}*/
   1.135 +
   1.136 +	if(!clipped) {
   1.137 +		return 0;
   1.138 +	}
   1.139 +
   1.140 +	assert(verts.size() < 5);
   1.141 +	bool quad = verts.size() > 3;
   1.142 +
   1.143 +	if(!quad) {
   1.144 +		faces[0] = inface;
   1.145 +		faces[0].v[0] = verts[0];
   1.146 +		faces[0].v[1] = verts[1];
   1.147 +		faces[0].v[2] = verts[2];
   1.148 +		return 1;
   1.149 +	}
   1.150 +
   1.151 +	/* calculate triangle areas for both possible splits and pick the one
   1.152 +	 * with the smallest absolute difference to avoid slivers.
   1.153 +	 */
   1.154 +	float area1, area2;
   1.155 +
   1.156 +	area1 = calc_sq_area(verts[0].pos, verts[1].pos, verts[2].pos);
   1.157 +	area2 = calc_sq_area(verts[0].pos, verts[2].pos, verts[3].pos);
   1.158 +	float s1diff = fabs(area1 - area2);
   1.159 +
   1.160 +	area1 = calc_sq_area(verts[0].pos, verts[1].pos, verts[3].pos);
   1.161 +	area2 = calc_sq_area(verts[1].pos, verts[2].pos, verts[3].pos);
   1.162 +	float s2diff = fabs(area1 - area2);
   1.163 +
   1.164 +	faces[0] = faces[1] = inface;
   1.165 +	if(s1diff < s2diff) {
   1.166 +		faces[0].v[0] = verts[0];
   1.167 +		faces[0].v[1] = verts[1];
   1.168 +		faces[0].v[2] = verts[2];
   1.169 +		faces[1].v[0] = verts[0];
   1.170 +		faces[1].v[1] = verts[2];
   1.171 +		faces[1].v[2] = verts[3];
   1.172 +	} else {
   1.173 +		faces[0].v[0] = verts[0];
   1.174 +		faces[0].v[1] = verts[1];
   1.175 +		faces[0].v[2] = verts[3];
   1.176 +		faces[1].v[0] = verts[1];
   1.177 +		faces[1].v[1] = verts[2];
   1.178 +		faces[1].v[2] = verts[3];
   1.179 +	}
   1.180 +	return 2;
   1.181 +}
   1.182 +
   1.183 +static float calc_sq_area(const Vector3 &a, const Vector3 &b, const Vector3 &c)
   1.184 +{
   1.185 +	Vector3 v1 = b - a;
   1.186 +	Vector3 v2 = c - a;
   1.187 +	return cross(v1, v2).lengthsq();
   1.188 +}