summaryrefslogtreecommitdiffstats
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.cpp254
1 files changed, 29 insertions, 225 deletions
diff --git a/core/math/triangle_mesh.cpp b/core/math/triangle_mesh.cpp
index 6515c55a85..0da1b8c7ad 100644
--- a/core/math/triangle_mesh.cpp
+++ b/core/math/triangle_mesh.cpp
@@ -1,32 +1,32 @@
-/*************************************************************************/
-/* triangle_mesh.cpp */
-/*************************************************************************/
-/* This file is part of: */
-/* GODOT ENGINE */
-/* https://godotengine.org */
-/*************************************************************************/
-/* Copyright (c) 2007-2022 Juan Linietsky, Ariel Manzur. */
-/* Copyright (c) 2014-2022 Godot Engine contributors (cf. AUTHORS.md). */
-/* */
-/* Permission is hereby granted, free of charge, to any person obtaining */
-/* a copy of this software and associated documentation files (the */
-/* "Software"), to deal in the Software without restriction, including */
-/* without limitation the rights to use, copy, modify, merge, publish, */
-/* distribute, sublicense, and/or sell copies of the Software, and to */
-/* permit persons to whom the Software is furnished to do so, subject to */
-/* the following conditions: */
-/* */
-/* The above copyright notice and this permission notice shall be */
-/* included in all copies or substantial portions of the Software. */
-/* */
-/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */
-/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */
-/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/
-/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */
-/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */
-/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */
-/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */
-/*************************************************************************/
+/**************************************************************************/
+/* triangle_mesh.cpp */
+/**************************************************************************/
+/* This file is part of: */
+/* GODOT ENGINE */
+/* https://godotengine.org */
+/**************************************************************************/
+/* Copyright (c) 2014-present Godot Engine contributors (see AUTHORS.md). */
+/* Copyright (c) 2007-2014 Juan Linietsky, Ariel Manzur. */
+/* */
+/* Permission is hereby granted, free of charge, to any person obtaining */
+/* a copy of this software and associated documentation files (the */
+/* "Software"), to deal in the Software without restriction, including */
+/* without limitation the rights to use, copy, modify, merge, publish, */
+/* distribute, sublicense, and/or sell copies of the Software, and to */
+/* permit persons to whom the Software is furnished to do so, subject to */
+/* the following conditions: */
+/* */
+/* The above copyright notice and this permission notice shall be */
+/* included in all copies or substantial portions of the Software. */
+/* */
+/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */
+/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */
+/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. */
+/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */
+/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */
+/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */
+/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */
+/**************************************************************************/
#include "triangle_mesh.h"
@@ -182,90 +182,6 @@ void TriangleMesh::create(const Vector<Vector3> &p_faces, const Vector<int32_t>
valid = true;
}
-Vector3 TriangleMesh::get_area_normal(const AABB &p_aabb) const {
- uint32_t *stack = (uint32_t *)alloca(sizeof(int) * max_depth);
-
- enum {
- TEST_AABB_BIT = 0,
- VISIT_LEFT_BIT = 1,
- VISIT_RIGHT_BIT = 2,
- VISIT_DONE_BIT = 3,
- VISITED_BIT_SHIFT = 29,
- NODE_IDX_MASK = (1 << VISITED_BIT_SHIFT) - 1,
- VISITED_BIT_MASK = ~NODE_IDX_MASK,
-
- };
-
- int n_count = 0;
- Vector3 n;
-
- int level = 0;
-
- const Triangle *triangleptr = triangles.ptr();
- // const Vector3 *verticesr = vertices.ptr();
- const BVH *bvhptr = bvh.ptr();
-
- int pos = bvh.size() - 1;
-
- 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: {
- if (!b.aabb.intersects(p_aabb)) {
- 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++;
-
- 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;
- level++;
- stack[level] = b.left | TEST_AABB_BIT;
- continue;
- }
- case VISIT_RIGHT_BIT: {
- stack[level] = (VISIT_DONE_BIT << VISITED_BIT_SHIFT) | node;
- level++;
- stack[level] = b.right | TEST_AABB_BIT;
- continue;
- }
- case VISIT_DONE_BIT: {
- if (level == 0) {
- done = true;
- break;
- } else {
- level--;
- }
- continue;
- }
- }
-
- if (done) {
- break;
- }
- }
-
- 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, int32_t *r_surf_index) const {
uint32_t *stack = (uint32_t *)alloca(sizeof(int) * max_depth);
@@ -468,118 +384,6 @@ bool TriangleMesh::intersect_ray(const Vector3 &p_begin, const Vector3 &p_dir, V
return inters;
}
-bool TriangleMesh::intersect_convex_shape(const Plane *p_planes, int p_plane_count, const Vector3 *p_points, int p_point_count) const {
- uint32_t *stack = (uint32_t *)alloca(sizeof(int) * max_depth);
-
- //p_fully_inside = true;
-
- enum {
- TEST_AABB_BIT = 0,
- VISIT_LEFT_BIT = 1,
- VISIT_RIGHT_BIT = 2,
- VISIT_DONE_BIT = 3,
- VISITED_BIT_SHIFT = 29,
- NODE_IDX_MASK = (1 << VISITED_BIT_SHIFT) - 1,
- VISITED_BIT_MASK = ~NODE_IDX_MASK,
-
- };
-
- int level = 0;
-
- const Triangle *triangleptr = triangles.ptr();
- const Vector3 *vertexptr = vertices.ptr();
- const BVH *bvhptr = bvh.ptr();
-
- int pos = bvh.size() - 1;
-
- 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: {
- if (!b.aabb.intersects_convex_shape(p_planes, p_plane_count, p_points, p_point_count)) {
- 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) {
- const Vector3 &point = vertexptr[s.indices[j]];
- const Vector3 &next_point = vertexptr[s.indices[(j + 1) % 3]];
- Vector3 res;
- bool over = true;
- for (int i = 0; i < p_plane_count; i++) {
- const Plane &p = p_planes[i];
-
- if (p.intersects_segment(point, next_point, &res)) {
- bool inisde = true;
- for (int k = 0; k < p_plane_count; k++) {
- if (k == i) {
- continue;
- }
- const Plane &pp = p_planes[k];
- if (pp.is_point_over(res)) {
- inisde = false;
- break;
- }
- }
- if (inisde) {
- return true;
- }
- }
-
- if (p.is_point_over(point)) {
- over = false;
- break;
- }
- }
- 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;
- level++;
- stack[level] = b.left | TEST_AABB_BIT;
- continue;
- }
- case VISIT_RIGHT_BIT: {
- stack[level] = (VISIT_DONE_BIT << VISITED_BIT_SHIFT) | node;
- level++;
- stack[level] = b.right | TEST_AABB_BIT;
- continue;
- }
- case VISIT_DONE_BIT: {
- if (level == 0) {
- done = true;
- break;
- } else {
- level--;
- }
- continue;
- }
- }
-
- if (done) {
- break;
- }
- }
-
- return false;
-}
-
bool TriangleMesh::inside_convex_shape(const Plane *p_planes, int p_plane_count, const Vector3 *p_points, int p_point_count, Vector3 p_scale) const {
uint32_t *stack = (uint32_t *)alloca(sizeof(int) * max_depth);