[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [51558] trunk/blender/source/blender: Partially replace convex hull implementation with Bullet implementation
Nicholas Bishop
nicholasbishop at gmail.com
Wed Oct 24 01:54:16 CEST 2012
Revision: 51558
http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=51558
Author: nicholasbishop
Date: 2012-10-23 23:54:15 +0000 (Tue, 23 Oct 2012)
Log Message:
-----------
Partially replace convex hull implementation with Bullet implementation
* Bullet's convex hull implementation is significantly more robust
than the one I implemented, as well as being faster.
* This fixes bug [#32864] "Convex Hull fails in some cases."
projects.blender.org/tracker/?func=detail&aid=32864&group_id=9&atid=498
That bug, and others like it, relate to the poor handling of
co-planar surfaces in the input. Pretty much any model that is
simple-subdivided a few times gave very bad results before, Bullet's
implementation handles this much better.
* In order to ensure a smooth transition, the Bullet output is
translated into the existing HullTriangle hash structure. This makes
it easy to ensure that the existing slot output stays the same; the
interactions between the slots are somewhat complicated, detangling
is a TODO.
* Reviewed by Brecht:
https://codereview.appspot.com/6741063
Modified Paths:
--------------
trunk/blender/source/blender/bmesh/CMakeLists.txt
trunk/blender/source/blender/bmesh/SConscript
trunk/blender/source/blender/bmesh/intern/bmesh_opdefines.c
trunk/blender/source/blender/bmesh/operators/bmo_hull.c
trunk/blender/source/blender/editors/mesh/CMakeLists.txt
trunk/blender/source/blender/editors/mesh/SConscript
trunk/blender/source/blender/editors/mesh/editmesh_tools.c
trunk/blender/source/blender/editors/mesh/mesh_ops.c
Modified: trunk/blender/source/blender/bmesh/CMakeLists.txt
===================================================================
--- trunk/blender/source/blender/bmesh/CMakeLists.txt 2012-10-23 23:54:02 UTC (rev 51557)
+++ trunk/blender/source/blender/bmesh/CMakeLists.txt 2012-10-23 23:54:15 UTC (rev 51558)
@@ -29,6 +29,7 @@
../blenlib
../makesdna
../../../intern/guardedalloc
+ ../../../extern/bullet2/src
)
set(INC_SYS
@@ -113,4 +114,8 @@
set(CMAKE_C_FLAGS "${CMAKE_C_FLAGS} /WX")
endif()
+if(WITH_BULLET)
+ add_definitions(-DWITH_BULLET)
+endif()
+
blender_add_lib(bf_bmesh "${SRC}" "${INC}" "${INC_SYS}")
Modified: trunk/blender/source/blender/bmesh/SConscript
===================================================================
--- trunk/blender/source/blender/bmesh/SConscript 2012-10-23 23:54:02 UTC (rev 51557)
+++ trunk/blender/source/blender/bmesh/SConscript 2012-10-23 23:54:15 UTC (rev 51558)
@@ -13,7 +13,12 @@
'../makesdna',
'../blenkernel',
'#/intern/guardedalloc',
+ '#/extern/bullet2/src'
]
defs = []
+
+if env['WITH_BF_BULLET']:
+ defs.append('WITH_BULLET')
+
env.BlenderLib ( libname = 'bf_bmesh', sources = sources, includes = Split(incs), libtype = ['core','player'], defines=defs, priority=[100, 100], compileflags=cflags )
Modified: trunk/blender/source/blender/bmesh/intern/bmesh_opdefines.c
===================================================================
--- trunk/blender/source/blender/bmesh/intern/bmesh_opdefines.c 2012-10-23 23:54:02 UTC (rev 51557)
+++ trunk/blender/source/blender/bmesh/intern/bmesh_opdefines.c 2012-10-23 23:54:15 UTC (rev 51558)
@@ -1162,6 +1162,7 @@
BMO_OP_FLAG_UNTAN_MULTIRES
};
+#ifdef WITH_BULLET
/*
* Convex Hull
*
@@ -1191,6 +1192,7 @@
bmo_convex_hull_exec,
0
};
+#endif
/*
* Symmetrize
@@ -1227,7 +1229,9 @@
&bmo_collapse_uvs_def,
&bmo_connect_verts_def,
&bmo_contextual_create_def,
+#ifdef WITH_BULLET
&bmo_convex_hull_def,
+#endif
&bmo_create_circle_def,
&bmo_create_cone_def,
&bmo_create_cube_def,
Modified: trunk/blender/source/blender/bmesh/operators/bmo_hull.c
===================================================================
--- trunk/blender/source/blender/bmesh/operators/bmo_hull.c 2012-10-23 23:54:02 UTC (rev 51557)
+++ trunk/blender/source/blender/bmesh/operators/bmo_hull.c 2012-10-23 23:54:15 UTC (rev 51558)
@@ -24,19 +24,17 @@
* \ingroup bmesh
*/
+#ifdef WITH_BULLET
+
#include "MEM_guardedalloc.h"
+#include "BLI_array.h"
#include "BLI_ghash.h"
#include "BLI_listbase.h"
#include "BLI_math.h"
#include "BLI_utildefines.h"
-/*XXX: This operator doesn't work well (at all?) for flat surfaces with
- * >3 sides - creating overlapping faces at times.
- * An easy workaround is to add in some noise but this is
- * weak and unreliable, ideally this would detect flat surfaces
- * (possibly making them into ngons) - see
- */
+#include "Bullet-C-Api.h"
/* XXX: using 128 for totelem and pchunk of mempool, no idea what good
* values would be though */
@@ -46,21 +44,15 @@
#include "intern/bmesh_operators_private.h" /* own include */
-#define HULL_EPSILON_FLT 0.0001f
-/* values above 0.0001 cause errors, see below for details, don't increase
- * without checking against bug [#32027] */
-#define HULL_EPSILON_DOT_FLT 0.00000001f
-
/* 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_INTERIOR_ELE = (1 << 1),
+ HULL_FLAG_OUTPUT_GEOM = (1 << 2),
- HULL_FLAG_DEL = (1 << 4),
- HULL_FLAG_HOLE = (1 << 5)
+ HULL_FLAG_DEL = (1 << 3),
+ HULL_FLAG_HOLE = (1 << 4)
} HullFlags;
/* Store hull triangles separate from BMesh faces until the end; this
@@ -72,65 +64,8 @@
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_v1, BMVert *e1_v2, BMVert *e2[2])
-{
- return (e1_v1 == e2[0] && e1_v2 == e2[1]) ||
- (e1_v1 == e2[1] && e1_v2 == 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 *v1, BMVert *v2)
-{
- HullBoundaryEdge *e, *e_next;
-
- for (e = edges->first; e; e = e_next) {
- e_next = e->next;
-
- if (edge_match(v1, v2, 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 *e_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])) {
- e_new = BLI_mempool_calloc(edge_pool);
- e_new->v[0] = t->v[i];
- e_new->v[1] = t->v[(i + 1) % 3];
- BLI_addtail(edges, e_new);
- }
- }
-}
-
-
-
/*************************** Hull Triangles ***************************/
static void hull_add_triangle(BMesh *bm, GHash *hull_triangles, BLI_mempool *pool,
@@ -152,75 +87,6 @@
normal_tri_v3(t->no, v1->co, v2->co, v3->co);
}
-static int hull_point_tri_side(const HullTriangle *t, const float co[3])
-{
- /* Added epsilon to fix bug [#31941], improves output when some
- * vertices are nearly coplanar. Might need further tweaking for
- * other cases though.
- * ...
- * Update: epsilon of 0.0001 causes [#32027], use HULL_EPSILON_DOT_FLT
- * and give it a much smaller value
- * */
- float p[3], d;
- sub_v3_v3v3(p, co, t->v[0]->co);
- d = dot_v3v3(t->no, p);
- if (d < -HULL_EPSILON_DOT_FLT) return -1;
- else if (d > HULL_EPSILON_DOT_FLT) 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_ptr_new("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;
-}
-
-/* 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(BMesh *bm, GHash *hull_triangles, BLI_mempool *hull_pool,
- BLI_mempool *edge_pool, GHash *outside, BMVert *v)
-{
- ListBase edges = {NULL, NULL};
- HullBoundaryEdge *e, *e_next;
- GHashIterator iter;
-
- GHASH_ITER (iter, outside) {
- HullTriangle *t = BLI_ghashIterator_getKey(&iter);
- int i;
-
- expand_boundary_edges(&edges, edge_pool, t);
-
- /* Mark triangle's vertices as interior */
- for (i = 0; i < 3; i++)
- BMO_elem_flag_enable(bm, t->v[i], HULL_FLAG_INTERIOR_ELE);
-
- /* 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 = e_next) {
- e_next = e->next;
- hull_add_triangle(bm, 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;
@@ -362,158 +228,6 @@
-/************************* Initial Tetrahedron ************************/
-
-static void hull_add_tetrahedron(BMesh *bm, GHash *hull_triangles, BLI_mempool *pool,
- BMVert *tetra[4])
-{
- float center[3];
- int i, indices[4][3] = {
- {0, 1, 2},
- {0, 2, 3},
- {1, 0, 3},
- {2, 1, 3}
- };
-
- /* Calculate center */
- zero_v3(center);
- for (i = 0; i < 4; i++)
- add_v3_v3(center, tetra[i]->co);
- mul_v3_fl(center, 0.25f);
-
- for (i = 0; i < 4; i++) {
- BMVert *v1 = tetra[indices[i][0]];
- BMVert *v2 = tetra[indices[i][1]];
- BMVert *v3 = tetra[indices[i][2]];
- float no[3], d[3];
-
- normal_tri_v3(no, v1->co, v2->co, v3->co);
- sub_v3_v3v3(d, center, v1->co);
- if (dot_v3v3(no, d) > 0)
- SWAP(BMVert *, v1, v3);
-
- hull_add_triangle(bm, hull_triangles, pool, v1, v2, v3);
- }
-}
-
-/* For each axis, get the minimum and maximum input vertices */
-static void hull_get_min_max(BMesh *bm, BMOperator *op,
- BMVert *min[3], BMVert *max[3])
-{
- BMOIter oiter;
- BMVert *v;
-
- min[0] = min[1] = min[2] = NULL;
- max[0] = max[1] = max[2] = NULL;
-
- BMO_ITER (v, &oiter, bm, op, "input", BM_VERT) {
- int i;
-
- for (i = 0; i < 3; i++) {
- if (!min[i] || v->co[i] < min[i]->co[i])
- min[i] = v;
- if (!max[i] || v->co[i] > max[i]->co[i])
- max[i] = v;
- }
- }
-}
-
-/* Returns true if input is coplanar */
-static int hull_find_large_tetrahedron(BMesh *bm, BMOperator *op,
- BMVert *tetra[4])
-{
- BMVert *min[3], *max[3], *v;
- BMOIter oiter;
- float widest_axis_len, largest_dist, plane_normal[3];
- int i, j, widest_axis;
-
- tetra[0] = tetra[1] = tetra[2] = tetra[3] = NULL;
- hull_get_min_max(bm, op, min, max);
-
- /* Check for flat axis */
- for (i = 0; i < 3; i++) {
- if (min[i] == max[i]) {
- return TRUE;
- }
- }
-
- /* Find widest axis */
- widest_axis_len = 0.0f;
- widest_axis = 0; /* set here in the unlikey case this isn't set below */
- for (i = 0; i < 3; i++) {
- float len = (max[i]->co[i] - min[i]->co[i]);
- if (len >= widest_axis_len) {
- widest_axis_len = len;
- widest_axis = i;
- }
- }
-
- /* Use widest axis for first two points */
- tetra[0] = min[widest_axis];
- tetra[1] = max[widest_axis];
- BMO_elem_flag_enable(bm, tetra[0], HULL_FLAG_TETRA_VERT);
- BMO_elem_flag_enable(bm, tetra[1], HULL_FLAG_TETRA_VERT);
-
- /* Choose third vertex farthest from existing line segment */
- largest_dist = 0;
- for (i = 0; i < 3; i++) {
- BMVert *v;
- float dist;
-
- if (i == widest_axis)
- continue;
-
- v = min[i];
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list