发布时间 : 星期日 文章Bézier曲线的细分技术毕业论文外文翻译更新完毕开始阅读7c77118e10a6f524cdbf8536
杭州电子科技大学
毕业设计（论文）外文文献翻译
毕业设计（论文）题目
Bézier曲线的细分技术
翻译（1）题目 翻译（2）题目
学 院
Bézier曲线的交集的完整细分算法
轮廓平滑算法基于Bézier曲线的应用
计算机学院
专 业 计算机科学与技术
姓 名 郭佳远
班 级 09052314
学 号 09051412
指导教师 余正生
译文一：
Bézier曲线的交集的完整细分算法1
Chee K. Yap
摘要：我们给第一个完整的细分算法可能与切线相交的两个Bézier曲线F，G，交叉点。我们强大的细分方法算法是基于几何分离的界限，它们使用同一个标准的，用于检测非交叉交点曲线。我们的算法是自适应的，仅根据精确的长浮点数计算。特别是，我们避免操纵代数数字和合成计算。它被设计成与现有的算法竞争哪个是―好‖的选择。所有的标准算法假定F，G是互质的 - 我们的算法需要推广这一点。
关键词：计算几何，曲线相交，Bézier曲线,，细分方法，有效的数值算法，精确的几何计算。 1 介绍
代数曲线和曲面的交叉分析在许多几何模型领域是一个根本性的问题[16]。最实用的算法是基于自由曲面的曲线和曲面[8，6]。在本文中，我们考虑一类自由曲线，Bézier曲线。目前所有的交叉贝塞尔曲线算法是不准确的，主要的就是不稳定的问题。让我们看看一个根本原因。
一条曲线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。只要Q为非空，从Q中提取候选人对（F，G）。如果F∪G的直径小于ε，则输出该对；否则它细分曲线具有较大的直径，来讨论F，把他分成代替曲线F0，F1，并在Q上附加（F0，G）和（F1，G）。
该算法依赖于一个常数ε> 0：（F，G）对的直径小于ε被视为相交。为显示的目的，这样的常量是合理的。但对于拓扑分析的曲线的安排，我们希望输出（F，G）对代表的独特交集。但通用的算法，输出一对（F，G）没有交集，或有多个交点。
让p是F和G的一个交点。在标准假设，F，G有没有共同的组件，然后，p是F∩G的一个孤立的点。在P点的交集可以是切向或横向。这取决于F和G在p点的切线是否或重合。另外，我们可以根据曲线是否彼此交叉的在p或没有，把P作为一个交叉或不相交叉的交点；这相当于交叉点p的重数是奇数还是偶数。不相交的交点，必须相切的，横向交叉点必须是横切的。因此我们有3个可能性，如图1所示。
1
Chee K. Yap SCG 06 Proceedings of the twenty-second annual symposium on Computational
geometry Pages 217 - 226
（a）横向的（交叉） （b）切向的（交叉）
(C) 切线(不相交) 图1：交点：（a）横向（b）切向（c）切线
可以避免使用ε吗？这似乎也合情合理，如果F和G只有交叉的交点，那么我们可以设计一个不使用任何ε来限制基于细分交叉算法。这不是显而易见，但它是隐含了本文交集算法。在任何情况下，关键的问题是如何检测非交叉的交点。最近，沃伯特[23，22]，解决了非奇异代数曲线的问题。这类曲线，她的地址和本文中提到的那些不具有直接可比性，虽然Bézier曲线是比较特殊的代数曲线，它们可以是单数（参见图5）。她介绍广义Jacobi曲线的技术来检测不相交非奇异的曲线的交点。她还使用细分的空间，以避免操纵代数数字（不同于传统方法的基础上圆柱分解）。但她的做法仍然使用有效的代数工具，如生成物和根隔离。这样代数技术在其他部分的算法是花费很大的和减少的有效性的适应性的。一个最近的一篇论文中，Seidel和沃伯特[20]地址计算平面代数曲线的拓扑安排的；再次，细分和代数方法相结合的被使用。相比之下，我们使用仅有的代数的信息是代数的零界。否则，我们使用长浮点数和原始的几何操作进行纯数字计算，如计算凸壳并相交的用一条线的曲线。这不是明显的先验我们可以只用这样的操作实现我们精确的曲线相交的目标。比如，一个在沃伯特 - 赛德尔设定中是不知道纯粹的自适应/数值版本。
前的细分算法采用各种用于检测的交点的标准。这些部分都是典型的标准：要么拒绝标准，确认非交叉或验收标准，确认交点。一个完整的标准是，既接受和排斥的标准。上面的泛型算法仅使用凸壳准则。由于这是一个拒绝的标准，通用的算法也从来没有肯定的交点。Sederberg和Meyers[19]根据矢端曲线肯定存在的横向交叉点给出了验收标准。但是没有任何已知的验收不交叉的交点的标准，我们将在第3节提供一个。在一般情况下，部分的标准是有数字滤波器组成的概念几何模拟[5]。部分标
准作为一个启发式的快速拒绝/接受是非常有用的。但最终，一个正确的算法必须使用一些完整的标准或其他一些全球保证其完整性。
我们的方法概述。1。最根本的动机这项工作是为Bézier交点设计一个确切的细分算法。细分意味着适应性。形成鲜明对比的方法,结合代数用数值的方法[22、23、20]，我们是―完全自适应‖。
2。我们介绍的是主要的分析工具几何分离的范围内。他们回答这样的问题：如果它们不相交，什么是最接近的两个曲线段之间的距离？或如果q是不在曲线上的之间的最近距离是什么点q和曲线？这些界限，表示为功能度和高度的的相关多项式和代数数，表示通过各种Δ在本文中。请参阅第2和第7。
3。Δ发展提供停止准则数值模拟和细分的程序。的边界很容易该算法开始时计算。的逻辑中算法是无视这些Δ值。因此，如果提高Δ边界是可预见的未来，他们可以直接掺入而不改变算法逻辑。
4。适应性是指这些Δ界限仅在最坏的情况下被调用。―好的输入‖，一个迭代终止很久以前绑定的迭代是到达。这种提前终止依赖于半标准（即，滤波器）用于确定相交或不相交。为简单起见，我们描述我们的算法只使用凸船体过滤器（第1节）。虽然过滤器没有被强调在本文中，它们会影响我们的基本设计算法。我们预计，大多数过滤器可以很容易地注册成立到我们的算法有轻微的变化。
5。第3条规定的第一个完整的检测标准非交叉路口（NIC）的基本贝塞尔曲线。由一个―基本曲线‖，我们指的是一个曲线图凸部或凹函数。
6。我们的算法使用各种数值和几何近似的子程序。两个关键的子程序交叉的初等贝塞尔曲线用直线（第4部分）和用于评估的―α函数‖的迹象（第5部分）。
7。Δ界需要小心应用程序（它不只是一个问题的取代一些开往εΔ通用交叉算法）。同样地，该应用程序的不相交的交点标准（NIC）需要准备：在第6章中，我们描述了耦合过程中创建申请NIC的必要前提。
8。非基本贝塞尔曲线呢？一般的贝塞尔曲线的临界点，基本的曲线没有关键点。有一般方法，打破了代数曲线的关键点（例如，[14]）。这些涉及代数，非自适应的方法，我们希望避免的。相反，第7显示了如何细分与分离边界可以检测和隔离等关键点。第8提出了整体的交叉算法。
9。我们所有的数值计算，最终降低环操作（+， - ，×）（二进制）长浮点数，即理性号码的形式N2M其中n和m∈Z，这些操作进行准确。为了提高效率，我们不操纵代数甚至是一般合理的数字。我们也不会操纵多项式或执行在当前子结式的计算，如被发现确切的交集算法。
10。要强调长浮点数在我们的表达法中的作用，它介绍了以下术语是非常有用的。首先，定义的―标准参数化‖点，线和贝塞尔曲线如下：一个点p的坐标由下式给出P =（X，Y），一条线L它是由给定系数的方程AX + BY + C确定，一条贝塞尔曲线是