Homogeneous coordinates

Last updated
Rational Bezier curve - polynomial curve defined in homogeneous coordinates (blue) and its projection on plane - rational curve (red) RationalBezier2D.svg
Rational Bézier curve polynomial curve defined in homogeneous coordinates (blue) and its projection on plane rational curve (red)

In mathematics, homogeneous coordinates or projective coordinates, introduced by August Ferdinand Möbius in his 1827 work Der barycentrische Calcul, [1] [2] [3] are a system of coordinates used in projective geometry, as Cartesian coordinates are used in Euclidean geometry. They have the advantage that the coordinates of points, including points at infinity, can be represented using finite coordinates. Formulas involving homogeneous coordinates are often simpler and more symmetric than their Cartesian counterparts. Homogeneous coordinates have a range of applications, including computer graphics and 3D computer vision, where they allow affine transformations and, in general, projective transformations to be easily represented by a matrix.

Contents

If homogeneous coordinates of a point are multiplied by a non-zero scalar then the resulting coordinates represent the same point. Since homogeneous coordinates are also given to points at infinity, the number of coordinates required to allow this extension is one more than the dimension of the projective space being considered. For example, two homogeneous coordinates are required to specify a point on the projective line and three homogeneous coordinates are required to specify a point in the projective plane.

Introduction

The real projective plane can be thought of as the Euclidean plane with additional points added, which are called points at infinity, and are considered to lie on a new line, the line at infinity. There is a point at infinity corresponding to each direction (numerically given by the slope of a line), informally defined as the limit of a point that moves in that direction away from the origin. Parallel lines in the Euclidean plane are said to intersect at a point at infinity corresponding to their common direction. Given a point (x, y) on the Euclidean plane, for any non-zero real number Z, the triple (xZ, yZ, Z) is called a set of homogeneous coordinates for the point. By this definition, multiplying the three homogeneous coordinates by a common, non-zero factor gives a new set of homogeneous coordinates for the same point. In particular, (x, y, 1) is such a system of homogeneous coordinates for the point (x, y). For example, the Cartesian point (1, 2) can be represented in homogeneous coordinates as (1, 2, 1) or (2, 4, 2). The original Cartesian coordinates are recovered by dividing the first two positions by the third. Thus unlike Cartesian coordinates, a single point can be represented by infinitely many homogeneous coordinates.

The equation of a line through the origin (0, 0) may be written nx + my = 0 where n and m are not both 0. In parametric form this can be written x = mt, y = −nt. Let Z = 1/t, so the coordinates of a point on the line may be written (m/Z, −n/Z). In homogeneous coordinates this becomes (m, −n, Z). In the limit, as t approaches infinity, in other words, as the point moves away from the origin, Z approaches 0 and the homogeneous coordinates of the point become (m, −n, 0). Thus we define (m, −n, 0) as the homogeneous coordinates of the point at infinity corresponding to the direction of the line nx + my = 0. As any line of the Euclidean plane is parallel to a line passing through the origin, and since parallel lines have the same point at infinity, the infinite point on every line of the Euclidean plane has been given homogeneous coordinates.

To summarize:

Note that the triple (0, 0, 0) is omitted and does not represent any point. The origin is represented by (0, 0, 1). [4]

Notation

Some authors use different notations for homogeneous coordinates which help distinguish them from Cartesian coordinates. The use of colons instead of commas, for example (x:y:z) instead of (x, y, z), emphasizes that the coordinates are to be considered ratios. [5] Square brackets, as in [x, y, z] emphasize that multiple sets of coordinates are associated with a single point. [6] Some authors use a combination of colons and square brackets, as in [x:y:z]. [7]

Other dimensions

The discussion in the preceding section applies analogously to projective spaces other than the plane. So the points on the projective line may be represented by pairs of coordinates (x, y), not both zero. In this case, the point at infinity is (1, 0). Similarly the points in projective n-space are represented by (n + 1)-tuples. [8]

Other projective spaces

The use of real numbers gives homogeneous coordinates of points in the classical case of the real projective spaces, however any field may be used, in particular, the complex numbers may be used for complex projective space. For example, the complex projective line uses two homogeneous complex coordinates and is known as the Riemann sphere. Other fields, including finite fields, can be used.

Homogeneous coordinates for projective spaces can also be created with elements from a division ring (a skew field). However, in this case, care must be taken to account for the fact that multiplication may not be commutative. [9]

For the general ring A, a projective line over A can be defined with homogeneous factors acting on the left and the projective linear group acting on the right.

Alternative definition

Another definition of the real projective plane can be given in terms of equivalence classes. For non-zero elements of R3, define (x1, y1, z1) ~ (x2, y2, z2) to mean there is a non-zero λ so that (x1, y1, z1) = (λx2, λy2, λz2). Then ~ is an equivalence relation and the projective plane can be defined as the equivalence classes of R3 ∖ {0}. If (x, y, z) is one of the elements of the equivalence class p then these are taken to be homogeneous coordinates of p.

Lines in this space are defined to be sets of solutions of equations of the form ax + by + cz = 0 where not all of a, b and c are zero. Satisfaction of the condition ax + by + cz = 0 depends only on the equivalence class of (x, y, z), so the equation defines a set of points in the projective plane. The mapping (x, y) → (x, y, 1) defines an inclusion from the Euclidean plane to the projective plane and the complement of the image is the set of points with z = 0. The equation z = 0 is an equation of a line in the projective plane (see definition of a line in the projective plane), and is called the line at infinity.

The equivalence classes, p, are the lines through the origin with the origin removed. The origin does not really play an essential part in the previous discussion so it can be added back in without changing the properties of the projective plane. This produces a variation on the definition, namely the projective plane is defined as the set of lines in R3 that pass through the origin and the coordinates of a non-zero element (x, y, z) of a line are taken to be homogeneous coordinates of the line. These lines are now interpreted as points in the projective plane.

Again, this discussion applies analogously to other dimensions. So the projective space of dimension n can be defined as the set of lines through the origin in Rn+1. [10]

Homogeneity

Homogeneous coordinates are not uniquely determined by a point, so a function defined on the coordinates, say f(x, y, z), does not determine a function defined on points as with Cartesian coordinates. But a condition f(x, y, z) = 0 defined on the coordinates, as might be used to describe a curve, determines a condition on points if the function is homogeneous. Specifically, suppose there is a k such that

If a set of coordinates represents the same point as (x, y, z) then it can be written x, λy, λz) for some non-zero value of λ. Then

A polynomial g(x, y) of degree k can be turned into a homogeneous polynomial by replacing x with x/z, y with y/z and multiplying by zk, in other words by defining

The resulting function f is a polynomial, so it makes sense to extend its domain to triples where z = 0. The process can be reversed by setting z = 1, or

The equation f(x, y, z) = 0 can then be thought of as the homogeneous form of g(x, y) = 0 and it defines the same curve when restricted to the Euclidean plane. For example, the homogeneous form of the equation of the line ax + by + c = 0 is ax + by + cz = 0. [11]

Line coordinates and duality

The equation of a line in the projective plane may be given as sx + ty + uz = 0 where s, t and u are constants. Each triple (s, t, u) determines a line, the line determined is unchanged if it is multiplied by a non-zero scalar, and at least one of s, t and u must be non-zero. So the triple (s, t, u) may be taken to be homogeneous coordinates of a line in the projective plane, that is line coordinates as opposed to point coordinates. If in sx + ty + uz = 0 the letters s, t and u are taken as variables and x, y and z are taken as constants then the equation becomes an equation of a set of lines in the space of all lines in the plane. Geometrically it represents the set of lines that pass through the point (x, y, z) and may be interpreted as the equation of the point in line-coordinates. In the same way, planes in 3-space may be given sets of four homogeneous coordinates, and so on for higher dimensions. [12]

The same relation, sx + ty + uz = 0, may be regarded as either the equation of a line or the equation of a point. In general, there is no difference either algebraically or logically between homogeneous coordinates of points and lines. So plane geometry with points as the fundamental elements and plane geometry with lines as the fundamental elements are equivalent except for interpretation. This leads to the concept of duality in projective geometry, the principle that the roles of points and lines can be interchanged in a theorem in projective geometry and the result will also be a theorem. Analogously, the theory of points in projective 3-space is dual to the theory of planes in projective 3-space, and so on for higher dimensions. [13]

Plücker coordinates

Assigning coordinates to lines in projective 3-space is more complicated since it would seem that a total of 8 coordinates, either the coordinates of two points which lie on the line or two planes whose intersection is the line, are required. A useful method, due to Julius Plücker, creates a set of six coordinates as the determinants xiyjxjyi (1 ≤ i < j ≤ 4) from the homogeneous coordinates of two points (x1, x2, x3, x4) and (y1, y2, y3, y4) on the line. The Plücker embedding is the generalization of this to create homogeneous coordinates of elements of any dimension m in a projective space of dimension n. [14] [15]

Application to Bézout's theorem

Bézout's theorem predicts that the number of points of intersection of two curves is equal to the product of their degrees (assuming an algebraically closed field and with certain conventions followed for counting intersection multiplicities). Bézout's theorem predicts there is one point of intersection of two lines and in general this is true, but when the lines are parallel the point of intersection is infinite. Homogeneous coordinates are used to locate the point of intersection in this case. Similarly, Bézout's theorem predicts that a line will intersect a conic at two points, but in some cases one or both of the points is infinite and homogeneous coordinates must be used to locate them. For example, y = x2 and x = 0 have only one point of intersection in the finite (affine) plane. To find the other point of intersection, convert the equations into homogeneous form, yz = x2 and x = 0. This produces x = yz = 0 and, assuming not all of x, y and z are 0, the solutions are x = y = 0, z ≠ 0 and x = z = 0, y ≠ 0. This first solution is the point (0, 0) in Cartesian coordinates, the finite point of intersection. The second solution gives the homogeneous coordinates (0, 1, 0) which corresponds to the direction of the y-axis. For the equations xy = 1 and x = 0 there are no finite points of intersection. Converting the equations into homogeneous form gives xy = z2 and x = 0. Solving produces the equation z2 = 0 which has a double root at z = 0. From the original equation, x = 0, so y ≠ 0 since at least one coordinate must be non-zero. Therefore, (0, 1, 0) is the point of intersection counted with multiplicity 2 in agreement with the theorem. [16]

Circular points

The homogeneous form for the equation of a circle in the real or complex projective plane is x2 + y2 + 2axz + 2byz + cz2 = 0. The intersection of this curve with the line at infinity can be found by setting z = 0. This produces the equation x2 + y2 = 0 which has two solutions over the complex numbers, giving rise to the points with homogeneous coordinates (1, i, 0) and (1, −i, 0) in the complex projective plane. These points are called the circular points at infinity and can be regarded as the common points of intersection of all circles. This can be generalized to curves of higher order as circular algebraic curves. [17]

Change of coordinate systems

Just as the selection of axes in the Cartesian coordinate system is somewhat arbitrary, the selection of a single system of homogeneous coordinates out of all possible systems is somewhat arbitrary. Therefore, it is useful to know how the different systems are related to each other.

Let (x, y, z) be homogeneous coordinates of a point in the projective plane. A fixed matrix

with nonzero determinant, defines a new system of coordinates (X, Y, Z) by the equation

Multiplication of (x, y, z) by a scalar results in the multiplication of (X, Y, Z) by the same scalar, and X, Y and Z cannot be all 0 unless x, y and z are all zero since A is nonsingular. So (X, Y, Z) are a new system of homogeneous coordinates for the same point of the projective plane.

Barycentric coordinates

Möbius's original formulation of homogeneous coordinates specified the position of a point as the center of mass (or barycenter) of a system of three point masses placed at the vertices of a fixed triangle. Points within the triangle are represented by positive masses and points outside the triangle are represented by allowing negative masses. Multiplying the masses in the system by a scalar does not affect the center of mass, so this is a special case of a system of homogeneous coordinates.

Trilinear coordinates

Let l, m, n be three lines in the plane and define a set of coordinates X, Y and Z of a point p as the signed distances from p to these three lines. These are called the trilinear coordinates of p with respect to the triangle whose vertices are the pairwise intersections of the lines. Strictly speaking these are not homogeneous, since the values of X, Y and Z are determined exactly, not just up to proportionality. There is a linear relationship between them however, so these coordinates can be made homogeneous by allowing multiples of (X, Y, Z) to represent the same point. More generally, X, Y and Z can be defined as constants p, r and q times the distances to l, m and n, resulting in a different system of homogeneous coordinates with the same triangle of reference. This is, in fact, the most general type of system of homogeneous coordinates for points in the plane if none of the lines is the line at infinity. [18]

Use in computer graphics and computer vision

Homogeneous coordinates are ubiquitous in computer graphics because they allow common vector operations such as translation, rotation, scaling and perspective projection to be represented as a matrix by which the vector is multiplied. By the chain rule, any sequence of such operations can be multiplied out into a single matrix, allowing simple and efficient processing. By contrast, using Cartesian coordinates, translations and perspective projection cannot be expressed as matrix multiplications, though other operations can. Modern OpenGL and Direct3D graphics cards take advantage of homogeneous coordinates to implement a vertex shader efficiently using vector processors with 4-element registers. [19] [20]

For example, in perspective projection, a position in space is associated with the line from it to a fixed point called the center of projection. The point is then mapped to a plane by finding the point of intersection of that plane and the line. This produces an accurate representation of how a three-dimensional object appears to the eye. In the simplest situation, the center of projection is the origin and points are mapped to the plane z = 1, working for the moment in Cartesian coordinates. For a given point in space, (x, y, z), the point where the line and the plane intersect is (x/z, y/z, 1). Dropping the now superfluous z coordinate, this becomes (x/z, y/z). In homogeneous coordinates, the point (x, y, z) is represented by (xw, yw, zw, w) and the point it maps to on the plane is represented by (xw, yw, zw), so projection can be represented in matrix form as[ clarification needed ]

Matrices representing other geometric transformations can be combined with this and each other by matrix multiplication. As a result, any perspective projection of space can be represented as a single matrix. [21] [22]

Notes

  1. August Ferdinand Möbius: Der barycentrische Calcul, Verlag von Johann Ambrosius Barth, Leipzig, 1827.
  2. O'Connor, John J.; Robertson, Edmund F., "August Ferdinand Möbius", MacTutor History of Mathematics archive , University of St Andrews
  3. Smith, David Eugene (1906). History of Modern Mathematics. J. Wiley & Sons. p.  53.
  4. For the section: Jones 1912 , pp. 120122
  5. Woods 1922
  6. Garner 1981
  7. Miranda 1995
  8. Bôcher 1907 , pp. 1314
  9. Garner 1981 , pp. 3233
  10. For the section: Cox, Little & O'Shea 2007 , pp. 360362
  11. For the section: Miranda 1995 , p. 14 and Jones 1912 , p. 120
  12. Bôcher 1907 , pp. 107108 (adapted to the plane according to the footnote on p. 108)
  13. Woods 1922 , pp. 2, 40
  14. Wilczynski 1906 , p. 50
  15. Bôcher 1907 , p. 110
  16. Jones 1912 , pp. 117118, 122 with simplified examples.
  17. Jones 1912 , p. 204
  18. Jones 1912 , pp. 452 ff
  19. "Viewports and Clipping (Direct3D 9) (Windows)". msdn.microsoft.com. Retrieved 10 April 2018.
  20. Shreiner, Dave; Woo, Mason; Neider, Jackie; Davis, Tom; "OpenGL Programming Guide", 4th Edition, ISBN   978-0-321-17348-5, published December 2004. Page 38 and Appendix F (pp. 697-702) Discuss how OpenGL uses homogeneous coordinates in its rendering pipeline. Page 2 indicates that OpenGL is a software interface to graphics hardware.
  21. Mortenson, Michael E. (1999). Mathematics for Computer Graphics Applications . Industrial Press Inc. p.  318. ISBN   0-8311-3111-X.
  22. McConnell, Jeffrey J. (2006). Computer Graphics: Theory into Practice. Jones & Bartlett Learning. p.  120. ISBN   0-7637-2250-2.

Related Research Articles

Cartesian coordinate system Coordinate system

A Cartesian coordinate system in a plane is a coordinate system that specifies each point uniquely by a pair of numerical coordinates, which are the signed distances to the point from two fixed perpendicular oriented lines, measured in the same unit of length. Each reference line is called a coordinate axis or just axis of the system, and the point where they meet is its origin, at ordered pair (0, 0). The coordinates can also be defined as the positions of the perpendicular projections of the point onto the two axes, expressed as signed distances from the origin.

Euclidean space Fundamental space of geometry

Euclidean space is the fundamental space of classical geometry. Originally, it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are Euclidean spaces of any nonnegative integer dimension, including the three-dimensional space and the Euclidean plane. It was introduced by the Ancient Greek mathematician Euclid of Alexandria, and the qualifier Euclidean is used to distinguish it from other spaces that were later discovered in physics and modern mathematics.

Coordinate system System for determining the position of a point by a tuple of scalars

In geometry, a coordinate system is a system that uses one or more numbers, or coordinates, to uniquely determine the position of the points or other geometric elements on a manifold such as Euclidean space. The order of the coordinates is significant, and they are sometimes identified by their position in an ordered tuple and sometimes by a letter, as in "the x-coordinate". The coordinates are taken to be real numbers in elementary mathematics, but may be complex numbers or elements of a more abstract system such as a commutative ring. The use of a coordinate system allows problems in geometry to be translated into problems about numbers and vice versa; this is the basis of analytic geometry.

In mathematics, a quadric or quadric surface, is a generalization of conic sections. It is a hypersurface in a (D + 1)-dimensional space, and it is defined as the zero set of an irreducible polynomial of degree two in D + 1 variables. When the defining polynomial is not absolutely irreducible, the zero set is generally not considered a quadric, although it is often called a degenerate quadric or a reducible quadric.

Bézout's theorem is a statement in algebraic geometry concerning the number of common zeros of n polynomials in n indeterminates. In its original form the theorem states that in general the number of common zeros equals the product of the degrees of the polynomials. It is named after Étienne Bézout.

In mathematics, the matrix representation of conic sections permits the tools of linear algebra to be used in the study of conic sections. It provides easy ways to calculate a conic section's axis, vertices, tangents and the pole and polar relationship between points and lines of the plane determined by the conic. The technique does not require putting the equation of a conic section into a standard form, thus making it easier to investigate those conic sections whose axes are not parallel to the coordinate system.

Projective space Completion of the usual space with "points at infinity"

In mathematics, the concept of a projective space originated from the visual effect of perspective, where parallel lines seem to meet at infinity. A projective space may thus be viewed as the extension of a Euclidean space, or, more generally, an affine space with points at infinity, in such a way that there is one point at infinity of each direction of parallel lines.

Algebraic curve Curve defined as zeros of polynomials

In mathematics, an affine algebraic plane curve is the zero set of a polynomial in two variables. A projective algebraic plane curve is the zero set in a projective plane of a homogeneous polynomial in three variables. An affine algebraic plane curve can be completed in a projective algebraic plane curve by homogenizing its defining polynomial. Conversely, a projective algebraic plane curve of homogeneous equation h(x, y, t) = 0 can be restricted to the affine algebraic plane curve of equation h(x, y, 1) = 0. These two operations are each inverse to the other; therefore, the phrase algebraic plane curve is often used without specifying explicitly whether it is the affine or the projective case that is considered.

In mathematics, conformal geometry is the study of the set of angle-preserving (conformal) transformations on a space.

Affine space Geometric structure that generalizes the Euclidean space

In mathematics, an affine space is a geometric structure that generalizes some of the properties of Euclidean spaces in such a way that these are independent of the concepts of distance and measure of angles, keeping only the properties related to parallelism and ratio of lengths for parallel line segments.

Real projective plane Compact non-orientable two-dimensional manifold

In mathematics, the real projective plane is an example of a compact non-orientable two-dimensional manifold; in other words, a one-sided surface. It cannot be embedded in standard three-dimensional space without intersecting itself. It has basic applications to geometry, since the common construction of the real projective plane is as the space of lines in R3 passing through the origin.

Barycentric coordinate system Coordinate system that is defined by points instead of vectors

In geometry, a barycentric coordinate system is a coordinate system in which the location of a point is specified by reference to a simplex. The barycentric coordinates of a point can be interpreted as masses placed at the vertices of the simplex, such that the point is the center of mass of these masses. These masses can be zero or negative; they are all positive if and only if the point is inside the simplex.

Line (geometry) Straight figure with zero width and depth

In geometry, the notion of line or straight line was introduced by ancient mathematicians to represent straight objects with negligible width and depth. Lines are an idealization of such objects, which are often described in terms of two points or referred to using a single letter.

Pencil (mathematics)

In geometry, a pencil is a family of geometric objects with a common property, for example the set of lines that pass through a given point in a plane, or the set of circles that pass through two given points in a plane.

In projective geometry, a homography is an isomorphism of projective spaces, induced by an isomorphism of the vector spaces from which the projective spaces derive. It is a bijection that maps lines to lines, and thus a collineation. In general, some collineations are not homographies, but the fundamental theorem of projective geometry asserts that is not so in the case of real projective spaces of dimension at least two. Synonyms include projectivity, projective transformation, and projective collineation.

Three-dimensional space Geometric model of the physical space

Three-dimensional space is a geometric setting in which three values are required to determine the position of an element. This is the informal meaning of the term dimension.

In projective geometry, the circular points at infinity are two special points at infinity in the complex projective plane that are contained in the complexification of every real circle.

Lie sphere geometry Geometry founded on spheres

Lie sphere geometry is a geometrical theory of planar or spatial geometry in which the fundamental concept is the circle or sphere. It was introduced by Sophus Lie in the nineteenth century. The main idea which leads to Lie sphere geometry is that lines should be regarded as circles of infinite radius and that points in the plane should be regarded as circles of zero radius.

Conic section Curve obtained by intersecting a cone and a plane

In mathematics, a conic section is a curve obtained as the intersection of the surface of a cone with a plane. The three types of conic section are the hyperbola, the parabola, and the ellipse; the circle is a special case of the ellipse, though historically it was sometimes called a fourth type. The ancient Greek mathematicians studied conic sections, culminating around 200 BC with Apollonius of Perga's systematic work on their properties.

In geometry, line coordinates are used to specify the position of a line just as point coordinates are used to specify the position of a point.

References

Further reading