Page MenuHome
Paste P2290

D11993 alternative (loop-weight as float & fast_acos, 501bca9f5b1265e6f336bc7c1878b9b50a70356a
ActivePublic
Actions

Authored by Campbell Barton (campbellbarton) on Jul 27 2021, 3:48 AM.
diff --git a/source/blender/blenkernel/intern/mesh_normals.cc b/source/blender/blenkernel/intern/mesh_normals.cc
index f496d6eada1..da82284a762 100644
--- a/source/blender/blenkernel/intern/mesh_normals.cc
+++ b/source/blender/blenkernel/intern/mesh_normals.cc
@@ -52,13 +52,40 @@
// #define DEBUG_TIME
-#ifdef DEBUG_TIME
-# include "PIL_time.h"
-# include "PIL_time_utildefines.h"
-#endif
+// #ifdef DEBUG_TIME
+#include "PIL_time.h"
+#include "PIL_time_utildefines.h"
+// #endif
static CLG_LogRef LOG = {"bke.mesh_normals"};
+/* -------------------------------------------------------------------- */
+/** \name Local Utility Functions
+ * \{ */
+
+/**
+ * See: https://developer.download.nvidia.com/cg/acos.html
+ * Absolute error <= 6.7e-5.
+ */
+BLI_INLINE float fast_acos(float x)
+{
+ const float negate = (x < 0.0f) ? 1.0f : 0.0;
+ x = fabsf(x);
+ float ret = -0.0187293f;
+ ret = ret * x;
+ ret = ret + 0.0742610f;
+ ret = ret * x;
+ ret = ret - 0.2121144f;
+ ret = ret * x;
+ ret = ret + 1.5707288f;
+ ret = ret * sqrtf(1.0f - x);
+ ret = ret - 2.0f * negate * ret;
+ /* This isn't *exactly* PI (don't use #M_PI here). */
+ return negate * 3.14159265358979f + ret;
+}
+
+/** \} */
+
/* -------------------------------------------------------------------- */
/** \name Mesh Normal Calculation
* \{ */
@@ -204,7 +231,7 @@ struct MeshCalcNormalsData {
const MLoop *mloop;
MVert *mverts;
float (*pnors)[3];
- float (*lnors_weighted)[3];
+ float *lnors_weights;
float (*vnors)[3];
};
@@ -227,57 +254,45 @@ static void mesh_calc_normals_poly_prepare_cb(void *__restrict userdata,
const MLoop *ml = &data->mloop[mp->loopstart];
const MVert *mverts = data->mverts;
- float pnor_temp[3];
- float *pnor = data->pnors ? data->pnors[pidx] : pnor_temp;
- float(*lnors_weighted)[3] = data->lnors_weighted;
+ float *pnor = data->pnors[pidx];
+ float *lnors_weights = &data->lnors_weights[mp->loopstart];
+ const int i_end = mp->totloop - 1;
- const int nverts = mp->totloop;
- float(*edgevecbuf)[3] = (float(*)[3])BLI_array_alloca(edgevecbuf, (size_t)nverts);
+ int i_next = 0, i_curr = i_end;
+ const float *v_curr = mverts[ml[i_curr].v].co;
+ float edvec_prev[3], edvec_next[3], edvec_end[3];
+ sub_v3_v3v3(edvec_prev, mverts[ml[i_end - 1].v].co, v_curr);
+ normalize_v3(edvec_prev);
+ copy_v3_v3(edvec_end, edvec_prev);
- /* Polygon Normal and edge-vector */
- /* inline version of #BKE_mesh_calc_poly_normal, also does edge-vectors */
- {
- int i_prev = nverts - 1;
- 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++) {
- v_curr = mverts[ml[i].v].co;
- add_newell_cross_v3_v3v3(pnor, v_prev, v_curr);
-
- /* Unrelated to normalize, calculate edge-vector */
- sub_v3_v3v3(edgevecbuf[i_prev], v_prev, v_curr);
- normalize_v3(edgevecbuf[i_prev]);
- i_prev = i;
-
- v_prev = v_curr;
+ zero_v3(pnor);
+
+ while (true) {
+ const float *v_next = mverts[ml[i_next].v].co;
+ /* Inline normal calculation. */
+ add_newell_cross_v3_v3v3(pnor, v_curr, v_next);
+
+ /* Skip an extra normalization by reusing the first calculated edge. */
+ if (i_next != i_end) {
+ sub_v3_v3v3(edvec_next, v_curr, v_next);
+ normalize_v3(edvec_next);
}
- if (UNLIKELY(normalize_v3(pnor) == 0.0f)) {
- pnor[2] = 1.0f; /* other axes set to 0.0 */
+ else {
+ copy_v3_v3(edvec_next, edvec_end);
+ }
+ /* Calculate angle between the two poly edges incident on `i_curr` vertex. */
+ lnors_weights[i_curr] = fast_acos(-dot_v3v3(edvec_next, edvec_prev));
+ if (i_next == i_end) {
+ break;
}
+ i_next += 1;
+ i_curr = i_next;
+ v_curr = v_next;
+ copy_v3_v3(edvec_prev, edvec_next);
}
- /* 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];
-
- for (int i = 0; i < nverts; i++) {
- const int lidx = mp->loopstart + i;
- const float *cur_edge = edgevecbuf[i];
-
- /* 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;
- }
+ if (UNLIKELY(normalize_v3(pnor) == 0.0f)) {
+ pnor[2] = 1.0f; /* other axes set to 0.0 */
}
}
@@ -308,11 +323,12 @@ void BKE_mesh_calc_normals_poly(MVert *mverts,
float (*r_polynors)[3],
const bool only_face_normals)
{
+ TIMEIT_START(BKE_mesh_calc_normals_poly);
float(*pnors)[3] = r_polynors;
TaskParallelSettings settings;
BLI_parallel_range_settings_defaults(&settings);
- settings.min_iter_per_thread = 1024;
+ settings.min_iter_per_thread = 64;
if (only_face_normals) {
BLI_assert((pnors != nullptr) || (numPolys == 0));
@@ -329,9 +345,10 @@ 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__);
+ float *lnors_weights = (float *)MEM_malloc_arrayN(
+ (size_t)numLoops, sizeof(*lnors_weights), __func__);
bool free_vnors = false;
+ bool free_pnors = false;
/* first go through and calculate normals for all the polys */
if (vnors == nullptr) {
@@ -342,12 +359,17 @@ void BKE_mesh_calc_normals_poly(MVert *mverts,
memset(vnors, 0, sizeof(*vnors) * (size_t)numVerts);
}
+ if (pnors == nullptr) {
+ pnors = (float(*)[3])MEM_malloc_arrayN((size_t)numPolys, sizeof(*pnors), __func__);
+ free_pnors = true;
+ }
+
MeshCalcNormalsData data;
data.mpolys = mpolys;
data.mloop = mloop;
data.mverts = mverts;
data.pnors = pnors;
- data.lnors_weighted = lnors_weighted;
+ data.lnors_weights = lnors_weights;
data.vnors = vnors;
/* Compute poly normals, and prepare weighted loop normals. */
@@ -357,8 +379,13 @@ void BKE_mesh_calc_normals_poly(MVert *mverts,
/* 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]);
+ for (int pidx = 0; pidx < numPolys; pidx++) {
+ const float *no = pnors[pidx];
+ int lidx = mpolys[pidx].loopstart;
+ int loopterminate = lidx + mpolys[pidx].totloop;
+ for (; lidx < loopterminate; lidx++) {
+ madd_v3_v3fl(vnors[mloop[lidx].v], no, lnors_weights[lidx]);
+ }
}
/* Normalize and validate computed vertex normals. */
@@ -367,7 +394,12 @@ void BKE_mesh_calc_normals_poly(MVert *mverts,
if (free_vnors) {
MEM_freeN(vnors);
}
- MEM_freeN(lnors_weighted);
+ if (free_pnors) {
+ MEM_freeN(pnors);
+ }
+ MEM_freeN(lnors_weights);
+
+ TIMEIT_END(BKE_mesh_calc_normals_poly);
}
void BKE_mesh_ensure_normals(Mesh *mesh)