summaryrefslogtreecommitdiff
path: root/core/math/triangle_mesh.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'core/math/triangle_mesh.cpp')
-rw-r--r--core/math/triangle_mesh.cpp132
1 files changed, 43 insertions, 89 deletions
diff --git a/core/math/triangle_mesh.cpp b/core/math/triangle_mesh.cpp
index 0f7350a260..c9a546e385 100644
--- a/core/math/triangle_mesh.cpp
+++ b/core/math/triangle_mesh.cpp
@@ -33,30 +33,25 @@
#include "core/sort_array.h"
int TriangleMesh::_create_bvh(BVH *p_bvh, BVH **p_bb, int p_from, int p_size, int p_depth, int &max_depth, int &max_alloc) {
-
if (p_depth > max_depth) {
max_depth = p_depth;
}
if (p_size == 1) {
-
return p_bb[p_from] - p_bvh;
} else if (p_size == 0) {
-
return -1;
}
AABB aabb;
aabb = p_bb[p_from]->aabb;
for (int i = 1; i < p_size; i++) {
-
aabb.merge_with(p_bb[p_from + i]->aabb);
}
int li = aabb.get_longest_axis_index();
switch (li) {
-
case Vector3::AXIS_X: {
SortArray<BVH *, BVHCmpX> sort_x;
sort_x.nth_element(0, p_size, p_size / 2, &p_bb[p_from]);
@@ -90,9 +85,9 @@ int TriangleMesh::_create_bvh(BVH *p_bvh, BVH **p_bb, int p_from, int p_size, in
}
void TriangleMesh::get_indices(Vector<int> *r_triangles_indices) const {
-
- if (!valid)
+ if (!valid) {
return;
+ }
const int triangles_num = triangles.size();
@@ -110,7 +105,6 @@ void TriangleMesh::get_indices(Vector<int> *r_triangles_indices) const {
}
void TriangleMesh::create(const Vector<Vector3> &p_faces) {
-
valid = false;
int fc = p_faces.size();
@@ -122,7 +116,6 @@ void TriangleMesh::create(const Vector<Vector3> &p_faces) {
BVH *bw = bvh.ptrw();
{
-
//create faces and indices and base bvh
//except for the Set for repeated triangles, everything
//goes in-place.
@@ -132,12 +125,10 @@ void TriangleMesh::create(const Vector<Vector3> &p_faces) {
Map<Vector3, int> db;
for (int i = 0; i < fc; i++) {
-
Triangle &f = w[i];
const Vector3 *v = &r[i * 3];
for (int j = 0; j < 3; j++) {
-
int vidx = -1;
Vector3 vs = v[j].snapped(Vector3(0.0001, 0.0001, 0.0001));
Map<Vector3, int>::Element *E = db.find(vs);
@@ -149,10 +140,11 @@ void TriangleMesh::create(const Vector<Vector3> &p_faces) {
}
f.indices[j] = vidx;
- if (j == 0)
+ if (j == 0) {
bw[i].aabb.position = vs;
- else
+ } else {
bw[i].aabb.expand_to(vs);
+ }
}
f.normal = Face3(r[i * 3 + 0], r[i * 3 + 1], r[i * 3 + 2]).get_plane().get_normal();
@@ -174,7 +166,6 @@ void TriangleMesh::create(const Vector<Vector3> &p_faces) {
bwptrs.resize(fc);
BVH **bwp = bwptrs.ptrw();
for (int i = 0; i < fc; i++) {
-
bwp[i] = &bw[i];
}
@@ -188,7 +179,6 @@ void TriangleMesh::create(const Vector<Vector3> &p_faces) {
}
Vector3 TriangleMesh::get_area_normal(const AABB &p_aabb) const {
-
uint32_t *stack = (uint32_t *)alloca(sizeof(int) * max_depth);
enum {
@@ -215,23 +205,18 @@ Vector3 TriangleMesh::get_area_normal(const AABB &p_aabb) const {
stack[0] = pos;
while (true) {
-
uint32_t node = stack[level] & NODE_IDX_MASK;
const BVH &b = bvhptr[node];
bool done = false;
switch (stack[level] >> VISITED_BIT_SHIFT) {
case TEST_AABB_BIT: {
-
bool valid = b.aabb.intersects(p_aabb);
if (!valid) {
-
stack[level] = (VISIT_DONE_BIT << VISITED_BIT_SHIFT) | node;
} else {
-
if (b.face_index >= 0) {
-
const Triangle &s = triangleptr[b.face_index];
n += s.normal;
n_count++;
@@ -239,49 +224,47 @@ Vector3 TriangleMesh::get_area_normal(const AABB &p_aabb) const {
stack[level] = (VISIT_DONE_BIT << VISITED_BIT_SHIFT) | node;
} else {
-
stack[level] = (VISIT_LEFT_BIT << VISITED_BIT_SHIFT) | node;
}
}
continue;
}
case VISIT_LEFT_BIT: {
-
stack[level] = (VISIT_RIGHT_BIT << VISITED_BIT_SHIFT) | node;
stack[level + 1] = b.left | TEST_AABB_BIT;
level++;
continue;
}
case VISIT_RIGHT_BIT: {
-
stack[level] = (VISIT_DONE_BIT << VISITED_BIT_SHIFT) | node;
stack[level + 1] = b.right | TEST_AABB_BIT;
level++;
continue;
}
case VISIT_DONE_BIT: {
-
if (level == 0) {
done = true;
break;
- } else
+ } else {
level--;
+ }
continue;
}
}
- if (done)
+ if (done) {
break;
+ }
}
- if (n_count > 0)
+ if (n_count > 0) {
n /= n_count;
+ }
return n;
}
bool TriangleMesh::intersect_segment(const Vector3 &p_begin, const Vector3 &p_end, Vector3 &r_point, Vector3 &r_normal) const {
-
uint32_t *stack = (uint32_t *)alloca(sizeof(int) * max_depth);
enum {
@@ -309,35 +292,28 @@ bool TriangleMesh::intersect_segment(const Vector3 &p_begin, const Vector3 &p_en
stack[0] = pos;
while (true) {
-
uint32_t node = stack[level] & NODE_IDX_MASK;
const BVH &b = bvhptr[node];
bool done = false;
switch (stack[level] >> VISITED_BIT_SHIFT) {
case TEST_AABB_BIT: {
-
bool valid = b.aabb.intersects_segment(p_begin, p_end);
//bool valid = b.aabb.intersects(ray_aabb);
if (!valid) {
-
stack[level] = (VISIT_DONE_BIT << VISITED_BIT_SHIFT) | node;
} else {
-
if (b.face_index >= 0) {
-
const Triangle &s = triangleptr[b.face_index];
Face3 f3(vertexptr[s.indices[0]], vertexptr[s.indices[1]], vertexptr[s.indices[2]]);
Vector3 res;
if (f3.intersects_segment(p_begin, p_end, &res)) {
-
real_t nd = n.dot(res);
if (nd < d) {
-
d = nd;
r_point = res;
r_normal = f3.get_plane().get_normal();
@@ -348,52 +324,49 @@ bool TriangleMesh::intersect_segment(const Vector3 &p_begin, const Vector3 &p_en
stack[level] = (VISIT_DONE_BIT << VISITED_BIT_SHIFT) | node;
} else {
-
stack[level] = (VISIT_LEFT_BIT << VISITED_BIT_SHIFT) | node;
}
}
continue;
}
case VISIT_LEFT_BIT: {
-
stack[level] = (VISIT_RIGHT_BIT << VISITED_BIT_SHIFT) | node;
stack[level + 1] = b.left | TEST_AABB_BIT;
level++;
continue;
}
case VISIT_RIGHT_BIT: {
-
stack[level] = (VISIT_DONE_BIT << VISITED_BIT_SHIFT) | node;
stack[level + 1] = b.right | TEST_AABB_BIT;
level++;
continue;
}
case VISIT_DONE_BIT: {
-
if (level == 0) {
done = true;
break;
- } else
+ } else {
level--;
+ }
continue;
}
}
- if (done)
+ if (done) {
break;
+ }
}
if (inters) {
-
- if (n.dot(r_normal) > 0)
+ if (n.dot(r_normal) > 0) {
r_normal = -r_normal;
+ }
}
return inters;
}
bool TriangleMesh::intersect_ray(const Vector3 &p_begin, const Vector3 &p_dir, Vector3 &r_point, Vector3 &r_normal) const {
-
uint32_t *stack = (uint32_t *)alloca(sizeof(int) * max_depth);
enum {
@@ -421,33 +394,26 @@ bool TriangleMesh::intersect_ray(const Vector3 &p_begin, const Vector3 &p_dir, V
stack[0] = pos;
while (true) {
-
uint32_t node = stack[level] & NODE_IDX_MASK;
const BVH &b = bvhptr[node];
bool done = false;
switch (stack[level] >> VISITED_BIT_SHIFT) {
case TEST_AABB_BIT: {
-
bool valid = b.aabb.intersects_ray(p_begin, p_dir);
if (!valid) {
-
stack[level] = (VISIT_DONE_BIT << VISITED_BIT_SHIFT) | node;
} else {
-
if (b.face_index >= 0) {
-
const Triangle &s = triangleptr[b.face_index];
Face3 f3(vertexptr[s.indices[0]], vertexptr[s.indices[1]], vertexptr[s.indices[2]]);
Vector3 res;
if (f3.intersects_ray(p_begin, p_dir, &res)) {
-
real_t nd = n.dot(res);
if (nd < d) {
-
d = nd;
r_point = res;
r_normal = f3.get_plane().get_normal();
@@ -458,45 +424,43 @@ bool TriangleMesh::intersect_ray(const Vector3 &p_begin, const Vector3 &p_dir, V
stack[level] = (VISIT_DONE_BIT << VISITED_BIT_SHIFT) | node;
} else {
-
stack[level] = (VISIT_LEFT_BIT << VISITED_BIT_SHIFT) | node;
}
}
continue;
}
case VISIT_LEFT_BIT: {
-
stack[level] = (VISIT_RIGHT_BIT << VISITED_BIT_SHIFT) | node;
stack[level + 1] = b.left | TEST_AABB_BIT;
level++;
continue;
}
case VISIT_RIGHT_BIT: {
-
stack[level] = (VISIT_DONE_BIT << VISITED_BIT_SHIFT) | node;
stack[level + 1] = b.right | TEST_AABB_BIT;
level++;
continue;
}
case VISIT_DONE_BIT: {
-
if (level == 0) {
done = true;
break;
- } else
+ } else {
level--;
+ }
continue;
}
}
- if (done)
+ if (done) {
break;
+ }
}
if (inters) {
-
- if (n.dot(r_normal) > 0)
+ if (n.dot(r_normal) > 0) {
r_normal = -r_normal;
+ }
}
return inters;
@@ -528,23 +492,18 @@ bool TriangleMesh::intersect_convex_shape(const Plane *p_planes, int p_plane_cou
stack[0] = pos;
while (true) {
-
uint32_t node = stack[level] & NODE_IDX_MASK;
const BVH &b = bvhptr[node];
bool done = false;
switch (stack[level] >> VISITED_BIT_SHIFT) {
case TEST_AABB_BIT: {
-
bool valid = b.aabb.intersects_convex_shape(p_planes, p_plane_count, p_points, p_point_count);
if (!valid) {
-
stack[level] = (VISIT_DONE_BIT << VISITED_BIT_SHIFT) | node;
} else {
-
if (b.face_index >= 0) {
-
const Triangle &s = triangleptr[b.face_index];
for (int j = 0; j < 3; ++j) {
@@ -558,16 +517,18 @@ bool TriangleMesh::intersect_convex_shape(const Plane *p_planes, int p_plane_cou
if (p.intersects_segment(point, next_point, &res)) {
bool inisde = true;
for (int k = 0; k < p_plane_count; k++) {
- if (k == i)
+ if (k == i) {
continue;
+ }
const Plane &pp = p_planes[k];
if (pp.is_point_over(res)) {
inisde = false;
break;
}
}
- if (inisde)
+ if (inisde) {
return true;
+ }
}
if (p.is_point_over(point)) {
@@ -575,46 +536,45 @@ bool TriangleMesh::intersect_convex_shape(const Plane *p_planes, int p_plane_cou
break;
}
}
- if (over)
+ if (over) {
return true;
+ }
}
stack[level] = (VISIT_DONE_BIT << VISITED_BIT_SHIFT) | node;
} else {
-
stack[level] = (VISIT_LEFT_BIT << VISITED_BIT_SHIFT) | node;
}
}
continue;
}
case VISIT_LEFT_BIT: {
-
stack[level] = (VISIT_RIGHT_BIT << VISITED_BIT_SHIFT) | node;
stack[level + 1] = b.left | TEST_AABB_BIT;
level++;
continue;
}
case VISIT_RIGHT_BIT: {
-
stack[level] = (VISIT_DONE_BIT << VISITED_BIT_SHIFT) | node;
stack[level + 1] = b.right | TEST_AABB_BIT;
level++;
continue;
}
case VISIT_DONE_BIT: {
-
if (level == 0) {
done = true;
break;
- } else
+ } else {
level--;
+ }
continue;
}
}
- if (done)
+ if (done) {
break;
+ }
}
return false;
@@ -646,86 +606,81 @@ bool TriangleMesh::inside_convex_shape(const Plane *p_planes, int p_plane_count,
stack[0] = pos;
while (true) {
-
uint32_t node = stack[level] & NODE_IDX_MASK;
const BVH &b = bvhptr[node];
bool done = false;
switch (stack[level] >> VISITED_BIT_SHIFT) {
case TEST_AABB_BIT: {
-
bool intersects = scale.xform(b.aabb).intersects_convex_shape(p_planes, p_plane_count, p_points, p_point_count);
- if (!intersects)
+ if (!intersects) {
return false;
+ }
bool inside = scale.xform(b.aabb).inside_convex_shape(p_planes, p_plane_count);
if (inside) {
-
stack[level] = (VISIT_DONE_BIT << VISITED_BIT_SHIFT) | node;
} else {
-
if (b.face_index >= 0) {
const Triangle &s = triangleptr[b.face_index];
for (int j = 0; j < 3; ++j) {
Vector3 point = scale.xform(vertexptr[s.indices[j]]);
for (int i = 0; i < p_plane_count; i++) {
const Plane &p = p_planes[i];
- if (p.is_point_over(point))
+ if (p.is_point_over(point)) {
return false;
+ }
}
}
stack[level] = (VISIT_DONE_BIT << VISITED_BIT_SHIFT) | node;
} else {
-
stack[level] = (VISIT_LEFT_BIT << VISITED_BIT_SHIFT) | node;
}
}
continue;
}
case VISIT_LEFT_BIT: {
-
stack[level] = (VISIT_RIGHT_BIT << VISITED_BIT_SHIFT) | node;
stack[level + 1] = b.left | TEST_AABB_BIT;
level++;
continue;
}
case VISIT_RIGHT_BIT: {
-
stack[level] = (VISIT_DONE_BIT << VISITED_BIT_SHIFT) | node;
stack[level + 1] = b.right | TEST_AABB_BIT;
level++;
continue;
}
case VISIT_DONE_BIT: {
-
if (level == 0) {
done = true;
break;
- } else
+ } else {
level--;
+ }
continue;
}
}
- if (done)
+ if (done) {
break;
+ }
}
return true;
}
bool TriangleMesh::is_valid() const {
-
return valid;
}
Vector<Face3> TriangleMesh::get_faces() const {
-
- if (!valid)
+ if (!valid) {
return Vector<Face3>();
+ }
Vector<Face3> faces;
int ts = triangles.size();
@@ -745,7 +700,6 @@ Vector<Face3> TriangleMesh::get_faces() const {
}
TriangleMesh::TriangleMesh() {
-
valid = false;
max_depth = 0;
}
generated by cgit v1.2.3 (git 2.25.1) at 2025-01-23 11:07:20 +0000