computeInitialHull method

ConvexHull computeInitialHull()

Implementation

ConvexHull computeInitialHull() {
  //var line3, plane, closestPoint;

  //if (line3 == null) {
  var line3 = Line3(null, null);
  var plane = Plane(null, null);
  var closestPoint = Vector3.init();
  //}

  var vertex, vertices = this.vertices;
  var extremes = computeExtremes();
  var min = extremes["min"]!;
  var max = extremes["max"]!;

  var v0, v1, v2, v3;
  var 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;
  var 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.set(v0.point, v1.point);

  for (var 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 (var i = 0, l = this.vertices.length; i < l; i++) {
    vertex = vertices[i];

    if (vertex != v0 && vertex != v1 && vertex != v2) {
      distance = Math.abs(plane.distanceToPoint(vertex.point));

      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;

      // join face[ i ] i > 0, with the first face

      faces[i + 1].getEdge(2)!.setTwin(faces[0].getEdge((3 - i) % 3));

      // join face[ i ] with face[ i + 1 ]

      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 (var 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;
}