Page MenuHome
Paste P2284

D11993 alternative, 501bca9f5b1265e6f336bc7c1878b9b50a70356a
ActivePublic
Actions

Authored by Campbell Barton (campbellbarton) on Jul 26 2021, 6:13 AM.
diff --git a/source/blender/blenkernel/intern/mesh_normals.cc b/source/blender/blenkernel/intern/mesh_normals.cc
index f496d6eada1..bc03efdc88c 100644
--- a/source/blender/blenkernel/intern/mesh_normals.cc
+++ b/source/blender/blenkernel/intern/mesh_normals.cc
@@ -50,6 +50,8 @@
#include "BKE_global.h"
#include "BKE_mesh.h"
+#include "atomic_ops.h"
+
// #define DEBUG_TIME
#ifdef DEBUG_TIME
@@ -59,6 +61,46 @@
static CLG_LogRef LOG = {"bke.mesh_normals"};
+/* -------------------------------------------------------------------- */
+/** \name Private Utility Functions
+ * \{ */
+
+/**
+ * A thread-safe version of #add_v3_v3 that uses a spin-lock.
+ *
+ * \note Avoid using this when the chance of contention is high.
+ */
+static void add_v3_v3_atomic(float r[3], const float a[3])
+{
+#define FLT_EQ_NONAN(_fa, _fb) (*((const uint32_t *)&_fa) == *((const uint32_t *)&_fb))
+
+ float virtual_lock = r[0];
+ while (true) {
+ /* This loops until following conditions are met:
+ * - `r[0]` has same value as virtual_lock (i.e. it did not change since last try).
+ * - `r[0]` was not `FLT_MAX`, i.e. it was not locked by another thread. */
+ const float test_lock = atomic_cas_float(&r[0], virtual_lock, FLT_MAX);
+ if (_ATOMIC_LIKELY(FLT_EQ_NONAN(test_lock, virtual_lock) && (test_lock != FLT_MAX))) {
+ break;
+ }
+ virtual_lock = test_lock;
+ }
+ virtual_lock += a[0];
+ r[1] += a[1];
+ r[2] += a[2];
+
+ /* 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' `r[0]`,
+ * nobody should have changed it in the mean time. */
+ virtual_lock = atomic_cas_float(&r[0], FLT_MAX, virtual_lock);
+ BLI_assert(virtual_lock == FLT_MAX);
+
+#undef FLT_EQ_NONAN
+}
+
+/** \} */
+
/* -------------------------------------------------------------------- */
/** \name Mesh Normal Calculation
* \{ */
@@ -204,10 +246,26 @@ struct MeshCalcNormalsData {
const MLoop *mloop;
MVert *mverts;
float (*pnors)[3];
- float (*lnors_weighted)[3];
float (*vnors)[3];
+ uint32_t *vert_loop_count;
+};
+
+struct MeshCalcNormalsData_VertLoopCount {
+ const MLoop *mloop;
+
+ uint32_t *vert_loop_count;
};
+static void mesh_calc_normals_count_vert_loops_cb(void *__restrict userdata,
+ const int lidx,
+ const TaskParallelTLS *__restrict UNUSED(tls))
+{
+ MeshCalcNormalsData_VertLoopCount *data = (MeshCalcNormalsData_VertLoopCount *)userdata;
+ uint32_t *vert_loop_count = data->vert_loop_count;
+ const MLoop *ml = data->mloop + lidx;
+ atomic_add_and_fetch_uint32(&vert_loop_count[ml->v], 1);
+}
+
static void mesh_calc_normals_poly_cb(void *__restrict userdata,
const int pidx,
const TaskParallelTLS *__restrict UNUSED(tls))
@@ -218,32 +276,32 @@ static void mesh_calc_normals_poly_cb(void *__restrict userdata,
BKE_mesh_calc_poly_normal(mp, data->mloop + mp->loopstart, data->mverts, data->pnors[pidx]);
}
-static void mesh_calc_normals_poly_prepare_cb(void *__restrict userdata,
- const int pidx,
- const TaskParallelTLS *__restrict UNUSED(tls))
+static void mesh_calc_normals_poly_and_vert_cb(void *__restrict userdata,
+ const int pidx,
+ const TaskParallelTLS *__restrict UNUSED(tls))
{
- MeshCalcNormalsData *data = (MeshCalcNormalsData *)userdata;
+ const MeshCalcNormalsData *data = (MeshCalcNormalsData *)userdata;
const MPoly *mp = &data->mpolys[pidx];
const MLoop *ml = &data->mloop[mp->loopstart];
- const MVert *mverts = data->mverts;
+ MVert *mverts = data->mverts;
+ float(*vnors)[3] = data->vnors;
float pnor_temp[3];
float *pnor = data->pnors ? data->pnors[pidx] : pnor_temp;
- float(*lnors_weighted)[3] = data->lnors_weighted;
- const int nverts = mp->totloop;
- float(*edgevecbuf)[3] = (float(*)[3])BLI_array_alloca(edgevecbuf, (size_t)nverts);
+ float(*edgevecbuf)[3] = (float(*)[3])BLI_array_alloca(edgevecbuf, (size_t)mp->totloop);
+ const int loop_index_end = mp->totloop - 1;
/* Polygon Normal and edge-vector */
/* inline version of #BKE_mesh_calc_poly_normal, also does edge-vectors */
{
- int i_prev = nverts - 1;
+ int i_prev = loop_index_end;
const float *v_prev = mverts[ml[i_prev].v].co;
const float *v_curr;
zero_v3(pnor);
/* Newell's Method */
- for (int i = 0; i < nverts; i++) {
+ for (int i = 0; i <= loop_index_end; i++) {
v_curr = mverts[ml[i].v].co;
add_newell_cross_v3_v3v3(pnor, v_prev, v_curr);
@@ -259,43 +317,34 @@ static void mesh_calc_normals_poly_prepare_cb(void *__restrict userdata,
}
}
- /* accumulate angle weighted face normal */
- /* inline version of #accumulate_vertex_normals_poly_v3,
- * split between this threaded callback and #mesh_calc_normals_poly_accum_cb. */
- {
- const float *prev_edge = edgevecbuf[nverts - 1];
+ uint32_t *vert_loop_count = data->vert_loop_count;
- for (int i = 0; i < nverts; i++) {
- const int lidx = mp->loopstart + i;
+ /* Accumulate angle weighted face normal into the vertex normal. */
+ /* inline version of #accumulate_vertex_normals_poly_v3. */
+ {
+ const float *prev_edge = edgevecbuf[loop_index_end];
+ for (int i = 0; i <= loop_index_end; i++) {
const float *cur_edge = edgevecbuf[i];
-
- /* calculate angle between the two poly edges incident on
- * this vertex */
+ /* Calculate angle between the two poly edges incident on this vertex. */
const float fac = saacos(-dot_v3v3(cur_edge, prev_edge));
-
- /* Store for later accumulation */
- mul_v3_v3fl(lnors_weighted[lidx], pnor, fac);
-
prev_edge = cur_edge;
- }
- }
-}
-static void mesh_calc_normals_poly_finalize_cb(void *__restrict userdata,
- const int vidx,
- const TaskParallelTLS *__restrict UNUSED(tls))
-{
- MeshCalcNormalsData *data = (MeshCalcNormalsData *)userdata;
+ const int vidx = ml[i].v;
+ float *no = vnors[vidx];
+ const float vnor_add[3] = {pnor[0] * fac, pnor[1] * fac, pnor[2] * fac};
- MVert *mv = &data->mverts[vidx];
- float *no = data->vnors[vidx];
-
- if (UNLIKELY(normalize_v3(no) == 0.0f)) {
- /* following Mesh convention; we use vertex coordinate itself for normal in this case */
- normalize_v3_v3(no, mv->co);
+ if (atomic_sub_and_fetch_uint32(&vert_loop_count[vidx], 1) != 0) {
+ add_v3_v3_atomic(no, vnor_add);
+ }
+ else {
+ add_v3_v3(no, vnor_add);
+ if (UNLIKELY(normalize_v3(no) == 0.0f)) {
+ normalize_v3_v3(no, mverts[vidx].co);
+ }
+ normal_float_to_short_v3(mverts[vidx].no, no);
+ }
+ }
}
-
- normal_float_to_short_v3(mv->no, no);
}
void BKE_mesh_calc_normals_poly(MVert *mverts,
@@ -329,8 +378,6 @@ void BKE_mesh_calc_normals_poly(MVert *mverts,
}
float(*vnors)[3] = r_vertnors;
- float(*lnors_weighted)[3] = (float(*)[3])MEM_malloc_arrayN(
- (size_t)numLoops, sizeof(*lnors_weighted), __func__);
bool free_vnors = false;
/* first go through and calculate normals for all the polys */
@@ -342,32 +389,37 @@ void BKE_mesh_calc_normals_poly(MVert *mverts,
memset(vnors, 0, sizeof(*vnors) * (size_t)numVerts);
}
+ uint32_t *vert_loop_count = (uint32_t *)MEM_calloc_arrayN(
+ (size_t)numVerts, sizeof(uint32_t), __func__);
+
+ if (numLoops < settings.min_iter_per_thread) {
+ for (int i = 0; i < numLoops; i++) {
+ vert_loop_count[mloop[i].v]++;
+ }
+ }
+ else {
+ MeshCalcNormalsData_VertLoopCount data;
+ data.mloop = mloop;
+ data.vert_loop_count = vert_loop_count;
+ BLI_task_parallel_range(0, numLoops, &data, mesh_calc_normals_count_vert_loops_cb, &settings);
+ }
+
MeshCalcNormalsData data;
data.mpolys = mpolys;
data.mloop = mloop;
data.mverts = mverts;
data.pnors = pnors;
- data.lnors_weighted = lnors_weighted;
data.vnors = vnors;
+ data.vert_loop_count = vert_loop_count;
- /* Compute poly normals, and prepare weighted loop normals. */
- BLI_task_parallel_range(0, numPolys, &data, mesh_calc_normals_poly_prepare_cb, &settings);
-
- /* Actually accumulate weighted loop normals into vertex ones. */
- /* Unfortunately, not possible to thread that
- * (not in a reasonable, totally lock- and barrier-free fashion),
- * since several loops will point to the same vertex... */
- for (int lidx = 0; lidx < numLoops; lidx++) {
- add_v3_v3(vnors[mloop[lidx].v], data.lnors_weighted[lidx]);
- }
-
- /* Normalize and validate computed vertex normals. */
- BLI_task_parallel_range(0, numVerts, &data, mesh_calc_normals_poly_finalize_cb, &settings);
+ /* Compute poly normals (`pnors`), accumulating them into vertex normals (`vnors`). */
+ BLI_task_parallel_range(0, numPolys, &data, mesh_calc_normals_poly_and_vert_cb, &settings);
if (free_vnors) {
MEM_freeN(vnors);
}
- MEM_freeN(lnors_weighted);
+
+ MEM_freeN(vert_loop_count);
}
void BKE_mesh_ensure_normals(Mesh *mesh)