source: OniSplit/Akira/RoomBuilder.cs

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

namespace Oni.Akira
{
    internal class RoomBuilder
    {
        private const float roomHeight = 20.0f;
        private readonly PolygonMesh mesh;
        private OctreeNode octtree;

        public static void BuildRooms(PolygonMesh mesh)
        {
            var builder = new RoomBuilder(mesh);
            builder.BuildRooms();
        }

        private RoomBuilder(PolygonMesh mesh)
        {
            this.mesh = mesh;
        }

        private void BuildRooms()
        {
            foreach (Polygon floor in mesh.Floors)
                mesh.Rooms.Add(CreateRoom(floor, roomHeight));

            ConnectRooms();
            UpdateRoomsHeight();
        }

        private Room CreateRoom(Polygon floor, float height)
        {
            var floorPlane = floor.Plane;

            var bbox = floor.BoundingBox;
            bbox.Max.Y += height * floorPlane.Normal.Y;

            var room = new Room
            {
                FloorPolygon = floor,
                BoundingBox = bbox,
                FloorPlane = floor.Plane,
                Height = height * floorPlane.Normal.Y,
                BspTree = BuildBspTree(floor, height * floorPlane.Normal.Y)
            };

            if (floor.Material != null)
                room.Grid = CreateRoomGrid(floor);

            return room;
        }

        private static RoomBspNode BuildBspTree(Polygon floor, float height)
        {
            var points = floor.Points.ToArray();
            var floorPlane = floor.Plane;

            var bottom = new Plane(-floorPlane.Normal, -floorPlane.D);
            var node = new RoomBspNode(bottom, null, null);

            var top = new Plane(floorPlane.Normal, floorPlane.D - height);
            node = new RoomBspNode(top, node, null);

            for (int i = 0; i < points.Length; i++)
            {
                var p0 = points[i];
                var p1 = points[(i + 1) % points.Length];
                var p2 = p1 + Vector3.Up;

                node = new RoomBspNode(new Plane(p0, p1, p2), node, null);
            }

            return node;
        }

        private static RoomGrid CreateRoomGrid(Polygon floor)
        {
            if (!File.Exists(floor.Material.ImageFilePath))
                return null;

            var image = TgaReader.Read(floor.Material.ImageFilePath);
            var grid = RoomGrid.FromImage(image);

            //BoundingBox bbox = floor.GetBoundingBox();

            //
            // TODO: don't use hardcoded constants
            //

            //int gx = (int)(((bbox.Max.X - bbox.Min.X) / 4) + 5);
            //int gz = (int)(((bbox.Max.Z - bbox.Min.Z) / 4) + 5);

            //if (gx != image.Width || gz != image.Height)
            //{
            //    //Console.Error.WriteLine("Warning: Grid {0} has wrong size, expecting {1}x{2}, got {3}x{4}",
            //    //    floor.Material.Name,
            //    //    gx, gz,
            //    //    image.Width, image.Height);
            //}

            return grid;
        }

        private void ConnectRooms()
        {
            octtree = OctreeBuilder.BuildRoomsOctree(mesh);

            foreach (Polygon ghost in mesh.Ghosts)
            {
                float minY = ghost.Points.Select(p => p.Y).Min();
                Vector3[] points = ghost.Points.Where(p => Math.Abs(p.Y - minY) <= 0.1f).ToArray();

                if (points.Length != 2)
                {
                    Console.Error.WriteLine("BNV Builder: Bad ghost, it must have 2 lowest points, it has {0}, ignoring", points.Length);
                    continue;
                }

                Vector3 mid = (points[0] + points[1]) / 2.0f;
                Vector3 normal = ghost.Plane.Normal;

                Vector3 p0 = mid - normal + Vector3.Up * 2.0f;
                Vector3 p1 = mid + normal + Vector3.Up * 2.0f;

                RoomPair pair = PairRooms(p0, p1);

                if (pair == null)
                {
                    Console.WriteLine("BNV Builder: Ghost '{0}' has no adjacencies at {1} and {2}, ignoring", ghost.ObjectName, p0, p1);
                    continue;
                }

                if (pair.Room0.IsStairs || pair.Room1.IsStairs)
                {
                    var stairs = pair.Room0;

                    if (!stairs.IsStairs)
                        stairs = pair.Room1;

                    ghost.Flags &= ~GunkFlags.Ghost;

                    if (ghost.Material != null)
                        ghost.Material.Flags &= ~GunkFlags.Ghost;

                    if (ghost.BoundingBox.Min.Y > stairs.FloorPolygon.BoundingBox.Max.Y - 1.0f)
                        ghost.Flags |= GunkFlags.StairsDown;
                    else
                        ghost.Flags |= GunkFlags.StairsUp;
                }
                else
                {
                    ghost.Flags |= GunkFlags.Ghost;
                }

                pair.Room1.Ajacencies.Add(new RoomAdjacency(pair.Room0, ghost));
                pair.Room0.Ajacencies.Add(new RoomAdjacency(pair.Room1, ghost));
            }
        }

        #region private class RoomPair

        private class RoomPair : IComparable<RoomPair>
        {
            public readonly Room Room0;
            public readonly Room Room1;
            public readonly float HeightDelta;
            public readonly float VolumeDelta;

            public RoomPair(Room r0, Vector3 p0, Room r1, Vector3 p1)
            {
                Room0 = r0;
                Room1 = r1;
                HeightDelta = r0.FloorPlane.DotCoordinate(p0) - r1.FloorPlane.DotCoordinate(p1);
                VolumeDelta = r0.BoundingBox.Volume() - r1.BoundingBox.Volume();
            }

            int IComparable<RoomPair>.CompareTo(RoomPair other)
            {
                if (Math.Abs(HeightDelta - other.HeightDelta) < 1e-5f)
                    return VolumeDelta.CompareTo(other.VolumeDelta);
                else if (HeightDelta < other.HeightDelta)
                    return -1;
                else
                    return 1;
            }
        }

        #endregion

        private RoomPair PairRooms(Vector3 p0, Vector3 p1)
        {
            var pairs = new List<RoomPair>();

            var rooms0 = FindRooms(p0);
            var rooms1 = FindRooms(p1);

            foreach (Room r0 in rooms0)
            {
                foreach (Room r1 in rooms1)
                {
                    if (r0 != r1)
                        pairs.Add(new RoomPair(r0, p0, r1, p1));
                }
            }

            pairs.Sort();

            return pairs.Count > 0 ? pairs[0] : null;
        }

        private List<Room> FindRooms(Vector3 point)
        {
            var rooms = new List<Room>();

            var node = octtree.FindLeaf(point);

            if (node != null)
            {
                foreach (var room in node.Rooms)
                {
                    if (room.Contains(point))
                        rooms.Add(room);
                }
            }

            return rooms;
        }

        /// <summary>
        /// Set the height of the room to the max height of adjacencies.
        /// </summary>
        private void UpdateRoomsHeight()
        {
            foreach (var room in mesh.Rooms)
            {
                float maxFloorY = room.FloorPolygon.Points.Max(p => p.Y);
                float maxRoomY;

                if (room.Ajacencies.Count == 0)
                    maxRoomY = maxFloorY + 20.0f;
                else
                    maxRoomY = room.Ajacencies.Max(a => a.Ghost.Points.Max(p => p.Y));

                var bbox = room.FloorPolygon.BoundingBox;
                bbox.Max.Y = maxRoomY;

                room.BoundingBox = bbox;
                room.Height = (maxRoomY - maxFloorY) * room.FloorPlane.Normal.Y;
                room.BspTree = BuildBspTree(room.FloorPolygon, room.Height);
            }
        }
    }
}