《3.3 求交分类PPT》由会员分享，可在线阅读，更多相关《3.3 求交分类PPT（20页珍藏版）》请在金锄头文库上搜索。
1、清华大学计算机科学与技术系 计算机图形学基础,3.3 求交分类,几何造型中，通常利用集合运算（并、交、差运算）实现复杂形体的构造。集合运算需要大量的求交运算。 如何提高求交的实用性、稳定性、速度、精度等，对几何造型系统至关重要。,清华大学计算机科学与技术系 计算机图形学基础,3.3.1 求交分类简介,多面体模型 这种模型的求交计算主要是线段和平面的求交，求交问题的解决相对简单。 多面体模型的缺点是明显的。它只能近似表示形体，同时，复杂形体表面的离散会带来巨大的数据量。 CSG模型 在这种模型中，形体通过基本体素的组合来实现。二次曲面的求交是这些造型系统中必不可少的。,清华大学计算机科学与技术系
2、 计算机图形学基础,当前的几何造型系统，大多采用精确的边界表示模型。 在这种表示法中，形体的边界元素和某类几何元素相对应，它们可以是直线、圆（圆弧）、二次曲线、Bezier曲线、B样条曲线等，也可以是平面、球面、二次曲面、Bezier曲面、B样条曲面等，求交情况十分复杂。 二次曲面与各种自由曲面并存的混合表示模型的采用，导致了归类求交思想的产生。,清华大学计算机科学与技术系 计算机图形学基础,3.3.2 求交分类策略,在几何造型系统中，用到的几何元素主要有 点：3D点。 线：3D直线段、二次曲线(包括圆弧和整圆、椭圆弧和椭圆、抛物线段、双曲线段)、 Bezier曲线 (有理和非有理)、B样条曲
3、线、NURBS曲线。 面：平面、二次曲面(包括球面、圆柱面、圆锥/台面、双曲面、抛物面、椭球面和椭圆柱面)、Bezier曲面 (有理和非有理)、B样条曲面、NURBS曲面。,清华大学计算机科学与技术系 计算机图形学基础,将几何元素进行归类，利用同一元素之间的共性来研究求交算法。同时对每一类元素，在具体求交算法中要考虑它们的特性，以提高算法的效率，发挥混合表示方法的优势。 求交方法可分为：点点、点线、点面、线线、线面六种。,清华大学计算机科学与技术系 计算机图形学基础,3.3.3 基本的求交算法,3.3.3.1 线与线的求交计算 二次曲线与二次曲线的求交。 求交策略是将坐标系变换到该圆锥曲线的局
4、部坐标系下，一个圆锥曲线用隐式方程的形式表示，而另一圆锥曲线采用参数方程的形式，代入即可获得有关参数的四次方程，因而可计算出二者的交点。 二次曲线与NURBS曲线求交 将NURBS曲线的参数方程代入圆锥曲线的隐式方程，得到参数的一元高次方程，然后，使用一元高次方程的求根方法解出交点参数。或把圆锥曲线也表示为参数形式，转化为两个NURBS曲线的求交问题。,清华大学计算机科学与技术系 计算机图形学基础,NURBS曲线与NURBS曲线求交。采用离散法求初始交点，迭代求精确解的办法，步骤如下： （1）初始化。依据离散精度，将NURBS曲线形成对应的二叉树表示，叶子结点是对应于该曲线的某一离散子线段及其
5、包围盒，非叶子结点是对应于该段NURBS曲线的包围盒。 （2）求初始交点。遍历两曲线的二叉树，若其叶子结点的包围盒相交，则将两者的数据（曲线段中点的参数值，二者坐标的平均值）存入初始交点队列。 （3）将初始交点迭代求精确交点。迭代方程可形象地用图3.3.1表示。,清华大学计算机科学与技术系 计算机图形学基础,清华大学计算机科学与技术系 计算机图形学基础,3.3.3.2 线与面的求交计算,二次曲线与二次曲面的求交的求交计算，可以把二次曲线的参数形式代入二次曲面的隐式方程，计算出交点的参数。 NURBS曲线与二次曲面的求交计算，可以把NURBS曲线的参数形式代入二次曲面的隐式方程，得到关于参数的高
6、次方程，然后求解。 NURBS曲线与NURBS曲面的求交计算 1初始化。依据离散精度，将NURBS曲线离散成二叉树的形式,清华大学计算机科学与技术系 计算机图形学基础,2求初始交点。遍历该二叉树和四叉树，如果曲线二叉树叶子结点的包围盒与曲面四叉树的叶子结点的包围盒有交点，则将子曲线段中点的参数值、子曲面片的中心点的坐标值与参数值作为初始交点，记录到初始交点点列中去。 3对初始交点进行迭代，形成精确交点。可用牛顿迭代法求解精确交点。设NURBS曲线为C(t)，NURBS曲面为S(u,v)，则在交点处应满足： C(t)-S(u,v)=0 设 f(u,v,t)=C(t)-S(u,v),清华大学计算机
7、科学与技术系 计算机图形学基础,可得到： 令 , 则可建立迭代方程： 设初值为，一般迭代35次，便可达到要求的精度。,清华大学计算机科学与技术系 计算机图形学基础,3.3.3.3曲面与曲面的求交,曲面与曲面之间的求交是最为复杂的一种 曲面与曲面求交的基本方法主要有: 代数方法 几何方法 离散方法 跟踪方法,清华大学计算机科学与技术系 计算机图形学基础,1代数方法 利用代数运算，特别是求解代数方程的方法求出曲面的交线。 根据参与求交的两曲面的表示形式的不同，可以把求交分为三种情况。 隐式表示和参数表示的曲面求交，通过把参数方程代入隐式方程的方法，可以将交线表示为g(u,v)=0的形式。此时得到的
8、交线方程是平面代数曲线方程，可根据平面代数曲线理论的方法求解交线。,清华大学计算机科学与技术系 计算机图形学基础,两个曲面都是参数表示的情形，只需要将其中之一隐式化，然后用前面的方法求解。而参数多项式或有理多项式曲面的隐式化通过消元来实现。 两个曲面都是隐式曲面。一种方法是将其中一个曲面参数化，然后用第一种情况来求解。但是，一般情况下这种参数化很困难，对于某些情况可以采用另外的方法计算参数化的曲面。 代数法的弱点是对误差很敏感 这是因为代数法经常需要判别某些量是否大于零、等于零或小于零，而在计算机中的浮点数近似表示的误差常常会使这种判别出现错误。,清华大学计算机科学与技术系 计算机图形学基础,
9、2几何方法 利用几何的方法，对参与求交的曲面的形状大小、相互位置以及方向等进行计算和判断，识别出交线的形状和类型，从而可精确求出交线。 几何求交适应性不是很广，一般仅用于平面以及二次曲面等简单曲面的求交,清华大学计算机科学与技术系 计算机图形学基础,对于一些交线退化或相切的情形，交线往往是点、直线或圆锥曲线，用几何方法求交可以更加迅速和可靠。,清华大学计算机科学与技术系 计算机图形学基础,3离散方法 离散方法求交是利用分割的方法，将曲面不断离散成较小的曲面片，直到每一子曲面片均可用比较简单的面片，然后用这些简单面片求交得一系列交线段，连接这些交线段即得到精确交线的近似结果。 离散求交一般包括下
10、面的过程：用包围盒作分离性检查排除无交区域；根据平坦性检查判断是否终止离散过程；连接求出的交线段作为求交结果。,清华大学计算机科学与技术系 计算机图形学基础,由于Bezier曲面，B样条曲面具有离散性质，使得它们最适合于离散法求交。 缺点： 离散法求出的交线逼近精度不高。如果要求的精度较高，需要增加离散层数。这将大大增加了数据储存量和计算量。 处于不同离散层数的相邻子曲面片，由它们产生的交线段可能会出现裂缝。,清华大学计算机科学与技术系 计算机图形学基础,4跟踪方法 通过先求出初始交点，然后从已知的初始交点出发，相继跟踪计算出下一交点，从而求出整条交线的方法。 跟踪法的本质是构造交线满足的微分方程组，先求出满足方程组的某个某个初值解，通过数值求解微分方程组的方法来计算整个交线。 跟踪方法在计算相继交点的时候，利用了曲面的局部微分性质，一般采用数值迭代的方法求解，使得计算效率较高。,清华大学计算机科学与技术系 计算机图形学基础,跟踪法求交中考虑的主要问题包括： 如何求出初始交点并保证每一交线分支都有初始交点被求出； 如何计算奇异情况下的跟踪方向以及合理选取跟踪的前进步长； 如何处理相切的情况。,
