基于点表示几何体的造型技术

硕士学位论文论文题目基于点表示几何体的造型技术作者姓名杨振羽指导教师彭群生教授郑文庭副研究员学科专业应用数学所在学院理学院提交日期二四年三月浙江大学硕士学位论文GEOMETRYADIHEGRADUATESCHOOLOFZHEJIANGUNIVERSITYFORTHEDEGREEOFZHENYUYANGDEPARTMENTOFAPPLIEDMATHEMATICS,ZHYPROFISORASSOCIATEPROSUPERVISORSHAPEMODELINGOFPOINTSAMPLEDSSERTATIONSUBMITTEDTOTMASTEROFPHILOSOPHYPRESENTEDBYEJIANGUNIVERSITACCEPTEDONTHERECOMMENDATIONOFQUNSHSUPERVENGPENG,OFWENTINGZHENG,CMARCH,20042浙江大学硕士学位论文摘要近年来，以点作为造型与绘制的基本元素的方法，在计算机图形学领域内受到研究者越来越多的关注。本文回顾了基于点元表示的图形学的发展历史，并提出了两个在点造型方面的新算法。针对一般点云模型，本文提出了一个新的交互式布尔运算算法。在实施布尔运算时，利用自适应三色八叉树结构来加速内外测试。对于局部采样密度不一致的相交区域或曲率太大容易导致较大求交误差的地方，实行了自适应细分加密采样。最后重采样相交的部分获得精确的结果。此算法适用于一般的实测点云数据，包括含有少量噪声的点模型、非均匀采样的点模型以及不同分辨率的点模型之间的布尔运算。此外本文还从统计的观点出发，提出了一个基于邻域重心约束的光顺算法，通过极小化邻域重心约束的局部邻域目标函数达到局部光顺的目的。此方法有效地克服了拉普拉斯算子所造成的过度收缩与聚集现象。实验表明此方法不仅计算稳定、速度快，而且简便易用。最后，上述方法都被集成到一个基于点表示的交互造型系统中。关键词基于点的造型，布尔运算，光顺。3浙江大学硕士学位论文ABSTRACTRECETLY,MODELINGANDRENDERINGUSINGPOINTSASBASICANDEFFICIENTPRIMITIVES,HAVEBEENPAIDMUCRINTERACTIVEBOOLEANOPERATIONSBETWEENGENERALPOINSECONDLY,ACENTROIDCONSTRAINEDFAIRINGALGORITHMISPRESENTEDFORPOINTSAMPLEDGEOMETRYBYOPTIMIZINGALOCALFUNCTIONBASEDONTHECENTROIDCONSTRAINTSOFNEIGHBORHOOD,LOCALSMOOTHINGISACHIEVEDTHISMETHODOVERCOMESTHEPROBLEMSOFEXTREMESHRINKAGEANDEXTREMECONVERGENCEARISENFROMLAPLACIANSMOOTHINGOPERATOROUREXPERIMENTSVERIFYTHATITISSTABLE,FASTANDEMODELINGISIMPLEMENTEDINTEGRATINGOUREWALGORITHMSEYWORDSPOINTBASEDMODELING,BOOLEANOPERATION,FAIRINGNHATTENTIONINCOMPUTERGRAPHICSCOMMUNITYTHISTHESISREVIEWSTHEHISTORYOFPOINTBASEDGRAPHICSANDPRESENTSTWONEWALGORITHMSONSHAPEMODELINGOFPOINTSAMPLEDGEOMETRYANOVELALGORITHMISPROPOSEDFOTSAMPLEDGEOMETRYTHEBOOLEANOPERATIONSAREACCOMPLISHEDBYMEANSOFANADAPTIVETHREECOLOROCTREEACCELERATEDINSIDE/OUTSIDETESTINGFORTHEINTERSECTIONREGIONWITHDIFFERENTLOCALSAMPLINGDENSITIESORLARGECURVATURES,ADDITIONALADAPTIVESUPERSAMPLINGISAPPLIEDTHEINTERSECTIONPOINTSAREFURTHERRESAMPLEDFORACCURATERESULTSTHISALGORITHMISSUITABLEFORGENERALPOINTSAMPLEDGEOMETRYWHICHMIGHTBENOISY,NONUNIFORMSAMPLEDORINDIFFERENTSAMPLINGRESOLUTIONSEASYTOUSEFINALLY,ANINTERACTIVESYSTEMFORPOINTBASEDSHAPNK4浙江大学硕士学位论文目录摘要3目录5缩写表7第一章绪论811基本概念816主要贡献20第二章点模型的表示及基于点的造型22点的几何表示23221参数化表示23223SURFELS表示25231理论基础282312协方差分析292313局部采样密度3024本章小节31FELS表示点模型的布尔运算3231引言323333一般点模型的离散布尔操作35331一般点模型的布尔运算框架35332自适应三色八叉树363321自适应三色八叉树结点归类383322自适应三色八叉树边界结点进一步剖分39333SURFEL内外测试算法41334自适应细分加密采样433341主交线的选取433342边界SURFEL的剖分443343细分加密采样45335算法实现4712促动因素813历史回顾1214基本流程1815论文范围2017论文组织2018约定习惯2121引言2222基于222隐式表示24224其他表示方法2623基于点的造型272311局部邻域28232造型技术31第三章基于SUR32相关工作5浙江大学硕士学位论文34实验结果与分析讨论48341实验结果48342算法效率503421自适应八叉树建模分析50第四44结44345本章小第五章总结与参考文献附录致谢3422时间效率513423存储空间分析533424空间开销VS时间开销5435本章小结54章光顺造型5641引言56411问题描述5742LAPLACE算子57421点云的LAPLACE算子磨光57422理论分析594221空间分解594222噪声分布594223与多边形网格光顺的比较6043邻域重心约束光顺算法61431局部求解算法62432邻域控制63433局部光顺63434算法实现64果与分析65441数据模拟与误差评定66442计算结果67讨论70结71未来工作737683APPENDIXA83APPENDIXB85866浙江大学硕士学位论文缩写表APICSGDGDIDOFDPDIFEWAGBRIBMIBMRIBRLDCLDISLODNUPBMBRPOINTBASEDRENDERING基于点的绘制CAPRINCIPALCOMPONENTANALYSIS主元分析RBFSRADIALBASISFUNCTIONS径向基函数RIRANGEIMAGE深度图象SPGSTATISTICALPOINTGEOMETRY统计点几何APPLICATIONPROGRAMMINGINTERFACE应用程序界面CONSTRUCTIVESOLIDGEOMETRY构造实体几何PDIGITALGEOMETRYPROCESSING数字几何处理DIMEPTHAGE深度图象DEPTHOFFIELD场景深度FERENTIALPOINT微分点ELLIPTICALWEIGHTEDAVERAGE椭圆加权平均GEOMETRYBASEDRENDERING基于几何的绘制IMAGEBASEDMODELING基于图象的造型IMAGEBASEDMODELINGANDRENDERING基于图象的造型与绘制IMAGEBASEDRENDERING基于图象的绘制LAYEREDDEPTHCUBE层次深度立方体LAYEREDDEPTHIMAGES层次深度图象LEVELOFDETAIL细节层次MLSMOVINGLEASTSQUARE移动最小二乘NBHDNEIGHBORHOOD邻域RBSNONUNIFORMRATIONALBSPLINES非均匀有理B样条POINTBASEDMODELING基于点的造型PP7浙江大学硕士学位论文第一于点的实体点云POINTCLOUD基于点的造型基于点云的表面表示、处理及编辑。计算机绘制基于点表示实体的技术。一个带形状因子与光照属性的0维元组AZERODIMENSIONALNTUPLE，用来局部近似物体表面PFISTER00。点元映射到屏幕后在图象空间内重构物体表面。括多边形、示的目的在于能的绘制技术一分曲面等，最终硬件的高速发展以及对几何表面三角化算法的深入研究进一步巩固了三角网格在图形绘制以及造型中的地位GROSS01。然而，随着研究以及应用的不断深入，人们对场景绘制的真实感与速度要求章绪论本文主要研究基于点表示的三维实体的造型技术。本章将回顾基的表示、处理以及绘制技术的历史起源与发展现状。11基本概念密集三维点集，或称为密集离散点集。基于点的绘制点元SURFELSN12促动因素在计算机图形学领域内已经提出了很多成熟的曲面表示方法，包样条曲面、隐式曲面以及各种各样的混合表示方法。所有这些表简便地生成不同形状的物体表面。多年来，基于多边形/三角面片直受到高度重视。其他曲面表示，诸如隐式曲面、NURBS、子都被转化为三角形表示以便采用常规图形绘制硬件进行绘制。图形8浙江大学硕士学位论文越来越高，几何场景变得越来越复杂。特别是在虚拟现实中，为达到逼真的显示效果，用于构造场景的三角形数目往往数以亿计。尽管硬件性能不断发展，如NVIDIA公司的FX5800、FX5900，ATI公司的RADEON9700PRO、RADEON9800PRO等卡已经达到每秒上亿个三角形的绘制速率，但仍然不能满足场景实时绘制的需求。造型的角度上看，基于几何面片的场景造型方法往往需用大量的多边形来不仅造型工作量巨大，而且给实时绘制带来极大的困难。事实上，量微小的三面片已经成为高性能图形绘制的瓶颈。决方案试图解决这个瓶颈问题，但底解决造型与绘制方面所面临的压力型LOD来解决计算负担过重的问题E97COHEN98等。多分辨率模型利用人类视觉的特性，在视觉效果等同的条件下对复杂场景作多层次的简化以降低场景绘制的计算量。多分于三角面片的表示方式，在简化计算时常涉及几何误差估计、表快速消隐类算法GREENE93ZHANG97等通过剔除场景中的不可见景物来减少画面绘制的计算量，但这类算法对遮挡率较高的场景较为有效，且算法效率与CATMULL引入纹理映射CATMULL74以增加物体表面的视觉复杂度。纹理映射后的多边形可以承载更多的细节，并不依赖于场景复杂性，而仅仅跟显海量数据场景、更高的真实感实时动态交互仍然是当今图形技术所面临的巨大挑战。从描述场景细节，处理大角学术界已经针对性地提出了多种不同的解这些方案都不能彻众多研究者采用场景表面的多分辨率模HOPPE97LUEBK辨率模型通常基面重采样以及三角网格拓扑一致性维护等一系列复杂的问题。这种方法不仅预处理时计算量巨大，在显示时也难以实现不同分辨率之间的平滑过渡。场景的复杂度有关。因此用较少数目的三角面片就可以达到相似的显示效果，这可以在一定程度上减轻绘制方面的压力。然而基于硬件的纹理映射目前只适用于多边形几何体。表现一幅复杂的场景往往需要很多纹理，占用较多的纹理内存和传输带宽。许多自然场景如火焰、烟雾等，用纹理映射尚难以达到逼真的显示效果。基于图象的造型与绘制技术IBMR被普遍应用于虚拟现实中，具有绘制速度快、真实感强的优点。基于图象的绘制IBR9浙江大学硕士学位论文象素分辨率有关。但IBR技术与视点相关，需要存储大量的图象才能合成新的图象。高度的冗余消耗了大量宝贵的存储空间和传输带宽。扑信息，目表新制量的传输带宽。场景复杂度越高，效率问题就越突出。连贯性，的时候，发现随着多边形个数的增加，过象素个数时，这种连贯性的优势几乎丧失殆尽。图绘工程量，重达10从空间存储的角度看，基于多边形表示的实体的基本信息包括几何信息与拓通常采用一个顶点表和一个三角形表来分别存储，三角形数目是顶点数的两倍。绘制时不仅要传输顶点表，而且还要传输三角形表。在对基于多边形示者，从绘制体系的角度看，场景规模的不断增大对图形绘制体系也提出了的基本信息即可。在绘简的大规模场景绘制时，三角形表不但占用了大量的存储空间，而且占用了大再要求。传统的多边形绘制采用扫描线算法，扫描线算法充分利用了扫描线的采用增量方式实现快速绘制，且只需要存储顶点的单实体时这种算法效率非常高，而且非常适合硬件实现。但实体复杂度很高这类算法无明显的优势。LEVOY在研究复杂度与连贯性的关系时LEVOY85扫描线算法的绘制效率快速下降。当多边形个数超11THEDIGITALMICHELANGELOPROJECTPICTURES1左图3D实物扫描示意图；右图计算机制最终结果为2G多边形及7,000图片的模型，总数据量为32G。主扫描仪高75米，的米开朗基罗的大卫雕像。整个工程动用了22人和480个扫描仪，完成1,080人时的800千克，最高扫描精度为029MM。浙江大学硕士学位论文此外，随着近年来3D数码扫描仪的日益普及与应用（见图11），扫描获取的几何体的细节以及外形更加丰富，迫切需要新的能有效表示、处理以及绘制超大规基于以上几个因素的推动，基于点的表示及绘制技术重新引起了人们的关注。相对于传统的基于多边形的绘制体系，基于点的绘制具有以下优势基于点的绘制可避免传统多边形模型绘制时的大量时间开销。点能非常快速地绘制，无需进行复杂的多边形裁剪、扫描转换等中间处理过程。正因为点模型拓扑结构简单，因此能更方便地进行视点相关的表面重采样。只要根据硬件条件控制绘制点的数目，点绘制可以很容易地实现固定的绘制速率。基于点的造型与绘制特别适合于表示表面几何高度复杂或具有复杂表面光照细节的模型，如雕塑与石刻，也能用于火焰、流云、落叶、草地、树木等自然场景的模拟，点作为基本元素能很好地表示过程几何EBERT98。此外基于点的绘制能很方便地与传统的几何模型（多边形模型、样条面片模型等）混合绘制。可以利用多边形硬件加速点模模、高度复杂的几何模型的方法。3D扫描仪输出目标物体的大量密集采样点，这些点相互之间没有任何连接关系。传统方法需将扫描获得的离散采样点转化成多边形模型再作进一步的处理及绘制，但随着采样数据规模的不断扩大，多边形模型转化或重构的方法变得越来越低效，多边形表示方法的局限性变得更为明显。综上所述，随着应用规模的不断扩大以及新技术新设备的投入使用，图形学的发展迫切需要解决以下问题Z高效率绘制高度复杂的物体及场景；Z减少冗余，节约存储空间；Z新的绘制体系结构的需求；Z直接绘制由3D扫描设备生成密集点云。与基于图象的表示不同，基于点的表示方法很少冗余，能显著地节约存储空间。由于点之间相互独立，无拓扑关系以及邻接关系，也无需存储多边形网格表。现在的图形硬件无一例外地支持直接点绘制，11浙江大学硕士学位论文型绘制REN02并达到理想的绘制效果。另外还有非常重要的一点，由于表示模型的13本节我们将回顾基于点的图形学的历史发展，以时间顺序排列点作为基本的图形绘制元素已经有很长的历史了。早在1974年，CATMULLCATMULL74注意到任何几何剖分最终都将显示为一个个离散点。不幸的是点作为基本图形元素在很长一段时间内不受重视，尽管很多系统都将其集成到应用程序界面API中。随后REEVES在1983年提出在计算机图形绘制时用3D离散采样点粒子REEVES83作为基本绘制元素。一个粒子是三维欧氏空间内的一个点，附属一些如颜色、密度、光照反射系数等附加信息。粒子系统的最大的优点在于简便快捷的绘制将每个粒子投影到屏幕上，利用ZBUFFER消隐，并用粒子的颜色给相应象素着色。粒子系统主要应用于一些用传统造型方法很难表示和绘制的自然场景如火焰与爆炸场面REEVES83，流水MILLER89与瀑布SIMS90。LEVOY与WIHTTEDLEVOY85在1985年首先提出将点作为基本绘制元素的思想。他们分析出复杂物体用连续的扫描线方法绘制时的缺陷，并指出点虽然简单却足以表示任何物体只要三维点云足够致密，将一个个点投影到屏幕上后仍然能得到逼真的显示效果。其核心思想是在绘制前将任何物体转化成一系列离散点表示并用一个新的通用算法绘制。他们用圆形SPLAT来绘制点，并设定SPLAT的最小尺寸为一个象素以保证绘制质量，同时采用ABUFFERCARPENTER84技术进行反走样，论文中还详细地考虑了纹理问题。点的独立性，基于点的绘制允许高度的并行处理。概括地讲，点离散地表示几何而无需存储任何拓扑信息。因此，点云简化了实体表示方法而只保留最重要的信息，尽管无拓扑使得数据结构变得非常简单，它同时会给图形处理带来很大的困难与挑战。高性能绘制、光影计算、各向异性的纹理映射以及进一步的信号处理将是其最大的特点GROSS01。历史回顾12浙江大学硕士学位论文1992年SZELISKI与TONNESONSZELISKI92在REYNOLDSREYNOLDS87的工作基础上改进了粒子系统，给原本各向同性的粒子确定了一个法向，并将这个有向粒子系统应用于模型的表面造型以及交互编辑。每个有向粒子是一个具有局部构架的点，面的采样以及交互编辑，并采用同样的绘制方法SZELISKI92来显示有向粒子。受基于图象的绘制技术IBR的启发，1998年GROSSMAN与DALLYGROSSMAN981开展了点绘制方面的研究工作，其目标是在避免昂贵图形硬件的条件下实时绘制复杂物体。同一时期美国MERLMITSUBISHIELECTRICRESEARCHLABORATORIES拓展了SURFELSSURFACEELEMENTS的概念OOSTERBAAN99BAAR99，其思路与GROSSMAN和DALLY的点采样绘制方法POINTSAMPLERENDERINGAPPROACH非常相似。随后，1999年第一篇有关SURFELS的表示、压缩及动力特性的技术考察报告发表ZWICKER99。2000年随着PFISTER等人的SURFELSPFISTER00与RUSINKIEWICZ等人的QSPLATRUSINKIEWICZ00绘制系统出现,点绘制技术有了重要突破。PFISTER等PFISTER00在GROSSMAN和DALLY工作AN981的基础上加上层次LOD控制以及层次可见性剔除。他们采用了VISIBILITYSPLATTING技术来检测可见SURFELS以及ZBUFFER内的空洞，并采用PULLPUSHGORTLER96GROSSMAN981填补空洞。灵活权衡速度与质量的超采样技术被应用于反走样，达到了类似于三线性MIPMAPPING方法的图象质量。由于SURFELS采用LDI结构，点云分布在一个规则的空间网格中，因此从三维扫描设备获取的数据不能直接应用这个方法。SURFELS绘制技术介于基于几何绘制GBR及基于图象绘制IBR之间。同期，RUSINKIEWICZ和LEVOY给QSPLATRUSINKIEWICZ00系统设计了一种全新的数据结构，高效地压缩了数据并实现了层次LOD控制和基于法向聚类的可见性剔除。在预处理阶段，采样点存储在层次包围球内。在绘制时层次遍历数据结相互间通过远距离引力和近距离斥力发生关联。在绘制有向粒子时他们并没有使用基于点的绘制技术，而是用椭圆来显示粒子，最终实体也是三角化的曲面。这种有向粒子被他们首先命名为“SURFELS”。1994年WITKIN与HECKBERTWITKIN94将有向粒子应用于隐式曲GROSSMAN982重新GROSSM算法13浙江大学硕士学位论文构，对点云表示曲面的光线跟踪算法，所有00的项目报告发布技术KALAIAH01、点采样曲面的频谱处理PAULY01、基于点的多分辨率造型L作。ZWICKER等ZWICKER011结合了LEVOY等人LEVOY85的想法以及HECKBERT的纹理中波）SURFACESPLA合表示场景C根据当前视点视角、屏幕分辨率以及计算条件等情况选择绘制的层次。QSPLAT的算法设计允许使用硬件加速绘制，能实时地绘制上亿个点的超大模型。其缺点是没有考虑透明度以及反走样问题，因此绘制质量一般。TOBOR等TOBOR00也提出一种类似于GROSSMAN与DALLYGROSSMAN98点采样绘制技术的SURFELS绘制系统，充分利用硬件来处理SURFELS。GERNOTSCHAUFLER与HENRIKWANNJENSENSCHAUFLER00提出了一种针的SURFELS均位于八叉树结点内并用光线跟踪算法绘制。在QSPLAT的相同应用背景下，同年DIGITALMICHELANGELOLEVOY。新的扫描技术的发展以及几何实体复杂度的日益增长对基于点的图形技术发展提出了更高的要求。2001年出现了EWASURFACESPLATTING技术ZWICKER011、动态采样绘制技术STAMMINGER01WAND01、多边形与点的混合绘制系统CHEN01COHEN01、微分点绘制INSEN01、MLS曲面ALEXA01以及径向基函数CARR01等一大批基于点云表示的处理方面的研究工映射的反走样理论HECKBERT89，提出了EWASURFACESPLATTING技术，将EWA技术应用于不规则空间采样点的绘制。EWA（椭圆加权平均滤TTING是一种高质量的物体空间的绘制技术，从信号处理角度考虑各向异性的纹理过滤、消隐、边界反走样和象素精度的ABUFFER处理。EWASPLATTING技术也可以应用于体绘制ZWICKER012。纯粹用点云来构建场景有其应用缺陷首先，点云的密集分布造成了大量的数据冗余，极大地消耗了存储、传输以及绘制资源；其次，在当前的几何绘制引擎中，点云在绘制时最终采用三角形或圆面表示，而拓扑关系的缺失使得在视点靠近时无法保证无空洞的绘制效果。因此许多研究者采用多边形与点混HEN01COHEN01，这种混合表示方式结合了点与多边形两种表示方式的优点当绘制元素在屏幕上投影区域很小时用点绘制效率高一些，反过来投影区域较大时用多边形绘制效果更好。14浙江大学硕士学位论文动态重采样绘制是一类与视点相关的绘制算法，点云的重采样在绘制时进行，没有预处理过程。WAND等人WAND01使用三角面片集的随机采样点来达到交互显示的效果；STAMMINGER与DRETTAKISSTAMMINGER01使用固定采样模式从复杂场样点要少，因此非常节RUSINKIEWICZ01改进了QSPLAT，将其扩展到网络传输的应用。LUEBKE与HELLENLUEBKE01采用感知度量作为点绘制时LOD的选择标种针对点采样曲面的傅立叶变换以及频谱分ONU02使用硬件加速EWASPLATTING，三角面片景中动态采样。同时，他们还提出一套可用硬件加速点绘制的LOD技术。KALAIAH与VARSHNEYKALAIAH01使用DIFFERENTIALPOINTDP,微分点作为新的绘制元素。与传统的采样点不同，每个DP采样点保留了局部微分几何信息，用以高效高质量地刻画其局部邻域。DP模型比一般的点模型的采省空间，但又不影响绘制效果。DP可以从NURBS曲面上采样得到，也可以从任何微分曲面上采样得到。它的一个限制是只能表达光滑表面。RUSINKIEWICZ与LEVOY准。WIMMER等WIMMER01在城市漫游时采用点来绘制远处场景。ALEXA等ALEXA01使用移动最小二乘法MLS逼近点模型表面的点云得到局部逼近的多项式曲面，并以此定义光滑的二维流形表面来表示点云。MLS曲面被用来进行加密采样以及简化采样，并可在绘制时采用动态加密采样技术以得到光滑的表面显示效果。CARR等人CARR01采用多重调和的径向基函数RBFS从非均匀分布点云中重构出光滑的流形表面，并将其应用于CSG框架来实现一种新的造型方法。LINSENLINSEN01在其报告中提出一种点模型表面的多分辨率造型框架。他提出了简化采样算子、加密采样算子、磨光算子与点模型的多分辨率分解表示，并拓展了CSG表示方法使之适用于点模型。PAULY和GROSSPAULY01提出了一析框架。他们将模型分解为近似为平面的一系列小块，在每个小块上做傅立叶变换以及频谱分析，然后将各个小块拼接起来实现对点采样曲面的处理。2002年国际学术界在这以领域的工作主要集中于高效的点绘制算法，基于点的造型以及点绘制技术的应用。BOTSCH等人BOSTSCH02提出用一种非常节省空间的混合数据结构表示点模型并快速绘制。COCONU和HEGECOC15浙江大学硕士学位论文与转化成LDI的采样点均存储在八叉树内。他们的算法采用八叉树来做LOD以及可见性预计算，拓展并应用了MCMILLAN算法。同时，对EWA反走样滤波则用一系列查找表来估计。与此不同的是，REN等人REN02采用带ALPHA位的四边形表示并绘制SPLAT，并采用两步绘制流程来解决可见性问题及混合问题。WAND和STRAERWAND02提出一种点多边形混合绘制技术来实现固定帧的动画绘制。DEUSSEN等人DEUSSEN02用STAMMINGER的方法STAMMINGER01交互式绘制大规模生态场景。RSNENRSNEN02系统地讨论了EWASURFACESPLATTING并作了些改进，他用随机采样来实现高质量的EWASPLATTING。DEY和HUDSONDEY02发展了另外一种基于VORONOI表面重构技术AMENTA98的点多边形混合绘制系统。与其他点系统，他们简化算法以及粒子模拟算法来得到与原模型相近的简化点模型。理念如ZWICKER021允许交互编辑显示表面LEISHMAN等人FLEISHMAN02使用MLS面作为他们的基于点采样的多分辨率曲面的改进。KALAIAH和VARNSHEYKALAIAH031继续FLEI多边形混合绘制系统不同的是，他们的绘制系统可根据局部几何特征的大小来决定采用点还是多边形绘制。WRMLIN等人WRMLIN02设计了一套应用点绘制技术的3D视频还提出一种高效的点模型压缩技术。点绘制的另一个应用实例是GRIGORYAN和RHEINGANS的PROBABILISTICSURFACESGRIGORYAN02。PAULY等PAULY021比较了几种不同的点模型简化算法，包括区域增量聚类算法、层次聚类算法、迭代他们还提出了一种简化模型的误差计量方法。同年PAULY等设计了一个多分辨率点模型造型框架PAULY022。这个框架集成了当时不少多分辨率造型几何光顺、简化以及偏移量计算，包括了LINSEN01的一些特色。动态重采样是其一大特点，可保证编辑时点模型表面具有足够的采样密度。ZWICKER等人的编辑系统POINTSHOP3D为采样点的几何体。结合传统的2D象素编辑方法，POINTSHOP3D能支持多种变形、编辑技术如清理、纹理映射、雕刻、过滤以及重采样等，其最大的特性是点云模型集成了参数化表示。F表示的基础。他们主要的工作是对基于点云表示的表面作有效的渐进式编码，但在多分辨率编辑上没有很大SHMAN等人的工作FLEISHMAN02并加入DP，使得曲面表示拥有了更多的细节。ZWICKER等ZWICKER022提出了EWA表面以及体绘制的统一绘制框架。16浙江大学硕士学位论文EUROGRAPHICS2002的基于点的计算机图形学教程GROSS02总结了近几年来基于点的图形学的发展状况，并讨论了以下几个论题包括EWASPLATTING在内的点绘制技术、从图象中获取几何以及外观信息、动态重采样以及实时生态系统可视化、点模型的表示MLSSURFACES、点模型的频谱处理、点模型简化以及POINTSHOP3D系统。在2003年SIGGRAPH会议上，ALEXA等人ALEXA031在原来的基础上进一步拓展了MLSSURFACESALEXA01。ADAMSON和ALEXAADAMSON03使用MLS投影运算实现点采样表面的光线跟踪算法。ALEXA等ALEXA032通过对点模型表面建立方向场来实现表面参数化、纹理合成以及表面间的映射。PAULY等PAULY031在以前的工作基础上PAULY022提出了一个完整通用的点模布尔运算。被细分重采样以利通过深度模糊以及视觉聚焦选择适当的LOD绘制达到型自由造型框架。结合无约束点云及MLS近似得到的隐式曲面，他们构造出混合表示的实体模型。该造型系统同时利用了隐式曲面以及参数化曲面的优点，允许对任意形状的点模型作大规模的变形以及OHTAKE等人OHTAKE03提出了一种新的隐式外形表示方式整体多层分割MULTILEVELPARTITIONOFUNITY,MPU来构造大规模点云的表面模型。通过八叉树剖分点模型成若干区域块，并用分段二次函数来描述局部形状再用加权函数混合局部形状函数达到整体光顺的表示效果。ADAMS和DUTR实现了基于SURFELS表示实体的交互式布尔运算ADAMS031。八叉树结构被用来加速布尔运算时的内/外测试，相交边界处SURFELS达到锐的边界表示结果。同时他们还提供了一个相交边界的磨光算法ADAMS032。KIVNEKKIVNEK031在EWASURFACESPLATTING的基础上创建了一种新的快速深度场景DOF绘制算法。图象合成效果。BALA等BALA03提出了新的一种带阴影计算的复杂场景绘制技术，结合点与边生成高质量图象。用图形芯片GPU加速图形绘制已经成为热潮，DACHSBACHER等DACHSBACHER03设计了一个连续结构树并用可编程图形硬件绘制，使得CPU的计算负担大大减轻。17浙江大学硕士学位论文14要来源为3D扫描仪生成的原始数据，包括深度相机生成的深度图RI与激光三维扫描仪或者接触式机械探头等设备得到的大量三维空间点一步的造型处理如重采样、一系列的点并构成连续的表面。从三维离散制所含的基础问题，如光照计算、可见性计算、阴影计算、纹理映射基本流程基于点的图形学分成三个主要部分获取、处理以及绘制。获取点模型的主位置。三维点云再配合光学照片可以得到带颜色或纹理色彩的三维实物模型。点模型的另外一个来源是现存的几何模型。所有几何模型（多边形网格模型、样条面片模型、隐式曲面、CSG树、粒子系统等）均能方便地转化成点模型，不同的采样精度能得到不同分辨率的点模型。处理点模型的处理分前期处理OBJECTREPRESENTATION以及后期处理OBJECTMODELING。扫描得到的原始数据具有噪声、拼接错位、空洞、不确定性和过度采样的问题，需要经过前期处理才能使用。前期处理的目标是从原始点云中构造出一个连续的表面模型，后期处理则在前期处理的结果上再作进磨光、多分辨率简化、编辑、变形、布尔运算等操作，得到各种各样的点模型。对点模型的数字几何处理DGP也在后期处理阶段进行，其目标是在点模型的流形表面领域内拓展基本的信号处理概念。绘制点绘制的目标是在屏幕上输出点采样直接重建出三维空间的连续信号，对连续信号进行滤波后重新采样并投影至二维屏幕进行光照计算。由于点模型没有拓扑关系，利于重新采样和投影计算，因此点绘制的可以加快大规模数据构成场景的绘制过程。点模型的绘制同样需要解决面绘、反走样等。另一方面，点模型的离散性使得在视点靠近物体的时候，需要考虑点模型和面模型的混合绘制。基于点的绘制技术的一个特点是离散点集映射到屏幕后需要在图象空间内作图象重构处理来填补空洞并重构物体表面。整个流程如图12所示。18浙江大学硕士学位论文示实体的获取、处理及绘制全流程图。获取处理绘制图12基于点表点云表示模型正向WARPING过滤、光影计算可见性剔除图象重构帧缓存混合表示网格表示隐函数表示造型处理光顺、除噪、变形、编辑等传统技术处理传统技术处理配准映射到几何错误校正简化、去冗余纹理网格化三维扫描设备深度相机相机其它模型深度图象光影照片三维点集原始点云直接点云表示19浙江大学硕士学位论文15论文范围一些其它方面相关的内容也在论文中有所提及，包本文不讨论如何从实物扫描获取点模型，也不讨论如何将其他方法表示的模转化成点模型。造型时用到的点模型均是前期处理过的，不是原始扫描获得的6主要贡献本文的部分工作建立在AADAMS03、PAULY等人PAULY022的工作基础上。他们的论文中已经提到了部分重要内容，但还有许多工作没有提及ZAMS和框架并于不模型以及非均匀采样点模型的布尔运算。本文应用自适应八叉树剖分实体来加速INSIDE/OUTSIDE测试，并在相交边界处采用动态重采样技术以保持锐利的边界表示。Z从统计的角度分析点云模型的光顺除噪，并提出了一个针对随机噪声的邻域重心约束光顺算法。此方法不需保证迭代过程中主体形状不变。Z通过初始点约束将邻域重心约束光顺算法推广为局部光顺算法。7论文组织第一章回顾章将系统介绍人在基于点的模型表示与造型方面的工作；第三章介绍了一种不同分辨率点模型以及非均匀采样点模型的布尔运算框架，此框架是对ADAMS和DUTR提供的算法ADAMS03的一个拓展；第四章讨论点模型的光顺造型。第五章总结全文并介本文主要讨论点模型的表面表示以及在此基础上的造型技术，基于点的绘制方面的内容也将涉及到一点。括IBM，IBR，DGP等。型数据。1DAMS和DUTR或者还未完成。本文主要贡献如下拓展了ADDUTR的将其应用同分辨率点要表面重构并1基于点的造型与绘制的历史起源与发展状况；第二前20浙江大学硕士学位论文绍了一些未来工作。如果没有特别说明，每个采样点均表示一个带有法向的微小局部区域。通常用一个带一定半径的圆盘简化表示此区域。本文在绘制时采用直接几何绘制方法用带位的纹理绘制四边形，这个四边形垂直于其法向（在一些特殊场合默认采样点形状为球，采用正交投影到屏幕的方法绘制）。这种绘制方法可利用图形硬件绘制多边形并用硬件ZBUFFER消隐。果在一些区域内存在严重的空洞与走样现象，但这种方法能很好地表示局部几何信息，并且能快速地绘制，因此它特别适合于本文所研究的空间为欧氏空间。造型所依赖的座标系为右手标X图13右手座标系18约定习惯尽管局部放大绘制结造型阶段的交互式显示。要得到更好的绘制效果，可以采用更好更复杂的绘制方法（如EWASURFACESPLATTING），但这不在本文的研究范围之内。如果不做特殊说明，文中所提及的座系，X轴正向向右，Y轴正向向上，Z轴正向指向观察者（图13）。YOZ点云均以集合表示，其中代表采样点的索引表示，其中3,RPPPIPINDEXIIPINDEX集（即下标集，通常以,1NPN为集合P内元素个数）。21浙江大学硕士学位论文第二章点模型的表示及基于点的造型本章的内容属于基于点表示实体的获取、处理及绘制全流程（图12）的第二部分。及外形的日渐造型方法和造型软件在计算机内造型的工作量巨大，已经难于适用于新的应用场合。为解决这一问题，近年来基于点的绘制技术被广泛地研究并取得了一系列重要进展GROSSMAN982ZWICKER99PFISTER00RUSINKIEWICZ00ALEX01GROSS02KALAIAH032。然而，迄今为止基于点的造型方面的研究成果甚少SZELISKI92ADAMS031PAULY033，点作为基本体素在数字几何处理中的应用还未曾被深入研究过PAUPY033。由于点模型无拓扑无邻接关系，在造型时无需维护其拓扑一表面流形维护以及信了难度。局标架使得点模型的信号处理异常困难，然而这正是点信号处理特别具有挑战性的地方。在接下来的章节中，节22将主要介绍几种主要的点模型表示方法，节23将侧重介绍点作为基本体素的一些数学描述以及它在几何造型中的应用。本章将系统介绍前人在基于点的模型表示与造型方面的工作，并在基于点的造型方面做一些基础性的探讨。21引言随着计算机技术的应用与发展，人们对计算机造型与绘制技术的要求不断提高，计算机模拟场景的规模越来越大，景物的细节也越来越丰富。特别随着三维数码扫描仪的大规模普及与应用，随着扫描获取的几何体的细节以丰富，对有效生成、处理超大规模几何模型的新方法的需求也日渐增长。由于传统的基于几何面片的场景造型需要大量的多边形来描述场景细节，利用传统的致性，但却给绘制、号处理增加此外，缺乏一个全22浙江大学硕士学位论文22基于点的几何表示在计算机图形学领域内，自由曲面造型一直是研究者关注的核心问题之一。点模型的表示首先是一种表面表示方法，基于点的几何表示的目标是从离散点集中构以及采样处理的一些信息（如误差大小造出连续的表面。HOPPE将此问题一般化并提出了一个统一性的陈述HOPPE92表面重构的目标是用一个采样集P和采样密度）来确定一个近似表示未知表面M的表面M。（见图21）0P4P5P6P图21表面重构示例2PM1P3PMPPI基于点的表示的原始输入为点云，点云的输入途径见节14的介绍。每个采样点上可以附加多种属性，如色彩、材料属性、法向和表面曲率等。针对输出点模型的表示形式，众多研究者们提出了不同的输出方案，下面是几种常用的点模型表示方法表示等。221参数化表示在众多的表示方法之中最简单自然的想法是从离散点集中重构出参数化的2维表面。参数化表示的代表为样条曲面（特别是NURBS曲线/曲面）、子分曲面、多边形网格参数化重构/表示就是定义一个2维参数域到3R的拓扑同构映射3RF21映射的代数结构通常比较复杂并且同物体表面复杂度紧密相关；参数域F23浙江大学硕士学位论文通常选取比较简单的2维流形如平面、球面等。改变参数域或同构映射便能得到不同的参数化表示。此外由于参数化表示曲面使用显式邻接表示信息，能够保证在大幅度变形时曲面依然保持连续。特别地，当为插值映射时有ZZ细节丰富，能够表示尖锐特征；Z直观的编辑；Z保留微分属性，如法向、曲率等；Z支持层次细节表示LOD。另一方面，参数曲面表示有以下不足之处Z拓扑维护困难。一旦拓扑被改变，需要重构全局连续的映射；Z不适合作过度的变形。过度扭曲时需要更新网格的连接关系来维护一致性；Z布尔操作困难。22隐式表示表示方法通过找一个光滑的标量函数FFFP。参数曲面表示有以下优点快速高效地绘制，硬件支持多边形绘制；F2隐式寻RRG322使得在误差允许的范围内X接近于其零集GZ并以其零集GZ来表示实体表面。隐式表示方法的代表为移动最小二乘、TSMUSETH02、径向示法数结构，实体表面以MLSLEVIN01LEVELSE基函数RBFSCARR01和代数曲面。这些表方均具有一个简单的代3维标量场的零集GZ表示。其中G为一系列基函数RRGI3的权即和。24浙江大学硕士学位论文IIIG其中权向量IIG23可通过求解一个由点集P定义的线性方程组得到。对于3维空间内X的任意一点，通过就可以判别是属于实体外部、实体内部还是处于体表面上。的区别在于标量函数XGSIGNX实各种各样的隐式表示方式G的定义、表达形式以及对采样点集逼近程度上的差别。选取不同类型的基函数时表示的实体表面GZM具另外，这通过简单地控制采样点的数目准确地说即改变采样密度有不同的微分性质。通过不同基函数的组合，高度复杂的表面就能被简单地表示出来。种方式构造出来的表面具有全局连续性和光滑性。（）就能很方便地实现LOD。隐式表示的这些优点法目前尚不支持高效率的绘制以及示利的特征。表示SURFELS，2维SPRITE绘制的3维点。研究者提出SURFELS的初衷是用来加速真近的研究表明SURFELS也可以作为自由造型的基本体素PAULY031ADA按照PFISTER等人的定义PFISTER00，SURFEL点元是一个带形状因子与光照属性的0维元组AZERODIMENSIONALNTUPLE，用来局部近似物体表面（图22）。样属于R致密体域的采样点，通常列成规则的3维点阵KAJIYA84；Z粒子动态体采样点，用来模拟各种各样的模糊现象REEVES83；正是参数化表示所不具备的。然而此类表示方精确的特征造型。隐式表示的另一个缺点是细节不够丰富，难以表锐223SURFELS实感图形绘制，但最MS031。N大体上讲，大多数基于点采的表示方式均此类表示方式SNEN02Z点带颜色的0维表面采样点，通常有法向属性LEVOY85；ZSPLATS带颜色、法向和局部方差矩阵的表面采样点ZWICKER011；Z微分点带有局部微分信息的采样点KALAIAH01；Z体素25浙江大学硕士学位论文ZIBR基元图象，深度图象DISPOPESCU00和层次深度图LDISSHADE98包含的带色的表面表示方法具有以下优点隐S。这个过程被成为SURFELIZATION，它实际上是一个3D栅格化过Z通过改变SURFELIZATION时的栅格分辨率能很方便地得到不同分辨率表示LOD。如三角网格表示或者样条曲面表示的实体URFEL彩的采样点，通常呈规则分布。基于SURFELSTOBOR00Z每个几何体（多边形网格、样条面片、式曲面、CSG树等）能很方便地转化成SURFEL程。Z基于点表示的模型能与传统模型，混合绘制，并能极大地提高绘制效率。Z如果限定绘制的SURFELS的数目，可以达到给定的绘制速率。SPOSITIONNORMALRADIUSCOLOR,ETC图22SURFEL示意图SURFELS作为造型的基本元素的最大弱点是不能得到处处连续的实体表示，它只是物体表面的一系列离散的局部近似，所以不能应用于CAD等精密造型系统。基于。示SURFELS的造型受允许误差的影响较大，当SURFEL尺寸小于或跟允许误差大小差不多时很容易引起错误或者歧义，因此基于SURFELS的造型具有一定的局限性。尽管如此，在要求不高的前提下基于SURFELS的造型是一种快速简便的方法224其他表示方法以上3类表方法最受研究者重视，除此之外还有一些新颖独特的表示方式。26浙江大学硕士学位论文下面介绍主要的两种，限于篇幅，其他表示方法将不再一一介绍。统计点几何SPG型KALAIAH032。他们发云上始点云做层次统计分析（见图23），此方法描述如下树的每个结点内点云的位置、法向以及颜色作主元分析PCA；ZKALAIAH和VARSHNEY用统计的方法来有效表示点云模现以下两个特性离散点云在局部邻域内有很好的连续性；用统计方法在稀疏点生成致密点云后可以实现高精度的真实感绘制。针对这两个特性，他们对原1、对点云作八叉树空间剖分；2、对八叉3、用K平均聚类与量化方法实现高度的压缩；4、用随机生成的点云绘制。图23层次主元分析的2维示意图。先对无约束点云作八叉树剖分，然后再对每个非空节点作主元分析。这种表示方法有效地解决了几何带宽的瓶颈。此外，由于各个局部几何相互间的解码完全独立，这使得大规模并行绘制成为可能。SPG方法支持模型数据的高度压缩、渐进式网络传输和快速的实时绘制，它的另一个