⭐ 欢迎来到虫虫下载站！ | 📦 资源下载 📁 资源专辑 ℹ️ 关于我们
⭐ 虫虫下载站
📤 上传资源

📄 2.8.5 曲面求交.htm

📁 计算机图形学教程计算机图形学教程
💻 HTM
字号:
🔍 
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0058)http://www.ekany.com/wdg98/cg/contents/chapter2/les285.htm -->
<HTML><HEAD><TITLE>2</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb2312">
<META content="MSHTML 6.00.2800.1106" name=GENERATOR></HEAD>
<BODY>
<P align=justify><B><FONT face=楷体_GB2312 size=4>2.8.5 曲面求交</FONT></B></P>
<P style="MARGIN: 1px 0px; TEXT-INDENT: 0px; LINE-HEIGHT: 200%" 
align=justify><FONT face=楷体_GB2312 
size=4>本小节讨论的内容包括线与曲面的交点的求法以及面与曲面的交线的求法。</FONT></P>
<P style="MARGIN: 1px 0px; TEXT-INDENT: 0px; LINE-HEIGHT: 200%" 
align=justify><FONT face=楷体_GB2312><FONT size=4>1、直线段与参数曲面的交点</FONT></FONT></P>
<P style="MARGIN: 1px 0px; TEXT-INDENT: 0px; LINE-HEIGHT: 200%" 
align=justify><FONT face=楷体_GB2312 size=4>&nbsp;&nbsp;&nbsp; 
作为例子，考虑直线段与三次参数曲面求交，假设直线方程与曲面方程分别是：</FONT></P>
<P style="MARGIN: 1px 0px; TEXT-INDENT: 0px; LINE-HEIGHT: 200%" 
align=justify><FONT face=楷体_GB2312><FONT 
size=4>　　　　　　　　</FONT>P(t)=A+Bt</FONT></P>
<P style="MARGIN: 1px 0px; TEXT-INDENT: 0px; LINE-HEIGHT: 200%" 
align=justify><FONT face=楷体_GB2312 size=4>与</FONT></P>
<P style="MARGIN: 1px 0px; TEXT-INDENT: 0px; LINE-HEIGHT: 200%" 
align=justify><FONT face=楷体_GB2312><FONT size=4>　　　　　　　　q(u, 
v)=Bezier曲面或B样条曲面或其它参数曲面</FONT></FONT></P>
<P style="MARGIN: 1px 0px; TEXT-INDENT: 0px; LINE-HEIGHT: 200%" 
align=justify><FONT face=楷体_GB2312 size=4>则在交点处有</FONT></P>
<P style="MARGIN: 1px 0px; TEXT-INDENT: 0px; LINE-HEIGHT: 200%" 
align=justify><FONT face=楷体_GB2312><FONT size=4>　　　　　　　　</FONT>q(u, v 
)-p(t)=0</FONT></P>
<P style="MARGIN: 1px 0px; TEXT-INDENT: 0px; LINE-HEIGHT: 200%" 
align=justify><FONT face=楷体_GB2312 size=4>这是个三元高次方程组，必须用数值方法求解。</FONT></P>
<P style="MARGIN: 1px 0px; TEXT-INDENT: 0px; LINE-HEIGHT: 200%" 
align=justify><FONT face=楷体_GB2312 
size=4>也可以把直线方程表示为两个平面交的形式，然后把曲面参数方程代入直线方程（两平面交的形式），再用牛顿迭代法求解。具体做法请查阅第九章光线跟踪算法中求射线与参数曲面求交的部分。</FONT></P>
<P style="MARGIN: 1px 0px; TEXT-INDENT: 0px; LINE-HEIGHT: 200%" 
align=justify><FONT face=楷体_GB2312><FONT size=4>2、参数曲线与面的交点</FONT></FONT></P>
<P style="MARGIN: 1px 0px; TEXT-INDENT: 0px; LINE-HEIGHT: 200%" 
align=justify><FONT face=楷体_GB2312><FONT size=4>&nbsp;&nbsp;&nbsp; 
参数曲线与平面</FONT>/<FONT 
size=4>二次曲面的求交计算比较简单，只要把曲线的参数形式代入面的方程得到参数的一元方程，用求根公式或高次方程的求根方法求解。</FONT></FONT></P>
<P style="MARGIN: 1px 0px; TEXT-INDENT: 0px; LINE-HEIGHT: 200%" 
align=justify><FONT face=楷体_GB2312><FONT 
size=4>考虑参数曲线与参数曲面求交的问题时，假设空间曲线表示为P(t)=(x(t), y(t), z(t))，曲面表示为Q(u, w)=(x(u, w), 
y(u, w), z(u, w))。则曲线与曲面的交可以表示为方程</FONT></FONT></P>
<P style="MARGIN: 1px 0px; TEXT-INDENT: 0px; LINE-HEIGHT: 200%" 
align=justify><FONT face=楷体_GB2312 size=4>P(t)-Q(u, w)=0</FONT></P>
<P style="MARGIN: 1px 0px; TEXT-INDENT: 0px; LINE-HEIGHT: 200%" 
align=justify><FONT face=楷体_GB2312><FONT size=4>令</FONT> <FONT size=4>r(t, u, 
w)=P(t)-Q(u, w)</FONT></FONT></P>
<P style="MARGIN: 1px 0px; TEXT-INDENT: 0px; LINE-HEIGHT: 200%" 
align=justify><FONT face=楷体_GB2312 size=4>则有　　<IMG height=41 
src="2.8.5 曲面求交.files/Image187.gif" width=273></FONT>4/P>
<P style="MARGIN: 1px 0px; TEXT-INDENT: 0px; LINE-HEIGHT: 200%" 
align=justify><FONT face=楷体_GB2312><FONT 
size=4>由此可建立迭代方程，用迭代法求解t,u,w。迭代初值的选取可以通过对曲线与曲面分别建立包围盒树，当曲线的包围盒树叶子与曲面的包围盒树叶子相交时，取两个叶子内的参数值作为t<SUB>0</SUB>, 
u<SUB>0</SUB>, w<SUB>0</SUB>，并作为初值开始迭代至满足收敛条件。</FONT></FONT></P>
<P style="MARGIN: 1px 0px; TEXT-INDENT: 0px; LINE-HEIGHT: 200%" 
align=justify><FONT face=楷体_GB2312><FONT size=4>3、参数曲面与其它曲面的交线</FONT></FONT></P>
<P style="MARGIN: 1px 0px; TEXT-INDENT: 0px; LINE-HEIGHT: 200%" 
align=justify><FONT face=楷体_GB2312><FONT size=4>&nbsp;&nbsp;&nbsp; 
进行参数曲面与二次曲面的求交时，可以把参数曲面的参数表示代入二次曲面的隐式方程得到参数的二元高次方程，按一定步距取其中一参数为常数，求解代数方程可得另一参数的对应值，如此求出交线上的一组离散点。更通常的办法是把二次曲面表示为有理参数曲面（如</FONT>NURBS<FONT 
size=4>曲面），转化为参数曲面之间的求交问题。参数曲面之间的求交有多种算法，比较典型的有离散法与跟踪法。</FONT></FONT></P>
<P style="MARGIN: 1px 0px; TEXT-INDENT: 0px; LINE-HEIGHT: 200%" 
align=justify><FONT face=楷体_GB2312 
size=4>用离散法进行参数曲面求交时，把欲求交的参数曲面离散成一些细小的三角面片。用这些三角面片进行求交计算，得到一些小线段，把这些小线段联接起来，作为交线的近似结果。这种方法实现比较容易，但精度较低，往往不能满足数控加工的要求。在两张曲面接近相切的情形，用三角面片代替曲面求交，往往会产生漏交线，产生不正确的交线分支情况等问题。</FONT></P>
<P style="MARGIN: 1px 0px; TEXT-INDENT: 0px; LINE-HEIGHT: 200%" 
align=justify><FONT face=楷体_GB2312><FONT 
size=4>跟踪法是Timmer在1977年提出的。用跟踪法求参数曲面间交线时，从已知的交点出发，沿该交点处交线的切线方向，按一定的步长，用数值方法计算下一交点，产生一组离散交点序列，构成交线的一个近似表示。再用直线段连接这些交点，产生一条（或一组）开的或闭的折线。其拓扑结构与实际交线的拓扑结构相同。跟踪法主要包含三个步骤：</FONT></FONT></P>
<OL>
  <LI>
  <P style="MARGIN: 1px 0px; TEXT-INDENT: 0px; LINE-HEIGHT: 200%"><FONT 
  face=楷体_GB2312 size=4>搜索（初始交点）；</FONT> </P>
  <LI>
  <P style="MARGIN: 1px 0px; TEXT-INDENT: 0px; LINE-HEIGHT: 200%"><FONT 
  face=楷体_GB2312 size=4>跟踪（计算后继交点），跟踪法即由此得名；</FONT> </P>
  <LI>
  <P style="MARGIN: 1px 0px; TEXT-INDENT: 0px; LINE-HEIGHT: 200%"><FONT 
  face=楷体_GB2312 size=4>排序（把求交所得的交点序列连接起来，形成与实际交线相同的拓扑结构）。</FONT> </P></LI></OL>
<BLOCKQUOTE>
  <P style="MARGIN: 1px 0px; TEXT-INDENT: 0px; LINE-HEIGHT: 200%" 
  align=justify><FONT face=楷体_GB2312 size=4>下面对这三个步骤进行讨论：</FONT></P></BLOCKQUOTE>
<P style="MARGIN: 1px 0px; TEXT-INDENT: 0px; LINE-HEIGHT: 200%"><FONT 
face=楷体_GB2312 
size=4>（1）<U>搜索</U>。本步骤的目标是寻找一组交点，作为下一步骤的初始交点。为了保证求得的交线具有与实际的交线相同的拓扑结构，在交线的每一个独立分支上，都必须有一个交点作为初始点，否则该分支在后继步骤中将被遗漏。搜索初始交点有多种方法，如果两张曲面的交线集不存在封闭环的话，可以使用一个曲面的边界线与另一张曲面求交，得到一组初始交点，用这一组初始交点就足够保证每条交线分支上至少有一个初始交点。如果交线集中有封闭环，可以用其他方法搜索初始交点。一种方法是用一张面上的等参网格曲线与另一曲面求交，求得一组交点，作为初始交点。另一种方法是把两张曲面都递归分割成四叉树结构，先把整张曲面分割成四张子曲面。如果子曲面片不满足某种平坦性要求，就把它再分割成四张更小的子曲面片。如此递归检测与分割，形成一棵四叉树。叶子结点对应的子曲面片都满足平坦性要求。并且每个结点都生成一个包围盒，包含该结点所代表的子曲面片。然后对两个包围盒树求交，若某个叶子结点与另一张曲面的包围盒树的某叶子结点有交，则把对应的各子曲面片的平均参数值作为近似参数值，对应曲面上的两点的中点作为近似交点坐标，然后用后面（跟踪步骤）介绍的迭代方法求出精确交点。确定曲面的平坦性时，对于一般的参数曲面，可以采用比较曲面四顶点中相邻两顶点的切向量的夹角、相邻两顶点的法向量的夹角以及顶点与参数域中心所对应的曲面法向量的夹角来判断。对于具有凸包性质的参数曲面如Bezier、B样条、NURBS等，可以用子曲面片的控制多面体的扁平程度作为平坦性条件。这可以通过检测各行（列）控制点与该行（列）首末控制点的连线的距离大小来判断。用这种方法计算量较小，且结果更可靠。</FONT></P>
<P style="MARGIN: 1px 0px; TEXT-INDENT: 0px; LINE-HEIGHT: 200%">　</P>
<P style="MARGIN: 1px 0px; TEXT-INDENT: 0px; LINE-HEIGHT: 200%" 
align=justify><FONT face=楷体_GB2312><FONT 
size=4>（2）<U>跟踪</U>。这个步骤从上一个步骤所求的每一个初始交点出发，沿该点处交线的切向量方向，计算下一个交点的近似点，然后用数值迭代方法，从该近似点求出精确交点。这个步骤主要包括三步：1）计算切向量（步向量）。2）计算步长。长度为步长的切向量称为步向量（step 
vector）。3）把近似交点迭代到精确交点。</FONT></FONT></P>
<P style="MARGIN: 1px 0px; TEXT-INDENT: 0px; LINE-HEIGHT: 200%" 
align=justify><FONT face=楷体_GB2312><FONT size=4>&nbsp;&nbsp;&nbsp; 
下面就其中的第一步和第二步作一讨论。步向量的方向可以采用两曲面在交点处的切平面的交线方向，即两切平面法向量的叉积。该方向即为交线在该点的切向量方向。当两张曲面在该点处的切平面不平行时，其法向量的叉积是确定的，从而步向量方向也可确定。然而，当曲面的切平面互相平行（或非常接近平行，在平行的容差范围内而被判为平行）时，可以采用回溯法：把前面已经求得的两交点的差作为步向量方向。如果前面已求到的交点没有两个，也就是说只有一个初始交点，就不可能使用回溯法。这时可以采用从初始交点向四周几个辐射方向以一个小步长? 
取n个取样点，作为猜测的步向量方向，直至找到一个新交点为止。从初始点到新交点的连线方向就作为新的步向量方向。求到步向量之后，还要进一步计算步长。简单的实现方法可以取用户指定的定数作为步长。更精确的方法要考虑曲面的局部特性，可以使用基于曲率和转角容差的自适应方法。</FONT></FONT></P>
<P style="MARGIN: 1px 0px; TEXT-INDENT: 0px; LINE-HEIGHT: 200%" 
align=justify>　</P>
<P style="MARGIN: 1px 0px; TEXT-INDENT: 0px; LINE-HEIGHT: 200%"><FONT 
face=楷体_GB2312><FONT 
size=4>（3）<U>排序</U>。这个步骤的工作是把前面所求得的交点正确地连接起来，形成与实际交线相同的拓扑结构。这个步骤的算法与搜索步骤的算法有关。如果搜索步骤采用等参网格线与另一曲面求交取得初始交点，那么，可以对应地把曲面的参数域等分成一些小方形域，跟踪步骤从一个初始交点到同一网格区域边界上的另一初始交点产生一些交点序列，每一序列代表交线的一个子段。排序的任务就是比较各子段的端点，把它们联结成完整的交线结构。对于采用四叉树结构计算初始交点的方法，可以由底向上收集交线，联结下层结点所得的交点序列，到达根结点时就确定了交线。</FONT></FONT></P>
<P>　</P>
<P><A href="http://www.ekany.com/wdg98/cg/contents/chapter2/les284.htm"><FONT 
face=楷体_GB2312>&lt;上一节〉</FONT></A><FONT face=楷体_GB2312>&nbsp;&nbsp;&nbsp; <A 
href="http://www.ekany.com/wdg98/cg/contents/chapter3/les311.htm">〈下一节〉</A> 
&nbsp;&nbsp;&nbsp; <A 
href="http://www.ekany.com/wdg98/cg/tutorial/chapter2/lesson2-8.htm">〈返回〉</A></FONT></P></BODY></HTML>

⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -