计算机图形学_第三篇-6(求交分类).ppt

清华大学计算机科学与技术系 计算机图形学基础 清华大学计算机科学与技术系 清华大学计算机科学与技术系 计算机图形学基础 3.3 求交分类清华大学 几何造型中，通常利用集合运算（并、交、差运算）实现复杂形体的构造。集合运算需要大量的求交运算。 如何提高求交的实用性、稳定性、速度、精度等，对几何造型系统至关重要。 清华大学计算机科学与技术系 计算机图形学基础 3.3.1 求交分类简介 多面体模型 这种模型的求交计算主要是线段和平面的求交，求交问题的解决相对简单。 多面体模型的缺点是明显的。它只能近似表示形体，同时，复杂形体表面的离散会带来巨大的数据量。 CSG模型 在这种模型中，形体通过基本体素的组合来实现。二次曲面的求交是这些造型系统中必不可少的。 清华大学计算机科学与技术系 计算机图形学基础 当前的几何造型系统，大多采用精确的边界表示模型。 在这种表示法中，形体的边界元素和某类几何元素相对应，它们可以是直线、圆（圆弧）、二次曲线、Bezier曲线、B样条曲线等，也可以是平面、球面、二次曲面、Bezier曲面、B样条曲面等，求交情况十分复杂。 二次曲面与各种自由曲面并存的混合表示模型的采用，导致了归类求交思想的产生。 清华大学计算机科学与技术系 计算机图形学基础 3.3.2 求交分类策略 在几何造型系统中，用到的几何元素主要有 点：3D点。 线：3D直线段、二次曲线(包括圆弧和整圆、椭圆弧和椭圆、抛物线段、双曲线段)、 Bezier曲线 (有理和非有理)、B样条曲线、NURBS曲线。 面：平面、二次曲面(包括球面、圆柱面、圆锥/台面、双曲面、抛物面、椭球面和椭圆柱面)、Bezier曲面 (有理和非有理)、B样条曲面、NURBS曲面。 清华大学计算机科学与技术系 计算机图形学基础 将几何元素进行归类，利用同一元素之间的共性来研究求交算法。同时对每一类元素，在具体求交算法中要考虑它们的特性，以提高算法的效率，发挥混合表示方法的优势。 求交方法可分为：点点、点线、点面、线线、线面六种。 清华大学计算机科学与技术系 计算机图形学基础 3.3.3 基本的求交算法 3.3.3.1 线与线的求交计算 二次曲线与二次曲线的求交。 求交策略是将坐标系变换到该圆锥曲线的局部坐标系下，一个圆锥曲线用隐式方程的形式表示，而另一圆锥曲线采用参数方程的形式，代入即可获得有关参数的四次方程，，因而可计算出二者的交点。 二次曲线与NURBS曲线求交 将NURBS曲线的参数方程代入圆锥曲线的隐式方程，得到参数的一元高次方程，然后，使用一元高次方程的求根方法解出交点参数。或把圆锥曲线也表示为参数形式，转化为两个NURBS曲线的求交问题。 清华大学计算机科学与技术系 计算机图形学基础 NURBS曲线与NURBS曲线求交。采用离散法求初始交点，迭代求精确解的办法，步骤如下： （1）初始化。依据离散精度，将NURBS曲线形成对应的二叉树表示，叶子结点是对应于该曲线的某一离散子线段及其包围盒，非叶子结点是对应于该段NURBS曲线的包围盒。 （2）求初始交点。遍历两曲线的二叉树，若其叶子结点的包围盒相交，则将两者的数据（曲线段中点的参数值，二者坐标的平均值）存入初始交点队列。 （3）将初始交点迭代求精确交点。迭代方程可形象地用图3.3.1表示。 清华大学计算机科学与技术系 计算机图形学基础 清华大学计算机科学与技术系 计算机图形学基础 3.3.3.2 线与面的求交计算 二次曲线与二次曲面的求交的求交计算，可以把二次曲线的参数形式代入二次曲面的隐式方程，计算出交点的参数。 NURBS曲线与二次曲面的求交计算，可以把NURBS曲线的参数形式代入二次曲面的隐式方程，得到关于参数的高次方程，然后求解。 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) 清华大学计算机科学与技术系 计算机图形学基础 可得到： 令 , 则可建立迭代方程： 设初值为，一般迭代3~5次，便可达到要