AreTwoCurvestheSame?资源-CSDN文库

需积分: 1 196 浏览量 2013-07-02 19:39:13 上传评论收藏 780KB PDF 举报

We present an algorithm for answering the following fundamental question: Given two arbitrary (piecewise) polynomial curves, are they the same? This basic CAGD question is answered by first reducing the two curves into canonical irreducible forms. This is done by reversing the processes of knot refinement, degree raising, and composition. The two curves are then compared in their irreducible forms and their shared domains, if any, are identified. The ability to answer this fundamental identity question will be a boon for numerous applications. In this paper, we demonstrate a few such applications. The algorithm allows one to identify two boundary curves (shared as a common seam) between two different surfaces as an identical curve (or not) even when they are represented differently. Moreover, we show that reparameterization is insecure as a watermarking method, which invalidates the proposal of [8]. 在计算机辅助几何设计（CAGD）领域，识别两条曲线是否相同是一个基本问题。本文介绍了一个算法，用于回答给定两个任意（分段）多项式曲线是否相同的问题。算法的基本思想是首先将两条曲线转化为规范不可约形式，这一步是通过逆转结点细化、度数提升和组合的过程来实现的。之后，对两曲线的不可约形式进行比较，并识别它们共有的定义域。这一基础同一性问题的答案对于许多应用领域来说是一个巨大的福音。该算法的核心在于如何将多项式曲线转化为规范不可约形式，这涉及几个几何变换过程。首先是结点细化，这一过程是指在不改变曲线形状的前提下，向分段多项式或有理曲线中插入新的结点，可能会引入新的潜在不连续性。其次是度数提升，即把一个度数为d的多项式或有理曲线表示为更高度数d+k（k>0）的曲线。这两个过程都是可逆的，这意味着给定一条曲线的高阶表示，可以通过逆过程恢复到原始的表示形式。第三个过程是组合。如果我们有一个允许的参数变换函数，那么变换后曲线的轨迹与原始曲线的轨迹在可能不同的定义域或速度上是相同的。曲线匹配的关键是能够准确地识别出这些变换，并将曲线转化为一个通用的基线形式，从而进行有效的比较。该算法的应用包括但不限于识别两个不同曲面之间的两条边界曲线是否为同一曲线，即使这些曲线在表示形式上不同。例如，在复杂的3D模型中，识别两条边界的等同性可以帮助验证模型的完整性和一致性，或在模型修复和编辑过程中保持边界的一致性。此外，该文还揭示了重参数化作为水印方法的不安全性。在水印中，通常会对曲线进行重新参数化，以隐藏信息或作为版权标记。然而，由于重参数化过程的可逆性，该算法表明这种水印方法容易被识别和移除，从而使得[8]中的建议无效。关键词涵盖了多项式、有理数、组合、分解、结点细化、结点移除、度数提升、度数降低、水印和曲线匹配等领域。这些术语指出了算法在多项式曲线匹配中处理的各种操作和概念，不仅限于理论层面，还包括了实际应用中的安全性和精确性问题。文章作者包括来自以色列技术研究所的Diana Pekerman、Joon-Kyung Seong、Gershon Elber和首尔国立大学的Myung-Soo Kim。这一国际性合作团队为该研究领域贡献了重要的理论和实践成果。通过该算法的实现和应用，我们能够更好地理解复杂几何对象之间的关系，进而推动计算机图形学和几何设计等领域的发展。

资源推荐

资源详情

资源评论

Computer-Aided Design & Applications, Vol. 2, Nos. 1-4, 2005, pp 85-94

∑

Are Two Curves the Same?

Diana Pekerman

, Joon-Kyung Seong

, Gershon Elber

and Myung-Soo Kim

Technion-Israel Institute of Technology, pdiana@cs.technion.ac.il

Seoul National University, swallow@3map.snu.ac.kr

Technion-Israel Institute of Technology, gershon@cs.technion.ac.il

Seoul National University, mskim@cse.snu.ac.kr

ABSTRACT

We present an algorithm for answering the following fundamental question: Given two arbitrary

(piecewise) polynomial curves, are they the same? This basic CAGD question is answered by first

reducing the two curves into canonical irreducible forms. This is done by reversing the processes of

knot refinement, degree raising, and composition. The two curves are then compared in their

irreducible forms and their shared domains, if any, are identified. The ability to answer this

fundamental identity question will be a boon for numerous applications. In this paper, we

demonstrate a few such applications. The algorithm allows one to identify two boundary curves

(shared as a common seam) between two different surfaces as an identical curve (or not) even

when they are represented differently. Moreover, we show that reparameterization is insecure as a

watermarking method, which invalidates the proposal of [8].

Keywords: Polynomials; rationals; composition; decomposition; knot refinement; knot removal;

degree-raising; degree-reduction; water-marking; curve matching.

1. INTRODUCTION

There are several known ways of modifying the representation of a piecewise polynomial/rational regular curve, )(tC ,

while preserving its geometry or trace:

• Degree Raising [1]. A piecewise polynomial/rational curve of degree d can always be raised and represented

as a curve of higher degree d + k, k > 0 .

• Refinement [1]. Every piecewise polynomial/rational curve can be refined, i.e., new knots can be inserted

into the curve, without affecting its shape. However, these new knots introduce potential discontinuities into

the geometry.

• Composition [2], [5]. Let t(r) be an allowable change of parameter. Then, the trace of ))(()(

rtCrC = is

identical to that of C(t), albeit in a possibly different domain or speed.

It is quite well known that both degree raising and refinement are reversible. That is, given a curve )(tC known to be

of degree d, which is represented as a curve of degree d + k, k > 0 , one can deduce its original representation in

degree d. One simple way to achieve this, though not necessarily the most stable one, is to convert the representation

to monomial form as C(t) = and purge all the coefficients

, for i > d, that are zero. Then, convert the curve

back to the representation based on its original basis functions. More on degree reduction can be found, for example,

in [9].

Similarly, the process coined “knot removal” [7] attempts to detect knots whose removal has little or no effect over the

shape of the curve. Remove knot τ

and examine the best/closest shape one can find to the original curve )(tC , under

a certain norm, in the subspace that excludes knot τ

. If the new shape is identical to C(t), the curve C(t) resides in the

subspace that excludes τ

, since the knot τ

only introduces a potential discontinuity, and therefore, it can be removed.

The third way to modify the representation while preserving the shape is via functional composition. The composition

function modifies the speed of the curve or its domain but not the curve trace. In fact, when the composition is made

using an identity function, that is t(r) = r, the composition is reduced to a degree raising operation. Let the degree of

t(r) = r be k, e.g.,

−

+−=

rrrrt ])[()( , and let the degree of C(t) be d. Then, the composition is reduced to a simple

Computer-Aided Design & Applications, Vol. 2, Nos. 1-4, 2005, pp 85-94

degree raising, with ))(()(

rtCrC = being of degree dk. It is interesting to note that another simple way of achieving a

degree raising effect is by multiplying a constant one of degree l. Namely, let p(t) = 1 be a (constant) polynomial of

degree l, e.g.,

tttp ])[()( +−= 1 . Then, D(t) = C(t) p(t) is a new curve of degree d + l, but with exactly the same shape

as the curve C(t). In this paper, we assume only allowable changes of parameters, t(r), in the functional compositions;

that is, t'(r) > 0 ,

∀

Reversing the composition operation on polynomials, or decomposition of polynomials, is a complex task; yet it is a

feasible operation as we demonstrate it in this paper. Symbolic processing software packages, such as Maple [3] or

Mathematica [10], support the composition functionality as a built-in procedure. They do not, however, support the

reverse operation of the composition. Given a composed function H(x), we seek to find its decomposition, if any, as

H(x) = f(g(x)). In other words, we find the original functions, f(x) and g(x), if they exist.

The fact that symbolic manipulation programs provide no such reverse capability is more surprising, as function

decomposition has great importance in general, and in geometric modeling, specifically. In fact, the first algorithm to

decompose H(x) into f(x) and g(x) was proposed by [5] more than 15 years ago, and it was improved thereafter by [2].

Degree raising and refinement were both previously suggested as weak watermarking techniques. It is interesting to

note that the composition operation has been proposed to be a highly robust way to watermark spline models [8].

However, a clear implication of this paper invalidates the proposal of [8] – we show that composition is insecure as a

watermarking method.

Another important need for identifying the similarity of two curves could be found in the way geometry is typically

represented in contemporary geometric modelers. A model is typically a collection of freeform (trimmed) surfaces that

are stitched together along shared seams. In many cases the two curves sharing the seam are identical geometrically

but are represented differently due to the way the surfaces containing these two curves were constructed. For example,

to construct a ruled surface between a quadratic and a cubic curve, the quadratic is artificially degree-raised to be a

cubic. Having two curves sharing a seam represented differently makes cross-seams processing difficult. For example,

in order to create a water-tight tessellation of the geometry, both surfaces, along this shared seam, must be sampled in

exactly the same way. Knowing that these two curves are indeed the same curve can greatly simplify this process.

The rest of this paper is organized as follows. In Section 2, we present our approach to the functional decomposition

problem, and outline the complete algorithm, exploiting the unique structure that allows one to avoid solving a non-

linear system of constraints. In Section 3, an algorithm is presented that brings all these functionalities into play in a

single identity testing algorithm. In Section 4, we demonstrate a few interesting applications and examples, and finally,

we conclude this paper in Section 5.

2. FUNCTIONAL DECOMPOSITION

Consider two polynomials f(x) and g(x). The resulting composition of (f

g)(x) = f(g(x)) is a higher degree polynomial.

The coefficients of (f

g)(x) can be represented as non-linear expressions of the coefficients of f(x) and g(x). In general,

finding a solution to a set of non-linear equations is difficult. In our case, these equations are well structured, and we

will employ this simple structure to efficiently deduce the decomposition, if it exists. Moreover, its unique structure is

exactly the same in projective space when f(x) is rational.

The key observation that makes the functional decomposition feasible can be summarized as follows: In the

composition of two polynomials f(x) and g(x), the lowest degree terms reveal the structure of f(x) and the highest

degree terms expose the structure of g(x). The result of the composition has many high degree terms. However, being

closely related to convolution, many of these terms assume a simple form at the two ends of this composition process.

In other words, the terms with the highest and lowest degrees are the simplest. In Section 2.1, we provide additional

corroboration of our claim that no generality is lost by employing the following canonical forms of f(x) and g(x), for a

general composition H(x) = f(g(x)),

.)(

,)(

xcxcxxg

bxbxbxxf

+++=

++++=

−

(1)

By exploiting this canonical form, we could greatly simplify the composition formulation and its structure analysis.

When the two functions in Eqn. (1) are composed, we end up with a polynomial of degree km:

.)( )()(

))(()(

111

bxcxcxbxcxcxbxcxcx

xgfaxaxaxxH

kmk

+++++++++++++=

=++++=

−

−−

−

LLLL

Examine the coefficients of the k terms of H(x) with the highest degrees. Each coefficient

−

is expressible as a

function of

ikm

−

and

1+−ikk

cc ,,L

, for 11 −= ki ,,L , where

. Once the coefficients of g(x) are computed in this

剩余9页未读，继续阅读

评论收藏

内容反馈

唐三角

粉丝: 61
资源: 18

Are Two Curves the Same?

Agility and Modularity – Two Sides of the Same Coin（2014v21）

The Arithmetic of Elliptic Curves 第二版 Silverman.J.H

《怪曲线、数兔子及其他数学探究》的外文版本

A History of Curves and Surfaces in CAGD

Mumford - The structure of the moduli spaces of curves and abelian varieties

The Relationship Between Precision-Recall and ROC Curves

Intellipdf Curves 2.0 full

Focus on Curves and Surfaces

complex algebraic curves

curves.zip

The Adjusting Characteristic of Simulative Adaptive System

FlexGraphics_V_1.79_D4-XE10.2_Downloadly.ir

PDF转曲线IntelliPDF Curves Generator 1.0.1汉化版（绝对能用）

Advanced Topics in the Arithmetic of Elliptic Curves Silverman(268s)

IntelliPDF Curves 1.0

PDF转曲插件IntelliPDF Curves 2.0

Exp_Arrows_Curves - MetaTrader 5EA.zip

Differential Geometry of Curves and Surfaces DoCarmo

PDF -IntelliPDF Curves 1PDF软件快速转曲插件

i-vector的工具箱

Curves and Surfaces for CAGD

Synthesis and two-photon induced fluorescence spectroscopy of a novel nonlinear optical chromophore

Algebraic Geometry and Arithmetic Curves - Q Liu

Curves and Surfaces for CAGD:a practical guide.pdf

cost-curves.pdf.pdf

ADOL-C a package for the automatic differentiation of algorithms written in C C++

curves and surfaces for computer graphics

Intergraph Standard File Formats (Element Structure)

最新资源