（应用数学专业论文）参数曲面点元离散求交法.pdf

浙江大学硕士学位论文 摘要 参数曲面求交算法是几何造型中的一个基本问题。本文在前人提出的离散求 交方法基础上，结合近年来发展的基于点表示的造型技术，充分利用基于点的造 型技术拓扑简单和易于多分辨率采样的优势，提出了一种新的基于点元的光滑参 数曲面离散求交方法。 本文通过自适应地将曲厩离散采样为点模型，从而将曲砸的求交问题转化为 动态重采样的点模型的求交问题。算法在参数曲面上进行自适应的离散点元采 样，将点元组织为八叉树空间层次结构以加速求交测试，对相交并满足精度要求 的八叉树叶结点里的点元进行求交。最后进行交点排序得到最终的求交结果。 我们通过对包围盒中点元的法向分析，找出曲面可能相切或近似相切的区 域。由于这些区域对曲面的离散采样具有更高的精度要求，我们对它们进行加密 采样以增强算法的准确性。 与以往的基于m e s h 的参数曲面离散求交方法相比，本算法更简单高效。本 算法拓扑结构维护简单，基于点的多分辨率重采样技术方便高效，并且不需处理 在不同分辨率下的求交裂缝情况。该算法也可以很自然地应用于参数曲面与三维 扫描所得的点模型的求交运算上。实验结果表明，本文算法稳定可靠，误差可控， 而且可以达到交互速度。 关键词：参数曲面，求交运算，离散化，点元。 a b s t r a c t t h i st h e s i sp r o p o s e san o v e lp a r a m e t r i cs u r f a c e si n t e r s e c t i o na l g o r i t h m b a s e do nd i s c r e t es u r f e l s t h ei n t e r s e c t i o n a l g o r i t h m o f p a r a m e t r i c s u r f a c e s u r f a c ei so n eo ft h ef u n d a m e n t a lp r o b l e m si nc o m p u t e ra i d e dg e o m e t r i c d e s i g n i nr e c e n ty e a r s ，t h ep o i n t - b a s e dm o d e l i n ga n dr e n d e r i n gt e c h n i q u e sh a v e b e e np a i dm u c ha t t e n t i o ni nc o m p u t e rg r a p h i c sc o m m u n i t y i nt h i sw o r k , w e i n t e g r a t et h es u b d i v i s i o na l g o r i t h m sf o rt h ep a r a m e t r i cs u r f a c e si n t e r s e c t i o n w i t ht h ea d v a n t a g e so ft h ep o i n t - b a s e dm o d e l i n gt e c h n i q u e s f i r s t , t h ep a r a m e t r i cs u r f a c e sa r es a m p l e di n t ot h ep o i n ts a m p l e ds u r f a c e s t h es a m p l ep o i n t sa r ec a l l e ds u r f e i sw i t hg e o m e t r i ci n f o r m a t i o na t t a c h e d a d a p t i v eo c t r e ei sb u i l tt oa e c e l e r a t et h ei n t e r s e c t i o nt e s t s t h e nt h es u r f e i sn e a r t ot h ei n t e r s e c t i o nc u r v e sa r er e - s a m p l e da d a p t i v e l ya c c o r d i n gt ot h ee r r o r a n a l y s i s t h ei n t e r s e c t i o np o i n t sa r ef o u n d o u tb a s e do rt h ei n t e r s e c t i o nb e t w e e n t h es u r f e i si nt h eo v e r l a p p e dl e a f - n o d e so ft h eo c t r e e s f i n a l l y , t h ei n t e r s e c t i o n s e g m e n t sa r er e s u l t e da f t e rs o r t i n gt h e s ed i s c r e t ei n t e r s e c t i o np o i n t s i nt h er e g i o 珊恤砒t h es u r f a c e sa r ep o s s i b l et ob et a n g e n t i a l 。t h ea l g o r i t h m r e q u i r e sm o r ea c c u r a t es a m p l i n g t of i n do u tt h e s er e g i o n s ，t h ev a r y i n gr a n g e so f t h en o r m a l sa r ea n a l y s e da st h es u p p l e m e n tt ot h ep o s i t i o ni n f o r m a t i o no ft h e s u r f e l s c o m p a r e dt ot h et r a d i t i o n a ls u b d i v i s i o na l g o r i t h m sf o rt h ei n t e r s e c t i o no f p a r a m e t r i cs u r f a c e s ，o u ra l g o r i t h md o e sn o tn e e dt om a i n t a i nw i t ht h et o p o l o g y o fm e s h e s s ot h ea d a p t i v e l yr e s a m p l i n gi sm o r ee f f i c i e n ta n de a s i e lo u r a l g o r i t h mc a nb ea p p l i e dt og e tt h ei n t e r s e c t i o nb e t w e e nt h ep a r a m e t r i cs u r f a c e a n dp o i n ts a m p l eg e o m e t r y e x p e r i m e n t ss h o wt h a to u ra l g o r i t h mi se f f e c t i v e ， e a s yt oi m p l e m e n ta n d t h ep r e c i s i o no ft h ei n t e r s e c t i o nl i n e si sc o n t r o l l a b l e k e yw o r d s ：p a r a m e t r i cs u r f a c e s ，i n t e r s e c t i o no p e r a t i o n s ，s u b d i v i s i o n ，s u r f c l 4 浙江大学硕士学位论文 1 1 研究背景 第一章绪论 在计算机辅助几何设计、物体几何造型以及分析和制造等应用中，求交是一 个基本问题【1 】【2 【3 】【4 】【5 】【6 】【7 】，例如：在曲面的可视化中，为了得到曲面的轮 廓化表示，需要将曲面与一系列平行平面或者与一系列同轴圆柱面或圆锥面求 交；在物体造型中，不管是结构实体几何表示还是边界表示法，都要求解决求交 问题；在数控加工( 例如切肖u ) 中，为了产生球形铣刀的加工路径，需要计算等距 面与一系列平行平面的交线；在复杂几何物体的边界表示方法中，例如汽车、飞 机、轮船的内部几何和组成部分的描述包括：自由参数衄面与低阶代数曲面( 平 面、二次曲面、圆环面、柱面) 求交，低阶代数曲面之间的求交；在图形绘制和 图纸输出中，也会遇到大量的求交问题。因此，求交问题的解决在计算机辅助几 何设计中有着重要的意义和价值，求交问题还应用于碰撞检测、加工仿真、科学 可视化等领域。 通常求交问题所考虑的曲面分为以下几类：有理多项式参数型曲面 ( r a t i o n a lp o l y n o m i a lp a r a m e t r i cs u r f a c e ) ，过程参数型曲面( p r o c e d u r e p a r a m e t r i cs u r f a c e ) ，隐式代数型曲面( i m p l i c i ta l g e b r a i cs u r f a c e ) ，隐式 过程型曲面( i m p l i c i tp r o c e d u r es u r f a c e ) 。在本文中，我们只讨论参数曲面的 求交。 计算机辅助几何设计中大多数曲线曲面是用多项式或有理多项式来表示的， 它们的交就是这些多项式或有理多项式方程组的解集，通常无法得到解析解。目 前，参数曲面之间的求交的典型算法主要有三类：网格法( l a a i c cm e t h o d ) 、离散 剖分法( s u b d i v i s i o na l g o r i t h m ) 和跟踪法( m a r c h i n ga l g o 血h m ) 。 网格法的核心思想是降低曲面求交问题的维数。将曲面间的求交问题转化为 等参数线的求交问题，然后连接曲线交点形成曲面交线f 8 】。如何选择初始网格 ( 等参数线) 的分辨率是网格法面临的问题之一，粗网格可能会导致较小的环、孤 立点等重要特征的丢失；此外，如何正确连接曲线交点是其面临第二个问题。 6 离散剖分法的基本思想是通过对血面进行递归剖分，将曲面间的求交问题简 化至可以直接求解的程度( 如平面与平面求交) ，然后将各个独立解连接起来形成 完整解 7 1 1 9 1 1 1 0 1 1 11 1 1 2 1 1 3 ，即分而治之的思想。剖分法分为均匀剖分和非均匀 剖分两类。这类方法的不足在于：在奇异点和奇异点附近，解的分支不能保证正 确连接；由于用平面片逼近曲面，可能会导致丢失或增加一些交线的细节特征； 此外，剖分法在用于求解高精度的曲面交线时，时间和空间开销很大。 跟踪法主要思想是根据交线的局部微分几何性质，得到交线的前进方1 向 1 4 1 1 5 1 1 1 6 1 7 1 。具体实现时从一个初始交点出发，跟踪求出曲面交线上的一系列交 点。跟踪法可以求出高精度的交线。但是，该类方法强烈依赖于初始交点的位置。 如果有交线中存在小环、或奇点、曲面自交时，则算法的鲁棒性难以保证。 目前的求交方法还不能彻底解决应用中所碰到的求交问题，因此很多研究者 仍致力于这方面的研究。 近年来，随着三维表面扫描技术的发展和计算机几何造型复杂度的提高，基 于点的造型与绘制技术，在计算机图形学领域内受到研究者越来越多的关注 【1 8 1 9 2 0 2 1 ，形成了图形学的一个新的分支基于点的图形学( p o i n t - b a s e d g r a p h i c s ) 。在近年的s i g g r a p h 大会和e u r o g r a p h 大会上，均开设了以基于 点的图形学为主题的讲座 2 2 2 3 】。基于点的图形学以离散的采样点元( s u r f e l ) 作 为绘制和造型的基本元素。与传统的基于面的表示与处理方法相比，基于点的表 示方法可以表示更为丰富的几何细节，同时不需保存和维护复杂的拓扑信息，非 常利于进行灵活的多分辨率采样、并行计算，因此它能充分利用目前最新的图形 硬件( c p t o ，实现高质量的实时绘制。 我们认为，基于点的造型技术的出现，给参数曲面的离散求交技术提供了新 的思路。 1 2 本文的工作 本文在前人提出的离散求交方法基础上。结合近年来基于点元表示在图形学 上的发展情况，充分利用基于点的造型技术拓扑简单和易于多分辨率采样的优 势，提出了一种新的基于点元的参数曲面离散求交方法，来解决一般光滑参数曲 7 浙江大学硕士学位论文 面的求交问题。传统的参数曲面离散求交方法，在实现过程中使用平面片来逼近 曲面，可能会导致丢失或增加一些交线的细节特征，并且在不同分辨率下需要处 理裂缝情况。而本文通过自适应地将曲面离散采样为点模型，用离散的点元来替 代这些平面片，从而将曲面的求交问题转化为点模型的求交问题。算法根据我们 给定的精度来调节参数区域采样的范围以及采样点元的采样密度和点元半径，有 效地避免了曲面片之间的复杂拓扑关系。与以往的参数曲面求交方法相比，本算 法更简单高效，实验结果表明，本文算法稳定可靠，误差可控，而且可以达到交 互速度。针对算法切点可能存在区域，我们把上述算法进行了扩展，对相切的情 况进行了检测和处理。 1 3 论文的组织 本文中第二章详细地介绍了经典的参数魄面求交算法和基于点的造型技术； 第三章介绍了基于点模型的曲面求交算法，并对算法进行误差估计，最后给出了 程序实现结果；第四章针对第三章提出的算法的缺点和不足进行了分析，并针对 曲面近似相切时的特殊情况，对第三章的算法进行扩展和补充；第五章最后总结 全文并指出进一步的研究方向。 浙江大学硕士学位论文 第二章相关工作介绍 本章将介绍曲面的参数表示以及几种经典的曲面求交方法，并简单介绍基于 点的图形学的一些情况。 2 1 参数曲面求交算法介绍 2 1 1 曲面的参数表示 曲面的参数表示： 设在空间中 2 4 1 建立了直角坐标系q 。，x ( u ，v ) ，y v ) ，z 帆v ) 是定义在( u ，v ) 平面 的区域d 上的函数，x = x ( u ，v ) ，严y ( u v ) ，萨x ( u , v x ( u ，v ) d ) 称为s 的参数表示或 参数方程。也可以写成向量方程f _ f ( u v 产( x ( u v ) y ( u v ) ，z ( u v ) ) 。 曲面参数： ( u ，v ) 称为s 的曲面坐标或参数。 光滑的参数曲面： 参数曲面具有连续的关于各变量的一阶偏导数，则当( m ，v ) d 时点 ( x ( u ，v ) ，y ( u ，v ) z ( u ，v ) ) 构成的集s ，就是空间中的一个光滑曲面。 了解曲面的表示形式及其参数，下面我们来看求交的基本问题和前人在参数 曲面的求交问题上一些经典的解决方法。 2 2 求交问题概述 2 2 1 求交的基本问题 在几何造型中，求交的基本问题是如何有效地发现和描述高精度解的所有特 征 5 1 1 6 】。算法是否能够有效地应用在几何造型系统中决定了算法的可靠性，这 是对算法的一个基本的要求。算法的可靠性通常与解的特征密切相关，如收缩( 在 9 浙江大学硕士学位论文 奇异点或其附近) 、小环等情形。 求交问题可以根据问题的维数和所定义的方程来进行分类，所求得的解也会 随着输入表达式和算法结果的数字表示类型不同而不同。曲面与曲面求交问题的 解有可能是空集，也有可能是包含曲线( 可能由几段组成) 、曲面片、或者一个点。 目前，由于有限精度计算所引入的数值误差，大部分实用系统的求交结果变得非 常复杂。 图l 所示为一个较复杂的交线结果f ( u ，v ) = o ，其中包括从边界到边界的各种 分支、环和奇异点等。图中边界点( b o r d e rp o i n t s ) 指的是曲线f ( u ，v ) = 0 与参数 空间 0 ，1 2 四条边界的交点，例如f ( 0 ，v ) = 0 ，( 0 v 1 ) ；拐点( t u r n i n gp o i n t s ) ： u 一拐点( u t u r n i n g ) 是指曲线f ( u ，v ) = o 上切向平行于u = o 轴的点，它满足方程 f = f v = o ( f u o ) ；v 一拐点是指曲线f ( u ，v ) = o 上切向平行于v = o 轴的点，它满足方程 f = f u = o ( f v o ) 。奇异点( s i n g u l a rp o i n t s ) ：曲线上同时满足三个方程f = f u = f v = o 的点称作奇异点。交线环( 1 0 0 p ) ：交线为一个环。 由于计算机辅助几何设计中大多数曲线曲面是用多项式或有理多项式来表 示的，它们的交就是这些多项式或有理多项式方程组的解集，因此求交属于非线 性问题，随着计算机的出现和应用，大大推动了求交算法的发展。下面我们对它 们进行讨论说明。 2 2 2 参数曲面经典求交算法 目前，参数曲面之间的求交的典型算法主要有三类：网格法( l a t t i c em e t h o d ) 、 离散剖分法( s u b d i v i s i o na l g o r i t h i n ) 和跟踪法( m a r c h i n ga l g o r i t h l n ) 【l 】。 网格法网格法的核心思想是降低曲面求交问题的维数。该方法计算曲面上 一系列等参数曲线与另一个曲面上一系列等参数曲线的交点，然后将这些离散交 点连接起来f 8 】。对于参数曲面片之间的求交问题，该方法就简化为求解大量独 立的非线性方程组。在网格法中，维数的降低与初始网格分辨率的选取密切相关。 如果网格太粗，很可能会丢掉解的一些重要特征，如较小的环、孤立点等，而这 些特征表明曲面相切或者近似相切。此外，还有可能导致曲线交点的错误连接。 1 0 浙江大学硕士学位论文 。 舯 、 l一 、一，一 “留= f “ 琴 一 f _ f u _ |- u t m u l r , i l _ l f - f v = o 图i 相交得到的代数曲线只珥订= 0 ( ( 珥订为其所对应的参数空间) 1 7 。罗“ 。圳，多1 “，夕7 j p 0 i i 。一瓦- 叫 f 图2 代数曲线在点( u ，v ) 附近的变化形式图3 跟踪方法中的步长问题 离散削分法剖分法的主要思想是将求交问题递归地分解为更为简单的相 似问题，直至将问题简化到可以直接求解的程度( 如平面与平面求交【5 】) ，然后 将各个独立解连接起来形成完整解。简单的剖分法采用均匀剖分，这样可以得到 均匀四叉树数据结构。剖分法的优点是不需要起始点，在这一点上比跟踪法有优 势( 跟踪法我们稍后介绍) 。在自适应求交方法中，非均匀剖分允许用户有选择的 细化。剖分法用于求解的缺点在于：在奇异点和奇异点附近，不能保证交点的正 浙江大学硕士学位论文 确连接，而且在逼近解中，可能会丢失一些小环( 在用多边形逼近曲面时) ，或者 产生一些额外的环；而且剖分法在求解高精度的曲面交线时，会使数据量急剧增 加，求解变得很慢；由于用平面片逼近陷面，可能会导致丢失或增加一些交线的 细节特征。大部分c a d 系统应用中要求有高精度结果，所以单纯的剖分法是不实 用的。但是，自适应剖分法并结合恰当的局部技术可以得到较高的精度，这是计 算特征点的最实用方法。这些特征点可以通过跟踪法来跟踪所有的交线。 跟踪法主要是根据局部微分几何性质得到交线上的指定方向【1 1 】【1 2 】，然 后按照该方向从交线上一点前进到下一点，得到一个交线分支上的一系列点。但 是，跟踪法就其本身来说是不完整的方法，因为它需要知道所有解分支的起始点。 为了确定交线的所有连通分量，需要交线上一组重要的点( 特征点) 对给出定义。 这组重要的点可能是位于交线上的边界点、拐点和奇异点。跟踪法要求知道每一 个连通交线段上至少一个起始点，而且需要知道所有奇异点。给定代数曲线每一 个分支上的一个点根据曲线的微分性质跟踪曲线。这个方法的思想是求得关于 曲线以地订= o 的增量如和西，使其满足f ( u + 8 u ，v + o r ) = o 。对曲线尺地订进 行泰勒展开【1 】得： f ( u + 8 u ，v + 8 0 = f ( ”，v ) + e 占“十e 占v + ：1 ( f 0 占“2 + 2 f 抑j u j v + f , j v 2 ) + 二 当e 和昂不全为零或者坪+ 砰 o 时，为了使只qv ) = 0 和f ( u + 6 u ，v + b y ) = 0 满 足一阶逼近，可得：e 翮+ 只却；0 f 或者# v l = 一鲁8 u ，v 其中假设只o 。但是如图2 所示，占v ，可能导致点0 远离曲线只u 订= o 。此时， 可以采用具有初始逼近v ，= v + 占的牛顿法计算占n 从而获得较高精度的解。 为了使跟踪法能够正确地工作，必须事先给出所有分支的起点。步长的选择 也是复杂的，在很小的地方，太大的步长可能会导致跟踪偏离或循环，如图3 所 示，此时有必要缩短步长，使得算法可以拓扑可靠地跟踪曲线。 除此之外，曲面求交方法还有跟踪法与离散法相结合的混和方法 2 5 2 6 】 2 7 、代数法f 2 8 】【2 9 】【3 0 】等。代数法是根据交线的隐式表示，进一步用牛顿迭代 浙江大学硕士学位论文 法得到交线的数值解。众所周知，参数曲面的隐式化本身就是一个十分困难的问 题，而且隐式化过程容易引入数值误差。 2 3 基于点的造型技术 2 3 1 点元的基本概念 点元( s u r f e l ) ： 一个带形状因子与光照属性的0 维一元组( az e r od i m e n s i o n a ln - t u p l e ) ，用来 局部近似物体表面【2 0 】。这里需要指出的是，点元比纯粹几何意义上的点包含了 更多的信息，其中包括采样点的位置茁、采样点的法向行、采样区域的半径，以 及可选的颜色、纹理、材质等表面信息。 基于点的绘制： 利用计算机绘制基于点表示实体的技术。 点云( p o i n tc l o u d ) ： 密集三维点集，或称为密集离散点集。 基于点的造型： 基于点云的几何表面或实体表示、处理及编辑技术。 2 3 2 基于点的造型技术的发展背景和发展历史 近年来，以点作为造型与绘制的基本元素的方法，在计算机图形学领域内受 到研究者越来越多的关注【1 8 】【1 9 】【2 0 】【2 1 】。 随着计算机技术的应用与发展，人们对计算机造型与绘制技术的要求不断提 高，计算机模拟场景的规模越来越大，景物的细节也越来越丰富。特别随着三维 数码扫描仪的大规模普及与应用，由于扫描获取的几何体的细节以及外形的日渐 丰富，对有效生成、处理超大规模几何模型的新方法的需求也臼渐增长。而传统 的基于几何面片的场景造型需要大量的多边形来描述场景细节，利用传统的造型 浙江大学硕士学位论文 方法和造型软件在计算机内造型的工作量巨大，已经难于适用于新的应用场台。 为解决这一问题，基于点的造型和绘制技术被广泛地研究并取得了一系列重要进 展。 很早就有研究工作把点作为基本图形元素，但它在很长一段时间内并不受重 视。早在1 9 7 4 年，c a t m u l l 3 1 1 就注意到任何几何剖分最终都将显示为一个个离 散点。1 9 9 2 年s z e l i s k i 与t o r m e s o n 3 2 改进了粒子系统，使用有向粒子系统进行 模型的表面造型以及交互编辑。这种有向粒子被他们首先命名为 s u r f e l s 。直到 1 9 9 8 1 9 9 9 年，美国斯坦福大学l e v o y 带领的一个3 0 人研究小组对意大利文艺 复兴时代的著名雕刻家米开朗基罗的雕塑作品进行了细致的三维扫描，并在 2 0 0 0 年的s i g g r a p h 大会上，对这个项目进行了详细的介绍 3 3 】，面向这些点 数据设计了一个点绘制的算法和系统f 1 9 】。而在同一个s i g g r a p h 2 0 0 0 大会上， h p f i s t e r 等【2 0 】同时提出了基于s u f f e l s 的点绘制系统。由于这两项工作中所体现 出的对高度复杂几何模型的造型能力和优异的绘制效率，这几年来，基于点的造 型和绘制技术引起了研究者的广泛重视。我们下厦简单回顾下这几年来基于点 的造型技术的进展。 点模型的表示是基于点的造型技术的基础。很多研究者研究了点和曲面的混 合式表示技术。a l e x a 等f 3 4 】使用移动最小二乘法( m l s ) 逼近点模型表面的点云得 到局部逼近的多项式曲面，并以此定义光滑的二维流形表面来表示点云。m l s 曲面还可被用来进行加密采样以及简化采样。o h t a k e 等人【3 5 】提出了一种隐式曲 面和分段二次函数联合的点模型表面光顺曲面逼近技术。s h a c h a rf l e i s h m a n 等 给出了改进的m l s 描述【3 6 】。点模型的参数化技术将使离散的点集变得有序， 从而能高效地实现点模型编辑变形技术及纹理映射技术。f l o a t e r 等f 3 7 于2 0 0 1 年提出了无网格参数化技术。三维扫描所得大规模点云数据的后续几何处理算法 是点造型中的一个重要问题。目前越来越多的点模型是三维扫描仪所获得的。在 实际应用中，三维扫描仪得到的原始点云数据往往噪声较大，需要去噪、光顺、 补洞和扫描片对齐【3 8 】。还有些研究者关注点模型的变形技术。p a u l y 等【3 9 】利用 m l s 曲面逼近来辅助实现了点模型的自由变形。m u l l e r 等 4 0 】提出了一个基于物 理的点模型体变形技术，x i a o 等 4 1 1 提出了点模型的m o r p h i n g 技术。另外些 重要的研究工作聚焦于点模型的通用造型技术和系统。p a u l y 等提出了点模型上 1 4 浙江大学硕士学位论文 的的频谱处理算法 4 2 】。m z w i e k e r 实现了一个通用的点模型造型编辑软件 p o i n t s h o p3 d 【4 3 】，可以实现点模型上的雕刻等多种操作。特别要说明的是，该 软件为开源软件，研究者可以方便地在上面添加功能，该软件的发布进一步推进 了实用点造型系统。在2 0 0 3 年s i g g r a p h 会议上，a d a m s 和d u t r 6 实现了基于 s u r f e l s 表示实体的交互式布尔运算 1 8 】。最近，k o b b e l t 等基于点的造型和绘制 技术给出了一个好的综述【4 4 】，s i g g r a p h 和e u r o g r a p h i c s 大会更是开设了 精彩的专题讲座 2 2 】 2 3 】。 在下面我们将介绍一下点元处理的基本过程。 2 3 3 基于点的造型技术的基本流程 基于点的造型分成三个主要阶段：获取、前期去噪处理和后期几何处理。 获取：点模型的主要来源为3 d 扫描仪生成的原始数据，包括深度相机生成 的深度图( r a n g ei m a g e ) 与激光三维扫描仪或者接触式机械探头等设备得到的大 量三维空间点位置。三维点云再配合光学照片可以得到带颜色或纹理色彩的三维 实物模型。点模型的另外一个来源是现存的几何模型。所有几何模型均能方便地 转化成点模型，不同的采样精度能得到不同分辨率的点模型。 前期去噪处理：扫描得到的原始数据具有噪声、拼接错位、空洞、不确定性 和过度采样的问题，需要经过前期处理才能使用。前期处理的目标是从原始点云 中构造出一个连续的可用的表面模型。如果点模型是从良好的几何模型转换来 的，这一步可以跳过。 后期几何处理：在前期处理的结果上再作进一步的造型处理如重采样、磨光、 多分辨率简化、编辑、变形、布尔运算等操作，从而得到各种各样的点模型。对 点模型的数字几何处理也在后期处理阶段进行，其目标是在点模型的流形表面领 域内拓展基本的信号处理概念。 浙江大学硕士学位论文 第三章参数曲面点元离散求交法 近年来广泛采用的参数曲面离散求交方法，大多采用m e s h 来离散逼近参数 曲面。本章我们将采取一种新的思路，基于点来进行参数曲面离散求交。算法充 分发挥了基于点的造型技术的优势，拓扑结构维护简单。算法可以方便高效的进 行多分辨率自适应重采样，运算快速稳定。 本章将系统介绍我们的基于点的参数曲面离散求交方法。 3 1 算法求交流程 对于要求交的两个参数曲面，我们首先对参数曲面包围盒进行包围盒测试， 如果它们的包围盒不相交，那么这两个曲面无交点，否则，我们对它们进行初始 的点采样。对于满足凸包性的参数曲面，为了简单起见，我们可以近似使用参数 曲面控制顶点的包围盒作为参数曲面包围盒。 对通过测试的参数曲面包围盒，我们将进行如下步骤： 窃粥喃死j 购我们先对两个曲面分别进行均匀的初始点元采样，这样用 点元来代替这两个要求交的参数曲厦，就把醢面与曲面求交的问题转化成了点元 与点元之间是否相交的问题，这样有效地避免了曲面片之间的复杂拓扑关系。这 里要说明的一点是这里取的采样点元是需要满足一定条件的，它们带有半径，在 空间中可以当作圆盘来看待，其半径需进行计算，并非随机选取，具体算法到 3 1 1 节中初始点元采样中将详细介绍。 删( 霸蜕移罄当接着我们对这些初始的采样点元分别建立其空间八叉树 层次结构。对这些初始采样点元，算法计算出其平行于坐标平面的长方体包围盒， 以此作为空间八叉树的根结点。然后我们对之进行均匀的八叉树剖分，建立空间 层次结构。 【砭嘣篇戎必如果两八叉树结点包围盒不交，则这两个八叉树结点包 含的子曲面片无交。如果八叉树包围盒相交则递归测试其各自所属八叉树子结 点，直至当前结点均为叶结点为止。此时需考虑八叉树结点内的点元间求交测试。 1 6 浙江大学硕士学位论文 算法把其中最大点元半径作为误差的参考，具体方法我们在3 4 节中交点的误差 估计里有详细说明和解释。如果误差达不到所需要的结果，则必须进行下一步流 程：加密点采样。如果误差能满足求交精度要求。则对结点内的点元进行求交， 求交算法在3 1 _ 3 节中详细介绍。 勿藏点采襻：用3 1 2 节点元重采样的方法进一步有选择地进行点元加密重 采样，并剔除那些不可能相交的点元。 别【，咒娥剩下的点元都是经过我们筛选的，我们再把这些点元进行进 一步的八叉树细分，以加速这些点元间的求交。如果点元的半径还达不到精度的 要求，则进一步加密重采样，按3 1 2 中算法重新计算点元，点元的半径，一直 到满足精度要求为止。这是一个自适应的过程。由于用来求交的曲面是给定的， 区域有限，它在空间中的坐标位置及其曲率、法向等特征也是确定的，所以只要 这个自适应重采样的过程一直继续下去，采样点元不断加密，采样点元半径持续 减小，总能得到满足精度要求的点元采样，我们再把这些点元来进行求交。在实 验过程中，我们也可以根据以往的实验经验和所要求的精度，来有效地控制八叉 树剖分的层数和初始采样点元的个数。 炙符糟凹：对这些通过包围盒筛选所剩下点元进行求交，也就是把点元看 成三维空间中的圆盘，先考虑圆盘所在的平面，把它们所在的平面进行求交，求 得相应的交点后再进行判断，判断交点是不是位于点元的圆盘内，如果不满足， 则舍弃，如果满足，则将所求得的点元的交点作为我们要求的曲面的交点，详细 过程如3 1 3 交点的获取所述，在这个过程后，剩下最后一步：交点的排序。 芟荫街黼算法按3 2 节交点的排序算法进行排序，最终得到有序的求 交结果。 算法的主要求交过程流程图如下： 1 7 浙江大学硕士学位论文 囤广 巫巫圃垭甄虱 ll r 上一 眄磊 卜也塑丑一求絮l i 最终结果| 一交点捧序1 _ 一4 盖0 “l 下面我们讨论算法的细节。 3 1 1 初始点元采样 首先根据参数曲面参数方程中地v 参数的变化范围来进行初始的点元采样。 本文中采用的点元采样包含有中心点、采样半径和法向等信息，在空间中可以作 为圆盘看待。 假设g ( 坼为我们要进行求交的曲面方程之一，我们先按一定的分辨率在 g ( m v ) 所对应的参数域旭v ) 上均匀采样点元，一般情况下参数u 和v 所对应的数 值范围为0 到1 之闻。根据参数地v 所计算出来g ( 虬v ) 的值即是要求的采样点元 的中心点的坐标。 对曲面g ( m v ) 上任意点p ，在曲面g ( 珥v ) 上经过p 点的任意一条曲线在该点 的切向量称为曲面g ( 珥v ) 在p 的切向量【2 4 】。所以瓯( 材，v ) 和q ( ”，v ) 都是曲面 g ( v ) 的切向量。在三维空间中经过p 点，并且由曲面g ( m v ) 在p 点的切空间张 成的平面称为曲面g ( m 在点p 的切平面，这个切平面的单位法向量为 n = 茬襄妻耥，经过点p 并以n 为方向向量的直线称为曲面g v ) 在点 p 的法线，取瓴( “，q ( ”，v ) 方向为法向量时，认为取的是曲面g ( m v ) 的正向， 反之则为负向 2 4 】。为了计算方便，我们通常将法向单位化。 现在我们来计算中心点的采样半径。我们要求点元所代表的圆盘填满整个曲 1 8 面。点元半径的选取：点元g ( u o , v o ) 的半径，为与其相邻三个点的最大距离的 压2 倍。对于所求交的曲面根据精度来剖分，剖分后生成的小曲面片可以近似 地看成平面，那么对于覆盖在这个平面上的点元的半径的选取，我们可以用一个 图来进行表示，如图5 ，其中吐，如，以为这几个相邻点之间的距离： f 吐= i g ( u o + “，v o ) 一g ( u o ，v o ) l 吐= 1 g ( + a u ，v o + a v ) 一g ( ，v 0 ) i i 以- - i g ( u o ，+ a v ) - g ( u o ，v o ) i 我们把西，如，d 3 中的最大值找出来，即是m a x ( d , ，畋，喝) ，并假想以m a x ( d , ，吐，以) 为边长，以该点元中心点作为一个顶点组成一个正方形，这个正方形的对角线长 为压m a x ( d , ，也，以) ，我们只须取对角线长的一半作为要求的点元半径，就能达到 点样点的圆盘填满整个曲面的要求，所求点元半径r = x 2 2 m a x ( 4 ，吐砖) 。 为了保证各点元所代表的局部区域间无裂缝，以避免错误地遗漏交点，在如 下情况中在相邻两个采样点中增加点。如图6 ，相邻两个采样点元a ( g ( u o ，v 0 ) ) 、 b ( g ( u o + a u ，v o + a v ) ) 其法向分别为r i o 、n l ，且 i a = ( g ( u o + 巩+ v ) 一g ( v 。) ) ” 【段= ( g ( u o ，v o ) 一6 x u o + a u ，v o + v ) ) 码 p i p 2 0 ，则表明采样点元g ( u o ，v o ) 、g ( u o + a u ，v o + a v ) l 拘法向与它们的中心点 的连线段所成的角一个为钝角一个为锐角，这种情况表明这两个采样点元中间有 空隙，在求交的时候，有可能另一个曲面的点元恰好从这个空隙中穿过，如果不 采取措旆，就会导致交点丢失，发生错误，所以这时我们在这两个采样点元中间 增加一个采样点元c ( g ( u o + a u 2 ，v o + a v 2 ) ) ，这样就可以有效地防止上述情况的发 生。如果这个采样点元的自身的法向1 2 和它相邻的点元的法向满足p 。p ：0 ， 就取h 2 ，否则用新的法向n 2 。( g ( u o + a u 2 ，v o + a v 2 ) - g ( u o + a u 2 ，v o + a v 2 ) ) n o 作为 点g ( u o + a u 2 ，v o + a v 2 ) 的法向，这样做的目的是确保新增加的采样点元所在的平 面与原来那两个采样点元所在的平面相交，确保局部小曲面片被这三个点元完全 遮住。 有了初始的点元采样，对每一个参数曲面，我们建立其采样点的空间八叉树 结构，对每一参数曲面的采样点集合进行递归的空问分类。目前我们在实验中初 1 9 浙江大学硕士学位论文 始剖分层次的经验值取为4 层。 3 1 2 点元重采样和白适应细分八叉树的建立 算法利用八叉树的层次空间结构来加速求交测试。对于包围盒不相交的上层 结点，可以直接跳过；对于相交的八叉树包围盒。我们则对这两个八叉树结点的 每个子结点进步进行求交测试。如此下去，直到八叉树的叶结点。 假如两个曲面空间八叉树中非空的叶结点包围盒相交，我们必须对这两个叶 结点内所含点元作进一步的相交测试。对相交的八叉树叶结点中的各点元，我们 将它们当作空间中的小球来看待，比较它们中心点的距离与其半径和，这时，如 果两曲面上一对点元其中心点之间的距离小于两点元半径之和，则表明两曲面在 该点元附近的局部区域内可能存在交点，根据我们在节3 , 4 交点的误差估计中的 分析，精度与采样密度密切相关，所以为了提高精度，我们需要在这个区域附近 增加点元，根据这两个点元的( s t ) ，( u ，v ) 的值进行加密采样。 以n u r b s 曲面为例，如图7 ，r 毋f ) 及g d 是两个相交的n u r b s 曲面，交 点p 分别对应f ( s , 0 和g ( m v ) 方程中不同的参数( 毋，t ) 和( ”，v ，) 。设两个点元为 钗( ；j ( ，v o 强耳只而，f 0 ) ) ，如图8 ，我们在与a ( 用实心圆点表示) 相邻的点中间增加 8 个点： 鸽( g 一血2 一a v 2 ) ) ，4 ( g ( 一a u 2 ，v 0 ”，4 ( g ( 一缸2 ，v o + 舢2 ) ) ，4 ( g ，v o + v ，2 ) ) ， 4 ( g ( + a u 2 ，+ p 2 ) ) 4 ( g + a u 2 ，) ) ，4 ( g ( + 甜2 ，v o a v l 2 ) ) , 4 够( ，v o a v l 2 d 然后根据节3 1 1 中点元半径的计算方法重新计算上述点元的半径。同样地，也 在点元f ( ，岛) 相邻的点中间增加8 个点，加密准则同节3 1 1 一样。我们将 g ( u 。，吒) f ( s o ，t o ) 连同各自加密采样后新增的采样点分别存入两曲面的相交点元 候选表中。并在它们之间建立双向指针，然后我们删除两曲面八叉树叶结点中未 通过初始相交测试的所有点元。重采样后如果某个叶结点的点元数量超过一定 值，在我们的实验中通常取2 0 。则再自适应细分加密八叉树空间结构。 浙江大学硕士学位论文 图5 点元半径的选择示意图 图7 加密采样区域示意图，小矩形r j ，r 2 为 加密采样区域 3 1 3 交点的获取 v 0 v 2 图6 采样点加密示意图 一， 、以：； ，取。= - 2 ，把这个最近点作为下一个起点， 做标记后，继续搜索该起点的最近点，否则，选取离初始起点第二邻近的点，再 比较其切矢。如此递归，把搜索到的点顺次连成线。然后我们再类似从该叶结点 浙江大学硕士学位论文 中的初始起点沿反方向进行跟踪。把两部分跟踪点连接在一起，即得到我们所求 的交线段。跟踪完第一段交线后，我们在同一个叶结点中再检测是否还有未作标 记的点存在，如果存在，重复第一步，继续跟踪出另一段交线。 对每段交线，我们找出与其两个端点在空间中最为邻近的八叉树叶结点，分 别沿交线正向或负向继续下一步跟踪。 如图l o ，当跟踪到的点元满足排序条件，但已经标记，可以判断有交线环存 在，然后根据跟踪记录把这个环上的点顺次连结起来。 在上述局部跟踪过程结束后，我们需要在整个八叉树叶结点中寻找尚未标记 的交点，开始新一轮跟踪。如果所有交点都已经标记过，则跟踪结束。 3 3 参数曲面和点模型曲面的求交 由于在求交过程中，我们实际上把参数曲面离散成了点元模型，因此我们的 算法可以直接推广到参数曲面和通过扫描所得到的点模型曲面的求交上，它们具 有同样的离散形式，其交线可以根据求交曲面所对应的参数的连续性和求出的交 点的坐标关系来进行排序并绘制出来。 图1 2 ( h ) ( i ) 给出了b u d d h a 模型和d r a g o n 模型与曲面的求交效果图。 3 4 交点的误差估计 如图1 1 ，a ( g ( u o ，v o ) ) ，b ( g ( u o + z d 2 ，v o + z l v 2 ) ) ( 用蓝色线条表示的) 为曲面g ( u ，v ) 上的点元，e , d ( 用紫色线条表示的) 为曲面l 吖s , o 上的点元，根据我们的算法， 我们求得点元a d 的交点e ，点元b , e 的交点f ，把它们作为两个曲面的交点，点元 b 在点元a 法向上的投影距离为占( 由箭头标出) ，口为点元a 的法向吃与点元b 的法向n b 所成的角，从图中可以看出，e 和f 与实际交点o 的距离不会大于点元 a 中心点到点元b 中心点的距离，即为e s i n o ，( 口= a r c c o s ( n 唯) ) ，同样地，也不会 大于点元c 中心点到点元d 中心点的距离。根据我们假定的曲面的光滑性，由 t a y l o r 展开式， 浙江大学硕士学位论文 g ( u o + a u , + v )