org.jcae.mesh.amibe.ds
Class Mesh

java.lang.Object
  org.jcae.mesh.amibe.ds.Mesh

All Implemented Interfaces:

java.io.Serializable

Direct Known Subclasses:

Mesh2D

public class Mesh
extends java.lang.Object
implements java.io.Serializable

Mesh data structure. 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, three links to adjacent triangles, and each vertex contains a backward link to one of its incident triangles. It is then possible to loop within triangles or around vertices. But there is also a need for lighter data structures. For instance, visualization does not need adjacency relations, we only need to store triangle vertices. 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(...);
 

See Also:

Serialized Form

Field Summary

protected ElementFactoryInterface	factory
protected int	maxLabel
protected MeshParameters	meshParameters User-defined mesh parameters.
protected boolean	outerTrianglesAreConnected
Vertex	outerVertex Vertex at infinite.
protected Traits	traits User-defined traits
protected MeshTraitsBuilder	traitsBuilder User-defined traits builder.

Constructor Summary

Mesh()
Creates an empty mesh.

Mesh(MeshTraitsBuilder builder)

Mesh(MeshTraitsBuilder builder, MeshParameters mp)
Creates an empty mesh with specific features.

Method Summary

void	add(Triangle t) Adds an existing triangle to triangle list.
void	add(Vertex vertex) Adds a vertex to vertex list.
void	buildAdjacency() Build adjacency relations between triangles.
void	buildAdjacency(double minAngle) Build adjacency relations between triangles.
boolean	canCollapseEdge(AbstractHalfEdge e, Vertex v) Checks whether an edge can be contracted.
Triangle	createTetrahedron(Vertex[] v) Creates a triangle composed of four vertices, to emulate a tetrahedron.
Triangle	createTriangle(Triangle that) Clones a triangle.
Triangle	createTriangle(Vertex[] v) Creates a triangle composed of three vertices.
Triangle	createTriangle(Vertex v0, Vertex v1, Vertex v2) Creates a triangle composed of three vertices.
Vertex	createVertex(double[] p) Creates a 2D or 3D vertex.
Vertex	createVertex(double u, double v) Creates a 2D vertex.
Vertex	createVertex(double x, double y, double z) Creates a 3D vertex.
double	distance2(Vertex start, Vertex end, Vertex vm) Returns square distance between 2 vertices.
AbstractHalfEdge	edgeCollapse(AbstractHalfEdge e, Vertex v) Contracts an edge.
AbstractHalfEdge	edgeSwap(AbstractHalfEdge e) Swaps an edge.
void	ensureCapacity(int triangles) Resizes internal collections of vertices and triangles.
double[]	getBounds(Vertex v)
KdTree	getKdTree() Returns the Kd-tree associated with this mesh.
MeshParameters	getMeshParameters()
java.util.Collection<Vertex>	getNodes() Returns vertex list.
java.util.Collection<Triangle>	getTriangles() Returns triangle list.
boolean	hasAdjacency() Tells whether mesh contains adjacency relations.
boolean	hasNodes() Tells whether nodes are stored.
boolean	isValid() Checks whether this mesh is valid.
boolean	isValid(boolean constrained) Checks whether this mesh is valid.
void	remove(Triangle t) Removes a triangle from triangle list.
void	remove(Vertex v) Removes a vertex from vertex list.
void	resetKdTree(double[] bbmin, double[] bbmax) Initializes Kd-tree with a given bounding box.
void	setRefVertexOnboundary(Vertex v) Sets an unused boundary reference on a vertex.
AbstractHalfEdge	vertexSplit(AbstractHalfEdge e, Vertex v) Splits an edge.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

traitsBuilder

protected final MeshTraitsBuilder traitsBuilder

User-defined traits builder.

traits

protected final Traits traits

User-defined traits

meshParameters

protected final MeshParameters meshParameters

User-defined mesh parameters.

outerVertex

public Vertex outerVertex

Vertex at infinite.

factory

protected ElementFactoryInterface factory

outerTrianglesAreConnected

protected boolean outerTrianglesAreConnected

maxLabel

protected int maxLabel

Constructor Detail

Mesh

public Mesh()

Creates an empty mesh. When no MeshTraitsBuilder is passed, MeshTraitsBuilder.getDefault3D() is called implicitly.

Mesh

public Mesh(MeshTraitsBuilder builder)

Mesh

public Mesh(MeshTraitsBuilder builder,
            MeshParameters mp)

Creates an empty mesh with specific features.

Parameters:

builder - mesh traits builder

Method Detail

getMeshParameters

public MeshParameters getMeshParameters()

add

public void add(Triangle t)

Adds an existing triangle to triangle list.

Parameters:

t - triangle being added.

remove

public void remove(Triangle t)

Removes a triangle from triangle list.

Parameters:

t - triangle being removed.

getTriangles

public java.util.Collection<Triangle> getTriangles()

Returns triangle list.

Returns:

triangle list.

ensureCapacity

public void ensureCapacity(int triangles)

Resizes internal collections of vertices and triangles.

Parameters:

triangles - desired number of triangles

add

public void add(Vertex vertex)

Adds a vertex to vertex list.

remove

public void remove(Vertex v)

Removes a vertex from vertex list.

Parameters:

v - vertex being removed.

getNodes

public java.util.Collection<Vertex> getNodes()

Returns vertex list.

Returns:

vertex list.

hasNodes

public boolean hasNodes()

Tells whether nodes are stored.

Returns:

true if mesh was created with a MeshTraitsBuilder instance defining nodes, and false otherwise.

getKdTree

public KdTree getKdTree()

Returns the Kd-tree associated with this mesh.

Returns:

the Kd-tree associated with this mesh.

resetKdTree

public void resetKdTree(double[] bbmin,
                        double[] bbmax)

Initializes Kd-tree with a given bounding box. This method must be called before putting any vertex into this Kd-tree.

Parameters:

bbmin - coordinates of bottom-left vertex

bbmax - coordinates of top-right vertex

createTriangle

public Triangle createTriangle(Vertex[] v)

Creates a triangle composed of three vertices.

Parameters:

v - array of three vertices

Returns:

a new Triangle instance composed of three vertices

createTetrahedron

public Triangle createTetrahedron(Vertex[] v)

Creates a triangle composed of four vertices, to emulate a tetrahedron.

Parameters:

v - array of four vertices

Returns:

a new Triangle instance composed of four vertices

createTriangle

public Triangle createTriangle(Vertex v0,
                               Vertex v1,
                               Vertex v2)

Creates a triangle composed of three vertices.

Parameters:

v0 - first vertex

v1 - second vertex

v2 - third vertex

Returns:

a new Triangle instance composed of three vertices

createTriangle

public Triangle createTriangle(Triangle that)

Clones a triangle.

Parameters:

that - triangle to clone

Returns:

a new Triangle instance

createVertex

public Vertex createVertex(double[] p)

Creates a 2D or 3D vertex.

Parameters:

p - coordinates

Returns:

a new Vertex instance with this location.

createVertex

public Vertex createVertex(double u,
                           double v)

Creates a 2D vertex.

Parameters:

u - first coordinate

v - second coordinate

Returns:

a new Vertex instance with this location.

createVertex

public Vertex createVertex(double x,
                           double y,
                           double z)

Creates a 3D vertex.

Parameters:

x - first coordinate

y - second coordinate

z - third coordinate

Returns:

a new Vertex instance with this location.

hasAdjacency

public boolean hasAdjacency()

Tells whether mesh contains adjacency relations.

Returns:

true if mesh contains adjacency relations, false otherwise.

buildAdjacency

public void buildAdjacency()

Build adjacency relations between triangles.

buildAdjacency

public void buildAdjacency(double minAngle)

Build adjacency relations between triangles.

Parameters:

minAngle - when an edge has a dihedral angle greater than this value, it is considered as a ridge and its endpoints are treated as if they belong to a CAD edge. By convention, a negative value means that this check is not performed.

setRefVertexOnboundary

public void setRefVertexOnboundary(Vertex v)

Sets an unused boundary reference on a vertex.

distance2

public double distance2(Vertex start,
                        Vertex end,
                        Vertex vm)

Returns square distance between 2 vertices.

getBounds

public double[] getBounds(Vertex v)

canCollapseEdge

public boolean canCollapseEdge(AbstractHalfEdge e,
                               Vertex v)

Checks whether an edge can be contracted.

Parameters:

e - edge to be checked

v - the resulting vertex

Returns:

true if this edge can be contracted into the single vertex n, false otherwise.

edgeCollapse

public AbstractHalfEdge edgeCollapse(AbstractHalfEdge e,
                                     Vertex v)

Contracts an edge.

Parameters:

e - edge to contract

v - the resulting vertex

Returns:

edge starting from n and with the same apex

Throws:

java.lang.IllegalArgumentException - if edge belongs to an outer triangle, because there would be no valid return value. User must then run this method against symmetric edge, this is not done automatically.

vertexSplit

public AbstractHalfEdge vertexSplit(AbstractHalfEdge e,
                                    Vertex v)

Splits an edge. This is the opposite of edgeCollapse(org.jcae.mesh.amibe.ds.AbstractHalfEdge, org.jcae.mesh.amibe.ds.Vertex).

Parameters:

e - edge being splitted

v - the resulting vertex

edgeSwap

public AbstractHalfEdge edgeSwap(AbstractHalfEdge e)

Swaps an edge.

Returns:

swapped edge, origin and apical vertices are the same as in original edge

Throws:

java.lang.IllegalArgumentException - if edge is on a boundary or belongs to an outer triangle.

isValid

public boolean isValid()

Checks whether this mesh is valid. This routine returns isValid(true).

See Also:

isValid(boolean)

isValid

public boolean isValid(boolean constrained)

Checks whether this mesh is valid. This routine can be called at any stage, even before boundary edges have been enforced. In this case, some tests must be removed because they do not make sense.

Parameters:

constrained - true if mesh is constrained.