2024 CIS-RAM • Hangzhou, China 🇨🇳

3D Map Generation for Indoor Non-Manhattan World Environments

Timothy Bonner, Bryan Wei Xian Lee, Sutthiphong Srigrarom, Wai Lun Leong, Jimmy Chiun

3D MappingNon-Manhattan WorldsPoint CloudsIndoor Reconstruction
Paper Approach Results BibTeX
A noisy blue point cloud on the left and the reconstructed room, with walls that do not meet at right angles, on the right.
The raw scan on the left, the reconstructed room on the right. Its walls do not meet at right angles — the case a Manhattan-world reconstruction cannot represent.

Abstract

Accurate mapping of indoor environments is crucial for various real-world applications, including search and rescue operations, as well as home robotics. Utilizing small, cost-effective drones provides significant advantages over traditional methods for mapping confined and unknown spaces. This paper advances existing robotics mapping research by presenting a novel algorithm for three-dimensional (3D) indoor environment mapping, particularly in non-Manhattan World settings. Our approach addresses the limitations of previous methods by introducing an efficient algorithm that filters noise, identifies structural corners using breadth-first search and convolution, and constructs nonintersecting polygons for environment mapping. Experimental results validated the effectiveness of our solution in producing reliable indoor maps where previous methods fail, showing improvements in automatic wall detection, noise resilience, and handling of more complex shapes and scenarios.

The Approach

Mapping an interior from a small drone means working with a sparse, noisy point cloud — and, in most real buildings, with walls that refuse to line up on two axes.

  1. 01

    Filter the noise before fitting anything

    Range returns from a lightweight platform scatter around the true surface. Fitting geometry to raw points inherits every stray return, so the algorithm filters the cloud first and reasons about structure second.

  2. 02

    Find the corners with breadth-first search and convolution

    Structural corners are identified by a breadth-first search over the filtered cloud combined with a convolution step, which is what lets the method detect walls automatically instead of being handed their orientations.

  3. 03

    Join them into non-intersecting polygons

    Corners are assembled into polygons that never cross themselves, so the resulting map stays a valid description of the space — including rooms whose walls meet at arbitrary angles, where earlier methods fail.

Results

Reconstructions from real Crazyflie multi-ranger scans, on rooms with non-rectilinear walls that a Manhattan-world assumption cannot represent.

Point cloud and reconstructed polygon of an L-shaped room, with the corner-detection and wall-fitting stages shown side by side.
"L"-style room reconstruction, from raw scan through detected corners to the final wall polygon.
Point cloud and reconstructed polygon of a room with a fireplace-shaped recess, a more complex non-rectilinear layout.
"Fireplace"-style room reconstruction — a more complex recessed layout than the L-shape case above.
Grid showing shape completion and hollowing applied to the Fireplace environment, filling gaps left by sparse sensor returns.
Shape completion and hollowing on the Fireplace environment: gaps left by sparse multi-ranger returns are filled in by radial search along the shortest path through undiscovered grid cells, then hollowed back out to a thin wall.

BibTeX

@article{chiun20213d,
    author={Bonner, Timothy and Xian Lee, Bryan Wei and Srigrarom, Sutthiphong and Leong, Wai Lun and Chiun, Jimmy},
    booktitle={2024 IEEE International Conference on Cybernetics and Intelligent Systems (CIS) and IEEE International Conference on Robotics, Automation and Mechatronics (RAM)}, 
    title={3D Map Generation for Indoor Non-Manhattan World Environments}, 
    year={2024},
    volume={},
    number={},
    pages={417-422},
    keywords={Three-dimensional displays;Accuracy;Machine learning algorithms;Shape;Noise;Robot sensing systems;Real-time systems},
    doi={10.1109/CIS-RAM61939.2024.10673043}

}

Related Project