root/trunk/x42view.net/Helpers.Adjacency.cs

/******************************************************************************
        x42view.net - .x42 viewer and auditing tool
        Copyright (C) 2007 HermitWorks Entertainment Corporation

        This program is free software; you can redistribute it and/or modify it
        under the terms of the GNU General Public License as published by the Free
        Software Foundation; either version 2 of the License, or (at your option)
        any later version.

        This program is distributed in the hope that it will be useful, but
        WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
        or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
        for more details.

        You should have received a copy of the GNU General Public License along
        with this program; if not, write to the
        
                Free Software Foundation, Inc.
                51 Franklin Street, Fifth Floor
                Boston, MA  02110-1301, USA.
******************************************************************************/

using System;
using System.Collections.Generic;

namespace x42view
{
        partial class Helpers
        {
                public static ushort[] GetTriangleIndices( Libx42.Group g )
                {
                        switch( g.PrimitiveType )
                        {
                        case Libx42.PrimitiveType.TriangleList:
                                return g.Indices.ToArray();

                        case Libx42.PrimitiveType.TriangleStrip:
                        case Libx42.PrimitiveType.TriangleFan:
                                break;

                        default:
                                throw new InvalidOperationException();
                        }

                        int iRet = 0;
                        ushort[] ret = new ushort[g.PrimitiveCount * 3];

                        PrimitiveIterator iter = new PrimitiveIterator( g );
                        while( iter.MoveNext() )
                        {
                                ret[iRet++] = iter.Current( 0 );
                                ret[iRet++] = iter.Current( 1 );
                                ret[iRet++] = iter.Current( 2 );
                        }

                        return ret;
                }

                public sealed class Adjacency
                {
                        public struct AdjEntry
                        {
                                public int OtherTriangle;
                                
                                public int ThisEdge;
                                public int OtherEdge;

                                public AdjEntry( int otherTri, int thisEdge, int otherEdge )
                                {
                                        OtherTriangle = otherTri;
                                        ThisEdge = thisEdge;
                                        OtherEdge = otherEdge;
                                }
                        }

                        public struct TriEntry
                        {
                                public int AdjIndex;
                                public int AdjLength;

                                public TriEntry( int adjIndex, int adjLength )
                                {
                                        AdjIndex = adjIndex;
                                        AdjLength = adjLength;
                                }
                        }

                        public struct Edge : IComparable<Edge>, IEquatable<Edge>
                        {
                                public int Triangle;

                                public ushort First;
                                public ushort Second;

                                public Edge Reverse()
                                {
                                        Edge ret;

                                        ret.Triangle = Triangle;
                                        ret.First = Second;
                                        ret.Second = First;

                                        return ret;
                                }

                                public int CompareTo( Edge other )
                                {
                                        int dF = First - other.First;
                                        if( dF != 0 )
                                                return dF;

                                        int dS = Second - other.Second;
                                        if( dS != 0 )
                                                return dS;

                                        return Triangle - other.Triangle;
                                }

                                public bool Equals( Edge other )
                                {
                                        return CompareTo( other ) == 0;
                                }
                        }

                        private sealed class EndPointComparer : IComparer<Edge>
                        {
                                public int Compare( Edge x, Edge y )
                                {
                                        int dF = x.First - y.First;
                                        if( dF != 0 )
                                                return dF;

                                        return x.Second - y.Second;
                                }
                        }

                        private List<TriEntry> entries = new List<TriEntry>();
                        public List<TriEntry> Entries
                        {
                                get { return entries; }
                        }

                        private List<AdjEntry> values = new List<AdjEntry>();
                        public List<AdjEntry> Values
                        {
                                get { return values; }
                        }

                        private List<Edge> edges = new List<Edge>();
                        public List<Edge> Edges
                        {
                                get { return edges; }
                        }

                        private List<int> borderEdges = new List<int>();
                        public List<int> BorderEdges
                        {
                                get { return borderEdges; }
                        }

                        public int NumTris
                        {
                                get { return entries.Count; }
                        }

                        public Adjacency( ushort[] tris )
                        {
                                int numTris = tris.Length / 3;

                                edges.Capacity = numTris * 3;

                                //for each triangle
                                for( int t = 0; t < numTris; t++ )
                                {
                                        //skip degenerates
                                        if( tris[t * 3 + 0] == tris[t * 3 + 1] ||
                                                tris[t * 3 + 1] == tris[t * 3 + 2] ||
                                                tris[t * 3 + 2] == tris[t * 3 + 0] )
                                                continue;

                                        //for each edge
                                        for( int e = 0; e < 3; e++ )
                                        {
                                                ushort es = tris[t * 3 + e];
                                                ushort ee = tris[t * 3 + ((e + 1) % 3)];

                                                Edge edge = new Edge();
                                                edge.Triangle = t;
                                                edge.First = es;
                                                edge.Second = ee;

                                                //throw it into the list
                                                edges.Add( edge );
                                        }
                                }

                                edges.Sort();

                                //build adjacency (ignore Triangle in future comparisons)
                                EndPointComparer comparer = new EndPointComparer();
                                List<List<AdjEntry>> tmpAdj = new List<List<AdjEntry>>( numTris );
                                for( int t = 0; t < numTris; t++ )
                                        tmpAdj.Add( new List<AdjEntry>( 3 ) );

                                for( int i = 0; i < edges.Count; i++ )
                                {
                                        Edge ei = edges[i];

                                        //quick look-ahead for non-manifold type evil
                                        for( int j = i + 1; j < edges.Count; j++ )
                                        {
                                                Edge ej = edges[j];

                                                if( comparer.Compare( ei, ej ) != 0 )
                                                        break;

                                                tmpAdj[ei.Triangle].Add( new AdjEntry( ej.Triangle, i, j ) ); //should this be in here at all?
                                        }

                                        Edge er = ei.Reverse();
                                        
                                        int idx = edges.BinarySearch( er, comparer );

                                        //if there's more than one this might not point to the first, seek back
                                        while( idx > 0 && comparer.Compare( edges[idx - 1], er ) == 0 )
                                                idx--;

                                        if( idx < 0 )
                                        {
                                                borderEdges.Add( i );
                                                continue;
                                        }

                                        //add all the edges that match er
                                        for( int j = idx; j < edges.Count; j++ )
                                        {
                                                Edge ej = edges[j];

                                                if( comparer.Compare( er, ej ) != 0 )
                                                        break;

                                                tmpAdj[ei.Triangle].Add( new AdjEntry( ej.Triangle, i, j ) ); //should this be in here at all?
                                        }
                                }
                                
                                //pack tmpAdj down into a single array to save some space
                                values.Capacity = tris.Length;
                                entries.Capacity = numTris;

                                for( int t = 0; t < tmpAdj.Count; t++ )
                                {
                                        entries.Add( new TriEntry( values.Count, tmpAdj[t].Count ) );
                                        values.AddRange( tmpAdj[t] );
                                }
                        }
                }
        }
}