## HalfEdges.jl

Half-edge data structure for navigating polygonal meshes
Author digitaldomain
Popularity
9 Stars
Updated Last
2 Years Ago
Started In
February 2020

# 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

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
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)
``````