Page MenuHome
Differential D16893 Diff 59975 source/blender/blenkernel/intern/bvhutils.cc

Changeset View

Standalone View

View Options

source/blender/blenkernel/intern/bvhutils.cc

Show First 20 Lines • Show All 92 Lines • ▼ Show 20 Lines
int index, int index,
const float co[3], const float co[3],
BVHTreeNearest *nearest) BVHTreeNearest *nearest)
{ {
const BVHTreeFromMesh *data = (BVHTreeFromMesh *)userdata; const BVHTreeFromMesh *data = (BVHTreeFromMesh *)userdata;
const float(*positions)[3] = data->vert_positions; const float(*positions)[3] = data->vert_positions;
const MLoopTri *lt = &data->looptri[index]; const MLoopTri *lt = &data->looptri[index];
const float *vtri_co[3] = { const float *vtri_co[3] = {
positions[data->loop[lt->tri[0]].v], positions[data->corner_verts[lt->tri[0]]],
positions[data->loop[lt->tri[1]].v], positions[data->corner_verts[lt->tri[1]]],
positions[data->loop[lt->tri[2]].v], positions[data->corner_verts[lt->tri[2]]],
}; };
float nearest_tmp[3], dist_sq; float nearest_tmp[3], dist_sq;
closest_on_tri_to_point_v3(nearest_tmp, co, UNPACK3(vtri_co)); closest_on_tri_to_point_v3(nearest_tmp, co, UNPACK3(vtri_co));
dist_sq = len_squared_v3v3(co, nearest_tmp); dist_sq = len_squared_v3v3(co, nearest_tmp);
if (dist_sq < nearest->dist_sq) { if (dist_sq < nearest->dist_sq) {
nearest->index = index; nearest->index = index;
▲ Show 20 Lines • Show All 81 Lines • ▼ Show 20 Lines
int index, int index,
const BVHTreeRay *ray, const BVHTreeRay *ray,
BVHTreeRayHit *hit) BVHTreeRayHit *hit)
{ {
const BVHTreeFromMesh *data = (BVHTreeFromMesh *)userdata; const BVHTreeFromMesh *data = (BVHTreeFromMesh *)userdata;
const float(*positions)[3] = data->vert_positions; const float(*positions)[3] = data->vert_positions;
const MLoopTri *lt = &data->looptri[index]; const MLoopTri *lt = &data->looptri[index];
const float *vtri_co[3] = { const float *vtri_co[3] = {
positions[data->loop[lt->tri[0]].v], positions[data->corner_verts[lt->tri[0]]],
positions[data->loop[lt->tri[1]].v], positions[data->corner_verts[lt->tri[1]]],
positions[data->loop[lt->tri[2]].v], positions[data->corner_verts[lt->tri[2]]],
}; };
float dist; float dist;
if (ray->radius == 0.0f) { if (ray->radius == 0.0f) {
dist = bvhtree_ray_tri_intersection(ray, hit->dist, UNPACK3(vtri_co)); dist = bvhtree_ray_tri_intersection(ray, hit->dist, UNPACK3(vtri_co));
} }
else { else {
dist = bvhtree_sphereray_tri_intersection(ray, ray->radius, hit->dist, UNPACK3(vtri_co)); dist = bvhtree_sphereray_tri_intersection(ray, ray->radius, hit->dist, UNPACK3(vtri_co));
▲ Show 20 Lines • Show All 184 Lines • ▼ Show 20 Lines
/** \name Common Utils /** \name Common Utils
* \{ */ * \{ */
static void bvhtree_from_mesh_setup_data(BVHTree *tree, static void bvhtree_from_mesh_setup_data(BVHTree *tree,
const BVHCacheType bvh_cache_type, const BVHCacheType bvh_cache_type,
const float (*positions)[3], const float (*positions)[3],
const MEdge *edge, const MEdge *edge,
const MFace *face, const MFace *face,
const MLoop *loop, const int *corner_verts,
const MLoopTri *looptri, const MLoopTri *looptri,
BVHTreeFromMesh *r_data) BVHTreeFromMesh *r_data)
{ {
memset(r_data, 0, sizeof(*r_data)); memset(r_data, 0, sizeof(*r_data));
r_data->tree = tree; r_data->tree = tree;
r_data->vert_positions = positions; r_data->vert_positions = positions;
r_data->edge = edge; r_data->edge = edge;
r_data->face = face; r_data->face = face;
r_data->loop = loop; r_data->corner_verts = corner_verts;
r_data->looptri = looptri; r_data->looptri = looptri;
switch (bvh_cache_type) { switch (bvh_cache_type) {
case BVHTREE_FROM_VERTS: case BVHTREE_FROM_VERTS:
case BVHTREE_FROM_LOOSEVERTS: case BVHTREE_FROM_LOOSEVERTS:
/* a nullptr nearest callback works fine /* a nullptr nearest callback works fine
* remember the min distance to point is the same as the min distance to BV of point */ * remember the min distance to point is the same as the min distance to BV of point */
r_data->nearest_callback = nullptr; r_data->nearest_callback = nullptr;
▲ Show 20 Lines • Show All 184 Lines • ▼ Show 20 Lines
return tree; return tree;
} }
static BVHTree *bvhtree_from_mesh_looptri_create_tree(float epsilon, static BVHTree *bvhtree_from_mesh_looptri_create_tree(float epsilon,
int tree_type, int tree_type,
int axis, int axis,
const float (*positions)[3], const float (*positions)[3],
const MLoop *mloop, const int *corner_verts,
const MLoopTri *looptri, const MLoopTri *looptri,
const int looptri_num, const int looptri_num,
const BitVector<> &looptri_mask, const BitVector<> &looptri_mask,
int looptri_num_active) int looptri_num_active)
{ {
if (!looptri_mask.is_empty()) { if (!looptri_mask.is_empty()) {
BLI_assert(IN_RANGE_INCL(looptri_num_active, 0, looptri_num)); BLI_assert(IN_RANGE_INCL(looptri_num_active, 0, looptri_num));
} }
Show All 13 Lines
if (positions && looptri) { if (positions && looptri) {
for (int i = 0; i < looptri_num; i++) { for (int i = 0; i < looptri_num; i++) {
float co[3][3]; float co[3][3];
if (!looptri_mask.is_empty() && !looptri_mask[i]) { if (!looptri_mask.is_empty() && !looptri_mask[i]) {
continue; continue;
} }
copy_v3_v3(co[0], positions[mloop[looptri[i].tri[0]].v]); copy_v3_v3(co[0], positions[corner_verts[looptri[i].tri[0]]]);
copy_v3_v3(co[1], positions[mloop[looptri[i].tri[1]].v]); copy_v3_v3(co[1], positions[corner_verts[looptri[i].tri[1]]]);
copy_v3_v3(co[2], positions[mloop[looptri[i].tri[2]].v]); copy_v3_v3(co[2], positions[corner_verts[looptri[i].tri[2]]]);
BLI_bvhtree_insert(tree, i, co[0], 3); BLI_bvhtree_insert(tree, i, co[0], 3);
} }
} }
BLI_assert(BLI_bvhtree_get_len(tree) == looptri_num_active); BLI_assert(BLI_bvhtree_get_len(tree) == looptri_num_active);
return tree; return tree;
} }
Show All 22 Lines
BVHTree *bvhtree_from_editmesh_looptri( BVHTree *bvhtree_from_editmesh_looptri(
BVHTreeFromEditMesh *data, BMEditMesh *em, float epsilon, int tree_type, int axis) BVHTreeFromEditMesh *data, BMEditMesh *em, float epsilon, int tree_type, int axis)
{ {
return bvhtree_from_editmesh_looptri_ex(data, em, {}, -1, epsilon, tree_type, axis); return bvhtree_from_editmesh_looptri_ex(data, em, {}, -1, epsilon, tree_type, axis);
} }
BVHTree *bvhtree_from_mesh_looptri_ex(BVHTreeFromMesh *data, BVHTree *bvhtree_from_mesh_looptri_ex(BVHTreeFromMesh *data,
const float (*vert_positions)[3], const float (*vert_positions)[3],
const struct MLoop *mloop, const int *corner_verts,
const struct MLoopTri *looptri, const struct MLoopTri *looptri,
const int looptri_num, const int looptri_num,
const BitVector<> &looptri_mask, const BitVector<> &looptri_mask,
int looptri_num_active, int looptri_num_active,
float epsilon, float epsilon,
int tree_type, int tree_type,
int axis) int axis)
{ {
BVHTree *tree = bvhtree_from_mesh_looptri_create_tree(epsilon, BVHTree *tree = bvhtree_from_mesh_looptri_create_tree(epsilon,
tree_type, tree_type,
axis, axis,
vert_positions, vert_positions,
mloop, corner_verts,
looptri, looptri,
looptri_num, looptri_num,
looptri_mask, looptri_mask,
looptri_num_active); looptri_num_active);
bvhtree_balance(tree, false); bvhtree_balance(tree, false);
if (data) { if (data) {
/* Setup BVHTreeFromMesh */ /* Setup BVHTreeFromMesh */
bvhtree_from_mesh_setup_data( bvhtree_from_mesh_setup_data(
tree, BVHTREE_FROM_LOOPTRI, vert_positions, nullptr, nullptr, mloop, looptri, data); tree, BVHTREE_FROM_LOOPTRI, vert_positions, nullptr, nullptr, corner_verts, looptri, data);
} }
return tree; return tree;
} }
static BitVector<> loose_verts_map_get(const Span<MEdge> edges, static BitVector<> loose_verts_map_get(const Span<MEdge> edges,
int verts_num, int verts_num,
int *r_loose_vert_num) int *r_loose_vert_num)
▲ Show 20 Lines • Show All 68 Lines • ▼ Show 20 Lines
const MLoopTri *looptri = nullptr; const MLoopTri *looptri = nullptr;
int looptri_len = 0; int looptri_len = 0;
if (ELEM(bvh_cache_type, BVHTREE_FROM_LOOPTRI, BVHTREE_FROM_LOOPTRI_NO_HIDDEN)) { if (ELEM(bvh_cache_type, BVHTREE_FROM_LOOPTRI, BVHTREE_FROM_LOOPTRI_NO_HIDDEN)) {
looptri = BKE_mesh_runtime_looptri_ensure(mesh); looptri = BKE_mesh_runtime_looptri_ensure(mesh);
looptri_len = BKE_mesh_runtime_looptri_len(mesh); looptri_len = BKE_mesh_runtime_looptri_len(mesh);
} }
const float(*positions)[3] = reinterpret_cast<const float(*)[3]>(mesh->vert_positions().data()); const float(*positions)[3] = reinterpret_cast<const float(*)[3]>(mesh->vert_positions().data());
const Span<MEdge> edges = mesh->edges(); const Span<MEdge> edges = mesh->edges();
const Span<MLoop> loops = mesh->loops(); const Span<int> corner_verts = mesh->corner_verts();
/* Setup BVHTreeFromMesh */ /* Setup BVHTreeFromMesh */
bvhtree_from_mesh_setup_data(nullptr, bvhtree_from_mesh_setup_data(nullptr,
bvh_cache_type, bvh_cache_type,
positions, positions,
edges.data(), edges.data(),
(const MFace *)CustomData_get_layer(&mesh->fdata, CD_MFACE), (const MFace *)CustomData_get_layer(&mesh->fdata, CD_MFACE),
loops.data(), corner_verts.data(),
looptri, looptri,
data); data);
bool lock_started = false; bool lock_started = false;
data->cached = bvhcache_find( data->cached = bvhcache_find(
bvh_cache_p, bvh_cache_type, &data->tree, &lock_started, &mesh->runtime->eval_mutex); bvh_cache_p, bvh_cache_type, &data->tree, &lock_started, &mesh->runtime->eval_mutex);
if (data->cached) { if (data->cached) {
▲ Show 20 Lines • Show All 46 Lines • ▼ Show 20 Lines
&mask_bits_act_len); &mask_bits_act_len);
ATTR_FALLTHROUGH; ATTR_FALLTHROUGH;
} }
case BVHTREE_FROM_LOOPTRI: case BVHTREE_FROM_LOOPTRI:
data->tree = bvhtree_from_mesh_looptri_create_tree(0.0f, data->tree = bvhtree_from_mesh_looptri_create_tree(0.0f,
tree_type, tree_type,
6, 6,
positions, positions,
loops.data(), corner_verts.data(),
looptri, looptri,
looptri_len, looptri_len,
mask, mask,
mask_bits_act_len); mask_bits_act_len);
break; break;
case BVHTREE_FROM_EM_VERTS: case BVHTREE_FROM_EM_VERTS:
case BVHTREE_FROM_EM_EDGES: case BVHTREE_FROM_EM_EDGES:
case BVHTREE_FROM_EM_LOOPTRI: case BVHTREE_FROM_EM_LOOPTRI:
▲ Show 20 Lines • Show All 92 Lines • Show Last 20 Lines