[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [44778] trunk/blender/source/blender/bmesh : Speedup for ngon normal calculation
Campbell Barton
ideasman42 at gmail.com
Sat Mar 10 04:25:36 CET 2012
Revision: 44778
http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=44778
Author: campbellbarton
Date: 2012-03-10 03:25:16 +0000 (Sat, 10 Mar 2012)
Log Message:
-----------
Speedup for ngon normal calculation
- BM_mesh_normals_update was looping over all faces to find the largest one, this is no longer needed.
- calculating a face normal was looping over every faces corners twice, now only once - using the loops directly (not an iterator).
- face vert locations were being copied an array, now use directly.
- calculating the normals would copy a float vector for the next point in the face, which was never used (only current and previous used).
- was copying vectors to compute the normal, now just assign the float pointers.
Modified Paths:
--------------
trunk/blender/source/blender/bmesh/bmesh_operator_api.h
trunk/blender/source/blender/bmesh/intern/bmesh_mesh.c
trunk/blender/source/blender/bmesh/intern/bmesh_operators.c
trunk/blender/source/blender/bmesh/intern/bmesh_polygon.c
trunk/blender/source/blender/bmesh/intern/bmesh_private.h
Modified: trunk/blender/source/blender/bmesh/bmesh_operator_api.h
===================================================================
--- trunk/blender/source/blender/bmesh/bmesh_operator_api.h 2012-03-10 03:07:42 UTC (rev 44777)
+++ trunk/blender/source/blender/bmesh/bmesh_operator_api.h 2012-03-10 03:25:16 UTC (rev 44778)
@@ -373,9 +373,6 @@
void *BMO_slot_buffer_elem_first(BMOperator *op, const char *slotname);
-/* restrictmask restricts the iteration to certain element types
- * (e.g. combination of BM_VERT, BM_EDGE, BM_FACE), if iterating
- * over an element buffer (not a mapping).*/
void *BMO_iter_new(BMOIter *iter, BMesh *bm, BMOperator *op,
const char *slotname, const char restrictmask);
void *BMO_iter_step(BMOIter *iter);
Modified: trunk/blender/source/blender/bmesh/intern/bmesh_mesh.c
===================================================================
--- trunk/blender/source/blender/bmesh/intern/bmesh_mesh.c 2012-03-10 03:07:42 UTC (rev 44777)
+++ trunk/blender/source/blender/bmesh/intern/bmesh_mesh.c 2012-03-10 03:25:16 UTC (rev 44778)
@@ -213,25 +213,9 @@
BMIter faces;
BMIter loops;
BMIter edges;
- unsigned int maxlength = 0;
int index;
- float (*projectverts)[3];
float (*edgevec)[3];
-
- /* first, find out the largest face in mesh */
- BM_ITER(f, &faces, bm, BM_FACES_OF_MESH, NULL) {
- if (skip_hidden && BM_elem_flag_test(f, BM_ELEM_HIDDEN))
- continue;
-
- if (f->len > maxlength) maxlength = f->len;
- }
- /* make sure we actually have something to do */
- if (maxlength < 3) return;
-
- /* allocate projectverts array */
- projectverts = MEM_callocN(sizeof(float) * maxlength * 3, "BM normal computation array");
-
/* calculate all face normals */
BM_ITER(f, &faces, bm, BM_FACES_OF_MESH, NULL) {
if (skip_hidden && BM_elem_flag_test(f, BM_ELEM_HIDDEN))
@@ -241,7 +225,7 @@
continue;
#endif
- bmesh_face_normal_update(bm, f, f->no, projectverts);
+ bmesh_face_normal_update(bm, f, f->no);
}
/* Zero out vertex normals */
@@ -314,7 +298,6 @@
}
MEM_freeN(edgevec);
- MEM_freeN(projectverts);
}
/*
Modified: trunk/blender/source/blender/bmesh/intern/bmesh_operators.c
===================================================================
--- trunk/blender/source/blender/bmesh/intern/bmesh_operators.c 2012-03-10 03:07:42 UTC (rev 44777)
+++ trunk/blender/source/blender/bmesh/intern/bmesh_operators.c 2012-03-10 03:25:16 UTC (rev 44778)
@@ -1042,6 +1042,12 @@
return slot->data.buf ? *(void **)slot->data.buf : NULL;
}
+/**
+ * \brief New Iterator
+ *
+ * \param restrictmask restricts the iteration to certain element types
+ * (e.g. combination of BM_VERT, BM_EDGE, BM_FACE), if iterating
+ * over an element buffer (not a mapping). */
void *BMO_iter_new(BMOIter *iter, BMesh *UNUSED(bm), BMOperator *op,
const char *slotname, const char restrictmask)
{
Modified: trunk/blender/source/blender/bmesh/intern/bmesh_polygon.c
===================================================================
--- trunk/blender/source/blender/bmesh/intern/bmesh_polygon.c 2012-03-10 03:07:42 UTC (rev 44777)
+++ trunk/blender/source/blender/bmesh/intern/bmesh_polygon.c 2012-03-10 03:25:16 UTC (rev 44778)
@@ -77,77 +77,84 @@
*/
static void compute_poly_normal(float normal[3], float (*verts)[3], int nverts)
{
+ float const *v_prev = verts[nverts - 1];
+ float const *v_curr = verts[0];
+ float n[3] = {0.0f};
+ int i;
- float u[3], v[3], w[3]; /*, *w, v1[3], v2[3]; */
- float n[3] = {0.0f, 0.0f, 0.0f} /*, l, v1[3], v2[3] */;
- /* double l2; */
- int i /*, s = 0 */;
+ verts[0][0] = 1;
- /* this fixes some weird numerical erro */
- add_v3_fl(verts[0], 0.0001f);
-
- for (i = 0; i < nverts; i++) {
- copy_v3_v3(u, verts[i]);
- copy_v3_v3(v, verts[(i + 1) % nverts]);
- copy_v3_v3(w, verts[(i + 2) % nverts]);
-
-#if 0
- sub_v3_v3v3(v1, w, v);
- sub_v3_v3v3(v2, v, u);
- normalize_v3(v1);
- normalize_v3(v2);
-
- l = dot_v3v3(v1, v2);
- if (fabsf(l - 1.0) < 0.1f) {
- continue;
- }
-#endif
- /* newell's method
- *
- * so thats?:
- * (a[1] - b[1]) * (a[2] + b[2]);
- * a[1] * b[2] - b[1] * a[2] - b[1] * b[2] + a[1] * a[2]
- *
- * odd. half of that is the cross product. . .what's the
- * other half?
- *
- * also could be like a[1] * (b[2] + a[2]) - b[1] * (a[2] - b[2])
- */
-
- n[0] += (u[1] - v[1]) * (u[2] + v[2]);
- n[1] += (u[2] - v[2]) * (u[0] + v[0]);
- n[2] += (u[0] - v[0]) * (u[1] + v[1]);
+ /* Newell's Method */
+ for (i = 0; i < nverts; v_prev = v_curr, v_curr = verts[++i]) {
+ n[0] += (v_prev[1] - v_curr[1]) * (v_prev[2] + v_curr[2]);
+ n[1] += (v_prev[2] - v_curr[2]) * (v_prev[0] + v_curr[0]);
+ n[2] += (v_prev[0] - v_curr[0]) * (v_prev[1] + v_curr[1]);
}
- if (normalize_v3_v3(normal, n) == 0.0f) {
+ if (UNLIKELY(normalize_v3_v3(normal, n) == 0.0f)) {
normal[2] = 1.0f; /* other axis set to 0.0 */
}
+}
-#if 0
- l = len_v3(n);
- /* fast square root, newton/babylonian method:
- * l2 = l * 0.1;
- *
- * l2 = (l / l2 + l2) * 0.5;
- * l2 = (l / l2 + l2) * 0.5;
- * l2 = (l / l2 + l2) * 0.5;
- */
+/**
+ * \brief COMPUTE POLY NORMAL (BMFace)
+ *
+ * Same as #compute_poly_normal but operates directly on a bmesh face.
+ */
+static void bm_face_compute_poly_normal(BMFace *f)
+{
+ BMLoop *l_first = BM_FACE_FIRST_LOOP(f);
+ BMLoop *l_iter = l_first;
+ float const *v_prev = l_first->prev->v->co;
+ float const *v_curr = l_first->v->co;
+ float n[3] = {0.0f};
- if (l == 0.0) {
- normal[0] = 0.0f;
- normal[1] = 0.0f;
- normal[2] = 1.0f;
+ /* Newell's Method */
+ do {
+ n[0] += (v_prev[1] - v_curr[1]) * (v_prev[2] + v_curr[2]);
+ n[1] += (v_prev[2] - v_curr[2]) * (v_prev[0] + v_curr[0]);
+ n[2] += (v_prev[0] - v_curr[0]) * (v_prev[1] + v_curr[1]);
- return;
+ l_iter = l_iter->next;
+ v_prev = v_curr;
+ v_curr = l_iter->v->co;
+
+ } while (l_iter != l_first);
+
+ if (UNLIKELY(normalize_v3_v3(f->no, n) == 0.0f)) {
+ f->no[2] = 1.0f; /* other axis set to 0.0 */
}
- else {
- l = 1.0f / l;
- }
+}
- mul_v3_fl(n, l);
+/**
+ * \brief COMPUTE POLY NORMAL (BMFace)
+ *
+ * Same as #compute_poly_normal and #bm_face_compute_poly_normal
+ * but takes an array of vertex locations.
+ */
+static void bm_face_compute_poly_normal_vcos(BMFace *f, float (*vertexCos)[3])
+{
+ BMLoop *l_first = BM_FACE_FIRST_LOOP(f);
+ BMLoop *l_iter = l_first;
+ float const *v_prev = vertexCos[BM_elem_index_get(l_first->prev->v)];
+ float const *v_curr = vertexCos[BM_elem_index_get(l_first->v)];
+ float n[3] = {0.0f};
- copy_v3_v3(normal, n);
-#endif
+
+ /* Newell's Method */
+ do {
+ n[0] += (v_prev[1] - v_curr[1]) * (v_prev[2] + v_curr[2]);
+ n[1] += (v_prev[2] - v_curr[2]) * (v_prev[0] + v_curr[0]);
+ n[2] += (v_prev[0] - v_curr[0]) * (v_prev[1] + v_curr[1]);
+
+ l_iter = l_iter->next;
+ v_prev = v_curr;
+ v_curr = vertexCos[BM_elem_index_get(l_iter->v)];
+ } while (l_iter != l_first);
+
+ if (UNLIKELY(normalize_v3_v3(f->no, n) == 0.0f)) {
+ f->no[2] = 1.0f; /* other axis set to 0.0 */
+ }
}
/**
@@ -363,28 +370,12 @@
*/
void BM_face_normal_update(BMesh *bm, BMFace *f)
{
- if (f->len >= 3) {
- float (*proj)[3];
-
- BLI_array_fixedstack_declare(proj, BM_NGON_STACK_SIZE, f->len, __func__);
-
- bmesh_face_normal_update(bm, f, f->no, proj);
-
- BLI_array_fixedstack_free(proj);
- }
+ bmesh_face_normal_update(bm, f, f->no);
}
/* same as BM_face_normal_update but takes vertex coords */
void BM_face_normal_update_vcos(BMesh *bm, BMFace *f, float no[3], float (*vertexCos)[3])
{
- if (f->len >= 3) {
- float (*proj)[3];
-
- BLI_array_fixedstack_declare(proj, BM_NGON_STACK_SIZE, f->len, __func__);
-
- bmesh_face_normal_update_vertex_cos(bm, f, no, proj, vertexCos);
-
- BLI_array_fixedstack_free(proj);
- }
+ bmesh_face_normal_update_vertex_cos(bm, f, no, vertexCos);
}
/**
@@ -449,8 +440,7 @@
BM_vert_normal_update(bm, v);
}
-void bmesh_face_normal_update(BMesh *bm, BMFace *f, float no[3],
- float (*projectverts)[3])
+void bmesh_face_normal_update(BMesh *UNUSED(bm), BMFace *f, float no[3])
{
BMLoop *l;
@@ -458,19 +448,21 @@
switch (f->len) {
case 4:
{
- BMVert *v1 = (l = BM_FACE_FIRST_LOOP(f))->v;
- BMVert *v2 = (l = l->next)->v;
- BMVert *v3 = (l = l->next)->v;
- BMVert *v4 = (l->next)->v;
- normal_quad_v3(no, v1->co, v2->co, v3->co, v4->co);
+ const float *co1 = (l = BM_FACE_FIRST_LOOP(f))->v->co;
+ const float *co2 = (l = l->next)->v->co;
+ const float *co3 = (l = l->next)->v->co;
+ const float *co4 = (l->next)->v->co;
+
+ normal_quad_v3(no, co1, co2, co3, co4);
break;
}
case 3:
{
- BMVert *v1 = (l = BM_FACE_FIRST_LOOP(f))->v;
- BMVert *v2 = (l = l->next)->v;
- BMVert *v3 = (l->next)->v;
- normal_tri_v3(no, v1->co, v2->co, v3->co);
+ const float *co1 = (l = BM_FACE_FIRST_LOOP(f))->v->co;
+ const float *co2 = (l = l->next)->v->co;
+ const float *co3 = (l->next)->v->co;
+
+ normal_tri_v3(no, co1, co2, co3);
break;
}
case 0:
@@ -480,20 +472,14 @@
}
default:
{
- BMIter iter;
- int i = 0;
- BM_ITER(l, &iter, bm, BM_LOOPS_OF_FACE, f) {
- copy_v3_v3(projectverts[i], l->v->co);
- i += 1;
- }
- compute_poly_normal(no, projectverts, f->len);
+ bm_face_compute_poly_normal(f);
break;
}
}
}
/* exact same as 'bmesh_face_normal_update' but accepts vertex coords */
void bmesh_face_normal_update_vertex_cos(BMesh *bm, BMFace *f, float no[3],
- float (*projectverts)[3], float (*vertexCos)[3])
+ float (*vertexCos)[3])
{
BMLoop *l;
@@ -504,26 +490,21 @@
switch (f->len) {
case 4:
{
- BMVert *v1 = (l = BM_FACE_FIRST_LOOP(f))->v;
- BMVert *v2 = (l = l->next)->v;
- BMVert *v3 = (l = l->next)->v;
- BMVert *v4 = (l->next)->v;
- normal_quad_v3(no,
- vertexCos[BM_elem_index_get(v1)],
- vertexCos[BM_elem_index_get(v2)],
- vertexCos[BM_elem_index_get(v3)],
- vertexCos[BM_elem_index_get(v4)]);
+ const float *co1 = vertexCos[BM_elem_index_get((l = BM_FACE_FIRST_LOOP(f))->v)];
+ const float *co2 = vertexCos[BM_elem_index_get((l = l->next)->v)];
+ const float *co3 = vertexCos[BM_elem_index_get((l = l->next)->v)];
+ const float *co4 = vertexCos[BM_elem_index_get((l->next)->v)];
+
+ normal_quad_v3(no, co1, co2, co3, co4);
break;
}
case 3:
{
- BMVert *v1 = (l = BM_FACE_FIRST_LOOP(f))->v;
- BMVert *v2 = (l = l->next)->v;
- BMVert *v3 = (l->next)->v;
- normal_tri_v3(no,
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list