Clipping of imported meshes by the near and far view planes.

A straightforward clipping algorithm was implemented to
eliminate vertices that are out of the interval from the
near to far clipping distance defined by the active camera.
Previously, objects that come behind the camera could lead
to a crash.  The changes in this commit is intended to
address this issue.  When meshes are partially clipped, new
edges are added.  These edges can result in visible strokes
if they are within the camera view.

2 files changed, 231 insertions, 209 deletions

diff --git a/source/blender/freestyle/intern/blender_interface/BlenderFileLoader.cpp b/source/blender/freestyle/intern/blender_interface/BlenderFileLoader.cpp
index 6efa80431fc..31215eed069 100644
--- a/source/blender/freestyle/intern/blender_interface/BlenderFileLoader.cpp
+++ b/source/blender/freestyle/intern/blender_interface/BlenderFileLoader.cpp
@@ -1,17 +1,19 @@
 #include "BlenderFileLoader.h"
 
+#include <assert.h>
+
 BlenderFileLoader::BlenderFileLoader(Render *re, SceneRenderLayer* srl)
 {
 	_re = re;
 	_srl = srl;
-  _Scene = NULL;
-  _numFacesRead = 0;
-  _minEdgeSize = DBL_MAX;
+	_Scene = NULL;
+	_numFacesRead = 0;
+	_minEdgeSize = DBL_MAX;
 }
 
 BlenderFileLoader::~BlenderFileLoader()
 {
-  _Scene = NULL;
+	_Scene = NULL;
 }
 
 NodeGroup* BlenderFileLoader::Load()
@@ -28,8 +30,8 @@ NodeGroup* BlenderFileLoader::Load()
 	_viewplane_right=  _re->viewplane.xmax;
 	_viewplane_bottom= _re->viewplane.ymin;
 	_viewplane_top=    _re->viewplane.ymax;
-	_z_near= _re->clipsta;
-	_z_far=  _re->clipend;
+	_z_near= -_re->clipsta;
+	_z_far=  -_re->clipend;
 #if 0
 	cout << "frustrum: l " << _viewplane_left << " r " << _viewplane_right
 		<< " b " << _viewplane_bottom << " t " << _viewplane_top
@@ -53,23 +55,164 @@ NodeGroup* BlenderFileLoader::Load()
 	return _Scene;
 }
 
+#define CLIPPED_BY_NEAR -1
+#define NOT_CLIPPED      0
+#define CLIPPED_BY_FAR   1
+
+// check if each vertex of a triangle (V1, V2, V3) is clipped by the near/far plane
+// and calculate the number of triangles to be generated by clipping
+int BlenderFileLoader::countClippedFaces(VertRen *v1, VertRen *v2, VertRen *v3, int clip[3])
+{
+	VertRen *v[3];
+	int numClipped, sum, numTris;
+
+	v[0] = v1;
+	v[1] = v2;
+	v[2] = v3;
+	numClipped = sum = 0;
+	for (int i = 0; i < 3; i++) {
+		if (v[i]->co[2] > _z_near) {
+			clip[i] = CLIPPED_BY_NEAR;
+			numClipped++;
+		} else if (v[i]->co[2] < _z_far) {
+			clip[i] = CLIPPED_BY_FAR;
+			numClipped++;
+		} else {
+			clip[i] = NOT_CLIPPED;
+		}
+//		printf("%d %s\n", i, (clip[i] == NOT_CLIPPED) ? "not" : (clip[i] == CLIPPED_BY_NEAR) ? "near" : "far");
+		sum += clip[i];
+	}
+	switch (numClipped) {
+	case 0:
+		numTris = 1; // triangle
+		break;
+	case 1:
+		numTris = 2; // tetragon
+		break;
+	case 2:
+		if (sum == 0)
+			numTris = 3; // pentagon
+		else
+			numTris = 1; // triangle
+		break;
+	case 3:
+		if (sum == 3 || sum == -3)
+			numTris = 0;
+		else
+			numTris = 2; // tetragon
+		break;
+	}
+	return numTris;
+}
+
+// find the intersection point C between the line segment from V1 to V2 and
+// a clipping plane at depth Z (i.e., the Z component of C is known, while
+// the X and Y components are unknown).
+void BlenderFileLoader::clipLine(VertRen *v1, VertRen *v2, float c[3], float z)
+{
+	double d[3];
+	for (int i = 0; i < 3; i++)
+		d[i] = v2->co[i] - v1->co[i];
+	double t = (z - v1->co[2]) / d[2];
+	c[0] = v1->co[0] + t * d[0];
+	c[1] = v1->co[1] + t * d[1];
+	c[2] = z;
+}
+
+// clip the triangle (V1, V2, V3) by the near and far clipping plane and
+// obtain a set of vertices after the clipping.  The number of vertices
+// is at most 5.
+void BlenderFileLoader::clipTriangle(int numTris, float triCoords[][3], VertRen *v1, VertRen *v2, VertRen *v3, int clip[3])
+{
+	VertRen *v[3];
+	int i, j, k;
+
+	v[0] = v1;
+	v[1] = v2;
+	v[2] = v3;
+	k = 0;
+	for (i = 0; i < 3; i++) {
+		j = (i + 1) % 3;
+		if (clip[i] == NOT_CLIPPED) {
+			copy_v3_v3(triCoords[k++], v[i]->co);
+			if (clip[j] != NOT_CLIPPED) {
+				clipLine(v[i], v[j], triCoords[k++], (clip[j] == CLIPPED_BY_NEAR) ? _z_near : _z_far);
+			}
+		} else if (clip[i] != clip[j]) {
+			if (clip[j] == NOT_CLIPPED) {
+				clipLine(v[i], v[j], triCoords[k++], (clip[i] == CLIPPED_BY_NEAR) ? _z_near : _z_far);
+			} else {
+				clipLine(v[i], v[j], triCoords[k++], (clip[i] == CLIPPED_BY_NEAR) ? _z_near : _z_far);
+				clipLine(v[i], v[j], triCoords[k++], (clip[j] == CLIPPED_BY_NEAR) ? _z_near : _z_far);
+			}
+		}
+	}
+	assert (k == 2 + numTris);
+}
+
+void BlenderFileLoader::addTriangle(struct LoaderState *ls, float v1[3], float v2[3], float v3[3])
+{
+	float v12[3], v13[3], n[3];
+	float *fv[3], len;
+	unsigned i, j;
+
+	// initialize the bounding box by the first vertex
+	if (ls->currentIndex == 0) {
+		copy_v3_v3(ls->minBBox, v1);
+		copy_v3_v3(ls->maxBBox, v1);
+	}
+
+	// compute the normal of the triangle
+	sub_v3_v3v3(v12, v1, v2);
+	sub_v3_v3v3(v13, v1, v3);
+	cross_v3_v3v3(n, v12, v13);
+	normalize_v3(n);
+
+	fv[0] = v1;
+	fv[1] = v2;
+	fv[2] = v3;
+	for (i = 0; i < 3; i++) {
+
+		copy_v3_v3(ls->pv, fv[i]);
+		copy_v3_v3(ls->pn, n);
+
+		// update the bounding box
+		for (j = 0; j < 3; j++)
+		{
+	  		if (ls->minBBox[j] > ls->pv[j])
+	    		ls->minBBox[j] = ls->pv[j];
+
+	  		if (ls->maxBBox[j] < ls->pv[j])
+	    		ls->maxBBox[j] = ls->pv[j];
+		}
+
+		len = len_v3v3(fv[i], fv[(i + 1) % 3]);
+		if (_minEdgeSize > len)
+	  		_minEdgeSize = len;
+		
+		*ls->pvi = ls->currentIndex;
+		*ls->pni = ls->currentIndex;
+		*ls->pmi = ls->currentMIndex;
+
+		ls->currentIndex +=3;
+		ls->pv += 3;
+		ls->pn += 3;
+
+		ls->pvi++;
+		ls->pni++;
+		ls->pmi++;
+	}
+}
+
 void BlenderFileLoader::insertShapeNode(ObjectRen *obr, int id)
 {
-		VlakRen *vlr;
-	
-	float minBBox[3];
-	float maxBBox[3];
-	
-	NodeTransform *currentMesh = new NodeTransform;
-	NodeShape * shape;
+	VlakRen *vlr;
 	
 	// Mesh *mesh = (Mesh *)ob->data;
 	//---------------------
 	// mesh => obr
 	
-	// builds the shape:
-	shape = new NodeShape;
-	
 	// We invert the matrix in order to be able to retrieve the shape's coordinates in its local coordinates system (origin is the iNode pivot)
 	// Lib3dsMatrix M;
 	// lib3ds_matrix_copy(M, mesh->matrix);
@@ -86,20 +229,30 @@ void BlenderFileLoader::insertShapeNode(ObjectRen *obr, int id)
 	// mesh_calc_normals(mesh->mvert, mesh->totvert, mesh->mface, mesh->totface, NULL);
 	//---------------------
 	// already calculated and availabe in vlak ?	
+//	printf("%s\n", obr->ob->id.name + 2);
 	
 	// We build the rep:
 	IndexedFaceSet *rep;
 	unsigned numFaces = 0;
+	int clip_1[3], clip_2[3];
 	for(int a=0; a < obr->totvlak; a++) {
 		if((a & 255)==0) vlr= obr->vlaknodes[a>>8].vlak;
 		else vlr++;
-	
-		if(vlr->v4)
-			numFaces += 2;
-		else
-			numFaces++;
+//		printf("v1 %f, %f, %f\n", vlr->v1->co[0], vlr->v1->co[1], vlr->v1->co[2]);
+//		printf("v2 %f, %f, %f\n", vlr->v2->co[0], vlr->v2->co[1], vlr->v2->co[2]);
+//		printf("v3 %f, %f, %f\n", vlr->v3->co[0], vlr->v3->co[1], vlr->v3->co[2]);
+//		if (vlr->v4) printf("v4 %f, %f, %f\n", vlr->v4->co[0], vlr->v4->co[1], vlr->v4->co[2]);
+		numFaces += countClippedFaces(vlr->v1, vlr->v2, vlr->v3, clip_1);
+		if (vlr->v4)
+			numFaces += countClippedFaces(vlr->v1, vlr->v3, vlr->v4, clip_2);
 	}
-	
+//	cout <<"numFaces " <<numFaces<<endl;
+	if (numFaces == 0)
+		return;
+
+	NodeTransform *currentMesh = new NodeTransform;
+	NodeShape * shape = new NodeShape;
+
 	unsigned vSize = 3*3*numFaces;
 	float *vertices = new float[vSize];
 	unsigned nSize = vSize;
@@ -120,46 +273,35 @@ void BlenderFileLoader::insertShapeNode(ObjectRen *obr, int id)
 	unsigned *NIndices = new unsigned[niSize];
 	unsigned *MIndices = new unsigned[viSize]; // Material Indices
 	
-	
-	float *pv = vertices;
-	float *pn = normals;
-	unsigned *pvi = VIndices;
-	unsigned *pni = NIndices;
-	unsigned *pmi = MIndices;
-	
-	unsigned currentIndex = 0;
-	unsigned currentMIndex = 0;
+	struct LoaderState ls;
+	ls.pv = vertices;
+	ls.pn = normals;
+	ls.pvi = VIndices;
+	ls.pni = NIndices;
+	ls.pmi = MIndices;
+	ls.currentIndex = 0;
+	ls.currentMIndex = 0;
 	
 	FrsMaterial tmpMat;
 	
 	// we want to find the min and max coordinates as we build the rep. 
 	// We initialize the min and max values whith the first vertex.
 	//lib3ds_vector_transform(pvtmp, M, mesh->pointL[mesh->faceL[0].points[0]].pos);
-	float pvtmp[3];
-	pvtmp[0] = obr->vertnodes[0].vert->co[0];
-	pvtmp[1] = obr->vertnodes[0].vert->co[1];
-	pvtmp[2] = obr->vertnodes[0].vert->co[2];
-	
-	mul_m4_v3( M, pvtmp);
-	
-	minBBox[0] = pvtmp[0];
-	maxBBox[0] = pvtmp[0];
-	minBBox[1] = pvtmp[1];
-	maxBBox[1] = pvtmp[1];
-	minBBox[2] = pvtmp[2];
-	maxBBox[2] = pvtmp[2];
-	
+
 	int p;
-	real vert[3][3];
-	real norm;
 	for(p=0; p < obr->totvlak; ++p) // we parse the faces of the mesh
 	{
-			VertRen * fv[3];
-		
-		  // Lib3dsFace *f=&mesh->faceL[p];
-		  // Lib3dsMaterial *mat=0;
+			// Lib3dsFace *f=&mesh->faceL[p];
+			// Lib3dsMaterial *mat=0;
 			if((p & 255)==0) vlr = obr->vlaknodes[p>>8].vlak;
 			else vlr++;
+
+			unsigned numTris_1, numTris_2;
+			numTris_1 = countClippedFaces(vlr->v1, vlr->v2, vlr->v3, clip_1);
+			numTris_2 = (vlr->v4) ? countClippedFaces(vlr->v1, vlr->v3, vlr->v4, clip_2) : 0;
+			if (numTris_1 == 0 && numTris_2 == 0)
+				continue;
+
 			Material *mat = vlr->mat;
 	
 			if (mat) 
@@ -185,7 +327,7 @@ void BlenderFileLoader::insertShapeNode(ObjectRen *obr, int id)
 		    		it!=itend;
 		    		++it){
 		      			if(*it == tmpMat){
-		        			currentMIndex = i;
+		        			ls.currentMIndex = i;
 		        			found = true;
 		        			break;
 		      			}
@@ -194,171 +336,35 @@ void BlenderFileLoader::insertShapeNode(ObjectRen *obr, int id)
 		
 		    	if(!found){
 		      		meshFrsMaterials.push_back(tmpMat);
-		      		currentMIndex = meshFrsMaterials.size()-1;
+		      		ls.currentMIndex = meshFrsMaterials.size()-1;
 		    	}
 	  		}
-	
-			unsigned j;
-			fv[0] = vlr->v1;
-			fv[1] = vlr->v2;
-			fv[2] = vlr->v3;
-			float *pv_ptr[3];
-			for(i=0; i<3; ++i) // we parse the vertices of the face f
-			{
-	
-				//lib3ds_vector_transform(pv, M, mesh->pointL[f->points[i]].pos); //fills the cells of the pv array
-				for(j=0; j<3; j++)
-					pv[j] = fv[i]->co[j];
-				mul_m4_v3( M, pv);
-	
-				for(j=0; j<3; j++) // we parse the xyz coordinates of the vertex i
-				{
-			  		if(minBBox[j] > pv[j])
-			    		minBBox[j] = pv[j];
-	
-			  		if(maxBBox[j] < pv[j])
-			    		maxBBox[j] = pv[j];
-	
-			  		vert[i][j] = pv[j];
-				}
-				
-				pv_ptr[i] = pv;
-				*pvi = currentIndex;
-				*pmi = currentMIndex;
 
-				currentIndex +=3;
-				pv += 3;
+			float triCoords[5][3];
 
-				pvi++;
-				pmi++;
-			}
-			
-			currentIndex -= 9;
-						
-			float vec01[3];
-			vec01[0] = pv_ptr[1][0] - pv_ptr[0][0]; 
-			vec01[1] = pv_ptr[1][1] - pv_ptr[0][1];
-			vec01[2] = pv_ptr[1][2] - pv_ptr[0][2];
-			
-			float vec02[3];
-			vec02[0] = pv_ptr[2][0] - pv_ptr[0][0]; 
-			vec02[1] = pv_ptr[2][1] - pv_ptr[0][1];
-			vec02[2] = pv_ptr[2][2] - pv_ptr[0][2];
-			
-			float n[3];
-			cross_v3_v3v3(n, vec01, vec02);
-			normalize_v3(n);
-			
-			for(i=0; i<3; ++i) {
-				for(j=0; j<3; ++j) {
-					pn[j] = n[j];
+			if (numTris_1 > 0) {
+				clipTriangle(numTris_1, triCoords, vlr->v1, vlr->v2, vlr->v3, clip_1);
+				for (i = 0; i < 2 + numTris_1; i++) {
+					mul_m4_v3(M, triCoords[i]); // camera to world
+//					printf("%d %f, %f, %f\n", i, triCoords[i][0], triCoords[i][1], triCoords[i][2]);
 				}
-				*pni = currentIndex;
-
-				pn += 3;
-				pni++;
-
-				currentIndex +=3;
-			}
-	
-			for(i=0; i<3; i++)
-			{
-				norm = 0.0;
-				
-				for (unsigned j = 0; j < 3; j++)
-			  		norm += (vert[i][j] - vert[(i+1)%3][j])*(vert[i][j] - vert[(i+1)%3][j]);
-		
-				norm = sqrt(norm);
-				if(_minEdgeSize > norm)
-			  		_minEdgeSize = norm;
-			}
-			
-			++_numFacesRead;
-
-			
-			if(vlr->v4){
-
-				unsigned j;
-				fv[0] = vlr->v1;
-				fv[1] = vlr->v3;
-				fv[2] = vlr->v4;
-				float *pv_ptr[3];
-				for(i=0; i<3; ++i) // we parse the vertices of the face f
-				{
-
-					//lib3ds_vector_transform(pv, M, mesh->pointL[f->points[i]].pos); //fills the cells of the pv array
-					for(j=0; j<3; j++)
-						pv[j] = fv[i]->co[j];
-					mul_m4_v3( M, pv);
-
-					for(j=0; j<3; j++) // we parse the xyz coordinates of the vertex i
-					{
-				  		if(minBBox[j] > pv[j])
-				    		minBBox[j] = pv[j];
-
-				  		if(maxBBox[j] < pv[j])
-				    		maxBBox[j] = pv[j];
-
-				  		vert[i][j] = pv[j];
-					}
-
-					pv_ptr[i] = pv;
-					*pvi = currentIndex;
-					*pmi = currentMIndex;
-
-					currentIndex +=3;
-					pv += 3;
-
-					pvi++;
-					pmi++;
+				for (i = 0; i < numTris_1; i++) {
+					addTriangle(&ls, triCoords[0], triCoords[i+1], triCoords[i+2]);
+					_numFacesRead++;
 				}
+			}
 
-				currentIndex -= 9;
-
-				float vec01[3];
-				vec01[0] = pv_ptr[1][0] - pv_ptr[0][0]; 
-				vec01[1] = pv_ptr[1][1] - pv_ptr[0][1];
-				vec01[2] = pv_ptr[1][2] - pv_ptr[0][2];
-
-				float vec02[3];
-				vec02[0] = pv_ptr[2][0] - pv_ptr[0][0]; 
-				vec02[1] = pv_ptr[2][1] - pv_ptr[0][1];
-				vec02[2] = pv_ptr[2][2] - pv_ptr[0][2];
-
-				float n[3];
-				cross_v3_v3v3(n, vec01, vec02);
-				normalize_v3(n);
-				
-				for(i=0; i<3; ++i) {
-					for(j=0; j<3; ++j) {
-						pn[j] = n[j];
-					}
-					*pni = currentIndex;
-
-					pn += 3;
-					pni++;
-
-					currentIndex +=3;
+			if (numTris_2 > 0) {
+				clipTriangle(numTris_2, triCoords, vlr->v1, vlr->v3, vlr->v4, clip_2);
+				for (i = 0; i < 2 + numTris_2; i++) {
+					mul_m4_v3(M, triCoords[i]); // camera to world
+//					printf("%d %f, %f, %f\n", i, triCoords[i][0], triCoords[i][1], triCoords[i][2]);
 				}
-
-				for(i=0; i<3; i++)
-				{
-					norm = 0.0;
-
-					for (unsigned j = 0; j < 3; j++)
-				  		norm += (vert[i][j] - vert[(i+1)%3][j])*(vert[i][j] - vert[(i+1)%3][j]);
-
-					norm = sqrt(norm);
-					if(_minEdgeSize > norm)
-				  		_minEdgeSize = norm;
+				for (i = 0; i < numTris_2; i++) {
+					addTriangle(&ls, triCoords[0], triCoords[i+1], triCoords[i+2]);
+					_numFacesRead++;
 				}
-
-				++_numFacesRead;
-
-
-
 			}
-	
 	}
 	
 	// We might have several times the same vertex. We want a clean 
@@ -413,8 +419,8 @@ void BlenderFileLoader::insertShapeNode(ObjectRen *obr, int id)
 	// sets the id of the rep
 	rep->setId(Id(id, 0));
 	
-	const BBox<Vec3r> bbox = BBox<Vec3r>(Vec3r(minBBox[0], minBBox[1], minBBox[2]), 
-	                                     Vec3r(maxBBox[0], maxBBox[1], maxBBox[2]));
+	const BBox<Vec3r> bbox = BBox<Vec3r>(Vec3r(ls.minBBox[0], ls.minBBox[1], ls.minBBox[2]), 
+	                                     Vec3r(ls.maxBBox[0], ls.maxBBox[1], ls.maxBBox[2]));
 	rep->setBBox(bbox);
 	shape->AddRep(rep);
 	
diff --git a/source/blender/freestyle/intern/blender_interface/BlenderFileLoader.h b/source/blender/freestyle/intern/blender_interface/BlenderFileLoader.h
index 29acbfc203f..59fa5923b36 100644
--- a/source/blender/freestyle/intern/blender_interface/BlenderFileLoader.h
+++ b/source/blender/freestyle/intern/blender_interface/BlenderFileLoader.h
@@ -33,6 +33,18 @@ extern "C" {
 
 class NodeGroup;
 
+struct LoaderState {
+	float *pv;
+	float *pn;
+	unsigned *pvi;
+	unsigned *pni;
+	unsigned *pmi;
+	unsigned currentIndex;
+	unsigned currentMIndex;
+	float minBBox[3];
+	float maxBBox[3];
+};
+
 class LIB_SCENE_GRAPH_EXPORT BlenderFileLoader
 {
 public:
@@ -51,6 +63,10 @@ public:
 
 protected:
 	void insertShapeNode(ObjectRen *obr, int id);
+	int countClippedFaces(VertRen *v1, VertRen *v2, VertRen *v3, int clipped[3]);
+	void clipLine(VertRen *v1, VertRen *v2, float c[3], float z);
+	void clipTriangle(int numTris, float triCoords[][3], VertRen *v1, VertRen *v2, VertRen *v3, int clip[3]);
+	void addTriangle(struct LoaderState *state, float v1[3], float v2[3], float v3[3]);
 
 protected:
 	Render* _re;