Commit: 98f41066943d8b1cf9236d6b358d1e84c9e7cc4b
Author: Krzysztof Recko
Date: Tue Apr 7 12:44:39 2015 +1000
Branches: master
https://developer.blender.org/rB98f41066943d8b1cf9236d6b358d1e84c9e7cc4b
Metaball tessellation optimization (Octree to BVH)
Speedup is non-linear, 2x-10x faster is quite normal.
Patch T43678.
- Switched from an Octree to BVH.
- Finding first points of surface no longer "wastes" density function
evaluation: every result is cached.
- Use MemArena instead of using own memory management.
- Correct calculation of metaelem bounding box.
- Remove mball_count(): mballs are now counted "on the go".
===================================================================
M source/blender/blenkernel/BKE_mball.h
M source/blender/blenkernel/BKE_mball_tessellate.h
M source/blender/blenkernel/intern/mball_tessellate.c
M source/blender/windowmanager/intern/wm_init_exit.c
===================================================================
diff --git a/source/blender/blenkernel/BKE_mball.h
b/source/blender/blenkernel/BKE_mball.h
index 70f932f..321cbbb 100644
--- a/source/blender/blenkernel/BKE_mball.h
+++ b/source/blender/blenkernel/BKE_mball.h
@@ -45,8 +45,6 @@ struct MetaBall *BKE_mball_copy(struct MetaBall *mb);
void BKE_mball_make_local(struct MetaBall *mb);
-void BKE_mball_cubeTable_free(void);
-
bool BKE_mball_is_basis_for(struct Object *ob1, struct Object *ob2);
bool BKE_mball_is_basis(struct Object *ob);
struct Object *BKE_mball_basis_find(struct Scene *scene, struct Object *ob);
diff --git a/source/blender/blenkernel/BKE_mball_tessellate.h
b/source/blender/blenkernel/BKE_mball_tessellate.h
index a3d3e19..361f31b 100644
--- a/source/blender/blenkernel/BKE_mball_tessellate.h
+++ b/source/blender/blenkernel/BKE_mball_tessellate.h
@@ -31,4 +31,6 @@ void BKE_mball_polygonize(
struct EvaluationContext *eval_ctx, struct Scene *scene,
struct Object *ob, struct ListBase *dispbase);
+void BKE_mball_cubeTable_free(void);
+
#endif /* __BKE_MBALL_TESSELLATE_H__ */
diff --git a/source/blender/blenkernel/intern/mball_tessellate.c
b/source/blender/blenkernel/intern/mball_tessellate.c
index 0402494..080a8ce 100644
--- a/source/blender/blenkernel/intern/mball_tessellate.c
+++ b/source/blender/blenkernel/intern/mball_tessellate.c
@@ -44,26 +44,21 @@
#include "BLI_path_util.h"
#include "BLI_math.h"
#include "BLI_utildefines.h"
+#include "BLI_memarena.h"
#include "BKE_global.h"
#include "BKE_depsgraph.h"
#include "BKE_scene.h"
#include "BKE_displist.h"
-#include "BKE_mball.h"
#include "BKE_mball_tessellate.h" /* own include */
-/* Data types */
+#include "BLI_strict_flags.h"
-typedef struct vertex { /* surface vertex */
- float co[3]; /* position and surface normal */
- float no[3];
-} VERTEX;
+/* experimental (faster) normal calculation */
+// #define USE_ACCUM_NORMAL
-typedef struct vertices { /* list of vertices in polygonization */
- int count, max; /* # vertices, max # allowed */
- VERTEX *ptr; /* dynamically allocated */
-} VERTICES;
+/* Data types */
typedef struct corner { /* corner of a cube */
int i, j, k; /* (i, j, k) is index within lattice */
@@ -102,74 +97,161 @@ typedef struct intlists { /* list of list of
integers */
struct intlists *next; /* remaining elements */
} INTLISTS;
-/* dividing scene using octal tree makes polygonisation faster */
-typedef struct ml_pointer {
- struct ml_pointer *next, *prev;
- struct MetaElem *ml;
-} ml_pointer;
-
-typedef struct octal_node {
- struct octal_node *nodes[8];/* children of current node */
- struct octal_node *parent; /* parent of current node */
- struct ListBase elems; /* ListBase of MetaElem pointers
(ml_pointer) */
- float x_min, y_min, z_min; /* 1st border point */
- float x_max, y_max, z_max; /* 7th border point */
- float x, y, z; /* center of node */
- int pos, neg; /* number of positive and negative
MetaElements in the node */
- int count; /* number of MetaElems, which belongs to
the node */
-} octal_node;
-
-typedef struct octal_tree {
- struct octal_node *first; /* first node */
- int pos, neg; /* number of positive and negative
MetaElements in the scene */
- short depth; /* number of scene subdivision */
-} octal_tree;
-
-struct pgn_elements {
- struct pgn_elements *next, *prev;
- char *data;
-};
+typedef struct Box { /* an AABB with pointer to metalelem */
+ float min[3], max[3];
+ const MetaElem *ml;
+} Box;
+
+typedef struct MetaballBVHNode { /* BVH node */
+ Box bb[2]; /* AABB of
children */
+ struct MetaballBVHNode *child[2];
+} MetaballBVHNode;
+
+typedef struct process { /* parameters, storage */
+ float thresh, size; /* mball threshold, single cube
size */
+ float delta; /* small delta for calculating
normals */
+ unsigned int converge_res; /* converge procedure resolution (more
= slower) */
+
+ MetaElem **mainb; /* array of all metaelems */
+ unsigned int totelem, mem; /* number of metaelems */
+
+ MetaballBVHNode metaball_bvh; /* The simplest bvh */
+ Box allbb; /* Bounding box of all metaelems */
-typedef struct process { /* parameters, function, storage */
- /* ** old G_mb contents ** */
- float thresh;
- int totelem;
- MetaElem **mainb;
- octal_tree *metaball_tree;
-
- /* ** old process contents ** */
-
- /* what happens here? floats, I think. */
- /* float (*function)(void); */ /* implicit surface function */
- float (*function)(struct process *, float, float, float);
- float size, delta; /* cube size, normal delta */
- int bounds; /* cube range within lattice */
- CUBES *cubes; /* active cubes */
- VERTICES vertices; /* surface vertices */
+ MetaballBVHNode **bvh_queue; /* Queue used during bvh traversal */
+ unsigned int bvh_queue_size;
+
+ CUBES *cubes; /* stack of cubes waiting for
polygonization */
CENTERLIST **centers; /* cube center hash table */
CORNER **corners; /* corner value hash table */
EDGELIST **edges; /* edge and vertex id hash table */
- /* Runtime things */
- int *indices;
- int totindex, curindex;
+ int (*indices)[4]; /* output indices */
+ unsigned int totindex; /* size of memory allocated for indices
*/
+ unsigned int curindex; /* number of currently added indices */
+
+ float (*co)[3], (*no)[3]; /* surface vertices - positions and normals
*/
+ unsigned int totvertex; /* memory size */
+ unsigned int curvertex; /* currently added vertices */
- int pgn_offset;
- struct pgn_elements *pgn_current;
- ListBase pgn_list;
+ /* memory allocation from common pool */
+ MemArena *pgn_elements;
} PROCESS;
/* Forward declarations */
-static int vertid(PROCESS *process, const CORNER *c1, const CORNER *c2,
MetaBall *mb);
-static int setcenter(PROCESS *process, CENTERLIST *table[], const int i, const
int j, const int k);
-static CORNER *setcorner(PROCESS *process, int i, int j, int k);
-static void converge(PROCESS *process, const float p1[3], const float p2[3],
float v1, float v2,
- float p[3], MetaBall *mb, int f);
+static int vertid(PROCESS *process, const CORNER *c1, const CORNER *c2);
+static void add_cube(PROCESS *process, int i, int j, int k);
+static void make_face(PROCESS *process, int i1, int i2, int i3, int i4);
+static void converge(PROCESS *process, const CORNER *c1, const CORNER *c2,
float r_p[3]);
+
+/* ******************* SIMPLE BVH ********************* */
+
+static void make_box_union(const BoundBox *a, const Box *b, Box *r_out)
+{
+ r_out->min[0] = min_ff(a->vec[0][0], b->min[0]);
+ r_out->min[1] = min_ff(a->vec[0][1], b->min[1]);
+ r_out->min[2] = min_ff(a->vec[0][2], b->min[2]);
+
+ r_out->max[0] = max_ff(a->vec[6][0], b->max[0]);
+ r_out->max[1] = max_ff(a->vec[6][1], b->max[1]);
+ r_out->max[2] = max_ff(a->vec[6][2], b->max[2]);
+}
+
+static void make_box_from_metaelem(Box *r, const MetaElem *ml)
+{
+ copy_v3_v3(r->max, ml->bb->vec[6]);
+ copy_v3_v3(r->min, ml->bb->vec[0]);
+ r->ml = ml;
+}
+
+/**
+ * Partitions part of mainb array [start, end) along axis s. Returns i,
+ * where centroids of elements in the [start, i) segment lie "on the right
side" of div,
+ * and elements in the [i, end) segment lie "on the left"
+ */
+static unsigned int partition_mainb(MetaElem **mainb, unsigned int start,
unsigned int end, unsigned int s, float div)
+{
+ unsigned int i = start, j = end - 1;
+ div *= 2.0f;
+
+ while (1) {
+ while (i < j && div > (mainb[i]->bb->vec[6][s] +
mainb[i]->bb->vec[0][s])) i++;
+ while (j > i && div < (mainb[j]->bb->vec[6][s] +
mainb[j]->bb->vec[0][s])) j--;
+
+ if (i >= j)
+ break;
+
+ SWAP(MetaElem *, mainb[i], mainb[j]);
+ i++;
+ j--;
+ }
+
+ if (i == start) {
+ i++;
+ }
+
+ return i;
+}
+
+/**
+ * Recursively builds a BVH, dividing elements along the middle of the longest
axis of allbox.
+ */
+static void build_bvh_spatial(
+ PROCESS *process, MetaballBVHNode *node,
+ unsigned int start, unsigned int end, const Box *allbox)
+{
+ unsigned int part, j, s;
+ float dim[3], div;
+
+ /* Maximum bvh queue size is number of nodes which are made, equals
calls to this function. */
+ process->bvh_queue_size++;
+ dim[0] = allbox->max[0] - allbox->min[0];
+ dim[1] = allbox->max[1] - allbox->min[1];
+ dim[2] = allbox->max[2] - allbox->min[2];
+
+ s = 0;
+ if (dim[1] > dim[0] && dim[1] > dim[2]) s = 1;
+ else if (dim[2] > dim[1] && dim[2] > dim[0]) s = 2;
+
+ div = allbox->min[s] + (dim[s] / 2.0f);
+
+ part = partition_mainb(process->mainb, start, end, s, div);
+
+ make_box_from_metaelem(&node->bb[0], process->mainb[start]);
+ node->child[0] = NULL;
+
+ if (part > start + 1) {
+ for (j = start; j < part; j++) {
+ make_box_union(process->mainb[j]->bb, &node->bb[0],
&node->bb[0]);
+ }
+
+ node->child[0] = BLI_memarena_alloc(process->pgn_elements,
sizeof(MetaballBVHNode));
+ build_bvh_spatial(process, node->child[0], start, part,
&node->bb[0]);
+ }
+
+ node->child[1] = NULL;
+ if (part < end) {
+ make_box_from_metaelem(&node->bb[1], process->mainb[part]);
+
+ if (part < end - 1) {
+ for (j = part; j < end; j++) {
+ make_box_union(process->mainb[j]->bb,
&node->bb[1], &node->bb[1]);
+ }
+
+ node->child[1] =
BLI_memarena_alloc(process->pgn_elements, sizeof(MetaballBVHNode));
+ build_bvh_spatial(process, node->child[1], part, end,
&node->bb[1]);
+ }
+ }
+ else {
+ INIT_MINMAX(node->bb[1].min, node->bb[1].max);
+ }
+}
/* ******************** ARITH ************************* */
-/* BASED AT CODE (but mostly rewritten) :
+/**
+ * BASED AT CODE (but mostly rewritten) :
* C code from the article
* "An Implicit Surface Polygonizer"
* by Jules Bloomenthal, jbl...@beauty.gmu.edu
@@ -178,9 +260,8 @@ static void converge(PROCESS *process, const float p1[3],
const float p2[3], flo
* Authored by Jules Bloomenthal, Xerox PARC.
* Copyright (c) Xerox Corporation, 1991. All rights reserved.
* Permission is granted to reproduce, use and distribute this code for
- * any and all purposes, provided that this notice appears in all copies. */
-
-#de
@@ Diff output truncated at 10240 characters. @@
_______________________________________________
Bf-blender-cvs mailing list
Bf-blender-cvs@blender.org
http://lists.blender.org/mailman/listinfo/bf-blender-cvs
