Package org.jcae.mesh.oemm

Octree-based External Memory Mesh P.

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.

Package org.jcae.mesh.oemm Description

Octree-based External Memory Mesh

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 out-of-core 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.

Building an OEMM

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.

Determination of the octree structure

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

1. The total number of triangles is less than a given threshold
2. Neighbors in the final octree have a depth difference not greater than 2.

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 dmax must be chosen high enough in order to avoid this problem.

Dispatching triangles into octants

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.

Indexing vertices and triangles

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.

Indexing internal vertices

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.

Indexing external 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).

Examples

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