Class CreateClodMesh

  • All Implemented Interfaces:
    java.io.Serializable

    public class CreateClodMesh
    extends java.lang.Object
    implements java.io.Serializable
    A triangle decimator that is used for continuous level of detail of a triangle mesh. The algorithm is based on edge collapses of the mesh. A detailed discussion of the algorithm is found in Level Set Extraction
    See Also:
    Serialized Form
    • Field Detail

      • m_aiConnect

        private int[] m_aiConnect
        DOCUMENT ME!
      • m_aiIndex

        private int[] m_aiIndex
        DOCUMENT ME!
      • m_aiNewConnect

        private int[] m_aiNewConnect
        DOCUMENT ME!
      • m_aiVOrdered

        private int[] m_aiVOrdered
        DOCUMENT ME!
      • m_aiVPermute

        private int[] m_aiVPermute
        DOCUMENT ME!
      • m_kNewVBuffer

        private VertexBuffer m_kNewVBuffer
        DOCUMENT ME!
      • m_akRecord

        private CollapseRecordArray m_akRecord
        the incremental changes representing the decimation.
      • m_kIBuffer

        private IndexBuffer m_kIBuffer
        DOCUMENT ME!
      • m_bCollapsing

        private boolean m_bCollapsing
        DOCUMENT ME!
      • m_iHQuantity

        private int m_iHQuantity
        collapse support.
      • m_iTCurrent

        private int m_iTCurrent
        DOCUMENT ME!
      • m_iTQuantity

        private int m_iTQuantity
        DOCUMENT ME!
      • m_iVCurrent

        private int m_iVCurrent
        for reordering vertices and triangles.
      • m_iVQuantity

        private int m_iVQuantity
        triangle mesh to be decimated.
      • m_kE0

        private Vector3f m_kE0
        temporary variables to avoid 'new' calls.
      • m_kE1

        private Vector3f m_kE1
        temporary variables to avoid 'new' calls.
      • m_kN0

        private Vector3f m_kN0
        temporary variables to avoid 'new' calls.
      • m_kN1

        private Vector3f m_kN1
        temporary variables to avoid 'new' calls.
      • m_kCross

        private Vector3f m_kCross
        temporary variables to avoid 'new' calls.
      • m_kDiff

        private Vector3f m_kDiff
        temporary variables to avoid 'new' calls.
      • m_fAngleCutoff

        float m_fAngleCutoff
        Small angle cutoff for creating new triangles on an edge collapse.
    • Constructor Detail

      • CreateClodMesh

        public CreateClodMesh​(VertexBuffer pkVBuffer,
                              IndexBuffer pkIBuffer)
        The decimator constructed by this method is designed to be reused, if necessary, for decimating multiple meshes. If used this way, the input parameters measure the maximum quantities over all the meshes.
        Parameters:
        pkVBuffer - the maximum number of vertices for all meshes to be decimated by this object
        pkIBuffer - the maximum number of triangles for all meshes to be decimated by this object
    • Method Detail

      • decimate

        public void decimate()
        A triangle decimator for a triangle mesh. After decimation, the vertex and triangle connectivity arrays have been reordered and should be used as input in creating an ModelClodMesh object. The collapse records constructed in this function can be accessed via getRecords(). TODO explain: akVertex array of vertices in the mesh aiConnect Connectivity array for the triangles. Each triple of indices represents one triangle. The triangle is counterclockwise ordered as viewed by an observer outside the mesh.
      • getConsistentComponents

        public void getConsistentComponents()
        Construct the connected components of the mesh. The triangle ordering within a single component is guaranteed to be consistent. That is, all triangles in the component are counterclockwise ordered, or all are clockwise ordered. It is not possible to make ordering between two components consistent since this requires geometric information about how the components are placed in space relative to each other (requires specification of an eye point). TODO explain: return an array of components (triangles), each entry of type ModelSurfaceTopology
      • getData

        public java.lang.Object getData​(CreateClodMesh.Triangle kT)
        Get the attribute data associated with the specified triangle.
        Parameters:
        kT - the triangle whose attribute data will be retrieved
        Returns:
        the attribute data
      • getRecords

        public CollapseRecordArray getRecords()
        The collapse records that have been created by the constructor for ModelSurfaceDecimator. After construction, the application uses the vertex and triangle connectivity arrays that were passed to the constructor (arrays are now reordered) and should call this function to access the collapse records. All three data structures are then used to create an ModelClodMesh object.
        Returns:
        the array of collapse records for the decimation
      • insertTriangle

        public void insertTriangle​(int iV0,
                                   int iV1,
                                   int iV2)
        Insert triangle into the mesh. The ordering of the indices is relevant. Triangle is considered to be a different triangle (reversed ordering from ).
        Parameters:
        iV0 - index of triangle
        iV1 - index of triangle
        iV2 - index of triangle
      • insertTriangle

        public void insertTriangle​(CreateClodMesh.Triangle kT)
        Convenience function for inserting triangles into the mesh.
        Parameters:
        kT - the triangle to be inserted
      • OnEdgeInsert

        public void OnEdgeInsert​(Edge kE,
                                 boolean bCreate,
                                 CreateClodMesh.EdgeAttribute kEAttr)
        An override of the base class ModelSurfaceTopology member function. This callback is used to keep track of heap changes due to edge collapses.
        Parameters:
        kE - the edge that was attempted to be inserted into the map
        bCreate - true if the edge did not exist in the map before insertion (it is a brand new edge), false if the edge already existed.
        kEAttr - the attribute for the edge
      • OnEdgeRemove

        public void OnEdgeRemove​(Edge kE,
                                 boolean bDestroy,
                                 CreateClodMesh.EdgeAttribute kEAttr)
        An override of the base class ModelSurfaceTopology member function. This callback is used to keep track of heap changes due to edge collapses.
        Parameters:
        kE - the edge that was attempted to be removed from the map
        bDestroy - true if the edge did exist in the map before the attempted removal and no other mesh components are referencing the edge, false if the edge does exist in the map, but other mesh components are referencing it.
        kEAttr - the attribute for the edge
      • OnTriangleInsert

        public void OnTriangleInsert​(CreateClodMesh.Triangle kT,
                                     boolean bCreate,
                                     CreateClodMesh.TriangleAttribute kTAttr)
        An override of the base class ModelSurfaceTopology member function. This callback is used to assign integer indices to triangles in the mesh.
        Parameters:
        kT - the triangle that was attempted to be inserted into the map
        bCreate - true if the triangle did not exist in the map before insertion (it is a brand new triangle), false if the triangle already existed.
        kTAttr - the attribute for the triangle
      • OnTriangleRemove

        public void OnTriangleRemove​(CreateClodMesh.Triangle kT,
                                     boolean bDestroy,
                                     CreateClodMesh.TriangleAttribute kTAttr)
        An override of the base class ModelSurfaceTopology member function. This callback is used to assign integer indices to triangles in the mesh.
        Parameters:
        kT - the triangle that was attempted to be removed from the map
        bDestroy - true if the triangle did exist in the map before the attempted removal and no other mesh components are referencing the triangle, false if the triangle does exist in the map, but other mesh components are referencing it.
        kTAttr - the attribute for the triangle
      • OnVertexInsert

        public void OnVertexInsert​(CreateClodMesh.Vertex kV,
                                   boolean bCreate,
                                   CreateClodMesh.VertexAttribute kVAttr)
        An override of the base class ModelSurfaceTopology member function. This callback is used to keep track of vertices deleted during an edge collapse.
        Parameters:
        kV - the vertex that was attempted to be inserted into the map
        bCreate - true if the vertex did not exist in the map before insertion (it is a brand new vertex), false if the vertex already existed.
        kVAttr - the attribute for the vertex
      • OnVertexRemove

        public void OnVertexRemove​(CreateClodMesh.Vertex kV,
                                   boolean bDestroy,
                                   CreateClodMesh.VertexAttribute kVAttr)
        An override of the base class ModelSurfaceTopology member function. This callback is used to keep track of vertices deleted during an edge collapse.
        Parameters:
        kV - the vertex that was attempted to be removed from the map
        bDestroy - true if the vertex did exist in the map before the attempted removal and no other mesh components are referencing the vertex, false if the vertex does exist in the map, but other mesh components are referencing it.
        kVAttr - the attribute for the vertex
      • removeTriangle

        public void removeTriangle​(int iV0,
                                   int iV1,
                                   int iV2)
        Remove triangle from the mesh. The ordering of the indices is relevant. Triangle is considered to be a different triangle (reversed ordering from ).
        Parameters:
        iV0 - index of triangle
        iV1 - index of triangle
        iV2 - index of triangle
      • removeTriangle

        public void removeTriangle​(CreateClodMesh.Triangle kT)
        An override of the ModelSurfaceTopology member function. This function keeps track of the order of triangle removal to support reordering of the connectivity array. Once done, then the base class function is called to remove the triangle from the mesh.
        Parameters:
        kT - the triangle to be removed
      • setData

        public void setData​(CreateClodMesh.Triangle kT,
                            java.lang.Object kData)
        Set the attribute data associated with the specified triangle.
        Parameters:
        kT - the triangle whose attribute data will be set
        kData - the attribute data
      • superRemoveTriangle

        public void superRemoveTriangle​(CreateClodMesh.Triangle kT)
        Convenience function for removing triangles from the mesh.
        Parameters:
        kT - the triangle to be removed
      • add

        private void add​(float fMetric)
        New edges that occur because of modified triangles being added to the mesh must be added to the heap and the heap must be updated. This is an O(log N) process for N edges.
        Parameters:
        fMetric - The new edge weight to be added to the heap. The other heap element information was set up by the OnEdgeInsert callback.
      • collapseCausesFolding

        private boolean collapseCausesFolding​(int iVKeep,
                                              int iVThrow)
        A look-ahead test to determine if the requested edge collapse will cause the mesh to fold over itself.
        Parameters:
        iVKeep - the vertex to keep in the edge collapse
        iVThrow - the vertex to be thrown away in the edge collapse
        Returns:
        true iff the edge collapse will cause the mesh to fold over
      • collapseCausesNormalsFlip

        private boolean collapseCausesNormalsFlip​(int iVThrow,
                                                  int iVKeep,
                                                  int iV1,
                                                  int iV2)
        Test for folding. If the new triangle that is created by collapsing an edge (iVKeep, iV1, iV2) has a normal that points in the opposite direction from the original triangle (iVThrow, iV1, iV2) then do not collapse the edge that causes the triangle to flip.
        Parameters:
        iVThrow - the index of the triangle vertex to remove
        iVKeep - the index of the triangle vertex that replaces iVThrow
        iV1 - iV2 the other indices of the triangle.
        Returns:
        true if the triangle flips normals, false otherwise.
      • collapseEdge

        private void collapseEdge​(int iVKeep,
                                  int iVThrow)
        The internal edge collapse function. This is called as long as the suggested edge does not cause folding.
        Parameters:
        iVKeep - the vertex to keep in the edge collapse
        iVThrow - the vertex to be thrown away in the edge collapse
      • compareNormalsAcrossTriangles

        private float compareNormalsAcrossTriangles​(int iV1,
                                                    int iV2)
        Metric for determining the weight of the edge defined between vertices iV1->iV2. Creates a list of triangles that are adjacent to vertex iV1 and a list of triangles adjacent to iV2, excluding the triangles that contain both iV1 iV2. The triangle normals of the two lists are compared and the greatest angle is returned. This decreases the likelihood of edge collapses along high-curvature portions of the mesh and increases the likelihood of collapse along flat portions of the mesh.
        Parameters:
        iV1 - first vertex index of edge
        iV2 - second vertex index of edge
        Returns:
        maximum angle difference between triangles attached to iV1 versus iV2.
      • computeRecords

        private void computeRecords()
        All collapse information is known when this is called. What remains to be done is to determine which indices in the triangle connectivity must be changed when a collapse record is applied to the mesh. This is done to make the index changes fast in the application. Without the look-up tables in the collapse record, the application would have to constantly search the connectivity array and do the work in the current function every time level of detail is changed.
      • doCollapse

        private void doCollapse()
        The top-level edge collapse operation.
      • flushTriangles

        private void flushTriangles()
        When all edges have infinite weight, no further edge collapses are allowed. At this point the remaining triangles in the map are written to the reordering array and the edge collapse process is finished.
      • flushVertices

        private void flushVertices()
        When all edges have infinite weight, no further edge collapses are allowed. At this point the remaining vertices in the map are written to the reordering/permutation arrays and the edge collapse process is finished.
      • getMetric

        private float getMetric​(Edge kE,
                                CreateClodMesh.EdgeAttribute kEAttr)
        Computes the weight associated with an edge. The weight is based on the length of the edge, the area of the adjacent triangles, and the angle between the triangles. The smaller any of these quantites are, the more likely the edge should be removed. That is, attempt to collapse short edges whose triangles have small area and are nearly coplanar. Only manifold edges have finite weight. Other edges are assigned infinite weight to preserve topology of the mesh (boundary edges and junction edges should not be collapsed).
        Parameters:
        kE - the edge to be weighted
        kEAttr - the attribute associated with the edge
        Returns:
        the new weight of the edge
      • initializeHeap

        private void initializeHeap()
        Allocate the heap and initialize all the heap elements. This is an O(N) process for N edges.
      • modifyTriangle

        private void modifyTriangle​(CreateClodMesh.Triangle kT,
                                    int iVKeep,
                                    int iVThrow)
        When an edge is collapsed, all triangles sharing the edge have been removed. All remaining triangles that contain VThrow as a vertex must have VThrow replaced by VKeep. The old triangles are removed from the mesh and the modified triangles are inserted.
        Parameters:
        kT - the triangle to modify
        iVKeep - the vertex to keep in the edge collapse
        iVThrow - the vertex to be thrown away in the edge collapse
      • remove

        private void remove()
        The only remove operation from a heap occurs at the root of the heap. Once removed, the heap must be updated. This is an O(log N) process for N edges.
      • reorder

        private void reorder()
        After edge collapses are finished, the actual vertex locations, the triangle connectivity array, and the collapse record information must be reordered to support fast dynamic change in level of detail.
      • sort

        private void sort()
        After the heap is initialized, it must be sorted. This is an O(N log N) process for N edges.
      • update

        private void update​(int iHIndex,
                            float fMetric)
        If an edge weight changes for an edge whose heap element is interior to the heap tree, the heap must be updated. This is an O(log N) process for N edges.
        Parameters:
        iHIndex - the index of the heap element corresponding to the modified edge (the heap is a binary tree but is stored in an array)
        fMetric - the modified edge weight