summaryrefslogtreecommitdiff
path: root/core/math/quick_hull.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'core/math/quick_hull.cpp')
-rw-r--r--core/math/quick_hull.cpp31
1 files changed, 0 insertions, 31 deletions
diff --git a/core/math/quick_hull.cpp b/core/math/quick_hull.cpp
index 7fbb26c377..ace8ac9878 100644
--- a/core/math/quick_hull.cpp
+++ b/core/math/quick_hull.cpp
@@ -35,12 +35,10 @@
uint32_t QuickHull::debug_stop_after = 0xFFFFFFFF;
Error QuickHull::build(const Vector<Vector3> &p_points, Geometry::MeshData &r_mesh) {
-
/* CREATE AABB VOLUME */
AABB aabb;
for (int i = 0; i < p_points.size(); i++) {
-
if (i == 0) {
aabb.position = p_points[i];
} else {
@@ -57,7 +55,6 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry::MeshData &r_me
Set<Vector3> valid_cache;
for (int i = 0; i < p_points.size(); i++) {
-
Vector3 sp = p_points[i].snapped(Vector3(0.0001, 0.0001, 0.0001));
if (valid_cache.has(sp)) {
valid_points.write[i] = false;
@@ -78,12 +75,10 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry::MeshData &r_me
real_t max = 0, min = 0;
for (int i = 0; i < p_points.size(); i++) {
-
if (!valid_points[i])
continue;
real_t d = p_points[i][longest_axis];
if (i == 0 || d < min) {
-
simplex[0] = i;
min = d;
}
@@ -102,7 +97,6 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry::MeshData &r_me
Vector3 rel12 = p_points[simplex[0]] - p_points[simplex[1]];
for (int i = 0; i < p_points.size(); i++) {
-
if (!valid_points[i])
continue;
@@ -110,7 +104,6 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry::MeshData &r_me
real_t d = Math::abs(n.dot(p_points[simplex[0]]) - n.dot(p_points[i]));
if (i == 0 || d > maxd) {
-
maxd = d;
simplex[2] = i;
}
@@ -124,14 +117,12 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry::MeshData &r_me
Plane p(p_points[simplex[0]], p_points[simplex[1]], p_points[simplex[2]]);
for (int i = 0; i < p_points.size(); i++) {
-
if (!valid_points[i])
continue;
real_t d = Math::abs(p.distance_to(p_points[i]));
if (i == 0 || d > maxd) {
-
maxd = d;
simplex[3] = i;
}
@@ -152,7 +143,6 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry::MeshData &r_me
List<Face> faces;
for (int i = 0; i < 4; i++) {
-
static const int face_order[4][3] = {
{ 0, 1, 2 },
{ 0, 1, 3 },
@@ -183,7 +173,6 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry::MeshData &r_me
/* COMPUTE AVAILABLE VERTICES */
for (int i = 0; i < p_points.size(); i++) {
-
if (i == simplex[0])
continue;
if (i == simplex[1])
@@ -196,9 +185,7 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry::MeshData &r_me
continue;
for (List<Face>::Element *E = faces.front(); E; E = E->next()) {
-
if (E->get().plane.distance_to(p_points[i]) > over_tolerance) {
-
E->get().points_over.push_back(i);
break;
}
@@ -219,7 +206,6 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry::MeshData &r_me
uint32_t debug_stop = debug_stop_after;
while (debug_stop > 0 && faces.back()->get().points_over.size()) {
-
debug_stop--;
Face &f = faces.back()->get();
@@ -228,7 +214,6 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry::MeshData &r_me
real_t next_d = 0;
for (int i = 0; i < f.points_over.size(); i++) {
-
real_t d = f.plane.distance_to(p_points[f.points_over[i]]);
if (d > next_d) {
@@ -247,9 +232,7 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry::MeshData &r_me
Map<Edge, FaceConnect> lit_edges; //create this on the flight, should not be that bad for performance and simplifies code a lot
for (List<Face>::Element *E = faces.front(); E; E = E->next()) {
-
if (E->get().plane.distance_to(v) > 0) {
-
lit_faces.push_back(E);
for (int i = 0; i < 3; i++) {
@@ -265,7 +248,6 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry::MeshData &r_me
//left
F->get().left = E;
} else {
-
F->get().right = E;
}
}
@@ -276,7 +258,6 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry::MeshData &r_me
List<List<Face>::Element *> new_faces; //new faces
for (Map<Edge, FaceConnect>::Element *E = lit_edges.front(); E; E = E->next()) {
-
FaceConnect &fc = E->get();
if (fc.left && fc.right) {
continue; //edge is uninteresting, not on horizont
@@ -304,17 +285,14 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry::MeshData &r_me
//distribute points into new faces
for (List<List<Face>::Element *>::Element *F = lit_faces.front(); F; F = F->next()) {
-
Face &lf = F->get()->get();
for (int i = 0; i < lf.points_over.size(); i++) {
-
if (lf.points_over[i] == f.points_over[next]) //do not add current one
continue;
Vector3 p = p_points[lf.points_over[i]];
for (List<List<Face>::Element *>::Element *E = new_faces.front(); E; E = E->next()) {
-
Face &f2 = E->get()->get();
if (f2.plane.distance_to(p) > over_tolerance) {
f2.points_over.push_back(lf.points_over[i]);
@@ -327,7 +305,6 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry::MeshData &r_me
//erase lit faces
while (lit_faces.size()) {
-
faces.erase(lit_faces.front()->get());
lit_faces.pop_front();
}
@@ -335,7 +312,6 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry::MeshData &r_me
//put faces that contain no points on the front
for (List<List<Face>::Element *>::Element *E = new_faces.front(); E; E = E->next()) {
-
Face &f2 = E->get()->get();
if (f2.points_over.size() == 0) {
faces.move_to_front(E->get());
@@ -352,7 +328,6 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry::MeshData &r_me
List<Geometry::MeshData::Face> ret_faces;
for (List<Face>::Element *E = faces.front(); E; E = E->next()) {
-
Geometry::MeshData::Face f;
f.plane = E->get().plane;
@@ -363,7 +338,6 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry::MeshData &r_me
List<Geometry::MeshData::Face>::Element *F = ret_faces.push_back(f);
for (int i = 0; i < 3; i++) {
-
uint32_t a = E->get().vertices[i];
uint32_t b = E->get().vertices[(i + 1) % 3];
Edge e(a, b);
@@ -376,7 +350,6 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry::MeshData &r_me
//left
G->get().left = F;
} else {
-
G->get().right = F;
}
}
@@ -385,11 +358,9 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry::MeshData &r_me
//fill faces
for (List<Geometry::MeshData::Face>::Element *E = ret_faces.front(); E; E = E->next()) {
-
Geometry::MeshData::Face &f = E->get();
for (int i = 0; i < f.indices.size(); i++) {
-
int a = E->get().indices[i];
int b = E->get().indices[(i + 1) % f.indices.size()];
Edge e(a, b);
@@ -411,7 +382,6 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry::MeshData &r_me
if (O->get().indices[j] == a) {
//append the rest
for (int k = 0; k < ois; k++) {
-
int idx = O->get().indices[(k + j) % ois];
int idxn = O->get().indices[(k + j + 1) % ois];
if (idx == b && idxn == a) { //already have b!
@@ -463,7 +433,6 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry::MeshData &r_me
r_mesh.edges.resize(ret_edges.size());
idx = 0;
for (Map<Edge, RetFaceConnect>::Element *E = ret_edges.front(); E; E = E->next()) {
-
Geometry::MeshData::Edge e;
e.a = E->key().vertices[0];
e.b = E->key().vertices[1];
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-22 01:07:02 +0000