Legacy geodesic grid code released under BSD 2-Clause

GeodesicGrid.cs

/**
 * Copyright (c) 2012-2013, Majiir
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without modification, are permitted 
 * provided that the following conditions are met:
 * 
 * 1. Redistributions of source code must retain the above copyright notice, this list of 
 * conditions and the following disclaimer.
 * 
 * 2. Redistributions in binary form must reproduce the above copyright notice, this list of 
 * conditions and the following disclaimer in the documentation and/or other materials provided 
 * with the distribution.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR 
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
 * FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR 
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 
 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR 
 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 
 * POSSIBILITY OF SUCH DAMAGE.
 */
 
 // Original modification history available at:
 // https://github.com/Majiir/Kethane/commits/9db0ebac9a166dbd53aac03bd93d281a65004e0e/Plugin/GeodesicGrid.cs

using System;
using System.Collections.Generic;
using System.Linq;
using UnityEngine;

namespace Kethane
{
    internal class GeodesicGrid : IEnumerable<GeodesicGrid.Cell>, IEquatable<GeodesicGrid>
    {
        private readonly int n;

        private Cell.Map<Vector3> positions;

        /// <summary>
        /// Creates a new geodesic grid with the given number of triangle subdivisions.
        /// </summary>
        /// <param name="subdivisions">Number of times to subdivide triangles.</param>
        public GeodesicGrid(int subdivisions)
        {
            this.n = 1 << subdivisions;
            this.positions = new Cell.Map<Vector3>(subdivisions);

            var cache = new Cell.Dictionary<Vector3d>(subdivisions);
            foreach (var cell in this)
            {
                positions[cell] = (Vector3)cell.GetPosition(cache);
            }
        }

        /// <summary>
        /// Gets the number of cells in the grid.
        /// </summary>
        public int Count
        {
            get { return 10 * n * n + 2; }
        }

        public int Subdivisions
        {
            get { return (int)Math.Log(n, 2); }
        }

        public int SideLength
        {
            get { return n; }
        }

        public IEnumerator<Cell> GetEnumerator()
        {
            yield return new Cell(0, -1, 0, this);

            for (int x = 0; x < 5; x++)
            {
                for (int y = 0; y < 2 * n; y++)
                {
                    for (int z = 0; z < n; z++)
                    {
                        yield return new Cell(x, y, z, this);
                    }
                }
            }

            yield return new Cell(0, 2 * n - 1, n, this);
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { return GetEnumerator(); }

        /// <summary>
        /// Finds the cell closest to the given vector.
        /// </summary>
        /// <param name="line">Direction vector relative to the grid.</param>
        /// <returns>Cell on this grid which contains the given direction.</returns>
        /// <remarks>This function performs a best-first search starting with the pentagonal cells and then the neighbors of each iterated cell.</remarks>
        public Cell NearestCell(Vector3 line)
        {
            line = line.normalized;
            Cell head = this.Pentagons.WithMin(c => (c.Position - line).magnitude);
            Cell best;

            do
            {
                best = head;
                head = head.Neighbors.Prepend(head).WithMin(c => (c.Position - line).magnitude);
            } while (head != best);

            return head;
        }

        public IEnumerable<Cell> Pentagons
        {
            get
            {
                yield return new Cell(0, -1, 0, this);
                for (int x = 0; x < 5; x++)
                {
                    yield return new Cell(x, n - 1, 0, this);
                    yield return new Cell(x, 2 * n - 1, 0, this);
                }
                yield return new Cell(0, 2 * n - 1, n, this);
            }
        }

        #region Standard overrides

        public override bool Equals(object obj)
        {
            if (obj.GetType() != typeof(GeodesicGrid)) { return false; }
            return Equals((GeodesicGrid)obj);
        }

        public bool Equals(GeodesicGrid other)
        {
            return n == other.n;
        }

        public override int GetHashCode()
        {
            return n;
        }

        #endregion

        public struct Cell : IEquatable<Cell>
        {
            public int X { get; private set; }
            public int Y { get; private set; }
            public int Z { get; private set; }

            private readonly GeodesicGrid grid;

            public Cell(int x, int y, int z, GeodesicGrid grid)
                : this()
            {
                this.grid = grid;
                int n = grid.n;

                if (z < -1 || y < -1 || z > n || y > 2 * n)
                {
                    throw new ArgumentOutOfRangeException();
                }

                if (y == -1)
                {
                    if (z == 0)
                    {
                        x = 0;
                    }
                    else if (z == -1)
                    {
                        throw new ArgumentOutOfRangeException();
                    }
                    else
                    {
                        x = x - 1;
                        y = z - 1;
                        z = 0;
                    }
                }
                else if (z == -1)
                {
                    x = x + 1;
                    if (y < n)
                    {
                        z = y;
                        y = 0;
                    }
                    else
                    {
                        y = y - n;
                        z = n - 1;
                    }
                }
                else if (y == 2 * n)
                {
                    if (z == n)
                    {
                        throw new ArgumentOutOfRangeException();
                    }
                    x = x + 1;
                    y = n + z;
                    z = n - 1;
                }
                else if (z == n)
                {
                    if (y < n)
                    {
                        x = x - 1;
                        y = y + n;
                        z = 0;
                    }
                    else if (y < 2 * n - 1)
                    {
                        x = x - 1;
                        z = y - n + 1;
                        y = 2 * n - 1;
                    }
                    else
                    {
                        x = 4;
                    }
                }

                x %= 5;
                if (x < 0) { x += 5; }

                X = x;
                Y = y;
                Z = z;
            }

            /// <summary>
            /// Constructs a cell with the same hash code as the given parameter.
            /// </summary>
            public Cell(int i, GeodesicGrid grid)
            {
                if (i < 0 || i >= grid.Count) { throw new ArgumentOutOfRangeException(); }

                if (i == 0)
                {
                    this = new Cell(0, -1, 0, grid);
                }
                else if (i == grid.Count - 1)
                {
                    this = new Cell(0, 2 * grid.n - 1, grid.n, grid);
                }
                else
                {
                    i -= 1;
                    var x = i / (grid.n * grid.n * 2);
                    i -= grid.n * grid.n * 2 * x;
                    var y = i / grid.n;
                    var z = i - grid.n * y;
                    this = new Cell(x, y, z, grid);
                }
            }

            public bool IsNorth
            {
                get { return (Y == -1) && (Z == 0); }
            }

            public bool IsSouth
            {
                get
                {
                    int n = grid.n;
                    return (Z == n) && (Y == 2 * n - 1);
                }
            }

            /// <summary>
            /// Gets whether this cell is one of the twelve pentagonal cells.
            /// </summary>
            public bool IsPentagon
            {
                get
                {
                    int n = grid.n;
                    return Z % n == 0 && (Y + 1) % n == 0;
                }
            }

            public IEnumerable<Cell> Neighbors
            {
                get
                {
                    if (IsNorth)
                    {
                        for (int x = 0; x < 5; x++)
                        {
                            yield return new Cell(x, Y + 1, Z, grid);
                        }
                    }
                    else if (IsSouth)
                    {
                        for (int x = 4; x >= 0; x--)
                        {
                            yield return new Cell(x, Y - 1, Z, grid);
                        }
                    }
                    else
                    {
                        var neighbors = new Cell[] {
                            new Cell(X, Y - 1, Z,     grid),
                            new Cell(X, Y - 1, Z + 1, grid),
                            new Cell(X, Y,     Z + 1, grid),
                            new Cell(X, Y + 1, Z,     grid),
                            new Cell(X, Y + 1, Z - 1, grid),
                            new Cell(X, Y,     Z - 1, grid)
                        };
                        foreach (var cell in neighbors.Distinct())
                        {
                            yield return cell;
                        }
                    }
                }
            }

            #region Cell position

            /// <summary>
            /// Gets the position of the Cell on the unit sphere.
            /// </summary>
            public Vector3 Position
            {
                get { return grid.positions[this]; }
            }

            public Vector3d GetPosition(Cell.Dictionary<Vector3d> cache)
            {
                if (!cache.ContainsKey(this))
                {
                    cache[this] = getPosition(cache);
                }
                return cache[this];
            }

            private Vector3d getPosition(Cell.Dictionary<Vector3d> cache)
            {
                if (IsPentagon)
                {
                    if (IsNorth) { return new Vector3d(0, 1, 0); }
                    if (IsSouth) { return new Vector3d(0, -1, 0); }

                    int n = grid.n;
                    var lat = Math.Atan(0.5);
                    var lon = X * 2 * Math.PI / 5;
                    if (Y == 2 * n - 1)
                    {
                        lat = -lat;
                        lon += Math.PI / 5;
                    }
                    return new Vector3d(Math.Cos(lat) * Math.Cos(lon), Math.Sin(lat), Math.Cos(lat) * Math.Sin(lon));
                }
                else
                {
                    var first = getFirstParent();
                    var second = getSecondParent(first);
                    return (first.GetPosition(cache) + second.GetPosition(cache)).normalized;
                }
            }

            private Cell getFirstParent()
            {
                var s = getParentDistance() * 2;
                return new Cell(X, Y + (Y + 1) % s, Z - Z % s, grid);
            }

            private Cell getSecondParent(Cell parent)
            {
                return new Cell(X, 2 * Y - parent.Y, 2 * Z - parent.Z, grid);
            }

            /// <summary>
            /// Gets the distance to this cell's recursion parents, or if this cell is a pentagon, the distance to a neighboring pentagon.
            /// </summary>
            private int getParentDistance()
            {
                var s = Y + 1 | Z | grid.n;
                return s & -s;
            }

            #endregion

            #region Standard overrides

            public override string ToString()
            {
                return String.Format("({0}, {1}, {2})", X, Y, Z);
            }

            public override bool Equals(object obj)
            {
                if (obj is Cell) { return Equals((Cell)obj); }
                return false;
            }

            public bool Equals(Cell other)
            {
                if (X != other.X) { return false; }
                if (Y != other.Y) { return false; }
                if (Z != other.Z) { return false; }
                return grid.Equals(other.grid);
            }

            /// <summary>
            /// Minimal perfect hash function suitable for use as an array index.
            /// </summary>
            /// <returns>Zero-based index of the Cell.</returns>
            public override int GetHashCode()
            {
                if (IsNorth) { return 0; }
                return 1 + Z + grid.n * (Y + 2 * grid.n * X);
            }

            public static bool operator ==(Cell a, Cell b) { return a.Equals(b); }

            public static bool operator !=(Cell a, Cell b) { return !(a == b); }

            #endregion

            #region Dictionary

            public class Dictionary<T>
            {
                private Map<T> values;
                private Set set;

                public Dictionary(int subdivisions)
                {
                    set = new Set(subdivisions);
                    values = new Map<T>(subdivisions);
                }

                public T this[GeodesicGrid.Cell cell]
                {
                    get
                    {
                        if (!set[cell]) { throw new KeyNotFoundException(); }
                        return values[cell];
                    }
                    set
                    {
                        set[cell] = true;
                        values[cell] = value;
                    }
                }

                public bool ContainsKey(GeodesicGrid.Cell cell)
                {
                    return set[cell];
                }
            }

            #endregion

            #region Set

            public class Set
            {
                private System.Collections.BitArray set;

                public Set(int subdivisions)
                {
                    var n = 1 << subdivisions;
                    set = new System.Collections.BitArray(10 * n * n + 2);
                }

                public Set(int subdivisions, byte[] array)
                {
                    var n = 1 << subdivisions;
                    set = new System.Collections.BitArray(array);
                    set.Length = 10 * n * n + 2;
                }

                public bool this[GeodesicGrid.Cell cell]
                {
                    get
                    {
                        if (cell.grid.Count != set.Length) { throw new ArgumentException(); }
                        return set[cell.GetHashCode()];
                    }
                    set
                    {
                        if (cell.grid.Count != set.Length) { throw new ArgumentException(); }
                        set[cell.GetHashCode()] = value;
                    }
                }

                public int Length
                {
                    get { return set.Length; }
                }

                public byte[] ToByteArray()
                {
                    return set.ToByteArray();
                }
            }

            #endregion

            #region Map

            public class Map<T>
            {
                private T[] values;

                public Map(int subdivisions)
                {
                    var n = 1 << subdivisions;
                    values = new T[10 * n * n + 2];
                }

                public T this[Cell cell]
                {
                    get
                    {
                        if (cell.grid.Count != values.Length) { throw new ArgumentException(); }
                        return values[cell.GetHashCode()];
                    }
                    set
                    {
                        if (cell.grid.Count != values.Length) { throw new ArgumentException(); }
                        values[cell.GetHashCode()] = value;
                    }
                }
            }

            #endregion
        }
    }
}