source: OniSplit/Akira/AlphaBspBuilder.cs@ 1148

using System;
using System.Collections.Generic;

namespace Oni.Akira
{
    internal class AlphaBspBuilder
    {
        private PolygonMesh mesh;
        private bool debug;

        public static AlphaBspNode Build(PolygonMesh mesh, bool debug)
        {
            var builder = new AlphaBspBuilder
            {
                mesh = mesh,
                debug = debug
            };

            return builder.Build();
        }

        private AlphaBspNode Build()
        {
            var transparent = new List<Polygon>(1024);

            transparent.AddRange(mesh.Polygons.Where(p => p.IsTransparent));

            if (debug)
                transparent.AddRange(mesh.Ghosts.Where(p => p.IsTransparent));

            Console.Error.WriteLine("Building bsp tree for {0} transparent polygons...", transparent.Count);
            return Build(transparent);
        }

        private AlphaBspNode Build(List<Polygon> polygons)
        {
            if (polygons.Count == 0)
                return null;

            var separator = polygons[0].Plane;
            AlphaBspNode frontNode = null, backNode = null;

            if (polygons.Count > 1)
            {
                var front = new List<Polygon>(polygons.Count);
                var back = new List<Polygon>(polygons.Count);

                for (int i = 1; i < polygons.Count; i++)
                {
                    var polygon = polygons[i];
                    var plane = polygon.Plane;

                    bool isFront = false;
                    bool isBack = false;

                    if (Math.Abs(plane.D - separator.D) < 0.001f
                        && Vector3.Distance(plane.Normal, separator.Normal) < 0.001f)
                    {
                        isFront = true;
                    }
                    else
                    {
                        foreach (var point in polygon.Points)
                        {
                            if (separator.DotCoordinate(point) > 0.0f)
                                isFront = true;
                            else
                                isBack = true;
                        }
                    }

                    if (isFront)
                        front.Add(polygon);

                    if (isBack)
                        back.Add(polygon);
                }

                frontNode = Build(front);
                backNode = Build(back);
            }

            return new AlphaBspNode(polygons[0], frontNode, backNode);
        }
    }
}