GlobFit: Consistently Fitting Primitives by Discovering Global Relations

ACM Transactions on Graphics(Proceedings of SIGGRAPH 2011)

Yangyan Li1    Xiaokun Wu1, 2    Yiorgos Chrysanthou3    Andrei Sharf4, 1    Daniel Cohen-Or5   Niloy J. Mitra6   
1SIAT, China    2Zhejiang University    3University of Cyprus    4Ben-Gurion University    5TAU    6KAUST


Figure 1: Starting from a noisy scan, our algorithm recovers the primitive faces along with their global mutual relations, e.g., coplanarity, equality of length and angle. The aligned primitives are used to create a final model. We compare length and angles measured on the physical model and on the final output. All lengths are in mm.


Given a noisy and incomplete point set, we introduce a method that simultaneously recovers a set of locally fitted primitives along with their global mutual relations. We operate under the assumption that the data corresponds to a man-made engineering object consisting of basic primitives, possibly repeated and globally aligned under common relations. We introduce an algorithm to directly couple the local and global aspects of the problem. The local fit of the model is determined by how well the inferred model agrees to the observed data, while the global relations are iteratively learned, and enforced through a constrained optimization. Starting with a set of initial RANSAC based locally fitted primitives, relations across the primitives such as orientation, placement, and equality are progressively learned, and conformed to. In each stage, a set of feasible relations are extracted among the candidate relations, and then aligned, while best fitting to the input data. The global coupling corrects the primitives obtained in the local RANSAC stage, and brings them to precise global alignment. We test the robustness of our algorithm on a range of synthesized and scanned data, with varying amount of noise, outliers, and non-uniform sampling, and validate the results against ground truth, where available.







Figure 2: Various global relations extracted and conformed to, while aligning to the scanned data of a clutch-part. In the top-right region, the primitives remain separated in absence of enough data points to justify a connection. Extracted relations and lengths were validated with respect to the physical model.


Figure 3: Global alignment of primitives involving parallel axes, coplanarity, coaxial, and equal length constraints on the wheel model, while fitting to the scanned data. In this case, the coaxial and equality relations, lead to a hierarchy based on the mutual relations and spatial proximity among the primitives. We show an exploded view of one of the subcomponents along its common axis. RANSAC primitives have pairwise angle histogram in range [0, π /6], while after global alignment all pairwise angles vanish; the pairwise plane distance histogram also significantly improves.


Figure 4: Cylinder, plane, and sphere primitives are aligned using extracted coaxis, coplanar, parallel/orthogonal axes, equal angle as well as equal length constraints. They converge to the final model after two iterations of RANSAC fitting and constraint optimization. We overlap the final result on the initial RANSAC results for comparison; the histograms demonstrate the effect in the primitive pair angle space.


Code and Testing Data:

Code hosted on Google Code.

Testing Data(format description): Fig9, Fig11, Fig13, Fig14.



We are grateful to Ruwen Schnabel for making code from [Schnabel et al. 2007] publicly available, Ran Gal and Suhib Alsisan for proofreading the paper, KAUST car garage for lending machine parts for scanning, and AIM@Shape for the joint model used for the simulated scans in Figure 16. Niloy thanks Tanveer Alam for initial experiments for this project; Pierre Alliez, Cengiz Oztireli for running comparison tests using their state-of-the-art reconstruction algorithms; and Reinhard Klein for inspiring discussions.



  title = {GlobFit: Consistently Fitting Primitives by Discovering Global Relations},
  author = {Yangyan Li and Xiaokun Wu and Yiorgos Chrysathou and Andrei Sharf and Daniel Cohen-Or and Niloy J. Mitra},
  journal = {ACM Transactions on Graphics (Proceedings of SIGGRAPH 2011)},
  volume = {30},
  issue = {4},
  pages = {Article No. 52},
  year = {2011}