Abstract
Inverse Procedural Modeling (IPM) aims to discover the rules and parameters that generate a model matching a target shape. However, real-world point clouds from LiDAR or laser scanners are often incomplete, featuring occlusions and noise that confound traditional similarity metrics. This paper proposes a novel framework for Partial Procedural Geometric Model Fitting (PPGMF). The core of the approach is the Weighted Mean Measure (WMM), a similarity metric designed for partial rigid matching. Combined with a Markov chain Monte Carlo (MCMC) optimization strategy and a coarse-to-fine early rejection technique, the method robustly fits arbitrary procedural models to messy, real-world geometric data.
Introduction
The task of geometric model fitting involves finding a set of procedural parameters (e.g., the number of floors or window dimensions in a building grammar) that best approximate an input point cloud. While established for complete shapes, this process often fails when applied to "non-complete" data. Real-world scans are rarely perfect; they suffer from missing regions due to occlusions or extra clutter from the environment.
Existing metrics like the Symmetric Hausdorff Distance (SHD) or Voxel Difference (VD) require two-way comparisons that break down when the model and the target only partially overlap. To address this, the authors introduce a pipeline that prioritizes one-sided similarity and geometric measures to handle the inherent incompleteness of laser-scanned data.
Methodology
Weighted Mean Measure (WMM)
The primary contribution is the Weighted Mean Measure (WMM). Unlike SHD, which computes distances in both directions, WMM leverages the mathematical insight that two models are identical if the one-sided distance from the generated model to the query point cloud is zero and their intrinsic geometric measures (such as surface area) are equal.
For partial matching, the WMM divides the procedural model into sub-regions and applies an exponential decay weight based on their distance to the query points. This allows the metric to naturally ignore parts of the model that fall into voids or missing data areas of the point cloud, focusing only on the overlapping regions.
Optimization and Early Rejection
Because procedural grammars create a non-differentiable parameter space, the authors employ the Metropolis-Hastings algorithm for MCMC optimization. To handle the high computational cost of comparing dense models to large point clouds, they introduce a coarse-to-fine sampling strategy. By initially sampling the proposed model sparsely, the system can "fail fast" and reject poor candidates early, significantly reducing the total number of distance calculations required.
Key Results
The proposed method was evaluated on synthetic shapes, CGA building grammars, and real-world mobile laser scanner data.
Key findings include:
- Robustness: WMM was the only metric tested that correctly identified ground-truth parameters for partially overlapping and noisy point clouds.
- Efficiency: The coarse-to-fine early rejection strategy provided an approximate 3x speedup in the optimization process without compromising the accuracy of the fit.
- Flexibility: The algorithm successfully handled variable-length parameter sets, such as determining the correct number of floors in a building before optimizing the dimensions of individual windows.
Conclusion and Future Work
While the PPGMF framework represents a significant step forward in handling incomplete data, it faces challenges with the "curse of dimensionality" as the number of procedural parameters grows. Additionally, while the method handles missing data well, "corrupted holes"—regions where occlusions contain undesired reflection points—require specialized handling, such as the Squared Mean Measure (SMM). Future work may involve integrating deep learning to guide the MCMC search or improving preprocessing to filter out background noise more effectively.
Summary updated