PaperlayerView exact revision on arXiv

Source-linked AI summary

Automatic reconstruction of fully volumetric 3D building models from point clouds

Sebastian Ochmann, Richard Vock, Reinhard Klein

arXiv:1907.00631v1cs.GR

TL;DR

The paper addresses indoor building reconstruction from unstructured point clouds without relying on separate scans or predefined room segmentation. It combines automatic preprocessing with integer linear optimization over volumetric wall entities and constrained cell labels, producing interconnected multi-story room and wall models demonstrated on real-world datasets. The implementation remains limited by its treatment of slanted surfaces and computational complexity on larger or more detailed inputs.

  • Problem

    Prior approaches often lack building-structure relationships, impose restrictive input assumptions, or do not reconstruct general multi-story volumetric wall and slab elements suitable for BIM.

  • Method

    The method automatically detects planes, removes outliers, segments rooms, constructs a 3D plane arrangement, and solves an integer linear program for constrained volumetric cell labeling.

  • Results

    The approach reconstructs fully volumetric, interconnected wall entities and room topology for multi-story buildings and is demonstrated on varied real-world datasets.

  • Takeaways & Limitations

    The resulting models support volumetric room and wall representations, their interrelations, and additional hard constraints for BIM-related modeling tasks.

  • Takeaways & Limitations

    The current implementation excludes slanted walls, floors, and ceilings because a numerically stable 3D cell-complex construction is unavailable.

Abstract

from arXiv · show

We present a novel method for reconstructing parametric, volumetric, multi-story building models from unstructured, unfiltered indoor point clouds by means of solving an integer linear optimization problem. Our approach overcomes limitations of previous methods in several ways: First, we drop assumptions about the input data such as the availability of separate scans as an initial room segmentation. Instead, a fully automatic room segmentation and outlier removal is performed on the unstructured point clouds. Second, restricting the solution space of our optimization approach to arrangements of volumetric wall entities representing the structure of a building enforces a consistent model of volumetric, interconnected walls fitted to the observed data instead of unconnected, paper-thin surfaces. Third, we formulate the optimization as an integer linear programming problem which allows for an exact solution instead of the approximations achieved with most previous techniques. Lastly, our optimization approach is designed to incorporate hard constraints which were difficult or even impossible to integrate before. We evaluate and demonstrate the capabilities of our proposed approach on a variety of complex real-world point clouds.

1. Introduction

The paper targets indoor building reconstruction from point clouds, where prior methods often lack structural relationships, rely on restrictive input assumptions, or do not support general volumetric multi-story models. It proposes automatic segmentation and outlier removal combined with integer linear optimization over volumetric entities and constraints.

  • Previous methods commonly reconstruct separate planar surfaces or watertight boundaries, providing limited insight into building structure.
  • The method removes requirements for separate scans or predefined room segmentation through automatic outlier filtering and room segmentation.
  • Integer linear programming globally constrains feasible reconstructions while allowing optional hard constraints to guide local or global properties.
  • Volumetric wall and slab entities model intersections and dependencies between related surfaces rather than treating surfaces as disconnected elements.

2. Related Work

Related work spans floor-plan, room-level, whole-building, and 2.5D reconstruction, but the paper identifies limited support for general multi-story volumetric wall and slab models suitable for BIM.

  • Indoor building reconstruction: Existing approaches cover 2D floor plans, individual rooms, whole-building surfaces, and 2.5D room-segmented models.
  • Indoor building reconstruction: Methods handling slanted walls or ceilings include polyhedral room boundaries and complex multi-story applicability, but do not provide the paper’s target volumetric BIM representation.
  • Indoor building reconstruction: Some volumetric reconstruction methods impose strong input requirements, including interior and exterior scans, scanner positions, or manual post-processing of volumetric walls.
  • Indoor building reconstruction: The proposed approach is presented as the first to combine general multi-story, multi-room reconstruction with fully volumetric room and wall entities.
  • Applications: Scan-to-BIM research supports applications such as construction surveillance, facility management, energy simulation, and model validation.

3. Overview

The pipeline converts an unstructured indoor point cloud into a constrained volumetric building model by detecting and labeling geometric cells, then solving an optimization problem for room and wall assignments.

  • Planes are detected from the point cloud, and their supporting points are represented with occupancy bitmaps.
  • Outliers are removed and rooms are segmented automatically using plane-based processing and Markov Clustering without requiring the number of rooms.
  • Detected surfaces are labeled, rectified, clustered, and paired into volumetric wall and slab candidates rather than isolated surfaces.
  • Intersecting candidate planes creates a 3D cell complex whose cells encode possible room, outside, wall, and slab configurations.
  • The optimization assigns cells to rooms or outside space and places walls at inside–outside transitions while enforcing constraints such as wall connectivity.
  • The resulting cell labeling can be converted into renderable or exportable formats such as IFC or meshes.

4. Method

The method detects and cleans planes from unstructured point clouds, then automatically labels points into room clusters using visibility-based ray casting and graph clustering.

  • 4.1. Plane detection: Plane detection provides occupancy bitmaps that serve as a density-independent representation of point support for later processing.An efficient RANSAC procedure detects planes, projects supporting points into bitmaps, and enables pruning of weak planes.
  • 4.2. Point cloud cleaning: Outlier removal casts stochastic rays from each point against detected-plane occupancy bitmaps and removes points whose inside estimate falls below 0.5.The filtering process updates plane occupancy bitmaps and is iterated a small number of times.
  • 4.3. Point cloud labeling: Room priors are obtained by labeling the point cloud with room and outside-area labels before optimization.The labeling stage is designed to operate without preexisting room segmentation or scan-per-room assumptions.
  • 4.3. Point cloud labeling: Visibility tests between point patches on detected surfaces form a graph whose clusters define room labels.Patch-based processing reduces graph size, and Markov Clustering identifies natural clusters through flow simulation.
  • 4.3. Point cloud labeling: The resulting disjoint patch clusters assign room labels to points, although the number of labels may exceed the rooms in the final reconstruction.The labels are projected into multi-label bitmaps for subsequent room-location estimation.

4.4. Surface candidates

Surface candidates are extracted by pruning and classifying detected planes, then paired into volumetric wall or slab candidates with support dilated to favor intersections.

  • 4.4. Surface candidates: Detected planes are pruned, classified by orientation, and rectified into wall or slab surface candidates using occupancy-based support estimates.Low-support and non-approximately-vertical or horizontal planes are discarded.
  • 4.4. Surface candidates: Multi-label support bitmaps assign continuous room-label values to surface regions for estimating room locations in 3D.They are generated by projecting supporting points onto each surface and averaging their previously determined labels.
  • 4.5. Wall and slab candidates: Dilating surface support extends evidence into wall interiors, encouraging volumetric wall intersections that would otherwise incur high costs.Without dilation, scanner visibility restricts support to exposed surfaces rather than the interiors of walls.
  • 4.5. Wall and slab candidates: Nearby approximately parallel surfaces with opposing normals are paired into wall or slab candidates, while unmatched surfaces receive virtual counterparts.The augmentation supports volumetric boundaries for outside walls scanned only on their inner side.

4.6. Arrangement of planes

The optimization search space is an arrangement of candidate planes and its induced three-dimensional cell complex, where cells and faces encode building regions and boundaries.

  • 4.6. Arrangement of planes: Candidate wall and slab planes are intersected to construct an arrangement and the induced 3D cell complex for optimization.Vertical walls and horizontal slabs are treated identically as walls in the formulation.
  • 4.6. Arrangement of planes: Convex cells represent either rooms or outside area, while walls may occupy outside-area cells subject to optimization constraints.The formulation limits each cell to at most one room and restricts wall placement to appropriate regions.
  • 4.6. Arrangement of planes: Convex faces between neighboring cells lie on candidate wall planes and can separate regions such as rooms and walls.These faces provide the geometric interfaces used by the optimization model.

4.7. Volume and surface priors

The method estimates volumetric and surface-support priors over the arrangement, while its notation and constraints encode room labeling, wall occupancy, orientation, and connectedness.

  • 4.7. Volume and surface priors: Volumetric priors estimate whether each arrangement cell likely contains a room label or outside area, while face priors estimate point-cloud support.These two prior types guide candidate selection and regularize the optimization result.
  • 4.7. Volume and surface priors: The model defines oriented neighboring-cell faces, room, wall, and outside labels, and the wall-containing cells associated with each candidate.These sets provide the variables and incidence relationships needed to formulate constraints.
  • 4.7. Volume and surface priors: Face orientation constraints restrict interior-to-exterior transitions to the positive side of a face and require active boundary walls on the negative side.The constraints use ordered cell pairs and wall sets associated with each separating face.
  • 4.7. Volume and surface priors: Wall-ending constraints require an ending wall to meet a boundary face of another active wall, enforcing connectedness between walls.An inner face of one wall is correspondingly treated as a boundary face of an intersecting wall.

4.8. Cell complex optimization

The method labels cells with rooms, outside space, and walls through 0-1 integer linear programming, combining hard geometric constraints with a cost function that fits observed data while enforcing plausible wall structure.

  • Optimization formulation: 0-1 integer linear programming assigns binary room, outside, and wall labels to cells while allowing hard constraints unavailable to more restricted approximate multi-label methods.The optimization minimizes the objective subject to Constraints 1–6 using the Gurobi Optimizer.
  • Cell labeling: Each cell receives one room or outside label, while outside cells may additionally carry multiple wall labels, including intersecting walls.This representation permits wall intersections to be encoded directly in the cell complex.
  • Geometric constraints: Room-boundary constraints prevent directly neighboring room labels, forcing outside space and thereby avoiding paper-thin walls between rooms.Additional constraints require room boundaries to coincide with active wall boundaries and restrict wall labels to outside cells.
  • Geometric constraints: Wall connectivity constraints disallow a wall from ending at an inner face unless that face is also a boundary face of another active wall.This enforces interconnected wall endpoints in the reconstructed model.
  • Objective function: The cost function rewards likely room and outside assignments while penalizing wall boundary and inner-face areas, with penalties attenuated by face support.The room/outside fitness term is maximized through a negative sign in the minimized objective, and wall costs depend on face area and support.
  • Optimization formulation: An additional outside-label constraint produced a slight performance improvement attributed to heuristics in the particular optimizer implementation.The constraint was already implied by Constraints 1–2.

4.9. Optimization result

The optimization produces a dense volumetric labeling of rooms, outside space, and intersecting walls, with adjacency and incidence information suitable for navigation, simulation, and BIM integration.

  • Optimization result: The result assigns each cell to a room or outside area, while outside cells can carry multiple walls representing volumetric wall intersections.The cell complex provides a dense segmentation of space into rooms and outside space.
  • Optimization result: Cell adjacency makes room adjacency and wall incidence immediately available for navigation or simulation and supports transfer into IFC-compatible architecture software and BIM pipelines.The representation is closely related to building elements in BIM formats such as IFC.

5. Implementation details

Implementation uses fixed point-cloud preprocessing, plane-detection, bitmap-resolution, and ray-casting parameters for reconstruction preparation.

  • Implementation details: Input clouds were subsampled to 2 cm, with 1 cm plane detection, 20 cm clustering, 10 cm multi-label bitmaps, 20 cm occupancy bitmaps, and three cleaning ray-casting iterations.Plane detection also used a 6° normal threshold, 1000-point minimum support, and miss probability 0.001; Case study 2 used an 18° threshold.

6. Evaluation

The method was evaluated on synthetic and real-world multi-story point clouds, generally producing accurate reconstructions while supporting comparisons, interactive constraints, and parameter adjustments. Runtime ranged from about one to ten minutes, with fidelity and scalability affected by surface complexity and unsupported geometry.

  • Reconstruction quality: The approach generally reconstructed test datasets well without dataset-specific tuning, including reliable removal of large-scale clutter scanned through windows.Some thick walls were reconstructed as two thinner parallel walls, and occasional room oversegmentation occurred.
  • Runtime: Runtime ranged from about one minute on Datasets 1 and 2 to ten minutes on Dataset 6, with optimization cost driven mainly by plane-arrangement complexity.The experiments used minimum estimated areas of 2 m2 for vertical surfaces and 5 m2 for horizontal surfaces to trade detail against computational feasibility.
  • Comparison to IFC: All scanned rooms in Dataset 5 mostly matched the corresponding groundtruth BIM model, although some upper-floor regions were oversegmented and a railing was reconstructed as walls.The reported oversegmentation was described as manually fixable.
  • Comparison to related work: The method produced stronger wall regularization than the compared approach and avoided segmented, nearly coplanar walls and scan-dependent hallway oversegmentation.The volumetric wall formulation assigns costs to the added wall volume, discouraging unnecessary parallel wall elements.
  • Interactive modification: Additional hard constraints let users steer reconstructions by forcing regions to be inside or outside areas, walls, or no-wall locations.Virtual wall candidates could also be added by drawing a line, allowing the algorithm to enclose an otherwise open hallway protrusion.
  • Parameter sensitivity: Increasing the wall surface cost parameter α from 0.04 to 0.08 produced stronger regularization of walls and slabs in Case study 2.The default setting could fit some walls to strongly supported windows and leave a slab hole in a complex staircase region.

7. Conclusion and future work

The paper concludes that integer linear programming enables volumetric, interconnected multi-story reconstructions from point clouds with weak input assumptions and flexible hard constraints. Future work targets slanted or non-planar surfaces and improved scalability for large datasets.

  • Conclusion: The approach reconstructs volumetric, interconnected wall entities and room topology in multi-story buildings while requiring weaker assumptions about the input data.The resulting models are described as close to Building Information Modeling requirements for volumetric rooms, walls, and their interrelations.
  • Conclusion: Hard constraints can be added to force or avoid selected entities at chosen locations, allowing direct modification of the optimization result.The paper demonstrated this flexibility on a variety of real-world datasets.
  • Future work: Future work includes supporting slanted and possibly non-planar surfaces, reducing computational complexity, and connecting reconstruction with opening and object detection.Large datasets may require pruning invalid candidates or other optimizations because global plane arrangements increase cells and optimization variables.
Loading 1907.00631v1…