EdgeLoop.cs

using System;
using System.Collections.Generic;
using System.Diagnostics;


namespace g3
{
    /// <summary>
    /// Sequential set of vertices/edges in a mesh, that form a closed loop.
    /// 
    /// If all you have are the vertices, use EdgeLoop.VertexLoopToEdgeLoop() to construct an EdgeLoop
    /// </summary>
    public class EdgeLoop
    {
        public DMesh3 Mesh;

        public int[] Vertices;
        public int[] Edges;

        public int[] BowtieVertices;        // this may not be initialized!


        public EdgeLoop(DMesh3 mesh)
        {
            Mesh = mesh;
        }
        public EdgeLoop(DMesh3 mesh, int[] vertices, int[] edges, bool bCopyArrays)
        {
            Mesh = mesh;
            if ( bCopyArrays ) {
                Vertices = new int[vertices.Length];
                Array.Copy(vertices, Vertices, Vertices.Length);
                Edges = new int[edges.Length];
                Array.Copy(edges, Edges, Edges.Length);
            } else {
                Vertices = vertices;
                Edges = edges;
            }
        }

        public EdgeLoop(EdgeLoop copy)
        {
            Mesh = copy.Mesh;
            Vertices = new int[copy.Vertices.Length];
            Array.Copy(copy.Vertices, Vertices, Vertices.Length);
            Edges = new int[copy.Edges.Length];
            Array.Copy(copy.Edges, Edges, Edges.Length);
            if (copy.BowtieVertices != null) {
                BowtieVertices = new int[copy.BowtieVertices.Length];
                Array.Copy(copy.BowtieVertices, BowtieVertices, BowtieVertices.Length);
            }
        }


        /// <summary>
        /// construct EdgeLoop from a list of edges of mesh
        /// </summary>
        public static EdgeLoop FromEdges(DMesh3 mesh, IList<int> edges)
        {
            int[] Edges = new int[edges.Count];
            for (int i = 0; i < Edges.Length; ++i)
                Edges[i] = edges[i];

            int[] Vertices = new int[Edges.Length];
            Index2i start_ev = mesh.GetEdgeV(Edges[0]);
            Index2i prev_ev = start_ev;
            for (int i = 1; i < Edges.Length; ++i) {
                Index2i next_ev = mesh.GetEdgeV(Edges[i % Edges.Length]);
                Vertices[i] = IndexUtil.find_shared_edge_v(ref prev_ev, ref next_ev);
                prev_ev = next_ev;
            }
            Vertices[0] = IndexUtil.find_edge_other_v(ref start_ev, Vertices[1]);
            return new EdgeLoop(mesh, Vertices, Edges, false);
        }


        /// <summary>
        /// construct EdgeLoop from a list of vertices of mesh
        /// </summary>
        public static EdgeLoop FromVertices(DMesh3 mesh, IList<int> vertices)
        {
            int NV = vertices.Count;
            int[] Vertices = new int[NV];
            for (int i = 0; i < NV; ++i)
                Vertices[i] = vertices[i];
            int NE = NV;
            int[] Edges = new int[NE];
            for (int i = 0; i < NE; ++i) {
                Edges[i] = mesh.FindEdge(Vertices[i], Vertices[(i + 1)%NE]);
                if (Edges[i] == DMesh3.InvalidID)
                    throw new Exception("EdgeLoop.FromVertices: vertices are not connected by edge!");
            }
            return new EdgeLoop(mesh, Vertices, Edges, false);
        }



        /// <summary>
        /// construct EdgeLoop from a list of vertices of mesh
        /// if loop is a boundary edge, we can correct orientation if requested
        /// </summary>
        public static EdgeLoop FromVertices(DMesh3 mesh, IList<int> vertices, bool bAutoOrient = true)
        {
            int[] Vertices = new int[vertices.Count];
            for (int i = 0; i < Vertices.Length; i++) 
                Vertices[i] = vertices[i];

            if ( bAutoOrient ) {
                int a = Vertices[0], b = Vertices[1];
                int eid = mesh.FindEdge(a, b);
                if (mesh.IsBoundaryEdge(eid)) {
                    Index2i ev = mesh.GetOrientedBoundaryEdgeV(eid);
                    if (ev.a == b && ev.b == a)
                        Array.Reverse(Vertices);
                }
            }

            int[] Edges = new int[Vertices.Length];
            for (int i = 0; i < Edges.Length; ++i) {
                int a = Vertices[i], b = Vertices[(i + 1) % Vertices.Length];
                Edges[i] = mesh.FindEdge(a, b);
                if (Edges[i] == DMesh3.InvalidID)
                    throw new Exception("EdgeLoop.FromVertices: invalid edge [" + a + "," + b + "]");
            }

            return new EdgeLoop(mesh, Vertices, Edges, false);
        }


        public int VertexCount {
            get { return Vertices.Length; }
        }
        public int EdgeCount {
            get { return Edges.Length; }
        }

        public Vector3d GetVertex(int i) {
            return Mesh.GetVertex(Vertices[i]);
        }


        public AxisAlignedBox3d GetBounds()
        {
            AxisAlignedBox3d box = AxisAlignedBox3d.Empty;
            for (int i = 0; i < Vertices.Length; ++i)
                box.Contain(Mesh.GetVertex(Vertices[i]));
            return box;
        }


        public DCurve3 ToCurve(DMesh3 sourceMesh = null)
        {
            if (sourceMesh == null)
                sourceMesh = Mesh;
            DCurve3 curve = MeshUtil.ExtractLoopV(sourceMesh, Vertices);
            curve.Closed = true;
            return curve;
        }


        /// <summary>
        /// if this is a border edge-loop, we can check that it is oriented correctly, and
        /// if not, reverse it.
        /// Returns true if we reversed orientation.
        /// </summary>
        public bool CorrectOrientation()
        {
            int a = Vertices[0], b = Vertices[1];
            int eid = Mesh.FindEdge(a, b);
            if (Mesh.IsBoundaryEdge(eid)) {
                Index2i ev = Mesh.GetOrientedBoundaryEdgeV(eid);
                if (ev.a == b && ev.b == a) {
                    Reverse();
                    return true;
                }
            }
            return false;
        }


        public void Reverse()
        {
            Array.Reverse(Vertices);
            Array.Reverse(Edges);
        }


        /// <summary>
        /// check if all edges of this loop are internal edges (ie none on boundary)
        /// </summary>
        /// <returns></returns>
        public bool IsInternalLoop()
        {
            int NV = Vertices.Length;
            for (int i = 0; i < NV; ++i ) {
                int eid = Mesh.FindEdge(Vertices[i], Vertices[(i + 1) % NV]);
                Debug.Assert(eid != DMesh3.InvalidID);
                if (Mesh.IsBoundaryEdge(eid))
                    return false;
            }
            return true;
        }


        /// <summary>
        /// Check if all edges of this loop are boundary edges
        /// </summary>
        public bool IsBoundaryLoop()
        {
            int NV = Vertices.Length;
            for (int i = 0; i < NV; ++i ) {
                int eid = Mesh.FindEdge(Vertices[i], Vertices[(i + 1) % NV]);
                Debug.Assert(eid != DMesh3.InvalidID);
                if (Mesh.IsBoundaryEdge(eid) == false)
                    return false;
            }
            return true;
        }


        /// <summary>
        /// find index of vertex vID in Vertices list, or -1 if not found
        /// </summary>
        public int FindVertexIndex(int vID)
        {
            int N = Vertices.Length;
            for (int i = 0; i < N; ++i) {
                if (Vertices[i] == vID)
                    return i;
            }
            return -1;
        }

        /// <summary>
        /// find index of vertices of loop that is closest to point v
        /// </summary>
        public int FindNearestVertex(Vector3d v)
        {
            int iNear = -1;
            double fNearSqr = double.MaxValue;
            int N = Vertices.Length;
            for ( int i = 0; i < N; ++i ) {
                Vector3d lv = Mesh.GetVertex(Vertices[i]);
                double d2 = v.DistanceSquared(lv);
                if ( d2 < fNearSqr ) {
                    fNearSqr = d2;
                    iNear = i;
                }
            }
            return iNear;
        }

        // count # of vertices in loop that are within tol of v
        // final param returns last encountered index within tolerance, or -1 if return is 0
        public int CountWithinTolerance(Vector3d v, double tol, out int last_in_tol)
        {
            last_in_tol = -1;
            int count = 0;
            int N = Vertices.Length;
            for (int i = 0; i < N; ++i) {
                Vector3d lv = Mesh.GetVertex(Vertices[i]);
                if (v.Distance(lv) < tol) {
                    count++;
                    last_in_tol = i;
                }
            }
            return count;
        }


        // Check if Loop2 is the same set of positions on another mesh.
        // Does not require the indexing to be the same
        // Currently doesn't handle loop-reversal
        public bool IsSameLoop(EdgeLoop Loop2, bool bReverse2 = false, double tolerance = MathUtil.ZeroTolerance)
        {
            // find a duplicate starting vertex
            int N = Vertices.Length;
            int N2 = Loop2.Vertices.Length;
            if (N != N2)
                return false;

            DMesh3 Mesh2 = Loop2.Mesh;

            int start_i = 0, start_j = -1;

            // try to find a unique same-vertex on each loop. Do not
            // use vertices that have duplicate positions.
            bool bFoundGoodStart = false;
            while ( !bFoundGoodStart && start_i < N ) {
                Vector3d start_v = Mesh.GetVertex(start_i);
                int count = Loop2.CountWithinTolerance(start_v, tolerance, out start_j);
                if (count == 1)
                    bFoundGoodStart = true;
                else
                    start_i++;
            }
            if (!bFoundGoodStart)
                return false;       // no within-tolerance duplicate vtx to start at

            for ( int ii = 0; ii < N; ++ii ) {
                int i = (start_i + ii) % N;
                int j = (bReverse2) ? 
                    MathUtil.WrapSignedIndex(start_j - ii, N2)
                    : (start_j + ii) % N2;
                Vector3d v = Mesh.GetVertex(Vertices[i]);
                Vector3d v2 = Mesh2.GetVertex(Loop2.Vertices[j]);
                if (v.Distance(v2) > tolerance)
                    return false;
            }

            return true;
        }



        /// <summary>
        /// stores vertices [starti, starti+1, ... starti+count-1] in span, and returns span, or null if invalid range
        /// </summary>
        public int[] GetVertexSpan(int starti, int count, int[] span, bool reverse = false)
        {
            int N = Vertices.Length;
            if (starti < 0 || starti >= N || count > N - 1)
                return null;
            if (reverse) {
                for (int k = 0; k < count; ++k)
                    span[count-k-1] = Vertices[(starti + k) % N];
            } else {
                for (int k = 0; k < count; ++k)
                    span[k] = Vertices[(starti + k) % N];
            }
            return span;
        }




        /// <summary>
        /// Exhaustively check that verts and edges of this EdgeLoop are consistent. Not for production use.
        /// </summary>
        public bool CheckValidity(FailMode eFailMode = FailMode.Throw)
        {
            bool is_ok = true;
            Action<bool> CheckOrFailF = (b) => { is_ok = is_ok && b; };
            if (eFailMode == FailMode.DebugAssert) {
                CheckOrFailF = (b) => { Debug.Assert(b); is_ok = is_ok && b; };
            } else if (eFailMode == FailMode.gDevAssert) {
                CheckOrFailF = (b) => { Util.gDevAssert(b); is_ok = is_ok && b; };
            } else if (eFailMode == FailMode.Throw) {
                CheckOrFailF = (b) => { if (b == false) throw new Exception("EdgeLoop.CheckValidity: check failed"); };
            }

            CheckOrFailF(Vertices.Length == Edges.Length);
            for (int ei = 0; ei < Edges.Length; ++ei) {
                Index2i ev = Mesh.GetEdgeV(Edges[ei]);
                CheckOrFailF(Mesh.IsVertex(ev.a));
                CheckOrFailF(Mesh.IsVertex(ev.b));
                CheckOrFailF(Mesh.FindEdge(ev.a, ev.b) != DMesh3.InvalidID);
                CheckOrFailF(Vertices[ei] == ev.a || Vertices[ei] == ev.b);
                CheckOrFailF(Vertices[(ei + 1) % Edges.Length] == ev.a || Vertices[(ei + 1) % Edges.Length] == ev.b);
            }
            for ( int vi = 0; vi < Vertices.Length; ++vi ) {
                int a = Vertices[vi], b = Vertices[(vi + 1) % Vertices.Length];
                CheckOrFailF(Mesh.IsVertex(a));
                CheckOrFailF(Mesh.IsVertex(b));
                CheckOrFailF(Mesh.FindEdge(a,b) != DMesh3.InvalidID);
                int n = 0, edge_before_b = Edges[vi], edge_after_b = Edges[(vi + 1) % Vertices.Length];
                foreach ( int nbr_e in Mesh.VtxEdgesItr(b) ) {
                    if (nbr_e == edge_before_b || nbr_e == edge_after_b)
                        n++;
                }
                CheckOrFailF(n == 2);
            }
            return is_ok;
        }




        /// <summary>
        /// Convert a vertex loop to an edge loop. This should be somewhere else...
        /// </summary>
        public static int[] VertexLoopToEdgeLoop(DMesh3 mesh, int[] vertex_loop)
        {
            int NV = vertex_loop.Length;
            int[] edges = new int[NV];
            for ( int i = 0; i < NV; ++i ) {
                int v0 = vertex_loop[i];
                int v1 = vertex_loop[(i + 1) % NV];
                edges[i] = mesh.FindEdge(v0, v1);
            }
            return edges;
        }



    }
}