

PREV PACKAGE NEXT PACKAGE  FRAMES NO FRAMES 
See:
Description
Interface Summary  

RawStorage.SoupReaderInterface 
Class Summary  

Aggregate  Merge adjacent octree nodes. 
FakeNonReadVertex  
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
External
Memory Management and Simplification of Huge Meshes
a data structure for outofcore processing of huge meshes (also called
Octree based External Memory Mesh, or OEMM). The org.jcae.mesh.oemm
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 org.jcae.mesh.Mesher.triangleSoup
property to true
.
An empty OEMM
is first created with a given
maximal depth 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
OEMM.int2double(int[], double[])
.
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
octant.
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 nonadjacent leaves.
At the moment, this situation is not detected, so dmax
must
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
GNU libavl.
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 