[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [44884] trunk/blender/source/blender/bmesh : bmesh: Fkey now creates faces from 5 or more disconnected vertices.
Campbell Barton
ideasman42 at gmail.com
Wed Mar 14 23:57:21 CET 2012
Revision: 44884
http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=44884
Author: campbellbarton
Date: 2012-03-14 22:57:15 +0000 (Wed, 14 Mar 2012)
Log Message:
-----------
bmesh: Fkey now creates faces from 5 or more disconnected vertices.
Added function: BM_face_create_ngon_vcloud
creating quads and tris use this too since it finds the best face winding direction based on surrounding face (if any)
Modified Paths:
--------------
trunk/blender/source/blender/bmesh/intern/bmesh_construct.c
trunk/blender/source/blender/bmesh/intern/bmesh_construct.h
trunk/blender/source/blender/bmesh/operators/bmo_create.c
Modified: trunk/blender/source/blender/bmesh/intern/bmesh_construct.c
===================================================================
--- trunk/blender/source/blender/bmesh/intern/bmesh_construct.c 2012-03-14 22:39:56 UTC (rev 44883)
+++ trunk/blender/source/blender/bmesh/intern/bmesh_construct.c 2012-03-14 22:57:15 UTC (rev 44884)
@@ -263,10 +263,198 @@
return NULL;
}
+typedef struct AngleIndexPair {
+ float angle;
+ int index;
+} AngleIndexPair;
-/* bmesh_make_face_from_face(BMesh *bm, BMFace *source, BMFace *target) */
+static int angle_index_pair_cmp(const void *e1, const void *e2)
+{
+ const AngleIndexPair *p1 = e1, *p2 = e2;
+ if (p1->angle > p2->angle) return 1;
+ else if (p1->angle < p2->angle) return -1;
+ else return 0;
+}
+/**
+ * Makes an NGon from an un-ordered set of verts
+ *
+ * assumes...
+ * - that verts are only once in the list.
+ * - that the verts have roughly planer bounds
+ * - that the verts are roughly circular
+ * there can be concave areas but overlapping folds from the center point will fail.
+ *
+ * a brief explanation of the method used
+ * - find the center point
+ * - find the normal of the vcloud
+ * - order the verts around the face based on their angle to the normal vector at the center point.
+ *
+ * \note Since this is a vcloud there is no direction.
+ */
+BMFace *BM_face_create_ngon_vcloud(BMesh *bm, BMVert **vert_arr, int totv, int nodouble)
+{
+ BMFace *f;
+ float totv_inv = 1.0f / (float)totv;
+ int i = 0;
+
+ float cent[3], nor[3];
+
+ float *far = NULL, *far_cross = NULL;
+
+ float far_vec[3];
+ float far_cross_vec[3];
+ float sign_vec[3]; /* work out if we are pos/neg angle */
+
+ float far_dist, far_best;
+ float far_cross_dist, far_cross_best = 0.0f;
+
+ AngleIndexPair *vang;
+
+ BMVert **vert_arr_map;
+ BMEdge **edge_arr;
+ int i_prev;
+
+ unsigned int winding[2] = {0, 0};
+
+ /* get the center point and collect vector array since we loop over these a lot */
+ zero_v3(cent);
+ for (i = 0; i < totv; ++i) {
+ madd_v3_v3fl(cent, vert_arr[i]->co, totv_inv);
+ }
+
+
+ /* find the far point from cent */
+ far_best = 0.0f;
+ for (i = 0; i < totv; ++i) {
+ far_dist = len_squared_v3v3(vert_arr[i]->co, cent);
+ if (far_dist > far_best || far == NULL) {
+ far = vert_arr[i]->co;
+ far_best = far_dist;
+ }
+ }
+
+ sub_v3_v3v3(far_vec, far, cent);
+ far_dist = len_v3(far_vec); /* real dist */
+
+ /* --- */
+
+ /* find a point 90deg about to compare with */
+ far_cross_best = 0.0f;
+ for (i = 0; i < totv; ++i) {
+
+ if (far == vert_arr[i]->co) {
+ continue;
+ }
+
+ sub_v3_v3v3(far_cross_vec, vert_arr[i]->co, cent);
+ far_cross_dist = normalize_v3(far_cross_vec);
+
+ /* more of a weight then a distance */
+ far_cross_dist = (/* first we want to have a value close to zero mapped to 1 */
+ 1.0 - fabsf(dot_v3v3(far_vec, far_cross_vec)) *
+
+ /* second we multiply by the distance
+ * so points close to the center are not preferred */
+ far_cross_dist);
+
+ if (far_cross_dist > far_cross_best || far_cross == NULL) {
+ far_cross = vert_arr[i]->co;
+ far_cross_best = far_cross_dist;
+ }
+ }
+
+ sub_v3_v3v3(far_cross_vec, far_cross, cent);
+
+ /* --- */
+
+ /* now we have 2 vectors we can have a cross product */
+ cross_v3_v3v3(nor, far_vec, far_cross_vec);
+ normalize_v3(nor);
+ cross_v3_v3v3(sign_vec, far_vec, nor); /* this vector should match 'far_cross_vec' closely */
+
+ /* --- */
+
+ /* now calcualte every points angle around the normal (signed) */
+ vang = MEM_mallocN(sizeof(AngleIndexPair) * totv, __func__);
+
+ for (i = 0; i < totv; ++i) {
+ float co[3];
+ float proj_vec[3];
+ float angle;
+
+ /* center relative vec */
+ sub_v3_v3v3(co, vert_arr[i]->co, cent);
+
+ /* align to plane */
+ project_v3_v3v3(proj_vec, co, nor);
+ sub_v3_v3(co, proj_vec);
+
+ /* now 'co' is valid - we can compare its angle against the far vec */
+ angle = angle_v3v3(far_vec, co);
+
+ if (dot_v3v3(co, sign_vec) < 0.0f) {
+ angle = -angle;
+ }
+
+ vang[i].angle = angle;
+ vang[i].index = i;
+ }
+
+ /* sort by angle and magic! - we have our ngon */
+ qsort(vang, totv, sizeof(AngleIndexPair), angle_index_pair_cmp);
+
+ /* --- */
+
+ /* create edges and find the winding (if faces are attached to any existing edges) */
+ vert_arr_map = MEM_mallocN(sizeof(BMVert **) * totv, __func__);
+ edge_arr = MEM_mallocN(sizeof(BMEdge **) * totv, __func__);
+
+ for (i = 0; i < totv; ++i) {
+ vert_arr_map[i] = vert_arr[vang[i].index];
+ }
+ MEM_freeN(vang);
+
+ i_prev = totv - 1;
+ for (i = 0; i < totv; ++i) {
+ edge_arr[i] = BM_edge_create(bm, vert_arr_map[i_prev], vert_arr_map[i], NULL, TRUE);
+
+ /* the edge may exist already and be attached to a face
+ * in this case we can find the best winding to use for the new face */
+ if (edge_arr[i]->l) {
+ BMVert *test_v1, *test_v2;
+ /* we want to use the reverse winding to the existing order */
+ BM_edge_ordered_verts(edge_arr[i], &test_v2, &test_v1);
+ winding[(vert_arr_map[i_prev] == test_v2)]++;
+
+ }
+
+ i_prev = i;
+ }
+
+ /* --- */
+
+ if (winding[0] < winding[1]) {
+ winding[0] = 1;
+ winding[1] = 0;
+ }
+ else {
+ winding[0] = 0;
+ winding[1] = 1;
+ }
+
+ /* --- */
+
+ /* create the face */
+ f = BM_face_create_ngon(bm, vert_arr_map[winding[0]], vert_arr_map[winding[1]], edge_arr, totv, nodouble);
+
+ MEM_freeN(edge_arr);
+ MEM_freeN(vert_arr_map);
+
+ return f;
+}
+
/**
* Called by operators to remove elements that they have marked for
* removal.
Modified: trunk/blender/source/blender/bmesh/intern/bmesh_construct.h
===================================================================
--- trunk/blender/source/blender/bmesh/intern/bmesh_construct.h 2012-03-14 22:39:56 UTC (rev 44883)
+++ trunk/blender/source/blender/bmesh/intern/bmesh_construct.h 2012-03-14 22:57:15 UTC (rev 44884)
@@ -38,6 +38,8 @@
BMFace *BM_face_create_ngon(BMesh *bm, BMVert *v1, BMVert *v2, BMEdge **edges, int len, int nodouble);
+BMFace *BM_face_create_ngon_vcloud(BMesh *bm, BMVert **vert_arr, int len, int nodouble);
+
void BMO_remove_tagged_faces(BMesh *bm, const short oflag);
void BMO_remove_tagged_edges(BMesh *bm, const short oflag);
void BMO_remove_tagged_verts(BMesh *bm, const short oflag);
Modified: trunk/blender/source/blender/bmesh/operators/bmo_create.c
===================================================================
--- trunk/blender/source/blender/bmesh/operators/bmo_create.c 2012-03-14 22:39:56 UTC (rev 44883)
+++ trunk/blender/source/blender/bmesh/operators/bmo_create.c 2012-03-14 22:57:15 UTC (rev 44884)
@@ -1390,45 +1390,8 @@
e = BM_edge_create(bm, verts[0], verts[1], NULL, TRUE);
BMO_elem_flag_enable(bm, e, ELE_OUT);
}
- else if (amount == 3) {
- /* create triangle */
- f = BM_face_create_quad_tri(bm, verts[0], verts[1], verts[2], NULL, NULL, TRUE);
+ else if (0) { /* nice feature but perhaps it should be a different tool? */
- if (f) {
- BMO_elem_flag_enable(bm, f, ELE_OUT);
- }
- }
- else if (amount == 4) {
- f = NULL;
-
- /* the order of vertices can be anything, 6 cases to check */
- if (is_quad_convex_v3(verts[0]->co, verts[1]->co, verts[2]->co, verts[3]->co)) {
- f = BM_face_create_quad_tri(bm, verts[0], verts[1], verts[2], verts[3], NULL, TRUE);
- }
- else if (is_quad_convex_v3(verts[0]->co, verts[2]->co, verts[3]->co, verts[1]->co)) {
- f = BM_face_create_quad_tri(bm, verts[0], verts[2], verts[3], verts[1], NULL, TRUE);
- }
- else if (is_quad_convex_v3(verts[0]->co, verts[2]->co, verts[1]->co, verts[3]->co)) {
- f = BM_face_create_quad_tri(bm, verts[0], verts[2], verts[1], verts[3], NULL, TRUE);
- }
- else if (is_quad_convex_v3(verts[0]->co, verts[1]->co, verts[3]->co, verts[2]->co)) {
- f = BM_face_create_quad_tri(bm, verts[0], verts[1], verts[3], verts[2], NULL, TRUE);
- }
- else if (is_quad_convex_v3(verts[0]->co, verts[3]->co, verts[2]->co, verts[1]->co)) {
- f = BM_face_create_quad_tri(bm, verts[0], verts[3], verts[2], verts[1], NULL, TRUE);
- }
- else if (is_quad_convex_v3(verts[0]->co, verts[3]->co, verts[1]->co, verts[2]->co)) {
- f = BM_face_create_quad_tri(bm, verts[0], verts[3], verts[1], verts[2], NULL, TRUE);
- }
- else {
- printf("cannot find nice quad from concave set of vertices\n");
- }
-
- if (f) {
- BMO_elem_flag_enable(bm, f, ELE_OUT);
- }
- }
- else {
/* tricky feature for making a line/edge from selection history...
*
* Rather then do nothing, when 5+ verts are selected, check if they are in our history,
@@ -1473,4 +1436,24 @@
}
/* done creating edges */
}
+ else {
+ /* TODO, all these verts may be connected by edges.
+ * we should check on this before assuming they are a random set of verts */
+
+ BMVert **vert_arr = MEM_mallocN(sizeof(BMVert **) * totv, __func__);
+ int i = 0;
+
+ BMO_ITER(v, &oiter, bm, op, "geom", BM_VERT) {
+ vert_arr[i] = v;
+ i++;
+ }
+
+ f = BM_face_create_ngon_vcloud(bm, vert_arr, totv, TRUE);
+
+ if (f) {
+ BMO_elem_flag_enable(bm, f, ELE_OUT);
+ }
+
+ MEM_freeN(vert_arr);
+ }
}
More information about the Bf-blender-cvs
mailing list