[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [19286] branches/bmesh/blender/source/ blender: connect verts now does geometric tests to perform valid splits.
Joseph Eagar
joeedh at gmail.com
Sat Mar 14 14:16:36 CET 2009
Revision: 19286
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=19286
Author: joeedh
Date: 2009-03-14 14:16:35 +0100 (Sat, 14 Mar 2009)
Log Message:
-----------
connect verts now does geometric tests to perform valid splits. it also supports multiple splits in a face, going around the face boundary in a loop and performing splits.
Modified Paths:
--------------
branches/bmesh/blender/source/blender/blenkernel/BKE_utildefines.h
branches/bmesh/blender/source/blender/bmesh/bmesh.h
branches/bmesh/blender/source/blender/bmesh/bmesh_queries.h
branches/bmesh/blender/source/blender/bmesh/intern/bmesh_mods.c
branches/bmesh/blender/source/blender/bmesh/intern/bmesh_polygon.c
branches/bmesh/blender/source/blender/bmesh/operators/connectops.c
Modified: branches/bmesh/blender/source/blender/blenkernel/BKE_utildefines.h
===================================================================
--- branches/bmesh/blender/source/blender/blenkernel/BKE_utildefines.h 2009-03-14 13:12:11 UTC (rev 19285)
+++ branches/bmesh/blender/source/blender/blenkernel/BKE_utildefines.h 2009-03-14 13:16:35 UTC (rev 19286)
@@ -113,6 +113,8 @@
#define VECADD(v1,v2,v3) {*(v1)= *(v2) + *(v3); *(v1+1)= *(v2+1) + *(v3+1); *(v1+2)= *(v2+2) + *(v3+2);}
#define VECSUB(v1,v2,v3) {*(v1)= *(v2) - *(v3); *(v1+1)= *(v2+1) - *(v3+1); *(v1+2)= *(v2+2) - *(v3+2);}
#define VECSUB2D(v1,v2,v3) {*(v1)= *(v2) - *(v3); *(v1+1)= *(v2+1) - *(v3+1);}
+#define VECMUL(v1, fac) {v1[0] *= fac; v1[1] *= fac; v1[2] *= fac;}
+
#define VECADDFAC(v1,v2,v3,fac) {*(v1)= *(v2) + *(v3)*(fac); *(v1+1)= *(v2+1) + *(v3+1)*(fac); *(v1+2)= *(v2+2) + *(v3+2)*(fac);}
#define QUATADDFAC(v1,v2,v3,fac) {*(v1)= *(v2) + *(v3)*(fac); *(v1+1)= *(v2+1) + *(v3+1)*(fac); *(v1+2)= *(v2+2) + *(v3+2)*(fac); *(v1+3)= *(v2+3) + *(v3+3)*(fac);}
Modified: branches/bmesh/blender/source/blender/bmesh/bmesh.h
===================================================================
--- branches/bmesh/blender/source/blender/bmesh/bmesh.h 2009-03-14 13:12:11 UTC (rev 19285)
+++ branches/bmesh/blender/source/blender/bmesh/bmesh.h 2009-03-14 13:16:35 UTC (rev 19286)
@@ -52,8 +52,9 @@
The API includes iterators, including many useful topological iterators;
walkers, which walk over a mesh, without the risk of hitting the recursion
limit; operators, which are logical, reusable mesh modules; topological
-"euler" functions, which are used for topological manipulations; and some
-(not yet finished) geometric utility functions.
+modification functions (like split face, join faces, etc), which are used for
+topological manipulations; and some (not yet finished) geometric utility
+functions.
some definitions:
Modified: branches/bmesh/blender/source/blender/bmesh/bmesh_queries.h
===================================================================
--- branches/bmesh/blender/source/blender/bmesh/bmesh_queries.h 2009-03-14 13:12:11 UTC (rev 19285)
+++ branches/bmesh/blender/source/blender/bmesh/bmesh_queries.h 2009-03-14 13:16:35 UTC (rev 19286)
@@ -79,4 +79,11 @@
/*checks if a face is valid in the data structure*/
int BM_Validate_Face(BMesh *bm, BMFace *face, FILE *err);
+
+/*each pair of loops defines a new edge, a split. this function goes
+ through and sets pairs that are geometrically invalid to null. a
+ split is invalid, if it forms a concave angle or it intersects other
+ edges in the face.*/
+void BM_LegalSplits(BMesh *bm, BMFace *f, BMLoop *(*loops)[2], int len);
+
#endif
Modified: branches/bmesh/blender/source/blender/bmesh/intern/bmesh_mods.c
===================================================================
--- branches/bmesh/blender/source/blender/bmesh/intern/bmesh_mods.c 2009-03-14 13:12:11 UTC (rev 19285)
+++ branches/bmesh/blender/source/blender/bmesh/intern/bmesh_mods.c 2009-03-14 13:16:35 UTC (rev 19286)
@@ -275,7 +275,7 @@
BMFace *nf;
nf = bmesh_sfme(bm,f,v1,v2,nl);
- BM_Copy_Attributes(bm, bm, f, nf);
+ if (nf) BM_Copy_Attributes(bm, bm, f, nf);
return nf;
}
Modified: branches/bmesh/blender/source/blender/bmesh/intern/bmesh_polygon.c
===================================================================
--- branches/bmesh/blender/source/blender/bmesh/intern/bmesh_polygon.c 2009-03-14 13:12:11 UTC (rev 19285)
+++ branches/bmesh/blender/source/blender/bmesh/intern/bmesh_polygon.c 2009-03-14 13:16:35 UTC (rev 19286)
@@ -133,9 +133,9 @@
n[1] /= l;
n[2] /= l;
- normal[0] = n[0];
- normal[1] = n[1];
- normal[2] = n[2];
+ normal[0] = (float) n[0];
+ normal[1] = (float) n[1];
+ normal[2] = (float) n[2];
}
/*
@@ -249,77 +249,39 @@
the list that bridges a concave region of the face or intersects
any of the faces's edges.
*/
-static void shrink_edge(float *v1, float *v2, float fac)
+static void shrink_edged(double *v1, double *v2, double fac)
{
- float mid[3];
+ double mid[3];
- VecAddf(mid, v1, v2);
- VecMulf(mid, 0.5f);
+ VECADD(mid, v1, v2);
+ VECMUL(mid, 0.5);
- VecSubf(v1, v1, mid);
- VecSubf(v2, v2, mid);
+ VECSUB(v1, v1, mid);
+ VECSUB(v2, v2, mid);
- VecMulf(v1, fac);
- VecMulf(v2, fac);
+ VECMUL(v1, fac);
+ VECMUL(v2, fac);
- VecAddf(v1, v1, mid);
- VecAddf(v2, v2, mid);
-
+ VECADD(v1, v1, mid);
+ VECADD(v2, v2, mid);
}
-#if 0
-void BM_LegalSplits(BMesh *bm, BMFace *f, BMLoop (*loops)[2], int len)
+static void shrink_edgef(float *v1, float *v2, float fac)
{
- BMIter iter;
- BMLoop *l;
- float v1[3], v2[3], no[3], *p1, *p2;
- float projectverts[100][3];
- float edgevertsstack[100][2][3];
- float (*projverts)[3] = projectverts;
- float (*edgeverts)[2][3] = edgevertsstack;
- int i, nvert, j;
+ float mid[3];
- if (f->len > 100) projverts = MEM_mallocN(sizeof(float)*3*f->len, "projvertsb");
- if (len > 100) edgeverts = MEM_mallocN(sizeof(float)*3*2*len, "edgevertsb");
-
- i = 0;
- l = BMIter_New(&iter, bm, BM_LOOPS_OF_FACE, f);
- for (; l; l=BMIter_Step(&iter)) {
- VECCOPY(projverts[i], l->v->co);
- i++;
- }
+ VECADD(mid, v1, v2);
+ VECMUL(mid, 0.5);
- for (i=0; i<len; i++) {
- VECCOPY(v1, loops[i][0]->v->co);
- VECCOPY(v2, loops[i][0]->v->co);
+ VECSUB(v1, v1, mid);
+ VECSUB(v2, v2, mid);
- shrink_edge(v1, v2, 0.9999f);
+ VECMUL(v1, fac);
+ VECMUL(v2, fac);
- VECCOPY(edgeverts[i][0], v1);
- VECCOPY(edgeverts[i][1], v2);
- }
-
- compute_poly_normal(no, projverts, f->len);
- poly_rotate_plane(no, projverts, f->len);
- poly_rotate_plane(no, edgeverts, len);
-
- for (i=0; i<len; i++) {
- if (convexangle(
- }
-
- for (i=0; i<f->len; i++) {
- for (j=0; j<len; j++) {
- p1 = projverts[i];
- p2 = projverts[(i+1)%f->len];
- if (convexangle(
- if (linecrosses(p1, p2,
- }
- }
-
- if (projverts != projectverts) MEM_freeN(projverts);
- if (edgeverts != edgevertsstack) MEM_freeN(edgeverts);
+ VECADD(v1, v1, mid);
+ VECADD(v2, v2, mid);
}
-#endif
/*
* POLY ROTATE PLANE
@@ -337,8 +299,6 @@
double angle;
int i;
- compute_poly_normal(normal, verts, nverts);
-
Crossf(axis, up, normal);
axis[0] *= -1;
axis[1] *= -1;
@@ -512,6 +472,48 @@
return w1 == w2 && w2 == w3 && w3 == w4 && w4==w5;
}
+int windingf(float *a, float *b, float *c)
+{
+ float v1[3], v2[3], v[3];
+
+ VECSUB(v1, b, a);
+ VECSUB(v2, b, c);
+
+ v1[2] = 0;
+ v2[2] = 0;
+
+ Normalize(v1);
+ Normalize(v2);
+
+ Crossf(v, v1, v2);
+
+ /*!! (turns nonzero into 1) is likely not necassary,
+ since '>' I *think* should always
+ return 0 or 1, but I'm not totally sure. . .*/
+ return !!(v[2] > 0);
+}
+
+/* detects if two line segments cross each other (intersects).
+ note, there could be more winding cases then there needs to be. */
+int linecrossesf(float *v1, float *v2, float *v3, float *v4)
+{
+ int w1, w2, w3, w4, w5;
+
+ /*w1 = winding(v1, v3, v4);
+ w2 = winding(v2, v3, v4);
+ w3 = winding(v3, v1, v2);
+ w4 = winding(v4, v1, v2);
+
+ return (w1 == w2) && (w3 == w4);*/
+
+ w1 = windingf(v1, v3, v2);
+ w2 = windingf(v2, v4, v1);
+ w3 = !windingf(v1, v2, v3);
+ w4 = windingf(v3, v2, v4);
+ w5 = !windingf(v3, v1, v4);
+ return w1 == w2 && w2 == w3 && w3 == w4 && w4==w5;
+}
+
int goodline(float (*projectverts)[3], BMFace *f, int v1i,
int v2i, int v3i, int nvert) {
BMLoop *l = f->loopbase;
@@ -528,7 +530,7 @@
do {
i = l->v->head.eflag2;
if (i == v1i || i == v2i || i == v3i) {
- l = l->head.next;
+ l = (BMLoop*)l->head.next;
continue;
}
@@ -539,7 +541,7 @@
if (point_in_triangle(v1, v2, v3, pv1)) return 0;
if (point_in_triangle(v3, v2, v1, pv1)) return 0;
- l = l->head.next;
+ l = (BMLoop*)l->head.next;
} while (l != f->loopbase);
return 1;
}
@@ -617,7 +619,6 @@
int newedgeflag, int newfaceflag)
{
int i, done, nvert;
- float no[3];
BMLoop *l, *newl, *nextloop;
BMVert *v;
@@ -696,3 +697,122 @@
}
}
}
+
+#if 1
+/*each pair of loops defines a new edge, a split. this function goes
+ through and sets pairs that are geometrically invalid to null. a
+ split is invalid, if it forms a concave angle or it intersects other
+ edges in the face, or it intersects another split. in the case of
+ intersecting splits, only the first of the set of intersecting
+ splits survives.*/
+void BM_LegalSplits(BMesh *bm, BMFace *f, BMLoop *(*loops)[2], int len)
+{
+ BMIter iter;
+ BMLoop *l;
+ float v1[3], v2[3], v3[3], v4[3], no[3], mid[3], *p1, *p2;
+ float out[3] = {-234324.0f, -234324.0f, 0.0f};
+ float projectverts[100][3];
+ float edgevertsstack[200][3];
+ float (*projverts)[3] = projectverts;
+ float (*edgeverts)[3] = edgevertsstack;
+ int i, j, a=0, clen;
+
+ if (f->len > 100) projverts = MEM_mallocN(sizeof(float)*3*f->len, "projvertsb");
+ if (len > 100) edgeverts = MEM_mallocN(sizeof(float)*3*2*len, "edgevertsb");
+
+ i = 0;
+ l = BMIter_New(&iter, bm, BM_LOOPS_OF_FACE, f);
+ for (; l; l=BMIter_Step(&iter)) {
+ l->head.eflag2 = i;
+ VECCOPY(projverts[i], l->v->co);
+ i++;
+ }
+
+ for (i=0; i<len; i++) {
+ VECCOPY(v1, loops[i][0]->v->co);
+ VECCOPY(v2, loops[i][1]->v->co);
+
+ shrink_edgef(v1, v2, 0.9999f);
+
+ VECCOPY(edgeverts[a], v1);
+ a++;
+ VECCOPY(edgeverts[a], v2);
+ a++;
+ }
+
+ compute_poly_normal(no, projverts, f->len);
+ poly_rotate_plane(no, projverts, f->len);
+ poly_rotate_plane(no, edgeverts, len*2);
+
+ for (i=0; i<f->len; i++) {
+ p1 = projverts[i];
+ out[0] = MAX2(out[0], p1[0]) + 0.001;
+ out[1] = MAX2(out[1], p1[1]) + 0.001;
+ out[2] = 0.0f;
+ }
+
+ /*do convexity test*/
+ for (i=0; i<len; i++) {
+ //l = (BMLoop*)loops[i][0]->head.prev;
+ //VECCOPY(v1, projverts[l->head.eflag2]);
+
+ l = (BMLoop*)loops[i][0];
+ VECCOPY(v2, edgeverts[i*2]);
+
+ l = (BMLoop*)loops[i][1];
+ VECCOPY(v3, edgeverts[i*2+1]);
+
+ //l = (BMLoop*)loops[i][1]->head.next;
+ //VECCOPY(v4, projverts[l->head.eflag2]);
+
+ VecAddf(mid, v2, v3);
+ VecMulf(mid, 0.5f);
+
+ clen = 0;
+ for (j=0; j<f->len; j++) {
+ p1 = projverts[j];
+ p2 = projverts[(j+1)%f->len];
+
+ VECCOPY(v1, p1);
+ VECCOPY(v2, p2);
+
+ shrink_edgef(v1, v2, 1.001f);
+
+ if (linecrossesf(p1, p2, mid, out)) clen++;
+ else if (linecrossesf(p2, p1, out, mid)) clen++;
+ else if (linecrossesf(p1, p2, out, mid)) clen++;
+
+ }
+
+ if (clen%2 == 0) {
+ loops[i][0] = NULL;
+ }
+ //if (testedgeside(v1, v2, v3)) { // || testedgeside(v2, v3, v4)) {
+ // loops[i][0] = NULL;
+ //}
+ }
+
+ /*do line crossing tests*/
+ for (i=0; i<f->len; i++) {
+ p1 = projverts[i];
+ p2 = projverts[(i+1)%f->len];
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list