[Bf-blender-cvs] [cf3fce96b13] hair_guides: Fix for overflow of cell_index in the Poisson disk sample generator.
Lukas Tönne
noreply at git.blender.org
Mon Nov 20 21:05:40 CET 2017
Commit: cf3fce96b130112007a4a66ef83cc3f5bb700827
Author: Lukas Tönne
Date: Mon Nov 20 20:02:58 2017 +0000
Branches: hair_guides
https://developer.blender.org/rBcf3fce96b130112007a4a66ef83cc3f5bb700827
Fix for overflow of cell_index in the Poisson disk sample generator.
Using a single uint as combined cell index only leaves ~10 bits per
coordinate axis, which quickly leads to overflow for higher densities.
Now use 3 ints so that the sampling grid can have sufficiently small
cells.
===================================================================
M source/blender/blenkernel/intern/hair.c
M source/blender/blenkernel/intern/mesh_sample.c
===================================================================
diff --git a/source/blender/blenkernel/intern/hair.c b/source/blender/blenkernel/intern/hair.c
index cbb8c2d2711..e5f9f72748c 100644
--- a/source/blender/blenkernel/intern/hair.c
+++ b/source/blender/blenkernel/intern/hair.c
@@ -203,7 +203,7 @@ void BKE_hair_generate_follicles(
BKE_mesh_sample_generator_bind(gen, scalp);
- static const bool use_threads = true;
+ static const bool use_threads = false;
pattern->num_follicles = BKE_mesh_sample_generate_batch_ex(
gen,
&pattern->follicles->mesh_sample,
diff --git a/source/blender/blenkernel/intern/mesh_sample.c b/source/blender/blenkernel/intern/mesh_sample.c
index cc673f62774..253ec4367ec 100644
--- a/source/blender/blenkernel/intern/mesh_sample.c
+++ b/source/blender/blenkernel/intern/mesh_sample.c
@@ -754,7 +754,7 @@ typedef struct IndexedMeshSample {
unsigned int orig_verts[3];
float orig_weights[3];
float co[3];
- unsigned int cell_index;
+ int cell_index[3];
} IndexedMeshSample;
typedef struct MSurfaceSampleGenerator_PoissonDisk {
@@ -783,7 +783,7 @@ typedef struct MSurfaceSampleGenerator_PoissonDisk {
} MSurfaceSampleGenerator_PoissonDisk;
typedef struct MeshSampleCell {
- unsigned int cell_index;
+ int cell_index[3];
unsigned int sample_start;
unsigned int sample;
} MeshSampleCell;
@@ -795,20 +795,6 @@ typedef struct MSurfaceSampleGenerator_PoissonDisk_ThreadContext {
GHashIterator iter;
} MSurfaceSampleGenerator_PoissonDisk_ThreadContext;
-BLI_INLINE unsigned int poissondisk_index_from_grid(const MSurfaceSampleGenerator_PoissonDisk *gen, const int grid[3])
-{
- return (unsigned int)(grid[0] + (grid[1] + grid[2] * gen->grid_size[1]) * gen->grid_size[0]);
-}
-
-BLI_INLINE void poissondisk_grid_from_index(const MSurfaceSampleGenerator_PoissonDisk *gen, int grid[3], unsigned int idx)
-{
- div_t result = div((int)idx, gen->grid_size[0]);
- grid[0] = result.rem;
- result = div(result.quot, gen->grid_size[1]);
- grid[1] = result.rem;
- grid[2] = result.quot;
-}
-
BLI_INLINE void poissondisk_loc_from_grid(const MSurfaceSampleGenerator_PoissonDisk *gen, float loc[3], const int grid[3])
{
copy_v3_fl3(loc, grid[0] + gen->grid_offset[0], grid[1] + gen->grid_offset[1], grid[2] + gen->grid_offset[2]);
@@ -824,20 +810,6 @@ BLI_INLINE void poissondisk_grid_from_loc(const MSurfaceSampleGenerator_PoissonD
grid[2] = (int)floorf(gridco[2]) - gen->grid_offset[2];
}
-BLI_INLINE unsigned int poissondisk_index_from_loc(const MSurfaceSampleGenerator_PoissonDisk *gen, const float loc[3])
-{
- int grid[3];
- poissondisk_grid_from_loc(gen, grid, loc);
- return poissondisk_index_from_grid(gen, grid);
-}
-
-BLI_INLINE void poissondisk_loc_from_index(const MSurfaceSampleGenerator_PoissonDisk *gen, float loc[3], unsigned int index)
-{
- int grid[3];
- poissondisk_grid_from_index(gen, grid, index);
- poissondisk_loc_from_grid(gen, loc, grid);
-}
-
static void generator_poissondisk_free(MSurfaceSampleGenerator_PoissonDisk *gen)
{
BKE_mesh_sample_free_generator(gen->uniform_gen);
@@ -859,24 +831,69 @@ static void generator_poissondisk_uniform_sample_eval(void *userdata, const int
float nor[3], tang[3];
BKE_mesh_sample_eval(dm, sample, isample->co, nor, tang);
- isample->cell_index = poissondisk_index_from_loc(gen, isample->co);
+ poissondisk_grid_from_loc(gen, isample->cell_index, isample->co);
+}
+
+BLI_INLINE void copy_cell_index(int r[3], const int a[3])
+{
+ r[0] = a[0];
+ r[1] = a[1];
+ r[2] = a[2];
+}
+
+BLI_INLINE int cmp_cell_index(const int a[3], const int b[3])
+{
+ int d0 = a[0] - b[0];
+ int d1 = a[1] - b[1];
+ int d2 = a[2] - b[2];
+ if (d0 == 0)
+ {
+ if (d1 == 0)
+ {
+ if (d2 == 0)
+ {
+ return 0;
+ }
+ else
+ {
+ return d2 > 0 ? 1 : -1;
+ }
+ }
+ else
+ {
+ return d1 > 0 ? 1 : -1;
+ }
+ }
+ else
+ {
+ return d0 > 0 ? 1 : -1;
+ }
}
static int cmp_indexed_mesh_sample(const void *a, const void *b)
{
- return (int)((const IndexedMeshSample *)a)->cell_index - (int)((const IndexedMeshSample *)b)->cell_index;
+ return cmp_cell_index(((const IndexedMeshSample *)a)->cell_index, ((const IndexedMeshSample *)b)->cell_index);
+}
+
+BLI_INLINE bool cell_index_eq(const int *a, const int *b)
+{
+ return a[0] == b[0] && a[1] == b[1] && a[2] == b[2];
}
-static unsigned int mesh_sample_cell_hash(const void *key)
+/* hash key function */
+static unsigned int cell_hash_key(const void *key)
{
- return *(const unsigned int *)key;
- //return ((const MeshSampleCell *)key)->cell_index;
+ const int *cell_index = (const int *)key;
+ unsigned int hash0 = BLI_ghashutil_inthash(cell_index[0]);
+ unsigned int hash1 = BLI_ghashutil_inthash(cell_index[1]);
+ unsigned int hash2 = BLI_ghashutil_inthash(cell_index[2]);
+ return BLI_ghashutil_combine_hash(hash0, BLI_ghashutil_combine_hash(hash1, hash2));
}
-static bool mesh_sample_cell_cmp(const void *a, const void *b)
+/* hash function: return false when equal */
+static bool cell_hash_neq(const void *a, const void *b)
{
- return *(const unsigned int *)a != *(const unsigned int *)b;
- //return ((const MeshSampleCell *)a)->cell_index != ((const MeshSampleCell *)b)->cell_index;
+ return !cell_index_eq((const int *)a, (const int *)b);
}
static unsigned int generator_poissondisk_get_max_samples(const MSurfaceSampleGenerator_PoissonDisk *gen)
@@ -937,18 +954,19 @@ static void generator_poissondisk_bind(MSurfaceSampleGenerator_PoissonDisk *gen)
// Build a hash table for indexing cells
{
- gen->cell_table = BLI_ghash_new(mesh_sample_cell_hash, mesh_sample_cell_cmp, "MeshSampleCell hash table");
- unsigned int cur_cell_index = 0xFFFFFFFF;
+ gen->cell_table = BLI_ghash_new(cell_hash_key, cell_hash_neq, "MeshSampleCell hash table");
+ int cur_cell_index[3] = {-1, -1, -1};
const IndexedMeshSample *sample = gen->uniform_samples;
for (unsigned int i = 0; i < gen->num_uniform_samples; ++i, ++sample) {
- if (sample->cell_index != cur_cell_index) {
- cur_cell_index = sample->cell_index;
+ BLI_assert(cmp_cell_index(cur_cell_index, sample->cell_index) <= 0);
+ if (cmp_cell_index(cur_cell_index, sample->cell_index) < 0) {
+ copy_cell_index(cur_cell_index, sample->cell_index);
MeshSampleCell *cell = MEM_mallocN(sizeof(*cell), "MeshSampleCell");
- cell->cell_index = cur_cell_index;
+ copy_cell_index(cell->cell_index, cur_cell_index);
cell->sample_start = (unsigned int)i;
cell->sample = SAMPLE_INDEX_INVALID;
- BLI_ghash_insert(gen->cell_table, &cell->cell_index, cell);
+ BLI_ghash_insert(gen->cell_table, cell->cell_index, cell);
}
}
}
@@ -991,42 +1009,38 @@ static bool generator_poissondisk_make_sample(const MSurfaceSampleGenerator_Pois
MSurfaceSampleGenerator_PoissonDisk_ThreadContext *ctx = thread_ctx;
- const int sx = 1;
- const int sxx = sx << 1;
- const int sy = sx * gen->grid_size[0];
- const int syy = sy << 1;
- const int sz = sy * gen->grid_size[1];
- const int szz = sz << 1;
- const int neighbors[] = {
- -sxx -sy -szz, -sxx -szz, -sxx +sy -szz,
- -sx -syy -szz, -sx -sy -szz, -sx -szz, -sx +sy -szz, -sx +syy -szz,
- -syy -szz, -sy -szz, -szz, +sy -szz, +syy -szz,
- +sx -syy -szz, +sx -sy -szz, +sx -szz, +sx +sy -szz, +sx +syy -szz,
- +sxx -syy -szz, +sxx -sy -szz, +sxx -szz, +sxx +sy -szz, +sxx +syy -szz,
-
- -sxx -syy -sz, -sxx -sy -sz, -sxx -sz, -sxx +sy -sz, -sxx +syy -sz,
- -sx -syy -sz, -sx -sy -sz, -sx -sz, -sx +sy -sz, -sx +syy -sz,
- -syy -sz, -sy -sz, -sz, +sy -sz, +syy -sz,
- +sx -syy -sz, +sx -sy -sz, +sx -sz, +sx +sy -sz, +sx +syy -sz,
- +sxx -syy -sz, +sxx -sy -sz, +sxx -sz, +sxx +sy -sz, +sxx +syy -sz,
-
- -sxx -syy , -sxx -sy , -sxx , -sxx +sy , -sxx +syy ,
- -sx -syy , -sx -sy , -sx , -sx +sy , -sx +syy ,
- -syy , -sy , +sy , +syy ,
- +sx -syy , +sx -sy , +sx , +sx +sy , +sx +syy ,
- +sxx -syy , +sxx -sy , +sxx , +sxx +sy , +sxx +syy ,
-
- -sxx -syy +sz, -sxx -sy +sz, -sxx +sz, -sxx +sy +sz, -sxx +syy +sz,
- -sx -syy +sz, -sx -sy +sz, -sx +sz, -sx +sy +sz, -sx +syy +sz,
- -syy +sz, -sy +sz, +sz, +sy +sz, +syy +sz,
- +sx -syy +sz, +sx -sy +sz, +sx +sz, +sx +sy +sz, +sx +syy +sz,
- +sxx -syy +sz, +sxx -sy +sz, +sxx +sz, +sxx +sy +sz, +sxx +syy +sz,
-
- -sxx -syy +szz, -sxx -sy +szz, -sxx +szz, -sxx +sy +szz, -sxx +syy +szz,
- -sx -syy +szz, -sx -sy +szz, -sx +szz, -sx +sy +szz, -sx +syy +szz,
- -syy +szz, -sy +szz, +szz, +sy +szz, +syy +szz,
- +sx -syy +szz, +sx -sy +szz, +sx +szz, +sx +sy +szz, +sx +syy +szz,
- +sxx -sy +szz, +sxx +szz, +sxx +sy +szz,
+ // Offset of cells whose samples can potentially overlap a given cell
+ // Four corners are excluded because their samples can never overlap
+ const int neighbors[][3] = {
+ {-1, -2, -2}, { 0, -2, -2}, { 1, -2, -2},
+ {-2, -1, -2}, {-1, -1, -2}, { 0, -1, -2}, { 1, -1, -2}, { 2, -1, -2},
+ {-2, 0, -2}, {-1, 0, -2}, { 0, 0, -2}, { 1, 0, -2}, { 2, 0, -2},
+ {-2, 1, -2}, {-1, 1, -2}, { 0, 1, -2}, { 1, -2, -2}, { 2, 1, -2},
+ {-2, 2, -2}, {-1, 2, -2}, { 0, 2, -2}, { 1, -2, -2}, { 2, 2, -2},
+
+ {-2, -2, -1}, {-1, -2, -1}, { 0, -2, -1}, { 1, -2, -1}, { 2, -2, -1},
+ {-2, -1, -1}, {-1, -1, -1}, { 0, -1, -1}, { 1, -1, -1}, { 2, -1, -1},
+ {-2, 0, -1}, {-1, 0, -1}, { 0, 0, -1}, { 1, 0, -1}, { 2, 0, -1},
+ {-2, 1, -1}, {-1, 1, -1}, { 0, 1, -1}, { 1, -2, -1}, { 2, 1, -1},
+ {-2, 2, -1}, {-1, 2, -1}, { 0, 2, -1}, { 1, -2, -1}, { 2, 2, -1},
+
+ {-2, -2, 0}, {-1, -2, 0}, { 0, -2, 0}, { 1, -2, 0}, { 2, -2, 0},
+ {-2, -1, 0}, {-1, -1, 0}, { 0, -1, 0}, { 1, -1, 0}, { 2, -1, 0},
+ {-2, 0, 0}, {-1, 0, 0}, { 1, 0,
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list