[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [60005] trunk/blender/source/blender/ blenkernel: Core code for split normals computation.
Bastien Montagne
montagne29 at wanadoo.fr
Tue Sep 10 14:48:09 CEST 2013
Revision: 60005
http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=60005
Author: mont29
Date: 2013-09-10 12:48:08 +0000 (Tue, 10 Sep 2013)
Log Message:
-----------
Core code for split normals computation. Many thanks to ideasman for is optimization guiding and code reviews!
Note the API is not yet committed, as it may need a few more checks & tweaks. ;)
Modified Paths:
--------------
trunk/blender/source/blender/blenkernel/BKE_mesh.h
trunk/blender/source/blender/blenkernel/intern/mesh_evaluate.c
Modified: trunk/blender/source/blender/blenkernel/BKE_mesh.h
===================================================================
--- trunk/blender/source/blender/blenkernel/BKE_mesh.h 2013-09-10 12:46:27 UTC (rev 60004)
+++ trunk/blender/source/blender/blenkernel/BKE_mesh.h 2013-09-10 12:48:08 UTC (rev 60005)
@@ -164,8 +164,11 @@
struct MVert *mverts, int numVerts,
struct MFace *mfaces, int numFaces,
float (*faceNors_r)[3]);
+void BKE_mesh_normals_loop_split(
+ struct MVert *mverts, int numVerts, struct MEdge *medges, int numEdges,
+ struct MLoop *mloops, float (*r_loopnors)[3], int numLoops,
+ struct MPoly *mpolys, float (*polynors)[3], int numPolys, float split_angle);
-
void BKE_mesh_calc_poly_normal(
struct MPoly *mpoly, struct MLoop *loopstart,
struct MVert *mvarray, float no[3]);
Modified: trunk/blender/source/blender/blenkernel/intern/mesh_evaluate.c
===================================================================
--- trunk/blender/source/blender/blenkernel/intern/mesh_evaluate.c 2013-09-10 12:46:27 UTC (rev 60004)
+++ trunk/blender/source/blender/blenkernel/intern/mesh_evaluate.c 2013-09-10 12:48:08 UTC (rev 60005)
@@ -29,6 +29,8 @@
* Functions to evaluate mesh data.
*/
+#include <limits.h>
+
#include "MEM_guardedalloc.h"
#include "DNA_object_types.h"
@@ -41,15 +43,24 @@
#include "BLI_edgehash.h"
#include "BLI_bitmap.h"
#include "BLI_scanfill.h"
+#include "BLI_linklist.h"
+#include "BLI_linklist_stack.h"
#include "BLI_alloca.h"
#include "BKE_customdata.h"
#include "BKE_mesh.h"
#include "BKE_multires.h"
-
#include "BLI_strict_flags.h"
+
+// #define DEBUG_TIME
+
+#ifdef DEBUG_TIME
+# include "PIL_time.h"
+# include "PIL_time_utildefines.h"
+#endif
+
/* -------------------------------------------------------------------- */
/** \name Mesh Normal Calculation
@@ -253,9 +264,15 @@
void BKE_mesh_calc_normals(Mesh *mesh)
{
+#ifdef DEBUG_TIME
+ TIMEIT_START(BKE_mesh_calc_normals);
+#endif
BKE_mesh_calc_normals_poly(mesh->mvert, mesh->totvert,
mesh->mloop, mesh->mpoly, mesh->totloop, mesh->totpoly,
NULL, false);
+#ifdef DEBUG_TIME
+ TIMEIT_END(BKE_mesh_calc_normals);
+#endif
}
void BKE_mesh_calc_normals_tessface(MVert *mverts, int numVerts, MFace *mfaces, int numFaces, float (*faceNors_r)[3])
@@ -296,6 +313,265 @@
if (fnors != faceNors_r)
MEM_freeN(fnors);
}
+
+/**
+ * Compute split normals, i.e. vertex normals associated with each poly (hence 'loop normals').
+ * Useful to materialize sharp edges (or non-smooth faces) without actually modifying the geometry (splitting edges).
+ */
+void BKE_mesh_normals_loop_split(MVert *mverts, int UNUSED(numVerts), MEdge *medges, int numEdges,
+ MLoop *mloops, float (*r_loopnors)[3], int numLoops,
+ MPoly *mpolys, float (*polynors)[3], int numPolys, float split_angle)
+{
+#define INDEX_UNSET INT_MIN
+#define INDEX_INVALID -1
+/* See comment about edge_to_loops below. */
+#define IS_EDGE_SHARP(_e2l) (ELEM((_e2l)[1], INDEX_UNSET, INDEX_INVALID))
+
+ /* Mapping edge -> loops.
+ * If that edge is used by more than two loops (polys), it is always sharp (and tagged as such, see below).
+ * We also use the second loop index as a kind of flag: smooth edge: > 0,
+ * sharp edge: < 0 (INDEX_INVALID || INDEX_UNSET),
+ * unset: INDEX_UNSET
+ * Note that currently we only have two values for second loop of sharp edges. However, if needed, we can
+ * store the negated value of loop index instead of INDEX_INVALID to retrieve th real value later in code).
+ * Note also that lose edges always have the value 0!
+ */
+ int (*edge_to_loops)[2] = MEM_callocN(sizeof(int[2]) * (size_t)numEdges, __func__);
+
+ /* Simple mapping from a loop to its polygon index. */
+ int *loop_to_poly = MEM_mallocN(sizeof(int) * (size_t)numLoops, __func__);
+
+ MPoly *mp;
+ int mp_index;
+ const bool check_angle = (split_angle < (float)M_PI);
+
+ /* Temp normal stack. */
+ BLI_SMALLSTACK_DECLARE(normal, float *);
+
+#ifdef DEBUG_TIME
+ TIMEIT_START(BKE_mesh_normals_loop_split);
+#endif
+
+ if (check_angle) {
+ split_angle = cosf(split_angle);
+ }
+
+ /* This first loop check which edges are actually smooth, and compute edge vectors. */
+ for (mp = mpolys, mp_index = 0; mp_index < numPolys; mp++, mp_index++) {
+ MLoop *ml_curr;
+ int *e2l;
+ int ml_curr_index = mp->loopstart;
+ const int ml_last_index = (ml_curr_index + mp->totloop) - 1;
+
+ ml_curr = &mloops[ml_curr_index];
+
+ for (; ml_curr_index <= ml_last_index; ml_curr++, ml_curr_index++) {
+ e2l = edge_to_loops[ml_curr->e];
+
+ loop_to_poly[ml_curr_index] = mp_index;
+
+ /* Pre-populate all loop normals as if their verts were all-smooth, this way we don't have to compute
+ * those later!
+ */
+ normal_short_to_float_v3(r_loopnors[ml_curr_index], mverts[ml_curr->v].no);
+
+ /* Check whether current edge might be smooth or sharp */
+ if ((e2l[0] | e2l[1]) == 0) {
+ /* 'Empty' edge until now, set e2l[0] (and e2l[1] to INT_MIN to tag it as unset). */
+ e2l[0] = ml_curr_index;
+ e2l[1] = INDEX_UNSET;
+ }
+ else if (e2l[1] == INDEX_UNSET) {
+ /* Second loop using this edge, time to test its sharpness.
+ * An edge is sharp if it is tagged as such, or its face is not smooth, or angle between
+ * both its polys' normals is above split_angle value...
+ */
+ if (!(mp->flag & ME_SMOOTH) || (medges[ml_curr->e].flag & ME_SHARP) ||
+ (check_angle && dot_v3v3(polynors[loop_to_poly[e2l[0]]], polynors[mp_index]) < split_angle))
+ {
+ /* Note: we are sure that loop != 0 here ;) */
+ e2l[1] = INDEX_INVALID;
+ }
+ else {
+ e2l[1] = ml_curr_index;
+ }
+ }
+ else if (!IS_EDGE_SHARP(e2l)) {
+ /* More that two loops using this edge, tag as sharp if not yet done. */
+ e2l[1] = INDEX_INVALID;
+ }
+ /* Else, edge is already 'disqualified' (i.e. sharp)! */
+ }
+ }
+
+ /* We now know edges that can be smoothed (with their vector, and their two loops), and edges that will be hard!
+ * Now, time to generate the normals.
+ */
+ for (mp = mpolys, mp_index = 0; mp_index < numPolys; mp++, mp_index++) {
+ MLoop *ml_curr, *ml_prev;
+ float (*lnors)[3];
+ const int ml_last_index = (mp->loopstart + mp->totloop) - 1;
+ int ml_curr_index = mp->loopstart;
+ int ml_prev_index = ml_last_index;
+
+ ml_curr = &mloops[ml_curr_index];
+ ml_prev = &mloops[ml_prev_index];
+ lnors = &r_loopnors[ml_curr_index];
+
+ for (; ml_curr_index <= ml_last_index; ml_curr++, ml_curr_index++, lnors++) {
+ const int *e2l_curr = edge_to_loops[ml_curr->e];
+ const int *e2l_prev = edge_to_loops[ml_prev->e];
+
+ if (!IS_EDGE_SHARP(e2l_curr)) {
+ /* A smooth edge.
+ * We skip it because it is either:
+ * - in the middle of a 'smooth fan' already computed (or that will be as soon as we hit
+ * one of its ends, i.e. one of its two sharp edges), or...
+ * - the related vertex is a "full smooth" one, in which case pre-populated normals from vertex
+ * are just fine!
+ */
+ }
+ else if (IS_EDGE_SHARP(e2l_prev)) {
+ /* Simple case (both edges around that vertex are sharp in current polygon),
+ * this vertex just takes its poly normal.
+ */
+ copy_v3_v3(*lnors, polynors[mp_index]);
+ /* No need to mark loop as done here, we won't run into it again anyway! */
+ }
+ /* This loop may have been already computed, in which case its 'to_poly' map is set to -1... */
+ else if (loop_to_poly[ml_curr_index] != -1) {
+ /* Gah... We have to fan around current vertex, until we find the other non-smooth edge,
+ * and accumulate face normals into the vertex!
+ * Note in case this vertex has only one sharp edges, this is a waste because the normal is the same as
+ * the vertex normal, but I do not see any easy way to detect that (would need to count number
+ * of sharp edges per vertex, I doubt the additional memory usage would be worth it, especially as
+ * it should not be a common case in real-life meshes anyway).
+ */
+ const unsigned int mv_pivot_index = ml_curr->v; /* The vertex we are "fanning" around! */
+ const int *e2lfan_curr;
+ float vec_curr[3], vec_prev[3];
+ MLoop *mlfan_curr, *mlfan_next;
+ MPoly *mpfan_next;
+ float lnor[3] = {0.0f, 0.0f, 0.0f};
+ /* mlfan_vert_index: the loop of our current edge might not be the loop of our current vertex! */
+ int mlfan_curr_index, mlfan_vert_index, mpfan_curr_index;
+
+ e2lfan_curr = e2l_prev;
+ mlfan_curr = ml_prev;
+ mlfan_curr_index = ml_prev_index;
+ mlfan_vert_index = ml_curr_index;
+ mpfan_curr_index = mp_index;
+
+ /* Only need to compute previous edge's vector once, then we can just reuse old current one! */
+ {
+ const MEdge *me_prev = &medges[ml_prev->e];
+ const MVert *mv_1 = &mverts[mv_pivot_index];
+ const MVert *mv_2 = (me_prev->v1 == mv_pivot_index) ? &mverts[me_prev->v2] : &mverts[me_prev->v1];
+
+ sub_v3_v3v3(vec_prev, mv_2->co, mv_1->co);
+ normalize_v3(vec_prev);
+ }
+
+ while (true) {
+ /* Compute edge vectors.
+ * NOTE: We could pre-compute those into an array, in the first iteration, instead of computing them
+ * twice (or more) here. However, time gained is not worth memory and time lost,
+ * given the fact that this code should not be called that much in real-life meshes...
+ */
+ {
+ const MEdge *me_curr = &medges[ml_curr->e];
+ const MVert *mv_1 = &mverts[mv_pivot_index];
+ const MVert *mv_2 = (me_curr->v1 == mv_pivot_index) ? &mverts[me_curr->v2] :
+ &mverts[me_curr->v1];
+
+ sub_v3_v3v3(vec_curr, mv_2->co, mv_1->co);
+ normalize_v3(vec_curr);
+ }
+
+ {
+ /* Code similar to accumulate_vertex_normals_poly. */
+ /* Calculate angle between the two poly edges incident on this vertex. */
+ const float fac = saacos(dot_v3v3(vec_curr, vec_prev));
+ /* Accumulate */
+ madd_v3_v3fl(lnor, polynors[mpfan_curr_index], fac);
+ }
+
+ /* We store here a pointer to all loop-normals processed. */
+ BLI_SMALLSTACK_PUSH(normal, &(r_loopnors[mlfan_vert_index][0]));
+
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list