

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object org.jcae.mesh.amibe.ds.AbstractHalfEdge
public abstract class AbstractHalfEdge
Abstract class to define common methods on edges.
We use an halfedge data structure to perform mesh traversal. An halfedge
(red arrows) contains a link (black arrows) to its symmetric halfedge, a
link to the next halfedge 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 halfedges have
no links to vertices, they can be easily found; suppose that halfedge
e
has local number l
in triangle tri
:
e.origin()
is tri.vertex[(l+1)%3]
e.destination()
is tri.vertex[(l1)%3]
e.apex()
is tri.vertex[l]
For an halfedge e
, e.sym()
returns its symmetric
halfedge, if it does exist. In this case, e.sym().sym()
is
always e
, and in images below a link between symmetric halfedges
is represented by a single doubleheaded arrow instead of two arrows.
Moreover, symmetric edges must have opposite directions (except for
nonmanifold 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.
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.These operations are abstract methods and are implemented by derived classes:
swap
split
Warning: This method does not check that new triangles are not inverted.
collapse
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 nonmanifold meshes.
These two methods may also be of interest when writing new algorithms:
canCollapse
checkNewRingNormals
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
AbstractHalfEdge.OUTER
AbstractHalfEdge.NONMANIFOLD
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)
clearAttributes(int)
hasAttributes(int)
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.BOUNDARYAbstractHalfEdge.NONMANIFOLD)) { Vertex v = e.destination(); // Do something with v } e = e.nextOriginLoop(); } while (e.destination() != d);
A nonmanifold 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 nonmanifold 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 doublylinked list to iterate over all halfedges connected together, as is done with radialedge 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 halfedges 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 halfedges which are not outer.
In order to ease writing algorithms, this iterator is also defined on regular halfedges, and return only one
value which is this halfedge.
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 nonmanifold 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.
Nonmanifold edges can also be used to handle illoriented meshes. Two triangles which have opposite orientations, as already shown in this image
can be linked together if we state that common edge is nonmanifold, 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
Userdefined traits. 
protected HalfEdgeTraitsBuilder 
traitsBuilder
Userdefined 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 

protected final HalfEdgeTraitsBuilder traitsBuilder
protected final Traits traits
public static final int BOUNDARY
setAttributes(int)
,
hasAttributes(int)
,
clearAttributes(int)
,
Constant Field Valuespublic static final int OUTER
Mesh.outerVertex
)
setAttributes(int)
,
hasAttributes(int)
,
clearAttributes(int)
,
Constant Field Valuespublic static final int SWAPPED
setAttributes(int)
,
hasAttributes(int)
,
clearAttributes(int)
,
Constant Field Valuespublic static final int MARKED
setAttributes(int)
,
hasAttributes(int)
,
clearAttributes(int)
,
Constant Field Valuespublic static final int QUAD
setAttributes(int)
,
hasAttributes(int)
,
clearAttributes(int)
,
Constant Field Valuespublic static final int NONMANIFOLD
setAttributes(int)
,
hasAttributes(int)
,
clearAttributes(int)
,
Constant Field Valuesprotected 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 

public AbstractHalfEdge(HalfEdgeTraitsBuilder builder)
builder
 halfedge traits builderMethod Detail 

public abstract AbstractHalfEdge sym()
public abstract AbstractHalfEdge sym(AbstractHalfEdge that)
that
instance be a copy of current
instance, move it to its symmetric edge and return
this instance. Current instance is not modified.
that
 instance where transformed edge is stored
public abstract AbstractHalfEdge next()
public abstract AbstractHalfEdge next(AbstractHalfEdge that)
that
instance be a copy of current
instance, move it counterclockwise to next edge and
return this instance. Current instance is not modified.
that
 instance where transformed edge is stored
public abstract AbstractHalfEdge prev()
public abstract AbstractHalfEdge prev(AbstractHalfEdge that)
that
instance be a copy of current
instance, move it counterclockwise to previous edge and
return this instance. Current instance is not modified.
that
 instance where transformed edge is stored
public abstract AbstractHalfEdge nextOrigin()
public abstract AbstractHalfEdge nextOrigin(AbstractHalfEdge that)
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.
that
 instance where transformed edge is stored
public abstract AbstractHalfEdge nextOriginLoop()
public abstract Triangle getTri()
public abstract int getLocalNumber()
public abstract boolean hasSymmetricEdge()
true
if edge has a symmetric edge, false
otherwise.public abstract Vertex origin()
public abstract Vertex destination()
public abstract Vertex apex()
public abstract void setAttributes(int attr)
attr
 attributes of this edgepublic abstract void clearAttributes(int attr)
attr
 attributes of this edge to clear outpublic abstract boolean hasAttributes(int attr)
attr
 attributes to check
true
if this AbstractHalfEdge has
one of these attributes set, false
otherwiseprotected abstract AbstractHalfEdge swap()
java.lang.IllegalArgumentException
 if edge is on a boundary or belongs
to an outer triangle.Mesh.edgeSwap(org.jcae.mesh.amibe.ds.AbstractHalfEdge)
public abstract boolean checkNewRingNormals(double[] newpt)
newpt
 the new position to be checked
false
if the new position produces
an inverted triangle, true
otherwise.protected abstract boolean canCollapse(Vertex v)
v
 the resulting vertex
true
if this edge can be contracted into the single vertex n, false
otherwiseMesh.canCollapseEdge(org.jcae.mesh.amibe.ds.AbstractHalfEdge, org.jcae.mesh.amibe.ds.Vertex)
protected abstract AbstractHalfEdge collapse(Mesh m, Vertex v)
m
 meshv
 the resulting vertex
n
and with the same apex
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.Mesh.edgeCollapse(org.jcae.mesh.amibe.ds.AbstractHalfEdge, org.jcae.mesh.amibe.ds.Vertex)
protected abstract AbstractHalfEdge split(Mesh m, Vertex v)
collapse(org.jcae.mesh.amibe.ds.Mesh, org.jcae.mesh.amibe.ds.Vertex)
.
m
 meshv
 the resulting vertex
n
and pointing to original apexMesh.vertexSplit(org.jcae.mesh.amibe.ds.AbstractHalfEdge, org.jcae.mesh.amibe.ds.Vertex)
public abstract void glue(AbstractHalfEdge e)
e
 the edge tied to this objectpublic abstract double area()
public abstract java.util.Iterator<AbstractHalfEdge> fanIterator()


PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 