点云数据转换成实体模型通过基于点的立体像素化立体像素PointCloudDataConversionintoSolidModelsviaPoint-BasedVoxelization1 2 3 4Tommy Hinks ; Hamish Carr ; Linh Truong-Hong ; and Debra F. Laefer, M.ASCEAbstract:Automatedconversionofpointclouddatafromlaserscanninginto formatsappropriateforstructuralengineeringholdsgreatprom- iseforexploitingincreasinglyavailableaeriallyandterrestriallybase dpixelizeddataforawiderangeofsurveying-relatedapplicationsfrom environmental modeling to disaster management. This paper introduces a point-based voxelization method to automatically transform pointclouddataintosolidmodelsforcomputationalmodeling.Thefundamentalvi abilityofthetechniqueisvisuallydemonstratedforbothaerial andterrestrialdata.Foraerialandterrestrialdata,thiswasachievedinl essthan30sfordatasetsupto650,000points.Inallcases,thesolid models converged without any user intervention when processed in a commercial ?nite-element method program. DOI: 10.1061/ASCESU.1943-5428.0000097 2013 American Society of Civil Engineers.CE Database subject headings: Data processing; Surveys; Finite element method; Information management.Author keywords: Terrestrial; Aerial; Laser scanning; LiDAR; Voxelization; Computational modeling; Solid models; Finite element.Introductionexist.Thispaperlaysthegroundworkforkeyadvancementinsucha pipeline. The procedure proposed herein to reconstruct buildingLaser scanning has achieved great prominence within the civil en- facadesfrompointcloud,whichisafundamentalstepforgenerating gineering community in recent years for topics as divergent as city-scale computational models.coastline monitoring Olsen et al. 2009, 2011, airport layout op- timization Parrish and Nowak 2009, and ground-displacementidenti?cation for water-system risk assessment Stewart et al.FacadeReconstruction2009. Additionally, there has been strong motivation to obtainfurther functionality from laser scanning and other remote-sensing Inrecentyears,developmentsinlaser-scanningtechnologyand?ight-data, including three-dimensional 3D volume estimation forpath planning have allowed aerial laser scanning ALS to acquire mining Mukherji 2012, road documentation Dong et al. 2007,pointclouddataquicklyandaccuratelyatacityscale,therebyhaving structuralidenti?cationShanandLee2005;Zhangetal.2012,and thepotentialforreconstructing3Dbuildingsurfacesacrossanentire emergency planning Laefer and Pradhan 2006. Furthermore,city in nearly real time. A number of approaches based on semi- computational responses of city-scale building groups are increas- automaticLangandForstner1996andautomaticHenricssonetal. inglyindemandforheightenedurbanization,disastermanagement,1996techniqueshavebeenproposedtoreconstructbuildingmodelsand microclimate modeling, but input data are typically too ex- from such data sets, but automatically extracting highly detailed, pensive as a result of the need for manual surveying. Additionally, accurate,andcomplexbuildingsstillremainsachallengeHaalaandcurrent software tools for transforming remote-sensing data into Kada 2010. The semiautomatic procedures need human operator computationalmodelshaveoneormoreofthefollowingproblems: intelligence.TheautomaticvisualmodelingofurbanareasfromALS alowdegreeofreliability,aninabilitytocapturepotentiallycritical data tends to extract sample points for an individual building by details,and/oraneedforahighdegreeofhumaninteraction.Todate, applying segmentation techniques and then reconstructing eacha seamless, automated, and robust transformation pipeline frombuilding individually. In such cases, vertical facade surfaces are notremote-sensing data into city-scale computational models does not portrayed in detail, and outlines may be of relatively low accuracy unless ground planes are integrated, which requires either a priori1 informationormanualintervention.Unfortunately,theeffectivenessDoctoralRecipient,SchoolofComputerScienceandInformatics,Univ.of engineering modeling often depends largely on the geometricCollege Dublin, Bel?eld, Dublin 4, Ireland. E-mail: ******************2accuracy and details of the building models?thus the currentSeniorLecturer,SchoolofComputing,FacultyofEngineering,Univ.ofmismatch.Leeds, Leeds LS2 9JT, U.K. E-mail: h.carr@//0>.3Post-doctoral Researcher, Urban Modelling Group, School of Civil, Presently, commercial products are generally semiautomatic StructuralandEnvironmentalEngineering,Univ.CollegeDublin,Bel?eld, Laefer et al. 2011, whereas in the computer graphics and photo- Dublin 4, Ireland. E-mail: linh.truonghong@gmailgrammetry communities, researchers have focused on automated4AssociateProfessor,LeadPI,UrbanModellingGroup,SchoolofCivil,surfacereconstructionfromdenseandregularsamplepointsHoppeStructuralandEnvironmentalEngineering,Univ.CollegeDublin,Bel?eld, 1994; Kazhdan et al. 2006. Unfortunately, ALS data are oftenDublin 4, Ireland corresponding author. E-mail: ******************* sparse and irregular, and may contain major occlusions on vertical Note.ThismanuscriptwassubmittedonNovember16,2011; approvedsurfaces owing to street- and self-shadowing Hinks et al. 2009.on September 10, 2012; published online on September 13, 2012. Discus- Dedicated urban modeling surface-reconstruction approachession period open until October 1, 2013; separate discussions must be generallyusethemajorbuildingplanesChenandChen2007andsubmitted for individual papers. This paper is part of the Journal ofcan be described as either model-driven or data-driven. Model-Surveying Engineering, Vol. 139, No. 2, May 1, 2013ASCE, ISSN0733-9453/2013/2-72?83/$25.00. driven techniques use a ?xed set of geometric primitives that are72 / JOURNALOFSURVEYINGENGINEERING?ASCE / MAY2013J. Surv. Eng. 2013.139:72-83.Downloaded from by East China Inst of Tech on 04/13/13.Copyright ASCE. For personal use only; all rights reserved.Fig. 1. Work?ow of the proposed approach: *Collection and preparation of LiDAR data involve multiple steps outside the scope of this paper’s scienti?ccontribution;thesegenerallyincludeplanning,collection,re gistration,and?ltering;seeTruong-Hong2011andHinks2011forfurther detailsttedtothepointdata.Suchtechniquescanbeeffectivewhenadataset is sparse because the ?tting of geometric primitives does not require complete data. In contrast, data-driven techniques derive surfaces directly from the point data and are capable of modeling arbitrarilyshapedbuildings.Generally,data-drivenapproachesaremore?exiblethanmodel-drivenapproaches,butareoftensensitiveto noise in the input data.For strictly visual representation, model-driven approachescanbeeffective.Forexample,Haalaetal.1998 proposed four dif-ferent primitives and their combinations to automatically derive 3D building geometry of houses from ALS and existing ground planes.Similarly, Maas and Vosselman 1999 introduced an invariantmoment-basedalgorithmfortheparametersofastandardgabled-roofhouse type that allowed for modeling asymmetric elements such as dormers. However, these efforts assume homogeneous point dis-Fig. 2. Octree representationtributions, which is unrealistic. You et al. 2003 also adapted a set of geometric primitives and ?tting strategies to model complex buildings with irregular shapes, but the approach required user interventionandgeneratedonlylimitedwalldetails.Huetal.2004used a combination of linear and nonlinear ?tting primitives to SolidModelingreconstructacomplexbuilding,inwhichaerialimagerywasusedtore?ne the models. To generate building models directly from point cloud data forIncontrast,manydata-driventechniquesoperatingonALSdata engineering simulations [e.g., FEM], there are three dominant reconstruct roof shapes directly from sample points of roof planes. methods:1constructivesolidgeometryCSG,whereobjectsareSubsequently, the remainder of the building is simply extruded represented using Boolean combinations of simpler objects; 2 to the ground level from the roof-shape outlines. Vosselman and boundary representations B-reps, where object surfaces are rep- Dijkman2001usedaHoughtransformforextractionofplanefaces resentedeitherexplicitly orimplicitly;and3spatialsubdivision roofplanesfromtheALSdata,andthen3Dbuildingmodelswere representations,wherean objectdomain is decomposed intocells reconstructed by combining ground planes and the detected roof withsimple topologic and geometric structure, such as regular planes.Hofmannetal.2003introducedamethodtoextractplanar gridsandoctreesGoldman2009;HoffmannandRossignac1996;roof faces by analyzing triangle mesh slopes and orientations from there are many extensive treatises available for in-depth consid-a triangular irregular network structure generated from ALS data. eration of this topic B?hm et al. 1984; Rossignac and Requicha More recently, Dorninger and Pfeifer 2008 used an a-shape ap- 1984, 1999.proach to determine a roof outline from point clouds of the roof Generating solid models automatically from point cloud data projectedontoahorizontalplane.Also,ZhouandNeumann2010 is particularly important because the cost of manually creating created impressive buildings for a large urban area by using a vol- solid models of existing objects is far greater than the associated umetric modeling approach in which roof planes were determined hardware,software,andtrainingcosts.Assuch,spatialsubdivision based on a normal vector obtained from analysis of grid cells be- representations are used extensively for creating solid models of longingtorooflayers.However,thesemodelsarealsoextrudedand buildings in which regular grids or octrees are employed to de- lack vertical-wall details. compose an entire object intononoverlapping 3D regions, com-Therefore, this paper presents an automated approach to con- monly referred to as voxels. Voxels are usually connected andverting point clouds of individual buildings into solid models for described a simple topologic and geometric structure. In grids, structural analysis by means of computational analysis in which avolumeissubdividedintosmallerregionsbyappropriateplanes thepointcloudthatweresemiautomaticallysegmentedfromLight parallel to the coordinate system axes,typically using aCartesian Detection and Ranging LiDAR data become the input Fig. 1. coordinate system. An initial voxel bounding all point data re-Notably, this proposed approach focuses on reconstructing solid cursively divides a volume into eight subvoxels, organized in modelsbyusingvoxelgridswiththecriticalparameteraseitherthe a hierarchical structure Samet 1989. Voxels may be labeled voxel size or the number of voxel grids; for more details on col- white,black,orgraybasedontheirpositionsFig.2.Blackvoxels lecting ALS and terrestrial laser scanning TLS data and on are completely inside the solid, whereas white voxels are com- segmenting point clouds, see Truong-Hong 2011andHinks pletelyoutside.Voxelswithbothblackandwhitechildrenaregray 2011. Hoffmann and Rossignac 1996.JOURNALOFSURVEYINGENGINEERING?ASCE / MAY2013 / 73J. Surv. Eng. 2013.139:72-83.Downloaded from by East China Inst of Tech on 04/13/13. Copyright ASCE. For personal use only; all rights reserved.Fig.3.Voxelgridspanningavolumeina3Dspaceboundedbyx ,x ,y ,y ,andz ,z ,whe reDx,Dy,andDzarevoxelsizes andmin min minN , N , and N are the number of voxels in each directionx y zIn an application of spatial subdivision for surface recon-struction,CurlessandLevoy1996presentedavolumetricmethodforintegratingrangeimagestoreconstruc tanobject’ssurfacebasedon acumulative weighted signed-distancefunction. Unfortunately,the approach is not suited for arbitrary objects. In related work, GuarnieriandPontin2005builtatriangulatedmeshofanobject’ssurfacebycombiningaconsensussurface[asproposedbyWheeleret al. 1998], an octree representation, and the marching-cubesalgorithm Lorensen and Cline 1987. This multifaceted algorithmFig. 4. Point-based voxelization avoids surface reconstruction and canreducetheeffectofthenoiseowingtosurfacesampling,sensoroperates directly on point datameasurements,andregistrationerrors.However,foroptimalresults,themethodrequiresmodi?cationofparametersthatdependheavilyon input-data characteristics such as the voxel size, the threshold value for the angle, and the distance between two consecutive neighbor-range viewpoints. z 2zminN? 1 ?3?zDzThevoxelhaseightlatticeverticesassociatedwithsixrectangular VoxelizationfacesFig.3.Eachinteriorvoxelhas26neighboringvoxels,witheight sharing a vertex,12 sharing an edge,and six sharing a face. Critical to octree/quadree representations for further processing is Conversely,anexteriororinteriorvoxelonahole’sboundaryoften voxelization. This term describes the conversion of any type of has only 17 neighboring voxels four sharing a vertex, eight geometric or volumetric object such as a curve, surface, solid, or sharinganedge,and?vesharingaface.Moreover,mostexisting computedtomographicdataintovolumetricdatastoredina3Darray voxelization techniques operate on surface representations ofof voxels Karabassi et al. 1999. Initially, a voxel grid divides objects, where a signi?cant part of the problem is to identifya bounded 3D region into a set of cells, which are referred to as throughwhichvoxelsthesurfacespass.Suchmethodsarereferredvoxels. The division is typically conducted in the axial directions to as surface-based voxelization Cohen-Or and Kaufman 1995of a Cartesian coordinate system. Before voxelization, three pairs [Fig.4a?c].Incontrast,thepoint-basedvoxelizationinthispaper ofcoordinatevalues??x , x , ?y , y , and ?z , z ? aremin min minoperates directly on the point data and does not require a derived createdalongthethreeaxesX, Y, and Zde?ningaglobalsystemsurface [Fig. 4a?c]. Point-based voxelization is conceptually Fig. 3. The basic idea of a voxelization algorithm is to examine much simpler than surface-based voxelization algorithms, and whethervoxelsbelongtotheobjectofinterestandtoassignavalue whereas the mechanisms are well known, they have not beenof 1 or 0,respectively Karabassi et al. 1999; a further description applied to generating solid modeling of buildings from LiDARof voxel grids is available in Cohen and Kaufman 1990.data.An initial voxel bounding all point cloud data in 3D Euclidean3Asmentionedearlier,eachvoxelisclassi?edasactiveorinactivespaceR is subdivided into subset voxels by grids along the x-, y-, corresponding to binary values based on the sample points within andz-coordinatesinaCartesiancoordinatesystem.Eachvoxelinthethat voxel [Eq. 4]subset is represented by an index v?i, j, k?, where i2?0; N 21 , xj2?0; N 21 , and k2?0; N 21 Fig. 3. With the dimensionsy zactive ifn$TnofindividualvoxelsDx, Dy, Dz,anumberofvoxelsN , N , Nx y zf n?4?valong each direction are given in Eqs. 1?3 inactive ifn,Tnwheretheargumentn5numberofpointsmapping to avoxel,andx 2xmin T 5user-speci?edthresholdvalue.Typically,T 51,whichmeansn nN? 1 ?1?xDxthat voxels containing at least one mapping point are classi?edasactiveandallothersasinactive.Moresophisticateddensity-basedy 2yminclassi?cation functions can be designed. An example is shown inN? 1 ?2?yDyFig. 5.74 / JOURNALOFSURVEYINGENGINEERING?ASCE / MAY2013J. Surv. Eng. 2013.139:72-83.Downloaded from by East China Inst of Tech on 04/13/13. Copyright ASCE. For personal use only; all rights reserved.Fig. 5. Voxelization model of front building of Trinity College, Dublin, Ireland, created by a voxel grid: a input data set of 245,000 ALS points;bvoxelizationmodelwithvoxelsizeDx5Dy5Dz50:25m;cvoxelclassi?cationwiththethresholdT51andvoxelizationmodelwithaboutn5,000 active voxels n is the largest number of points mapping to asingle voxelFig. 6. Solid model componentsProposedConversionofVoxelizedModelsintoSolidModelsTo reconstruct vertical surfaces of building models, a voxel grid is used to divide data points in a bounded 3D region into smallervoxels. Important facade features such as windows and doors are subsequently detected basedon a voxel’s characteristics, where an inactive voxel represents the inside of an opening. Consequently, building models are converted into an appropriate format for com- putational processing.Anobjectisde?nedbyitssurfaceboundary,whichthenmustbeFig. 7. Face orientation as dictated by the right-hand ruleconvertedintoanappropriatesolidrepresentationcompatiblewithcommercialcomputationalpackages.Althoughmanyschemesareavailable,B-repsarehereinadoptedbecauseoftheircompatibilitywith commercial structural-analysis software e.g., ANSYS soft- Keypointsarerepresentedbya3Dcoordinateofasingularpoint.ware Laefer et al. 2011. The proposed method de?nes both the An edge is de?ned as the connection between exactly two keygeometry and topology of an object by a set of nonoverlappingpoints;forexample,theedgee 5fP, Pgistheedgewithstartingij i jandendingpointP.Notably,edgeshaveanorientation;asfaces approximate the boundary of the solid model. This section pointPi jsuch, e 52eThus, the edges e and e would be ?ipped. EdgepresentsabriefdescriptionoftheB-repschemeimplementedintheij ji ij jiproposed approach; for more details, see Goldman 2009. Ge- ?ipping is important when de?ning an orientable face for dis-ometry is de?ned by key singular points, with each point rep- tinguishing the inside from the outside.resenting a speci?c location in space. Topology is de?ned by Similarly, faces represent surfaces of a solid model that areconnections between key points. When used together, they can connections between edges. The faces are further connected de?neasolidmodelFig.6.DatastructuresfordescribingB-reps to form volumes. A face is de?ned as a list of edgesoften capture the incidence relations between a face and its f5fe ,e ,.,e g that involve closed paths. A face01 12 ?n22??n21?bounding edges and an edge and its bounding vertices, whichconsistingofthreekeypointsisatriangle,whereasqu。
