Package ffx.numerics.quickhull

Class Face

java.lang.Object
ffx.numerics.quickhull.Face
public class Face extends Object
Basic triangular face used to form the hull.

The information stored for each face consists of a planar normal, a planar offset, and a doubly-linked list of three HalfEdges which surround the face in a counter-clockwise direction.

Since:
1.0
Author:
John E. Lloyd, Fall 2004, Michael J. Schnieders

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    protected double
    area
     
    protected static final int
    DELETED
     
    protected HalfEdge
    he0
     
    protected int
    mark
     
    protected Face
    next
     
    protected static final int
    NON_CONVEX
     
    protected int
    numVerts
     
    protected Vertex
    outside
     
    protected double
    planeOffset
     
    protected static final int
    VISIBLE
     

  • Constructor Summary

    Constructors
    Constructor
    Description
    Face()
     

  • Method Summary

    Modifier and Type
    Method
    Description
    double
    areaSquared(HalfEdge hedge0, HalfEdge hedge1)
    Computes the squared area of the triangle defined by hedge0 (tail->head) and the point at the head of hedge1.
    void
    computeCentroid(Point3d centroid)
    Computes the centroid (arithmetic mean of vertices) of this face into the provided point.
    void
    computeNormal(Vector3d normal)
    Computes a unit-length normal vector for this face using the vertex winding and writes it into the provided vector.
    void
    computeNormal(Vector3d normal, double minArea)
    Computes a unit-length normal for this face, and if the preliminary area is below the specified minArea, adjusts the normal to be more orthogonal to the longest edge to improve robustness.
    static Face
    create(Vertex[] vtxArray, int[] indices)
    Creates a Face by linking the specified indices of a vertex array into a closed counter-clockwise half-edge loop and computing its normal and centroid.
    static Face
    createTriangle(Vertex v0, Vertex v1, Vertex v2)
    Convenience method to create a triangular Face from three vertices.
    static Face
    createTriangle(Vertex v0, Vertex v1, Vertex v2, double minArea)
    Constructs a triangular Face from vertices v0, v1, and v2 and computes its normal and centroid.
    double
    distanceToPlane(Point3d p)
    Computes the distance from a point p to the plane of this face.
    HalfEdge
    findEdge(Vertex vt, Vertex vh)
    Finds the half-edge within this face which has tail vt and head vh.
    Point3d
    getCentroid()
    Returns the centroid previously computed for this face.
    HalfEdge
    getEdge(int i)
    Gets the i-th half-edge associated with the face.
    HalfEdge
    getFirstEdge()
    Returns the first half-edge of this face (the start of the circular list).
    Vector3d
    getNormal()
    Returns the normal of the plane associated with this face.
    void
    getVertexIndices(int[] idxs)
    Writes the vertex indices of this face into the provided array in CCW order.
    String
    getVertexString()
    Returns a space-separated string of the vertex indices defining this face in counter-clockwise order.
    int
    mergeAdjacentFace(HalfEdge hedgeAdj, Face[] discarded)
    Merges this face with the adjacent face across the specified half-edge if possible.
    int
    numVertices()
    Returns the number of vertices (half-edges) bounding this face.
    void
    triangulate(FaceList newFaces, double minArea)
    Triangulates this (convex polygonal) face into a fan of triangles sharing the first vertex.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Field Details

    • DELETED

      protected static final int DELETED
      See Also:

    • NON_CONVEX

      protected static final int NON_CONVEX
      See Also:

    • VISIBLE

      protected static final int VISIBLE
      See Also:

    • area

      protected double area

    • he0

      protected HalfEdge he0

    • mark

      protected int mark

    • next

      protected Face next

    • numVerts

      protected int numVerts

    • outside

      protected Vertex outside

    • planeOffset

      protected double planeOffset

  • Constructor Details

    • Face

      public Face()

  • Method Details

    • create

      public static Face create(Vertex[] vtxArray, int[] indices)
      Creates a Face by linking the specified indices of a vertex array into a closed counter-clockwise half-edge loop and computing its normal and centroid.
      Parameters:
      vtxArray - array of vertices
      indices - indices into vtxArray specifying the face vertices in CCW order
      Returns:
      the newly created Face

    • createTriangle

      public static Face createTriangle(Vertex v0, Vertex v1, Vertex v2)
      Convenience method to create a triangular Face from three vertices.
      Parameters:
      v0 - first vertex
      v1 - second vertex
      v2 - third vertex
      Returns:
      the newly created triangular Face

    • createTriangle

      public static Face createTriangle(Vertex v0, Vertex v1, Vertex v2, double minArea)
      Constructs a triangular Face from vertices v0, v1, and v2 and computes its normal and centroid. If the computed area is below minArea, the normal is adjusted for robustness against near-collinearity.
      Parameters:
      v0 - first vertex
      v1 - second vertex
      v2 - third vertex
      minArea - minimum area threshold used to stabilize the normal
      Returns:
      the newly created triangular Face

    • computeCentroid

      public void computeCentroid(Point3d centroid)
      Computes the centroid (arithmetic mean of vertices) of this face into the provided point.
      Parameters:
      centroid - output parameter to receive the centroid

    • computeNormal

      public void computeNormal(Vector3d normal)
      Computes a unit-length normal vector for this face using the vertex winding and writes it into the provided vector. Also updates the face area and number of vertices encountered.
      Parameters:
      normal - output parameter to receive the unit normal

    • computeNormal

      public void computeNormal(Vector3d normal, double minArea)
      Computes a unit-length normal for this face, and if the preliminary area is below the specified minArea, adjusts the normal to be more orthogonal to the longest edge to improve robustness.
      Parameters:
      normal - output parameter to receive the unit normal
      minArea - minimum area threshold used to stabilize the normal computation

    • distanceToPlane

      public double distanceToPlane(Point3d p)
      Computes the distance from a point p to the plane of this face.
      Parameters:
      p - the point
      Returns:
      distance from the point to the plane

    • findEdge

      public HalfEdge findEdge(Vertex vt, Vertex vh)
      Finds the half-edge within this face which has tail vt and head vh.
      Parameters:
      vt - tail point
      vh - head point
      Returns:
      the half-edge, or null if none is found.

    • getCentroid

      public Point3d getCentroid()
      Returns the centroid previously computed for this face.
      Returns:
      the centroid point

    • getEdge

      public HalfEdge getEdge(int i)
      Gets the i-th half-edge associated with the face.
      Parameters:
      i - the half-edge index, in the range 0-2.
      Returns:
      the half-edge

    • getFirstEdge

      public HalfEdge getFirstEdge()
      Returns the first half-edge of this face (the start of the circular list).
      Returns:
      the first HalfEdge in the face

    • getNormal

      public Vector3d getNormal()
      Returns the normal of the plane associated with this face.
      Returns:
      the planar normal

    • getVertexIndices

      public void getVertexIndices(int[] idxs)
      Writes the vertex indices of this face into the provided array in CCW order. The array must be large enough to hold numVertices() entries.
      Parameters:
      idxs - output array receiving the vertex indices

    • getVertexString

      public String getVertexString()
      Returns a space-separated string of the vertex indices defining this face in counter-clockwise order.
      Returns:
      string listing the vertex indices in CCW order

    • mergeAdjacentFace

      public int mergeAdjacentFace(HalfEdge hedgeAdj, Face[] discarded)
      Merges this face with the adjacent face across the specified half-edge if possible. Updates connectivity, recomputes normals/centroids, and records any faces that become redundant in the provided discarded array.
      Parameters:
      hedgeAdj - the half-edge along which to merge with the adjacent face
      discarded - an output array to collect faces that are deleted by the merge
      Returns:
      the number of faces recorded in discarded (0, 1, or 2)

    • numVertices

      public int numVertices()
      Returns the number of vertices (half-edges) bounding this face.
      Returns:
      the vertex count of this face

    • triangulate

      public void triangulate(FaceList newFaces, double minArea)
      Triangulates this (convex polygonal) face into a fan of triangles sharing the first vertex. Newly created faces are added to newFaces, and appropriate opposite links are established. Normals/centroids are updated using the given minArea for stability.
      Parameters:
      newFaces - list that collects newly created triangular faces
      minArea - minimum area threshold used when computing normals

    • areaSquared

      public double areaSquared(HalfEdge hedge0, HalfEdge hedge1)
      Computes the squared area of the triangle defined by hedge0 (tail->head) and the point at the head of hedge1. Useful for robust comparisons without taking a square root.
      Parameters:
      hedge0 - the reference half-edge whose tail and head form two triangle vertices
      hedge1 - a half-edge providing the third vertex via its head
      Returns:
      the squared area of the resulting triangle