[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