polygon cube intersection in threejs

poly.ts

function signNonZero(x: number): number {
  return x < 0 ? -1 : 1;
}

function inClosedInterval(a: number, x: number, b: number): boolean {
  return (x-a) * (x-b) <= 0;
}

function segContainsPoint(a: number, b: number, x: number): number {
  return (b > x ? 1 : 0) - (a > x ? 1 : 0);
}

/**
 * See
 * <https://github.com/erich666/GraphicsGems/blob/9632659c0e3592d8cecf8866fcc34498a85c8d22/gemsv/ch7-2/pcube.c#L104>.
 */
const segmentIntersectsCube = (() => {
  // tslint:disable

  const edgevec = new THREE.Vector3();
  const edgevec_signs = new THREE.Vector3();

  return (
    v0: THREE.Vector3,
    v1: THREE.Vector3,
  ): boolean => {
    edgevec.copy(v0);
    edgevec.sub(v1);

    for (let i = 0; i < 3; i++) {
      edgevec_signs.setComponent(i, signNonZero(edgevec.getComponent(i)));
    }

    // Test the three cube faces on the v1-ward side of the cube--
    // if v0 is outside any of their planes then there is no intersection.
    // Also test the three cube faces on the v0-ward side of the cube--
    // if v1 is outside any of their planes then there is no intersection.

    for (let i = 0; i < 3; i++) {
      if (v0.getComponent(i) * edgevec_signs.getComponent(i) > 0.5) {
        return false;
      }
      if (v1.getComponent(i) * edgevec_signs.getComponent(i) < -0.5) {
        return false;
      }
    }

    // Okay, that's the six easy faces of the rhombic dodecahedron
    // out of the way.  Six more to go.
    // The remaining six planes bound an infinite hexagonal prism
    // joining the petrie polygons (skew hexagons) of the two cubes
    // centered at the endpoints.
    let iplus1: number;
    let iplus2: number;
    for (let i = 0; i < 3; i++) {
      iplus1 = (i+1)%3;
      iplus2 = (i+2)%3;

      const rhomb_normal_dot_v0 =
        edgevec.getComponent(iplus2) * v0.getComponent(iplus1) -
        edgevec.getComponent(iplus1) * v0.getComponent(iplus2);

      const rhomb_normal_dot_cubedge =
        .5 * (edgevec.getComponent(iplus2) * edgevec_signs.getComponent(iplus1) +
              edgevec.getComponent(iplus1) * edgevec_signs.getComponent(iplus2));

      if (
        rhomb_normal_dot_v0*rhomb_normal_dot_v0 >
        rhomb_normal_dot_cubedge*rhomb_normal_dot_cubedge
      ) {
        return false;
      }
    }

    return true;
  }
})();

const polygonContainsPoint3D = (() => {
  return (
    verts: THREE.Vector3[],
    polynormal: THREE.Vector3,
    point: THREE.Vector3,
  ): number => {
    // Determine which axis to ignore
    // (the one in which the polygon normal is largest)
    let zaxis = -1;
    let maxdim = -1;
    for (let i = 0; i < 3; i++) {
      const v = Math.abs(polynormal.getComponent(i));
      if (v > maxdim) {
        zaxis = i;
        maxdim = v;
      }
    }

    let xaxis: number;
    let yaxis: number;
    if (polynormal.getComponent(zaxis) < 0) {
      xaxis = (zaxis+2)%3;
      yaxis = (zaxis+1)%3;
    } else {
      xaxis = (zaxis+1)%3;
      yaxis = (zaxis+2)%3;
    }

    let count = 0;
    let v: THREE.Vector3;
    let w: THREE.Vector3;
    for (let i = 0; i < verts.length; i++) {
      v = verts[i];
      w = verts[(i+1)%verts.length];
      const xdirection = segContainsPoint(v.getComponent(xaxis), w.getComponent(xaxis), point.getComponent(xaxis));
      if (xdirection) {
        if (segContainsPoint(v.getComponent(yaxis), w.getComponent(yaxis), point.getComponent(yaxis))) {
          if (xdirection * (point.getComponent(xaxis)-v.getComponent(xaxis))*(w.getComponent(yaxis)-v.getComponent(yaxis)) <=
              xdirection * (point.getComponent(yaxis)-v.getComponent(yaxis))*(w.getComponent(xaxis)-v.getComponent(xaxis)))
              count += xdirection;
        } else {
          if (v.getComponent(yaxis) <= point.getComponent(yaxis))
              count += xdirection;
        }
      }
    }
    return count;
  }
})();

/* See
 * <https://github.com/erich666/GraphicsGems/blob/9632659c0e3592d8cecf8866fcc34498a85c8d22/gemsv/ch7-2/pcube.h#L53>
 */
const polygonIntersectsCube = (() => {
  // tslint:disable

  const best_diagonal = new THREE.Vector3();
  const p = new THREE.Vector3();

  return (
    verts: THREE.Vector3[],
    polynormal: THREE.Vector3,
  ): boolean => {
    // If any edge intersects the cube, return 1.
    for (let i = 0; i < verts.length; i++) {
      if (segmentIntersectsCube(verts[i], verts[(i+1)%verts.length])) {
        return true;
      }
    }

    // If the polygon normal is zero and none of its edges intersect the
    // cube, then it doesn't intersect the cube
    if (polynormal.x === 0 && polynormal.y === 0 && polynormal.z === 0) {
	    return false;
    }

    // Now that we know that none of the polygon's edges intersects the cube,
    // deciding whether the polygon intersects the cube amounts
    // to testing whether any of the four cube diagonals intersects
    // the interior of the polygon.
    //
    // Notice that we only need to consider the cube diagonal that comes
    // closest to being perpendicular to the plane of the polygon.
    // If the polygon intersects any of the cube diagonals,
    // it will intersect that one.
    for (let i = 0; i < 3; i++) {
      best_diagonal.setComponent(i, signNonZero(polynormal.getComponent(i)));
    }

    // Okay, we have the diagonal of interest.
    // The plane containing the polygon is the set of all points p satisfying
    //      DOT3(polynormal, p) == DOT3(polynormal, verts[0])
    // So find the point p on the cube diagonal of interest
    // that satisfies this equation.
    // The line containing the cube diagonal is described parametrically by
    //      t * best_diagonal
    // so plug this into the previous equation and solve for t.
    //      DOT3(polynormal, t * best_diagonal) == DOT3(polynormal, verts[0])
    // i.e.
    //      t = DOT3(polynormal, verts[0]) / DOT3(polynormal, best_diagonal)
    //
    // (Note that the denominator is guaranteed to be nonzero, since
    // polynormal is nonzero and best_diagonal was chosen to have the largest
    // magnitude dot-product with polynormal)
    const t = polynormal.dot(verts[0]) / polynormal.dot(best_diagonal);

    if (!inClosedInterval(-0.5, t, 0.5)) {
      return false; // intersection point is not in the cube
    }

    p.copy(best_diagonal).multiplyScalar(t);

    return !!polygonContainsPoint3D(verts, polynormal, p);
  }
})();