【優(yōu)秀碩士博士論文】散亂點(diǎn)云三角網(wǎng)格化技術(shù)研究與實(shí)現(xiàn)

碩士學(xué)位論文散亂點(diǎn)云三角網(wǎng)格化技術(shù)研究與實(shí)現(xiàn)REASEARCHANDAPPLICATIONOFTECHNIQUESON3DPOINTCLOUDNOISEREDUCINGANDSAMPLING學(xué)科專業(yè)機(jī)械電子工程論文題目散亂點(diǎn)云三角網(wǎng)格化技術(shù)研究與實(shí)現(xiàn)學(xué)科專業(yè)機(jī)械電子工程摘要隨著三維光學(xué)掃描技術(shù)的發(fā)展，已經(jīng)能夠獲得高精度的點(diǎn)云數(shù)據(jù)，然而如何高效地通過點(diǎn)云數(shù)據(jù)得到逼真的曲面模型是當(dāng)前逆向工程和產(chǎn)品質(zhì)量檢測中的一個難題。在各種曲面建模表現(xiàn)方式中，三角網(wǎng)格模型以其結(jié)構(gòu)簡單，便于計算，能夠高精度的逼近原始曲面等優(yōu)點(diǎn)，成為參數(shù)曲面的標(biāo)準(zhǔn)表示方法。本文針對逆向工程中的點(diǎn)云三角網(wǎng)格化技術(shù)，對散亂點(diǎn)云的三角剖分，建模之后的網(wǎng)格簡化和網(wǎng)格平滑技術(shù)進(jìn)行了深入的研究，主要內(nèi)容和成果有1設(shè)計并實(shí)現(xiàn)了針對三維光學(xué)測量系統(tǒng)的點(diǎn)云三角化系統(tǒng)方案，首先對散亂點(diǎn)云進(jìn)行三角網(wǎng)格剖分，接著對三角剖分后的網(wǎng)格模型進(jìn)行簡化處理，最后將網(wǎng)格模型光順處理，得到完整優(yōu)化的曲面模型由于逆向設(shè)計和產(chǎn)品的質(zhì)量檢測。2研究了海量點(diǎn)云的三角剖分技術(shù)。提出并實(shí)現(xiàn)了一種基于空間分割的曲面擬合三角化算法，對沒有拓?fù)浣Y(jié)構(gòu)的海量點(diǎn)云數(shù)據(jù)進(jìn)行空間劃分，求取每一個采樣點(diǎn)的K個鄰域點(diǎn)，計算點(diǎn)的切平面之后,構(gòu)建空間點(diǎn)到切平面的距離函數(shù)進(jìn)行插值，最后通過步進(jìn)立方體的算法生成網(wǎng)格模型。該算法提高了海量數(shù)據(jù)的處理效率，改善了曲面邊界及尖銳區(qū)域的重建效果。3研究并實(shí)現(xiàn)了網(wǎng)格模型的精簡技術(shù)，通過計算邊折疊代價實(shí)現(xiàn)了基于曲率的邊折疊簡化算法，將曲率作為判斷基準(zhǔn)進(jìn)行邊折疊的更新操作，達(dá)到網(wǎng)格簡化的目的，能夠在減少數(shù)據(jù)數(shù)據(jù)量的同時保持模型上的細(xì)小特征。4研究并實(shí)現(xiàn)了網(wǎng)格模型的光順技術(shù)，采用基于法失的自適應(yīng)雙邊濾波算法進(jìn)行濾波，首先根據(jù)鄰域點(diǎn)估算點(diǎn)的法失，其次在二階鄰域點(diǎn)內(nèi)計算濾波因子，最后計算出點(diǎn)的新坐標(biāo)值。該方法能較好保持幾何特性并實(shí)現(xiàn)曲面光順。經(jīng)過試驗(yàn)和分析，并結(jié)合在三維光學(xué)測量系統(tǒng)中的應(yīng)用，結(jié)果表明本系統(tǒng)能夠?qū)崿F(xiàn)散亂三維點(diǎn)云的三角網(wǎng)格重建，效果良好。關(guān)鍵詞網(wǎng)格重建；三角化；包圍盒劃分；網(wǎng)格簡化；網(wǎng)格光順論文類型應(yīng)用研究TITLEREASEARCHANDAPPLICATIONOFTECHNIQUESONPOINTCLOUDNOISEREDUCINGANDSAMPLINGSPECIALITYMECHANICALELECTRONICENGINEERINGAPPLICANTHUANGWANGSUPERVISORASSOCVICEPROFJINLIANGABSTRACTWITHTHETHREEDIMENSIONALOPTICALSCANNINGTECHNOLOGY,HASBEENABLETOOBTAINHIGHPRECISIONPOINTCLOUDDATA,BUTHOWTOEFFICIENTLYTHROUGHTHEPOINTCLOUDSURFACEDATAAREREALISTICMODELISTHECURRENTREVERSEENGINEERINGANDPRODUCTQUALITYTESTINGINAPROBLEMINAVARIETYOFMANIFESTATIONSOFSURFACEMODELING,TRIANGULARMESHMODELOFITSSIMPLESTRUCTURE,EASYCALCULATION,HIGHPRECISIONAPPROXIMATIONTOTHEORIGINALSURFACE,ETC,TOBECOMETHESTANDARDPARAMETRICSURFACEREPRESENTATIONINTHISPAPER,THEPOINTCLOUDREVERSEENGINEERINGTRIANGULARMESHTECHNOLOGY,THESCATTEREDPOINTCLOUDTRIANGULATION,MODELINGTHEGRIDAFTERTHEGRIDSMOOTHINGTECHNIQUETOSIMPLIFYANDCONDUCTEDINDEPTHRESEARCH,THEMAINCONTENTSANDRESULTSARE1DESIGNANDIMPLEMENTATHREEDIMENSIONALOPTICALMEASUREMENTSYSTEMFORPOINTCLOUDTRIANGULATIONGRIDDINGPROGRAM,FIRSTOFALLPAIRSOFSCATTEREDPOINTCLOUDFORTRIANGULATION,ANDTHENRIGHTAFTERTHETRIANGULATIONMESHSIMPLIFIEDMODEL,ANDFINALLYNETWORKLATTICEMODELSMOOTHINGTREATMENT,GETACOMPLETESURFACEMODELOPTIMIZATIONDUETOREVERSETHEDESIGNANDPRODUCTQUALITYTESTING2STUDYOFTHEMASSPOINTCLOUDTRIANGULATIONTECHNIQUESPROPOSEDANDIMPLEMENTEDASPACEBASEDSEGMENTATIONOFTHESURFACEFITTINGTRIANGULATIONALGORITHM,THEREISNOTOPOLOGICALSTRUCTUREOFMASSIVEPOINTCLOUDDATAINTOSPACETOSTRIKEASAMPLEPOINTFOREACHNEIGHBORHOODOFAPOINTOFKTOCALCULATEPOINTSTANGENTPLANE,THECONSTRUCTIONOFSPACEPOINTSTOTHETANGENTPLANEDISTANCEFUNCTIONINTERPOLATION,THEFINALADOPTIONOFMARCHINGCUBESALGORITHMGENERATESMESHMODELTHEALGORITHMIMPROVESTHEEFFICIENCYOFMASSDATAPROCESSINGANDIMPROVETHESURFACERECONSTRUCTIONOFTHEREGIONBOUNDARIESANDSHARPEFFECT3STUDYANDIMPLEMENTATIONOFTHEGRIDMODELTOSTREAMLINETHETECHNOLOGYANDTHEPRICEACHIEVEDBYCALCULATINGTHEEDGECOLLAPSEBASEDONTHECURVATUREOFTHEEDGECOLLAPSESIMPLIFICATIONALGORITHM,THECURVATUREOFEDGECOLLAPSEASABENCHMARKTOJUDGETHEUPDATEOPERATION,TOACHIEVETHEPURPOSEOFMESHSIMPLIFICATION,CANBEREDUCEDATAAMOUNTOFDATAWHILEMAINTAININGASMALLMODELFEATURES4STUDYANDIMPLEMENTATIONOFTHEGRIDMODELSMOOTHINGTECHNIQUES,LOSSBASEDMETHODOFADAPTIVEBILATERALFILTERINGALGORITHMFORFILTERING,THEFIRSTNEIGHBORHOODOFPOINTSUNDERTHEPOINTESTIMATESOFTHEFRENCHLOSS,FOLLOWEDBYSECONDORDERNEIGHBORHOODSPOTSINTHECALCULATIONOFFILTERFACTORANDFINALLYCALCULATETHENEWCOORDINATESOFPOINTSTHISMETHODCANMAINTAINTHEGEOMETRICPROPERTIESANDTOACHIEVESURFACESMOOTHNESSTHROUGHTESTINGANDANALYSIS,COMBINEDWITHTHREEDIMENSIONALOPTICALMEASUREMENTSYSTEMAPPLICATIONRESULTSSHOWTHATTHESYSTEMCANACHIEVETHESCATTERED3DPOINTCLOUDOFTHETRIANGULARMESHRECONSTRUCTION,GOODEFFECTKEYWORDSGRIDRECONSTRUCTIONTRIANGULATIONBOUNDINGBOXDIVISIONMESHSIMPLIFICATIONMESHSMOOTHINGTYPEOFTHESISAPPLICATIONRESEARCH目錄1緒論111引言112三維點(diǎn)云三角化技術(shù)1121研究背景1122國內(nèi)外研究現(xiàn)狀213課題來源與研究意義5131課題來源5132研究意義514研究內(nèi)容與技術(shù)路線6141研究內(nèi)容6142技術(shù)路線615本文結(jié)構(gòu)安排72散亂點(diǎn)云三角網(wǎng)格重建方案921引言922XJTUOM系統(tǒng)及網(wǎng)格重建環(huán)節(jié)9221XJTUOM三維光學(xué)掃描系統(tǒng)介紹9222點(diǎn)云三角網(wǎng)格重建所處的環(huán)節(jié)1023點(diǎn)云網(wǎng)格重建關(guān)鍵技術(shù)分析11231點(diǎn)云三角化11232網(wǎng)格簡化13233網(wǎng)格光順1424點(diǎn)云網(wǎng)格重建系統(tǒng)方案設(shè)計15241點(diǎn)云網(wǎng)格重建系統(tǒng)設(shè)計原則15242針對三維光學(xué)測量的點(diǎn)云三角化方案15243點(diǎn)云三角化目標(biāo)的制定1625本章小結(jié)163點(diǎn)云三角網(wǎng)格劃分1731引言1732MARCHINGCUBES算法原理17321基本定義17322基本原理與步驟18323三角形頂點(diǎn)位置和法向計算1933基于空間分割的三角網(wǎng)格劃分20331空間劃分及鄰域計算20332點(diǎn)云切平面計算22333場函數(shù)定義24334算法實(shí)現(xiàn)2434實(shí)驗(yàn)結(jié)果及分析2635本章小結(jié)294三角網(wǎng)格的簡化與光順3041引言3042網(wǎng)格基礎(chǔ)30421網(wǎng)格表示的數(shù)據(jù)結(jié)構(gòu)30422三維網(wǎng)格中的基本定義3143網(wǎng)格簡化32431簡化算法的分類及評價32432基于曲率的邊折疊簡化算法32433實(shí)驗(yàn)效果及分析3644網(wǎng)格光順38441常用網(wǎng)格光順?biāo)惴?8442點(diǎn)的法向量的計算39443基于法失調(diào)整的雙邊濾波網(wǎng)格光順?biāo)惴?0444實(shí)驗(yàn)效果及分析4245本章小結(jié)455系統(tǒng)實(shí)現(xiàn)及應(yīng)用4651引言4652點(diǎn)云網(wǎng)格重建系統(tǒng)方案的實(shí)現(xiàn)46521軟件的實(shí)現(xiàn)46522功能模塊46523點(diǎn)云網(wǎng)格建模過程4853應(yīng)用實(shí)例5354本章小結(jié)556結(jié)論與展望5661結(jié)論5662展望56致謝58參考文獻(xiàn)59附錄62攻讀學(xué)位期間取得的研究成果63聲明CONTENTS1PREFACEX11DRIPIRRIGATIONTECHNOLOGYX111DRIPIRRIGATIONSYSTEMSX2RAPIDDEVELOPMENTOFLABYRINTHDRIPIRRIGATIONEMITTERSX21STRUCTURALDESIGNOFLABYRINTHDRIPIRRIGATIONEMITTERSX211THEORYX26BRIEFSUMMARYX12CONCLUSIONSANDSUGGESTIONSXACKNOWLEDGEMENTSXREFERENCESXAPPENDICES（單個附件用APPENDIX）XACHIEVEMENTSXDECLARATIONEQUATIONCHAPTER1SECTION1MERGEFORMAT111緒論11引言隨著計算機(jī)圖形學(xué)的發(fā)展，很多領(lǐng)域都出現(xiàn)了對“實(shí)體數(shù)字化”技術(shù)的強(qiáng)烈要求，越來越多的企業(yè)、研究機(jī)構(gòu)甚至個人迫切地需要得到實(shí)體的高精度數(shù)字化模型，而利用傳統(tǒng)的幾何造型技術(shù)進(jìn)行設(shè)計不僅費(fèi)時而且不能得到物體真實(shí)的幾何信息。正是在這樣的應(yīng)用背景下，三維光學(xué)測量技術(shù)實(shí)現(xiàn)了飛速的發(fā)展。三維掃描能獲得物體表面點(diǎn)的三維坐標(biāo)信息，它屬于一種立體測量技術(shù)。與傳統(tǒng)測量技術(shù)相比，它能夠完成對復(fù)雜物體的測量，特點(diǎn)是非接觸、精度高、速度快，能大幅節(jié)約時間和成本，并且其測量數(shù)據(jù)通用性比較強(qiáng)。這些優(yōu)勢使三維掃描技術(shù)得到了廣泛的應(yīng)用，并且在某些特殊場合，三維掃描技術(shù)還具有獨(dú)特的、不可替代的作用。比如測量比較柔軟的物體，用傳統(tǒng)的接觸測量方法，很可能在測量時使物體變形，從而使測量結(jié)果不準(zhǔn)確，而三維掃描技術(shù)以光為測量媒質(zhì)，不會引起物體表面的形變和損傷。三維掃描技術(shù)在眾多領(lǐng)域內(nèi)的廣泛應(yīng)用。其中最為重要的并且最為代表性的應(yīng)用領(lǐng)域?yàn)槟嫦蚬こ毯唾|(zhì)量檢測。三維光學(xué)掃描儀采用非接觸的測量方法，直接得到真實(shí)物體表面的采樣點(diǎn)，即點(diǎn)云數(shù)據(jù)，利用點(diǎn)云數(shù)據(jù)即可以重構(gòu)出任意曲面。如何快速的講點(diǎn)云數(shù)據(jù)轉(zhuǎn)變化為實(shí)體模型是逆向工程中需要解決的重要問題。本章首先介紹了點(diǎn)云三角化技術(shù)的研究背景、國內(nèi)外研究狀況，然后闡述了本課題的來源和研究意義，最后說明了本文的主要研究內(nèi)容和技術(shù)路線。12三維點(diǎn)云三角化技術(shù)121研究背景計算機(jī)輔助設(shè)計與制造（CAD/CAM）技術(shù)是計算機(jī)應(yīng)用最重要的領(lǐng)域之一，是先進(jìn)制造技術(shù)的重要組成部分，它是指利用計算機(jī)技術(shù)完成設(shè)計過程中的信息檢索、分析、計算、綜合、修改及文件編制工作。上個世紀(jì)90年代以來，隨著激烈的市場競爭，對產(chǎn)品研發(fā)的時間和產(chǎn)品的更新?lián)Q代速度提出了越來越高的要求，因此，逆向工程技術(shù)1（REVERSEENGINEERING）應(yīng)運(yùn)而生。通過三維激光掃描得到的點(diǎn)云數(shù)據(jù)，需要建立起三維模型。早期，三維模型大多是從三維視圖和照片用手工建立起來的，這類建模方法通常和某些軟件結(jié)合在一起，常用的如3DSTUDIO、AUTOCAD、3DSMAX等。這樣的方法在概念上有嚴(yán)格的數(shù)學(xué)描述，對幾何形體有精確表達(dá)，可控制形狀的平滑并有很多基于物理的高級建模工具。但這種方法需要物體的參數(shù)表達(dá)，模型不連續(xù)且在撲結(jié)構(gòu)上不靈活。目前最流行的方式是用多邊形網(wǎng)格來描述和繪制三維模型，它把三維模型表面的點(diǎn)連接成以多邊形為單位的網(wǎng)格，是一種簡單而高效的表達(dá)方式。它可以表達(dá)復(fù)雜的表面，提供很強(qiáng)的適應(yīng)性，其中尤以三角網(wǎng)格的使用最為廣泛。相對于早期手工建模，三角形網(wǎng)格的方法采用了分段線性擬合的思想，可以在物體表面不規(guī)則地采集樣本點(diǎn)并完全不需要對物體進(jìn)行參數(shù)化。因?yàn)樯鲜龅倪@些優(yōu)點(diǎn)，三角形作為為三維模型的基本要素已經(jīng)被廣泛地接受，三角形網(wǎng)格繪制的方法也獲得了大部分計算機(jī)硬件的支持。三維掃描中采集到的點(diǎn)云數(shù)據(jù)具有數(shù)據(jù)龐大的特點(diǎn)，并且由于采集中不可避免的會有噪聲的存在，因此在對點(diǎn)云進(jìn)行網(wǎng)格重建后，需要對網(wǎng)格模型進(jìn)行后續(xù)的精簡和關(guān)順操作，這些點(diǎn)云處理技術(shù)就是本文研究的重點(diǎn)。122國內(nèi)外研究現(xiàn)狀三角網(wǎng)格自動剖分技術(shù)的研究起源于20世紀(jì)70年代，主要為了滿足航空、數(shù)學(xué)、地質(zhì)等領(lǐng)域解決實(shí)際問題的需要。20世紀(jì)80年代三角網(wǎng)格剖分在眾多領(lǐng)域引起了廣泛的關(guān)注，世界各國的學(xué)者和研究機(jī)構(gòu)從不同的需求出發(fā)，對三角網(wǎng)格剖分進(jìn)行深入的研究。目前，點(diǎn)集的網(wǎng)格剖分的主要研究集中在曲面網(wǎng)格剖分以及邊界的一致性問題問題，散亂點(diǎn)云的網(wǎng)格重建技術(shù)2,3,4成為圖形學(xué)中一個活躍的研究方向,目前主要包括有以下幾個研究方向1）基于德勞內(nèi)（DELAUNAY）準(zhǔn)則的方法DELAUNAY準(zhǔn)則的方法主要應(yīng)用VORONOI圖對散亂點(diǎn)云進(jìn)行DELAUNAY三角化，其主要思想是對每個采樣點(diǎn)在各個方向探索所有鄰域，尋找可能的鄰近點(diǎn)來計算曲面。1972年，LAWSON5提出了三角化的最大內(nèi)角最小化原則，符合這一原則的三角化稱為局部均勻的。隨后SIBON29證明了DELAUNAY三角化是符合這一原則的唯一形式。緊接著GREENANDSIBONL實(shí)現(xiàn)了二維空間的VORONOI圖的計算及DELAUNAY三角化。BOWYER和WATSON把結(jié)果推廣到任意維。隨后出現(xiàn)了大量的文獻(xiàn)，用各種不同的方法去實(shí)現(xiàn)VORONOI圖和DELAUNAY三角化。由于DELAUNAY三角剖分后的結(jié)果是一個三角形二維或四面體三維的凸包，并不表示真正的原物體表面，其中包含許多冗余的三角形或四面體。常用的DELAUNAY準(zhǔn)則方法主要有增量法和分治算法。增量法通過遍歷所有離散點(diǎn)，求出點(diǎn)集包圍盒，再將點(diǎn)集中的點(diǎn)依次逐點(diǎn)插入。增量法如圖11所示，首先找出包含新頂點(diǎn)的三角形，然后再做局部的修改和優(yōu)化，直至所有點(diǎn)均插入為止。該方法理論嚴(yán)密，唯一性好，且易滿足DELAUNAY三角化的空外接圓特性。二維BOWYER/WATSON算法先生成給定點(diǎn)區(qū)域的大三角化，然后遞增地向其中插入新點(diǎn)。新插入點(diǎn)落在一些現(xiàn)有三角片的外接圓內(nèi)時，這些三角片圖中深色部分就不再是DELAUNAY三角片了，首先將其刪除。由于剩余三角片依然還都是DELAUNAY三角片，只需在插入點(diǎn)周圍形成的空多邊形內(nèi)增加新的三角片，分別連接插入頂點(diǎn)與空多邊形各頂點(diǎn)，即可形成新的DELAUNAY三角化。重復(fù)上述操作直至所有頂點(diǎn)均插入到三角化當(dāng)中。分治算法，將點(diǎn)集分成規(guī)模相當(dāng)?shù)膬刹糠?，對形成的兩部分再進(jìn)行分割，如此遞歸處理，然后對兩部分作拼合計算，直至最后全部完成。LEWIS和ROBINSON在1977年首先提出分治算法，并將分治算法的基本思想應(yīng)用于DELAUNAY三角網(wǎng)格的構(gòu)建。其思路是采用遞歸分割點(diǎn)集直至每個子集中僅含三個離散點(diǎn)而形成三角形的辦法，經(jīng)過自下而上逐級合并生成最終的三角網(wǎng)。圖11BOWYER/WATSON算法示意圖DELAUNAY算法的優(yōu)點(diǎn)就是重建曲面網(wǎng)格的復(fù)雜性和輸入采樣點(diǎn)的復(fù)雜性成正比，而且采樣濃度未知也能夠界定重建質(zhì)量。其主要缺點(diǎn)就是計算DELAUNAY三角形需要較大的內(nèi)存開銷和時間，對于大規(guī)模的點(diǎn)云，這些方法就顯得力不從心。2）基于區(qū)域增長的方法區(qū)域增長的方法基本原理是從一種子三角形開始，基于某種準(zhǔn)則，不斷選擇新點(diǎn)并加入當(dāng)前的區(qū)域邊界，生成新三角形，更新邊界，直到遍歷所有點(diǎn)，將所得數(shù)據(jù)集的初始剖分優(yōu)化后，獲取逼近被測面的三角網(wǎng)格。算法的關(guān)鍵是按照怎樣的規(guī)則在點(diǎn)云中選擇新的點(diǎn)。如圖12所示BOISSOLMAT中率先介紹了這種算法，并以三角形張角最大為選點(diǎn)準(zhǔn)則。CHOFI43的三角形遞增基于以下假設(shè)存在某個三維點(diǎn)，由該點(diǎn)可看到被測面上所有散亂點(diǎn)，并V可定義以為錐頂?shù)耐瑰F，使之包含所有散亂點(diǎn)。初始三角剖分后，以最小內(nèi)角最大V和光順性準(zhǔn)則優(yōu)化網(wǎng)格。該算法具有可直接處理凸封閉曲面和開曲面的優(yōu)點(diǎn)，盡管如此，因受凸錐頂角的角度限制，所建曲面可能存在不穩(wěn)定區(qū)域。GOPI等人基于低維DELAUNAY三角剖分技術(shù)，快速實(shí)現(xiàn)每個數(shù)據(jù)點(diǎn)的局部拓?fù)渲亟ǎ詣映C正局部數(shù)據(jù)點(diǎn)的非法連接關(guān)系，算法效率高，能處理大規(guī)模數(shù)據(jù)點(diǎn)云。CROSSNO基于螺旋邊準(zhǔn)則，即從初始三角網(wǎng)格的邊界開始，對邊界上的每個點(diǎn)按最小內(nèi)接圓準(zhǔn)則得到新的三角形，更新邊界，直至覆蓋整個數(shù)據(jù)點(diǎn)云，該法在數(shù)據(jù)分布均勻時效率很高。BEMARDINI47的滾球法，又稱BPA算法BALLPIVOTINGALGORITHM是基于即E理論，利用半徑為的球在數(shù)據(jù)點(diǎn)云中的滾動建立網(wǎng)格。滾球遵循的基本原則是若該球接R觸到3個點(diǎn)，且不含其它點(diǎn)，則該點(diǎn)形成一個三角形。該法繼承了的各種優(yōu)良性能，并具有概念簡單、直觀、參數(shù)設(shè)置少、執(zhí)行時間為線性、存儲要求低、魯棒性好、能處理簡單模型等優(yōu)點(diǎn)，可惜因難以確定滾球半徑而致算法效率低。此外，文獻(xiàn)中的方法，對于每一條活動邊，分別將與這條邊的兩個端點(diǎn)距離最近的個點(diǎn)投影到這條邊K所在的三角面片決定的平面上，從這些投影點(diǎn)中選擇一點(diǎn)，這一點(diǎn)所對應(yīng)的點(diǎn)云中的點(diǎn)與這條邊形成一個新的三角面片。ABCD圖12三角網(wǎng)格生長算法基于區(qū)域生長的方法能處理大規(guī)模數(shù)據(jù)點(diǎn)云，可直接處理凸封閉曲面和開曲面情況，然而，該類方法通常需人為對數(shù)據(jù)點(diǎn)云預(yù)先劃分區(qū)域，不可靠，也降低了自動化程度，對于噪音則顯得無能為力。3）基于隱士曲面擬合的方法隱式曲面擬合方法是使用隱函數(shù)曲面擬合數(shù)據(jù)點(diǎn)，然后在零等值面上提取三角形網(wǎng)格的一類方法。這些隱函數(shù)通常為徑向基函數(shù)或多項(xiàng)式函數(shù)，而提取三角形網(wǎng)格的方法，主要以MATCHINGCUBE和BLOOMENTHAL多邊形化這兩種方法為代表。曲面擬合方法可用一個函數(shù)解析表達(dá)式完全表達(dá)被測表面的曲面方程，廣泛應(yīng)用于計算機(jī)視覺、模式識別等鄰域，但整體逼近的方式致使逼近精度往往不高否則導(dǎo)致解大規(guī)模的線性方程，如徑向基函數(shù)擬合法，因此常常需要進(jìn)行局部細(xì)微特征的擬合。1996年，F(xiàn)LOATER使用分層結(jié)構(gòu)的緊支撐徑向基函數(shù)，首先使用DELAUNAY三角剖分計算數(shù)據(jù)子集的嵌套序列，每層基函數(shù)的尺度由來自三角化信息的當(dāng)前層的點(diǎn)云濃度所決定。這個方法大大降低了傳統(tǒng)徑向基函數(shù)插值/逼近散亂點(diǎn)的時間效率問題。2001年，CARR等人提出了一種通過貪婪選擇過程減少基函數(shù)中心的快速算法，叫快速多極方法?？焖俣鄻O方法能夠?qū)资f個點(diǎn)，使用一個簡單的RBF函數(shù)來實(shí)現(xiàn)快速的擬合，同時對缺失的點(diǎn)云能夠?qū)崿F(xiàn)很好的修補(bǔ)，彌補(bǔ)了緊支撐徑向基函數(shù)的主要缺點(diǎn)。同年，MORSE等人利用高斯函數(shù)來作為緊支撐徑向基函數(shù)，獲得稀疏插值矩陣。2003年，OHTAKE通過對點(diǎn)云分層建立八叉樹，每層構(gòu)造緊支撐徑向基函數(shù)來實(shí)現(xiàn)對散亂點(diǎn)的插值/逼近。這種由粗至精的方法能夠很好恢復(fù)大片的殘缺點(diǎn)云數(shù)據(jù)，而且對點(diǎn)云的疏密不敏感。同年，在單位分解法思想的基礎(chǔ)上，OHTAKE提出了MPU方法MULTILEVELPARTITION。RUNITY，為了獲取曲面局部的細(xì)節(jié)特征，使用系數(shù)不同的分段二次多項(xiàng)式函數(shù)來逼近局部點(diǎn)云，同時權(quán)函數(shù)混合這些多項(xiàng)式函數(shù)。對于局部形狀的復(fù)雜程度不同，八叉樹相應(yīng)進(jìn)行不同程度的細(xì)分來充分表示物體表面特征，比如表面細(xì)節(jié)、邊和角等尖銳特征。規(guī)則的隱式曲面一般用多邊形化法來繪制，可以滿足任意精度的要求。存在的問題是曲面上一些曲率較大的部分要用許多多邊形才能精確表達(dá)出來，繪制效率很低；還有對于一些隱式曲面，比如自相交（SELFINTERSECTING）隱式曲面是很難用多邊形化法繪制出來。（A）原始點(diǎn)云（B）MARCHINGCUBES輸出（C）重建效果圖13隱士曲面擬合的重建效果13課題來源與研究意義131課題來源對企業(yè)進(jìn)行了深入的調(diào)研和需求分析，陜汽集團(tuán)、西飛集團(tuán)、四川德陽二重、河南奔馬集團(tuán)、天津汽車模具有限公司、美國CAOGROUPE,INC都對得到工件完整的實(shí)體數(shù)字模型有著極大的需求。本課題研究成果將應(yīng)用于天津汽車模具有限公司泡沫實(shí)型的檢測、模具的表面檢測和制件的檢測以及美國CAOGROUPE,INC牙模點(diǎn)云采集及點(diǎn)云預(yù)處理。本課題得到國家863項(xiàng)目“大型復(fù)雜曲面產(chǎn)品的反求和三維快速檢測系統(tǒng)研究”和江蘇省科技支撐計劃（工業(yè)部分）的支持。研究成果將應(yīng)用于天津汽車模具有限公司泡沫實(shí)型的檢測、模具的表面檢測和制件的檢測。132研究意義點(diǎn)云網(wǎng)格重建如圖14所示，其過程在于尋找某種數(shù)學(xué)描述形式，構(gòu)造一個帶有頂點(diǎn)和相互連接拓?fù)潢P(guān)系的三角形網(wǎng)格模型，并以此為依據(jù)對網(wǎng)格本身進(jìn)行分析、優(yōu)化改和繪制。復(fù)雜物體掃描獲取的點(diǎn)云數(shù)目己經(jīng)超過幾百萬個，甚至上億，給曲面重建技術(shù)帶來新戰(zhàn)和困難L由于這些技術(shù)產(chǎn)生大量的體數(shù)據(jù)，需要有效地被存儲和處理2不精確的照相機(jī)定位，圖像扭曲和配準(zhǔn)誤差使得點(diǎn)云產(chǎn)生大量噪音和離群點(diǎn)加大了曲面重建的難度，同時導(dǎo)致細(xì)節(jié)特征丟失。3掃描光照的不完善、材料表面的低反射率和遮擋導(dǎo)致物體表面的數(shù)據(jù)丟失，從而在點(diǎn)云中產(chǎn)生空洞，導(dǎo)致原始表面特征恢復(fù)難度加大。針對這些問題，許多研究者提出了多種解決方案，但是對超大規(guī)模而且?guī)в写罅吭胍舻狞c(diǎn)云，推測物體表面幾何結(jié)構(gòu)形式，并非易事。圖14散亂點(diǎn)云三角化模型從近幾年來的點(diǎn)云網(wǎng)格重建方法中可以看出，快速魯棒地對點(diǎn)云進(jìn)行曲面重建仍然是廣大研究者不斷努力的目標(biāo)，除了基于點(diǎn)的造型、CAD中的NURBS曲面外，散亂點(diǎn)云曲面重建幾乎都集中網(wǎng)格重建。散亂數(shù)據(jù)的曲面重建一直以來只是函數(shù)逼近論的一個重要研究內(nèi)容，但是隨著激光測距掃描等三維數(shù)據(jù)采樣技術(shù)和硬件設(shè)備的日益完善。以往難以滿足取樣密度的散亂數(shù)據(jù)點(diǎn)集的障礙現(xiàn)在不再是曲面重建的瓶頸。散亂數(shù)據(jù)的曲面重建作為一種能代表將來發(fā)展趨勢的新造型技術(shù)得到了廣泛的研究，特別自從九十年代以來，HOPPE等人對基于散亂數(shù)據(jù)點(diǎn)集的任意拓?fù)渲亟ㄋ惴ㄟM(jìn)行了開創(chuàng)性的研究，散亂數(shù)據(jù)點(diǎn)的曲面重建越來越成為圖形學(xué)界的研究熱點(diǎn)之一。該技術(shù)具有廣泛的應(yīng)用前景，它的發(fā)展將會在科學(xué)研究和工程上很多的應(yīng)用領(lǐng)域，其中包括三維掃描、邊緣數(shù)據(jù)的曲面重建、藝術(shù)品及考古文物復(fù)制、游戲影視制作等發(fā)揮極大的作用。對散亂數(shù)據(jù)點(diǎn)集的曲面重建研究將會有力地促進(jìn)造型和可視化等技術(shù)的高速發(fā)展。因此對散亂數(shù)據(jù)的曲面重建研究具有重要的理論和現(xiàn)實(shí)意義。14研究內(nèi)容與技術(shù)路線141研究內(nèi)容本文針對無拓?fù)浣Y(jié)構(gòu)的三維散亂點(diǎn)云，主要的研究工作有1提出針對研究所自主研發(fā)的XJTUOM三維光學(xué)面掃描系統(tǒng)點(diǎn)云三角網(wǎng)格重建方案。2點(diǎn)云三角化算法的研究與實(shí)現(xiàn)，針對無拓?fù)浣Y(jié)構(gòu)的散亂點(diǎn)云，根據(jù)鄰域信息構(gòu)建隱函數(shù)，采用MARCHINGCUBE算法輸出三角面片。3為了保證存儲的速度，對三角化后的點(diǎn)云進(jìn)行光順處理。4為了保證模型得匹配精度，對三角化后的點(diǎn)云進(jìn)行光順處理。5對點(diǎn)云三角化、網(wǎng)格簡化和網(wǎng)格光順等模塊分別進(jìn)行實(shí)驗(yàn)和分析。并將其應(yīng)用于XJTUOM三維光學(xué)面掃描系統(tǒng)中，對其點(diǎn)云處理效果進(jìn)行驗(yàn)證和分析。142技術(shù)路線本文首先簡要介紹了XJTUOM三維光學(xué)面掃描系統(tǒng)的基本原理、組成、應(yīng)用領(lǐng)域，指明了點(diǎn)云網(wǎng)格重建在逆向工程和產(chǎn)品檢測所處的環(huán)節(jié)。在針對天汽模模具檢測、北京CAOGROUPE，INC公司點(diǎn)云采集和國家863課題“大型復(fù)雜曲面產(chǎn)品的反求和三維快速檢測系統(tǒng)研究”進(jìn)行了需求分析后提出了可行的開發(fā)方案，接著按照點(diǎn)云網(wǎng)格重建三個關(guān)鍵技術(shù)模塊三維散亂點(diǎn)云三角化、網(wǎng)格簡化和網(wǎng)格光順。點(diǎn)云三角網(wǎng)格劃分模塊主要是對隱士曲面擬合得算法上得改進(jìn)，采用基于步進(jìn)立方體的算法生成三角網(wǎng)格。網(wǎng)格簡化主要通過局部簡化算法中的邊折疊算法來實(shí)現(xiàn)；網(wǎng)格平滑通過基于法矢的網(wǎng)格調(diào)整。然后采用MICROSOFTVISUALC60軟件和OPENGL開放式圖形庫為開發(fā)工具，運(yùn)用面向?qū)ο蟪绦蛟O(shè)計OBJECTORIENTEDPROGRAMMING，OOP思想，完成了點(diǎn)云網(wǎng)格重建系統(tǒng)設(shè)計。最后，對實(shí)現(xiàn)的點(diǎn)云網(wǎng)格重建處理數(shù)據(jù)量的能力、處理速度、處理效果方面對點(diǎn)云網(wǎng)格重建方案進(jìn)行試驗(yàn)和分析，并將其應(yīng)用到實(shí)際，最后根據(jù)試驗(yàn)和應(yīng)用結(jié)果得出點(diǎn)云三角網(wǎng)格重建系統(tǒng)的結(jié)論，并在此基礎(chǔ)上對進(jìn)一步的發(fā)展完善方面提出展望。從總體上講，點(diǎn)云網(wǎng)格重建所采用的技術(shù)路線如圖15所示。圖15本文技術(shù)路線15本文結(jié)構(gòu)安排第二章先簡要介紹XJTUOM三維光學(xué)面掃描系統(tǒng)的原理和組成，針對點(diǎn)云數(shù)據(jù)特點(diǎn)和研究所在企業(yè)橫向課題以及國家863項(xiàng)目中遇見的問題提出了三維點(diǎn)云網(wǎng)格重建方案。第三章介紹散亂點(diǎn)云三角網(wǎng)格劃分和步進(jìn)立方體（MARCHINGCUBES）算法原理，對HOPPE等人提出的三維重建算法上進(jìn)行改進(jìn)，提出并實(shí)現(xiàn)了基于空間立方體分割的曲面擬合三角化方法。建立了三角化數(shù)據(jù)結(jié)構(gòu)，提出了對海量數(shù)據(jù)進(jìn)行空間劃分的算法，并對其進(jìn)行實(shí)驗(yàn)分析。第四章闡述了網(wǎng)格的簡化和光順方法，實(shí)現(xiàn)了基于法向量的雙邊濾波網(wǎng)格光順?biāo)惴ê突谇实倪呎郫B簡化算法。第五章對點(diǎn)云網(wǎng)格重建進(jìn)行了實(shí)驗(yàn)和分析，包括對點(diǎn)云三角化、網(wǎng)格簡化和網(wǎng)格光順三個模塊分別進(jìn)行精度和速度的分析，并介紹了三維點(diǎn)云處理系統(tǒng)的應(yīng)用實(shí)例。第六章在總結(jié)全文和創(chuàng)新點(diǎn)的基礎(chǔ)上，指出了本文算法的進(jìn)一步研究內(nèi)容，明確今后的研究方向。EQUATIONCHAPTER2SECTION12散亂點(diǎn)云三角網(wǎng)格重建方案21引言曲面重建是指從去曲面上的部分采樣信息恢復(fù)原始曲面的幾何模型。隨著三位掃描設(shè)備精度的提高，獲得的點(diǎn)云數(shù)據(jù)越來越龐大。點(diǎn)云的曲面重建方案必須滿足海量點(diǎn)云數(shù)據(jù)快速、準(zhǔn)確和高效的需求。本章首先簡要介紹了XJTUOM三維光學(xué)面掃描系統(tǒng)，進(jìn)而闡述了針對XJTUOM三維光學(xué)面掃描系統(tǒng)的散亂點(diǎn)云曲面重建方案，針對三角化后的網(wǎng)格進(jìn)行簡化和光順技術(shù)的研究，實(shí)現(xiàn)網(wǎng)格的優(yōu)化目標(biāo)。22XJTUOM系統(tǒng)及網(wǎng)格重建環(huán)節(jié)221XJTUOM三維光學(xué)掃描系統(tǒng)介紹1）系統(tǒng)原理三維光學(xué)測量系統(tǒng)采用結(jié)構(gòu)光非接觸式照相測量原理，如圖21XJTUOM三維掃面系統(tǒng)原理所示，它結(jié)合結(jié)構(gòu)光、相位測量、計算機(jī)視覺等技術(shù)于一體，通過光柵投影裝置投影數(shù)幅特定編碼的結(jié)構(gòu)光到待測物體上，并由成一定夾角的兩個攝像頭同步采集相應(yīng)圖像，然后對圖像進(jìn)行解碼和相位計算，并利用匹配技術(shù)和三角形測量原理，計算出兩個攝像機(jī)公共視區(qū)內(nèi)像素點(diǎn)的三維坐標(biāo)，從而實(shí)現(xiàn)物體的三維信息數(shù)字化和測量。所謂照相測量，就是類似于照相機(jī)對視野內(nèi)的物體進(jìn)行照相，不同的是照相機(jī)攝取的是物體的二維圖像，而三維光學(xué)測量系統(tǒng)獲得的是物體的三維信息。圖21XJTUOM三維掃面系統(tǒng)原理2）硬件組成XJTUOM三維光學(xué)面掃描系統(tǒng)分為硬件和軟件兩部分。其掃描頭部分如圖22所示，硬件部分主要包括鏡頭、投影儀、兩個工業(yè)相機(jī)、橫梁、云臺、三腳架、高性能計算機(jī)等，軟件部分實(shí)現(xiàn)的主要功能有圖像采集、圖像預(yù)處理、相機(jī)標(biāo)定、立體匹配和三維重建。圖22XJTUOM系統(tǒng)硬件組成面掃描系統(tǒng)采用結(jié)構(gòu)光非接觸式照相測量原理，通過光柵投影裝置投影數(shù)幅特定編碼的結(jié)構(gòu)光到待測物體上，由成一定夾角的兩個攝像頭同步采集相應(yīng)圖像，然后對圖像進(jìn)行解碼和相位計算，并利用外差式多頻相移三維光學(xué)測量技術(shù)，利用空間頻接近的多個投影條紋莫爾特性的解相方法，計算出兩個攝像機(jī)公共視區(qū)內(nèi)像素點(diǎn)的三維坐標(biāo)，從而實(shí)現(xiàn)物體的三維信息數(shù)字化和測量。3）應(yīng)用領(lǐng)域XJTUOM三維光學(xué)面掃描系統(tǒng)主要應(yīng)用領(lǐng)域1逆向設(shè)計快速獲取零件的曲面點(diǎn)云數(shù)據(jù)，建立三維數(shù)模，達(dá)到快速設(shè)計產(chǎn)品的目的。2產(chǎn)品檢測生產(chǎn)線產(chǎn)品質(zhì)量控制和形位尺寸檢測、特別適合復(fù)雜曲面的檢測，可以檢測鑄件、鍛件、沖壓件、模具、注塑件、木制品等產(chǎn)品。3其它應(yīng)用文物掃描和三維顯示、牙齒及畸形矯正、整容等。222點(diǎn)云三角網(wǎng)格重建所處的環(huán)節(jié)面掃描系統(tǒng)可以在短時間內(nèi)掃描到大量的點(diǎn)云數(shù)據(jù)，由于所獲得的點(diǎn)云只包含有點(diǎn)的三維坐標(biāo)信息，沒有明確的拓?fù)浣Y(jié)構(gòu)，為了應(yīng)用到逆向設(shè)計和產(chǎn)品的質(zhì)量檢測中，需要對獲得的散亂點(diǎn)云進(jìn)行三角網(wǎng)格建模及三角化處理。建模后的點(diǎn)云包含大量的三角網(wǎng)格信息，而且由于設(shè)備本身的因素，也不可避免得含有很多噪聲信息，為了得到更精確得曲面模型，減少硬件存儲空間，有必要對三角化后的點(diǎn)云模型進(jìn)行光順和簡化處理，得到更加優(yōu)化的網(wǎng)格模型。將XJTUOM系統(tǒng)采集得到的點(diǎn)云應(yīng)用于實(shí)際中，要對其進(jìn)行點(diǎn)云的網(wǎng)格重建。本文所提到的針對XJTUOM系統(tǒng)的點(diǎn)云處理技術(shù)在其整個測量流程中所處環(huán)節(jié)如圖23所示。產(chǎn)品模型三維掃描獲得點(diǎn)云數(shù)據(jù)點(diǎn)云三角化網(wǎng)格簡化網(wǎng)格光順逆向設(shè)計產(chǎn)品檢測其它應(yīng)用點(diǎn)云網(wǎng)格重建圖23點(diǎn)云網(wǎng)格重建在測量流程中所處環(huán)節(jié)23點(diǎn)云網(wǎng)格重建關(guān)鍵技術(shù)分析231點(diǎn)云三角化對于點(diǎn)云數(shù)據(jù)而言，由于數(shù)據(jù)本身除了點(diǎn)的空間坐標(biāo)之外不包含其它附加信息，因此對其進(jìn)行網(wǎng)格化的過程實(shí)際就是進(jìn)行三角剖分的過程，即對所給點(diǎn)集，用互不相交的三角形來近似表示點(diǎn)集形成的曲面，三角形的集1,2,PPN合即為該曲面的三角剖分。本文采用基于曲面擬合的方法實(shí)現(xiàn)網(wǎng)格重建。給定一組分布于曲面上的點(diǎn)云，隱式曲面擬合技術(shù)的主要思想就是建立一個函數(shù)，的零3IXXRYFXF水平集逼近或者插值點(diǎn)云,描述了某個物體的半空間，則描述物體X0FX0的邊界。在判斷一個點(diǎn)在曲面上哪一側(cè)，及進(jìn)行曲面求交時，隱式化表示給這些操作帶來了極大的方便。隱式曲面允許一個復(fù)雜的形狀通過一個單一的公式處理，它統(tǒng)一了曲面和體模型。在這樣的隱式模型中，許多復(fù)雜的曲面編輯操作變得較為容易。在隱式曲面構(gòu)造中，使用最多的是徑向基函數(shù)RADIALBASISFUNCTIONS，RBF，它是幾何數(shù)據(jù)分析、模式識別、神經(jīng)網(wǎng)絡(luò)的標(biāo)準(zhǔn)工具，在各種數(shù)學(xué)文獻(xiàn)中得到了廣泛的研究，此外二次多項(xiàng)式隱函數(shù)也有較多的應(yīng)用。KFX1X2MXM12輸入層輸出層隱層圖24基向徑函數(shù)示意圖如果要插值或者逼近給定的一組散亂點(diǎn)云，徑向基函數(shù)，定義為X3FR1NIIFXPXMERGEFORMAT21式中是低維的多項(xiàng)式，是基函數(shù)，區(qū)間分布為，這里的通常被看做0,IX徑向基函數(shù)的中心，公示表明，徑向基函數(shù)由基函數(shù)的線性組合及線性多項(xiàng)式F組成，基函數(shù)通常有多種選擇，比如THINPLANE線條，高斯函數(shù)，P2EPCR或等。R3R在構(gòu)建某個點(diǎn)的函數(shù)時，需要用到該點(diǎn)的鄰域點(diǎn)，也就是在空間中距離該頂點(diǎn)歐式距離最近的點(diǎn)。目前常用的空間搜索算法主要有八叉樹、空間單元格ERRORREFERENCESOURCENOTFOUND和KDTREE法。其中KDTREE是由BENTLEY于1975年提出來并發(fā)展成為一種多維空間樹狀搜索索引結(jié)構(gòu)，它特別適合空間點(diǎn)的搜索，具有快速查找鄰近的特性，其典型應(yīng)用是求點(diǎn)的K個最近點(diǎn)，本文就是采用這種結(jié)構(gòu)來組織三維數(shù)據(jù)點(diǎn)的。圖25KDTREE法劃分二維平面及離散點(diǎn)的二叉樹存儲對于一個包含離散點(diǎn)的二維空間來說，如圖25，KDTREE的生成過程就是平面被X軸和Y軸連續(xù)遞歸劃分的過程，平面的劃分深度就是KDTREE的深度，若用D表示，則KDTREE上節(jié)點(diǎn)的總數(shù)為2D或2D1。假設(shè)水平方向?yàn)閄軸，豎直方向?yàn)閅軸，則具體的劃分過程如下首先按X軸尋找分割線，即計算所有點(diǎn)X值的平均值，以此平均值將平面分成兩部分；然后在分成的子平面中按Y值劃分，分割好的子平面再按X值分割，依此類推，直到最后分割的區(qū)域內(nèi)只有一個點(diǎn)。這樣的分割過程就對應(yīng)了一個二叉樹，二叉樹的分支節(jié)點(diǎn)對應(yīng)一條分割線，而每個葉子節(jié)點(diǎn)就對應(yīng)一個數(shù)據(jù)點(diǎn)。由上面的介紹，可以得出KDTREE的三個特點(diǎn)第一，每個節(jié)點(diǎn)代表一個矩形區(qū)域；第二，每個節(jié)點(diǎn)對應(yīng)一個坐標(biāo)軸上的劃分，它的子節(jié)點(diǎn)就對應(yīng)著這個劃分；第三，節(jié)點(diǎn)所對應(yīng)的分割線與深度對應(yīng)。此外，KDTREE還具有點(diǎn)分布均勻的特點(diǎn)，所以搜索的效率比較高。232網(wǎng)格簡化通常,3D模型需要上百萬的三角面片對其進(jìn)行渲染,這使得計算機(jī)硬件處理能力已不能滿足現(xiàn)在3D計算的要求。在協(xié)同設(shè)計領(lǐng)域,復(fù)雜的模型影響了計算機(jī)硬件的處理能力。因此,可以在保持模型幾何外觀和允許誤差范圍內(nèi),采用適當(dāng)?shù)暮喕僮?減少原始模型的幾何特征包括面片數(shù)、邊數(shù)和頂點(diǎn)數(shù),達(dá)到需要的簡化速度和質(zhì)量。分析歸納現(xiàn)有的多邊形網(wǎng)格簡化算法的基礎(chǔ)上,以3D圖形圖像處理的實(shí)際需要為依據(jù),可以將簡化算法分為局部簡化算法和全局簡化算法。局部簡化算法是指簡化過程中僅考慮物體的某個局部區(qū)域的特征,應(yīng)用一組局部規(guī)則對其進(jìn)行簡化。包括了頂點(diǎn)刪除，邊折疊以及面折疊等方法。頂點(diǎn)刪除VERTEXDECIMATION的思想很簡單在單個頂點(diǎn)上進(jìn)行操作,首先根據(jù)這個點(diǎn)到平面距離的閥值來判斷它是否與周圍的三角面片共面,如果共面,且刪除這個頂點(diǎn)后不會改變局部的拓?fù)浣Y(jié)構(gòu),那么算法將刪除這個頂點(diǎn)。同時,所有與該頂點(diǎn)相鄰的面均被刪除,然后通過局部三角化填補(bǔ)所產(chǎn)生的孔洞,操作反復(fù)進(jìn)行,直到網(wǎng)格達(dá)到用戶的簡化要求為止。SCHROEDER等在1992年首先提出了頂點(diǎn)刪除算法。該算法簡化效率較高,簡化質(zhì)量好,并且實(shí)現(xiàn)和應(yīng)用簡單,可應(yīng)用于大規(guī)模網(wǎng)格模型上。但只適用于流形模型,不能簡化輸入模型上非流形的頂點(diǎn)面折疊操作是將三角面的三個頂點(diǎn)聚合到一個頂點(diǎn),原始三角化面退化成一個點(diǎn)和相鄰面退化成線段。最終,一次面折疊操作將會從模型中刪除四個三角面片。邊折疊的思想為首先采用一組選擇準(zhǔn)則,選擇一對合適的頂點(diǎn)對即一條邊,然后將這條邊折疊成一個頂點(diǎn),其次更新所有與這這條邊相連的邊。在一個沒有邊界的流形網(wǎng)格上,每一個邊折疊操作會剛好折疊兩個面。頂點(diǎn)刪除面刪除頂點(diǎn)聚類圖26常用簡化操作一個好的網(wǎng)格簡化算法應(yīng)該在減少網(wǎng)格三角面和頂點(diǎn)數(shù)目的同時盡量保持原始模型的拓?fù)浣Y(jié)構(gòu)、邊界和尖銳棱邊之類的形狀特征。以往的簡化算法大多采用幾何距離度量作為簡化準(zhǔn)則的。如GARLNAD提出的二次誤差矩陣，實(shí)際也是計算新點(diǎn)到鄰近面的距離平方和，GUEZIE提出的體積變動最小原則也是一個類似距離的度量。用幾何距離度量作為簡化準(zhǔn)則能較好地控制簡化后的網(wǎng)格與原始網(wǎng)之間的空間距離誤差，但它很難保持網(wǎng)格的形狀細(xì)節(jié)。例如網(wǎng)格有些地方曲率變化較大，但因?yàn)轫旤c(diǎn)與其鄰點(diǎn)的距離較近，用幾何距離來度量的話將被簡化。SUNJOCNG考慮了網(wǎng)格的離散曲率，提出了以網(wǎng)格曲率變動最小作為一個簡化時的折疊順序準(zhǔn)則。但同樣的，如果處理的網(wǎng)格折疊的邊長較大時，可能局部的曲率變動較小，但在空間距離誤差上會有較大的變動。233網(wǎng)格光順由于各種因素的影響,由測量數(shù)據(jù)直接得到的三角網(wǎng)格模型往往存在大量的噪聲。為滿足后續(xù)處理的要求,需對這種三角網(wǎng)格模型進(jìn)行光順處目前,用于三角網(wǎng)格模型光順的主流算法有兩類，能量法和拉普拉斯光順法。能量法是用全部頂點(diǎn)作參數(shù)對原始網(wǎng)格模型定義一個全局能量函數(shù),通過求解這個函數(shù)的約束最小解來調(diào)整網(wǎng)格頂點(diǎn)。能量法不僅計算量大,且難以對局部形狀進(jìn)行控制。拉普拉斯光順法是通過對每個頂點(diǎn)定義一個拉普拉斯算子來確定調(diào)整方向,然后沿此方向以一定的速度移動頂點(diǎn)達(dá)到調(diào)整網(wǎng)格的目的。該方法能有效調(diào)整網(wǎng)格至規(guī)則形狀,網(wǎng)格密度與形狀都趨于均勻。為了構(gòu)造一種整體光順效果好,且變形小,模型原有特征得到充分保留的三角網(wǎng)格模型光順方法，首先需判斷出模型中的特征區(qū)域與非特征區(qū)域,然后分別采用KUWAHARA濾波算子與拉普拉斯算子進(jìn)行法矢調(diào)整。在三角片法矢調(diào)整后,再調(diào)整頂點(diǎn)位置,即可完成模型光順過程。頂點(diǎn)的位置調(diào)整可以分解為法向和切向兩個正交分量來進(jìn)行。沿著網(wǎng)格頂點(diǎn)的法向以平均曲率速度調(diào)節(jié)頂點(diǎn)的位置，能夠明顯地改善頂點(diǎn)的局部區(qū)域的幾何變形，如果在切平面上移動頂點(diǎn)，則不能達(dá)到去噪的效果。實(shí)際上，在曲面論中，極小曲面的充要條件是平均曲率處處為零，通過在法向方向以平均曲率的速度移動可以達(dá)到光順的目的，采用了頂點(diǎn)估計公式其中為平均曲率。HK1COTT24IHIJJJIJAMVKNXMERGEFORMAT22IXJXIJEIXJX1J1JXJJ圖27平均曲率流算法圖示如圖27所示，為三角形的兩個頂點(diǎn)，是在相鄰IJIJJIEXJJIJE兩個三角形中的對角，當(dāng)?shù)闹荡笥诘臅r候?qū)?dǎo)致為負(fù)值，JJCOTTJJ因此有時候模型的部分區(qū)域會在光順中出現(xiàn)畸變。為了解決這個問題，在曲率大的地方可以適當(dāng)降低光順?biāo)俣?，而在曲率小的地方可以適當(dāng)加大光順?biāo)俣?。平均曲率流的方法能解決頂點(diǎn)漂移，但是該算法對曲率的依賴程度很大，光順的效果與三維模型的曲率估計精確關(guān)系很大。24點(diǎn)云網(wǎng)格重建系統(tǒng)方案設(shè)計241點(diǎn)云網(wǎng)格重建系統(tǒng)設(shè)計原則該系統(tǒng)面向?qū)ο鬄槠髽I(yè)橫向課題和國家863項(xiàng)目部分，具有較強(qiáng)的實(shí)際應(yīng)用需求，在系統(tǒng)設(shè)計時應(yīng)遵循以下原則1具備處理大數(shù)據(jù)量的能力一般情況下，單次掃描獲取得到的點(diǎn)云有上千萬個點(diǎn)，軟件系統(tǒng)需要能同時處理大數(shù)據(jù)量的點(diǎn)云，實(shí)現(xiàn)海量點(diǎn)云的網(wǎng)格重建。2具有快速的處理速度無論在于逆向設(shè)計還是產(chǎn)品的檢測，都要滿足系統(tǒng)的實(shí)時性。3高精度的處理結(jié)果三角化后的曲面保持原始曲面得幾何特征。4較好的系統(tǒng)穩(wěn)定性。242針對三維光學(xué)測量的點(diǎn)云三角化方案根據(jù)上面對系統(tǒng)的分析，本文制定了點(diǎn)云處理系統(tǒng)方案，如圖28所示，首先加載XJTUOM系統(tǒng)采集得到的點(diǎn)云，然后計算每個點(diǎn)的法向量，再搜索點(diǎn)的鄰域，計算點(diǎn)的場函數(shù)，根據(jù)步進(jìn)立方體算法輸出三角網(wǎng)格。對得到的初始網(wǎng)格進(jìn)行簡化和光順處理，進(jìn)一步節(jié)省存儲空間，保持曲面的幾何特征。加載點(diǎn)云數(shù)據(jù)計算鄰域和切平面計算場函數(shù)MC算法輸出三角面片計算離散曲率網(wǎng)格簡化網(wǎng)格光順結(jié)束點(diǎn)云三角化圖28點(diǎn)云網(wǎng)格重建方案243點(diǎn)云三角化目標(biāo)的制定1首先能快速的初始化點(diǎn)云包括去除孤立點(diǎn)、計算法向量、計算點(diǎn)云權(quán)值等。2快速的判斷多幅點(diǎn)云的重疊區(qū)域。3融合重疊區(qū)域。4最終獲得高質(zhì)量的能夠用于檢測和逆向建模設(shè)計的點(diǎn)云模型。25本章小結(jié)本章主要介紹了XJTUOM三維光學(xué)面掃描系統(tǒng)的組成和應(yīng)用領(lǐng)域，對本文所設(shè)計到的點(diǎn)云三角化的方案進(jìn)行了分析和設(shè)計，對點(diǎn)云點(diǎn)云網(wǎng)格重建的關(guān)鍵技術(shù)進(jìn)行研究，并根據(jù)點(diǎn)云曲面重建系統(tǒng)的設(shè)計原則提出了針對XJTUOM三維光學(xué)面掃描系統(tǒng)點(diǎn)云三角化方案。EQUATIONCHAPTERNEXTSECTION13點(diǎn)云三角網(wǎng)格劃分31引言本文是針對密集點(diǎn)云的三角化，應(yīng)用在后續(xù)的逆向設(shè)計和產(chǎn)品檢測中，要求重建后的曲面嚴(yán)格的逼近原始模型，而且點(diǎn)云數(shù)據(jù)量龐大，點(diǎn)云的拓?fù)浣Y(jié)構(gòu)不明確。需要在保證精度的前提下，盡可能的提高處理速度。為此本文在HOPPE等人提出的三維重建算法上進(jìn)行改進(jìn)，提出了對海量數(shù)據(jù)進(jìn)行空間劃分的算法，首先取每一個采樣點(diǎn)的K個鄰域點(diǎn),，計算點(diǎn)的近似切平面,求出切平面的法向量，確定了切平面后,構(gòu)建空間點(diǎn)到切平面的距離函數(shù)進(jìn)行插值，通過步進(jìn)立方體的算法生成網(wǎng)格進(jìn)而生成曲面。32MARCHINGCUBES算法原理321基本定義基于分割的MC（MARCHINGCUBES）算法以圖像分割作為三維重構(gòu)的基礎(chǔ),分割的目的是將三維圖像序列二值化。三維重構(gòu)用圖像分割的結(jié)果作為輸入,進(jìn)行等值面的提取。圖像分割的結(jié)果組成三維規(guī)則數(shù)據(jù)場,作為MC算法的輸入。三維規(guī)則數(shù)據(jù)場可以用下式表示,1,1,IJKIJKXYZFXYZINJKNMERGEFORMAT31式中定義為，定義為X軸，Y軸，Z軸各方向上的,IJK,IJKFXYZ數(shù)據(jù)點(diǎn)，給出以下定義定義1已知區(qū)域內(nèi)的場函數(shù),則等值面可由隱函數(shù)來定義RS,|,RSXYZZC為常數(shù)定義2稱為等值點(diǎn),為正點(diǎn),為負(fù)點(diǎn)。CPF（）|PF（）C|PF（）是面檢測參數(shù)。定義3MC算法中的體元可以如圖31所示體元實(shí)際上是體數(shù)據(jù)中包含相鄰八個采樣點(diǎn)的最小立方體,其八個數(shù)據(jù)點(diǎn)位于該體元的八個角點(diǎn)上。圖31體元示意圖322基本原理與步驟MC算法以數(shù)據(jù)場中的相鄰兩層上的各四個像素為頂點(diǎn)組成的立方體為最小的等值面搜索單元也稱為體元。其基本思想是逐個處理數(shù)據(jù)場的體元，分類出與等值面相交的體元，采用線性插值計算出與等值面相交的體元的棱邊上的交點(diǎn)，根據(jù)體元8個頂點(diǎn)與等值面的相對位置，將這些交點(diǎn)按一定方式連接成三角面，作為等值面在體元內(nèi)的逼近表示，所有體元中的等值面構(gòu)成整個數(shù)據(jù)場的等值面。等值面中各三角片頂點(diǎn)處的法向量的計算，一般先采用中心差分計算出體元頂點(diǎn)處的梯度，再用線性插值計算等值點(diǎn)處的梯度值作為該點(diǎn)的法向量。計算等值點(diǎn)的過程比較簡單，首先對體元的8個頂點(diǎn)進(jìn)行分類，以判定該頂點(diǎn)是位于等值面內(nèi)還是等值面外。再根據(jù)8個頂點(diǎn)的狀態(tài)，確定等值面在體元內(nèi)部的連接方式。假定等值面的值為C。則頂點(diǎn)分類規(guī)則為（1）如果體元頂點(diǎn)的數(shù)據(jù)場值C0，則定義該頂點(diǎn)位于等值面之外，標(biāo)記為1；（2）如果體元頂點(diǎn)的數(shù)據(jù)場值C0，則定義該頂點(diǎn)位于等值面之內(nèi)，標(biāo)記為0；（3）對于一個體元而言,如果它所有頂點(diǎn)的索引值都為1,則表示該體元位于表面內(nèi)如果所有頂點(diǎn)的索引值都為0,則表示該體元位于表面外除此之外的索引值的其它情況,則表示該表面穿過此體元。（4）在此基礎(chǔ)上定義體元中表面的拓?fù)浣Y(jié)構(gòu),以后根據(jù)具體的數(shù)據(jù)確定切點(diǎn)的位置由于每個體元有八個角點(diǎn),每個角點(diǎn)可能有0,1兩種狀態(tài),因此每個體元與等值面相交的情況有256種狀態(tài)。這些狀態(tài)具有對稱性,即互補(bǔ)對稱性和旋轉(zhuǎn)對稱性1互補(bǔ)對稱性將一個體元的八個角點(diǎn)的狀態(tài)都加以改變，1變?yōu)?，0變?yōu)?,得到的體元與等值面的相交狀態(tài)與原體元狀態(tài)一致。經(jīng)過這種對稱性變換,體元的狀態(tài)可以簡化為128種。2旋轉(zhuǎn)對稱性如果某一體元經(jīng)過旋轉(zhuǎn)變換后與另一狀態(tài)的體元一致,即頂點(diǎn)位置和及其狀態(tài)值相同,那么這兩種狀態(tài)可以合并為一種狀態(tài)。根據(jù)旋轉(zhuǎn)對稱性,體元的最后以減少到減少15種。圖3215種體元相交狀態(tài)323三角形頂點(diǎn)位置和法向計算對于每一種相交模式,可以基于各頂點(diǎn)的狀態(tài)建立它的索引,索引設(shè)8位,每一位代表一個頂點(diǎn)的狀態(tài),如所示此索引值作為查詢情況表的指