HalfEdges

The HalfEdges Julia package defines the HalfEdges type and methods/types to implement operations on the halfedge data structure.

At this time HalfEdges only supports immutable operations (read-only). i.e. you can't currently modify a Topology once created.

Creation

To represent the topology of a discrete polygon mesh, instance the Topology type.

julia> topo = Topology([[1,2,3],[1,3,4],[1,4,5,2]],5)

or

julia> topo = Topology([1,2,3,1,3,4,1,4,2])

a flat list of indices is assumed to be a manifold set of connected triangles.

Handles

There are unique handle types for each simplex element. These are essentially uniquely typed integer handles for the different simplex parts you might want to reference. EdgeHandle, VertexHandle, and FaceHandle.

HalfEdgeHandle is the most common return type for methods in the HalfEdges package. EdgeHandle represents a unique edge, whereas there are two distinct HalfEdgeHandle per edge.

julia> using HalfEdges: vertices, edges, face, halfedge, head, tail    

julia> vertices(topo) |> first |> typeof
HalfEdgeHandle

julia> vertices(topo) |> first |> heᵢ->tail(topo, heᵢ) |> typeof
VertexHandle

HalfEdge conventions

A given HalfEdge points from tail to head vertex and is associated with the face on it's left. A Polygon is considered to be "wound" in the counterclockwise direction. FaceHandle and VertexHandle integer values will correspond to the polygon and vertex indices you created the Topology with, so long as you haven't called any methods that do any reindexing.

julia> using HalfEdges: halfedges, vertices, vertex, edges, edge, halfedge, face, head, tail, opposite, next

    2
   /|\
  / | \ 
 /  |  \
3---1---4

julia> topo = Topology([[1,2,3],[1,4,2]])

# find the only halfedge pointing from vertex 1 to 2
julia> h = Iterators.filter(h->head(topo, h)==VertexHandle(2), OneRing(topo, VertexHandle(1))) |> first
3

julia> tail(topo, h)
1

julia> head(topo, h)
2

julia> vertex(topo, h) == ans
true

julia> map( hᵢ->vertex(topo, hᵢ), Polygon(topo, face(topo, h)))
3-element Array{VertexHandle,1}:
 3
 1
 2

julia> h = opposite(topo, h)
4

julia> map( hᵢ->vertex(topo, hᵢ), Polygon(topo, face(topo, h)))
3-element Array{VertexHandle,1}:
 1
 4
 2

Iterating over components

A number of iterators are provided. Unless stated, the iterates are HalfEdgeHandles

• OneRing iterates around the edge "spokes" radiating out from a vertex. This iteration is done clockwise for performance reasons.
• Rim iterates around the "tire" edges of the polygons attached to a vertex. This iteration is performned in a clockwise manner.
• Polygon iterates around a polgon in a counterclockwise manner.
• BoundaryLoop iterates around the boundary connected to the given halfedge.

Examples:

    2====6
   /+\  ||
  / + \ ||
 /  +  \||
3+++1+++4
 \     /
  \   /
   \ /
    5 

OneRing₁ => '+'
Rim₁ => '-'

julia> topo = Topology([[1,2,3],[1,4,2],[1,3,5,4],[2,4,6]])  # note we have a quad mixed in 

julia> edges(topo, OneRing(topo, VertexHandle(1)))
3-element Array{Tuple{VertexHandle,VertexHandle},1}:
 (1, 3)
 (1, 2)
 (1, 4)

julia> edges(topo, Rim(topo, VertexHandle(1)))
4-element Array{Tuple{VertexHandle,VertexHandle},1}:
 (2, 3)
 (4, 2)
 (3, 5)
 (5, 4)

julia> BoundaryLoop(topo, first(OneRing(topo, VertexHandle(1))))

julia> edges(topo, BoundaryLoop(topo, first(OneRing(topo, VertexHandle(2)))))
5-element Array{Tuple{VertexHandle,VertexHandle},1}:
 (2, 6)
 (6, 4)
 (4, 5)
 (5, 3)
 (3, 2)

julia> edges(topo, Polygon(topo, FaceHandle(1)))
3-element Array{Tuple{VertexHandle,VertexHandle},1}:
 (3, 1)
 (1, 2)
 (2, 3)

Navigating a mesh

Methods to move around by following HalfEdgeHandle are the most flexible ways to navigate.

Lets move from an edge on vertex 1 to vertex 6.

    2---6
   /^+  ^
  / + + +
 /  +  >+
3++>1---4

We start on the halfedge 3->1, which is on the interior of the face (1,2,3).
Use next to move ccw onto 1->2 opposite will jump across the edge to the halfedge 2->1 on face (1,4,2) Now we pivot around vertex 2 over edge (2,4) using next and land on the halfedge 2->4 on face (4,6,2) We finally move ccw one more time with next Finally check we are pointing at vertex 6

# do it the long way
julia> head(topo, next(topo, opposite(topo, next(topo, next(topo, opposite(topo, next(topo, HalfEdgeHandle(1))))))))
6

# use 1-arity methods to avoid repeating topo parameter excessively

# make a function to pivot around a vertex over an edge
julia> pivot = opposite(next(next))
#62 (generic function with 1 method)

# execute our plan to get from 3->1 to vertex 6
julia> head(next)(topo, pivot(topo, opposite(next)(topo, HalfEdgeHandle(1))))
6

# use julia's function chaining macro to order operations in a more natural way.
julia> (halfedge |> next |> opposite |> next |> next |> opposite |> next |> head)(topo, (3,1)) == ans
true

Collision Detection

There is support for accelerating collision queries using a Bounding Volume Hierarchy.

# create a Collider first to cache the BVH
julia> col = Collider(topo, P)

# can query all the faces that overlap a bounding box
julia> query_aabb(col, HalfEdges.BVH.AABB(SVector{3}(0.,0.,0.5), SVector{3}(1.0,1.0,1.0)))  

# we need to provide our own method to actually collide the candidate faces
julia> traingle_vs_triangle(a1,b1,c1, a2,b2,c2) = (true, "some collision data")  # provide your own

# now we can do a self-intersection test on the entire mesh
julia> hits = collide_self(col, triangle_vs_triangle)

Project Information

Contributing

Please read CONTRIBUTING.md for details.

Authors

• Michael Alexander Ewert - Developer - Digital Domain

License

This project is licensed under a modified Apache 2.0 license - see the LICENSE file for details