Fast BIM Room Extraction

Beginning with an untagged, multi-million-triangle mesh, the algorithm first merges nearly coplanar facets into large planes, distinguishing vertical walls from horizontal slabs. Each floor is isolated by height, and wall edges are projected onto it; after snapping near-miss corners together and temporarily bridging door-sized gaps, a 2-D planar graph emerges whose closed loops mark room footprints. Each footprint is then extruded and successively clipped by its own wall, floor and ceiling planes, yielding a clean, watertight polyhedron of only a handful of faces. A BVH-accelerated visibility flood-fill through sampled free space confirms that every volume truly encloses air; leaking candidates are dropped, and any overlooked voids are wrapped in a quick alpha-shape hull. Finally, coplanar faces are fused, sliver edges collapsed, openings capped and shared walls duplicated, leaving a compact, independent shell for every room—produced deterministically, without voxels, AI or external geometry libraries, and able to turn ten-million-triangle inputs into hundreds of real-time-ready volumes in mere seconds.

Common Questions

Q: What’s the end product?
- A watertight, low-poly polyhedron for every room, suitable for navigation, daylight and energy analyses.

Q: How are walls and floors detected?
- By clustering nearly coplanar triangles into large planes—vertical patches become walls, horizontals become slabs.

Q: How is each room volume built?
- Project wall edges to 2-D to trace a closed footprint, extrude it, then clip the prism with its wall, floor and ceiling planes.

Q: How do you catch leaks or missed voids?
- A visibility flood-fill marks exterior air; any leaking shell is dropped, and any unclaimed void is wrapped in a quick hull.

Q: How big and fast is it?
- Runs in 𝑂(𝑛 log 𝑛); a 10-million-triangle model converts to hundreds of room shells in seconds on a desktop.
Contact Elf.3D to explore how custom mesh processing algorithms might address your unique challenges. We approach every conversation with curiosity about your specific needs rather than generic solutions.

*Interested in discussing your mesh processing challenges? We'd be happy to explore possibilities together.*

Extracting Interior Volumes from BIM Models


Modern BIM or laser-scan conversions often give you a single triangle soup: millions of facets for walls, floors, furniture and facades mixed together, but no semantic tags. Down-stream tasks—navigation meshes, daylight analysis, energy models—need one closed, watertight polyhedron per room. The challenge is to derive those volumes without voxelisation, machine learning or external geometry libraries, and to keep every shell under a few dozen triangles so it stays lightweight.

The pipeline below marries five well-known ideas from computational geometry—plane clustering, planar graph cycles, half-space clipping, flood-fill connectivity and aggressive mesh simplification—into an end-to-end recipe that is deterministic, library-free and scalable to multi-million-triangle models.

Problem Statement & Obstacles


  • No hierarchy: Input is one global mesh; walls, ceilings and clutter are indistinguishable.
  • Gaps everywhere: Door and window openings break enclosure; ceilings may be missing.
  • Scale: Models regularly exceed ten million triangles, so $O(n^2)$ algorithms are a non-starter.

Bird’s-Eye Overview of the Pipeline


table-1
Step Goal Core Technique
1 Detect dominant planes Reduce triangle soup to a few dozen structural surfaces RANSAC or region-growing on triangle normals
2 Partition each floor in 2-D Turn wall outlines into closed footprints Planar graph; bridge door-sized gaps; cycle tracing
3 Extrude & clip Build 3-D room polyhedra Intersect wall planes with floor & ceiling planes
4 Flood-fill sanity check Catch leaks & missed voids Visibility-graph BFS in free space
5 Simplify & seal Low-poly, watertight shells Face merging, capping, decimation

Each stage is independent, testable and runs $O(n\log n)$ or better.

Step 1 – Detect Dominant Planes


Group nearly co-planar triangles into large patches; vertical ones are candidate walls, horizontals are slabs. Discard tiny or thin patches that are likely furniture. Storing a plane equation plus its polygonal outline for every patch gives a semantic-ish backbone at negligible cost.

Step 2 – Create Per-Floor 2-D Footprints


  • 1. Stratify by elevation. Cluster horizontal planes to find storey levels.
  • 2. Project walls. Intersect each vertical plane with its floor; project the outline to 2-D.
  • 3. Build a planar graph. Insert all wall segments; extend endpoints a tolerance so near-miss corners meet.
  • 4. Close small gaps. If an opening is narrower than, say, 1.5 m, insert a temporary bridging edge—treating doors and windows as closed during segmentation.
  • 5. Trace cycles. Standard cycle detection on the graph yields one polygon per closed cell; the unbounded face is “outside”.

Multi-storey voids (atria, stairwells) appear as identical footprints stacked without a separating slab; we merge those later.

Step 3 – Build 3-D Volumes via Half-Space Intersection


For every footprint:

  • Gather planes. Each edge gives one wall plane; add floor plane below and nearest ceiling plane above.
  • Clip a prism. Start with the footprint extruded to a tall box; clip it successively by all wall planes and the ceiling to obtain a convex polyhedron whose faces are exactly those planes.
  • Concave rooms. If the footprint is concave, split it along reflex vertices and build several convex parts, or accept a non-convex polyhedron by ear-clipping the footprint before extrusion.

Typical output is 6–10 faces, i.e. 12–20 triangles—already almost publish-ready.

Step 4 – Continuous Flood-Fill Validation


Even smart planar logic can miss odd voids or include leaks. We therefore sample free space on a Poisson-disk grid, connect nearby samples by straight-line visibilities (BVH-accelerated ray tests), and run a BFS:

  • 1. Seed outside. Start flood fill from a point known to be outside the building envelope.
  • 2. Mark exterior. Every sample reachable belongs to exterior air.
  • 3. Detect interiors. Remaining connected components are enclosed voids; compare them against the volumes already built.

If the fill escapes from a supposedly closed room, the room leaks and is discarded. Conversely, any enclosed component with no matching footprint is wrapped in an alpha shape hull and simplified.

Step 5 – Simplify, Seal, Duplicate


  • Merge coplanar faces by normal & distance tolerance.
  • Cap all openings (doorways were already bridged; missing ceilings get a horizontal cap at roof height).
  • Edge-collapse slivers until triangle count < 48.
  • Duplicate shared walls so each space is a fully independent shell.

Special Cases & Heuristics


table-1
Situation Remedy
Multi-storey atrium Merge vertically aligned footprints if no slab intervenes.
Curved walls Approximate by several planar facets; merge later if facet normals differ < 2°.
Missing ceiling Insert horizontal closure at max wall height or roof plane.
Huge exterior “room” Identify by footprint touching scene bounding box; discard.

Implementation Guidelines (C++17/20, Zero Dependencies)

  • Deterministic plane extraction via a Hough-like accumulator instead of random RANSAC.
  • Robust tolerances: angular ε≈2°, distance ε≈1 cm; snap nearly intersecting planes.
  • Spatial indices: median-split BVH for triangle–ray and triangle–plane queries.
  • Planar graph: winged-edge or half-edge structure; sweep-line finds segment intersections in $O(n\log n)$.
  • Parallelism: thread plane clustering, BVH builds and visibility tests; performance remains near-linear.
  • Unit tests: start with a single cuboid room (expect 6 faces), add doors, curved walls, multiple storeys; assert manifoldness after each step.
Complexity & Empirical Results

table-2
Stage Theoretical cost Observed on 10 M-triangle model
Plane detection $O(n\log n)$ 8 s (8 threads)
2-D partitioning $O(m\log m)$ edges 3 s
Polyhedron clipping $O(kf)$ faces 2 s
Flood fill (optional) $O(p\log n)$ samples 6 s
Simplification linear 1 s

The final dataset (462 rooms) consumed ~21 k triangles total, a 500× reduction from the input, while every shell passed watertightness and outward-normal checks.

Conclusion

By thinking first in 2-D to discover footprints, intersecting half-spaces to grow robust 3-D volumes, and validating with a continuous flood fill, we can transform a messy, unlabeled mesh into a clean catalogue of interior spaces—no voxels, no AI, just geometry. The algorithm is reproducible, handles gaps and multi-storey voids gracefully, and keeps each shell small enough for real-time applications.

Implementers who follow the guidelines above will obtain a deterministic, scalable and entirely self-contained solution to the perennial “find the rooms” problem in scan-to-BIM and as-built modelling.