|PREV PACKAGE NEXT PACKAGE||FRAMES NO FRAMES|
|Aggregate||Merge adjacent octree nodes.|
|MeshReader||This class builds a mesh from disk.|
|OEMM||This class represents an empty OEMM.|
|OEMM.Node||This class represents octants of an OEMM.|
|PAVLTreeIntArrayDup||Implementation of PAVL binary trees to store locational codes.|
|RawStorage||Convert a triangle soup into an OEMM data structure.|
|Storage||This class converts between disk and memory formats.|
|TraversalProcedure||Abstract class to implement OEMM traversal.|
P. Cignoni, C. Montani, C. Rocchini and R. Scopigno described in their paper
Memory Management and Simplification of Huge Meshes
a data structure for out-of-core processing of huge meshes (also called
Octree based External Memory Mesh, or OEMM). The
package is a Java implementation of these ideas. Algorithms to build and
use this data structure are detailed below.
An OEMM structure is designed to handle very large meshes.
We cannot work with indexed triangles because storing
indices in memory would require lots of RAM. For this reason, our
starting point is a triangle soup, which consists of a sequence of
triangles, each triangle being represented by the coordinates of
its three vertices and predefined attributes.
This triangle soup had been computed for instance by running
Mesher and setting
OEMM is first created with a given
dmax, and its bounding box is set. This is needed to transform
double coordinates into integers (and also the other way around), see
OEMM.double2int(double, int) and
The triangle soup is read a first time by
RawStorage.countTriangles(org.jcae.mesh.oemm.OEMM, java.lang.String); for each triangle,
vertices are located in the smallest octant (i.e. with the depth
specified when creating this octree), and a counter is
incremented for all octants containing at least one vertex. At the end
of this first pass, we know how many triangles will be collected by each
An optimization is then performed by
Aggregate.compute(org.jcae.mesh.oemm.OEMM, int) on this
OEMM structure: octants are recursively
merged with their siblings if
The optimized octree has fewer leaves than the original, and the number
of neighbors is bounded by a small constant. This property is important
so that loading a node and all its neighbors can be performed in constant
time. It is also important to understand that there will be trouble if
an edge is so long that its vertices belong to non-adjacent leaves.
At the moment, this situation is not detected, so
be chosen high enough in order to avoid this problem.
Triangles can then be gathered by octants in
RawStorage.dispatch(org.jcae.mesh.oemm.OEMM, java.lang.String, java.lang.String, java.lang.String).
The previous step counted the number of triangles which will be assigned
to each octant. so dispatched file offset for each octant can be computed,
Triangles are read a second time from the triangle soup and copied into
the right block. This dispatched file is similar to the triangle soup,
but triangles have been sorted by octant.
In each octant, triangle soup is replaced by an indexed mesh, and
connections to adjacent octants are kept. This is performed by
RawStorage.indexOEMM(java.lang.String, java.lang.String) in two steps.
The final data structure for each octant is composed of its interior
vertices and a list of indexed triangles. A preorder traversal of
the octree is performed, and vertices are read from the dispatched
file. As triangles have been rearranged by octants, a global index
can be assigned so that all indices of the first leaf are lower than
those of the second leaf, etc. Or in other words, each leaf has an
index range which has been already computed, and global indices are
equal to the sum of the minimal index
OEMM.Node.minIndex and a local index.
The task performed during this traversal is thus to identify unique
interior vertices. This is done by using
PAVLTreeIntArrayDup class, which is an
implementation of AVL trees based on Ben Pfaff's
For each leaf, a list of neighbor leaves was computed during the initial step. The maximal depth difference between neighbor leaves is 2, so a leaf has at most 6*16+12*4+8=152 neighbors, and information about neighbors for vertices can be packed in a byte array. If a triangle contains interior and outer vertices, outer ones are located inside those neighbor leaves, and the index within this list is associated with interior vertices.
The dispatched file is read another time to build a list of indexed triangles. For each octant, interior vertices for itself and all its neighbors are loaded into memory. Triangles are then read again from the dispatched file, and vertices are replaced by their global index (or more precisely by its leaf and local indices).
Creation of a triangle soup:
java -Dorg.jcae.mesh.Mesher.triangleSoup=true org.jcae.mesh.Mesher hammer.brep RAW 10 0
Transformation of a triangle soup (found in file
RAW/soup) into an
OEMM data structure, stored into directory
oemm, with maximal depth
set to 5 and at most 1000 triangles by octant:
java org.jcae.mesh.MeshOEMMIndex RAW oemm 5 1000
Visualization of an OEMM:
java org.jcae.mesh.MeshOEMMViewer3d oemm
|PREV PACKAGE NEXT PACKAGE||FRAMES NO FRAMES|