Package WildMagic.LibGraphics.Detail
Class CreateClodMesh
- java.lang.Object
-
- WildMagic.LibGraphics.Detail.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
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description protected class
CreateClodMesh.EdgeAttribute
The attributes associated with an edge.private class
CreateClodMesh.HeapRecord
The representation of a heap element.class
CreateClodMesh.Triangle
A representation of a triangle for the vertex-edge-triangle table.protected class
CreateClodMesh.TriangleAttribute
The attributes associated with a triangle.class
CreateClodMesh.Vertex
A representation of a vertex for the vertex-edge-triangle table.protected class
CreateClodMesh.VertexAttribute
The attributes associated with a vertex.
-
Field Summary
Fields Modifier and Type Field Description private int[]
m_aiConnect
DOCUMENT ME!private int[]
m_aiIndex
DOCUMENT ME!private int[]
m_aiNewConnect
DOCUMENT ME!private int[]
m_aiVOrdered
DOCUMENT ME!private int[]
m_aiVPermute
DOCUMENT ME!private CreateClodMesh.HeapRecord[]
m_akHeap
DOCUMENT ME!private CollapseRecordArray
m_akRecord
the incremental changes representing the decimation.private boolean
m_bCollapsing
DOCUMENT ME!(package private) float
m_fAngleCutoff
Small angle cutoff for creating new triangles on an edge collapse.private int
m_iHQuantity
collapse support.private int
m_iTCurrent
DOCUMENT ME!private int
m_iTQuantity
DOCUMENT ME!private int
m_iVCurrent
for reordering vertices and triangles.private int
m_iVQuantity
triangle mesh to be decimated.private Vector3f
m_kCross
temporary variables to avoid 'new' calls.private Vector3f
m_kDiff
temporary variables to avoid 'new' calls.private Vector3f
m_kE0
temporary variables to avoid 'new' calls.private Vector3f
m_kE1
temporary variables to avoid 'new' calls.(package private) java.util.Vector<CollapseRecord>
m_kEDelete
DOCUMENT ME!protected java.util.HashMap<Edge,CreateClodMesh.EdgeAttribute>
m_kEMap
map of. private IndexBuffer
m_kIBuffer
DOCUMENT ME!private Vector3f
m_kN0
temporary variables to avoid 'new' calls.private Vector3f
m_kN1
temporary variables to avoid 'new' calls.private VertexBuffer
m_kNewVBuffer
DOCUMENT ME!protected java.util.HashMap<CreateClodMesh.Triangle,CreateClodMesh.TriangleAttribute>
m_kTMap
map of. private VertexBuffer
m_kVBuffer
DOCUMENT ME!(package private) java.util.HashSet<CreateClodMesh.Vertex>
m_kVDelete
DOCUMENT ME!protected java.util.HashMap<CreateClodMesh.Vertex,CreateClodMesh.VertexAttribute>
m_kVMap
map of. private static long
serialVersionUID
-
Constructor Summary
Constructors Constructor Description CreateClodMesh(VertexBuffer pkVBuffer, IndexBuffer pkIBuffer)
The decimator constructed by this method is designed to be reused, if necessary, for decimating multiple meshes.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description 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.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.private boolean
collapseCausesNormalsFlip(int iVThrow, int iVKeep, int iV1, int iV2)
Test for folding.private void
collapseEdge(int iVKeep, int iVThrow)
The internal edge collapse function.private float
compareNormalsAcrossTriangles(int iV1, int iV2)
Metric for determining the weight of the edge defined between vertices iV1->iV2.private void
computeRecords()
All collapse information is known when this is called.void
decimate()
A triangle decimator for a triangle mesh.private void
doCollapse()
The top-level edge collapse operation.private void
flushTriangles()
When all edges have infinite weight, no further edge collapses are allowed.private void
flushVertices()
When all edges have infinite weight, no further edge collapses are allowed.void
getConsistentComponents()
Construct the connected components of the mesh.java.lang.Object
getData(CreateClodMesh.Triangle kT)
Get the attribute data associated with the specified triangle.private float
getMetric(Edge kE, CreateClodMesh.EdgeAttribute kEAttr)
Computes the weight associated with an edge.private Vector3f
getNormal(CreateClodMesh.Triangle kT)
CollapseRecordArray
getRecords()
The collapse records that have been created by the constructor for ModelSurfaceDecimator.private void
initializeHeap()
Allocate the heap and initialize all the heap elements.void
insertTriangle(int iV0, int iV1, int iV2)
Insert triangleinto the mesh. void
insertTriangle(CreateClodMesh.Triangle kT)
Convenience function for inserting triangles into the mesh.private void
modifyTriangle(CreateClodMesh.Triangle kT, int iVKeep, int iVThrow)
When an edge is collapsed, all triangles sharing the edge have been removed.void
OnEdgeInsert(Edge kE, boolean bCreate, CreateClodMesh.EdgeAttribute kEAttr)
An override of the base class ModelSurfaceTopology member function.void
OnEdgeRemove(Edge kE, boolean bDestroy, CreateClodMesh.EdgeAttribute kEAttr)
An override of the base class ModelSurfaceTopology member function.void
OnTriangleInsert(CreateClodMesh.Triangle kT, boolean bCreate, CreateClodMesh.TriangleAttribute kTAttr)
An override of the base class ModelSurfaceTopology member function.void
OnTriangleRemove(CreateClodMesh.Triangle kT, boolean bDestroy, CreateClodMesh.TriangleAttribute kTAttr)
An override of the base class ModelSurfaceTopology member function.void
OnVertexInsert(CreateClodMesh.Vertex kV, boolean bCreate, CreateClodMesh.VertexAttribute kVAttr)
An override of the base class ModelSurfaceTopology member function.void
OnVertexRemove(CreateClodMesh.Vertex kV, boolean bDestroy, CreateClodMesh.VertexAttribute kVAttr)
An override of the base class ModelSurfaceTopology member function.private void
remove()
The only remove operation from a heap occurs at the root of the heap.void
removeTriangle(int iV0, int iV1, int iV2)
Remove trianglefrom the mesh. void
removeTriangle(CreateClodMesh.Triangle kT)
An override of the ModelSurfaceTopology member function.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.void
setData(CreateClodMesh.Triangle kT, java.lang.Object kData)
Set the attribute data associated with the specified triangle.private void
sort()
After the heap is initialized, it must be sorted.void
superRemoveTriangle(CreateClodMesh.Triangle kT)
Convenience function for removing triangles from the mesh.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.
-
-
-
Field Detail
-
serialVersionUID
private static final long serialVersionUID
- See Also:
- Constant Field Values
-
m_kEMap
protected java.util.HashMap<Edge,CreateClodMesh.EdgeAttribute> m_kEMap
map of.
-
m_kTMap
protected java.util.HashMap<CreateClodMesh.Triangle,CreateClodMesh.TriangleAttribute> m_kTMap
map of.
-
m_kVMap
protected java.util.HashMap<CreateClodMesh.Vertex,CreateClodMesh.VertexAttribute> m_kVMap
map of.
-
m_kEDelete
java.util.Vector<CollapseRecord> m_kEDelete
DOCUMENT ME!
-
m_kVDelete
java.util.HashSet<CreateClodMesh.Vertex> m_kVDelete
DOCUMENT ME!
-
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_akHeap
private CreateClodMesh.HeapRecord[] m_akHeap
DOCUMENT ME!
-
m_kNewVBuffer
private VertexBuffer m_kNewVBuffer
DOCUMENT ME!
-
m_akRecord
private CollapseRecordArray m_akRecord
the incremental changes representing the decimation.
-
m_kVBuffer
private VertexBuffer m_kVBuffer
DOCUMENT ME!
-
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 objectpkIBuffer
- 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 triangleinto the mesh. The ordering of the indices is relevant. Triangle is considered to be a different triangle (reversed ordering from ). - Parameters:
iV0
- index of triangleiV1
- index of triangleiV2
- 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 mapbCreate
- 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 mapbDestroy
- 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 mapbCreate
- 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 mapbDestroy
- 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 mapbCreate
- 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 mapbDestroy
- 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 trianglefrom the mesh. The ordering of the indices is relevant. Triangle is considered to be a different triangle (reversed ordering from ). - Parameters:
iV0
- index of triangleiV1
- index of triangleiV2
- 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 setkData
- 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 collapseiVThrow
- 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 removeiVKeep
- the index of the triangle vertex that replaces iVThrowiV1
- 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 collapseiVThrow
- 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 edgeiV2
- 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 weightedkEAttr
- the attribute associated with the edge- Returns:
- the new weight of the edge
-
getNormal
private Vector3f getNormal(CreateClodMesh.Triangle kT)
-
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 modifyiVKeep
- the vertex to keep in the edge collapseiVThrow
- 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
-
-