a r X i v :c s /0310017v 1 [c s .C G ] 9 O c t 2003
Circle and sphere blending with conformal geometric algebra Chris Doran 1bachelor翻译
英语翻译机Astrophysics Group,Cavendish Laboratory,Madingley Road,
Cambridge CB30HE,UK.
Abstract
Blending schemes bad on circles provide smooth ‘fair’interpolations between ries of points.Here we demonstrate a simple,robust t of algorithms for performing circle blends for a range of cas.An arbitrary level of G -continuity can be achieved by simple alterations to the underly-ing parameterisation.Our method exploits the computational framework provided by conformal geometric algebra.This employs a five-dimensional reprentation of points in space,in contrast to the four-dimensional rep-rentation typically ud in projective geometry.The advantage of the conformal scheme is that straight lines and circles are treated in a single,unified framework.As a further illustration of the power of the conformal framework,the basic idea is extended to the ca of sphere blending to interpolate over a surface.
外景地
Keywords:spline,geometry,geometric algebra,conformal
1Introduction
In a range of applications we often ek curves and surfaces that have an aesthet-ically pleasing ‘roundedness’to them.One way to make this concept concrete is through looking for globally-optimid ‘minimum variation curves’[1].The philosophy behind this idea is straightforward.We usually prefer curves that are clo to circular over curves with sharp turns.This is particularly true when designing camera trajectories,where sudden changes in curvature can have a very disorienting effect.Circular paths are characterid by having constant curvature,so a natural idea in forming interpolations between control points is to find a curve that minimis the total change in curvature.The problem with such a strategy is that the curves can be extremely hard to compute.If one adopted a variational strategy,with endpoint conditions,the equations for the curve can be as high as fifth order and are even more difficult to treat than tho of elasticity.Such equations can only be solved numerically and do not have straightforward,controllable,analytic solutions.The problem is even more acute if multiple control points are involved,as even numerical computation can be extremely difficult.
A more straightforward,local scheme that provides smooth interpolations was introduced by Wenz [2]and later extended by Szilv´a si-Nagy &Vendel [3].The idea explored by the authors is to generate curves that are as clo as possible to circles.Given four points X 0,...,X 3we construct the circles C 1through X 0,X 1and X 2,and C 2through X 1,X 2and X 3.The curve between X 1and X 2is then formed by smoothly interpolating between the two circles.This idea was further extended by S´e quin &Yen [4]and S´e quin &Lee [5],
who introduced an angle-bad circle blending scheme.The angle-bad scheme gives better results than the earlier,midpoint scheme,and we argue here that it is geometrically the‘correct’one.S´e quin&Lee also showed how to achieve G2-continuity(and higher order continuity,if desired),and demonstrated the value of angle-bad blending for interpolating over the surface of a sphere.
In this paper we further explore the geometry associated with circle blend-ing,following the methods developed by S´e quin and his coworkers.The esntial idea is that the natural way to transform between two circles is via a conformal transformation.Conformal transformations leave angles invariant,but can alter distances.Euclidean transformations are the subt of conformal transforma-tions that also leave distances invariant.Conformal transformations in a plane can take any three chon points to any three image points.As such,they can transform a line or circle into any other cir
cle.In this geometry,straight lines are examples of circles that pass through the point at infinity.By exploiting the features of conformal geometry,we can write robust code that treats(straight) lines and circles in a single,unified manner.This eliminates the need to check for special cas.Similarly,in three dimensions,planes and spheres are treated as examples of the same object.So a single routine can interpolate between points on a sphere,and will reduce to the planar ca when four points happen to lie in a plane.
To fully exploit the advantages of conformal geometry we work in the math-ematical framework of geometric algebra[6,7].This algebra treats points,lines, circles,planes and spheres,and the transformations acting on them,in a uni-fied algebraic framework.A number of authors have argued for the advantages of the conformal geometric algebra framework for computer graphics applica-tions[7,8,9,10,11].The prent work should be viewed in this context.We show how complex problems such asfinding the conformal transformation be-tween a line and a circle reduce to simple,robust expressions in the geometric algebra framework.As a further application we show how the same framework naturally extends to sphere-blending over a surface.This suggests a new method of characterising surfaces that does not require the concept of swept curves.
This paper starts with an introduction to conformal geometric algebra.This introduction is lf-contain
ed,but to keep its length down a number of concepts are introduced with a minimum of explanation.We then turn to the question of how to mathematically encode transformations between circles.Wefind the conformal transformation that achieves this and explore its properties.Some subtleties involving the orientation of the transformation are explained,and we demonstrate how they are easily resolved in the conformal framework.We then provide a ries of examples of blended curves,and illustrate the effects of demanding higher-order G-continuity.Wefinish by introducing a method of sphere blending and discuss the potential of this idea for encoding surfaces.
2Conformal geometry and Euclidean space
The starting point for our description of geometry is the conformal group.This marks a radical departure from conventional descriptions of Euclidean space bad on projective geometry and homogeneous coordinates.The main advan-tage of basing the description in a conformal tting is that distance is encoded simply,making the geometry well suited to describing the real three-dimensional
取个英文名2
world.
Suppo we start with an n-dimensional Euclidean vector space R n.The conformal group consists of the t of all transformations of R n that leave angles invariant.The include translations and rotations,so the conformal group includes the t of Euclidean transformations as a subgroup.The conformal group on R n has a natural reprentation in terms of rotations in a space two dimensions higher,with signature(n+1,1).So,in the same way that projective transformations are linearid by working in a space one dimension higher than the Euclidean ba space,conformal transformations are linearid in a space two dimensions higher.The conformal reprentation of points in Euclidean three-space consists of vectors in a5-dimensional space.While this may appear to be an unnecessary abstraction,working in thisfive-dimensional space does bring a number of advantages.
To exploit the conformal reprentation we need a standard reprentation for a Euclidean point in thefive-dimensional conformal space.Given that we are occupying a space two dimensions higher,two constraints are required to specify a unique point.Thefirst of the is that our underlying reprentation is homogeneous,so X andλX reprent the same point in Euclidean space.The cond constraint is that the vector X is null,
X2=0.(1) (The existence of null vectors is guaranteed by the fact that the conformal vector space has mixed signature.)This is esntially the only further constraint that can be enforced which is consiste
nt with homogeneity and invariant under orthogonal transformations in conformal space.Now suppo that e1,e2and e3reprent three vectors in the three-dimensional ba space,and we add to the the vectors e0and e4.The satisfy
e20=−1,e24=+1,(2) and all5vectors{e0,...,e4}are orthogonal.From the two extra vectors we define the two null vectors n and¯n by
n=e4+e0,¯n=e4−e0,n·¯n=2.(3) (It is a straightforward exerci to confirm that the two vectors both have zero magnitude.)From the we need to cho a vector to reprent the origin.This is conventionally taken as−1
4
e Figure 1:The null cone.In a three dimensional space o
f signature (2,1)the t of null vectors form a cone.To ensure a unique reprentation of points that maintains orientation,we restrict to the subction with positive e 0component.The t of vectors satisfyin
g X ·n =−2defines the ‘standard’reprentation of points,in this ca defining the conformal reprentation of a one-dimensional space.
The Euclidean coordinates of the point x are recovered from X via the homogeneous relation
x i =−X ·e i
A ·n .(7)
One should be wary of employing this map when writing code,as the right-hand side is singular if A happens to be the point at infinity.As is the ca for projective
geometry,it is better practice to let the normalisation run free,and only u equation (6)in the final stage to recover the coordinates.
The power of the conformal reprentation starts to become clear when we consider the inner product of points.Suppo that X and Y are the conformal reprentations of the points x and y respectively,both in the standard form ofexpress yourlf
4
equation(5).Their inner product is
天行健君子以自强不息的意思X·Y= x2n+2x−¯n · y2n+2y−¯n
托业考试报名=−2x2−2y2+4x·y
=−2(x−y)2.(8) This is the esntial result that underpins the conformal approach to Euclidean geometry.The inner product in conformal space encodes the distance between points in Euclidean space.This is the reason why points are reprented with null vectors—the distance between a point and itlf is zero.
Generalising equation(8)to unnormalid vectors,the distance between points can be written
X·Y
|x−y|2=−2
tpp是什么(ab+ba).(12)
2
The remaining,antisymmetric part of the geometric product returns the outer or exterior product familiar from projective geometry.We write this as
a∧b=1
The geometric product of two vectors can now be written
ab=a·b+a∧b.(14) Under the geometric product,orthogonal vectors anticommute and parallel vec-tors commute.The product therefore encodes the basic geometric relationships between vectors.Now that we know how to multiply vectors together,it is straightforward to construct the entire geometric algebra of a given vector space. This is facilitated by introducing an orthonormal frame of vectors{e i}.The satisfy
e i·e j=ηij,(15) whereηij is the metric tensor.For a space o
f signature(p,q),ηij is a diagonal matrix consistin
g of p+1s and q−1s.The space of interest to us here is the conformal space of signature(4,1).A basis for this is provided by the vectors e0,...,e4,wit
h e0having negative square.The algebra generated by the vectors has32terms in total,and is spanned by
1{e i}{e i∧e j}{e i∧e j∧e k}{Ie i}I
honestgrade012345
dimension15101051.
We refer to this algebra as G(4,1).The term‘grade’is ud to refer to the number of vectors in any exterior product.The dimensions of each graded subspace are given by the binomial coefficients.
不知不觉英文
The highest grade term in G(4,1)is called the pudoscalar and is given the symbol I.This is defined by
I=e0e1e2e3e4.(16) The pudoscalar commutes with all elements in the algebra,a feature of odd-dimensional algebras,and the(4,1)signature of the space implies that the pudoscalar satisfies
I2=−1.(17) So,algebraically,I has the properties of a unit imaginary.But it also plays a definite geometric role,as multiplication by the pudoscalar performs a duality transformation in conformal space.A matrix reprentation of G(4,1)can be constructed in terms of4×4complex matrices.The can be found in the physics literature in the gui of the Dirac matrices[13].For practical applications this matrix reprentation has little value and one is better offcoding up the algebraic rules explicitly.
A general element of G(4,1)is called a multivector and can consist of a sum of terms all grades in the algebra.Arbitrary elements of G(4,1)can be added and multiplied together.A multivector that consists only of terms of a single grade is said to be homogeneous.The geometric product of a pair of homogeneous multivectors decompos as follows:
A r
B s= A r B s |r−s|+ A r B s |r−s|+2+···+ A r B s r+s.(18) The angle brackets M r are ud to denote the projection onto the grade-r terms in M.The dot and wedge symbols are ud to generali the inner and
6
