source: OniSplit/Akira/RoomGridBuilder.cs@ 1124

using System;
using System.Collections.Generic;
using System.IO;
using Oni.Collections;
using Oni.Imaging;

namespace Oni.Akira
{
    internal class RoomGridBuilder
    {
        private readonly Dae.Scene roomsScene;
        private readonly PolygonMesh geometryMesh;
        private PolygonMesh roomsMesh;
        private OctreeNode geometryOcttree;
        private OctreeNode dangerOcttree;

        public RoomGridBuilder(Dae.Scene roomsScene, PolygonMesh geometryMesh)
        {
            this.roomsScene = roomsScene;
            this.geometryMesh = geometryMesh;
        }

        public PolygonMesh Mesh => roomsMesh;

        public void Build()
        {
            roomsMesh = RoomDaeReader.Read(roomsScene);

            RoomBuilder.BuildRooms(roomsMesh);

            Console.Error.WriteLine("Read {0} rooms", roomsMesh.Rooms.Count);

            geometryOcttree = OctreeBuilder.Build(geometryMesh, GunkFlags.NoCollision | GunkFlags.NoCharacterCollision);
            dangerOcttree = OctreeBuilder.Build(geometryMesh, p => (p.Flags & GunkFlags.Danger) != 0);

            ProcessStairsCollision();

            Parallel.ForEach(roomsMesh.Rooms, room =>
            {
                BuildGrid(room);
            });
        }

        private void ProcessStairsCollision()
        {
            var verticalTolerance1 = new Vector3(0.0f, 0.1f, 0.0f);
            var verticalTolerance2 = new Vector3(0.0f, 7.5f, 0.0f);

            foreach (var stairs in geometryMesh.Polygons.Where(p => p.IsStairs && p.VertexCount == 4))
            {
                var floorPoints = stairs.Points.Select(v => v + verticalTolerance1).ToArray();
                var ceilPoints = stairs.Points.Select(v => v + verticalTolerance2).ToArray();
                var bbox = BoundingBox.CreateFromPoints(floorPoints.Concatenate(ceilPoints));

                var floorPlane = new Plane(floorPoints[0], floorPoints[1], floorPoints[2]);
                var ceilingPlane = new Plane(ceilPoints[0], ceilPoints[1], ceilPoints[2]);

                foreach (var node in geometryOcttree.FindLeafs(bbox))
                {
                    foreach (var poly in node.Polygons)
                    {
                        if ((poly.Flags & (GunkFlags.NoCollision | GunkFlags.NoCharacterCollision)) != 0)
                        {
                            //
                            // already a no collision polygon, skip it
                            //

                            continue;
                        }

                        if (!poly.BoundingBox.Intersects(bbox))
                            continue;

                        var points = poly.Points.ToList();

                        points = PolygonUtils.ClipToPlane(points, floorPlane);

                        if (points == null)
                        {
                            //
                            // this polygon is below stairs, skip it
                            //

                            continue;
                        }

                        points = PolygonUtils.ClipToPlane(points, ceilingPlane);

                        if (points != null)
                        {
                            //
                            // this polygon is too high above the stairs, skip it
                            //

                            continue;
                        }

                        poly.Flags |= GunkFlags.NoCharacterCollision;
                    }
                }
            }
        }

        private void BuildGrid(Room room)
        {
            var floor = room.FloorPolygon;
            var bbox = room.BoundingBox;

            //
            // Create an empty grid and mark all tiles as 'danger'
            //

            var rasterizer = new RoomGridRasterizer(bbox);
            rasterizer.Clear(RoomGridWeight.Danger);

            //
            // Collect all polygons that intersect the room
            // 

            bbox.Inflate(2.0f * new Vector3(rasterizer.TileSize, 0.0f, rasterizer.TileSize));

            var testbox = bbox;
            testbox.Min.X -= 1.0f;
            testbox.Min.Y = bbox.Min.Y - 6.0f;
            testbox.Min.Z -= 1.0f;
            testbox.Max.X += 1.0f;
            testbox.Max.Y = bbox.Max.Y - 6.0f;
            testbox.Max.Z += 1.0f;

            var polygons = new Set<Polygon>();
            var dangerPolygons = new Set<Polygon>();

            foreach (var node in geometryOcttree.FindLeafs(testbox))
            {
                polygons.UnionWith(node.Polygons);
            }

            foreach (var node in dangerOcttree.FindLeafs(testbox))
            {
                dangerPolygons.UnionWith(node.Polygons);
            }

            //
            // Draw all the floors on the grid. This will overwrite the 'danger'
            // areas with 'clear' areas. This means danger area will remain
            // where there isn't any floor.
            //

            foreach (var polygon in polygons)
            {
                if (polygon.Plane.Normal.Y > 0.5f)
                    rasterizer.DrawFloor(polygon.Points);
            }

            if (room.FloorPlane.Normal.Y >= 0.999f)
            {
                //
                // Draw the walls.
                //

                float floorMaxY = floor.BoundingBox.Max.Y;
                var floorPlane = new Plane(floor.Plane.Normal, floor.Plane.D - 4.0f);
                var ceilingPlane = new Plane(-floor.Plane.Normal, -(floor.Plane.D - 20.0f));

                foreach (var polygon in polygons)
                {
                    if ((polygon.Flags & (GunkFlags.Stairs | GunkFlags.NoCharacterCollision | GunkFlags.Impassable)) == 0)
                    {
                        //
                        // Remove curbs from character collision.
                        //

                        var polyBox = polygon.BoundingBox;

                        if (Math.Abs(polygon.Plane.Normal.Y) < MathHelper.Eps
                            && polyBox.Height <= 4.0f
                            && Math.Abs(polyBox.Max.Y - floorMaxY) <= 4.0f)
                        {
                            polygon.Flags |= GunkFlags.NoCharacterCollision;
                            continue;
                        }
                    }

                    if ((polygon.Flags & (GunkFlags.Stairs | GunkFlags.GridIgnore | GunkFlags.NoCollision | GunkFlags.NoCharacterCollision)) != 0)
                        continue;

                    var points = polygon.Points.ToList();

                    points = PolygonUtils.ClipToPlane(points, floorPlane);

                    if (points == null)
                        continue;

                    points = PolygonUtils.ClipToPlane(points, ceilingPlane);

                    if (points == null)
                        continue;

                    if (Math.Abs(polygon.Plane.Normal.Y) <= 0.1f)
                        rasterizer.DrawWall(points);
                    else
                        rasterizer.DrawImpassable(points);
                }

                //
                // Draw ramp entry/exit lines. Hmm, this seems useless.
                //

                //if (room.FloorPlane.Normal.Y >= 0.98f)
                //{
                //    foreach (RoomAdjacency adj in room.Ajacencies)
                //    {
                //        if (Math.Abs(room.FloorPlane.Normal.Y - adj.AdjacentRoom.FloorPlane.Normal.Y) > 0.001f)
                //            rasterizer.DrawStairsEntry(adj.Ghost.Points);
                //    }
                //}

                //
                // Draw 'danger' quads.
                //

                foreach (var polygon in dangerPolygons)
                {
                    rasterizer.DrawDanger(polygon.Points);
                }

                //
                // Draw 'near wall' borders.
                //

                rasterizer.AddBorders();
            }

            //
            // Finally, get the rasterized pathfinding grid.
            //

            room.Grid = rasterizer.GetGrid();

            if (room.Grid.XTiles * room.Grid.ZTiles > 256 * 256)
                Console.Error.WriteLine("Warning: pathfinding grid too large");
        }
    }
}