[Bf-blender-cvs] [caded470a6d] strand_editmode: Fix neighbor conflict checks for Poisson disk distribution.
Lukas Tönne
noreply at git.blender.org
Sat Aug 26 16:34:01 CEST 2017
Commit: caded470a6d0a9e002451ef1050032c4b882379d
Author: Lukas Tönne
Date: Sat Aug 26 15:32:09 2017 +0100
Branches: strand_editmode
https://developer.blender.org/rBcaded470a6d0a9e002451ef1050032c4b882379d
Fix neighbor conflict checks for Poisson disk distribution.
The cell size is chosen as r/sqrt(3) (i.e. max. 1 sample per cell),
which means that the influence of each cell extends beyond the 1st
neighbor. a 5x5x5 box (except the center and corners) needs to be
examined to find collisions.
===================================================================
M source/blender/blenkernel/intern/mesh_sample.c
===================================================================
diff --git a/source/blender/blenkernel/intern/mesh_sample.c b/source/blender/blenkernel/intern/mesh_sample.c
index b946911abe2..e364c205830 100644
--- a/source/blender/blenkernel/intern/mesh_sample.c
+++ b/source/blender/blenkernel/intern/mesh_sample.c
@@ -795,6 +795,49 @@ 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]);
+ mul_v3_fl(loc, gen->cellsize);
+}
+
+BLI_INLINE void poissondisk_grid_from_loc(const MSurfaceSampleGenerator_PoissonDisk *gen, int grid[3], const float loc[3])
+{
+ float gridco[3];
+ mul_v3_v3fl(gridco, loc, gen->grid_scale);
+ grid[0] = (int)floorf(gridco[0]) - gen->grid_offset[0];
+ grid[1] = (int)floorf(gridco[1]) - gen->grid_offset[1];
+ 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);
@@ -816,13 +859,7 @@ 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);
- float gridco[3];
- mul_v3_v3fl(gridco, isample->co, gen->grid_scale);
- int c[3];
- c[0] = (int)floorf(gridco[0]) - gen->grid_offset[0];
- c[1] = (int)floorf(gridco[1]) - gen->grid_offset[1];
- c[2] = (int)floorf(gridco[2]) - gen->grid_offset[2];
- isample->cell_index = (unsigned int)(c[0] + (c[1] + c[2] * gen->grid_size[1]) * gen->grid_size[0]);
+ isample->cell_index = poissondisk_index_from_loc(gen, isample->co);
}
static int cmp_indexed_mesh_sample(const void *a, const void *b)
@@ -867,13 +904,13 @@ static void generator_poissondisk_bind(MSurfaceSampleGenerator_PoissonDisk *gen)
dm->getMinMax(dm, min, max);
mul_v3_fl(min, gen->grid_scale);
mul_v3_fl(max, gen->grid_scale);
- /* grid size gets an empty 1 cell margin to simplify neighbor lookups */
- gen->grid_offset[0] = (int)floorf(min[0]) - 1;
- gen->grid_offset[1] = (int)floorf(min[1]) - 1;
- gen->grid_offset[2] = (int)floorf(min[2]) - 1;
- gen->grid_size[0] = (int)floorf(max[0]) - gen->grid_offset[0] + 2;
- gen->grid_size[1] = (int)floorf(max[1]) - gen->grid_offset[1] + 2;
- gen->grid_size[2] = (int)floorf(max[2]) - gen->grid_offset[2] + 2;
+ /* grid size gets an empty 2 cell margin to simplify neighbor lookups */
+ gen->grid_offset[0] = (int)floorf(min[0]) - 2;
+ gen->grid_offset[1] = (int)floorf(min[1]) - 2;
+ gen->grid_offset[2] = (int)floorf(min[2]) - 2;
+ gen->grid_size[0] = (int)floorf(max[0]) - gen->grid_offset[0] + 4;
+ gen->grid_size[1] = (int)floorf(max[1]) - gen->grid_offset[1] + 4;
+ gen->grid_size[2] = (int)floorf(max[2]) - gen->grid_offset[2] + 4;
}
// Generate initial uniform random point set
@@ -954,6 +991,45 @@ 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,
+ };
+ const int num_neighbors = ARRAY_SIZE(neighbors);
+
bool found_sample = false;
for (; ctx->trial < max_trials; ++ctx->trial) {
while (!BLI_ghashIterator_done(&ctx->iter)) {
@@ -977,28 +1053,15 @@ static bool generator_poissondisk_make_sample(const MSurfaceSampleGenerator_Pois
else {
/* Check the sample candidate */
unsigned int idx = cell->cell_index;
- unsigned int sx = 1;
- unsigned int sy = sx * (unsigned int)gen->grid_size[0];
- unsigned int sz = sy * (unsigned int)gen->grid_size[1];
- unsigned int neighbors[] = {
- idx - sx - sy - sz, idx - sy - sz, idx + sx - sy - sz,
- idx - sx - sz, idx - sz, idx + sx - sz,
- idx - sx + sy - sz, idx + sy - sz, idx + sx + sy - sz,
- idx - sx - sy , idx - sy , idx + sx - sy ,
- idx - sx , idx + sx ,
- idx - sx + sy , idx + sy , idx + sx + sy ,
- idx - sx - sy + sz, idx - sy + sz, idx + sx - sy + sz,
- idx - sx + sz, idx + sz, idx + sx + sz,
- idx - sx + sy + sz, idx + sy + sz, idx + sx + sy + sz,
- };
- int num_neighbors = ARRAY_SIZE(neighbors);
bool conflict = false;
for (int i = 0; i < num_neighbors; ++i) {
- const MeshSampleCell *ncell = BLI_ghash_lookup(gen->cell_table, &neighbors[i]);
+ unsigned int nidx = (unsigned int)((int)idx + neighbors[i]);
+ const MeshSampleCell *ncell = BLI_ghash_lookup(gen->cell_table, &nidx);
if (ncell) {
if (ncell->sample != SAMPLE_INDEX_INVALID) {
const IndexedMeshSample *nsample = &gen->uniform_samples[ncell->sample];
+ BLI_assert(nsample->cell_index == ncell->cell_index);
if (len_squared_v3v3(isample->co, nsample->co) < gen->mindist_squared) {
conflict = true;
break;
More information about the Bf-blender-cvs
mailing list