Bézier曲线的细分技术毕业论文外文翻译(39页).doc

《Bézier曲线的细分技术毕业论文外文翻译(39页).doc》由会员分享，可在线阅读，更多相关《Bézier曲线的细分技术毕业论文外文翻译(39页).doc（39页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-Bzier曲线的细分技术毕业论文外文翻译-第 39 页杭州电子科技大学毕业设计（论文）外文文献翻译毕业设计（论文）题目Bzier曲线的细分技术翻译（1）题目Bzier曲线的交集的完整细分算法翻译（2）题目轮廓平滑算法基于Bzier曲线的应用学 院计算机学院专 业计算机科学与技术姓 名郭佳远班 级09052314学 号09051412指导教师余正生 译文一： Bzier曲线的交集的完整细分算法Chee K. Yap SCG 06 Proceedings of the twenty-second annual symposium on Computational geometry Pages 2

2、17 - 226 Chee K. Yap摘要：我们给第一个完整的细分算法可能与切线相交的两个Bzier曲线F，G，交叉点。我们强大的细分方法算法是基于几何分离的界限，它们使用同一个标准的，用于检测非交叉交点曲线。我们的算法是自适应的，仅根据精确的长浮点数计算。特别是，我们避免操纵代数数字和合成计算。它被设计成与现有的算法竞争哪个是“好”的选择。所有的标准算法假定F，G是互质的 - 我们的算法需要推广这一点。关键词：计算几何，曲线相交，Bzier曲线,，细分方法，有效的数值算法，精确的几何计算。1 介绍 代数曲线和曲面的交叉分析在许多几何模型领域是一个根本性的问题16。最实用的算法是基于自由曲面

3、的曲线和曲面8，6。在本文中，我们考虑一类自由曲线，Bzier曲线。目前所有的交叉贝塞尔曲线算法是不准确的，主要的就是不稳定的问题。让我们看看一个根本原因。 一条曲线F是一个有限的曲线段，代表序列P（F）=（P0，.，PM）的控制点8,6。让CH（F）表示P（F）中，作为观察的凸包封闭区域。一对（F，G）贝塞尔曲线被称为候选对CH（F）CH（G）的非空。标准贝塞尔曲线相交算法是基于两个曲线的想法。首先，使用属性，包含一条曲线F在CH(F)，该算法可以丢弃非候选对。其次，算法的操作主要是细分，曲线F分割成两个代替曲线F0，F1采用De Casteljau的算法。通用交叉算法候选对维护一个队列Q。

4、只要Q为非空，从Q中提取候选人对（F，G）。如果FG的直径小于，则输出该对；否则它细分曲线具有较大的直径，来讨论F，把他分成代替曲线F0，F1，并在Q上附加（F0，G）和（F1，G）。该算法依赖于一个常数 0：（F，G）对的直径小于被视为相交。为显示的目的，这样的常量是合理的。但对于拓扑分析的曲线的安排，我们希望输出（F，G）对代表的独特交集。但通用的算法，输出一对（F，G）没有交集，或有多个交点。让p是F和G的一个交点。在标准假设，F，G有没有共同的组件，然后，p是FG的一个孤立的点。在P点的交集可以是切向或横向。这取决于F和G在p点的切线是否或重合。另外，我们可以根据曲线是否彼此交叉的在p

5、或没有，把P作为一个交叉或不相交叉的交点；这相当于交叉点p的重数是奇数还是偶数。不相交的交点，必须相切的，横向交叉点必须是横切的。因此我们有3个可能性，如图1所示。 （a）横向的（交叉） （b）切向的（交叉） (C) 切线(不相交) 图1：交点：（a）横向（b）切向（c）切线 可以避免使用吗？这似乎也合情合理，如果F和G只有交叉的交点，那么我们可以设计一个不使用任何来限制基于细分交叉算法。这不是显而易见，但它是隐含了本文交集算法。在任何情况下，关键的问题是如何检测非交叉的交点。最近，沃伯特23，22，解决了非奇异代数曲线的问题。这类曲线，她的地址和本文中提到的那些不具有直接可比性，虽然Bzie

6、r曲线是比较特殊的代数曲线，它们可以是单数（参见图5）。她介绍广义Jacobi曲线的技术来检测不相交非奇异的曲线的交点。她还使用细分的空间，以避免操纵代数数字（不同于传统方法的基础上圆柱分解）。但她的做法仍然使用有效的代数工具，如生成物和根隔离。这样代数技术在其他部分的算法是花费很大的和减少的有效性的适应性的。一个最近的一篇论文中，Seidel和沃伯特20地址计算平面代数曲线的拓扑安排的；再次，细分和代数方法相结合的被使用。相比之下，我们使用仅有的代数的信息是代数的零界。否则，我们使用长浮点数和原始的几何操作进行纯数字计算，如计算凸壳并相交的用一条线的曲线。这不是明显的先验我们可以只用这样的操

7、作实现我们精确的曲线相交的目标。比如，一个在沃伯特 - 赛德尔设定中是不知道纯粹的自适应/数值版本。前的细分算法采用各种用于检测的交点的标准。这些部分都是典型的标准：要么拒绝标准，确认非交叉或验收标准，确认交点。一个完整的标准是，既接受和排斥的标准。上面的泛型算法仅使用凸壳准则。由于这是一个拒绝的标准，通用的算法也从来没有肯定的交点。Sederberg和Meyers19根据矢端曲线肯定存在的横向交叉点给出了验收标准。但是没有任何已知的验收不交叉的交点的标准，我们将在第3节提供一个。在一般情况下，部分的标准是有数字滤波器组成的概念几何模拟5。部分标准作为一个启发式的快速拒绝/接受是非常有用的。但

8、最终，一个正确的算法必须使用一些完整的标准或其他一些全球保证其完整性。我们的方法概述。1。最根本的动机这项工作是为Bzier交点设计一个确切的细分算法。细分意味着适应性。形成鲜明对比的方法,结合代数用数值的方法22、23、20，我们是“完全自适应”。2。我们介绍的是主要的分析工具几何分离的范围内。他们回答这样的问题：如果它们不相交，什么是最接近的两个曲线段之间的距离？或如果q是不在曲线上的之间的最近距离是什么点q和曲线？这些界限，表示为功能度和高度的的相关多项式和代数数，表示通过各种在本文中。请参阅第2和第7。3。发展提供停止准则数值模拟和细分的程序。的边界很容易该算法开始时计算。的逻辑中算法

9、是无视这些值。因此，如果提高边界是可预见的未来，他们可以直接掺入而不改变算法逻辑。4。适应性是指这些界限仅在最坏的情况下被调用。“好的输入”，一个迭代终止很久以前绑定的迭代是到达。这种提前终止依赖于半标准（即，滤波器）用于确定相交或不相交。为简单起见，我们描述我们的算法只使用凸船体过滤器（第1节）。虽然过滤器没有被强调在本文中，它们会影响我们的基本设计算法。我们预计，大多数过滤器可以很容易地注册成立到我们的算法有轻微的变化。5。第3条规定的第一个完整的检测标准非交叉路口（NIC）的基本贝塞尔曲线。由一个“基本曲线”，我们指的是一个曲线图凸部或凹函数。6。我们的算法使用各种数值和几何近似的子程序

10、。两个关键的子程序交叉的初等贝塞尔曲线用直线（第4部分）和用于评估的“函数”的迹象（第5部分）。7。界需要小心应用程序（它不只是一个问题的取代一些开往通用交叉算法）。同样地，该应用程序的不相交的交点标准（NIC）需要准备：在第6章中，我们描述了耦合过程中创建申请NIC的必要前提。8。非基本贝塞尔曲线呢？一般的贝塞尔曲线的临界点，基本的曲线没有关键点。有一般方法，打破了代数曲线的关键点（例如，14）。这些涉及代数，非自适应的方法，我们希望避免的。相反，第7显示了如何细分与分离边界可以检测和隔离等关键点。第8提出了整体的交叉算法。9。我们所有的数值计算，最终降低环操作（+， - ，）（二进制）长浮

11、点数，即理性号码的形式N2M其中n和mZ，这些操作进行准确。为了提高效率，我们不操纵代数甚至是一般合理的数字。我们也不会操纵多项式或执行在当前子结式的计算，如被发现确切的交集算法。10。要强调长浮点数在我们的表达法中的作用，它介绍了以下术语是非常有用的。首先，定义的“标准参数化”点，线和贝塞尔曲线如下：一个点p的坐标由下式给出P =（X，Y），一条线L它是由给定系数的方程AX + BY + C确定，一条贝塞尔曲线是由给出的控制点（依次给出的坐标）确定。当这样的标准长浮点数参数X，Y，A，B，C等，我们称他们为直接对象，否则他们是间接对象。例如，相交的“直通线”和“直接曲线”F产生的坐标是代数数

12、点P *。因此P*间接对象。然后，我们必须提供的替代方法通过直接代表（近似）间接物体对象。我们在直接对象的上面使用“表达式”。例如，如果p是L和F的唯一的交集，我们可能会用“点L，F”表示p*。因此，L，F作为P *的非标准参数的直接对象。这表示可以精确如下：使用De Casteljau的算法的通用算法，把曲线F细分为两个代替曲线（F0，F1）。检查L和F0是否相交（第4节），如果是这样，精致的表示是点L，F0，否则它是点L，F1。这个过程可以重复，当每次我们经常想得到越来越近似的P*。 间接对象的近似计算与一定迭代，通过适当的停止条件发展。举例说明，假设我们希望测试是否P*=点L，F坐落在一

13、个标准的贝塞尔曲线G上。假设我们可以计算一定范围内 0，如果p*不在G上，那么它的距离G至少是（第2部分）。然后，我们细化点L，F如上文所述，直到直径（F）/ 2。接下来，我们多次使用De Casteljau的算法细分G得到代替曲线（j=0，1，.）。当是空集时，我们丢弃；当直径 0，我们说F，G分离的属性，如果对所有p=q，如果（p，q）是（F，G）正相反对，或者如果p，qFG，那么。上述定理给我们一个明确的绑定为。重要的是要注意，本取决于仅在初始输入曲线F，G;随后细分的F，G不改变。3 初等曲线本节介绍的基本曲线的概念。的主要结果是一个完整的标准非过交集基本的曲线。设f是有界的，连续可微

14、的函数定义在区间c，dc 0，那么F和G是不相交的。在接下来的三个部分中,我们将展示如何应用在一个交点应用NIC算法。4 交叉点与线与一条贝塞尔曲线F相交的特殊情况直线l处理在标准教科书8。现在，我们给出一个完整的情况下，F是基本的算法。当F代表了其控制多边形P(F) =(p0, . . . , pm),然后它有贝塞尔曲线参数化和虽然默认的曲线是F = F0，1，我们也可以指定一个任意的间隔I = c, d定义曲线FI = Fc, d。使用符号“I ()”如果一个间隔I分为两个子区间（除非另有说明，否则承担二分I说明）。同样,我们写“”意味着F = FI在被细分为。我们的输出线相交算法是一组（

15、l,），每个（i0）都是原始曲线F的代替曲线并且有一个独特的交点。相对简单的算法，省略在该扩展抽象的。我们注意到，在这个特殊的情况下，我们在没有调用NIC的情况下可以检测使用几何分离边界的独立的切线交点。这条线相交算法中使用的一般算法的几个中的子程序。正下方超越算法的用处：这是一种形式的“射线拍摄”中使用的以下的连接过程。至于qv，让射线（q，v）表示射线原始点在q并且通过v。在输入（F，q，v），其中F是最基本的，这个测试会产生三个输出之一：通过，如果q F；在上方，如果射线（q，v）与F相交，但是qF；在下方，其他情况。我们首先计算线F与通过q，v线的交点。如果没有交点，我们得到在下方。另

16、外，我们多次细分F并且如果CH（）包涵q就用代替F。我们终止当q CH() CH(),或者直径（F）(定理3)。在终止，如果q在CH()CH()外，我们可以很容易地确定在下方或者在上方；否则我们得到通过，因为（F） 0.让l和F相交于点F（）。我们想确定的符号角，其中是l的倾斜角。我们认为该（t）的符号是等于S（t）：=c的符号。从式（2），我们可以为S（）开发一个下界：如果控制多边形的F具有m +1个点L-位浮点的坐标，和假设c,d,e,f是L-位浮点数，那么意味着。现在，我们可以自适应地通过近似和估计误差进行计算的符号。查看完整的纸张了解详细信息。6 连接过程 在本节中，假设F，G是满足形

17、分离特性的初等贝塞尔曲线，并且使得FG的直径小于。这意味着，| FG|1。我们的目标是，以确定它们是否相交。如果他们相交，相切，我们最终必须至少是含蓄地减少他们NIC，。此过程被称为连接的过程。通过研究的动力，注意，要应用NIC，必须细分F，G直到我们看到一个基本的连接（），其中 F， G。这似乎一般很难达到。相反，我们建议扩展NIC来处理“半连接”。让F = F0, 1是一个A-初级，G就是前面提到的G。即，垂直条带内的S（F）有界通过F（0）和F（1）的垂直线，G就是上述F。假设我们发现一个 半正态分布 aF（t）与G相较于一个特殊的点。如果是G到U（F0，t）的限制，那么我们把（F0,t

18、,）叫做半连接；我们同样可以定义另一个半连接（Ft,1，）。注意，是间接的贝塞尔曲线。原来我们可以为半连接改编NIC（定理7）。概括地说，连接过程有三个步骤：1.我们检测是否F和G穿越交叉点。这是很容易减少到最多四个下方超越测试。如果有是交点，我们正在处理。因此任何假定。都有对称性，我们可以假设F = F0,1是A-初级，G是上述F。2.使用二进制搜索找到一个t0，1这样aF（t）相交G。这不是很难解决的轻微复杂的情况下假设aF（t）相交G于两个点。在任何情况下，我们已经减少了两个半连接的搜索。3.应用下面的半连接NIC。这三种情况图4中可见的半连接。定理8.（半连接NIC）。假设(F0, 1

19、, Gc, d)是一个半连接aF（0）通过G（c）并且aF（1）不与G相交。此外，终点G（d）在U（F）上，F是上文中的F。让表示G（d）低一半标准。定义是角度的向上正常在G（d）作出与正x-轴（如前）。我们有三种可能性：（1） 相交。（2） 相交。（3） 在点F(t)相交。在这种情况下，让。然后我们拥有：（4） 图4.半连接：（1）相交。（2）相交。（3）在点F(t)相交7 关键点我们现在解决非基本Bzier曲线这个问题。贝塞尔曲线F 0，1可以细分为有限多个初级代替曲线。点F（t）在该细分发生的“临界点”。图5（1）表示三次Bzier一个临界点。图5 单一三次Bzier曲线：（1）控制多边

20、形（2）矢端曲线 让是F = F0, 1的坐标函数，即，F（t）=（ ），然后让表示相对于t的衍生工具。把t (0, 1) 称为一个临界值，F（t）是一个临界点，如果满足下列条件之一（参见Kim和Lee14）： （1）F（t）是固定值，即，； （2）F（t）是x极限值，即，； (3) F(t)是一个拐点，即，0，在。引理9.如果F其相对内部没有关键点，那么F是基本的。相反，如果F是基本的，那么它没有X-极值或拐点在其相对内部。临界值是代数数字。因此，我们不建议细分Bzier曲线的基本部件细分的关键点。相反，我们将细分Bzier曲线在长浮点数以使所得代替曲线是初级或包含在最关键点。把正好包含一个

21、临界点基本曲线叫做临界曲线。现在，我们呼吁更多的分离由一个单一的数字总结的边界*0进行说明。在本节的其余部分，假设控制多边形F，G是P(F)=（），P(G)=()。此外，坐标是L位长浮点数。首先，我们约束的程度和规范关键点：引理10.（1） 如果F（t）=（ ）是一个固定或x极值，那么有角度m-1，2-标准最多。（2） 如果F(t)是一个拐点，那么F（t）有角度最多（）。这给我们：推论11.设p，q是F的两个不同的关键点。如果那么| p.x - q.x|或| p.y - q.y|有一个比大。接下来，我们推广定理3为了处理p是任何代数点：定理12.设q=（q.x，q.y），在那里q.x，q.y是

22、代数2-范数c和角度d。让多项式A（X，Y）有2-范数a和m角度。如果曲线A（X，Y）= 0不包含一个圆圈集中在q点那么q到A=0的距离最少 其中的让6=（m，n，L）是曲线G和F中一个关键点p的之间的最小距离，假设。这限制来自定理12中的引理10。最后，选择在（定理1），所述（定理2），和中范围是最低的。如果直径，我们可以称F为微曲线。这是众所周知的，相对于t的导数是由下式给出这里我们定义。并且让表示（）。因此，我们看到，mP（F）是曲线的控制多边形，称为速度图F。因此，F包含一个固定的点，当且仅当通过其原点。例如，图5（2）的P（F）是为图5（1）立方Bzier曲线的给出的；在这种情况下我

23、们可以检查速度面通过的原点。定理13 （固定点）。 让直径（F）。然后F包含一个固定的点当且仅当凸包逼近 P（F）中包含的原点（0，0）。定理14（x极端点）。让直径（F）。然后F包含X极端点当且仅当和。如果p，q，r是平面点，让行列式（p，q，r）是33矩阵的决定因素它的行是，其中的。同样也让行列式（p，q）表示p.xq.y-p.yq.x。定理15（拐点）。让直径（F）。然后F包含了一个拐点，当且仅当行列式（）（） 0。前面的三个定理给我们的完整条件检查，如果一个微型的曲线是一个基本的临界曲线。8 交叉点算法 我们现在目前全球任意两个Bzier曲线相交算法。我们设计的算法，以便自然是通用的交

24、叉算法（参见导言）嵌入式的第一阶段，我们的算法。简单而不是实际的效率是下列目的描述。我们有两个工作队列。每个队列只是候选对的列表。如果直径CH(F)CH(G)比小，一个候选对（F，G）被称为一个微对；否则这是一个宏观的对。称为宏观队列和微队列，因为它们分别含有宏对和微型双。明显的初始化后，该算法分为两个阶段：宏阶段 ：这基本上是第1节上操作通用交点的算法。关键的区别是分拆后一对（F，G）在（，G）（i = 0，1）中，如果（，G）是一个候选对，我们根据它是否是一个宏观或微观对，把它变成。如果我们没有其他的东西还是宏观段，我们仍然是正确的。但在实践中，我们执行各种有效的部分标准（例如，测试横向交

25、点）。是空的的时候，这个阶段结束。微观段： 现在，我们为每对（F，G）提取：我们检查，如果F包含一个关键点（第7章）。如果是这样，我们就可以对输出。否则，我们采用的连接过程（第6章）。 备注。宏观相是“标准”，易于实现。微相对待退化和可能情况。宏观相结束时，微队列预计为“很好的”输入是小的或空的。8. 开放性问题 本文开辟了可能性，实现全面的自适应算法与其他计算的正确性保证涉及的曲线和曲面的问题。这个新的方向在本质上依赖于使用的几何分离边界。最明显的问题是开放的，所以我们只列出的近期论文有关的几个问题：我们的F，G交叉算法有这样的双极性假设：F，G有有限多正相反对。如前所述，它概括了标准的假设

26、，F，G是互质。显然，如果F是一个G的偏移量，反之亦然，正相反假设将失败。我们推测它是相反的东西。Sungwoo Choi已经证明了这个猜想。Choi的定理意味着，当双极性假设失败的时候它是一个分离的属性持有者。因此,对映假设并不是必不可少的。 不幸的是，我们不知道如何约束没有正相反的假设。 给我们的算法的复杂度分析，或一些的变型。在一般情况下，细分的算法的复杂性似乎知之甚少。 像我们这样实现一个自适应算法，比较非健壮的细分算法或代数算法。 提高我们的分离范围。 我们已经有所改善利用的事实是贝塞尔曲线的边界，这些都为简洁起见省略。 提供一个简单的算法的情况下，只有横向的交叉点。鸣谢特别感谢My

27、ung-Soo Kim教授在首尔国立大学的热情款待。在与Myung-Soo Kim, Gershon Elber, Joon-Kyung Seong 和 Iddo Hanniel的讨论中我们受益匪浅。王文平教授指出，有必要区分切向交叉和切向非交叉的情况。9. 参考文献1 D. S. Arnon and S. McCullum. A polynomial-time algorithm for the topological type of a real algebraic curve. J. of Symbolic Computation, 5:213236, 1988.2 C. Bajaj a

28、nd M.-S. Kim. Algorithms for planar geometric models. In Proc. 15th Int. Colloq. Automata, Languages and Programming, pages 6781, 1988. Lecture Notes in Computer Science.3 S. Basu, R. Pollack, and M.-F. Roy. Algorithms in Real Algebraic Geometry. Algorithms and Computation in Mathematics. Springer,

29、2003.4 E. Berberich, A. Eigenwillig, M. Hemmer, S. Hert, K. Mehlhorn, and E. Schomer. A computational basis for conic arcs and boolean operations on conic polygons. In Proc. 10th European Symp. On Algorithms (ESA02), pages 174186. Springer, 2002. Lecture Notes in CS, No. 2461.5 H. Bronnimann, C. Bur

30、nikel, and S. Pion. Interval arithmetic yields efficient dynamic filters for computational geometry. Discrete Applied Mathematics, 109(1-2):2547, 2001.6 E. Cohen, R. Riesenfeld, and G. Elber. Geometric Modeling with Splines: An Introduction. A.K. Peters, Ltd, Wellesley, MA, 2001.7 G. Elber and M.-S.

31、 Kim. Geometric constraint solver using multivariate rational spline functions. In Proc. 6th ACM Symp. on Solid Modeling and Applications, pages 110. ACM Press, 2001.8 G. Farin. Curves and Surfaces for Computer Aided Geometric Design: A Practical Guide. Academic Press, Inc, second edition, 1990.9 R.

32、 T. Farouki. Numerical stability in geometric algorithms and representation. In D. C. Handscomb, editor, The Mathematics of Surfaces III, pages 83114. Clarendon Press, Oxford, 1989.10 N. Geismann, M. Hemmer, and E. Schomer. Computing a 3-dimensional cell in an arrangement of quadrics: Exactly and ac

33、tually! In Proc. 17th ACM Symp. on Comp. Geometry, pages 264273, 2001.11 L. Gonzalez-Vega and M. E. Kahoui. An improved upper complexity bound for the topology computation of a real algebraic plane curve. J. Complex., 12(4):527544, 1996.12 L. Gonzalez-Vega and I. Necula. Efficient topology determina

34、tion of implicitly defined algebraic plane curves. Comput. Aided Geom. Des., 19(9):719743, 2002.13 H. Hong. An efficient method for analyzing the topology of plane real algebraic curves. Mathematics and Computers in Simulation, 42:571582, 1996.14 M.-S. Kim and I.-K. Lee. Gaussian approximations of o

35、bjects bounded by algebraic curves. In Proc. 1990 IEEE Intl, Conf. on Robotics and Automation, pages 322326, 1990. May 1318, Cincinnati, U.S.A.15 B. Mourrain and J.-P. Pavone. Subdivision methods for solving polynomial equations. Technical Report 5658, INRIA, 2005.16 N. M. Patrikalakis and T. Maekaw

36、a. Shape Interrogation for Computer Aided Design and Manufacturing. Springer Verlag, Heidelberg, Germany, 2002.17 S. Plantinga and G. Vegter. Isotopic approximation of implicit curves and surfaces. In Proc. Eurographics Symposium on Geometry Processing, pages 245254, New York, 2004. ACM Press.18 T. Sakkalis. The topological configuration of a real algebraic curve. Bulletin of the Australian Math. Soc., 43:3750, 1991.19 T. W. Sederberg and R. J. Meye