org.jcae.mesh.amibe.ds
Class AbstractHalfEdge

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

Direct Known Subclasses:

HalfEdge, VirtualHalfEdge

public abstract class AbstractHalfEdge
extends java.lang.Object

Abstract class to define common methods on edges. We use an half-edge data structure to perform mesh traversal. An half-edge (red arrows) contains a link (black arrows) to its symmetric half-edge, a link to the next half-edge in the same triangle, a link to its underlying triangle and a local number within this triangle. A triangle contains an array of three vertices; by convention, in each triangle, edge i is located at the opposite of vertex i. Thus even if half-edges have no links to vertices, they can be easily found; suppose that half-edge e has local number l in triangle tri:

• e.origin() is tri.vertex[(l+1)%3]
• e.destination() is tri.vertex[(l-1)%3]
• e.apex() is tri.vertex[l]

For an half-edge e, e.sym() returns its symmetric half-edge, if it does exist. In this case, e.sym().sym() is always e, and in images below a link between symmetric half-edges is represented by a single double-headed arrow instead of two arrows. Moreover, symmetric edges must have opposite directions (except for non-manifold edges), or in other words

• e.origin() == e.sym().destination()
• e.destination() == e.sym().origin()

Image below shows two triangles which cannot be linked together because their common edge has the same direction in both triangles.

Geometrical primitives

Consider AbstractHalfEdge edge e between vertices A and B, starting from A, in image below:

The following methods can be applied to e:

• e.next() and e.prev() get respectively next and previous edges in the same triangle (ABC) in a counterclockwise cycle.
• e.sym() gets the opposite AbstractHalfEdge, in triangle (BAF).
• e.nextOrigin() returns next edge starting from the same origin A when cycling counterclockwise around A.

Warning: As VirtualHalfEdge instances are handles to edges and not physical objects, these methods modify current instance. Another set of methods is defined to apply these transformations to another instance, so that current instance is not modified.

• e.next(f) (resp. e.prev(f)) moves f to next (resp. previous) edge in the same triangle (ABC) in a counterclockwise cycle.
• e.sym(f) moves f to opposite of e.
• e.nextOrigin(f) moves f to next edge starting from the same origin A when cycling counterclockwise around A.

For convenience, derived classes may also define the following methods, which are combinations of previous ones:

• e.prevOrigin() moves counterclockwise to the previous edge starting from the same origin.
• e.nextDest() (resp. e.prevDest()) moves counterclockwise to next (resp. previous) edge with the same destination vertex B.
• e.nextApex() (resp. e.prevApex()) moves counterclockwise to next (resp. previous) edge with the same apical vertex C.

Mesh Operations

These operations are abstract methods and are implemented by derived classes:

swap

Swaps an edge. Return value has the same original and apical vertices as original edge. Triangles and edges are modified, objects are not destroyed and inserted into mesh.

split

Splits a vertex to create a new edge. In figure below, A is duplicated into N, and two new triangles are created. Return value has the same original and apical vertices as original edge, and its destination vertex is N.

Warning: This method does not check that new triangles are not inverted.

collapse

Collapses an edge into a new point. Triangles, edges and vertices are removed from mesh and replaced by new objects. New point may be origin or destination points, or a new point. Return value has the new point as its origin, and its apex is the same as in original edge. When N is A, collapse is the opposite of split.

Warning: This method does not check that triangles are not inverted. Method canCollapse must have been called to ensure that this edge collapse is possible, otherwise errors may occur. This method is not called automatically because it is sometimes costful.

Return values have been chosen so that these methods always return an edge which has the same apical vertex. As will be explained below, they gracefully work with boundaries and non-manifold meshes.

These two methods may also be of interest when writing new algorithms:

canCollapse

Tells whether an edge can be collapsed and replaced by the given vertex.

checkNewRingNormals

Tells whether triangles become inverted if origin point is moved at given location.

Boundaries

In order to simplify mesh operations, outer triangles are added to opposite side of free edges, by linking vertices on boundary to a special vertex Mesh.outerVertex which represents a point at infinite. With this convention, all mesh edges have a symmetric edge. On the other hand, all edges which have Mesh.outerVertex as an endpoint have no symmetric edges, so in these special triangles, there is only one edge with a symmetric edge.

All AbstractHalfEdge derived classes allow to set attributes on edges. They are defined as bitwise OR values, these values are useful:

AbstractHalfEdge.BOUNDARY

This edge is on a mesh boundary (either part of an outer triangle or of a regular triangle)

AbstractHalfEdge.OUTER

This edge is part of an outer triangle

AbstractHalfEdge.NONMANIFOLD

This edge is not manifold (see below)

Other values, namely AbstractHalfEdge.MARKED, AbstractHalfEdge.SWAPPED and AbstractHalfEdge.QUAD may be removed in future releases, please do not use them.

For instance, image below is an excerpt of previous image into which edge attributes are displayed: O represents AbstractHalfEdge.OUTER attribute, B represents AbstractHalfEdge.BOUNDARY and | means that attributes are combined.

Attributes are handled by these methods:

setAttributes(int)

Combines edge attribute with method argument.

clearAttributes(int)

Combines edge attribute with 2-complement of method argument, which means that attributes passed as argument are reset.

hasAttributes(int)

Checks whether edge attribute contains any of attributes passed as method argument.

With these outer triangles, we can also loop around vertices even on mesh boundaries. The nextOriginLoop() method behaves like nextOrigin() when edge is not outer, and when it is outer, it turns clockwise until boundary is reached. For instance on image below, a.nextOriginLoop() returns b, b.nextOriginLoop() returns o, o.nextOriginLoop() returns d and d.nextOriginLoop() returns a.

With nextOriginLoop, it is easy to loop around a vertex without having to care about boundaries; a canonical way to process all inner triangles by looping around edge origin is:

   Vertex d = e.destination();
   do
   {
     if (!e.hasAttributes(AbstractHalfEdge.OUTER))
     {
       Triangle t = e.getTri();
       // Do something with t
     }
     e = e.nextOriginLoop();
   }
   while (e.destination() != d);
 

Here is a more complete example to show how to process all neighbors of a manifold vertex:

   // This sample code only works with manifold vertices!
   Triangle t = (Triangle) o.getLink();
   AbstractHalfEdge e = t.getAbstractHalfEdge();
   if (e.destination() == o)
     e = e.next();
   else if (e.apex() == o)
     e = e.prev();
   // Now e is an edge starting from vertex o.
   Vertex d = e.destination();
   do
   {
     if (!e.hasAttributes(AbstractHalfEdge.OUTER)
         || e.hasAttributes(AbstractHalfEdge.BOUNDARY|AbstractHalfEdge.NONMANIFOLD))
     {
       Vertex v = e.destination();
       // Do something with v
     }
     e = e.nextOriginLoop();
   }
   while (e.destination() != d);
 

Non-manifold edges

A non-manifold edge is bound to more than two triangles. In image below, edges (AB), (BC) and (CD) belong to four triangles.

As with free edges, virtual triangles are added so that non-manifold edge has only one symmetric edge, and this time it is tagged with NONMANIFOLD attribute. Edge attributes are printed in blue for left shell:

We explained that the two outer edges are not connected to other triangles, so we have two free slots. We use these two slots to build a circular doubly-linked list to iterate over all half-edges connected together, as is done with radial-edge data structure. Here is an example, with an edge connected to three triangles; virtual triangles are represented by dashed lines.

All edges have only one symmetric edge. But adjacency relations between virtual triangles (represented by dotted arrows) are special, these half-edges are the only ones which do not necessarily satisfy these identities:

• e.origin() == e.sym().destination()
• e.destination() == e.sym().origin()

The fanIterator method returns an iterator over all edges connected to this one through such virtual triangles. By convention, this iterator returns half-edges which are not outer. In order to ease writing algorithms, this iterator is also defined on regular half-edges, and return only one value which is this half-edge.

How can we iterate over all neighbors of A? If we look again at sample code above, it is obvious that not all neighbors are caught. We could try to ask non-manifold edges to the rescue, it does not seem trivial. A simpler solution is to store a list of all triangles connected to each vertex, but it consumes lots of memory. We call triangle fan the set of triangles which are visited when calling nextOriginLoop() iteratively. If vertex is manifold, all neighbors are then reached. If not, we take another triangle which has not been visited yet, and repeat the same procedure until all neighbors have been reached. A good compromise is to take a single triangle by triangle fans, and they are stored into a triangle array because topology is usually not modified and number of triangle fans does not change. It is easy to modify sample code above, put it into a method taking a triangle as argument, call it with o.getLink() if it is a Triangle instance, otherwise loop over Triangle[] and call this method for each Triangle instance.

Consider the same mesh as above, from which triangles (ABE), (CDF) and their symmetric ones have been removed. Edges (AB) and (CD) are manifold, but (BC) is not. Vertices A and D are manifold, but B and C and connected to three triangle fans, while edge (BC) is connected to four triangles. All mesh operations described above can gracefully handle such geometries, the only problem is when we try to mesh a surface which is not orientable.

Non-manifold edges can also be used to handle ill-oriented meshes. Two triangles which have opposite orientations, as already shown in this image

can be linked together if we state that common edge is non-manifold, add two virtual triangles and link these triangles as shown below:

Field Summary

static int	BOUNDARY Numeric constants for edge attributes.
protected static java.lang.Integer[]	int3 Integer array to store values for 0, 1 and 2.
static int	MARKED Numeric constants for edge attributes.
static int	NONMANIFOLD Numeric constants for edge attributes.
static int	OUTER Numeric constants for edge attributes.
static int	QUAD Numeric constants for edge attributes.
static int	SWAPPED Numeric constants for edge attributes.
protected Traits	traits User-defined traits.
protected HalfEdgeTraitsBuilder	traitsBuilder User-defined traits builder.

Constructor Summary

AbstractHalfEdge(HalfEdgeTraitsBuilder builder)
Constructor.

Method Summary

abstract Vertex	apex() Returns apex of this edge.
abstract double	area() Returns the area of triangle bound to this edge.
protected abstract boolean	canCollapse(Vertex v) Checks whether an edge can be contracted into a given vertex.
abstract boolean	checkNewRingNormals(double[] newpt) Checks that triangles are not inverted if origin vertex is moved.
abstract void	clearAttributes(int attr) Resets attributes of this edge.
protected abstract AbstractHalfEdge	collapse(Mesh m, Vertex v) Contracts an edge.
abstract Vertex	destination() Returns end vertex of this edge.
abstract java.util.Iterator<AbstractHalfEdge>	fanIterator() Returns an iterator over triangle fans connected to this edge.
abstract int	getLocalNumber() Returns edge local number.
abstract Triangle	getTri() Returns triangle tied to this edge.
abstract void	glue(AbstractHalfEdge e) Sets the edge tied to this object.
abstract boolean	hasAttributes(int attr) Checks if some attributes of this edge are set.
abstract boolean	hasSymmetricEdge() Tells whether edge is connected to a symmetric edge.
abstract AbstractHalfEdge	next() Moves counterclockwise to following edge.
abstract AbstractHalfEdge	next(AbstractHalfEdge that) Moves counterclockwise to following edge.
abstract AbstractHalfEdge	nextOrigin() Moves counterclockwise to the following edge which has the same origin.
abstract AbstractHalfEdge	nextOrigin(AbstractHalfEdge that) Moves counterclockwise to the following edge which has the same origin.
abstract AbstractHalfEdge	nextOriginLoop() Moves counterclockwise to the following edge which has the same origin.
abstract Vertex	origin() Returns start vertex of this edge.
abstract AbstractHalfEdge	prev() Moves counterclockwise to previous edge.
abstract AbstractHalfEdge	prev(AbstractHalfEdge that) Moves counterclockwise to previous edge.
abstract void	setAttributes(int attr) Sets attributes of this edge.
protected abstract AbstractHalfEdge	split(Mesh m, Vertex v) Splits an edge.
protected abstract AbstractHalfEdge	swap() Swaps an edge.
abstract AbstractHalfEdge	sym() Moves to symmetric edge.
abstract AbstractHalfEdge	sym(AbstractHalfEdge that) Moves to symmetric edge.

Methods inherited from class java.lang.Object

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

Field Detail

traitsBuilder

protected final HalfEdgeTraitsBuilder traitsBuilder

User-defined traits builder.

traits

protected final Traits traits

User-defined traits.

BOUNDARY

public static final int BOUNDARY

Numeric constants for edge attributes. Set if edge is on boundary.

See Also:

setAttributes(int), hasAttributes(int), clearAttributes(int), Constant Field Values

OUTER

public static final int OUTER

Numeric constants for edge attributes. Set if edge is outer. (Ie. one of its end point is Mesh.outerVertex)

See Also:

setAttributes(int), hasAttributes(int), clearAttributes(int), Constant Field Values

SWAPPED

public static final int SWAPPED

Numeric constants for edge attributes. Set if edge had been swapped.

See Also:

setAttributes(int), hasAttributes(int), clearAttributes(int), Constant Field Values

MARKED

public static final int MARKED

Numeric constants for edge attributes. Set if edge had been marked (for any operation).

See Also:

setAttributes(int), hasAttributes(int), clearAttributes(int), Constant Field Values

QUAD

public static final int QUAD

Numeric constants for edge attributes. Set if edge is the inner edge of a quadrangle.

See Also:

setAttributes(int), hasAttributes(int), clearAttributes(int), Constant Field Values

NONMANIFOLD

public static final int NONMANIFOLD

Numeric constants for edge attributes. Set if edge is non manifold.

See Also:

setAttributes(int), hasAttributes(int), clearAttributes(int), Constant Field Values

int3

protected static final java.lang.Integer[] int3

Integer array to store values for 0, 1 and 2. These objects may be useful when edge local numbers are put into HashSet or HashMap structures.

Constructor Detail

AbstractHalfEdge

public AbstractHalfEdge(HalfEdgeTraitsBuilder builder)

Constructor. Creates a new instance, and creates traits by

Parameters:

builder - half-edge traits builder

Method Detail

sym

public abstract AbstractHalfEdge sym()

Moves to symmetric edge.

Returns:

current instance after its transformation

sym

public abstract AbstractHalfEdge sym(AbstractHalfEdge that)

Moves to symmetric edge. Make that instance be a copy of current instance, move it to its symmetric edge and return this instance. Current instance is not modified.

Parameters:

that - instance where transformed edge is stored

Returns:

argument after its transformation

next

public abstract AbstractHalfEdge next()

Moves counterclockwise to following edge.

Returns:

current instance after its transformation

next

public abstract AbstractHalfEdge next(AbstractHalfEdge that)

Moves counterclockwise to following edge. Make that instance be a copy of current instance, move it counterclockwise to next edge and return this instance. Current instance is not modified.

Parameters:

that - instance where transformed edge is stored

Returns:

argument after its transformation

prev

public abstract AbstractHalfEdge prev()

Moves counterclockwise to previous edge.

Returns:

current instance after its transformation

prev

public abstract AbstractHalfEdge prev(AbstractHalfEdge that)

Moves counterclockwise to previous edge. Make that instance be a copy of current instance, move it counterclockwise to previous edge and return this instance. Current instance is not modified.

Parameters:

that - instance where transformed edge is stored

Returns:

argument after its transformation

nextOrigin

public abstract AbstractHalfEdge nextOrigin()

Moves counterclockwise to the following edge which has the same origin.

Returns:

current instance after its transformation

nextOrigin

public abstract AbstractHalfEdge nextOrigin(AbstractHalfEdge that)

Moves counterclockwise to the following edge which has the same origin. Make that instance be a copy of current instance, move it counterclockwise to the following edge which has the same origin and return this instance. Current instance is not modified.

Parameters:

that - instance where transformed edge is stored

Returns:

argument after its transformation

nextOriginLoop

public abstract AbstractHalfEdge nextOriginLoop()

Moves counterclockwise to the following edge which has the same origin. If a boundary is reached, loop backward until another boundary is found and start again from there.

Returns:

current instance after its transformation

getTri

public abstract Triangle getTri()

Returns triangle tied to this edge.

Returns:

triangle tied to this edge

getLocalNumber

public abstract int getLocalNumber()

Returns edge local number.

Returns:

edge local number

hasSymmetricEdge

public abstract boolean hasSymmetricEdge()

Tells whether edge is connected to a symmetric edge.

Returns:

true if edge has a symmetric edge, false otherwise.

origin

public abstract Vertex origin()

Returns start vertex of this edge.

Returns:

start vertex of this edge

destination

public abstract Vertex destination()

Returns end vertex of this edge.

Returns:

end vertex of this edge

apex

public abstract Vertex apex()

Returns apex of this edge.

Returns:

apex of this edge

setAttributes

public abstract void setAttributes(int attr)

Sets attributes of this edge.

Parameters:

attr - attributes of this edge

clearAttributes

public abstract void clearAttributes(int attr)

Resets attributes of this edge.

Parameters:

attr - attributes of this edge to clear out

hasAttributes

public abstract boolean hasAttributes(int attr)

Checks if some attributes of this edge are set.

Parameters:

attr - attributes to check

Returns:

true if this AbstractHalfEdge has one of these attributes set, false otherwise

swap

protected abstract AbstractHalfEdge swap()

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.

See Also:

Mesh.edgeSwap(org.jcae.mesh.amibe.ds.AbstractHalfEdge)

checkNewRingNormals

public abstract boolean checkNewRingNormals(double[] newpt)

Checks that triangles are not inverted if origin vertex is moved.

Parameters:

newpt - the new position to be checked

Returns:

false if the new position produces an inverted triangle, true otherwise.

canCollapse

protected abstract boolean canCollapse(Vertex v)

Checks whether an edge can be contracted into a given vertex.

Parameters:

v - the resulting vertex

Returns:

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

See Also:

Mesh.canCollapseEdge(org.jcae.mesh.amibe.ds.AbstractHalfEdge, org.jcae.mesh.amibe.ds.Vertex)

collapse

protected abstract AbstractHalfEdge collapse(Mesh m,
                                             Vertex v)

Contracts an edge.

Parameters:

m - mesh

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.

See Also:

Mesh.edgeCollapse(org.jcae.mesh.amibe.ds.AbstractHalfEdge, org.jcae.mesh.amibe.ds.Vertex)

split

protected abstract AbstractHalfEdge split(Mesh m,
                                          Vertex v)

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

Parameters:

m - mesh

v - the resulting vertex

Returns:

edge starting from n and pointing to original apex

See Also:

Mesh.vertexSplit(org.jcae.mesh.amibe.ds.AbstractHalfEdge, org.jcae.mesh.amibe.ds.Vertex)

glue

public abstract void glue(AbstractHalfEdge e)

Sets the edge tied to this object.

Parameters:

e - the edge tied to this object

area

public abstract double area()

Returns the area of triangle bound to this edge.

Returns:

triangle area

fanIterator

public abstract java.util.Iterator<AbstractHalfEdge> fanIterator()

Returns an iterator over triangle fans connected to this edge. If edge is manifold, this iterator contains a single value, which is this edge. But if it is non-manifold and bound to n triangles, this iterator returns successively the n edges contained in these triangles and connected to the same endpoints.

Returns:

iterator over triangle fans connected to this edge