using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
namespace Plankton
{Provides access to the halfedges and PlanktonHalfedge related functionality of a Mesh.
public class PlanktonHalfEdgeList : IEnumerable<PlanktonHalfedge>
{
private readonly PlanktonMesh _mesh;
private List<PlanktonHalfedge> _list;Initializes a new instance of the PlanktonHalfedgeList class. Should be called from the mesh constructor.
internal PlanktonHalfEdgeList(PlanktonMesh owner)
{
this._list = new List<PlanktonHalfedge>();
this._mesh = owner;
} public int Count
{
get
{
return this._list.Count;
}
}
#region methods
#region halfedge accessAdds a new halfedge to the end of the Halfedge list.
The index of the newly added halfedge.
public int Add(PlanktonHalfedge halfedge)
{
if (halfedge == null) return -1;
this._list.Add(halfedge);
return this.Count - 1;
}Add a pair of halfedges to the mesh.
The index of the first halfedge in the pair.
internal int AddPair(int start, int end, int face)
{
// he->next = he->pair
int i = this.Count;
this.Add(new PlanktonHalfedge(start, face, i + 1));
this.Add(new PlanktonHalfedge(end, -1, i));
return i;
}Removes a pair of halfedges from the mesh.
The halfedges are topologically disconnected from the mesh and marked for deletion. Note that this helper method doesn't update adjacent faces.
internal void RemovePairHelper(int index)
{
int pair = this.GetPairHalfedge(index);
// Reconnect adjacent halfedges
this.MakeConsecutive(this[pair].PrevHalfedge, this[index].NextHalfedge);
this.MakeConsecutive(this[index].PrevHalfedge, this[pair].NextHalfedge);
// Update vertices' outgoing halfedges, if necessary. If last halfedge then
// make vertex unused (outgoing == -1), otherwise set to next around vertex.
var v1 = _mesh.Vertices[this[index].StartVertex];
var v2 = _mesh.Vertices[this[pair].StartVertex];
if (v1.OutgoingHalfedge == index)
{
if (this[pair].NextHalfedge == index) { v1.OutgoingHalfedge = -1; }
else { v1.OutgoingHalfedge = this[pair].NextHalfedge; }
}
if (v2.OutgoingHalfedge == pair)
{
if (this[index].NextHalfedge == pair) { v2.OutgoingHalfedge = -1; }
else { v2.OutgoingHalfedge = this[index].NextHalfedge; }
}
// Mark halfedges for deletion
this[index] = PlanktonHalfedge.Unset;
this[pair] = PlanktonHalfedge.Unset;
}Returns the PlanktonHalfedge at the given index.
The halfedge at the given index.
public PlanktonHalfedge this[int index]
{
get
{
return this._list[index];
}
internal set
{
this._list[index] = value;
}
}
#endregion internal void CompactHelper()
{
int marker = 0; // Location where the current halfedge should be moved to
// Run through all the vertices
for (int iter = 0; iter < _list.Count; iter++)
{
// If halfedge is alive, check if we need to shuffle it down the list
if (!_list[iter].IsUnused)
{
if (marker < iter)
{
// Room to shuffle. Copy current halfedge to marked slot.
_list[marker] = _list[iter];
// Update start vertex, if necessary
var vertex = _mesh.Vertices[_list[marker].StartVertex];
if (vertex.OutgoingHalfedge == iter) { vertex.OutgoingHalfedge = marker; }
// Update adjacent face, if necessary
if (_list[marker].AdjacentFace > -1)
{
var face = _mesh.Faces[_list[marker].AdjacentFace];
if (face.FirstHalfedge == iter) { face.FirstHalfedge = marker; }
}
// Update next/prev halfedges
_list[_list[marker].NextHalfedge].PrevHalfedge = marker;
_list[_list[marker].PrevHalfedge].NextHalfedge = marker;
}
marker++; // That spot's filled. Advance the marker.
}
}
// Throw a fit if we've ended up with an odd number of halfedges
// This could happen if only one of the halfedges in a pair was marked for deletion
if (marker % 2 > 0) { throw new InvalidOperationException("Halfedge count was odd after compaction"); }
// Trim list down to new size
if (marker < _list.Count) { _list.RemoveRange(marker, _list.Count - marker); }
}
#region traversalsTraverses clockwise around the starting vertex of a halfedge.
An enumerable of halfedge indices incident to the starting vertex of halfedgeIndex. Ordered clockwise around the vertex. The returned enumerable will start with the specified halfedge.
Lazily evaluated so if you change the mesh topology whilst using this circulator, you'll know about it!
public IEnumerable<int> GetVertexCirculator(int halfedgeIndex)
{
if (halfedgeIndex < 0 || halfedgeIndex > this.Count) { yield break; }
int h = halfedgeIndex;
int count = 0;
do
{
yield return h;
h = this[this.GetPairHalfedge(h)].NextHalfedge;
if (h < 0) { throw new InvalidOperationException("Unset index, cannot continue."); }
if (count++ > 999) { throw new InvalidOperationException("Runaway vertex circulator"); }
}
while (h != halfedgeIndex);
}Traverses anticlockwise around the adjacent face of a halfedge.
An enumerable of halfedge indices incident to the adjacent face of halfedgeIndex. Ordered anticlockwise around the face.
Lazily evaluated so if you change the mesh topology whilst using this circulator, you'll know about it!
public IEnumerable<int> GetFaceCirculator(int halfedgeIndex)
{
if (halfedgeIndex < 0 || halfedgeIndex > this.Count) { yield break; }
int h = halfedgeIndex;
int count = 0;
do
{
yield return h;
h = this[h].NextHalfedge;
if (h < 0) { throw new InvalidOperationException("Unset index, cannot continue."); }
if (count++ > 999) { throw new InvalidOperationException("Runaway face circulator."); }
}
while (h != halfedgeIndex);
}
#endregion
#region public helpersGets the halfedge index between two vertices.
If it exists, the index of the halfedge which originates from start and terminates at end. Otherwise -1 is returned.
public int FindHalfedge(int start, int end)
{
int halfedgeIndex = _mesh.Vertices[start].OutgoingHalfedge;
foreach (int h in this.GetVertexCirculator(halfedgeIndex))
{
if (end == this[this.GetPairHalfedge(h)].StartVertex)
return h;
}
return -1;
}Gets the opposing halfedge in a pair.
The halfedge index with which the specified halfedge is paired.
public int GetPairHalfedge(int halfedgeIndex)
{
if (halfedgeIndex < 0 || halfedgeIndex >= this.Count)
{
throw new ArgumentOutOfRangeException();
}
return halfedgeIndex % 2 == 0 ? halfedgeIndex + 1 : halfedgeIndex - 1;
}
[Obsolete("PairHalfedge is deprecated, pease use GetPairHalfedge instead.")]
public int PairHalfedge(int halfedgeIndex)
{
return this.GetPairHalfedge(halfedgeIndex);
}Gets the two vertices for a halfedge.
The pair of vertex indices connected by the specified halfedge. The order follows the direction of the halfedge.
public int[] GetVertices(int index)
{
int I, J;
I = this[index].StartVertex;
J = this[this.GetPairHalfedge(index)].StartVertex;
return new int[]{ I, J };
}Gets the halfedge a given number of 'next's around a face from a starting halfedge
The resulting halfedge
[Obsolete("GetNextHalfedge(int,int) is deprecated, please use" +
"GetFaceCirculator(int).ElementAt(int) instead (LINQ).")]
public int GetNextHalfEdge(int startHalfEdge, int around)
{
int he_around = startHalfEdge;
for (int i = 0; i < around; i++)
{
he_around = this[he_around].NextHalfedge;
}
return he_around;
}A halfedge is on a boundary if it only has a face on one side.
if the specified halfedge is on a boundary; otherwise, .
public bool IsBoundary(int index)
{
int pair = this.GetPairHalfedge(index);
// Check for a face on both sides
return (this[index].AdjacentFace == -1 || this[pair].AdjacentFace == -1);
}Gets the index of the vertex at the of a halfedge.
The index of vertex at the end of the specified halfedge.
This helper actually returns the start vertex of the other halfedge in the pair.
public int EndVertex(int halfedgeIndex)
{
return this[GetPairHalfedge(halfedgeIndex)].StartVertex;
}
#endregion
#region internal helpers
internal void MakeConsecutive(int prev, int next)
{
this[prev].NextHalfedge = next;
this[next].PrevHalfedge = prev;
}
#endregion
#region Geometry
public double[] GetLengths()Measure the lengths of all the halfedges
An array of lengths for all halfedges, or -1 for dead ones
{
double[] Lengths = new double[this.Count];
for (int i = 0; i < this.Count; i += 2)
{
double EdgeLength = GetLength(i);
Lengths[i] = EdgeLength;
Lengths[i + 1] = EdgeLength;
}
return Lengths;
}
public double GetLength(int index)Measure the length of a single halfedge
The length of the halfedge, or -1 if unused
{
double EdgeLength = -1;
if (this[index].IsUnused == false)
{
PlanktonXYZ Start = _mesh.Vertices[this[index].StartVertex].ToXYZ();
PlanktonXYZ End = _mesh.Vertices[this.EndVertex(index)].ToXYZ();
EdgeLength = (End - Start).Length;
}
return EdgeLength;
}
#endregion
#region Euler operators
public bool FlipEdge(int index)
{
// Don't allow if halfedge is on a boundary
if (this[index].AdjacentFace < 0 || this[GetPairHalfedge(index)].AdjacentFace < 0)
return false;
// Make a note of some useful halfedges, along with 'index' itself
int pair = this.GetPairHalfedge(index);
int next = this[index].NextHalfedge;
int pair_next = this[pair].NextHalfedge;
// Also don't allow if the edge that would be created by flipping already exists in the mesh
if (FindHalfedge(EndVertex(pair_next), EndVertex(next)) != -1)
return false;
// to flip an edge
// 6 nexts
// 6 prevs
this.MakeConsecutive(this[pair].PrevHalfedge, next);
this.MakeConsecutive(index, this[next].NextHalfedge);
this.MakeConsecutive(next, pair);
this.MakeConsecutive(this[index].PrevHalfedge, pair_next);
this.MakeConsecutive(pair, this[pair_next].NextHalfedge);
this.MakeConsecutive(pair_next, index);
// for each vert, check if need to update outgoing
int v = this[index].StartVertex;
if (_mesh.Vertices[v].OutgoingHalfedge == index)
_mesh.Vertices[v].OutgoingHalfedge = pair_next;
v = this[pair].StartVertex;
if (_mesh.Vertices[v].OutgoingHalfedge == pair)
_mesh.Vertices[v].OutgoingHalfedge = next;
// for each face, check if need to update start he
int f = this[index].AdjacentFace;
if (_mesh.Faces[f].FirstHalfedge == next)
_mesh.Faces[f].FirstHalfedge = index;
f = this[pair].AdjacentFace;
if (_mesh.Faces[f].FirstHalfedge == pair_next)
_mesh.Faces[f].FirstHalfedge = pair;
// update 2 start verts
this[index].StartVertex = EndVertex(pair_next);
this[pair].StartVertex = EndVertex(next);
// 2 adjacentfaces
this[next].AdjacentFace = this[pair].AdjacentFace;
this[pair_next].AdjacentFace = this[index].AdjacentFace;
return true;
}Creates a new vertex, and inserts it along an existing edge, splitting it in 2.
The index of the newly created halfedge in the same direction as the input halfedge.
public int SplitEdge(int index)
{
int pair = this.GetPairHalfedge(index);
// Create a copy of the existing vertex (user can move it afterwards if needs be)
int end_vertex = this[pair].StartVertex;
int new_vertex_index = _mesh.Vertices.Add(_mesh.Vertices[end_vertex].ToXYZ()); // use XYZ to copy
// Add a new halfedge pair
int new_halfedge1 = this.AddPair(new_vertex_index, this.EndVertex(index), this[index].AdjacentFace);
int new_halfedge2 = this.GetPairHalfedge(new_halfedge1);
this[new_halfedge2].AdjacentFace = this[pair].AdjacentFace;
// Link new pair into mesh
this.MakeConsecutive(new_halfedge1, this[index].NextHalfedge);
this.MakeConsecutive(index, new_halfedge1);
this.MakeConsecutive(this[pair].PrevHalfedge, new_halfedge2);
this.MakeConsecutive(new_halfedge2, pair);
// Set new vertex's outgoing halfedge
_mesh.Vertices[new_vertex_index].OutgoingHalfedge = new_halfedge1;
// Change the start of the pair of the input halfedge to the new vertex
this[pair].StartVertex = new_vertex_index;
// Update end vertex's outgoing halfedge, if necessary
if (_mesh.Vertices[end_vertex].OutgoingHalfedge == pair)
{
_mesh.Vertices[end_vertex].OutgoingHalfedge = new_halfedge2;
}
return new_halfedge1;
}Split 2 adjacent triangles into 4 by inserting a new vertex along the edge
The index of the halfedge going from the new vertex to the end of the input halfedge, or -1 on failure
public int TriangleSplitEdge(int index)
{
//split the edge
// (I guess we could include a parameter for where along the edge to split)
int new_halfedge = this.SplitEdge(index);
int point_on_edge = this[new_halfedge].StartVertex;
_mesh.Vertices[point_on_edge].X = 0.5F * (_mesh.Vertices[this[index].StartVertex].X + _mesh.Vertices[this.EndVertex(new_halfedge)].X);
_mesh.Vertices[point_on_edge].Y = 0.5F * (_mesh.Vertices[this[index].StartVertex].Y + _mesh.Vertices[this.EndVertex(new_halfedge)].Y);
_mesh.Vertices[point_on_edge].Z = 0.5F * (_mesh.Vertices[this[index].StartVertex].Z + _mesh.Vertices[this.EndVertex(new_halfedge)].Z);
int new_face1 = _mesh.Faces.SplitFace(new_halfedge, this[this[new_halfedge].NextHalfedge].NextHalfedge);
int new_face2 = _mesh.Faces.SplitFace(this.GetPairHalfedge(index), this[this[this.GetPairHalfedge(index)].NextHalfedge].NextHalfedge);
return new_halfedge;
}Collapse an edge by combining 2 vertices
The successor to index around its vertex, or -1 on failure.
public int CollapseEdge(int index)
{
var fs = _mesh.Faces;
int pair = this.GetPairHalfedge(index);
int v_keep = this[index].StartVertex;
int v_kill = this[pair].StartVertex;
int f = this[index].AdjacentFace;
int f_pair = this[pair].AdjacentFace;
// Don't allow the creation of non-manifold vertices
// This would happen if the edge is internal (face on both sides) and
// both incident vertices lie on a boundary
if (f > -1 && f_pair > -1)
{
if (this[_mesh.Vertices[v_keep].OutgoingHalfedge].AdjacentFace < 0 &&
this[_mesh.Vertices[v_kill].OutgoingHalfedge].AdjacentFace < 0)
{
return -1;
}
}
// Avoid creating a non-manifold edge...
// If the edge is internal, then its ends must not have more than 2 neighbours in common.
// If the edge is a boundary edge (or has one 3+ sided face), then its ends must not
// have more than one neighbour in common.
//int allowed = (f > -1 && f_pair > -1) ? 2 : 1;
int allowed = 0;
if (f >= 0 && fs.GetHalfedges(f).Length == 3) { allowed++; }
if (f_pair >= 0 && fs.GetHalfedges(f_pair).Length == 3) { allowed++; }
if (_mesh.Vertices.GetVertexNeighbours(v_keep)
.Intersect(_mesh.Vertices.GetVertexNeighbours(v_kill)).Count() > allowed)
{
return -1;
}
// Save a couple of halfedges for later
int next = this[index].NextHalfedge;
int pair_prev = this[pair].PrevHalfedge;
// Find the halfedges starting at the vertex we are about to remove
// and reconnect them to the one we are keeping
foreach (int h in this.GetVertexCirculator(next))
{
this[h].StartVertex = v_keep;
}
// Store return halfedge index (next around start vertex)
int h_rtn = this[pair].NextHalfedge;
// Set outgoing halfedge
int v_kill_outgoing = _mesh.Vertices[v_kill].OutgoingHalfedge;
if (this[v_kill_outgoing].AdjacentFace < 0 && v_kill_outgoing != pair)
_mesh.Vertices[v_keep].OutgoingHalfedge = v_kill_outgoing;
else if (_mesh.Vertices[v_keep].OutgoingHalfedge == index)
_mesh.Vertices[v_keep].OutgoingHalfedge = h_rtn; // Next around vertex
// Bypass both halfedges by linking prev directly to next for each
this.MakeConsecutive(this[index].PrevHalfedge, next);
this.MakeConsecutive(pair_prev, this[pair].NextHalfedge);
// Kill the halfedge pair and its end vertex
this[index] = PlanktonHalfedge.Unset;
this[pair] = PlanktonHalfedge.Unset;
_mesh.Vertices[v_kill] = PlanktonVertex.Unset;
// Update faces' first halfedges, if necessary
if (f != -1 && fs[f].FirstHalfedge == index)
fs[f].FirstHalfedge = next;
if (f_pair != -1 && fs[f_pair].FirstHalfedge == pair)
fs[f_pair].FirstHalfedge = this[pair].NextHalfedge;
// If either adjacent face was triangular it will now only have two sides. If so,
// try to merge faces into whatever is on the RIGHT of the associated halfedge.
if (f > -1 && this.GetFaceCirculator(next).Count() < 3)
{
if (fs.MergeFaces(this.GetPairHalfedge(next)) < 0) { fs.RemoveFace(f); }
}
if (f_pair > -1 && !this[pair_prev].IsUnused && this.GetFaceCirculator(pair_prev).Count() < 3)
{
if (fs.MergeFaces(this.GetPairHalfedge(pair_prev)) < 0) { fs.RemoveFace(f_pair); }
}
return h_rtn;
}
#endregion
#endregion
#region IEnumerable implementationGets an enumerator that yields all halfedges in this collection.
An enumerator.
public IEnumerator<PlanktonHalfedge> GetEnumerator()
{
return this._list.GetEnumerator();
}
IEnumerator IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
#endregion
}
}