From e3f14564a42db8489950de2ea0081c99076a957c Mon Sep 17 00:00:00 2001 From: Jacques Lucke Date: Tue, 12 Jan 2021 20:11:00 +0100 Subject: initial new implementation --- .../geometry/nodes/node_geo_point_distribute.cc | 125 ++++++++++++++++++++- 1 file changed, 123 insertions(+), 2 deletions(-) diff --git a/source/blender/nodes/geometry/nodes/node_geo_point_distribute.cc b/source/blender/nodes/geometry/nodes/node_geo_point_distribute.cc index 76f1bf30c85..c86664c4025 100644 --- a/source/blender/nodes/geometry/nodes/node_geo_point_distribute.cc +++ b/source/blender/nodes/geometry/nodes/node_geo_point_distribute.cc @@ -16,9 +16,11 @@ #include "BLI_float3.hh" #include "BLI_hash.h" +#include "BLI_kdtree.h" #include "BLI_math_vector.h" #include "BLI_rand.hh" #include "BLI_span.hh" +#include "BLI_timeit.hh" #include "DNA_mesh_types.h" #include "DNA_meshdata_types.h" @@ -122,6 +124,124 @@ static Vector random_scatter_points_from_mesh(const Mesh *mesh, return points; } +BLI_NOINLINE static void initial_uniform_distribution(const Mesh *mesh, + const float density, + const int seed, + Vector &r_positions, + Vector &r_normals, + Vector &r_ids) +{ + /* This only updates a cache and can be considered to be logically const. */ + const MLoopTri *looptris = BKE_mesh_runtime_looptri_ensure(const_cast(mesh)); + const int looptris_len = BKE_mesh_runtime_looptri_len(mesh); + + for (const int looptri_index : IndexRange(looptris_len)) { + const MLoopTri &looptri = looptris[looptri_index]; + const int v0_index = mesh->mloop[looptri.tri[0]].v; + const int v1_index = mesh->mloop[looptri.tri[1]].v; + const int v2_index = mesh->mloop[looptri.tri[2]].v; + const float3 v0_pos = mesh->mvert[v0_index].co; + const float3 v1_pos = mesh->mvert[v1_index].co; + const float3 v2_pos = mesh->mvert[v2_index].co; + const float area = area_tri_v3(v0_pos, v1_pos, v2_pos); + const int looptri_seed = BLI_hash_int(looptri_index + seed); + RandomNumberGenerator looptri_rng(looptri_seed); + + const float points_amount_fl = area * density; + const float add_point_probability = fractf(points_amount_fl); + const bool add_point = add_point_probability > looptri_rng.get_float(); + const int point_amount = (int)points_amount_fl + (int)add_point; + + for (int i = 0; i < point_amount; i++) { + const float3 bary_coords = looptri_rng.get_barycentric_coordinates(); + float3 point_pos; + interp_v3_v3v3v3(point_pos, v0_pos, v1_pos, v2_pos, bary_coords); + r_positions.append(point_pos); + + /* Build a hash stable even when the mesh is deformed. */ + r_ids.append(((int)(bary_coords.hash()) + looptri_index)); + + float3 tri_normal; + normal_tri_v3(tri_normal, v0_pos, v1_pos, v2_pos); + r_normals.append(tri_normal); + } + } +} + +BLI_NOINLINE static KDTree_3d *build_kdtree(Span positions) +{ + KDTree_3d *kdtree = BLI_kdtree_3d_new(positions.size()); + for (const int i : positions.index_range()) { + BLI_kdtree_3d_insert(kdtree, i, positions[i]); + } + BLI_kdtree_3d_balance(kdtree); + return kdtree; +} + +BLI_NOINLINE static void create_elimination_mask_for_close_points( + Span positions, const float minimum_distance, MutableSpan r_elimination_mask) +{ + KDTree_3d *kdtree = build_kdtree(positions); + + for (const int i : positions.index_range()) { + if (r_elimination_mask[i]) { + continue; + } + + struct CallbackData { + int index; + MutableSpan elimination_mask; + } callback_data = {i, r_elimination_mask}; + + BLI_kdtree_3d_range_search_cb( + kdtree, + positions[i], + minimum_distance, + [](void *user_data, int index, const float *UNUSED(co), float UNUSED(dist_sq)) { + CallbackData &callback_data = *static_cast(user_data); + if (index != callback_data.index) { + callback_data.elimination_mask[index] = true; + } + return true; + }, + &callback_data); + } + BLI_kdtree_3d_free(kdtree); +} + +BLI_NOINLINE static void eliminate_points_based_on_mask(Span elimination_mask, + Vector &positions, + Vector &normals, + Vector &ids) +{ + for (int i = positions.size() - 1; i >= 0; i--) { + if (elimination_mask[i]) { + positions.remove_and_reorder(i); + normals.remove_and_reorder(i); + ids.remove_and_reorder(i); + } + } +} + +static Vector stable_random_scatter_with_minimum_distance( + const Mesh *mesh, + const float max_density, + const float minimum_distance, + const FloatReadAttribute &density_factors, + Vector &r_normals, + Vector &r_ids, + const int seed) +{ + SCOPED_TIMER(__func__); + + Vector positions; + initial_uniform_distribution(mesh, max_density, seed, positions, r_normals, r_ids); + Array elimination_mask(positions.size(), false); + create_elimination_mask_for_close_points(positions, minimum_distance, elimination_mask); + eliminate_points_based_on_mask(elimination_mask, positions, r_normals, r_ids); + return positions; +} + static void geo_node_point_distribute_exec(GeoNodeExecParams params) { GeometrySet geometry_set = params.extract_input("Geometry"); @@ -164,8 +284,9 @@ static void geo_node_point_distribute_exec(GeoNodeExecParams params) mesh_in, density, density_factors, normals, stable_ids, seed); break; case GEO_NODE_POINT_DISTRIBUTE_POISSON: - const float min_dist = params.extract_input("Distance Min"); - UNUSED_VARS(min_dist); + const float minimum_distance = params.extract_input("Distance Min"); + points = stable_random_scatter_with_minimum_distance( + mesh_in, density, minimum_distance, density_factors, normals, stable_ids, seed); break; } -- cgit v1.2.3