Perspective Projection of an Ellipse David Eberly Geometric Tools, LLC http://www.geometrictools.com/ c 1998-2015. All Rights Reserved. Copyright Created: March 10, 2015 Contents 1 Introduction 2 2 Elliptical Cones 2 2.1 Right Elliptical Cones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2.2 Skewed Elliptical Cones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.3 General Elliptical Cones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.4 Converting General Cones to Skewed Cones . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 3 Projection of the Ellipse to Another Plane 5 1 1 Introduction The standard axis-aligned ellipse in 2D is of the form 2 2 y1 y0 + =1 d0 d1 (1) where d0 > 0 and d1 > 0. The 2D coordinates of points are (y0 , y1 ). In 3D, we can specify an ellipse in a general plane. Let the ellipse center be Ce , which is a point on the plane. Let the plane normal be the unit-length vector Ne . Choose unit-length vectors Ue and Ve so that the set {Ue , Ve , Ne } is a right-handed orthonormal basis; that is, the vectors are unit-length, mutually orthogonal, and Ne = Ue × Ve . The ellipse consists of 3D points Xe = Ce + y0 Ue + y1 Ve = Ce + Je Ye (2) where (y0 , y1 ) is a solution to equation (1). The second equality in equation (2) defines the 3 × 2 matrix Je whose columns are Ue and Ve and defines the 2 × 1 column vector Ye whose rows are the components of (y0 , y1 ). Given an eyepoint E, we want to perspectively project the ellipse onto another plane. That plane has unitlength normal Np and origin point Cp . We may choose the normal so that E is on the side of the plane to which Np is directed; that is, Np · (E − Cp ) > 0. If {Up , Vp , Np } is a right-handed orthonormal set, then points on the projection plane are Xp = Cp + y2 Up + y3 Vp = Cp + Jp Yp (3) The second equality in equation (3) defines the 3 × 2 matrix Jp whose columns are Up and Vp and defines the 2 × 1 column vector Yp whose rows are the components of (y2 , y3 ). Assuming the ellipse is between the eyepoint and the projection plane, the projection is also an ellipse. We will determine a quadratic equation in the components of Yp that define the projected ellipse. 2 Elliptical Cones There are multiple ways to approach the projection problem. The one presented here is based on computing an ellipse as the intersection of an elliptical cone and a plane. The intersection will be represented implicitly by a quadratic equation of Yp . 2.1 Right Elliptical Cones A standard right elliptical cone is represented algebraically as 2 2 2 y2 y0 y1 −1 = + e2 d0 d1 (4) where the cone vertex is located at (0, 0, e2 ) with e2 > 0. The cone vertex is a solution to equation (4). When y2 = 0, the elliptical cone equation reduces to the standard ellipse equation (1). Thus, the standard ellipse points are on the elliptical cone, which means that these points are the intersection of the elliptical cone with the y0 y1 -plane. 2 2.2 Skewed Elliptical Cones The use of the term right elliptical refers to the vector from ellipse origin to cone vertex is perpendicular to the ellipse plane. We can define an elliptical cone generally by allowing the cone vertex to be at a point ¯ = (¯ E e0 , e¯1 , e¯2 ) with e¯2 > 0 and the first two components not necessarily zero. The cone axis passes through ¯ E and the origin (0, 0, 0) but is no longer perpendicular to the ellipse plane. We wish to have an algebraic representation of this cone. Let us first look at a derivation that leads to equation (4). ¯ T Y + c¯, where as a 3-tuple, Y = (y0 , y1 , y2 ). The 3 × 3 matrix A¯ is symmetric, ¯ +B Define Q(Y) = YT AY ¯ is a 3 × 1 vector, and c¯ is a scalar. The right elliptical cone is represented by the quadratic equation B ¯ and c¯. Observe that the choices involve 10 parameters, 6 for A¯ = [¯ ¯ B, Q(Y) = 0 for some choice of A, aij ], 3 ¯ ¯ for B = [bj ], and 1 for c¯. 1. When y2 = 0, Q(Y) = 0 must reduce to the standard ellipse equation. Replacing y2 = 0 in the quadratic equation, h h i a i y0 ¯00 a ¯01 y0 + ¯b0 ¯b1 + c¯ = 0 y0 y1 a ¯01 a ¯11 y1 y1 To obtain the standard ellipse equation, we need a ¯00 = 1/d20 , a ¯01 = 0, a ¯11 = 1/d21 , ¯b0 = 0, ¯b1 = 0, and c¯ = −1. 2. The surface normal at the cone vertex is degenerate, so the gradient must be the zero vector: 0 = ¯ = 2A¯E ¯ + B. ¯ Using the information from item 1 and this constraint, we have a ∇Q(E) ¯02 = −¯ e0 /(¯ e2 d20 ), 2 2 2 2 2 2 ¯ a ¯12 = −¯ e1 /(¯ e2 d1 ), and 2¯ e2 a ¯22 + e¯2 b2 = 2(¯ e0 /d0 + e¯1 /d1 ). ¯ = 0, which implies e¯2 a 3. The cone vertex solves Q(E) ¯2¯b2 = 1 + (¯ e20 /d20 + e¯21 /d21 ). 2 ¯22 + e 4. Items 2 and 3 are solved for a ¯22 = (¯ e20 /d20 + e¯21 /d21 − 1)/¯ e22 and ¯b2 = 2/¯ e2 . We have determined A, B, and c, namely, 1/d20 0 ¯ A= 0 1/d21 −¯ e0 /(¯ e2 d20 ) −¯ e1 /(¯ e2 d21 ) −¯ e0 /(¯ e2 d20 ) −¯ e1 /(¯ e2 d21 ) ¯ , B = e22 (¯ e20 /d20 + e¯21 /d21 − 1)/¯ 0 0 2/¯ e2 , c¯ = −1 (5) Some factorization leads to the equation for the elliptical cone, 2.3 2 2 2 y0 e¯0 y2 y1 e¯1 y2 y2 −1 = − + − e¯2 d0 d0 e¯2 d1 d1 e¯2 (6) General Elliptical Cones In the most general case, the ellipse is not necessary in a coordinate-axis plane. Equation (2) is the equation for ellipse points, where (y0 , y1 ) solves equation (1). We want to determine A, B, and c for which Q(X) = 0 implicitly defines the elliptical cone with vertex E and contains the specified ellipse points Xe . 3 First, the ellipse points must satisfy 0 = Q(X) = XT AX + BT X + c, 0 = T XT e AXe + B Xe + c = (Ce + Je Ye ) A (Ce + Je Ye ) + BT (Ce + Je Ye ) + c T T T T YT Ye + CT e Je AJe Ye + Je (B + 2ACe ) e ACe + B Ce + c = T (7) Because Ye is a solution to the standard ellipse equation, T JeT AJe = Diagonal(1/d20 , 1/d21 ), JeT (B + 2ACe ) = (0, 0), CT e ACe + B Ce + c = −1 (8) which is a set of 6 linear equations in the unknowns. Second, the gradient of Q must be the zero vector at the cone vertex, ∇Q(E) = 2AE + B = 0 (9) which is a set of 3 linear equations in the unknowns. Third, the cone vertex is a solution to the quadratic equation, Q(E) = ET AE + BT E + c = 0 (10) which is 1 linear equation in the unknowns. Altogether we have 10 linear equations in the 10 unknowns, allowing us to use a linear system solver to obtain the solution. 2.4 Converting General Cones to Skewed Cones Alternatively, we may translate the ellipse center to the origin and then rotate the ellipse plane into a coordinate plane, thus transforming the problem to the one we know has the representation in equation (6). Let Re = [Ue Ve Ne ] be the rotation matrix whose columns are the right-handed orthonormal basis mentioned in the introduction. A point X in the current coordinate system is related to a point Y in the coordinate system of the skewed cone via the transformations X = Ce + Re Y, Y = ReT (X − Ce ) (11) ¯ = RT (E − Ce ) = (¯ The eyepoint E is transformed to an eyepoint E e0 , e¯1 , e¯2 ). Equation (6) provides the e ellipse representation 2 2 2 y0 e¯0 y2 e¯1 y2 y1 y2 −1 = − − + (12) e¯2 d0 d0 e¯2 d1 d1 e¯2 In summary, the vertex of the general elliptical cone is E. The ellipse consists of points Xe = Ce + y0 Ue + ¯ = RT (E − Ce ) and Re = [Ue Ve Ne ]. y1 Ve , where (y0 , y1 ) is a solution to equation (12) with E e For later use, we require the quadratic equation in the transformed coordinate system, 0 = XT AX + BT X + c T (Ce + Re Y) A (Ce + Re Y) + BT (Ce + Re Y) + c T T = YT ReT ARe Y + ReT (B + 2ACe ) Y + CT e ACe + B Ce + c = = ¯ T Y + c¯ ¯ +B YT AY 4 (13) ¯ and the scalar c¯; that is, ¯ the 3 × 1 vector B, where the last equality defines the 3 × 3 matrix A, ¯ = RT (B + 2ACe ), c¯ = CT ACe + BT Ce + c A¯ = ReT ARe , B e e (14) ¯ and c¯ are constructued using equation (5). This determines the coefficients of the X-quadratic; ¯ B, where A, ¯ e = RT Ce ; then define C e ¯ − 2A¯C ¯ e ), c = C ¯ T A¯C ¯e − B ¯ TC ¯ e + c¯ ¯ eT , B = Re (B A = Re AR e 3 (15) Projection of the Ellipse to Another Plane We now have a representation of the general elliptical cone that contains the eyepoint E and the user-specified ¯ and c¯ ¯ B, ellipse: XT AX + BT X + c = 0, where A, B, and c are defined by equation (15). The quantities A, ¯ = RT (E − Ce ) in the skewed ellipse equation (5). are determined using E e We have the projection plane, whose origin is the point Cp and unit-length normal is Np , and a right-handed orthonormal basis {Up , Vp , Np } that may be used to represent points relative to this plane. Assume that this projection plane intersects the cone in a closed curve, which is necessarily an ellipse. The plane points are specified by equation (3). To compute the intersection of cone and plane, substitute the plane points into the quadratic equation for the elliptical cone, 0 = T XT p AXp + B Xp + c = = (Cp + Jp Yp ) A (Cp + Jp Yp ) + BT (Cp + Jp Yp ) + c T T T T Yp + CT YT p ACp + B Cp + c p Jp AJp Yp + Jp (B + 2ACp ) = ˆ ˆ ˆ YT p AYp + B Yp + c T (16) T ˆ and cˆ; that is, ˆ B, where the last equality defines A, ˆ = J T (B + 2ACp ), cˆ = CT ACp + BT Cp + c Aˆ = JpT AJp , B p p (17) The equation for the projected ellipse may be factored into T (Yp − K) M (Yp − K) = 1, (18) ˆ ˆ T Aˆ−1 B/4 ˆ − cˆ). To obtain axis vectors and extents, you may apply ˆ B and M = A/( where K = −Aˆ−1 B/2 T an eigendecomposition of M = RDR . The columns of R are the axis vectors and the reciprocals of the diagonal entries of D are the squared extents. 5 The outline of the algorithm is listed next. 1. Inputs: (a) Eyepoint E. (b) Ellipse plane containing ellipse center Ce , unit-length normal Ne , and unit-length ellipse axes Ue and Ve . The matrix Re = [Ue Ve Ne ] is a rotation matrix. Ellipse axis lengths d0 (associated with Ue ) and d1 (associated with Ve ). Define Je = [Ue Ve ]. The ellipse points are Xe = Ce + Je Ye 2 2 with YT e Diagonal(1/d0 , 1/d1 )Ye = 1. (c) Projection plane with origin Cp , unit-length normal Np , and vectors Up and Vp that span the plane. The matrix Rp = [Up Vp Np ] is a rotation matrix. Define Jp = [Up Vp ]. The projected ellipse points are Xp = Cp + Jp Yp , and the goal is to determine a quadratic equation in Yp that represents this ellipse. 2. Compute: ¯ = RT (E − Ce ) = (¯ ¯ e = RT Ce . (a) E e0 , e¯1 , e¯2 ), C e e ¯ ¯ (b) From equation (5) compute A = [¯ aij ], B = [¯bj ], and c¯: a ¯00 = 1/d20 , a ¯11 = 1/d21 , a ¯01 = a ¯10 = 0, a ¯02 = a ¯20 = −¯ e0 /(¯ e2 d20 ), a ¯12 = a ¯21 = −¯ e1 /(¯ e2 d21 ), a ¯22 = (¯ e20 /d20 + e¯21 /d21 − 1)/¯ e22 , ¯b0 = 0, ¯b1 = 0, ¯b2 = 2/¯ e2 , c¯ = −1 (c) From equation (15) compute A, B, and c: ¯ − 2A¯C ¯ e ), c = C ¯ T A¯C ¯e − B ¯ TC ¯ e + c¯ ¯ eT , B = Re (B A = Re AR e ˆ and cˆ: ˆ B, (d) From equation (17) compute A, ˆ = J T (B + 2ACp ), cˆ = CT ACp + BT Cp + c Aˆ = JpT AJp , B p p 3. Outputs: (a) The quadratic equation ˆ ˆ YT ˆ p AYp + BYp + c that defines the projected ellipse. (b) The factored equation T (Yp − K) M (Yp − K) = 1, ˆ and M = A/( ˆ T Aˆ−1 B/4 ˆ − cˆ). ˆ B where K = −Aˆ−1 B/2 (c) Eigendecomposition RDRT = M , where the columns of R are the projected ellipse axis vectors and D = Diagonal(1/λ20 , 1/λ21 ). The projected ellipse axis lengths are λ0 and λ1 . 6

© Copyright 2018