[Bf-blender-cvs] [496045fc30f] master: BMesh: simplify normal calculation, resolve partial update error
Campbell Barton
noreply at git.blender.org
Tue Jun 8 09:16:29 CEST 2021
Commit: 496045fc30f72be8d2ca32394ed233266f043152
Author: Campbell Barton
Date: Tue Jun 8 15:54:21 2021 +1000
Branches: master
https://developer.blender.org/rB496045fc30f72be8d2ca32394ed233266f043152
BMesh: simplify normal calculation, resolve partial update error
Simplify vertex normal calculation by moving the main normal
accumulation function to operate on vertices instead of faces.
Using faces had the down side that it needed to zero, accumulate and
normalize the vertex normals in 3 separate passes, accumulating also
needed a spin-lock for thread since the face would write it's normal
to all of it's vertices which could be shared with other faces.
Now a single loop over vertices is performed without locking.
This gives 5-6% speedup calculating all normals.
This also simplifies partial updates, fixing a problem where
all connected faces were being read from when calculating normals.
While this could have been resolved separately,
it's simpler to operate on vertices directly.
===================================================================
M source/blender/bmesh/intern/bmesh_mesh_normals.c
M source/blender/bmesh/intern/bmesh_mesh_partial_update.c
M source/blender/bmesh/intern/bmesh_mesh_partial_update.h
===================================================================
diff --git a/source/blender/bmesh/intern/bmesh_mesh_normals.c b/source/blender/bmesh/intern/bmesh_mesh_normals.c
index e5501100ce3..f0a791bae19 100644
--- a/source/blender/bmesh/intern/bmesh_mesh_normals.c
+++ b/source/blender/bmesh/intern/bmesh_mesh_normals.c
@@ -35,8 +35,6 @@
#include "BKE_global.h"
#include "BKE_mesh.h"
-#include "atomic_ops.h"
-
#include "intern/bmesh_private.h"
/* -------------------------------------------------------------------- */
@@ -59,19 +57,28 @@ typedef struct BMEdgesCalcVectorsData {
float (*edgevec)[3];
} BMEdgesCalcVectorsData;
-static void mesh_edges_calc_vectors_cb(void *userdata, MempoolIterData *mp_e)
+static void bm_edge_calc_vectors_cb(void *userdata, MempoolIterData *mp_e)
{
- BMEdgesCalcVectorsData *data = userdata;
BMEdge *e = (BMEdge *)mp_e;
-
- if (e->l) {
- const float *v1_co = data->vcos ? data->vcos[BM_elem_index_get(e->v1)] : e->v1->co;
- const float *v2_co = data->vcos ? data->vcos[BM_elem_index_get(e->v2)] : e->v2->co;
- sub_v3_v3v3(data->edgevec[BM_elem_index_get(e)], v2_co, v1_co);
- normalize_v3(data->edgevec[BM_elem_index_get(e)]);
+ /* The edge vector will not be needed when the edge has no radial. */
+ if (e->l != NULL) {
+ float(*edgevec)[3] = userdata;
+ float *e_diff = edgevec[BM_elem_index_get(e)];
+ sub_v3_v3v3(e_diff, e->v2->co, e->v1->co);
+ normalize_v3(e_diff);
}
- else {
- /* the edge vector will not be needed when the edge has no radial */
+}
+
+static void bm_edge_calc_vectors_with_coords_cb(void *userdata, MempoolIterData *mp_e)
+{
+ BMEdge *e = (BMEdge *)mp_e;
+ /* The edge vector will not be needed when the edge has no radial. */
+ if (e->l != NULL) {
+ BMEdgesCalcVectorsData *data = userdata;
+ float *e_diff = data->edgevec[BM_elem_index_get(e)];
+ sub_v3_v3v3(
+ e_diff, data->vcos[BM_elem_index_get(e->v2)], data->vcos[BM_elem_index_get(e->v1)]);
+ normalize_v3(e_diff);
}
}
@@ -79,118 +86,123 @@ static void bm_mesh_edges_calc_vectors(BMesh *bm, float (*edgevec)[3], const flo
{
BM_mesh_elem_index_ensure(bm, BM_EDGE | (vcos ? BM_VERT : 0));
- BMEdgesCalcVectorsData data = {
- .vcos = vcos,
- .edgevec = edgevec,
- };
-
- BM_iter_parallel(
- bm, BM_EDGES_OF_MESH, mesh_edges_calc_vectors_cb, &data, bm->totedge >= BM_OMP_LIMIT);
+ if (vcos == NULL) {
+ BM_iter_parallel(
+ bm, BM_EDGES_OF_MESH, bm_edge_calc_vectors_cb, edgevec, bm->totedge >= BM_OMP_LIMIT);
+ }
+ else {
+ BMEdgesCalcVectorsData data = {
+ .edgevec = edgevec,
+ .vcos = vcos,
+ };
+ BM_iter_parallel(bm,
+ BM_EDGES_OF_MESH,
+ bm_edge_calc_vectors_with_coords_cb,
+ &data,
+ bm->totedge >= BM_OMP_LIMIT);
+ }
}
-typedef struct BMVertsCalcNormalsData {
+typedef struct BMVertsCalcNormalsWithCoordsData {
/* Read-only data. */
const float (*fnos)[3];
const float (*edgevec)[3];
const float (*vcos)[3];
- /* Read-write data, protected by an atomic-based fake spin-lock like system. */
+ /* Write data. */
float (*vnos)[3];
-} BMVertsCalcNormalsData;
+} BMVertsCalcNormalsWithCoordsData;
-static void mesh_verts_calc_normals_accum(
- BMFace *f,
- const float *f_no,
- const float (*edgevec)[3],
-
- /* Read-write data, protected by an atomic-based fake spin-lock like system. */
- float (*vnos)[3])
+BLI_INLINE void bm_vert_calc_normals_accum_loop(const BMLoop *l_iter,
+ const float (*edgevec)[3],
+ const float f_no[3],
+ float v_no[3])
{
-#define FLT_EQ_NONAN(_fa, _fb) (*((const uint32_t *)&_fa) == *((const uint32_t *)&_fb))
-
- BMLoop *l_first, *l_iter;
- l_iter = l_first = BM_FACE_FIRST_LOOP(f);
- do {
- const float *e1diff, *e2diff;
- float dotprod;
- float fac;
-
- /* calculate the dot product of the two edges that
- * meet at the loop's vertex */
- e1diff = edgevec[BM_elem_index_get(l_iter->prev->e)];
- e2diff = edgevec[BM_elem_index_get(l_iter->e)];
- dotprod = dot_v3v3(e1diff, e2diff);
-
- /* edge vectors are calculated from e->v1 to e->v2, so
- * adjust the dot product if one but not both loops
- * actually runs from from e->v2 to e->v1 */
- if ((l_iter->prev->e->v1 == l_iter->prev->v) ^ (l_iter->e->v1 == l_iter->v)) {
- dotprod = -dotprod;
- }
-
- fac = saacos(-dotprod);
-
- if (fac != fac) { /* NAN detection. */
- /* Degenerated case, nothing to do here, just ignore that vertex. */
- continue;
- }
+ /* Calculate the dot product of the two edges that meet at the loop's vertex. */
+ const float *e1diff = edgevec[BM_elem_index_get(l_iter->prev->e)];
+ const float *e2diff = edgevec[BM_elem_index_get(l_iter->e)];
+ /* Edge vectors are calculated from e->v1 to e->v2, so adjust the dot product if one but not
+ * both loops actually runs from from e->v2 to e->v1. */
+ float dotprod = dot_v3v3(e1diff, e2diff);
+ if ((l_iter->prev->e->v1 == l_iter->prev->v) ^ (l_iter->e->v1 == l_iter->v)) {
+ dotprod = -dotprod;
+ }
+ const float fac = saacos(-dotprod);
+ /* NAN detection, otherwise this is a degenerated case, ignore that vertex in this case. */
+ if (fac == fac) { /* NAN detection. */
+ madd_v3_v3fl(v_no, f_no, fac);
+ }
+}
- /* accumulate weighted face normal into the vertex's normal */
- float *v_no = vnos ? vnos[BM_elem_index_get(l_iter->v)] : l_iter->v->no;
-
- /* This block is a lockless threadsafe madd_v3_v3fl.
- * It uses the first float of the vector as a sort of cheap spin-lock,
- * assuming FLT_MAX is a safe 'illegal' value that cannot be set here otherwise.
- * It also assumes that collisions between threads are highly unlikely,
- * else performances would be quite bad here. */
- float virtual_lock = v_no[0];
- while (true) {
- /* This loops until following conditions are met:
- * - v_no[0] has same value as virtual_lock (i.e. it did not change since last try).
- * - v_no[0] was not FLT_MAX, i.e. it was not locked by another thread.
- */
- const float vl = atomic_cas_float(&v_no[0], virtual_lock, FLT_MAX);
- if (FLT_EQ_NONAN(vl, virtual_lock) && vl != FLT_MAX) {
- break;
+static void bm_vert_calc_normals_impl(const float (*edgevec)[3], BMVert *v)
+{
+ float *v_no = v->no;
+ zero_v3(v_no);
+ BMEdge *e_first = v->e;
+ if (e_first != NULL) {
+ BMEdge *e_iter = e_first;
+ do {
+ BMLoop *l_first = e_iter->l;
+ if (l_first != NULL) {
+ BMLoop *l_iter = l_first;
+ do {
+ if (l_iter->v == v) {
+ bm_vert_calc_normals_accum_loop(l_iter, edgevec, l_iter->f->no, v_no);
+ }
+ } while ((l_iter = l_iter->radial_next) != l_first);
}
- virtual_lock = vl;
+ } while ((e_iter = BM_DISK_EDGE_NEXT(e_iter, v)) != e_first);
+
+ if (LIKELY(normalize_v3(v_no) != 0.0f)) {
+ return;
}
- BLI_assert(v_no[0] == FLT_MAX);
- /* Now we own that normal value, and can change it.
- * But first scalar of the vector must not be changed yet, it's our lock! */
- virtual_lock += f_no[0] * fac;
- v_no[1] += f_no[1] * fac;
- v_no[2] += f_no[2] * fac;
- /* Second atomic operation to 'release'
- * our lock on that vector and set its first scalar value. */
- /* Note that we do not need to loop here, since we 'locked' v_no[0],
- * nobody should have changed it in the mean time. */
- virtual_lock = atomic_cas_float(&v_no[0], FLT_MAX, virtual_lock);
- BLI_assert(virtual_lock == FLT_MAX);
-
- } while ((l_iter = l_iter->next) != l_first);
-
-#undef FLT_EQ_NONAN
+ }
+ /* Fallback normal. */
+ normalize_v3_v3(v_no, v->co);
}
-static void mesh_verts_calc_normals_accum_cb(void *userdata, MempoolIterData *mp_f)
+static void bm_vert_calc_normals_cb(void *userdata, MempoolIterData *mp_v)
{
- BMVertsCalcNormalsData *data = userdata;
- BMFace *f = (BMFace *)mp_f;
- const float *f_no = data->fnos ? data->fnos[BM_elem_index_get(f)] : f->no;
- mesh_verts_calc_normals_accum(f, f_no, data->edgevec, data->vnos);
+ const float(*edgevec)[3] = userdata;
+ BMVert *v = (BMVert *)mp_v;
+ bm_vert_calc_normals_impl(edgevec, v);
}
-static void mesh_verts_calc_normals_normalize_cb(void *userdata, MempoolIterData *mp_v)
+static void bm_vert_calc_normals_with_coords(BMVert *v, BMVertsCalcNormalsWithCoordsData *data)
{
- BMVertsCalcNormalsData *data = userdata;
- BMVert *v = (BMVert *)mp_v;
+ float *v_no = data->vnos[BM_elem_index_get(v)];
+ zero_v3(v_no);
+
+ /* Loop over edges. */
+ BMEdge *e_first = v->e;
+ if (e_first != NULL) {
+ BMEdge *e_iter = e_first;
+ do {
+ BMLoop *l_first = e_iter->l;
+ if (l_first != NULL) {
+ BMLoop *l_iter = l_first;
+ do {
+ if (l_iter->v == v) {
+ bm_vert_calc_normals_accum_loop(
+ l_iter, data->edgevec, data->fnos[BM_elem_index_get(l_iter->f)], v_no);
+ }
+ } while ((l_iter = l_iter->radial_next) != l_first);
+ }
+ } while ((e_iter = BM_DISK_EDGE_NEXT(e_iter, v)) != e_first);
- float *v_no = data->vnos ? data->vnos[BM_elem_index_get(v)] : v->no;
- if (UNLIKELY(normalize_v3(v_no) == 0.0f)) {
- const float *v_co = data->vcos ? data->vcos[BM_elem_index_get(v)] : v->co;
- normalize_v3_v3(v_no, v_co);
+ if (LIKELY(normalize_v3(v_no) != 0.0f)) {
+ return;
+ }
}
+ /* Fallback normal. */
+ normalize_v3_v3(v_no, data->vcos[BM_elem_index_get(v)]);
+}
+
+static void bm_vert_calc_normals_with_coords_cb(void *userdata, MempoolIterData *mp_v)
+{
+ BMVertsCalcNormalsWithCoordsData *data = userdata;
+ BMVert *v = (BMVert *)mp_v;
+ bm_vert_calc_normals_with_coords(v, data);
}
static void bm_mesh_verts_calc_normals(BMesh *bm,
@@ -201,29 +213,34 @@ static void bm_mesh_verts_calc_normals(BMesh *bm,
{
BM_mesh_elem_index_ensure(bm, (BM_EDGE | BM_FACE) | ((vnos || vcos) ? BM_VERT : 0));
- BMVertsCalcNormalsData data = {
- .fnos = fnos,
- .edgevec = edgevec,
- .vcos = vcos,
- .vnos = vnos,
- };
-
- BM_iter_parallel(
-
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list