[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [48181] branches/soc-2012-sushi/source/ blender: The operator bmo_vertexsmoothlaplacian now work with quads and triangles.

Alexander Pinzon apinzonf at gmail.com
Fri Jun 22 00:39:33 CEST 2012


Revision: 48181
          http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=48181
Author:   apinzonf
Date:     2012-06-21 22:39:26 +0000 (Thu, 21 Jun 2012)
Log Message:
-----------
The operator bmo_vertexsmoothlaplacian now work with quads and triangles.
The algorithm was changed for best performance.

Modified Paths:
--------------
    branches/soc-2012-sushi/source/blender/bmesh/operators/bmo_smooth_laplacian.c
    branches/soc-2012-sushi/source/blender/editors/mesh/editmesh_tools.c

Modified: branches/soc-2012-sushi/source/blender/bmesh/operators/bmo_smooth_laplacian.c
===================================================================
--- branches/soc-2012-sushi/source/blender/bmesh/operators/bmo_smooth_laplacian.c	2012-06-21 20:14:27 UTC (rev 48180)
+++ branches/soc-2012-sushi/source/blender/bmesh/operators/bmo_smooth_laplacian.c	2012-06-21 22:39:26 UTC (rev 48181)
@@ -47,88 +47,332 @@
 #define SMOOTH_LAPLACIAN_AREA_FACTOR 4.0f
 #define SMOOTH_LAPLACIAN_EDGE_FACTOR 2.0f
 
+struct BBMOLaplacianSystem {
+	float *eweights;		/* Length weights per Edge */
+	float (*fweights)[3];   /* Cotangent weights per face */
+	float *ring_areas;		/* Total area per ring*/
+	float *vlengths;		/* Total sum of lengths(edges) per vertice*/
+	float *vweights;		/* Total sum of weights per vertice*/
+	int numEdges;			/* Number of edges*/
+	int numFaces;			/* Number of faces*/
+	int numVerts;			/* Number of verts*/
+	short *zerola;			/* Is zero area or length*/
+
+	/* Pointers to data*/
+	BMesh *bm;
+	BMOperator *op;
+	NLContext *context;
+
+	/*Data*/
+	float min_area;
+};
+typedef struct BBMOLaplacianSystem BMOLaplacianSystem;
+
 static float cotan_weight(float *v1, float *v2, float *v3);
 int vert_is_boundary(BMVert *v);
-void compute_weights_in_ring(BMVert *v, float lambda, float min_area);
-void compute_weights_in_border(BMVert *v, float lambda, float min_area);
 float compute_volume(BMesh *bm, BMOperator *op);
 void volume_preservation(BMesh *bm, BMOperator *op, float vini, float vend, int usex, int usey, int usez);
+static void init_laplacian(BMOLaplacianSystem * sys);
+static void fill_laplacian_matrix(BMOLaplacianSystem * sys);
+static void delete_void_MLS(void * data);
+static void delete_BMOLaplacianSystem(BMOLaplacianSystem * sys);
+static void memset_BMOLaplacianSystem(BMOLaplacianSystem *sys, int val);
+static BMOLaplacianSystem * init_BMOLaplacianSystem( int a_numEdges, int a_numFaces, int a_numVerts);
 
-void bmo_vertexsmoothlaplacian_exec(BMesh *bm, BMOperator *op)
+static void delete_void_MLS(void * data)
 {
-	int i;
-	int m_vertex_id;
-	int usex, usey, usez;
-	float lambda, lambda_border, min_area;
-	float vini, vend;
-	BMOIter siter;
-	BMVert *v;
-	NLContext *context;
+	if (data) {
+		MEM_freeN(data);
+		data = NULL;
+	}
+}
 
-	BM_mesh_elem_index_ensure(bm, BM_VERT);
-	lambda = BMO_slot_float_get(op, "lambda");
-	lambda_border = BMO_slot_float_get(op, "lambda_border");
-	min_area = BMO_slot_float_get(op, "min_area");
-	usex = BMO_slot_bool_get(op, "use_x");
-	usey = BMO_slot_bool_get(op, "use_y");
-	usez = BMO_slot_bool_get(op, "use_z");
+static void delete_BMOLaplacianSystem(BMOLaplacianSystem * sys) 
+{
+	delete_void_MLS(sys->eweights);
+	delete_void_MLS(sys->fweights);
+	delete_void_MLS(sys->ring_areas);
+	delete_void_MLS(sys->vlengths);
+	delete_void_MLS(sys->vweights);
+	delete_void_MLS(sys->zerola);
+	if (sys->context) {
+		nlDeleteContext(sys->context);
+	}
+	sys->bm = NULL;
+	sys->op = NULL;
+	MEM_freeN(sys);
+}
 
-	nlNewContext();
-	context = nlGetCurrent();
+static void memset_BMOLaplacianSystem(BMOLaplacianSystem *sys, int val)
+{
+	memset(sys->eweights	, val, sizeof(float) * sys->numEdges);
+	memset(sys->fweights	, val, sizeof(float) * sys->numFaces * 3);
+	memset(sys->ring_areas	, val, sizeof(float) * sys->numVerts);
+	memset(sys->vlengths	, val, sizeof(float) * sys->numVerts);
+	memset(sys->vweights	, val, sizeof(float) * sys->numVerts);
+	memset(sys->zerola		, val, sizeof(short) * sys->numVerts);
+}
 
-	nlSolverParameteri(NL_NB_VARIABLES, bm->totvert);
-	nlSolverParameteri(NL_LEAST_SQUARES, NL_TRUE);
-	nlSolverParameteri(NL_NB_ROWS, bm->totvert);
-	nlSolverParameteri(NL_NB_RIGHT_HAND_SIDES, 3);
+static BMOLaplacianSystem * init_BMOLaplacianSystem( int a_numEdges, int a_numFaces, int a_numVerts) 
+{
+	BMOLaplacianSystem * sys; 
+	sys = MEM_callocN(sizeof(BMOLaplacianSystem), "ModLaplSmoothSystem");
+	sys->numEdges = a_numEdges;
+	sys->numFaces = a_numFaces;
+	sys->numVerts = a_numVerts;
 
-	nlBegin(NL_SYSTEM);	
-	for (i=0; i < bm->totvert; i++) {
-		nlLockVariable(i);
+	sys->eweights =  MEM_callocN(sizeof(float) * sys->numEdges, "ModLaplSmoothEWeight");
+	if (!sys->eweights) {
+		delete_BMOLaplacianSystem(sys);
+		return NULL;
 	}
-	BMO_ITER (v, &siter, bm, op, "verts", BM_VERT) {
-		m_vertex_id = BM_elem_index_get(v);
-		nlUnlockVariable(m_vertex_id);
-		nlSetVariable(0,m_vertex_id, v->co[0]);
-		nlSetVariable(1,m_vertex_id, v->co[1]);
-		nlSetVariable(2,m_vertex_id, v->co[2]);
+	
+	sys->fweights =  MEM_callocN(sizeof(float) * 3 * sys->numFaces, "ModLaplSmoothFWeight");
+	if (!sys->fweights) {
+		delete_BMOLaplacianSystem(sys);
+		return NULL;
 	}
+	
+	sys->ring_areas =  MEM_callocN(sizeof(float) * sys->numVerts, "ModLaplSmoothRingAreas");
+	if (!sys->ring_areas) {
+		delete_BMOLaplacianSystem(sys);
+		return NULL;
+	}
+	
+	sys->vlengths =  MEM_callocN(sizeof(float) * sys->numVerts, "ModLaplSmoothVlengths");
+	if (!sys->vlengths) {
+		delete_BMOLaplacianSystem(sys);
+		return NULL;
+	}
 
-	nlBegin(NL_MATRIX);
-	BMO_ITER (v, &siter, bm, op, "verts", BM_VERT) {
-		m_vertex_id = BM_elem_index_get(v);
-		nlRightHandSideAdd(0, m_vertex_id, v->co[0]);
-		nlRightHandSideAdd(1, m_vertex_id, v->co[1]);
-		nlRightHandSideAdd(2, m_vertex_id, v->co[2]);
-		if (vert_is_boundary(v) == 0) {
-			compute_weights_in_ring(v, lambda, min_area);
-		}else{
-			compute_weights_in_border(v, lambda_border, min_area);
+	sys->vweights =  MEM_callocN(sizeof(float) * sys->numVerts, "ModLaplSmoothVweights");
+	if (!sys->vweights) {
+		delete_BMOLaplacianSystem(sys);
+		return NULL;
+	}
+
+	sys->zerola =  MEM_callocN(sizeof(short) * sys->numVerts, "ModLaplSmoothZeloa");
+	if (!sys->zerola) {
+		delete_BMOLaplacianSystem(sys);
+		return NULL;
+	}
+
+	return sys;
+}
+
+/* Compute weigth between vertice v_i and all your neighbors
+ * weight between v_i and v_neighbor 
+ * Wij = cot(alpha) + cot(beta) / (4.0 * total area of all faces  * sum all weight)
+ *        v_i *
+ *          / | \
+ *         /  |  \
+ *  v_beta*   |   * v_alpha
+ *         \  |  /
+ *          \ | /
+ *            * v_neighbor
+*/
+
+static void init_laplacian(BMOLaplacianSystem * sys)
+{
+	float *v1, *v2, *v3, *v4;
+	float w1, w2, w3, w4;
+	float areaf;
+	int i, j;
+	unsigned int idv1, idv2, idv3, idv4, idv[4];
+	int has_4_vert ;
+	BMEdge *e;
+	BMFace *f;
+	BMIter eiter;
+	BMIter fiter;
+	BMIter vi;
+	BMVert *vn;
+	BMVert *vf[4];
+
+	BM_ITER_MESH_INDEX (e, &eiter, sys->bm, BM_EDGES_OF_MESH, j) {
+		if (!BM_elem_flag_test(e, BM_ELEM_SELECT) && BM_edge_is_boundary(e)) {
+			v1 = e->v1->co;
+			v2 =  e->v2->co;
+			idv1 = BM_elem_index_get(e->v1);
+			idv2 = BM_elem_index_get(e->v2);
+			
+			w1 = len_v3v3(v1, v2);
+			if (w1 > sys->min_area) {
+				w1 = 1.0f / w1;
+				i = BM_elem_index_get(e);
+				sys->eweights[i] = w1;
+				sys->vlengths[idv1] += w1;
+				sys->vlengths[idv2] += w1;
+			}else{
+				sys->zerola[idv1] = 1;
+				sys->zerola[idv2] = 1;
+			}
 		}
-		
 	}
-		
-	nlEnd(NL_MATRIX);
-	nlEnd(NL_SYSTEM);
 
-	if (nlSolveAdvanced(NULL, NL_TRUE) ) {
-		vini = compute_volume(bm, op);
-		BMO_ITER (v, &siter, bm, op, "verts", BM_VERT) {
-			m_vertex_id = BM_elem_index_get(v);
-			if(usex){
-				v->co[0] =  nlGetVariable(0, m_vertex_id);
+	BM_ITER_MESH (f, &fiter, sys->bm, BM_FACES_OF_MESH) {
+		if (BM_elem_flag_test(f, BM_ELEM_SELECT)) {
+
+			BM_ITER_ELEM_INDEX (vn, &vi, f, BM_VERTS_OF_FACE, i) {
+				vf[i] = vn;
 			}
-			if(usey){
-				v->co[1] =  nlGetVariable(1, m_vertex_id);
+			has_4_vert = (i == 4) ? 1 : 0;
+			idv1 = BM_elem_index_get(vf[0]);
+			idv2 = BM_elem_index_get(vf[1]);
+			idv3 = BM_elem_index_get(vf[2]);
+			idv4 = has_4_vert ? BM_elem_index_get(vf[3]) : 0;
+
+			v1 = vf[0]->co;
+			v2 = vf[1]->co;
+			v3 = vf[2]->co;
+			v4 = has_4_vert ? vf[3]->co : 0;
+
+			if (has_4_vert) {
+				areaf = area_quad_v3(v1, v2, v3, v4);
+			} else {
+				areaf = area_tri_v3(v1, v2, v3);
 			}
-			if(usez){
-				v->co[2] =  nlGetVariable(2, m_vertex_id);
+
+			if (fabs(areaf) < sys->min_area) { 
+				sys->zerola[idv1] = 1;
+				sys->zerola[idv2] = 1;
+				sys->zerola[idv3] = 1;
+				if (has_4_vert) sys->zerola[idv4] = 1;
 			}
+
+			sys->ring_areas[idv1] += areaf;
+			sys->ring_areas[idv2] += areaf;
+			sys->ring_areas[idv3] += areaf;
+			if (has_4_vert) sys->ring_areas[idv4] += areaf;
+
+			if (has_4_vert) {
+			
+				idv[0] = idv1;
+				idv[1] = idv2;
+				idv[2] = idv3;
+				idv[3] = idv4;
+
+				for (j = 0; j < 4; j++) {
+					idv1 = idv[j];
+					idv2 = idv[(j + 1) % 4];
+					idv3 = idv[(j + 2) % 4];
+					idv4 = idv[(j + 3) % 4];
+
+					v1 = vf[j]->co;
+					v2 = vf[(j + 1) % 4]->co;
+					v3 = vf[(j + 2) % 4]->co;
+					v4 = vf[(j + 3) % 4]->co;
+
+					w2 = cotan_weight(v4, v1, v2) + cotan_weight(v3, v1, v2);
+					w3 = cotan_weight(v2, v3, v1) + cotan_weight(v4, v1, v3);
+					w4 = cotan_weight(v2, v4, v1) + cotan_weight(v3, v4, v1);
+	
+					sys->vweights[idv1] += (w2 + w3 + w4) / 4.0f;
+				}
+			} else {			
+				i = BM_elem_index_get(f);
+
+				w1 = cotan_weight(v1, v2, v3);
+				w2 = cotan_weight(v2, v3, v1);
+				w3 = cotan_weight(v3, v1, v2);
+
+				sys->fweights[i][0] += w1;
+				sys->fweights[i][1] += w2;
+				sys->fweights[i][2] += w3;
+			
+				sys->vweights[idv1] += w2 + w3;
+				sys->vweights[idv2] += w1 + w3;
+				sys->vweights[idv3] += w1 + w2;
+			}
 		}
-		vend = compute_volume(bm, op);
-		volume_preservation(bm, op, vini, vend, usex, usey, usez);
 	}
+}
+
+static void fill_laplacian_matrix(BMOLaplacianSystem * sys)
+{
+	float *v1, *v2, *v3, *v4;
+	float w2, w3, w4;
+	int i, j;
+	int has_4_vert ;
+	unsigned int idv1, idv2, idv3, idv4, idv[4];
+
+	BMEdge *e;
+	BMFace *f;
+	BMIter eiter;
+	BMIter fiter;
+	BMIter vi;
+	BMVert *vn;
+	BMVert *vf[4];
+
+	BM_ITER_MESH (f, &fiter, sys->bm, BM_FACES_OF_MESH) {
+		if (BM_elem_flag_test(f, BM_ELEM_SELECT)) {
+			BM_ITER_ELEM_INDEX (vn, &vi, f, BM_VERTS_OF_FACE, i) {
+				vf[i] = vn;
+			}
+			has_4_vert = (i == 4) ? 1 : 0;
+			if (has_4_vert) {
+				idv[0] = BM_elem_index_get(vf[0]);
+				idv[1] = BM_elem_index_get(vf[1]);
+				idv[2] = BM_elem_index_get(vf[2]);
+				idv[3] = BM_elem_index_get(vf[3]);
+				for (j = 0; j < 4; j++) {
+					idv1 = idv[j];
+					idv2 = idv[(j + 1) % 4];
+					idv3 = idv[(j + 2) % 4];
+					idv4 = idv[(j + 3) % 4];
+
+					v1 = vf[j]->co;
+					v2 = vf[(j + 1) % 4]->co;
+					v3 = vf[(j + 2) % 4]->co;
+					v4 = vf[(j + 3) % 4]->co;
+
+					w2 = cotan_weight(v4, v1, v2) + cotan_weight(v3, v1, v2);
+					w3 = cotan_weight(v2, v3, v1) + cotan_weight(v4, v1, v3);

@@ Diff output truncated at 10240 characters. @@



More information about the Bf-blender-cvs mailing list