convex.js

/**
 * @author qiao / https://github.com/qiao
 * @fileoverview This is a convex hull generator using the incremental method.
 * The complexity is O(n^2) where n is the number of vertices.
 * O(nlogn) algorithms do exist, but they are much more complicated.
 *
 * Benchmark:
 *
 *  Platform: CPU: P7350 @2.00GHz Engine: V8
 *
 *  Num Vertices	Time(ms)
 *
 *     10           1
 *     20           3
 *     30           19
 *     40           48
 *     50           107
 */

THREE.ConvexGeometry = function(vertices) {

  THREE.Geometry.call(this);

  var faces = [
    [0, 1, 2],
    [0, 2, 1]
  ];

  for (var i = 3; i < vertices.length; i++) {

    addPoint(i);

  }


  function addPoint(vertexId) {

    var vertex = vertices[vertexId].clone();

    var mag = vertex.length();
    vertex.x += mag * randomOffset();
    vertex.y += mag * randomOffset();
    vertex.z += mag * randomOffset();

    var hole = [];

    for (var f = 0; f < faces.length;) {

      var face = faces[f];

      // for each face, if the vertex can see it,
      // then we try to add the face's edges into the hole.
      if (visible(face, vertex)) {

        for (var e = 0; e < 3; e++) {

          var edge = [face[e], face[(e + 1) % 3]];
          var boundary = true;

          // remove duplicated edges.
          for (var h = 0; h < hole.length; h++) {

            if (equalEdge(hole[h], edge)) {

              hole[h] = hole[hole.length - 1];
              hole.pop();
              boundary = false;
              break;

            }

          }

          if (boundary) {

            hole.push(edge);

          }

        }

        // remove faces[ f ]
        faces[f] = faces[faces.length - 1];
        faces.pop();

      } else { // not visible

        f++;

      }
    }

    // construct the new faces formed by the edges of the hole and the vertex
    for (var h = 0; h < hole.length; h++) {

      faces.push([
        hole[h][0],
        hole[h][1],
        vertexId
      ]);

    }
  }

  /**
   * Whether the face is visible from the vertex
   */
  function visible(face, vertex) {

    var va = vertices[face[0]];
    var vb = vertices[face[1]];
    var vc = vertices[face[2]];

    var n = normal(va, vb, vc);

    // distance from face to origin
    var dist = n.dot(va);

    return n.dot(vertex) >= dist;

  }

  /**
   * Face normal
   */
  function normal(va, vb, vc) {

    var cb = new THREE.Vector3();
    var ab = new THREE.Vector3();

    cb.subVectors(vc, vb);
    ab.subVectors(va, vb);
    cb.cross(ab);

    cb.normalize();

    return cb;

  }

  /**
   * Detect whether two edges are equal.
   * Note that when constructing the convex hull, two same edges can only
   * be of the negative direction.
   */
  function equalEdge(ea, eb) {

    return ea[0] === eb[1] && ea[1] === eb[0];

  }

  /**
   * Create a random offset between -1e-6 and 1e-6.
   */
  function randomOffset() {

    return (Math.random() - 0.5) * 2 * 1e-6;

  }


  /**
   * XXX: Not sure if this is the correct approach. Need someone to review.
   */
  function vertexUv(vertex) {

    var mag = vertex.length();
    return new THREE.Vector2(vertex.x / mag, vertex.y / mag);

  }

  // Push vertices into `this.vertices`, skipping those inside the hull
  var id = 0;
  var newId = new Array(vertices.length); // map from old vertex id to new id

  for (var i = 0; i < faces.length; i++) {

    var face = faces[i];

    for (var j = 0; j < 3; j++) {

      if (newId[face[j]] === undefined) {

        newId[face[j]] = id++;
        this.vertices.push(vertices[face[j]]);

      }

      face[j] = newId[face[j]];

    }

  }

  // Convert faces into instances of THREE.Face3
  for (var i = 0; i < faces.length; i++) {

    this.faces.push(new THREE.Face3(
      faces[i][0],
      faces[i][1],
      faces[i][2]
    ));

  }

  // Compute UVs
  for (var i = 0; i < this.faces.length; i++) {

    var face = this.faces[i];

    this.faceVertexUvs[0].push([
      vertexUv(this.vertices[face.a]),
      vertexUv(this.vertices[face.b]),
      vertexUv(this.vertices[face.c])
    ]);

  }

  this.computeFaceNormals();
  this.computeVertexNormals();

};

THREE.ConvexGeometry.prototype = Object.create(THREE.Geometry.prototype);