computeInitialHull method
Implementation
ConvexHull computeInitialHull() {
//final line3, plane, closestPoint;
//if (line3 == null) {
final line3 = Line3();
final plane = Plane();
final closestPoint = Vector3();
//}
VertexNode? vertex;
final vertices = this.vertices;
final extremes = computeExtremes();
final min = extremes["min"]!;
final max = extremes["max"]!;
late VertexNode v0, v1, v2, v3;
int i, j;
// 1. Find the two vertices 'v0' and 'v1' with the greatest 1d separation
// (max.x - min.x)
// (max.y - min.y)
// (max.z - min.z)
num distance;
num maxDistance = 0;
int index = 0;
for (i = 0; i < 3; i++) {
distance = max[i].point.getComponent(i) - min[i].point.getComponent(i);
if (distance > maxDistance) {
maxDistance = distance;
index = i;
}
}
v0 = min[index];
v1 = max[index];
// 2. The next vertex 'v2' is the one farthest to the line formed by 'v0' and 'v1'
maxDistance = 0;
line3.setStartEnd(v0.point, v1.point);
for (int i = 0, l = this.vertices.length; i < l; i++) {
vertex = vertices[i];
if (vertex != v0 && vertex != v1) {
line3.closestPointToPoint(vertex.point, true, closestPoint);
distance = closestPoint.distanceToSquared(vertex.point);
if (distance > maxDistance) {
maxDistance = distance;
v2 = vertex;
}
}
}
// 3. The next vertex 'v3' is the one farthest to the plane 'v0', 'v1', 'v2'
maxDistance = -1;
plane.setFromCoplanarPoints(v0.point, v1.point, v2.point);
for (int i = 0, l = this.vertices.length; i < l; i++) {
vertex = vertices[i];
if (vertex != v0 && vertex != v1 && vertex != v2) {
distance = plane.distanceToPoint(vertex.point).abs();
if (distance > maxDistance) {
maxDistance = distance;
v3 = vertex;
}
}
}
List<Face2> faces = [];
if (plane.distanceToPoint(v3.point) < 0) {
// the face is not able to see the point so 'plane.normal' is pointing outside the tetrahedron
faces.addAll([
Face2.create(v0, v1, v2),
Face2.create(v3, v1, v0),
Face2.create(v3, v2, v1),
Face2.create(v3, v0, v2)
]);
// set the twin edge
for (i = 0; i < 3; i++) {
j = (i + 1) % 3;
// join face[ i ] i > 0, with the first face
faces[i + 1].getEdge(2)!.setTwin(faces[0].getEdge(j));
// join face[ i ] with face[ i + 1 ], 1 <= i <= 3
faces[i + 1].getEdge(1)!.setTwin(faces[j + 1].getEdge(0));
}
} else {
// the face is able to see the point so 'plane.normal' is pointing inside the tetrahedron
faces.addAll([
Face2.create(v0, v2, v1),
Face2.create(v3, v0, v1),
Face2.create(v3, v1, v2),
Face2.create(v3, v2, v0)
]);
// set the twin edge
for (i = 0; i < 3; i++) {
j = (i + 1) % 3;
faces[i + 1].getEdge(2)!.setTwin(faces[0].getEdge((3 - i) % 3));
faces[i + 1].getEdge(0)!.setTwin(faces[j + 1].getEdge(1));
}
}
// the initial hull is the tetrahedron
for (i = 0; i < 4; i++) {
faces.add(faces[i]);
}
// initial assignment of vertices to the faces of the tetrahedron
for (int i = 0, l = vertices.length; i < l; i++) {
vertex = vertices[i];
if (vertex != v0 && vertex != v1 && vertex != v2 && vertex != v3) {
maxDistance = tolerance;
Face2? maxFace2;
for (j = 0; j < 4; j++) {
distance = faces[j].distanceToPoint(vertex.point);
if (distance > maxDistance) {
maxDistance = distance;
maxFace2 = faces[j];
}
}
if (maxFace2 != null) {
addVertexToFace2(vertex, maxFace2);
}
}
}
return this;
}