misc changes from bmesh, syncing across to trunk, no functional changes

10 files changed, 186 insertions, 72 deletions

diff --git a/source/blender/blenkernel/intern/mesh.c b/source/blender/blenkernel/intern/mesh.c
index 189ce890c2f..f6bd321466c 100644
--- a/source/blender/blenkernel/intern/mesh.c
+++ b/source/blender/blenkernel/intern/mesh.c
@@ -42,12 +42,12 @@
 #include "DNA_meshdata_types.h"
 #include "DNA_ipo_types.h"
 
+#include "BLI_utildefines.h"
 #include "BLI_blenlib.h"
 #include "BLI_bpath.h"
 #include "BLI_editVert.h"
 #include "BLI_math.h"
 #include "BLI_edgehash.h"
-#include "BLI_utildefines.h"
 
 #include "BKE_animsys.h"
 #include "BKE_main.h"
@@ -1295,7 +1295,7 @@ float (*mesh_getVertexCos(Mesh *me, int *numVerts_r))[3]
 	
 	if (numVerts_r) *numVerts_r = numVerts;
 	for (i=0; i<numVerts; i++)
-		VECCOPY(cos[i], me->mvert[i].co);
+		copy_v3_v3(cos[i], me->mvert[i].co);
 	
 	return cos;
 }
diff --git a/source/blender/blenlib/BLI_math_geom.h b/source/blender/blenlib/BLI_math_geom.h
index 27da6c1025d..8d18f5253c4 100644
--- a/source/blender/blenlib/BLI_math_geom.h
+++ b/source/blender/blenlib/BLI_math_geom.h
@@ -54,6 +54,8 @@ float area_tri_v3(const float a[3], const float b[3], const float c[3]);
 float area_quad_v3(const float a[3], const float b[3], const float c[3], const float d[3]);
 float area_poly_v3(int nr, float verts[][3], const float normal[3]);
 
+int is_quad_convex_v3(const float *v1, const float *v2, const float *v3, const float *v4);
+
 /********************************* Distance **********************************/
 
 float dist_to_line_v2(const float p[2], const float l1[2], const float l2[2]);
@@ -221,6 +223,9 @@ void accumulate_vertex_normals(float n1[3], float n2[3], float n3[3],
 	float n4[3], const float f_no[3], const float co1[3], const float co2[3],
 	const float co3[3], const float co4[3]);
 
+void accumulate_vertex_normals_poly(float **vertnos, float polyno[3],
+	float **vertcos, float vdiffs[][3], int nverts);
+
 /********************************* Tangents **********************************/
 
 typedef struct VertexTangent {
diff --git a/source/blender/blenlib/BLI_math_vector.h b/source/blender/blenlib/BLI_math_vector.h
index b75d8e0daa6..12a0b1892a1 100644
--- a/source/blender/blenlib/BLI_math_vector.h
+++ b/source/blender/blenlib/BLI_math_vector.h
@@ -171,6 +171,7 @@ float angle_v3v3v3(const float a[3], const float b[3], const float c[3]);
 float angle_normalized_v3v3(const float v1[3], const float v2[3]);
 void angle_tri_v3(float angles[3], const float v1[3], const float v2[3], const float v3[3]);
 void angle_quad_v3(float angles[4], const float v1[3], const float v2[3], const float v3[3], const float v4[3]);
+void angle_poly_v3(float* angles, const float* verts[3], int len);
 
 /********************************* Geometry **********************************/
 
diff --git a/source/blender/blenlib/intern/BLI_ghash.c b/source/blender/blenlib/intern/BLI_ghash.c
index 9f388b68c38..e10082348be 100644
--- a/source/blender/blenlib/intern/BLI_ghash.c
+++ b/source/blender/blenlib/intern/BLI_ghash.c
@@ -40,8 +40,8 @@
 
 // #include "BLI_blenlib.h"
 
-#include "BLI_mempool.h"
 #include "BLI_utildefines.h"
+#include "BLI_mempool.h"
 #include "BLI_ghash.h"
 
 #include "BLO_sys_types.h" // for intptr_t support
diff --git a/source/blender/blenlib/intern/math_geom.c b/source/blender/blenlib/intern/math_geom.c
index ef04e5e9bce..d7880e40626 100644
--- a/source/blender/blenlib/intern/math_geom.c
+++ b/source/blender/blenlib/intern/math_geom.c
@@ -2382,6 +2382,38 @@ void accumulate_vertex_normals(float n1[3], float n2[3], float n3[3],
 	}
 }
 
+/* Add weighted face normal component into normals of the face vertices.
+   Caller must pass pre-allocated vdiffs of nverts length. */
+void accumulate_vertex_normals_poly(float **vertnos, float polyno[3],
+	float **vertcos, float vdiffs[][3], int nverts)
+{
+	int i;
+
+	/* calculate normalized edge directions for each edge in the poly */
+	for (i = 0; i < nverts; i++) {
+		sub_v3_v3v3(vdiffs[i], vertcos[(i+1) % nverts], vertcos[i]);
+		normalize_v3(vdiffs[i]);
+	}
+
+	/* accumulate angle weighted face normal */
+	{
+		const float *prev_edge = vdiffs[nverts-1];
+		int i;
+
+		for(i=0; i<nverts; i++) {
+			const float *cur_edge = vdiffs[i];
+			
+			/* calculate angle between the two poly edges incident on
+			   this vertex */
+			const float fac= saacos(-dot_v3v3(cur_edge, prev_edge));
+
+			/* accumulate */
+			madd_v3_v3fl(vertnos[i], polyno, fac);
+			prev_edge = cur_edge;
+		}
+	}
+}
+
 /********************************* Tangents **********************************/
 
 /* For normal map tangents we need to detect uv boundaries, and only average
@@ -3038,3 +3070,26 @@ float form_factor_hemi_poly(float p[3], float n[3], float v1[3], float v2[3], fl
 
 	return contrib;
 }
+
+/* evaluate if entire quad is a proper convex quad */
+ int is_quad_convex_v3(const float *v1, const float *v2, const float *v3, const float *v4)
+ {
+	float nor[3], nor1[3], nor2[3], vec[4][2];
+	int axis_a, axis_b;
+	
+	/* define projection, do both trias apart, quad is undefined! */
+	normal_tri_v3(nor1, v1, v2, v3);
+	normal_tri_v3(nor2, v1, v3, v4);
+	add_v3_v3v3(nor, nor1, nor2);
+
+	axis_dominant_v3(&axis_a, &axis_b, nor);
+
+	vec[0][0]= v1[axis_a]; vec[0][1]= v1[axis_b];
+	vec[1][0]= v2[axis_a]; vec[1][1]= v2[axis_b];
+
+	vec[2][0]= v3[axis_a]; vec[2][1]= v3[axis_b];
+	vec[3][0]= v4[axis_a]; vec[3][1]= v4[axis_b];
+	
+	/* linetests, the 2 diagonals have to instersect to be convex */
+	return (isect_line_line_v2(vec[0], vec[2], vec[1], vec[3]) > 0) ? 1 : 0;
+}
diff --git a/source/blender/blenlib/intern/math_vector.c b/source/blender/blenlib/intern/math_vector.c
index 590a48e8085..47deb705def 100644
--- a/source/blender/blenlib/intern/math_vector.c
+++ b/source/blender/blenlib/intern/math_vector.c
@@ -239,6 +239,20 @@ void angle_quad_v3(float angles[4], const float v1[3], const float v2[3], const
 	angles[3]= (float)M_PI - angle_normalized_v3v3(ed4, ed1);
 }
 
+void angle_poly_v3(float *angles, const float *verts[3], int len)
+{
+	int i;
+	float vec[3][3];
+
+	sub_v3_v3v3(vec[2], verts[len-1], verts[0]);
+	normalize_v3(vec[2]);
+	for (i = 0; i < len; i++) {
+		sub_v3_v3v3(vec[i%3], verts[i%len], verts[(i+1)%len]);
+		normalize_v3(vec[i%3]);
+		angles[i] = (float)M_PI - angle_normalized_v3v3(vec[(i+2)%3], vec[i%3]);
+	}
+}
+
 /********************************* Geometry **********************************/
 
 /* Project v1 on v2 */
diff --git a/source/blender/blenlib/intern/math_vector_inline.c b/source/blender/blenlib/intern/math_vector_inline.c
index dc9a32222f7..9c5d8f3261f 100644
--- a/source/blender/blenlib/intern/math_vector_inline.c
+++ b/source/blender/blenlib/intern/math_vector_inline.c
@@ -515,6 +515,29 @@ MINLINE float normalize_v3_v3(float r[3], const float a[3])
 	return d;
 }
 
+MINLINE double normalize_v3_d(double n[3])
+{
+	double d= n[0]*n[0] + n[1]*n[1] + n[2]*n[2];
+
+	/* a larger value causes normalize errors in a
+	   scaled down models with camera xtreme close */
+	if(d > 1.0e-35) {
+		double mul;
+
+		d= sqrt(d);
+		mul = 1.0 / d;
+
+		n[0] *= mul;
+		n[1] *= mul;
+		n[2] *= mul;
+	} else {
+		n[0] = n[1] = n[2] = 0;
+		d= 0.0;
+	}
+
+	return d;
+}
+
 MINLINE float normalize_v3(float n[3])
 {
 	return normalize_v3_v3(n, n);
diff --git a/source/blender/blenloader/intern/readfile.c b/source/blender/blenloader/intern/readfile.c
index fa15590e4e3..fb49f3974b4 100644
--- a/source/blender/blenloader/intern/readfile.c
+++ b/source/blender/blenloader/intern/readfile.c
@@ -97,9 +97,9 @@
 
 #include "MEM_guardedalloc.h"
 
+#include "BLI_utildefines.h"
 #include "BLI_blenlib.h"
 #include "BLI_math.h"
-#include "BLI_utildefines.h"
 
 #include "BKE_anim.h"
 #include "BKE_action.h"
diff --git a/source/blender/editors/mesh/mesh_ops.c b/source/blender/editors/mesh/mesh_ops.c
index 90b3d45deb7..2ff90525498 100644
--- a/source/blender/editors/mesh/mesh_ops.c
+++ b/source/blender/editors/mesh/mesh_ops.c
@@ -300,6 +300,7 @@ void ED_keymap_mesh(wmKeyConfig *keyconf)
 	
 	WM_keymap_add_item(keymap, "MESH_OT_fill", FKEY, KM_PRESS, KM_ALT, 0);
 	WM_keymap_add_item(keymap, "MESH_OT_beautify_fill", FKEY, KM_PRESS, KM_SHIFT|KM_ALT, 0);
+
 	WM_keymap_add_item(keymap, "MESH_OT_quads_convert_to_tris", TKEY, KM_PRESS, KM_CTRL, 0);
 	WM_keymap_add_item(keymap, "MESH_OT_tris_convert_to_quads", JKEY, KM_PRESS, KM_ALT, 0);
 	WM_keymap_add_item(keymap, "MESH_OT_edge_flip", FKEY, KM_PRESS, KM_SHIFT|KM_CTRL, 0);
diff --git a/source/blender/modifiers/intern/MOD_build.c b/source/blender/modifiers/intern/MOD_build.c
index 119934ea2f0..ebb5bd9ab9b 100644
--- a/source/blender/modifiers/intern/MOD_build.c
+++ b/source/blender/modifiers/intern/MOD_build.c
@@ -76,135 +76,150 @@ static int dependsOnTime(ModifierData *UNUSED(md))
 }
 
 static DerivedMesh *applyModifier(ModifierData *md, Object *UNUSED(ob),
-						DerivedMesh *derivedData,
-						int UNUSED(useRenderParams),
-						int UNUSED(isFinalCalc))
+                                  DerivedMesh *derivedData,
+                                  int UNUSED(useRenderParams),
+                                  int UNUSED(isFinalCalc))
 {
 	DerivedMesh *dm = derivedData;
 	DerivedMesh *result;
 	BuildModifierData *bmd = (BuildModifierData*) md;
 	int i;
-	int numFaces, numEdges;
+	int numFaces_dst, numEdges_dst;
 	int *vertMap, *edgeMap, *faceMap;
 	float frac;
 	GHashIterator *hashIter;
 	/* maps vert indices in old mesh to indices in new mesh */
 	GHash *vertHash = BLI_ghash_new(BLI_ghashutil_inthash,
-					BLI_ghashutil_intcmp, "build ve apply gh");
+	                                BLI_ghashutil_intcmp, "build ve apply gh");
 	/* maps edge indices in new mesh to indices in old mesh */
 	GHash *edgeHash = BLI_ghash_new(BLI_ghashutil_inthash,
-					BLI_ghashutil_intcmp, "build ed apply gh");
+	                                BLI_ghashutil_intcmp, "build ed apply gh");
 
-	const int maxVerts= dm->getNumVerts(dm);
-	const int maxEdges= dm->getNumEdges(dm);
-	const int maxFaces= dm->getNumFaces(dm);
+	const int numVert_src= dm->getNumVerts(dm);
+	const int numEdge_src= dm->getNumEdges(dm);
+	const int numFace_src= dm->getNumFaces(dm);
 
-	vertMap = MEM_callocN(sizeof(*vertMap) * maxVerts, "build modifier vertMap");
-	for(i = 0; i < maxVerts; ++i) vertMap[i] = i;
-	edgeMap = MEM_callocN(sizeof(*edgeMap) * maxEdges, "build modifier edgeMap");
-	for(i = 0; i < maxEdges; ++i) edgeMap[i] = i;
-	faceMap = MEM_callocN(sizeof(*faceMap) * maxFaces, "build modifier faceMap");
-	for(i = 0; i < maxFaces; ++i) faceMap[i] = i;
+	vertMap = MEM_callocN(sizeof(*vertMap) * numVert_src, "build modifier vertMap");
+	for (i = 0; i < numVert_src; i++) vertMap[i] = i;
+	edgeMap = MEM_callocN(sizeof(*edgeMap) * numEdge_src, "build modifier edgeMap");
+	for (i = 0; i < numEdge_src; i++) edgeMap[i] = i;
+	faceMap = MEM_callocN(sizeof(*faceMap) * numFace_src, "build modifier faceMap");
+	for (i = 0; i < numFace_src; i++) faceMap[i] = i;
 
 	frac = (BKE_curframe(md->scene) - bmd->start) / bmd->length;
 	CLAMP(frac, 0.0f, 1.0f);
 
-	numFaces = dm->getNumFaces(dm) * frac;
-	numEdges = dm->getNumEdges(dm) * frac;
+	numFaces_dst = dm->getNumFaces(dm) * frac;
+	numEdges_dst = dm->getNumEdges(dm) * frac;
 
 	/* if there's at least one face, build based on faces */
-	if(numFaces) {
-		if(bmd->randomize)
+	if (numFaces_dst) {
+		if (bmd->randomize) {
 			BLI_array_randomize(faceMap, sizeof(*faceMap),
-						maxFaces, bmd->seed);
+			                    numFace_src, bmd->seed);
+		}
 
 		/* get the set of all vert indices that will be in the final mesh,
-		* mapped to the new indices
-		*/
-		for(i = 0; i < numFaces; ++i) {
+		 * mapped to the new indices
+		 */
+		for (i = 0; i < numFaces_dst; i++) {
 			MFace mf;
 			dm->getFace(dm, faceMap[i], &mf);
 
-			if(!BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(mf.v1)))
+			if (!BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(mf.v1))) {
 				BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(mf.v1),
-					SET_INT_IN_POINTER(BLI_ghash_size(vertHash)));
-			if(!BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(mf.v2)))
+				                 SET_INT_IN_POINTER(BLI_ghash_size(vertHash)));
+			}
+			if (!BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(mf.v2))) {
 				BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(mf.v2),
-					SET_INT_IN_POINTER(BLI_ghash_size(vertHash)));
-			if(!BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(mf.v3)))
+				                 SET_INT_IN_POINTER(BLI_ghash_size(vertHash)));
+			}
+			if (!BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(mf.v3))) {
 				BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(mf.v3),
-					SET_INT_IN_POINTER(BLI_ghash_size(vertHash)));
-			if(mf.v4 && !BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(mf.v4)))
+				                 SET_INT_IN_POINTER(BLI_ghash_size(vertHash)));
+			}
+			if (mf.v4 && !BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(mf.v4))) {
 				BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(mf.v4),
-					SET_INT_IN_POINTER(BLI_ghash_size(vertHash)));
+				                 SET_INT_IN_POINTER(BLI_ghash_size(vertHash)));
+			}
 		}
 
 		/* get the set of edges that will be in the new mesh (i.e. all edges
-		* that have both verts in the new mesh)
-		*/
-		for(i = 0; i < maxEdges; ++i) {
+		 * that have both verts in the new mesh)
+		 */
+		for (i = 0; i < numEdge_src; i++) {
 			MEdge me;
 			dm->getEdge(dm, i, &me);
 
-			if(BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(me.v1))
-						&& BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(me.v2)))
-				BLI_ghash_insert(edgeHash,
-					SET_INT_IN_POINTER(BLI_ghash_size(edgeHash)), SET_INT_IN_POINTER(i));
+			if ( BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(me.v1)) &&
+			     BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(me.v2)))
+			{
+				BLI_ghash_insert(edgeHash, SET_INT_IN_POINTER(BLI_ghash_size(edgeHash)),
+				                 SET_INT_IN_POINTER(i));
+			}
 		}
-	} else if(numEdges) {
-		if(bmd->randomize)
+	}
+	else if (numEdges_dst) {
+		if (bmd->randomize) {
 			BLI_array_randomize(edgeMap, sizeof(*edgeMap),
-						maxEdges, bmd->seed);
+			                    numEdge_src, bmd->seed);
+		}
 
 		/* get the set of all vert indices that will be in the final mesh,
-		* mapped to the new indices
-		*/
-		for(i = 0; i < numEdges; ++i) {
+		 * mapped to the new indices
+		 */
+		for (i = 0; i < numEdges_dst; i++) {
 			MEdge me;
 			dm->getEdge(dm, edgeMap[i], &me);
 
-			if(!BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(me.v1)))
+			if (!BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(me.v1))) {
 				BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(me.v1),
-					SET_INT_IN_POINTER(BLI_ghash_size(vertHash)));
-			if(!BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(me.v2)))
+				                 SET_INT_IN_POINTER(BLI_ghash_size(vertHash)));
+			}
+			if (!BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(me.v2))) {
 				BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(me.v2),
-					SET_INT_IN_POINTER(BLI_ghash_size(vertHash)));
+				                 SET_INT_IN_POINTER(BLI_ghash_size(vertHash)));
+			}
 		}
 
 		/* get the set of edges that will be in the new mesh
-		*/
-		for(i = 0; i < numEdges; ++i) {
+		 */
+		for (i = 0; i < numEdges_dst; i++) {
 			MEdge me;
 			dm->getEdge(dm, edgeMap[i], &me);
 
 			BLI_ghash_insert(edgeHash, SET_INT_IN_POINTER(BLI_ghash_size(edgeHash)),
-					 SET_INT_IN_POINTER(edgeMap[i]));
+			                 SET_INT_IN_POINTER(edgeMap[i]));
 		}
-	} else {
+	}
+	else {
 		int numVerts = dm->getNumVerts(dm) * frac;
 
-		if(bmd->randomize)
+		if (bmd->randomize) {
 			BLI_array_randomize(vertMap, sizeof(*vertMap),
-						maxVerts, bmd->seed);
+			                    numVert_src, bmd->seed);
+		}
 
 		/* get the set of all vert indices that will be in the final mesh,
 		* mapped to the new indices
 		*/
-		for(i = 0; i < numVerts; ++i)
-			BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(vertMap[i]), SET_INT_IN_POINTER(i));
+		for (i = 0; i < numVerts; i++) {
+			BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(vertMap[i]),
+			                 SET_INT_IN_POINTER(i));
+		}
 	}
 
 	/* now we know the number of verts, edges and faces, we can create
-	* the mesh
-	*/
+	 * the mesh
+	 */
 	result = CDDM_from_template(dm, BLI_ghash_size(vertHash),
-					BLI_ghash_size(edgeHash), numFaces);
+	                            BLI_ghash_size(edgeHash), numFaces_dst);
 
 	/* copy the vertices across */
-	for(	hashIter = BLI_ghashIterator_new(vertHash);
-			!BLI_ghashIterator_isDone(hashIter);
-			BLI_ghashIterator_step(hashIter)
-	) {
+	for ( hashIter = BLI_ghashIterator_new(vertHash);
+	      !BLI_ghashIterator_isDone(hashIter);
+	      BLI_ghashIterator_step(hashIter))
+	{
 		MVert source;
 		MVert *dest;
 		int oldIndex = GET_INT_FROM_POINTER(BLI_ghashIterator_getKey(hashIter));
@@ -219,7 +234,7 @@ static DerivedMesh *applyModifier(ModifierData *md, Object *UNUSED(ob),
 	BLI_ghashIterator_free(hashIter);
 	
 	/* copy the edges across, remapping indices */
-	for(i = 0; i < BLI_ghash_size(edgeHash); ++i) {
+	for (i = 0; i < BLI_ghash_size(edgeHash); i++) {
 		MEdge source;
 		MEdge *dest;
 		int oldIndex = GET_INT_FROM_POINTER(BLI_ghash_lookup(edgeHash, SET_INT_IN_POINTER(i)));
@@ -235,7 +250,7 @@ static DerivedMesh *applyModifier(ModifierData *md, Object *UNUSED(ob),
 	}
 
 	/* copy the faces across, remapping indices */
-	for(i = 0; i < numFaces; ++i) {
+	for (i = 0; i < numFaces_dst; i++) {
 		MFace source;
 		MFace *dest;
 		int orig_v4;
@@ -248,7 +263,7 @@ static DerivedMesh *applyModifier(ModifierData *md, Object *UNUSED(ob),
 		source.v1 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v1)));
 		source.v2 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v2)));
 		source.v3 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v3)));
-		if(source.v4)
+		if (source.v4)
 			source.v4 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v4)));
 		
 		DM_copy_face_data(dm, result, faceMap[i], i, 1);
@@ -258,14 +273,14 @@ static DerivedMesh *applyModifier(ModifierData *md, Object *UNUSED(ob),
 	}
 
 	CDDM_calc_normals(result);
-	
+
 	BLI_ghash_free(vertHash, NULL, NULL);
 	BLI_ghash_free(edgeHash, NULL, NULL);
 	
 	MEM_freeN(vertMap);
 	MEM_freeN(edgeMap);
 	MEM_freeN(faceMap);
-	
+
 	return result;
 }