[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [47298] branches/soc-2012-sushi/source/ blender/bmesh/operators/bmo_smooth_laplacian.c: Optimizing the code to reduce the number of accesses and loops to the structure .
Alexander Pinzon
apinzonf at gmail.com
Thu May 31 22:50:09 CEST 2012
Revision: 47298
http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=47298
Author: apinzonf
Date: 2012-05-31 20:50:08 +0000 (Thu, 31 May 2012)
Log Message:
-----------
Optimizing the code to reduce the number of accesses and loops to the structure.
Modified Paths:
--------------
branches/soc-2012-sushi/source/blender/bmesh/operators/bmo_smooth_laplacian.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-05-31 20:26:42 UTC (rev 47297)
+++ branches/soc-2012-sushi/source/blender/bmesh/operators/bmo_smooth_laplacian.c 2012-05-31 20:50:08 UTC (rev 47298)
@@ -43,150 +43,68 @@
#include "intern/bmesh_operators_private.h" /* own include */
-void init_index(BMesh *bm);
-void compute_weight(BMFace *f, int vid, float lambda);
-float compute_weight_return( BMFace *f, int vid, float lambda);
+#define SMOOTH_LAPLACIAN_AREA_FACTOR 4.0f
+
static float cotan_weight(float *v1, float *v2, float *v3);
-float area_ring(BMVert *v);
+void compute_weights_in_ring(BMVert *v, float lambda);
void bmo_vertexsmoothlaplacian_exec(BMesh *bm, BMOperator *op)
{
+ int i;
+ int m_vertex_id;
+ float lambda;
BMOIter siter;
- BMIter iter;
BMVert *v;
- BMFace *f;
- int m_vertex_id;
NLContext *context;
- float lambda = BMO_slot_float_get(op, "lambda");
- float we;
- int i;
- init_index(bm);
-
- nlNewContext();
- context = nlGetCurrent();
- 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);
- nlBegin(NL_SYSTEM);
-
- for(i=0; i<bm->totvert; i++){
- nlLockVariable(i);
- }
- 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]);
- }
- 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]);
-
- nlMatrixAdd(m_vertex_id, m_vertex_id, 1.0f);
-
- we = 0.0f;
- BM_ITER_ELEM (f, &iter, v, BM_FACES_OF_VERT) {
- we = we + compute_weight_return(f,m_vertex_id, lambda);
- }
- we = lambda/(we*4.0f*area_ring(v));
- BM_ITER_ELEM (f, &iter, v, BM_FACES_OF_VERT) {
- compute_weight(f,m_vertex_id, we);
- }
- nlMatrixAdd(m_vertex_id, m_vertex_id, lambda/(4.0f*area_ring(v)));
- }
-
- nlEnd(NL_MATRIX);
- nlEnd(NL_SYSTEM);
- if(bm->totvert <32){
- nlPrintMatrix();
- }
- nlSolveAdvanced(NULL, NL_TRUE);
- BMO_ITER (v, &siter, bm, op, "verts", BM_VERT) {
- m_vertex_id = BM_elem_index_get(v);
- v->co[0] = nlGetVariable(0, m_vertex_id);
- v->co[1] = nlGetVariable(1, m_vertex_id);
- v->co[2] = nlGetVariable(2, m_vertex_id);
- }
-
- nlDeleteContext(context);
-}
-
-void init_index(BMesh *bm){
BM_mesh_elem_index_ensure(bm, BM_VERT);
-}
+ lambda = BMO_slot_float_get(op, "lambda");
+ nlNewContext();
+ context = nlGetCurrent();
-/*
- * v_i *
- * / | \
- * / | \
- * v_beta* | * v_alpha
- * \ | /
- * \ | /
- * * v_neighbor
-*/
-void compute_weight( BMFace *f, int vid, float lambda){
- BMIter iter;
- BMVert *v;
- BMVert *vf[3];
- int i;
- float wa = 0.0f;
- i = 0;
- BM_ITER_ELEM (v, &iter, f, BM_VERTS_OF_FACE) {
- vf[i] = v;
- i = i + 1;
+ 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);
+
+ nlBegin(NL_SYSTEM);
+ for (i=0; i < bm->totvert; i++) {
+ nlLockVariable(i);
}
-
- for(i=0; i<3; i++){
- int va = i;
- int vb = (i+1)%3;
- int vc = (i+2)%3;
- int va_id = BM_elem_index_get(vf[va]);
- int vb_id = BM_elem_index_get(vf[vb]);
- int vc_id = BM_elem_index_get(vf[vc]);
- if(va_id == vid ){
- int vb_id = BM_elem_index_get(vf[vb]);
- int vc_id = BM_elem_index_get(vf[vc]);
- wa = lambda*cotan_weight(vf[vb]->co, vf[vc]->co, vf[va]->co);
- nlMatrixAdd(vid, vc_id, -wa);
- wa = lambda*cotan_weight(vf[vc]->co, vf[va]->co, vf[vb]->co);
- nlMatrixAdd(vid, vb_id, -wa);
- }
+ 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]);
}
-}
-float compute_weight_return( BMFace *f, int vid, float lambda){
- BMIter iter;
- BMVert *v;
- BMVert *vf[3];
- int i;
- float wa = 0.0f;
- i = 0;
- BM_ITER_ELEM (v, &iter, f, BM_VERTS_OF_FACE) {
- vf[i] = v;
- i = i + 1;
+ 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]);
+ compute_weights_in_ring(v, lambda);
}
-
- for(i=0; i<3; i++){
- int va = i;
- int vb = (i+1)%3;
- int vc = (i+2)%3;
- int va_id = BM_elem_index_get(vf[va]);
- int vb_id = BM_elem_index_get(vf[vb]);
- int vc_id = BM_elem_index_get(vf[vc]);
- if(va_id == vid ){
- int vb_id = BM_elem_index_get(vf[vb]);
- int vc_id = BM_elem_index_get(vf[vc]);
- wa = cotan_weight(vf[vb]->co, vf[vc]->co, vf[va]->co);
- wa = wa + cotan_weight(vf[vc]->co, vf[va]->co, vf[vb]->co);
- }
+
+ nlEnd(NL_MATRIX);
+ nlEnd(NL_SYSTEM);
+
+ if(bm->totvert <32){
+ nlPrintMatrix();
}
- return wa;
+
+ nlSolveAdvanced(NULL, NL_TRUE);
+
+ BMO_ITER (v, &siter, bm, op, "verts", BM_VERT) {
+ m_vertex_id = BM_elem_index_get(v);
+ v->co[0] = nlGetVariable(0, m_vertex_id);
+ v->co[1] = nlGetVariable(1, m_vertex_id);
+ v->co[2] = nlGetVariable(2, m_vertex_id);
+ }
+
+ nlDeleteContext(context);
}
static float cotan_weight(float *v1, float *v2, float *v3)
@@ -205,24 +123,86 @@
return dot_v3v3(a, b) / clen;
}
-float area_ring(BMVert *v){
- BMIter fiter;
- BMIter viter;
- BMVert *vn;
+/* 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
+*/
+void compute_weights_in_ring(BMVert *v, float lambda)
+{
+ float area = 0.0f;
+ float factor;
+ float sumw = 0.0f;
+ float w1, w2;
+ float *weight = NULL;
+ int ai, bi, ci;
+ int id1, id2, id3;
+ int i, j;
+ int * index = NULL;
+ BMIter fi;
+ BMIter vi;
BMFace *f;
+ BMVert *vn;
BMVert *vf[3];
- int i;
- float area = 0.0f;
- BM_ITER_ELEM (f, &fiter, v, BM_FACES_OF_VERT) {
+
+ BLI_array_declare(index);
+ BLI_array_declare(weight);
+
+ if (v == NULL) {
+ return;
+ }
+
+ id1 = BM_elem_index_get(v);
+ j = 0;
+ BM_ITER_ELEM (f, &fi, v, BM_FACES_OF_VERT) {
i = 0;
- BM_ITER_ELEM (vn, &viter, f, BM_VERTS_OF_FACE) {
+ ai = -1;
+ BM_ITER_ELEM (vn, &vi, f, BM_VERTS_OF_FACE) {
vf[i] = vn;
+ if (BM_elem_index_get (vf[i]) == id1) {
+ ai = i;
+ bi = (i + 1) % 3;
+ ci = (i + 2) % 3;
+ }
i = i + 1;
}
- if(i == 3){
+ if (i == 3 && ai > -1){
area = area + area_tri_v3(vf[0]->co, vf[1]->co, vf[2]->co);
+ w1 = cotan_weight (vf[bi]->co, vf[ci]->co, vf[ai]->co);
+ w2 = cotan_weight (vf[ci]->co, vf[ai]->co, vf[bi]->co);
+ id2 = BM_elem_index_get (vf[bi]);
+ id3 = BM_elem_index_get (vf[ci]);
+ BLI_array_grow_one (index);
+ BLI_array_grow_one (weight);
+ index[j] = id3;
+ weight[j] = w1;
+ j = j + 1;
+ BLI_array_grow_one (index);
+ BLI_array_grow_one (weight);
+ index[j] = id2;
+ weight[j] = w2;
+ sumw = sumw + w1 + w2;
+ j = j + 1;
}
}
- return area;
+ for(i = 0; i < j; i = i + 2){
+ factor = lambda / (SMOOTH_LAPLACIAN_AREA_FACTOR * sumw * area);
+ w1 = -factor * weight[i];
+ w2 = -factor * weight[i+1];
+ id2 = index[i];
+ id3 = index[i+1];
+ nlMatrixAdd(id1, id2, w1);
+ nlMatrixAdd(id1, id3, w2);
+ }
+ nlMatrixAdd(id1, id1, 1.0f + lambda / (SMOOTH_LAPLACIAN_AREA_FACTOR * area));
+ BLI_array_free(index);
+ BLI_array_free(weight);
+
}
\ No newline at end of file
More information about the Bf-blender-cvs
mailing list