[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [56649] trunk/blender/source/blender: Optimize BKE_mesh_calc_normals(), gives approx 25% speedup.

[Campbell Barton]

Revision: 56649
          http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=56649
Author:   campbellbarton
Date:     2013-05-10 10:07:01 +0000 (Fri, 10 May 2013)
Log Message:
-----------
Optimize BKE_mesh_calc_normals(), gives approx 25% speedup.
- no need to allocate polygon normal array.
- no need to use BLI_array_ functions (realloc's).
- reduce some of the looping.

Modified Paths:
--------------
    trunk/blender/source/blender/blenkernel/intern/mesh.c
    trunk/blender/source/blender/blenlib/BLI_math_geom.h
    trunk/blender/source/blender/blenlib/intern/math_geom.c

Modified: trunk/blender/source/blender/blenkernel/intern/mesh.c
===================================================================
--- trunk/blender/source/blender/blenkernel/intern/mesh.c	2013-05-10 09:54:25 UTC (rev 56648)
+++ trunk/blender/source/blender/blenkernel/intern/mesh.c	2013-05-10 10:07:01 UTC (rev 56649)
@@ -1941,52 +1941,75 @@
 	
 }
 
-void BKE_mesh_calc_normals(MVert *mverts, int numVerts, MLoop *mloop, MPoly *mpolys,
-                           int UNUSED(numLoops), int numPolys, float (*polyNors_r)[3])
+static void mesh_calc_normals_poly_accum(MPoly *mp, MLoop *ml,
+                                         MVert *mvert, float polyno[3], float (*tnorms)[3])
 {
-	float (*pnors)[3] = polyNors_r;
+	const int nverts = mp->totloop;
+	float (*edgevecbuf)[3] = BLI_array_alloca(edgevecbuf, nverts);
+	int i;
 
-	float (*tnorms)[3], (*edgevecbuf)[3] = NULL;
-	float **vertcos = NULL, **vertnos = NULL;
-	BLI_array_declare(vertcos);
-	BLI_array_declare(vertnos);
-	BLI_array_declare(edgevecbuf);
+	/* Polygon Normal and edge-vector */
+	/* inline version of #BKE_mesh_calc_poly_normal, also does edge-vectors */
+	{
+		float const *v_prev = mvert[ml[nverts - 1].v].co;
+		float const *v_curr;
+		int i_prev = nverts - 1;
 
-	int i, j;
-	MPoly *mp;
-	MLoop *ml;
+		zero_v3(polyno);
+		/* Newell's Method */
+		for (i = 0; i < nverts; i++) {
+			v_curr = mvert[ml[i].v].co;
+			add_newell_cross_v3_v3v3(polyno, v_prev, v_curr);
 
-	if (!pnors) pnors = MEM_callocN(sizeof(float) * 3 * numPolys, "poly_nors mesh.c");
+			/* Unrelated to normalize, calcualte edge-vector */
+			sub_v3_v3v3(edgevecbuf[i_prev], v_prev, v_curr);
+			i_prev = i;
 
-	/* first go through and calculate normals for all the polys */
-	tnorms = MEM_callocN(sizeof(float) * 3 * numVerts, "tnorms mesh.c");
+			v_prev = v_curr;
+		}
+		if (UNLIKELY(normalize_v3(polyno) == 0.0f)) {
+			polyno[2] = 1.0f; /* other axis set to 0.0 */
+		}
+	}
 
-	mp = mpolys;
-	for (i = 0; i < numPolys; i++, mp++) {
-		BKE_mesh_calc_poly_normal(mp, mloop + mp->loopstart, mverts, pnors[i]);
-		ml = mloop + mp->loopstart;
+	/* accumulate angle weighted face normal */
+	/* inline version of #accumulate_vertex_normals_poly */
+	{
+		const float *prev_edge = edgevecbuf[nverts - 1];
 
-		BLI_array_empty(vertcos);
-		BLI_array_empty(vertnos);
-		BLI_array_grow_items(vertcos, mp->totloop);
-		BLI_array_grow_items(vertnos, mp->totloop);
+		for (i = 0; i < nverts; i++) {
+			const float *cur_edge = edgevecbuf[i];
+			unsigned int vindex = ml[i].v;
 
-		for (j = 0; j < mp->totloop; j++) {
-			int vindex = ml[j].v;
-			vertcos[j] = mverts[vindex].co;
-			vertnos[j] = tnorms[vindex];
+			/* 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(tnorms[vindex], polyno, fac);
+			prev_edge = cur_edge;
 		}
+	}
 
-		BLI_array_empty(edgevecbuf);
-		BLI_array_grow_items(edgevecbuf, mp->totloop);
+}
 
-		accumulate_vertex_normals_poly(vertnos, pnors[i], vertcos, edgevecbuf, mp->totloop);
+void BKE_mesh_calc_normals(MVert *mverts, int numVerts, MLoop *mloop, MPoly *mpolys,
+                           int UNUSED(numLoops), int numPolys, float (*polyNors_r)[3])
+{
+	float (*pnors)[3] = polyNors_r;
+	float (*tnorms)[3];
+	float tpnor[3];  /* temp poly normal */
+	int i;
+	MPoly *mp;
+
+	/* first go through and calculate normals for all the polys */
+	tnorms = MEM_callocN(sizeof(*tnorms) * numVerts, __func__);
+
+	mp = mpolys;
+	for (i = 0; i < numPolys; i++, mp++) {
+		mesh_calc_normals_poly_accum(mp, mloop + mp->loopstart, mverts, pnors ? pnors[i] : tpnor, tnorms);
 	}
 
-	BLI_array_free(vertcos);
-	BLI_array_free(vertnos);
-	BLI_array_free(edgevecbuf);
-
 	/* following Mesh convention; we use vertex coordinate itself for normal in this case */
 	for (i = 0; i < numVerts; i++) {
 		MVert *mv = &mverts[i];
@@ -2000,8 +2023,6 @@
 	}
 
 	MEM_freeN(tnorms);
-
-	if (pnors != polyNors_r) MEM_freeN(pnors);
 }
 
 void BKE_mesh_calc_normals_tessface(MVert *mverts, int numVerts, MFace *mfaces, int numFaces, float (*faceNors_r)[3])

Modified: trunk/blender/source/blender/blenlib/BLI_math_geom.h
===================================================================
--- trunk/blender/source/blender/blenlib/BLI_math_geom.h	2013-05-10 09:54:25 UTC (rev 56648)
+++ trunk/blender/source/blender/blenlib/BLI_math_geom.h	2013-05-10 10:07:01 UTC (rev 56649)
@@ -237,8 +237,8 @@
                                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);
+void accumulate_vertex_normals_poly(float **vertnos, const float polyno[3],
+                                    const float **vertcos, float vdiffs[][3], const int nverts);
 
 /********************************* Tangents **********************************/
 

Modified: trunk/blender/source/blender/blenlib/intern/math_geom.c
===================================================================
--- trunk/blender/source/blender/blenlib/intern/math_geom.c	2013-05-10 09:54:25 UTC (rev 56648)
+++ trunk/blender/source/blender/blenlib/intern/math_geom.c	2013-05-10 10:07:01 UTC (rev 56649)
@@ -3107,8 +3107,8 @@
 
 /* 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)
+void accumulate_vertex_normals_poly(float **vertnos, const float polyno[3],
+                                    const float **vertcos, float vdiffs[][3], int nverts)
 {
 	int i;