[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [44907] trunk/blender/source: mesh_validate code for bmesh (i.e.
Bastien Montagne
montagne29 at wanadoo.fr
Thu Mar 15 21:10:10 CET 2012
Revision: 44907
http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=44907
Author: mont29
Date: 2012-03-15 20:10:07 +0000 (Thu, 15 Mar 2012)
Log Message:
-----------
mesh_validate code for bmesh (i.e. polys/loops).
Everything seems to work well (many tests making random changes over various meshes went good), but the code is a bit complex and hard to follow, due to the various possibilities of invalid poly/loop combinations?\226?\128?\166 Code also makes more operations than previous tri/quad faces version (hence is a bit slower), but I don?\226?\128?\153t think we can do otherwise, it?\226?\128?\153s just the price for bmesh flexibility. ;)
Note: added the py script I used to make the tests, under source/tests/...
Modified Paths:
--------------
trunk/blender/source/blender/blenkernel/BKE_mesh.h
trunk/blender/source/blender/blenkernel/intern/mesh.c
trunk/blender/source/blender/blenkernel/intern/mesh_validate.c
Added Paths:
-----------
trunk/blender/source/tests/bl_mesh_validate.py
Modified: trunk/blender/source/blender/blenkernel/BKE_mesh.h
===================================================================
--- trunk/blender/source/blender/blenkernel/BKE_mesh.h 2012-03-15 19:24:16 UTC (rev 44906)
+++ trunk/blender/source/blender/blenkernel/BKE_mesh.h 2012-03-15 20:10:07 UTC (rev 44907)
@@ -160,7 +160,8 @@
/* if old, it converts mface->edcode to edge drawflags */
void make_edges(struct Mesh *me, int old);
-void mesh_strip_loose_faces(struct Mesh *me);
+void mesh_strip_loose_faces(struct Mesh *me); /* Needed for compatibility (some old read code). */
+void mesh_strip_loose_polysloops(struct Mesh *me);
void mesh_strip_loose_edges(struct Mesh *me);
/* Calculate vertex and face normals, face normals are returned in *faceNors_r if non-NULL
@@ -268,11 +269,14 @@
void mesh_translate(struct Mesh *me, float offset[3], int do_keys);
/* mesh_validate.c */
+/* XXX Loop v/e are unsigned, so using max uint_32 value as invalid marker... */
+#define INVALID_LOOP_EDGE_MARKER 4294967295u
int BKE_mesh_validate_arrays(
- struct Mesh *me,
+ struct Mesh *me,
struct MVert *mverts, unsigned int totvert,
struct MEdge *medges, unsigned int totedge,
- struct MFace *mfaces, unsigned int totface,
+ struct MLoop *mloops, unsigned int totloop,
+ struct MPoly *mpolys, unsigned int totpoly,
struct MDeformVert *dverts, /* assume totvert length */
const short do_verbose, const short do_fixes);
int BKE_mesh_validate(struct Mesh *me, int do_verbose);
Modified: trunk/blender/source/blender/blenkernel/intern/mesh.c
===================================================================
--- trunk/blender/source/blender/blenkernel/intern/mesh.c 2012-03-15 19:24:16 UTC (rev 44906)
+++ trunk/blender/source/blender/blenkernel/intern/mesh.c 2012-03-15 20:10:07 UTC (rev 44907)
@@ -1016,38 +1016,131 @@
mesh_strip_loose_faces(me);
}
+/* We need to keep this for edge creation (for now?), and some old readfile code... */
void mesh_strip_loose_faces(Mesh *me)
{
- int a,b;
+ MFace *f;
+ int a, b;
- for (a=b=0; a<me->totface; a++) {
- if (me->mface[a].v3) {
- if (a!=b) {
- memcpy(&me->mface[b],&me->mface[a],sizeof(me->mface[b]));
+ for (a = b = 0, f = me->mface; a < me->totface; a++, f++) {
+ if (f->v3) {
+ if (a != b) {
+ memcpy(&me->mface[b], f, sizeof(me->mface[b]));
CustomData_copy_data(&me->fdata, &me->fdata, a, b, 1);
- CustomData_free_elem(&me->fdata, a, 1);
}
b++;
}
}
- me->totface = b;
+ if (a != b) {
+ CustomData_free_elem(&me->fdata, b, a - b);
+ me->totface = b;
+ }
}
+/* Works on both loops and polys! */
+/* Note: It won't try to guess which loops of an invalid poly to remove!
+ * this is the work of the caller, to mark those loops...
+ * See e.g. BKE_mesh_validate_arrays(). */
+void mesh_strip_loose_polysloops(Mesh *me)
+{
+ MPoly *p;
+ MLoop *l;
+ int a, b;
+ /* New loops idx! */
+ int *new_idx = MEM_mallocN(sizeof(int) * me->totloop, "strip_loose_polysloops old2new idx mapping for polys.");
+
+ for (a = b = 0, p = me->mpoly; a < me->totpoly; a++, p++) {
+ int invalid = FALSE;
+ int i = p->loopstart;
+ int stop = i + p->totloop;
+
+ if (stop > me->totloop || stop < i) {
+ invalid = TRUE;
+ }
+ else {
+ l = &me->mloop[i];
+ i = stop - i;
+ /* If one of the poly's loops is invalid, the whole poly is invalid! */
+ for (; i--; l++) {
+ if (l->e == INVALID_LOOP_EDGE_MARKER) {
+ invalid = TRUE;
+ break;
+ }
+ }
+ }
+
+ if (p->totloop >= 3 && !invalid) {
+ if (a != b) {
+ memcpy(&me->mpoly[b], p, sizeof(me->mpoly[b]));
+ CustomData_copy_data(&me->pdata, &me->pdata, a, b, 1);
+ }
+ b++;
+ }
+ }
+ if (a != b) {
+ CustomData_free_elem(&me->pdata, b, a - b);
+ me->totpoly = b;
+ }
+
+ /* And now, get rid of invalid loops. */
+ for (a = b = 0, l = me->mloop; a < me->totloop; a++, l++) {
+ if (l->e != INVALID_LOOP_EDGE_MARKER) {
+ if (a != b) {
+ memcpy(&me->mloop[b], l, sizeof(me->mloop[b]));
+ CustomData_copy_data(&me->ldata, &me->ldata, a, b, 1);
+ }
+ new_idx[a] = b;
+ b++;
+ }
+ else {
+ /* XXX Theorically, we should be able to not do this, as no remaining poly
+ * should use any stripped loop. But for security's sake... */
+ new_idx[a] = -a;
+ }
+ }
+ if (a != b) {
+ CustomData_free_elem(&me->ldata, b, a - b);
+ me->totloop = b;
+ }
+
+ /* And now, update polys' start loop index. */
+ /* Note: At this point, there should never be any poly using a striped loop! */
+ for (a = 0, p = me->mpoly; a < me->totpoly; a++, p++) {
+ p->loopstart = new_idx[p->loopstart];
+ }
+}
+
void mesh_strip_loose_edges(Mesh *me)
{
- int a,b;
+ MEdge *e;
+ MLoop *l;
+ int a, b;
+ unsigned int *new_idx = MEM_mallocN(sizeof(int) * me->totedge, "strip_loose_edges old2new idx mapping for loops.");
- for (a=b=0; a<me->totedge; a++) {
- if (me->medge[a].v1!=me->medge[a].v2) {
- if (a!=b) {
- memcpy(&me->medge[b],&me->medge[a],sizeof(me->medge[b]));
+ for (a = b = 0, e = me->medge; a < me->totedge; a++, e++) {
+ if (e->v1 != e->v2) {
+ if (a != b) {
+ memcpy(&me->medge[b], e, sizeof(me->medge[b]));
CustomData_copy_data(&me->edata, &me->edata, a, b, 1);
- CustomData_free_elem(&me->edata, a, 1);
}
+ new_idx[a] = b;
b++;
}
+ else {
+ new_idx[a] = INVALID_LOOP_EDGE_MARKER;
+ }
}
- me->totedge = b;
+ if (a != b) {
+ CustomData_free_elem(&me->edata, b, a - b);
+ me->totedge = b;
+ }
+
+ /* And now, update loops' edge indices. */
+ /* XXX We hope no loop was pointing to a striped edge!
+ * Else, its e will be set to INVALID_LOOP_EDGE_MARKER :/ */
+ for (a = 0, l = me->mloop; a < me->totloop; a++, l++) {
+ l->e = new_idx[l->e];
+ }
}
void mball_to_mesh(ListBase *lb, Mesh *me)
@@ -2215,7 +2308,7 @@
CustomData *ldata, CustomData *pdata,
MVert *mvert, int totface, int UNUSED(totloop),
int totpoly,
- /* when tessellating to recalcilate normals after
+ /* when tessellating to recalculate normals after
* we can skip copying here */
const int do_face_nor_cpy)
{
Modified: trunk/blender/source/blender/blenkernel/intern/mesh_validate.c
===================================================================
--- trunk/blender/source/blender/blenkernel/intern/mesh_validate.c 2012-03-15 19:24:16 UTC (rev 44906)
+++ trunk/blender/source/blender/blenkernel/intern/mesh_validate.c 2012-03-15 20:10:07 UTC (rev 44907)
@@ -33,111 +33,91 @@
#include "DNA_mesh_types.h"
#include "DNA_meshdata_types.h"
+#include "DNA_object_types.h"
#include "BLO_sys_types.h"
-#include "BLI_utildefines.h"
#include "BLI_edgehash.h"
#include "BLI_math_base.h"
+#include "BLI_utildefines.h"
+#include "BKE_deform.h"
+#include "BKE_depsgraph.h"
#include "BKE_DerivedMesh.h"
+#include "BKE_mesh.h"
#include "MEM_guardedalloc.h"
-#include "BKE_mesh.h"
-#include "BKE_deform.h"
-
#define SELECT 1
-typedef union {
- uint32_t verts[2];
- int64_t edval;
-} EdgeUUID;
+/* Used to detect polys (faces) using exactly the same vertices. */
+/* Used to detect loops used by no (disjoint) or more than one (intersect) polys. */
+typedef struct SortPoly {
+ int *verts;
+ int numverts;
+ int loopstart;
+ unsigned int index;
+ int invalid; /* Poly index. */
+} SortPoly;
-typedef struct SortFace {
-// unsigned int v[4];
- EdgeUUID es[4];
- unsigned int index;
-} SortFace;
-
-static void edge_store_assign(uint32_t verts[2], const uint32_t v1, const uint32_t v2)
+/* TODO check there is not some standard define of this somewhere! */
+static int int_cmp(const void *v1, const void *v2)
{
- if(v1 < v2) {
- verts[0]= v1;
- verts[1]= v2;
- }
- else {
- verts[0]= v2;
- verts[1]= v1;
- }
+ return *(int*)v1 > *(int*)v2 ? 1 : *(int*)v1 < *(int*)v2 ? -1 : 0;
}
-static void edge_store_from_mface_quad(EdgeUUID es[4], MFace *mf)
+static int search_poly_cmp(const void *v1, const void *v2)
{
- edge_store_assign(es[0].verts, mf->v1, mf->v2);
- edge_store_assign(es[1].verts, mf->v2, mf->v3);
- edge_store_assign(es[2].verts, mf->v3, mf->v4);
- edge_store_assign(es[3].verts, mf->v4, mf->v1);
-}
+ const SortPoly *sp1 = v1, *sp2 = v2;
+ const int max_idx = sp1->numverts > sp2->numverts ? sp2->numverts : sp1->numverts;
+ int idx = 0;
-static void edge_store_from_mface_tri(EdgeUUID es[4], MFace *mf)
-{
- edge_store_assign(es[0].verts, mf->v1, mf->v2);
- edge_store_assign(es[1].verts, mf->v2, mf->v3);
- edge_store_assign(es[2].verts, mf->v3, mf->v1);
- es[3].verts[0] = es[3].verts[1] = UINT_MAX;
+ /* Reject all invalid polys at end of list! */
+ if (sp1->invalid || sp2->invalid)
+ return sp1->invalid && sp2->invalid ? 0 : sp1->invalid ? 1 : -1;
+ /* Else, sort on first non-egal verts (remember verts of valid polys are sorted). */
+ while (idx < max_idx && sp1->verts[idx] == sp2->verts[idx])
+ idx++;
+ return sp1->verts[idx] > sp2->verts[idx] ? 1 : sp1->verts[idx] < sp2->verts[idx] ? -1 :
+ sp1->numverts > sp2->numverts ? 1 : sp1->numverts < sp2->numverts ? -1 : 0;
}
-static int int64_cmp(const void *v1, const void *v2)
+static int search_polyloop_cmp(const void *v1, const void *v2)
{
- const int64_t x1= *(const int64_t *)v1;
- const int64_t x2= *(const int64_t *)v2;
+ const SortPoly *sp1 = v1, *sp2 = v2;
- if( x1 > x2 ) return 1;
- else if( x1 < x2 ) return -1;
- return 0;
+ /* Reject all invalid polys at end of list! */
+ if (sp1->invalid || sp2->invalid)
+ return sp1->invalid && sp2->invalid ? 0 : sp1->invalid ? 1 : -1;
+ /* Else, sort on loopstart. */
+ return sp1->loopstart > sp2->loopstart ? 1 : sp1->loopstart < sp2->loopstart ? -1 : 0;
}
-static int search_face_cmp(const void *v1, const void *v2)
-{
- const SortFace *sfa= v1, *sfb= v2;
-
- if (sfa->es[0].edval > sfb->es[0].edval) return 1;
- else if (sfa->es[0].edval < sfb->es[0].edval) return -1;
-
- else if (sfa->es[1].edval > sfb->es[1].edval) return 1;
- else if (sfa->es[1].edval < sfb->es[1].edval) return -1;
-
- else if (sfa->es[2].edval > sfb->es[2].edval) return 1;
- else if (sfa->es[2].edval < sfb->es[2].edval) return -1;
-
- else if (sfa->es[3].edval > sfb->es[3].edval) return 1;
- else if (sfa->es[3].edval < sfb->es[3].edval) return -1;
- else return 0;
-
-}
-
#define PRINT if(do_verbose) printf
-int BKE_mesh_validate_arrays( Mesh *me,
- MVert *mverts, unsigned int totvert,
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list