[Bf-blender-cvs] [98f4106] master: Metaball tessellation optimization (Octree to BVH)

Krzysztof Recko noreply at git.blender.org
Tue Apr 7 05:20:51 CEST 2015


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, jbloom at 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. @@




More information about the Bf-blender-cvs mailing list