[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [58621] branches/ soc-2013-meshdata_transfer/source/blender/bmesh/tools/bmesh_data_transfer.c : Using vertex tables to eliminate the usage of BM_vert_at_index to optimize for the vertex access speed

[Walid Shouman]

Revision: 58621
          http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=58621
Author:   walid
Date:     2013-07-26 11:44:23 +0000 (Fri, 26 Jul 2013)
Log Message:
-----------
Using vertex tables to eliminate the usage of BM_vert_at_index to optimize for the vertex access speed

Modified Paths:
--------------
    branches/soc-2013-meshdata_transfer/source/blender/bmesh/tools/bmesh_data_transfer.c

Modified: branches/soc-2013-meshdata_transfer/source/blender/bmesh/tools/bmesh_data_transfer.c
===================================================================
--- branches/soc-2013-meshdata_transfer/source/blender/bmesh/tools/bmesh_data_transfer.c	2013-07-26 11:15:22 UTC (rev 58620)
+++ branches/soc-2013-meshdata_transfer/source/blender/bmesh/tools/bmesh_data_transfer.c	2013-07-26 11:44:23 UTC (rev 58621)
@@ -443,6 +443,13 @@
 	return true;
 }
 
+typedef struct BMVert_map {
+	BMVert *v1;
+	BMVert *v2;
+}BMVert_map;
+
+#define MAX_AUTO_TOL 100
+
 /**
  * @brief inherit vertices' offset from the source, then interpolate within the destination by using distance from
  * vertices that inherited And normals from those vertices
@@ -490,10 +497,13 @@
 
 	int i, j, k, m;
 
-	int *inherit_vert_ind;
-	int *interp_vert_ind;
-
+	//weights carry the weights of the vertices organized by their index
+	//act as a link between the offsets of the barycentric transformation and the vertices' data
 	float ** weights;
+	BMVert *v_match;
+	BMVert_map *inherit_v_table;
+	BMVert **interp_v_table;			//the vertices for interpolation are those that don't have matches
+										//in the source
 
 	//---for interpolation
 	float (*eff_vert)[3];				//the effective vertices' shapekeys
@@ -554,8 +564,9 @@
 		vertexCos_dst_basis = MEM_mallocN(sizeof(*vertexCos_dst_basis) * num_vert, "vertexCos_dst_basis bmesh_data_transfer.c");
 		vertexCos_dst_offset = MEM_mallocN(sizeof(*vertexCos_dst_offset) * num_vert, "vertexCos_dst_offset bmesh_data_transfer.c");
 
-		interp_vert_ind = MEM_mallocN(sizeof(*interp_vert_ind) * num_vert, "interp_vert_ind bmesh_data_transfer.c");
-		inherit_vert_ind = MEM_mallocN(sizeof(*inherit_vert_ind) * num_vert, "inherit_vert_ind bmesh_data_transfer.c");
+		//table for the inheriting vertices
+		inherit_v_table = MEM_mallocN(sizeof(*inherit_v_table) * num_vert, "inherit_v_table bmesh_data_transfer.c");
+		interp_v_table = MEM_mallocN(sizeof(*interp_v_table) * num_vert, "interp_v_table bmesh_data_transfer.c");
 
 		//getting the cage coordinates is by using
 		//const float (*cagecos)[3];
@@ -586,7 +597,6 @@
 
 		//the way we do it is by looping over each vertex!!
 		for (v = BM_iter_new(&iter, bm_dst, BM_VERTS_OF_MESH, NULL); v; v = BM_iter_step(&iter)) {
-			BMVert *v_match;
 			float tmp1[3];
 
 			//this check may be useless under the current algorithm
@@ -608,11 +618,12 @@
 					//pointing weights to vertexCos_dst_offset[ident_vert - 1]
 					weights[BM_elem_index_get(v)] = vertexCos_dst_offset[ident_vert - 1];
 
-					inherit_vert_ind[ident_vert - 1] = BM_elem_index_get(v);
+					inherit_v_table[ident_vert - 1].v1 = v;
+					inherit_v_table[ident_vert - 1].v2 = v_match;
 				}
 				else {
 					interp_vert++;
-					interp_vert_ind[interp_vert - 1] = BM_elem_index_get(v);
+					interp_v_table[interp_vert - 1] = v;
 				}
 			}
 		}
@@ -625,7 +636,7 @@
 
 		//updating the main vertices in the destination
 		for (k = 0; k < ident_vert; k++) {
-			v = BM_vert_at_index(bm_dst, inherit_vert_ind[k]);
+			v = inherit_v_table[k].v1;
 			add_v3_v3v3(BM_ELEM_CD_GET_VOID_P(v,CD_offset_dst), BM_ELEM_CD_GET_VOID_P(v,CD_basis_dst),
 						(float*) weights[BM_elem_index_get(v)]);
 		}
@@ -646,13 +657,13 @@
 			float weight_accu[3];
 			zero_v3(weight_accu);
 
-			v = BM_vert_at_index(bm_dst, interp_vert_ind[m]);
+			v = interp_v_table[m];
 
 			j = 0;
 			//get the effective vertices
 			for(k = 0; k < ident_vert; k++)
 			{
-				v2 = BM_vert_at_index(bm_dst, inherit_vert_ind[k]);
+				v2 = inherit_v_table[k].v1;
 				len = len_v3v3(v2->co, v->co);
 				if (len <= radius_interp) {
 					num_effective_v++;
@@ -718,14 +729,13 @@
 	MEM_freeN(eff_vert);
 
 	MEM_freeN(weights);
-	MEM_freeN(inherit_vert_ind);
-	MEM_freeN(interp_vert_ind);
+	MEM_freeN(inherit_v_table);
+	MEM_freeN(interp_v_table);
 
-	MEM_freeN(vertexCos_dst_offset);
-
 	MEM_freeN(vertexCos_src_basis);
 	MEM_freeN(vertexCos_src_offset);
 	MEM_freeN(vertexCos_dst_basis);
+	MEM_freeN(vertexCos_dst_offset);
 
 	return true;
 }