基于层次包围盒的bézier曲面求交算法分析与实现

《基于层次包围盒的bézier曲面求交算法分析与实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、大连理工大学硕士研究生学位论文大连理工大学学位论文版权使用授权书本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论文。作者签名拯邀亟一引币笨受．翌唬咀导师签名：二I”纽”，呼j堑年上月上日大连理工大学硕士学位论文1绪论1．1研究的背景和意义I．1．1研究的背景曲面求交研究属于CAGD／CAM(ComputerAidedGeometricDesig

2、n／Computer-AidedManufacture)的研究领域。是CAGD／cAM中一个基本但重要的问题。计算机辅助几何造型技术是计算机辅助几何设计(ComputerAidedDesign，简称CAGD)、计算机图形学(CG)、微分几何、CAD／CAM(ComputerAidedManufaelure)、程序设计等多门学科的交叉。计算机辅助几何造型是用计算机及其图形工具表示、描述物体形状、设计几何形体、模拟物体动态处理过程的一门综合技术。随着计算机图形学与计算几何(ComputationalGeometry)这两门学科的发展和相互渗透，70年代形成了--f]边缘学科计算机辅助几何设计，它

3、主要研究自由曲线曲面的表示、设计、造型、显示、分析和处理等问题，是几何造型方法的基础。它的主要内容有曲面造型、实体造型、曲面与实体的表示分析与应用。其理论和应用研究在最近几年已经取得了很大进展，从而促进了相关学科的理论与应用的发展。国外曲面求交的研究始于60年代，发表的论文专著非常丰富。South和Kelly使用网格法计算双三次曲面片等高线的方法进行求交。Sederberg和Owen等提出将参数方程转化为代数方程，并应用求解代数方程的方法进行求交。1980年，Lane和Riesenfeld首次提出了Bazier和均匀B样条曲线曲面的分割求交方法【lJ，接着Cohen，Lyche等又提出了非均

4、匀B样条曲线曲面分割求交的OSLO算法【2l。Dokkcn等人则利用B6zier等曲面所具有的离散分割性，利用小平面片逼近的方法纯几何的处理曲面的交线13】。Sabin和Bamhill等人提出根据交线的代数几何性质采取迭代和追踪相结合的方法沿着交线走向去寻找下一个交点，从而得到所有的交线的追踪法14,5】。M．AzizandRedaBata研究了基于B6zier／B6zier曲面求交的分割法和追踪法[61。由于使用单一的方法无法适应复杂情况的求交，Koparkar等人提出结合多种方法去解决曲面的求交问题17一。国内自70年代以来，由于开发几何造型及数控加工系统的要求，对曲面求交问题也进行了大

5、量的研究。北京航空航天大学在70年代完成了用代数法及对分法进行曲面求交的软件包【9】o彭群生利用离散分割的思想解决的B样条曲面的求交【Ⅲ。汪国昭、张定华提出了适／羽7：Bazier面求交的离散分割层次的确定方法[II,12]。但今年来国内外在曲面求交领域研究的较少，其中比较有代表性的方法为：Mullen基于层次包围盒的Bdzicr曲面算法的研究及实现heinG．提出了一种有效的方法来求取追踪法的初始点【131。Grandiue，ThomasA用拓扑优化来优化交线【141。Mlll'ioFioravanfi对有理曲面的求交进行研究旧。陈丽萍、姜歌东、王小椿、许晓革等提出的基于Bdzicr曲面分

6、割求交的快速跟踪求交算法【16·m。浙江大学曾阳艳的参数曲面点元离散求交算法【‘引。李学艺，陈松，王小椿将曲面间最小距离应用在曲面求交中【l91。关履泰，途峰，杨朝霞的利用投影的方法求曲面相交算法【20】。是一种改进的跟踪求交算法。1．1．2研究的意义曲面求交具有重要的理论意义。曲面求交(SSlsurface／surfaceintersection)是CAGD／CAM领域中的最为重要也最为复杂的问题之一。自由曲面求交一直是个活跃的课题，但至今还没有有效的求交方法，因为自由曲面一般为双三次参数曲面，不可能用纯数学方法求其交线，而用非数学方法或非纯数学方法又存在精度和效率问题，因此，准确、稳定、

7、快速地解决复杂曲面的求交问题一直是相关研究领域的前沿课题。而且，自由曲面求交被广泛的用于曲面裁剪、数控加工刀位轨迹计算及其实体造型拼合的各种运算中。求交算法是上述各种算法的基础算法，所以求交算法具有广泛的应用价值【2”，在如下几个方面对它几乎是必不可少的：(1)曲面造型(SurfaceModeling)在各种几何处理技术中(如剪裁、过渡等)均须以曲面求交操作为基础。曲面的剪裁边界由两相交曲面的交线及有关边界界