[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [46081] trunk/blender/source/blender: Add convex hull operator (bmesh operator and wm operator.)
Nicholas Bishop
nicholasbishop at gmail.com
Sun Apr 29 18:09:40 CEST 2012
Revision: 46081
http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=46081
Author: nicholasbishop
Date: 2012-04-29 16:09:40 +0000 (Sun, 29 Apr 2012)
Log Message:
-----------
Add convex hull operator (bmesh operator and wm operator.)
Image-heavy user documentation:
http://wiki.blender.org/index.php/User:Nicholasbishop/Convex_Hull
Thanks to Campbell for providing code review:
http://codereview.appspot.com/6114060
Modified Paths:
--------------
trunk/blender/source/blender/bmesh/CMakeLists.txt
trunk/blender/source/blender/bmesh/intern/bmesh_error.h
trunk/blender/source/blender/bmesh/intern/bmesh_opdefines.c
trunk/blender/source/blender/bmesh/intern/bmesh_operators_private.h
trunk/blender/source/blender/editors/mesh/editmesh_tools.c
trunk/blender/source/blender/editors/mesh/mesh_intern.h
trunk/blender/source/blender/editors/mesh/mesh_ops.c
Added Paths:
-----------
trunk/blender/source/blender/bmesh/operators/bmo_hull.c
Modified: trunk/blender/source/blender/bmesh/CMakeLists.txt
===================================================================
--- trunk/blender/source/blender/bmesh/CMakeLists.txt 2012-04-29 16:09:28 UTC (rev 46080)
+++ trunk/blender/source/blender/bmesh/CMakeLists.txt 2012-04-29 16:09:40 UTC (rev 46081)
@@ -41,6 +41,7 @@
operators/bmo_dupe.c
operators/bmo_edgesplit.c
operators/bmo_extrude.c
+ operators/bmo_hull.c
operators/bmo_inset.c
operators/bmo_join_triangles.c
operators/bmo_mesh_conv.c
Modified: trunk/blender/source/blender/bmesh/intern/bmesh_error.h
===================================================================
--- trunk/blender/source/blender/bmesh/intern/bmesh_error.h 2012-04-29 16:09:28 UTC (rev 46080)
+++ trunk/blender/source/blender/bmesh/intern/bmesh_error.h 2012-04-29 16:09:40 UTC (rev 46081)
@@ -69,6 +69,7 @@
#define BMERR_NONMANIFOLD 8
#define BMERR_INVALID_SELECTION 9
#define BMERR_MESH_ERROR 10
+#define BMERR_CONVEX_HULL_FAILED 11
/* BMESH_ASSERT */
#ifdef WITH_ASSERT_ABORT
Modified: trunk/blender/source/blender/bmesh/intern/bmesh_opdefines.c
===================================================================
--- trunk/blender/source/blender/bmesh/intern/bmesh_opdefines.c 2012-04-29 16:09:28 UTC (rev 46080)
+++ trunk/blender/source/blender/bmesh/intern/bmesh_opdefines.c 2012-04-29 16:09:40 UTC (rev 46081)
@@ -1144,7 +1144,36 @@
BMO_OP_FLAG_UNTAN_MULTIRES
};
+/*
+ * Convex Hull
+ *
+ * Builds a convex hull from the vertices in 'input'.
+ *
+ * If 'use_existing_faces' is true, the hull will not output triangles
+ * that are covered by a pre-existing face.
+ *
+ * All hull vertices, faces, and edges are added to 'geomout'. Any
+ * input elements that end up inside the hull (i.e. are not used by an
+ * output face) are added to the 'interior_geom' slot. The
+ * 'unused_geom' slot will contain all interior geometry that is
+ * completely unused. Lastly, 'holes_geom' contains edges and faces
+ * that were in the input and are part of the hull.
+*/
+static BMOpDefine bmo_convex_hull_def = {
+ "convex_hull",
+ {{BMO_OP_SLOT_ELEMENT_BUF, "input"},
+ {BMO_OP_SLOT_BOOL, "use_existing_faces"},
+ /* Outputs */
+ {BMO_OP_SLOT_ELEMENT_BUF, "geomout"},
+ {BMO_OP_SLOT_ELEMENT_BUF, "interior_geom"},
+ {BMO_OP_SLOT_ELEMENT_BUF, "unused_geom"},
+ {BMO_OP_SLOT_ELEMENT_BUF, "holes_geom"},
+ {0} /* null-terminating sentinel */},
+ bmo_convex_hull_exec,
+ 0
+};
+
BMOpDefine *opdefines[] = {
&bmo_split_def,
&bmo_spin_def,
@@ -1214,6 +1243,7 @@
&bmo_inset_def,
&bmo_wireframe_def,
&bmo_vertex_slide_def,
+ &bmo_convex_hull_def,
};
int bmesh_total_ops = (sizeof(opdefines) / sizeof(void *));
Modified: trunk/blender/source/blender/bmesh/intern/bmesh_operators_private.h
===================================================================
--- trunk/blender/source/blender/bmesh/intern/bmesh_operators_private.h 2012-04-29 16:09:28 UTC (rev 46080)
+++ trunk/blender/source/blender/bmesh/intern/bmesh_operators_private.h 2012-04-29 16:09:40 UTC (rev 46081)
@@ -101,5 +101,6 @@
void bmo_solidify_face_region_exec(BMesh *bm, BMOperator *op);
void bmo_inset_exec(BMesh *bm, BMOperator *op);
void bmo_wireframe_exec(BMesh *bm, BMOperator *op);
+void bmo_convex_hull_exec(BMesh *bm, BMOperator *op);
#endif /* __BMESH_OPERATORS_PRIVATE_H__ */
Added: trunk/blender/source/blender/bmesh/operators/bmo_hull.c
===================================================================
--- trunk/blender/source/blender/bmesh/operators/bmo_hull.c (rev 0)
+++ trunk/blender/source/blender/bmesh/operators/bmo_hull.c 2012-04-29 16:09:40 UTC (rev 46081)
@@ -0,0 +1,742 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * Contributor(s): Nicholas Bishop
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+/** \file blender/bmesh/operators/bmo_hull.c
+ * \ingroup bmesh
+ */
+
+#include "MEM_guardedalloc.h"
+
+#include "BLI_ghash.h"
+#include "BLI_listbase.h"
+#include "BLI_math.h"
+#include "BLI_utildefines.h"
+
+/* XXX: using 128 for totelem and pchunk of mempool, no idea what good
+ values would be though */
+#include "BLI_mempool.h"
+
+#include "bmesh.h"
+
+/* Internal operator flags */
+typedef enum {
+ HULL_FLAG_INPUT = (1 << 0),
+ HULL_FLAG_TETRA_VERT = (1 << 1),
+
+ HULL_FLAG_INTERIOR_ELE = (1 << 2),
+ HULL_FLAG_OUTPUT_GEOM = (1 << 3),
+
+ HULL_FLAG_DEL = (1 << 4),
+ HULL_FLAG_HOLE = (1 << 5)
+} HullFlags;
+
+/* Store hull triangles seperate from BMesh faces until the end; this
+ way we don't have to worry about cleaning up extraneous edges or
+ incorrectly deleting existing geometry. */
+typedef struct HullTriangle {
+ BMVert *v[3];
+ float no[3];
+ int skip;
+} HullTriangle;
+
+/* These edges define the hole created in the hull by deleting faces
+ that can "see" a new vertex (the boundary edges then form the edge
+ of a new triangle fan that has the new vertex as its center) */
+typedef struct HullBoundaryEdge {
+ struct HullBoundaryEdge *next, *prev;
+ BMVert *v[2];
+} HullBoundaryEdge;
+
+
+
+/*************************** Boundary Edges ***************************/
+
+static int edge_match(BMVert *e1_0, BMVert *e1_1, BMVert *e2[2])
+{
+ return (e1_0 == e2[0] && e1_1 == e2[1]) ||
+ (e1_0 == e2[1] && e1_1 == e2[0]);
+}
+
+/* Returns true if the edge (e1, e2) is already in edges; that edge is
+ deleted here as well. if not found just returns 0 */
+static int check_for_dup(ListBase *edges, BLI_mempool *pool,
+ BMVert *e1, BMVert *e2)
+{
+ HullBoundaryEdge *e, *next;
+
+ for (e = edges->first; e; e = next) {
+ next = e->next;
+
+ if (edge_match(e1, e2, e->v)) {
+ /* remove the interior edge */
+ BLI_remlink(edges, e);
+ BLI_mempool_free(pool, e);
+ return 1;
+ }
+ }
+
+ return 0;
+}
+
+static void expand_boundary_edges(ListBase *edges, BLI_mempool *edge_pool,
+ const HullTriangle *t)
+{
+ HullBoundaryEdge *new;
+ int i;
+
+ /* Insert each triangle edge into the boundary list; if any of
+ its edges are already in there, remove the edge entirely */
+ for (i = 0; i < 3; i++) {
+ if (!check_for_dup(edges, edge_pool, t->v[i], t->v[(i + 1) % 3])) {
+ new = BLI_mempool_calloc(edge_pool);
+ new->v[0] = t->v[i];
+ new->v[1] = t->v[(i + 1) % 3];
+ BLI_addtail(edges, new);
+ }
+ }
+}
+
+
+
+/*************************** Hull Triangles ***************************/
+
+static void hull_add_triangle(GHash *hull_triangles, BLI_mempool *pool,
+ BMVert *v1, BMVert *v2, BMVert *v3)
+{
+ HullTriangle *t;
+
+ t = BLI_mempool_calloc(pool);
+ t->v[0] = v1;
+ t->v[1] = v2;
+ t->v[2] = v3;
+
+ BLI_ghash_insert(hull_triangles, t, NULL);
+ normal_tri_v3(t->no, v1->co, v2->co, v3->co);
+}
+
+static int hull_point_tri_side(const HullTriangle *t, const float co[3])
+{
+ float p[3], d;
+ sub_v3_v3v3(p, co, t->v[0]->co);
+ d = dot_v3v3(t->no, p);
+ if (d < 0) return -1;
+ else if (d > 0) return 1;
+ else return 0;
+}
+
+/* Get all hull triangles that vertex 'v' is outside of */
+static GHash *hull_triangles_v_outside(GHash *hull_triangles, const BMVert *v)
+{
+ GHash *outside;
+ GHashIterator iter;
+
+ outside = BLI_ghash_new(BLI_ghashutil_ptrhash,
+ BLI_ghashutil_ptrcmp,
+ "outside");
+
+ GHASH_ITER (iter, hull_triangles) {
+ HullTriangle *t = BLI_ghashIterator_getKey(&iter);
+
+ if (hull_point_tri_side(t, v->co) >= 0)
+ BLI_ghash_insert(outside, t, NULL);
+ }
+
+ return outside;
+}
+
+/* Similar to above, but just get true/false rather than triangles */
+static int hull_test_v_outside(GHash *hull_triangles, const BMVert *v)
+{
+ GHashIterator iter;
+
+ GHASH_ITER (iter, hull_triangles) {
+ HullTriangle *t = BLI_ghashIterator_getKey(&iter);
+
+ if (hull_point_tri_side(t, v->co) >= 0)
+ return TRUE;
+ }
+
+ return FALSE;
+}
+
+
+/* For vertex 'v', find which triangles must be deleted to extend the
+ hull; find the boundary edges of that hole so that it can be filled
+ with connections to the new vertex, and update the hull_triangles
+ to delete the marked triangles */
+static void add_point(GHash *hull_triangles, BLI_mempool *hull_pool,
+ BLI_mempool *edge_pool, GHash *outside, BMVert *v)
+{
+ ListBase edges = {NULL, NULL};
+ HullBoundaryEdge *e, *next;
+ GHashIterator iter;
+
+ GHASH_ITER (iter, outside) {
+ HullTriangle *t = BLI_ghashIterator_getKey(&iter);
+ expand_boundary_edges(&edges, edge_pool, t);
+
+ /* Delete the triangle */
+ BLI_ghash_remove(hull_triangles, t, NULL, NULL);
+ BLI_mempool_free(hull_pool, t);
+ }
+
+ /* Fill hole boundary with triangles to new point */
+ for (e = edges.first; e; e = next) {
+ next = e->next;
+ hull_add_triangle(hull_triangles, hull_pool, e->v[0], e->v[1], v);
+ BLI_mempool_free(edge_pool, e);
+ }
+}
+
+static BMFace *hull_find_example_face(BMesh *bm, BMEdge *e)
+{
+ BMIter iter;
+ BMFace *f;
+
+ BM_ITER_ELEM (f, &iter, e, BM_FACES_OF_EDGE) {
+ if (BMO_elem_flag_test(bm, f, HULL_FLAG_INPUT) ||
+ !BMO_elem_flag_test(bm, f, HULL_FLAG_OUTPUT_GEOM))
+ return f;
+ }
+
+ return NULL;
+}
+
+static void hull_output_triangles(BMesh *bm, GHash *hull_triangles)
+{
+ GHashIterator iter;
+
+ GHASH_ITER (iter, hull_triangles) {
+ HullTriangle *t = BLI_ghashIterator_getKey(&iter);
+
+ if (!t->skip) {
+ BMEdge *edges[3] = {
+ BM_edge_create(bm, t->v[0], t->v[1], NULL, TRUE),
+ BM_edge_create(bm, t->v[1], t->v[2], NULL, TRUE),
+ BM_edge_create(bm, t->v[2], t->v[0], NULL, TRUE)
+ };
+ BMFace *f, *example = NULL;
+ int i;
+
+ /* Look for an adjacent face that existed before the hull */
+ for (i = 0; i < 3; i++) {
+ if (!example)
+ example = hull_find_example_face(bm, edges[i]);
+ }
+
+ f = BM_face_create_quad_tri_v(bm, t->v, 3, example, FALSE);
+ BM_face_copy_shared(bm, f);
+
+ /* Mark face/verts/edges for 'geomout' slot and select */
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list