[Bf-blender-cvs] [e3033693f9c] strand_editmode: Initial implementation of Poisson disk sampling on meshes.
Lukas Tönne
noreply at git.blender.org
Fri Aug 25 10:22:54 CEST 2017
Commit: e3033693f9cba3f6117f44ea9df9d2f4e10e9851
Author: Lukas Tönne
Date: Fri Aug 25 09:19:49 2017 +0100
Branches: strand_editmode
https://developer.blender.org/rBe3033693f9cba3f6117f44ea9df9d2f4e10e9851
Initial implementation of Poisson disk sampling on meshes.
This is still buggy (uneven sample coverage) and needs changes to the
sampling system for better threading support.
The implementation is based on
Bowers, John, et al. "Parallel Poisson disk sampling with spectrum analysis on surfaces." ACM Transactions on Graphics (TOG). Vol. 29. No. 6. ACM, 2010.
===================================================================
M source/blender/blenkernel/BKE_mesh_sample.h
M source/blender/blenkernel/intern/hair.c
M source/blender/blenkernel/intern/mesh_sample.c
M tests/gtests/blenkernel/BKE_mesh_sample_test.cc
===================================================================
diff --git a/source/blender/blenkernel/BKE_mesh_sample.h b/source/blender/blenkernel/BKE_mesh_sample.h
index 4721e0aae2d..f089a098288 100644
--- a/source/blender/blenkernel/BKE_mesh_sample.h
+++ b/source/blender/blenkernel/BKE_mesh_sample.h
@@ -52,12 +52,13 @@ void BKE_mesh_sample_clear(struct MeshSample *sample);
/* ==== Sampling ==== */
+float* BKE_mesh_sample_calc_triangle_weights(struct DerivedMesh *dm, MeshSampleVertexWeightFp vertex_weight_cb, void *userdata, float *r_area);
+
struct MeshSampleGenerator *BKE_mesh_sample_gen_surface_vertices(struct DerivedMesh *dm);
/* face_weights is optional */
-struct MeshSampleGenerator *BKE_mesh_sample_gen_surface_random(struct DerivedMesh *dm, unsigned int seed);
-struct MeshSampleGenerator *BKE_mesh_sample_gen_surface_random_ex(struct DerivedMesh *dm, unsigned int seed,
- MeshSampleVertexWeightFp vertex_weight_cb, void *userdata, bool use_facearea);
+struct MeshSampleGenerator *BKE_mesh_sample_gen_surface_random(struct DerivedMesh *dm, unsigned int seed, MeshSampleVertexWeightFp vertex_weight_cb, void *userdata);
+struct MeshSampleGenerator *BKE_mesh_sample_gen_surface_random_ex(struct DerivedMesh *dm, unsigned int seed, float *tri_weights);
struct MeshSampleGenerator *BKE_mesh_sample_gen_surface_raycast(
struct DerivedMesh *dm,
@@ -66,6 +67,12 @@ struct MeshSampleGenerator *BKE_mesh_sample_gen_surface_raycast(
MeshSampleRayFp ray_cb,
void *userdata);
+int BKE_mesh_sample_poissondisk_max_samples(float mindist, float area, int max_samples);
+struct MeshSampleGenerator *BKE_mesh_sample_gen_surface_poissondisk_ex(struct DerivedMesh *dm, unsigned int seed, float mindist,
+ int num_uniform_samples, float *tri_weights);
+struct MeshSampleGenerator *BKE_mesh_sample_gen_surface_poissondisk(struct DerivedMesh *dm, unsigned int seed, float mindist, int max_samples,
+ MeshSampleVertexWeightFp vertex_weight_cb, void *userdata);
+
struct MeshSampleGenerator *BKE_mesh_sample_gen_volume_random_bbray(struct DerivedMesh *dm, unsigned int seed, float density);
void BKE_mesh_sample_free_generator(struct MeshSampleGenerator *gen);
diff --git a/source/blender/blenkernel/intern/hair.c b/source/blender/blenkernel/intern/hair.c
index f9e66a88b03..493f7220dd9 100644
--- a/source/blender/blenkernel/intern/hair.c
+++ b/source/blender/blenkernel/intern/hair.c
@@ -125,7 +125,7 @@ void BKE_hair_follicles_generate(HairPattern *hair, DerivedMesh *scalp, int coun
return;
}
- MeshSampleGenerator *gen = BKE_mesh_sample_gen_surface_random(scalp, seed);
+ MeshSampleGenerator *gen = BKE_mesh_sample_gen_surface_random(scalp, seed, NULL, NULL);
unsigned int i;
HairFollicle *foll = hair->follicles;
diff --git a/source/blender/blenkernel/intern/mesh_sample.c b/source/blender/blenkernel/intern/mesh_sample.c
index 9fefc28f74a..c4259c4b3b2 100644
--- a/source/blender/blenkernel/intern/mesh_sample.c
+++ b/source/blender/blenkernel/intern/mesh_sample.c
@@ -24,6 +24,8 @@
* Sample a mesh surface or volume and evaluate samples on deformed meshes.
*/
+#include <limits.h>
+
#include "MEM_guardedalloc.h"
#include "DNA_key_types.h"
@@ -31,8 +33,10 @@
#include "DNA_meshdata_types.h"
#include "BLI_utildefines.h"
+#include "BLI_ghash.h"
#include "BLI_math.h"
#include "BLI_rand.h"
+#include "BLI_sort.h"
#include "BLI_task.h"
#include "BKE_bvhutils.h"
@@ -451,7 +455,7 @@ static bool generator_random_make_sample(const MSurfaceSampleGenerator_Random *g
return true;
}
-BLI_INLINE float triangle_weight(DerivedMesh *dm, const MLoopTri *tri, MeshSampleVertexWeightFp vertex_weight_cb, void *userdata)
+BLI_INLINE float triangle_weight(DerivedMesh *dm, const MLoopTri *tri, const float *vert_weights, float *r_area)
{
MVert *mverts = dm->getVertArray(dm);
MLoop *mloops = dm->getLoopArray(dm);
@@ -463,11 +467,14 @@ BLI_INLINE float triangle_weight(DerivedMesh *dm, const MLoopTri *tri, MeshSampl
MVert *v3 = &mverts[index3];
float weight = area_tri_v3(v1->co, v2->co, v3->co);
+ if (r_area) {
+ *r_area = weight;
+ }
- if (vertex_weight_cb) {
- float w1 = vertex_weight_cb(dm, v1, index1, userdata);
- float w2 = vertex_weight_cb(dm, v2, index2, userdata);
- float w3 = vertex_weight_cb(dm, v3, index3, userdata);
+ if (vert_weights) {
+ float w1 = vert_weights[index1];
+ float w2 = vert_weights[index2];
+ float w3 = vert_weights[index3];
weight *= (w1 + w2 + w3) / 3.0f;
}
@@ -475,8 +482,64 @@ BLI_INLINE float triangle_weight(DerivedMesh *dm, const MLoopTri *tri, MeshSampl
return weight;
}
-MeshSampleGenerator *BKE_mesh_sample_gen_surface_random_ex(DerivedMesh *dm, unsigned int seed,
- MeshSampleVertexWeightFp vertex_weight_cb, void *userdata, bool use_facearea)
+float* BKE_mesh_sample_calc_triangle_weights(DerivedMesh *dm, MeshSampleVertexWeightFp vertex_weight_cb, void *userdata, float *r_area)
+{
+ int numverts = dm->getNumVerts(dm);
+ int numtris = dm->getNumLoopTri(dm);
+ int numweights = numtris;
+
+ float *vert_weights = NULL;
+ if (vertex_weight_cb) {
+ vert_weights = MEM_mallocN(sizeof(float) * (size_t)numverts, "mesh sample vertex weights");
+ {
+ MVert *mv = dm->getVertArray(dm);
+ for (int i = 0; i < numtris; ++i, ++mv) {
+ vert_weights[i] = vertex_weight_cb(dm, mv, (unsigned int)i, userdata);
+ }
+ }
+ }
+
+ float *tri_weights = MEM_mallocN(sizeof(float) * (size_t)numweights, "mesh sample triangle weights");
+ /* accumulate weights */
+ float totarea = 0.0;
+ float totweight = 0.0f;
+ {
+ const MLoopTri *mt = dm->getLoopTriArray(dm);
+ for (int i = 0; i < numtris; ++i, ++mt) {
+ tri_weights[i] = totweight;
+
+ float triarea;
+ float triweight = triangle_weight(dm, mt, vert_weights, &triarea);
+ totarea += triarea;
+ totweight += triweight;
+ }
+ }
+
+ if (vert_weights) {
+ MEM_freeN(vert_weights);
+ }
+
+ /* normalize */
+ if (totweight > 0.0f) {
+ float norm = 1.0f / totweight;
+ const MLoopTri *mt = dm->getLoopTriArray(dm);
+ for (int i = 0; i < numtris; ++i, ++mt) {
+ tri_weights[i] *= norm;
+ }
+ }
+ else {
+ /* invalid weights, remove to avoid invalid binary search */
+ MEM_freeN(tri_weights);
+ tri_weights = NULL;
+ }
+
+ if (r_area) {
+ *r_area = totarea;
+ }
+ return tri_weights;
+}
+
+MeshSampleGenerator *BKE_mesh_sample_gen_surface_random_ex(DerivedMesh *dm, unsigned int seed, float *tri_weights)
{
MSurfaceSampleGenerator_Random *gen;
@@ -492,48 +555,21 @@ MeshSampleGenerator *BKE_mesh_sample_gen_surface_random_ex(DerivedMesh *dm, unsi
gen->dm = dm;
gen->seed = seed;
- if (use_facearea) {
- int numtris = dm->getNumLoopTri(dm);
- int numweights = numtris;
- const MLoopTri *mtris = dm->getLoopTriArray(dm);
- const MLoopTri *mt;
- int i;
- float totweight;
-
- gen->tri_weights = MEM_mallocN(sizeof(float) * (size_t)numweights, "mesh sample triangle weights");
-
- /* accumulate weights */
- totweight = 0.0f;
- for (i = 0, mt = mtris; i < numtris; ++i, ++mt) {
- float weight = triangle_weight(dm, mt, vertex_weight_cb, userdata);
- gen->tri_weights[i] = totweight;
- totweight += weight;
- }
-
- /* normalize */
- if (totweight > 0.0f) {
- float norm = 1.0f / totweight;
- for (i = 0, mt = mtris; i < numtris; ++i, ++mt) {
- gen->tri_weights[i] *= norm;
- }
- }
- else {
- /* invalid weights, remove to avoid invalid binary search */
- MEM_freeN(gen->tri_weights);
- gen->tri_weights = NULL;
- }
+ if (tri_weights) {
+ gen->tri_weights = tri_weights;
#ifdef USE_DEBUG_COUNT
- gen->debug_count = MEM_callocN(sizeof(int) * (size_t)numweights, "surface sample debug counts");
+ gen->debug_count = MEM_callocN(sizeof(int) * (size_t)dm->getNumLoopTri(dm), "surface sample debug counts");
#endif
}
return &gen->base;
}
-MeshSampleGenerator *BKE_mesh_sample_gen_surface_random(DerivedMesh *dm, unsigned int seed)
+MeshSampleGenerator *BKE_mesh_sample_gen_surface_random(DerivedMesh *dm, unsigned int seed, MeshSampleVertexWeightFp vertex_weight_cb, void *userdata)
{
- return BKE_mesh_sample_gen_surface_random_ex(dm, seed, NULL, NULL, true);
+ float *tri_weights = BKE_mesh_sample_calc_triangle_weights(dm, vertex_weight_cb, userdata, NULL);
+ return BKE_mesh_sample_gen_surface_random_ex(dm, seed, tri_weights);
}
/* ------------------------------------------------------------------------- */
@@ -637,6 +673,306 @@ MeshSampleGenerator *BKE_mesh_sample_gen_surface_raycast(
/* ------------------------------------------------------------------------- */
+#define MAX_CIRCLE_PACKING 0.906899682
+#define SQRT_3 1.732050808
+
+typedef struct IndexedMeshSample {
+ unsigned int orig_verts[3];
+ float orig_weights[3];
+ float co[3];
+ unsigned int cell_index;
+} IndexedMeshSample;
+
+typedef struct MSurfaceSampleGenerator_PoissonDisk {
+ MeshSampleGenerator base;
+
+ IndexedMeshSample *uniform_samples;
+ int num_uniform_samples;
+
+ float mindist_squared;
+ /* Size of grid cells is mindist/sqrt(3),
+ * so that each cell contains at most one valid sample.
+ */
+ float cellsize;
+ /* Transform mesh space to grid space */
+ float grid_scale;
+ /* offset and size of the grid */
+ int grid_offset[3];
+ int grid_size[3];
+
+ struct GHash *cell_table;
+} MSurfaceSampleGenerator_PoissonDisk;
+
+typedef struct MSurfaceSampleGenerator_PoissonDisk_ThreadContext {
+ unsigned int trial;
+ GHashIterator iter;
+} MSurfaceSampleGenerator_PoissonDisk_ThreadContext;
+
+static void generator_poissondisk_free(MSurfaceSampleGenerator_PoissonDisk *gen)
+{
+ if (gen->cell_table) {
+ BLI_ghash_free(gen->cell_table, NULL, MEM_freeN);
+ }
+
+ if (gen->uniform_samples) {
+ MEM_freeN(gen->uniform_samples);
+ }
+
+ MEM_freeN(gen);
+}
+
+static void* generator_poissondisk_thread_context_create(const MSurfaceSampleGenerator_PoissonDisk *gen, int UNUSED(start))
+{
+ MSurfaceSampleGenerator_PoissonDisk_ThreadContext *ctx = MEM_mallocN(sizeof(*ctx), "thread context");
+ ctx->trial = 0;
+ BLI_ghashIterator_init(&ctx->iter, ge
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list