csg.cs

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

namespace CSG
{
    // Constructive Solid Geometry (CSG) is a modeling technique that uses Boolean
    // operations like union and intersection to combine 3D solids. This library
    // implements CSG operations on meshes elegantly and concisely using BSP trees,
    // and is meant to serve as an easily understandable implementation of the
    // algorithm. All edge cases involving overlapping coplanar polygons in both
    // solids are correctly handled.
    //
    // Example usage:
    //
    //     var cube = CSG.cube();
    //     var sphere = CSG.sphere({ radius: 1.3 });
    //     var polygons = cube.subtract(sphere).toPolygons();
    //
    // ## Implementation Details
    //
    // All CSG operations are implemented in terms of two functions, `clipTo()` and
    // `invert()`, which remove parts of a BSP tree inside another BSP tree and swap
    // solid and empty space, respectively. To find the union of `a` and `b`, we
    // want to remove everything in `a` inside `b` and everything in `b` inside `a`,
    // then combine polygons from `a` and `b` into one solid:
    //
    //     a.clipTo(b);
    //     b.clipTo(a);
    //     a.build(b.allPolygons());
    //
    // The only tricky part is handling overlapping coplanar polygons in both trees.
    // The code above keeps both copies, but we need to keep them in one tree and
    // remove them in the other tree. To remove them from `b` we can clip the
    // inverse of `b` against `a`. The code for union now looks like this:
    //
    //     a.clipTo(b);
    //     b.clipTo(a);
    //     b.invert();
    //     b.clipTo(a);
    //     b.invert();
    //     a.build(b.allPolygons());
    //
    // Subtraction and intersection naturally follow from set operations. If
    // union is `A | B`, subtraction is `A - B = ~(~A | B)` and intersection is
    // `A & B = ~(~A | ~B)` where `~` is the complement operator.
    //
    // ## License
    //
    // Copyright (c) 2011 Evan Wallace (http://madebyevan.com/), under the MIT license.


    public struct Options
    {
        public Vector3 center;
        public float radius;
        public int slices;
        public int stacks;
    }

    // # class CSG

    public class CSG
    {
        // Holds a binary space partition tree representing a 3D solid. Two solids can
        // be combined using the `union()`, `subtract()`, and `intersect()` methods.
        List<Polygon> polygons;

        // Construct a CSG solid from a list of `CSG.Polygon` instances.
        public static CSG FromPolygons(List<Polygon> polygons)
        {
            var csg = new CSG();
            csg.polygons = polygons;
            return csg;
        }

        public CSG Clone()
        {
            var csg = new CSG();
            csg.polygons = this.polygons.Select(p => p.Clone()).ToList();
            return csg;
        }

        public List<Polygon> ToPolygons() {
            return this.polygons;
        }

        public Mesh ToMesh()
        {
            Mesh newMesh = new Mesh();
            List<int> triangles = new List<int>(); List<Vector3> vertices = new List<Vector3>();
            int c = 0;
            foreach (Polygon poly in this.polygons)
            {
                vertices.AddRange(poly.vertices.Select(v => v.pos));
                triangles.AddRange(new int[6] { 0+c,1+c,3+c,1+c,2+c,3+c });

                Vector3[] crossed = new Vector3[poly.vertices.Count];
                for (int i=0; i<poly.vertices.Count; i++)
                {

                    //Quaternion.
                    //Camera.main.
                    //crossed[i] = Vector3.(poly.vertices[i].pos, poly.plane.normal);
                }
                c+=4;
            }
            newMesh.vertices = vertices.ToArray();
            newMesh.triangles = triangles.ToArray();

            return newMesh;
        }

        // Return a new CSG solid representing space in either this solid or in the
        // solid `csg`. Neither this solid nor the solid `csg` are modified.
        //
        //     A.union(B)
        //
        //     +-------+            +-------+
        //     |       |            |       |
        //     |   A   |            |       |
        //     |    +--+----+   =   |       +----+
        //     +----+--+    |       +----+       |
        //          |   B   |            |       |
        //          |       |            |       |
        //          +-------+            +-------+
        //
        public CSG Union(CSG csg)
        {
            var a = new Node(Clone().polygons);
            var b = new Node(csg.Clone().polygons);
            a.ClipTo(b);
            b.ClipTo(a);
            b.Invert();
            b.ClipTo(a);
            b.Invert();
            a.Build(b.AllPolygons());
            return CSG.FromPolygons(a.AllPolygons());
        }

        // Return a new CSG solid representing space in this solid but not in the
        // solid `csg`. Neither this solid nor the solid `csg` are modified.
        //
        //     A.subtract(B)
        //
        //     +-------+            +-------+
        //     |       |            |       |
        //     |   A   |            |       |
        //     |    +--+----+   =   |    +--+
        //     +----+--+    |       +----+
        //          |   B   |
        //          |       |
        //          +-------+
        //
        public CSG Subtract(CSG csg)
        {
            //var a = new CSG.Node(this.clone().polygons);
            //var b = new CSG.Node(csg.clone().polygons);
            //a.invert();
            //a.clipTo(b);
            //b.clipTo(a);
            //b.invert();
            //b.clipTo(a);
            //b.invert();
            //a.build(b.allPolygons());
            //a.invert();
            //return CSG.fromPolygons(a.allPolygons());
            return new CSG();
        }

        // Return a new CSG solid representing space both this solid and in the
        // solid `csg`. Neither this solid nor the solid `csg` are modified.
        //
        //     A.intersect(B)
        //
        //     +-------+
        //     |       |
        //     |   A   |
        //     |    +--+----+   =   +--+
        //     +----+--+    |       +--+
        //          |   B   |
        //          |       |
        //          +-------+
        //
        public CSG Intersect(CSG csg) {
            //var a = new CSG.Node(this.clone().polygons);
            //var b = new CSG.Node(csg.clone().polygons);
            //a.invert();
            //b.clipTo(a);
            //b.invert();
            //a.clipTo(b);
            //b.clipTo(a);
            //a.build(b.allPolygons());
            //a.invert();
            //return CSG.fromPolygons(a.allPolygons());
            return new CSG();
        }

        // Return a new CSG solid with solid and empty space switched. This solid is
        // not modified.
        public void Inverse()
        {
            //var csg = this.clone();
            //csg.polygons.map(function(p) { p.flip(); });
            //return csg;
        }

        // Construct an axis-aligned solid cuboid. Optional parameters are `center` and
        // `radius`, which default to `[0, 0, 0]` and `[1, 1, 1]`. The radius can be
        // specified using a single number or a list of three numbers, one for each axis.
        //
        // Example code:
        //
        //     var cube = CSG.cube({
        //       center: [0, 0, 0],
        //       radius: 1
        //     });
        public static CSG Cube(Options options)
        {
            Vector3 c, r;
            if (options.center!=null)
                c = options.center;
            else
                c = Vector3.zero;
            if (options.radius>0)
                r = new Vector3(options.radius, options.radius, options.radius);
            else
                r = new Vector3(1, 1, 1);

            Vertex[] vertices = new Vertex[8];
            for (int i=0; i<vertices.Length; i++)
            {
                vertices[i] = new Vertex( new Vector3 (
                c.x + r[0] * (((i & 1) == 1) ? 1 : -1 ),
                c.y + r[1] * (((i & 2) == 2) ? 1 : -1 ),
                c.z + r[2] * (((i & 4) == 4) ? 1 : -1 )),
                Vector3.zero);
            }
            int[,] indices = new int[6,4]
            {
                {0, 4, 6, 2},
                {1, 3, 7, 5},
                {0, 1, 5, 4},
                {2, 6, 7, 3},
                {0, 2, 3, 1},
                {4, 5, 7, 6},
            };
            Vector3[] shared = new Vector3[6]
            {
                new Vector3(-1, 0, 0),
                new Vector3(+1, 0, 0),
                new Vector3(0, -1, 0),
                new Vector3(0, +1, 0),
                new Vector3(0, 0, -1),
                new Vector3(0, 0, +1)
            };
            List<Polygon> polys = new List<Polygon>();
            for (int i=0; i<indices.GetLength(0); i++)
            {
                polys.Add(new Polygon( new List<Vertex>() {
                    vertices[indices[i,0]],
                    vertices[indices[i,1]],
                    vertices[indices[i,2]],
                    vertices[indices[i,3]]
                    }
                ));
            }
            return CSG.FromPolygons(polys);
        }

        // Construct a solid sphere. Optional parameters are `center`, `radius`,
        // `slices`, and `stacks`, which default to `[0, 0, 0]`, `1`, `16`, and `8`.
        // The `slices` and `stacks` parameters control the tessellation along the
        // longitude and latitude directions.
        //
        // Example usage:
        //
        //     var sphere = CSG.sphere({
        //       center: [0, 0, 0],
        //       radius: 1,
        //       slices: 16,
        //       stacks: 8
        //     });
        public static CSG Sphere(Options options) {/*
            options = options || {};
            var c = new CSG.Vector(options.center || [0, 0, 0]);
            var r = options.radius || 1;
            var slices = options.slices || 16;
            var stacks = options.stacks || 8;
            var polygons = [], vertices;
            function vertex(theta, phi) {
            theta *= Math.PI * 2;
            phi *= Math.PI;
            var dir = new CSG.Vector(
                Math.cos(theta) * Math.sin(phi),
                Math.cos(phi),
                Math.sin(theta) * Math.sin(phi)
            );
            vertices.push(new CSG.Vertex(c.plus(dir.times(r)), dir));
        }
        for (var i = 0; i < slices; i++) {
            for (var j = 0; j < stacks; j++) {
                vertices = [];
                vertex(i / slices, j / stacks);
                if (j > 0) vertex((i + 1) / slices, j / stacks);
                if (j < stacks - 1) vertex((i + 1) / slices, (j + 1) / stacks);
                    vertex(i / slices, (j + 1) / stacks);
                    polygons.push(new CSG.Polygon(vertices));
                }
            }
        return CSG.fromPolygons(polygons);*/
            return new CSG();
        }


        // Construct a solid cylinder. Optional parameters are `start`, `end`,
        // `radius`, and `slices`, which default to `[0, -1, 0]`, `[0, 1, 0]`, `1`, and
        // `16`. The `slices` parameter controls the tessellation.
        //
        // Example usage:
        //
        //     var cylinder = CSG.cylinder({
        //       start: [0, -1, 0],
        //       end: [0, 1, 0],
        //       radius: 1,
        //       slices: 16
        //     });
        public static CSG Cylinder(Options options)
        {
            /*options = options || {};
            var s = new CSG.Vector(options.start || [0, -1, 0]);
            var e = new CSG.Vector(options.end || [0, 1, 0]);
            var ray = e.minus(s);
            var r = options.radius || 1;
            var slices = options.slices || 16;
            var axisZ = ray.unit(), isY = (Math.abs(axisZ.y) > 0.5);
            var axisX = new CSG.Vector(isY, !isY, 0).cross(axisZ).unit();
            var axisY = axisX.cross(axisZ).unit();
            var start = new CSG.Vertex(s, axisZ.negated());
            var end = new CSG.Vertex(e, axisZ.unit());
            var polygons = [];
            function point(stack, slice, normalBlend) {
                var angle = slice * Math.PI * 2;
                var out = axisX.times(Math.cos(angle)).plus(axisY.times(Math.sin(angle)));
                var pos = s.plus(ray.times(stack)).plus(out.times(r));
                var normal = out.times(1 - Math.abs(normalBlend)).plus(axisZ.times(normalBlend));
                return new CSG.Vertex(pos, normal);
            }
            for (var i = 0; i < slices; i++) {
                var t0 = i / slices, t1 = (i + 1) / slices;
                polygons.push(new CSG.Polygon([start, point(0, t0, -1), point(0, t1, -1)]));
                polygons.push(new CSG.Polygon([point(0, t1, 0), point(0, t0, 0), point(1, t0, 0), point(1, t1, 0)]));
                polygons.push(new CSG.Polygon([end, point(1, t1, 1), point(1, t0, 1)]));
            }
            return CSG.fromPolygons(polygons);*/
            return new CSG();
        }
    }



    public enum PolygonType
    {
        COPLANAR =0,
        FRONT = 1,
        BACK = 2,
        SPANNING = 3
    }


    // # class Vertex

    // Represents a vertex of a polygon. Use your own vertex class instead of this
    // one to provide additional features like texture coordinates and vertex
    // colors. Custom vertex classes need to provide a `pos` property and `clone()`,
    // `flip()`, and `interpolate()` methods that behave analogous to the ones
    // defined by `CSG.Vertex`. This class provides `normal` so convenience
    // functions like `CSG.sphere()` can return a smooth vertex normal, but `normal`
    // is not used anywhere else.
    public class Vertex
    {
        public Vector3 pos;
        public Vector3 normal;

        public Vertex(Vector3 pos, Vector3 normal)
        {
            this.pos = pos;
            this.normal = normal;
        }

        public Vertex Clone()
        {
            return new Vertex(this.pos, this.normal);
        }

        // Invert all orientation-specific data (e.g. vertex normal). Called when the
        // orientation of a polygon is flipped.
        public void Flip()
        {
            normal = -normal;
        }
        // Create a new vertex between this vertex and `other` by linearly
        // interpolating all properties using a parameter of `t`. Subclasses should
        // override this to interpolate additional properties.
        public Vertex Interpolate(Vertex other, float t)
        {
            return new Vertex(Vector3.Lerp(this.pos, other.pos, t), Vector3.Lerp(this.normal, other.normal, t));
        }
    }


    // # class Plane

    // Represents a plane in 3D space.
    public class Plane
    {
        public Vector3 normal;
        public float w;

        public Plane(Vector3 normal, float w)
        {
            this.normal = normal;
            this.w = w;
        }

        // `CSG.Plane.EPSILON` is the tolerance used by `splitPolygon()` to decide if a
        // point is on the plane.
        public static float EPSILON = 1e-5f;

        public static Plane FromPoints(Vector3 a, Vector3 b, Vector3 c)
        {
            Vector3 n = Vector3.Cross((b-a), (c-a)).normalized;
            return new Plane(n, Vector3.Dot(n, a));
        }

        public Plane Clone()
        {
            return new Plane(this.normal ,this.w);
        }
        public void Flip()
        {
            normal = -normal;
            w = -w;
        }

        // Split `polygon` by this plane if needed, then put the polygon or polygon
        // fragments in the appropriate lists. Coplanar polygons go into either
        // `coplanarFront` or `coplanarBack` depending on their orientation with
        // respect to this plane. Polygons in front or in back of this plane go into
        // either `front` or `back`.
        public void SplitPolygon(Polygon polygon, ref List<Polygon> coplanar, ref List<Polygon> front, ref List<Polygon> back)
        {
            // Classify each point as well as the entire polygon into one of the above
            // four classes.
            PolygonType polygonType = PolygonType.COPLANAR;
            List<PolygonType> types = new List<PolygonType>();
            for (var i = 0; i < polygon.vertices.Count; i++) {
              var t = Vector3.Dot(this.normal, polygon.vertices[i].pos) - this.w;
              var type = (t < -Plane.EPSILON) ? PolygonType.BACK : (t > Plane.EPSILON) ? PolygonType.FRONT : PolygonType.COPLANAR;
              polygonType |= type;
              types.Add(type);
            }

            // Put the polygon in the correct list, splitting it when necessary.
            switch (polygonType) {
              case PolygonType.COPLANAR:
                if (Vector3.Dot(this.normal, polygon.plane.normal) > 0)
                    coplanar.Add(polygon);
                else
                    coplanar.Add(polygon);
                break;
              case PolygonType.FRONT:
                front.Add(polygon);
                break;
              case PolygonType.BACK:
                back.Add(polygon);
                break;
              case PolygonType.SPANNING:
                List<Vertex> f = new List<Vertex>(); List<Vertex> b = new List<Vertex>();
                for (var i = 0; i < polygon.vertices.Count; i++) {
                    var j = (i + 1) % polygon.vertices.Count;
                    PolygonType ti = types[i]; PolygonType tj = types[j];
                    Vertex vi = polygon.vertices[i]; Vertex vj = polygon.vertices[j];
                    if (ti != PolygonType.BACK)
                        f.Add(vi);
                    if (ti != PolygonType.FRONT)
                        b.Add(ti != PolygonType.BACK ? vi.Clone() : vi);
                    if ((ti | tj) == PolygonType.SPANNING) {
                        var t = (this.w - Vector3.Dot(this.normal, vi.pos)) / Vector3.Dot(this.normal, vj.pos-vi.pos);
                        var v = vi.Interpolate(vj, t);
                        f.Add(v);
                        b.Add(v.Clone());
                    }
                }
                    if (f.Count >= 3)
                        front.Add(new Polygon(f, polygon.shared));
                    if (b.Count >= 3)
                        back.Add(new Polygon(b, polygon.shared));
                    break;
                default:
                    break;
            }
        }

        public void SplitPolygon(Polygon polygon, ref List<Polygon> front, ref List<Polygon> back)
        {
            // Classify each point as well as the entire polygon into one of the above
            // four classes.
            PolygonType polygonType = PolygonType.COPLANAR;
            List<PolygonType> types = new List<PolygonType>();
            for (var i = 0; i < polygon.vertices.Count; i++) {
              var t = Vector3.Dot(this.normal, polygon.vertices[i].pos) - this.w;
              var type = (t < -Plane.EPSILON) ? PolygonType.BACK : (t > Plane.EPSILON) ? PolygonType.FRONT : PolygonType.COPLANAR;
              polygonType |= type;
              types.Add(type);
            }

            // Put the polygon in the correct list, splitting it when necessary.
            switch (polygonType) {
              case PolygonType.COPLANAR:
                if (Vector3.Dot(this.normal, polygon.plane.normal) > 0)
                    front.Add(polygon);
                else
                    back.Add(polygon);
                break;
              case PolygonType.FRONT:
                front.Add(polygon);
                break;
              case PolygonType.BACK:
                back.Add(polygon);
                break;
              case PolygonType.SPANNING:
                List<Vertex> f = new List<Vertex>(); List<Vertex> b = new List<Vertex>();
                for (var i = 0; i < polygon.vertices.Count; i++) {
                    var j = (i + 1) % polygon.vertices.Count;
                    PolygonType ti = types[i]; PolygonType tj = types[j];
                    Vertex vi = polygon.vertices[i]; Vertex vj = polygon.vertices[j];
                    if (ti != PolygonType.BACK)
                        f.Add(vi);
                    if (ti != PolygonType.FRONT)
                        b.Add(ti != PolygonType.BACK ? vi.Clone() : vi);
                    if ((ti | tj) == PolygonType.SPANNING) {
                        var t = (this.w - Vector3.Dot(this.normal, vi.pos)) / Vector3.Dot(this.normal, vj.pos-vi.pos);
                        var v = vi.Interpolate(vj, t);
                        f.Add(v);
                        b.Add(v.Clone());
                    }
                }
                    if (f.Count >= 3)
                        front.Add(new Polygon(f, polygon.shared));
                    if (b.Count >= 3)
                        back.Add(new Polygon(b, polygon.shared));
                    break;
                default:
                    break;
            }
        }
    }

    // # class Polygon

    // Represents a convex polygon. The vertices used to initialize a polygon must
    // be coplanar and form a convex loop. They do not have to be `CSG.Vertex`
    // instances but they must behave similarly (duck typing can be used for
    // customization).
    //
    // Each convex polygon has a `shared` property, which is shared between all
    // polygons that are clones of each other or were split from the same polygon.
    // This can be used to define per-polygon properties (such as surface color).
    public class Polygon
    {
        public List<Vertex> vertices;
        public Vector3 shared;
        public Plane plane;

        public Polygon(List<Vertex> vertices)
        {
            this.vertices = vertices;
            this.plane = Plane.FromPoints(vertices[0].pos, vertices[1].pos, vertices[2].pos);
        }
        public Polygon(List<Vertex> vertices, Vector3 shared)
        {
            this.vertices = vertices;
            this.shared = shared;
            this.plane = Plane.FromPoints(vertices[0].pos, vertices[1].pos, vertices[2].pos);
        }


        public Polygon Clone()
        {
            List<Vertex> vertices = this.vertices.Select(v => v.Clone()).ToList();
            return new Polygon(vertices);
        }

        public void Flip()
        {
            this.vertices.ForEach( v => v.Flip());
            this.plane.Flip();
        }
    }



    // # class Node

    // Holds a node in a BSP tree. A BSP tree is built from a collection of polygons
    // by picking a polygon to split along. That polygon (and all other coplanar
    // polygons) are added directly to that node and the other polygons are added to
    // the front and/or back subtrees. This is not a leafy BSP tree since there is
    // no distinction between internal and leaf nodes.

    public class Node
    {
        Plane plane;
        List<Polygon> polygons;
        Node front;
        Node back;

        public Node(List<Polygon> polygons)
        {
            this.plane = null;
            this.front = null;
            this.back = null;
            this.polygons = new List<Polygon>();
            if (polygons.Count>0)
                Build(polygons);
        }
        public Node()
        {
            this.plane = null;
            this.front = null;
            this.back = null;
            this.polygons = new List<Polygon>();
        }
        public Node Clone()
        {
            Node node = new Node(polygons);
            node.plane = plane.Clone();
            node.front = front.Clone();
            node.back = back.Clone();
            node.polygons = polygons.Select(p => p.Clone()).ToList();
            return node;
        }

        public void Invert()
        {
            for (var i = 0; i < polygons.Count; i++) {
              polygons[i].Flip();
            }
            this.plane.Flip();
            if (front!=null) this.front.Invert();
            if (back!=null) this.back.Invert();
            var temp = this.front;
            this.front = this.back;
            this.back = temp;
        }


        // Recursively remove all polygons in `polygons` that are inside this BSP
        // tree.
        public List<Polygon> ClipPolygons(List<Polygon> polygons)
        {
            if (polygons!=null)
            {
                if (polygons.Count<1)
                    return new List<Polygon>();
            }
            else
            {
                return new List<Polygon>();
            }
            if (plane==null) return new List<Polygon>();
            List<Polygon> front = new List<Polygon>();
            List<Polygon> back = new List<Polygon>();
            for (var i = 0; i < polygons.Count; i++) {
              this.plane.SplitPolygon(polygons[i], ref front, ref back);
            }
            if (this.front!=null)
                front = this.front.ClipPolygons(front);
            if (this.back!=null)
                back = this.back.ClipPolygons(back);
            else
                back = new List<Polygon>();
            return front.Concat(back).ToList();
        }

        // Remove all polygons in this BSP tree that are inside the other BSP tree
        // `bsp`.
        public void ClipTo(Node bsp)
        {
            this.polygons = bsp.ClipPolygons(this.polygons);
            if (this.front!=null)
                this.front.ClipTo(bsp);
            if (this.back!=null)
                this.back.ClipTo(bsp);
        }

        // Return a list of all polygons in this BSP tree.
        public List<Polygon> AllPolygons()
        {
            var polygons = this.polygons;
            if (this.front!=null) polygons = polygons.Concat(this.front.AllPolygons()).ToList();
            if (this.back!=null) polygons = polygons.Concat(this.back.AllPolygons()).ToList();
            return polygons;
        }

        // Build a BSP tree out of `polygons`. When called on an existing tree, the
        // new polygons are filtered down to the bottom of the tree and become new
        // nodes there. Each set of polygons is partitioned using the first polygon
        // (no heuristic is used to pick a good split).
        public void Build(List<Polygon> polygons) {
            if (polygons.Count==0) return;
            if (this.plane==null) this.plane = polygons[0].plane.Clone();
            List<Polygon> front = new List<Polygon>();
            List<Polygon> back = new List<Polygon>();
            for (var i = 0; i < polygons.Count; i++) {
            this.plane.SplitPolygon(polygons[i], ref this.polygons, ref front, ref back);
            }
            if (front.Count>0) {
                if (this.front==null)
                    this.front = new Node();
                this.front.Build(front);
            }
            if (back.Count>0) {
                if (this.back==null)
                    this.back = new Node();
                this.back.Build(back);
            }
        }
    }
}