Package org.jcae.mesh.amibe.ds

Mesh data structure.

See:
Description

Interface Summary

ElementFactoryInterface

Class Summary

AbstractHalfEdge	Abstract class to define common methods on edges.
ElementFactory
HalfEdge	Half-edge data structure.
MEdge1D	1D edge.
Mesh	Mesh data structure.
MeshParameters	Mesh parameters.
MGroup3D	Group of triangles in the 3D mesh.
MMesh0D	List of vertices of the whole shape.
MMesh1D	1D discretization of the whole shape.
MNode1D	1D node.
SubMesh1D	1D discretization of a single topological edge.
Triangle	A triangle containing adjacency relations.
Triangle.List	Singly linked list of triangles.
TriangleHE
TriangleVH	A triangular element of the mesh.
Vertex	Vertex of a mesh.
VirtualHalfEdge	A handle to abstract half-edge instances.

Package org.jcae.mesh.amibe.ds Description

Mesh data structure.

Introduction

A mesh is composed of triangles, edges and vertices. There are many data structures to represent meshes, and we focused on the following constraints:

• Memory usage must be minimal in order to perform very large meshes.
• Mesh traversal must be cheap.

We decided to implement a triangle-based data structure which is known to be more memory efficient. A Triangle is composed of three Vertex and three half-edges.

By convention, in each triangle, edge i is located at the opposite of vertex i. Each half-edge (red arrows) has a link (black arrows) to its symmetric edge, and each vertex contains a backward link to one of its incident triangles. It is then possible to loop within triangles or around vertices. Blue arrows show triangle orientation, by looping from vertex 0 to vertex 1 to vertex 2. Meshing operations ensure that symmetric edges have opposite directions, and thus that resultant mesh is well oriented. More details can be found in description of AbstractHalfEdge, and in particular how this scheme is extended to non-manifold meshes.

But there is also a need for lighter data structures. For instance, visualization does not need adjacency relations, we only need to store triangles.

Mesh constructor takes an optional MeshTraitsBuilder argument to fully describe the desired mesh data structure. Once a Mesh instance is created, its features cannot be modified. With this argument, it is possible to specify if adjacent relations between triangles have to be computed, if an octree is needed to locate vertices, if triangles and/or nodes are stored in a list or a set, etc. Example:

   MeshTraitsBuilder mtb = new MeshTraitsBuilder();
   // Store triangles into a set
   mtb.addTriangleSet();
   TriangleTraitsBuilder ttb = new TriangleTraitsBuilder();
   // Store adjacency relations with HalfEdge
   ttb.addHalfEdge();
   mtb.add(ttb);
   // Create a new instance with these features
   Mesh mesh = new Mesh(mtb);
   // Then each triangle created by mesh.createTriangle
   // will contain objects needed to store adjacency relations.
   Triangle t = (Triangle) mesh.createTriangle(...);
   // Vertices must be created by mesh.createVertex
   Vertex v = (Vertex) mesh.createVertex(...);

When a Mesh instance is created without specifying a MeshTraitsBuilder instance, MeshTraitsBuilder.getDefault3D() is implicitly used.

Adjacency relations

When adjacency relations are not requested by MeshTraitsBuilder, Mesh.createTriangle creates Triangle instances which only contains vertices and no other data.

Adjacency relations can be requested either with TriangleTraitsBuilder.addHalfEdge() or TriangleTraitsBuilder.addVirtualHalfEdge(). With the former, Mesh.createTriangle creates TriangleHE instances and adjacency operations are performed by an HalfEdge. With the latter, Mesh.createTriangle creates TriangleVH instances which directly store adjacency relations.

With TriangleHE

A TriangleHE instance contains a private HalfEdge instance, which represents an edge of underlying triangle. This edge is linked to the next edge in the same triangle; in fact Mesh.createTriangle creates three edges which are linked together to form a cycle, so a single reference is needed to access these three edges.

With TriangleVH

This is a more compact implementation (about 40% smaller) of adjacency relations: edges are not created as distinct objects, but taken as a local number (with values 0, 1 or 2) of a triangle.

A TriangleVH instance contains three links to adjacent TriangleVH instances, and TriangleVH.adjPos member is a packed representation of local numbers in adjacent triangles.

The downside is that edges are not physical objects but can be accessed only through handles. For instance, if edges have to be sorted in order to be processed in a certain order (as in QEMDecimateHalfEdge), TriangleHE must be used instead of TriangleVH.

Mesh traversal

For TriangleVH instances, VirtualHalfEdge are handles on edges. Both VirtualHalfEdge and HalfEdge inherits from AbstractHalfEdge, thus algorithms can be written without code duplication for both TriangleHE and TriangleVH instances if they only refer to AbstractHalfEdge and not their derived classes.