《bézier曲线的细分技术毕业(设计)论文外文翻译》由会员分享，可在线阅读，更多相关《bézier曲线的细分技术毕业(设计)论文外文翻译（47页珍藏版）》请在金锄头文库上搜索。
1、杭州电子科技大学毕业设计（论文）外文文献翻译毕业设计（论文）题目Bzier曲线的细分技术翻译（1）题目Bzier曲线的交集的完整细分算法翻译（2）题目轮廓平滑算法基于Bzier曲线的应用学 院计算机学院专 业计算机科学与技术姓 名郭佳远班 级09052314学 号09051412指导教师余正生 译文一： Bzier曲线的交集的完整细分算法Chee K. Yap SCG 06 Proceedings of the twenty-second annual symposium on Computational geometry Pages 217 - 226 Chee K. Yap摘要：我们给第一
2、个完整的细分算法可能与切线相交的两个Bzier曲线F，G，交叉点。我们强大的细分方法算法是基于几何分离的界限，它们使用同一个标准的，用于检测非交叉交点曲线。我们的算法是自适应的，仅根据精确的长浮点数计算。特别是，我们避免操纵代数数字和合成计算。它被设计成与现有的算法竞争哪个是“好”的选择。所有的标准算法假定F，G是互质的 - 我们的算法需要推广这一点。关键词：计算几何，曲线相交，Bzier曲线,，细分方法，有效的数值算法，精确的几何计算。1 介绍 代数曲线和曲面的交叉分析在许多几何模型领域是一个根本性的问题16。最实用的算法是基于自由曲面的曲线和曲面8，6。在本文中，我们考虑一类自由曲线，Bz
3、ier曲线。目前所有的交叉贝塞尔曲线算法是不准确的，主要的就是不稳定的问题。让我们看看一个根本原因。 一条曲线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）。如果FG的直
4、径小于，则输出该对；否则它细分曲线具有较大的直径，来讨论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或没有，把P作为一个交叉或不相交叉的交点；这相当于交叉点
5、p的重数是奇数还是偶数。不相交的交点，必须相切的，横向交叉点必须是横切的。因此我们有3个可能性，如图1所示。 （a）横向的（交叉） （b）切向的（交叉） (C) 切线(不相交) 图1：交点：（a）横向（b）切向（c）切线 可以避免使用吗？这似乎也合情合理，如果F和G只有交叉的交点，那么我们可以设计一个不使用任何来限制基于细分交叉算法。这不是显而易见，但它是隐含了本文交集算法。在任何情况下，关键的问题是如何检测非交叉的交点。最近，沃伯特23，22，解决了非奇异代数曲线的问题。这类曲线，她的地址和本文中提到的那些不具有直接可比性，虽然Bzier曲线是比较特殊的代数曲线，它们可以是单数（参见图5）。
6、她介绍广义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。我们的算法使用各种数值和几何近似的子程序。两个关键的子程序交叉的初等贝塞尔曲线用直线（第4部分）
10、和用于评估的“函数”的迹象（第5部分）。7。界需要小心应用程序（它不只是一个问题的取代一些开往通用交叉算法）。同样地，该应用程序的不相交的交点标准（NIC）需要准备：在第6章中，我们描述了耦合过程中创建申请NIC的必要前提。8。非基本贝塞尔曲线呢？一般的贝塞尔曲线的临界点，基本的曲线没有关键点。有一般方法，打破了代数曲线的关键点（例如，14）。这些涉及代数，非自适应的方法，我们希望避免的。相反，第7显示了如何细分与分离边界可以检测和隔离等关键点。第8提出了整体的交叉算法。9。我们所有的数值计算，最终降低环操作（+， - ，）（二进制）长浮点数，即理性号码的形式N2M其中n和mZ，这些操作进行准
11、确。为了提高效率，我们不操纵代数甚至是一般合理的数字。我们也不会操纵多项式或执行在当前子结式的计算，如被发现确切的交集算法。10。要强调长浮点数在我们的表达法中的作用，它介绍了以下术语是非常有用的。首先，定义的“标准参数化”点，线和贝塞尔曲线如下：一个点p的坐标由下式给出P =（X，Y），一条线L它是由给定系数的方程AX + BY + C确定，一条贝塞尔曲线是由给出的控制点（依次给出的坐标）确定。当这样的标准长浮点数参数X，Y，A，B，C等，我们称他们为直接对象，否则他们是间接对象。例如，相交的“直通线”和“直接曲线”F产生的坐标是代数数点P *。因此P*间接对象。然后，我们必须提供的替代方法
12、通过直接代表（近似）间接物体对象。我们在直接对象的上面使用“表达式”。例如，如果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坐落在一个标准的贝塞尔曲线G上。假设我们可以计算一定范围内 0，
13、如果p*不在G上，那么它的距离G至少是（第2部分）。然后，我们细化点L，F如上文所述，直到直径（F）/ 2。接下来，我们多次使用De Casteljau的算法细分G得到代替曲线（j=0，1，.）。当是空集时，我们丢弃；当直径时我们也将停止细分最后，我们的结论P在G上，当且仅当凸包CH（F），CH（GJ）对于一些j相交。此程序的正确性是不难看出。11。附录中包含所有被忽略的证明。我们的全论文可从http:/cs.nyu.edu/cs/faculty/yap/papers/看到。相关工作。曲线和曲面的代数计算文献是非常大的和多样的。我们可能会粗略地划分为两个不同的计算方法：(一)代数的观点对待曲线
14、和表面作为系统的代数方程来解决的，通常使用符号或代数技术。这种“代数算法“是准确的，并且（或可以完成）完整的。（二）几何的角度更喜欢曲线和曲面的参数形式，利用数值通常解决技术，例如同伦或细分。这样的“几何算法”往往不完整但广泛在实践中使用。在过去的20年里代数的观点已经发生了令人印象深刻的进步3。然而，许多代数算法不考虑实用。曲线和应用程序中的表面通常有界子集（“修补程序”）的代数集。几何算法直接操作这些补丁;代数算法把完整的代数套，往往被认为是束缚。这个事实可以减少算法的代数适用性。要指定补丁的代数集，可以用半代数的公式（即不等式）。但它是不容易，指定一个特定的分支曲线附近的一个置曲线自交点
15、使用这种方法。真正的平面的计算和拓扑分析曲线是一个很好的研究的问题1，18，而最坏的情况下复杂性是令人望而却步的；当前最好的理论束缚是时间曲线F(X,Y)= 0度n和2-范数n11。这种算法不考虑实际9。当代数算法与数字技术相结合，更实用的算法实现13，12。近日，计算几何学已开始处理曲线和曲面4，10，21。这些文件提供高效，完整的代数算法低度曲面和曲线。更一般地，它们的目标是使算法的代数观点下更有效的和完整的；这些问题都往往被掩盖了更多的理论文章。相反，我们的目标是让算法下几何完全健壮的观点，同时保留其适应性效率。更一般地，我们的表面上的目标是没有代数操作的情况下做精确的代数运算。我们只能做的数值逼近，但利用代数零界限的正确性实现。这项工作最直接与我们可比的是Wolpert的和赛德尔的23，22，20，如上所述。最近，普兰廷卡Vegter17给出了同位素的近似隐式非奇异的表面的拓扑正确的算法。他们的细分基础的方法是几何的，全面的自适应；但是它是目前未知是否它可以扩展处理的奇点。细分方法,为解决多变量多项式系
