Total views : 433

An Analysis of Reconstruction Algorithms Applied to 3D Building Modeling


  • School of Information Technology and Engineering, VIT University, Vellore - 632014, Tamil Nadu, India


Objectives: The process of reconstructing a city cannot be fully automated. More human intervention is required to achieve high quality mass modeling. Our objectives are to provide a guide for the 3D graphic designers and 3D modelers in developing 3D building models. Methods: We present an up-to-date survey of the reconstruction algorithms which are further classified as point cloud based reconstruction methods and structure-aware shape reconstruction methods. We introduce various existing 3D reconstruction techniques and have compared those techniques based on shape simplification, surface completion and shape modeling methodologies. Findings: We have identified the pipeline process and technical issues encountered in each phase of the reconstruction process from a given image layout. As stated, the inverse procedural reconstruction approaches are best oriented towards the reconstruction of buildings from a given input 2D image. Also, there is a lack of systems that are capable of generating procedural rules from user interaction. Improvements: We propose a new 3D reconstruction methodology and novel framework that combines component based structure capturing and rule based modeling techniques that would best be suitable for 3D building modeling, resembling the real world buildings in future systems.


3D Building Modeling, 3D reconstruction, 3D Shape Analysis, Image Based Modeling, Scene Understanding.

Full Text:

 |  (PDF views: 389)


  • Schnabel R, Wahl R, Klein R. Efficient ransac for point-cloud shape detection. Computer Graphics Forum. 2007; 26(2):214–26.
  • Drost B, Ulrich M, Navab N, Ilic S. Model globally, match locally: Efficient and robust 3D object recognition. IEEE CVPR. 2010. p. 198–1005.
  • Scheidegger CE, Fleishman S, Silva CT. Triangulating point set surfaces with bounded error. Proc of the EG/SIGGRAPH Symposium on Geometry processing; Switzerland. 2005. p. 63–72.
  • Schnabel R, Degener P, Klein R. Completion and reconstruction with primitive shapes. Computer Graphics Forum (Proc of Eurographics). 2009; 28(2):503–12.
  • Chauve AL, Labatut P, Pons JP. Robust piecewise-planar 3D reconstruction and completion from largescale unstructured point data. IEEE CVPR; 2010. p. 1261–8.
  • Reisner-Kollmann I, Maierhofer S, Purgathofer W. Reconstructing shape boundaries with multimodal constraints. Computers and Graphics. 2013; 3(37):137–47.
  • Xiao J, Furukawa Y. Reconstructing the worlds museums. ECCV; 2012. p. 668–81.
  • Oesau S, Lafarge F, Alliez P. Indoor scene reconstruction using primitive-driven space partitioning and graphcut. Proc of EG workshop on Urban Data Modeling and Visualisation; Girona, Spain. 2013. p. 9–12.
  • Lafarge F, Alliez P. Surface reconstruction through point set structuring. Computer Graphics Forum (Proc of Eurographics). 2013; 32(2):225–34.
  • Van Kreveld M, Van Lankveld T, Veltkamp RC. Watertight scenes from urban lidar and planar surfaces. Computer Graphics Forum. 2013; 32(5):217–28.
  • Labatut P, Pons JP, Keriven R. Robust and efficient surface reconstruction from range data. Computer Graphics Forum. 2009; 28(8):2275–90.
  • Cheng ZQ, Wang YZ, Li B, Xu K, Dang G, Jin SY. A survey of methods for moving least squares surfaces. Proceedings of the 5th Eurographics/IEEE VGTC Conference on Point-Based Graphics; Switzerland. 2008. p. 9–23.
  • Alexa M, Behr J, Cohen-Or D, Fleishman S, Levin D, Silva C. Computing and rendering point set surfaces. Trans on Visualization and Computer Graphics. 2003; 9(1):3–15.
  • Amenta N, Kil YJ. Defining point-set surfaces. ACM Trans on Graphics. 2004; 23(2):264–70.
  • Schreiner J, Scheidegger CE, Fleishman S, Silva CT. Direct (re)meshing for efficient surface processing. Computer Graphics Forum. 2006; 25(3):527–36.
  • Ohtake Y, Belyaev A, Alexa M, Turk G, Seidel H. Multi-level partition of unity implicits. ACM Trans Graph. 2003; 22(2):463–70.
  • Nagai Y, Ohtake Y, Suzuki H. Smoothing of partition of unity implicit surfaces for noise robust surface reconstruction. Computer Graphics Forum (Proc. of the Symposium on Geometry Processing). 2009; 28(5):1339–48.
  • Kolluri R, Shewchuk JR, O’brien JF. Spectral surface reconstruction from noisy point clouds. Proc of the EG/SIGGRAPH Symposium on Geometry Processing; 2004. p. 11–21.
  • Hornung A, Kobbelt L. Robust reconstruction of watertight 3D models from non-uniformly sampled point clouds without normal information. Computer Graphics Forum (Proc of the Symposium on Geometry Processing); 2006. p. 41–50.
  • Dinh HQ, Turk G, Slabaugh G. Reconstructing surfaces using anisotropic basis functions. International Journal of Computer Vision. 2001; 606–13.
  • Adamson A, Alexa M. Anisotropic point set surfaces. Proc AFRIGRAPH; 2006. p. 7–13.
  • Avron H, Sharf A, Greif C, Cohen-Or D. 1-sparse reconstruction of sharp point set surfaces. ACM Trans on Graphics. 2010; 29(5):1–12.
  • Mitra NJ, Pauly M, Wand M, Ceylan D. Symmetry in 3D geometry: Extraction and applications. Computer Graphics Forum (STAR Proceedings of Eurographics). 2013; 32(6):1–23.
  • Law AJ, Aliaga DG. Single viewpoint model completion of symmetric objects for digital inspection. Computer Vision and Image Understanding. 2011; 115(5):603–10.
  • Pauly M, Mitra NJ, Wallner J, Pottmann H, Guibas LJ. Discovering structural regularity in 3D geometry. ACM Trans Graph. 2008; 27(3):1–11.
  • Lipman Y, Chen X, Daubechies I, Funkhouser T. Symmetry factored embedding and distance. ACM Trans on Graphics. 2010; 29(4):1–12.
  • Berner A, Wand M, Mitra NJ, Mewes D, Seidel HP. Shape analysis with subspace symmetries. Computer Graphics Forum. 2011; 30(2):277–86.
  • Zheng Q, Sharf A, Wan G, Li Y, Mitra NJ, Cohen-Or D, Chen B. Non-local scan consolidation for 3D urban scenes. ACM Trans Graph. 2010; 29(4):1–9.
  • Shen CH, Huang SS, Fu H, Hu SM. Adaptive partitioning of urban facades. Proc of ACM SIGGRAPH Asia. 2011; 30(6):184.
  • Wan G, Sharf A. Grammar-based 3D facade segmentation and reconstruction. Computers and Graphics. 2012; 36(4):216–23.
  • Friedman S, Stamos I. Online facade reconstruction from dominant frequencies in structured point clouds. IEEE CVPR; 2012. p. 1–8.
  • Li Y, Zheng Q, Sharf A, Cohen-Or D, Chen B, Mitra NJ. 2D-3D fusion for layer decomposition of urban facades. ICCV; 2011. p. 882–9.
  • Wu C, Frahm JM, Pollefeys M. Detecting large repetitive structures with salient boundaries. ECCV; 2010. p. 142–55.
  • Zhou QY, Neumann U. 2.5 D building modeling by discovering global regularities. CVPR; 2012. p. 326–33.
  • Li Y, Wu X, Chrysathou Y, Sharf A, Cohenor D, Mitra NJ. Globfit: Consistently fitting primitives by discovering global relations. ACM Trans Graph. 2011; 30(4):52.
  • Sadidi J, Talebzadeh M, Rezaian H, Firouzabadi PZ. Designing 3D semantic model in LOD4 to simulate building utility network. Indian Journal of Science and Technology. 2015 Jul; 8(16):1–9.
  • Sivaranjani P, Kumar AS. 3D VLSI non-slicing floor planning using modified corner list representation. Indian Journal of Science and Technology. 2015 Dec; 8(35):1–6.
  • Guennebaud G, Gross M. Algebraic point set surfaces. ACM Trans Graph. 2007; 26(3):23.
  • Fleishman S, Cohen-Or D, Silva CT. Robust moving least-squares fitting with sharp features. ACM Trans Graph. 2005; 24(3):544–52.
  • Sharf A, Lewiner T, Shklarski G, Toledo S, Cohen-Or D. Interactive topology-aware surface reconstruction. ACM Trans Graph. 2007; 26(3):43.
  • Curless B, Levoy M. A volumetric method for building complex models from range images. Proc of ACM SIGGRAPH; 1996. p. 303–12.
  • Whitaker R. A level-set approach to 3D reconstruction from range data. International Journal of Computer Vision. 1998; 29(3):203–31.
  • Lempitsky V, Boykov Y. Global optimization for shape fitting. IEEE CVPR; 2007. p. 1–8.
  • Labatut P, Pons J P, Keriven R. Robust and efficient surface reconstruction from range data. Computer Graphics Forum. 2009; 28(8):2275–90.
  • Zach C, Pock T, Bischof H. A globally optimal algorithm for robust tv-l1 range image integration. ICCV; 2007. p. 1–8.
  • Fuhrmann S, Goesele M. Fusion of depth maps with multiple scales. Proc of ACM SIGGRAPH Asia; 2011. p. 148.
  • Ummenhofer B, Brox T. Point-based 3d reconstruction of thin objects. ICCV; 2013. p. 969–76.
  • Katz S, Tal A, Basri R. Direct visibility of point sets. ACM Trans Graph. 2007; 26(3):24.
  • Mehra R, Tripathi P, Sheffer A, Mitra NJ. Visibility of noisy point cloud data. Computers and Graphics. 2010; 34(3):219–30.
  • Chen YL, Chen BY, Lai SH, Nishita T. Binary orientation trees for volume and surface reconstruction from unoriented point clouds. Computer Graphics Forum. 2010; 29(7):2011–9.
  • Chen YL, Lee TY, Chen BY, Lai SH. Bipartite polar classification for surface reconstruction. Computer Graphics Forum. 2011; 30(7):2003–10.
  • Amenta N, Bern M. Surface reconstruction by voronoi filtering. Discrete and Computational Geometry. 1999; 22(4):481–504.
  • Tagliasacchi A, Zhang H, Cohen-Or D. Curve skeleton extraction from incomplete point cloud. ACM Trans Graph. 2009; 28(3).
  • Seung-Woon J, Cheong-Hwan L, Young-Cheol J. A study on the work environment and VDT syndrome in radiation technologists working in the area of 3D processing. Indian Journal of Science and Technology. 2015 Aug; 8(18):1–7.
  • Cao J, Tagliasacchi A, Olson M, Zhang H, Su Z. Point cloud skeletons via laplacian based contraction. Proc of IEEE Shape Modeling International; 2010. p. 187–97.
  • Huang H, Wu S, Cohen-Or D, Gong M, Zhang H, Li G, Chen B. l1-medial skeleton of point cloud. CM Trans Graph. 2013; 32(4):65–70.
  • Sharf A, Lewiner T, Shamir A, Kobbelt L, Cohen-Or D. Competing fronts for coarse–to–fine surface reconstruction. Computer Graphics Forum. 2006; 25(3):389–98.
  • Sharf A, Lewiner T, Shamir A, Kobbelt L.On-the-fly curve-skeleton computation for 3D shapes. In Computer Graphics Forum. 2007; 26(3):323–8.
  • Li G, Liu L, Zheng H, Mitra NJ. Analysis reconstruction and manipulation using arterial snakes. ACM Trans Graph; 2010; 29(6).
  • Neubert B, Franken T, Deussen O. Approximate image-based tree-modeling using particle flows. ACM Trans Graph. 2007; 26(3):88–75.
  • Runions A, Fuhrer M, Lane B, Federl P, Rolland-Lagan AG, Rusinkiewicz P. Modeling and visualization of leaf venation patterns. ACM Trans Graph. 2005; 24(3):702–11.
  • Livny Y, Yan F, Olson M, Chen B, Zhang H, El-Sana J. Automatic reconstruction of tree skeletal structures from point clouds. ACM Trans Graph. 2010; 29(6).
  • Berger M, Silva CT. Medial kernels. Computer Graphics Forum (Proc of Eurographics). 2012; 31(2):795–804.
  • Tagliasacchi A, Olson M, Zhang H, Hamarneh G, Cohen-Or D. Vase: Volume-aware surface evolution for surface reconstruction from incomplete point clouds. Computer Graphics Forum. 2011; 30(5):1563–71.
  • Pauly M, Mitra NJ, Giesen J, Gross MH, Guibas LJ. Example-based 3D scan completion. Proc of the EG/SIGGRAPH Symposium on Geometry processing; 2005. p. 23–32.
  • Gal R, Shamir A, Hassner T, Pauly M, Cohen-Or D. Surface reconstruction using local shape priors. Computer Graphics Forum. 2007; 253–62.
  • Shamir A. A survey on mesh segmentation techniques. Computer Graphics Forum. 2008; 27(6):1539–56.
  • Van Kaick O, Zhang H, Hamarneh G, Cohen-Or D. A survey on shape correspondence. Computer Graphics Forum. 2011; 30(6):1681–707.
  • Attene M, Robbiano F, Spagnuolo M, Falcidieno B. Characterization of 3D shape parts for semantic annotation. Computer Aided Design. 2009; 41(10):756–63.
  • Golovinskiy A, Funkhouser T. Consistent segmentation of 3D models. Computers and Graphics (Proc of SMI). 2009; 33(3):262–9.
  • Xu K, Li H, Zhang H, Cohen-Or D, Xiong Y, Cheng Z. Style-content separation by anisotropic part scales. ACM Transactions on Graphics. 2010; 29(6).
  • Sidi O, Van Kaick O, Kleiman Y, Zhang H, Cohen-Or D. Unsupervised co-segmentation of a set of shapes via descriptor-space spectral clustering. ACM Trans on Graphics. 2011; 30(6).
  • Kim Vg, Li W, Mitra N, Diverdi S, Funkhouser T. Exploring collections of 3D models using fuzzy correspondences. Trans on Graphics. 2012; 31(4):1–11.
  • Yumer M, Kara L. Co-abstraction of shape collections. ACM Transactions on Graphics. 2013; 31(6):1–11.
  • Huang Q, Koltun V, Guibas L. Joint shape segmentation with linear programming. ACM Trans Graph. 2011; 30(6):1–12.
  • Wang Y, Asafi S, Van Kaick O, Zhang H, Cohen-Or D, Chen B. Active co-analysis of a set of shapes. ACM Transactions on Graphics. 2012; 31(6).
  • Zheng Y, Cohenor D, Mitra NJ. Functional substructures for part compatibility. Computer Graphics Forum. 2013; 32(2):195–204.
  • Fisher M, Savva M, Hanrahan P. Characterizing structural relationships in scenes using graph kernels. ACM Trans Graph. 2011; 30(4):1–12.
  • Fisher M, Ritchie D, Savva M, Funkhouser T, Hanrahan P. Example-based synthesis of 3D object arrangements. ACM Transactions on Graphics. 2012; 31(6):1–11.
  • Simari P, Kalogerakis E, Singh K. Folding meshes: Hierarchical mesh segmentation based on planar symmetry. Proc Symp Geometry Processing; 2006. p. 111–9.
  • Mitra NJ, Guibas LJ, Pauly M. Partial and approximate symmetry detection for 3D geometry. ACM Trans Graph. 2006; 25(3):560–8.
  • Podolak J, Shilane P, Golovinskiy A, Rusinkiewicz S, Funkhouser T. A planar-reflective symmetry transform for 3D shapes. ACM Trans Graph. 2006; 25(3):549–59.
  • Fu H, Cohen-Or D, Dror G, Sheffer A. Upright orientation of man-made objects. ACM Trans Graph. 2008; 27(3):1–7.
  • Liu Y, Hel-Or H, Kaplan CS, Gool LV. Computational symmetry in computer vision and computer graphics. Foundations and Trends in Computer Graphics and Vision. 2010; 5(1):1-195.
  • Thrun S, Wegbreit B. Shape from symmetry. Proc Int Conf Computer Vision; 2005. p. 1824–31.
  • Hu R, Fan L, Liu L. Co-segmentation of 3D shapes via subspace clustering. Computer Graphics Forum. 2012; 31(5):1703–13.
  • Kraevoy V, Sheffer A, Shamir A, Cohenor D. Non-homogeneous resizing of complex models. ACM Trans Graph. 2008; 27(5):1–9.
  • Xu W, Wang J, Yin K, Zhou K, Van De Panne M, Chen F, Guo B. Joint-aware manipulation of deformable models. ACM Trans Graph. 2009; 28(3):1–9.
  • Gal R, Sorkine O, Mitra N, Cohen-Or D. iWires: An Analyze-And-Edit Approach To Shape Manipulation. ACM Trans Graph. 2009; 28(3):1–10.
  • Zheng Y, Fu H, Cohen-Or D, Au OKC, Tai CL. Component-wise controllers for structure-preserving shape manipulation. Computer Graphics Forum. 2011; 30(2):563–72.
  • Habbecke M, Kobbelt L. Linear analysis of nonlinear constraints for interactive geometric modeling. Computer Graphics Forum. 2012; 31(2):641–50.
  • Bokeloh M, Wand M, Seidel H P, Koltun V. An algebraic model for parameterized shape editing. ACM Transactions on Graphics. 2012; 31(4):1–10.
  • Newell M. The utilization of procedure models in digital image synthesis [PhD thesis]. The University of Utah; 1975.
  • Stiny G, Mitchell WJ. The Palladian grammar. Environment and Planning B. 1978; 5(1):5–18.
  • Flemming U. More than the sum of parts: the grammar of Queen Anne houses. Environment and Planning B Planning and Design. 1987; 14(3):323–50.
  • Muller P, Parish YIH. Procedural modeling of cities. SIGGRAPH; 2001. p. 301–8.
  • Greuter S, Parker J, Stewart N, Leach G. Real-time procedural generation of ’pseudo infinite’ cities. International Conference on Computer Graphics and Interactive Techniques in Australasia and South East Asia; 2003. p. 87–95.
  • Muller P, Vereenooghe T, Wonka P, Van Gool L. Procedural 3D reconstruction of puuc buildings in xkipché. International Symposium on Virtual Reality,Archeology and Cultural Heritage; 2006. p. 139–46.
  • Teboul O, Kokkinos I, Simon L, Sourakis PK, Paragios N. Shape grammar parsing via reinforcement learning. 2011. p. 2273–80.
  • Stava O, Benes B, Mech R, Aliaga DG, Kristof P. Inverse procedural modeling by automatic generation of L-systems. Computer Graphics Forum. 2010; 29(2):665–74.
  • Benes B, Stava O, Mech R, Miller G. Guided procedural modeling. Computer Graphics Forum. 2011; 30(2):325–34.
  • Vanegas C A, Aliaga D G, Benes B. Building reconstruction using manhattan-world grammars. IEEE CVPR; 2010. p. 358–65.
  • Mathias M, Martinovic A, Weissenberg J, Van Gool L. Procedural 3D building reconstruction using shape grammars and detectors. International Conference on 3D Imaging, Modeling, Processing, Visualisation and Transmission; 2011. p. 304–11.
  • Ripperda N, Brenner C. Application of a formal grammar to facade reconstruction in semiautomatic and automatic environments. Proc AGILE Conference on GIScience; 2009. p. 1–12.
  • Martinovic A, Van Gool L. Bayesian grammar learning for inverse procedural modeling. IEEE CVPR; 2013. p. 201–8.
  • Wu F, Yan D M, Dong W, Zhang X, Wonka P. Inverse procedural modeling of facade layouts. ACM TOG 34. 2014. p. 1–10.
  • Kelly T, Wonka P. Interactive architectural modeling with procedural extrusions. ACM Trans on Graph. 2011; 30(2):14–24.


  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.