## Re: [Algorithms] Transforming a [normal, D] plane

 Re: [Algorithms] Transforming a [normal, D] plane From: Eric Lengyel - 2000-11-23 23:42:04 ```> I'm having the problem: > At the start of the game, I create the 6 planes of the frustum. > Each plane is defined as > > struct TPlane{ > D3DVECTOR normal; > float D; > }; > > and, at the beginning of each frame, I have to update the planes by the view > matrix. How do I transform a plane defined like that? Assuming that a point P in your plane satisfies the equation P dot N = D then treat the plane as a four-vector with components (Nx, Ny, Nz, -D). This is a covariant vector, so it needs to be transformed by the inverse transpose of your 4x4 view matrix (I'm assuming you're referring to a world- to eye-space transformation): eye_space_plane = Transpose(Inverse(matrix)) * world_space_plane In the case that your view matrix is orthonormal (it probably is), then the inverse transpose matrix is the same as the original matrix. BTW, there is a D3DXPLANE structure available in DX8. You might also want to check out the D3DXPlaneTransform function. -- Eric Lengyel ```

 [Algorithms] Transforming a [normal, D] plane From: Jose Marin - 2000-11-23 18:43:48 ```Hi! I'm having the problem: At the start of the game, I create the 6 planes of the frustum. Each plane is defined as struct TPlane{ D3DVECTOR normal; float D; }; and, at the beginning of each frame, I have to update the planes by the view matrix. How do I transform a plane defined like that? Thanks in advance. Jose. _____________________________________________________________________________________ Get more from the Web. FREE MSN Explorer download : http://explorer.msn.com ```
 Re: [Algorithms] Transforming a [normal, D] plane From: David Hunt - 2000-11-23 19:34:09 ```> struct TPlane{ > D3DVECTOR normal; > float D; > }; > > How do I transform a plane defined like that? I'm not sure you can but the plane presumably came from a normal and a position on the plane. N and P. Where D=-N.P So if you define a second plane structure struct TNPPlane{ D3DVECTOR normal; D3DVECTOR pos; }; Transform those by the view matrix - remembering the normal is a vector - and then convert it to an ABCD plane. ```
 RE: [Algorithms] Transforming a [normal, D] plane From: Jon Creighton - 2000-11-23 22:31:26 ```You do not use the view matrix to transform normals, the transpose of the inverse must be used. D3DX has a function D3DXMatrixTranspose that will do this for you, but you will need to zero the translation components of the matrix too. Here's a little snippet of code that does it for me. D3DXMatrixTranspose(&matTransposed, &matView); matTranspose._14 = 0; matTranspose._24 = 0; matTranspose._34 = 0; for (int nPlane = 0; nPlane <= 5; ++nPlane) D3DXVec3Transform(&m_vecNormals[nPlane], &m_vecFixed[nPlane], &matTransposed); Hope this helps, Jon Creighton http://jon.creighton.com -----Original Message----- From: gdalgorithms-list-admin@... [mailto:gdalgorithms-list-admin@...]On Behalf Of David Hunt Sent: Friday, 24 November 2000 5:37 AM To: gdalgorithms-list@... Subject: Re: [Algorithms] Transforming a [normal, D] plane > struct TPlane{ > D3DVECTOR normal; > float D; > }; > > How do I transform a plane defined like that? I'm not sure you can but the plane presumably came from a normal and a position on the plane. N and P. Where D=-N.P So if you define a second plane structure struct TNPPlane{ D3DVECTOR normal; D3DVECTOR pos; }; Transform those by the view matrix - remembering the normal is a vector - and then convert it to an ABCD plane. _______________________________________________ GDAlgorithms-list mailing list GDAlgorithms-list@... http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list ```
 Re: [Algorithms] Transforming a [normal, D] plane From: Eric Lengyel - 2000-11-23 23:42:04 ```> I'm having the problem: > At the start of the game, I create the 6 planes of the frustum. > Each plane is defined as > > struct TPlane{ > D3DVECTOR normal; > float D; > }; > > and, at the beginning of each frame, I have to update the planes by the view > matrix. How do I transform a plane defined like that? Assuming that a point P in your plane satisfies the equation P dot N = D then treat the plane as a four-vector with components (Nx, Ny, Nz, -D). This is a covariant vector, so it needs to be transformed by the inverse transpose of your 4x4 view matrix (I'm assuming you're referring to a world- to eye-space transformation): eye_space_plane = Transpose(Inverse(matrix)) * world_space_plane In the case that your view matrix is orthonormal (it probably is), then the inverse transpose matrix is the same as the original matrix. BTW, there is a D3DXPLANE structure available in DX8. You might also want to check out the D3DXPlaneTransform function. -- Eric Lengyel ```
 Re: [Algorithms] Transforming a [normal, D] plane From: Eric Lengyel - 2000-11-24 06:22:28 ```> Assuming that a point P in your plane satisfies the equation > > P dot N = D > > then treat the plane as a four-vector with components (Nx, Ny, Nz, -D). > This is a covariant vector, so it needs to be transformed by the inverse > transpose of your 4x4 view matrix (I'm assuming you're referring to a world- > to eye-space transformation): > > eye_space_plane = Transpose(Inverse(matrix)) * world_space_plane > > In the case that your view matrix is orthonormal (it probably is), then the > inverse transpose matrix is the same as the original matrix. I take back the "probably" part. Your view matrix is probably NOT orthonormal because their will be some translation in the fourth column. So you're stuck with using the inverse transpose all the time for planes. (I was previously thinking along the line of transforming normals, for which the fourth column is irrelevant.) -- Eric Lengyel ```
 RE: [Algorithms] Transforming a [normal, D] plane From: John Mckenna - 2000-11-24 09:27:52 ```>> eye_space_plane = Transpose(Inverse(matrix)) * world_space_plane >> In the case that your view matrix is orthonormal (it probably is)... >I take back the "probably" part. Your view matrix is probably NOT >orthonormal because their will be some translation in the fourth >column. But it is probably an affine matrix, which isn't hard to invert. If R is the rotation part, and T is the translation part: M = ( R 0 ) ( T 1 ) then Inverse(M) is ( Inverse(R) 0 ) ( -T.Inverse(R) 1 ) (the . is a matrix multiplication) The rotation part is orthogonal, so just transpose it to invert. John -Virus Scanned and cleared ok ```
 Re: [Algorithms] Transforming a [normal, D] plane From: - 2000-11-24 21:00:41 ```Eric Lengyel wrote: >> Assuming that a point P in your plane satisfies the equation >> >> P dot N = D >> >> then treat the plane as a four-vector with components (Nx, Ny, Nz, -D). >> This is a covariant vector, so it needs to be transformed by the inverse >> transpose of your 4x4 view matrix (I'm assuming you're referring to a world- >> to eye-space transformation): >> >> eye_space_plane = Transpose(Inverse(matrix)) * world_space_plane >> >> In the case that your view matrix is orthonormal (it probably is), then the >> inverse transpose matrix is the same as the original matrix. > >I take back the "probably" part. Your view matrix is probably NOT >orthonormal because their will be some translation in the fourth column. So >you're stuck with using the inverse transpose all the time for planes. (I >was previously thinking along the line of transforming normals, for which >the fourth column is irrelevant.) But for transforming a vector, the translation part is irrelevant. True, you don't use the inverse transpose of the 4x4 affine matrix, but you do use the inverse transpose of the upper left 3x3 linear part, and since this is almost always orthogonal, it is almost always the 3x3 matrix itself. ```
 Re: [Algorithms] Transforming a [normal, D] plane From: Eric Lengyel - 2000-11-25 01:33:18 ```>>> Assuming that a point P in your plane satisfies the equation >>> >>> P dot N = D >>> >>> then treat the plane as a four-vector with components (Nx, Ny, Nz, -D). >>> This is a covariant vector, so it needs to be transformed by the inverse >>> transpose of your 4x4 view matrix (I'm assuming you're referring to a world- >>> to eye-space transformation): >>> >>> eye_space_plane = Transpose(Inverse(matrix)) * world_space_plane >>> >>> In the case that your view matrix is orthonormal (it probably is), then the >>> inverse transpose matrix is the same as the original matrix. >> >> I take back the "probably" part. Your view matrix is probably NOT >> orthonormal because their will be some translation in the fourth column. So >> you're stuck with using the inverse transpose all the time for planes. (I >> was previously thinking along the line of transforming normals, for which >> the fourth column is irrelevant.) > > But for transforming a vector, the translation part is irrelevant. > True, you don't use the inverse transpose of the 4x4 affine matrix, > but you do use the inverse transpose of the upper left 3x3 linear > part, and since this is almost always orthogonal, it is almost always > the 3x3 matrix itself. I'm treating planes as four-dimensional gradients of the function f(P) = P dot (Nx, Ny, Nz, -D) where P is a homogenous point. Our plane (Nx, Ny, Nz, -D) is exactly the gradient of f at any point P. (We are only interested in the isosurface where f(P) = 0.) Gradients are covariant vectors, so under a 4D coordinate transformation given by an arbitrary 4x4 matrix M, we have to use the inverse transpose of M to correctly transform the vector (Nx, Ny, Nz, -D). Now our 4D transformation matrices usually look like this: ( R11 R12 R13 Tx ) ( ) ( R21 R22 R23 Ty ) M = ( ) ( R31 R32 R33 Tz ) ( ) ( 0 0 0 1 ) Here R represents the rotation portion of the matrix and T the translation portion. If the 3x3 matrix R is orthonormal, then the inverse transpose of M looks like this: ( R11 R12 R13 0 ) ( ) -1 t ( R21 R22 R23 0 ) M = ( ) ( R31 R32 R33 0 ) ( ) ( t t t ) ( (-R T)x (-R T)y (-R T)z 1 ) t Here R T denotes the 3D matrix-vector product of R transpose and T. When this matrix transforms a plane (Nx, Ny, Nz, -D), it rotates N by the 3x3 matrix R, and it adds ((R transpose * T) dot N) to D. If the 3x3 matrix R is NOT orthonormal, then the inverse transpose of M looks like this: ( -1 -1 -1 ) ( (R )11 (R )21 (R )31 0 ) ( ) ( -1 -1 -1 ) -1 t ( (R )12 (R )22 (R )32 0 ) M = ( ) ( -1 -1 -1 ) ( (R )13 (R )23 (R )33 0 ) ( ) ( -1 -1 -1 ) ( (-R T)x (-R T)y (-R T)z 1 ) 1. Note the transposition of the indices in the 3x3 portion of the matrix. 2. This, of course, includes the previous case since when R is orthonormal, R inverse = R transpose. This shows that, in general, a plane's normal needs to be transformed by the inverse transpose of a 3x3 transformation matrix, and that the value of D should have the quantity ((R inverse * T) dot N) added to it. This is all accomplished by treating the plane as a 4D normal vector and transforming it by the inverse transpose of a 4D matrix. Knowing whether the upper right 3x3 matrix is orthonormal just makes the computation of the inverse a little easier. -- Eric Lengyel ```
 Re: [Algorithms] Transforming a [normal, D] plane From: - 2000-11-25 22:00:01 ```Eric Lengyel wrote: >>>> Assuming that a point P in your plane satisfies the equation >>>> >>>> P dot N = D >>>> >>>> then treat the plane as a four-vector with components (Nx, Ny, Nz, -D). >>>> This is a covariant vector, so it needs to be transformed by the inverse >>>> transpose of your 4x4 view matrix (I'm assuming you're referring to a world- >>>> to eye-space transformation): >>>> >>>> eye_space_plane = Transpose(Inverse(matrix)) * world_space_plane >>>> >>>> In the case that your view matrix is orthonormal (it probably is), then the >>>> inverse transpose matrix is the same as the original matrix. >>> >>> I take back the "probably" part. Your view matrix is probably NOT >>> orthonormal because their will be some translation in the fourth column. So >>> you're stuck with using the inverse transpose all the time for planes. (I >>> was previously thinking along the line of transforming normals, for which >>> the fourth column is irrelevant.) >> >> But for transforming a vector, the translation part is irrelevant. >> True, you don't use the inverse transpose of the 4x4 affine matrix, >> but you do use the inverse transpose of the upper left 3x3 linear >> part, and since this is almost always orthogonal, it is almost always >> the 3x3 matrix itself. > >I'm treating planes as four-dimensional gradients of the function > >f(P) = P dot (Nx, Ny, Nz, -D) > >where P is a homogenous point. Our plane (Nx, Ny, Nz, -D) is exactly the >gradient of f at any point P. (We are only interested in the isosurface >where f(P) = 0.) Gradients are covariant vectors, so under a 4D coordinate >transformation given by an arbitrary 4x4 matrix M, we have to use the >inverse transpose of M to correctly transform the vector (Nx, Ny, Nz, -D). >Now our 4D transformation matrices usually look like this: > > ( R11 R12 R13 Tx ) > ( ) > ( R21 R22 R23 Ty ) >M = ( ) > ( R31 R32 R33 Tz ) > ( ) > ( 0 0 0 1 ) > So you are an operator-on-leftist. I can live with that, but remember that D3D users will have to transpose this. >Here R represents the rotation portion of the matrix and T the translation >portion. If the 3x3 matrix R is orthonormal, then the inverse transpose of >M looks like this: > > ( R11 R12 R13 0 ) > ( ) > -1 t ( R21 R22 R23 0 ) >M = ( ) > ( R31 R32 R33 0 ) > ( ) > ( t t t ) > ( (-R T)x (-R T)y (-R T)z 1 ) > > t >Here R T denotes the 3D matrix-vector product of R transpose and T. When >this matrix transforms a plane (Nx, Ny, Nz, -D), it rotates N by the 3x3 >matrix R, and it adds ((R transpose * T) dot N) to D. > >If the 3x3 matrix R is NOT orthonormal, then the inverse transpose of M >looks like this: > > ( -1 -1 -1 ) > ( (R )11 (R )21 (R )31 0 ) > ( ) > ( -1 -1 -1 ) > -1 t ( (R )12 (R )22 (R )32 0 ) >M = ( ) > ( -1 -1 -1 ) > ( (R )13 (R )23 (R )33 0 ) > ( ) > ( -1 -1 -1 ) > ( (-R T)x (-R T)y (-R T)z 1 ) > >1. Note the transposition of the indices in the 3x3 portion of the matrix. >2. This, of course, includes the previous case since when R is orthonormal, >R inverse = R transpose. > >This shows that, in general, a plane's normal needs to be transformed by the >inverse transpose of a 3x3 transformation matrix, and that the value of D >should have the quantity ((R inverse * T) dot N) added to it. ... > This is all >accomplished by treating the plane as a 4D normal vector and transforming it >by the inverse transpose of a 4D matrix. Knowing whether the upper right >3x3 matrix is orthonormal just makes the computation of the inverse a little >easier. > IMO, the whole derivation is a lot easier if you do not go via the roundabout path of homogeneous coordinates and 4D gradients, but rather stick to intuitive elementary 3D vector geometry. In general, I think the use of 4x4 matrices and homogeneous coordinates for affine transformations is pretty silly. Better to keep in mind the intrinsic geometry of an affine transformation A = [L, T], as a pair consisting of a 3D linear transformation L (leaving some origin fixed) followed by a translation defined by a 3-vector T. Of course, when you introduce a particular coordinate system, then L has expression as a 3x3 matrix and T as a column vector, or 3x1 matrix, and these can be combined into a 3x4 matrix that represents the affine transformation, which you can, if you like, augment to a 4x4 matrix by adding the useless, information-free last row of 0 0 0 1, but which augmentation I find silly. The affine transformation A =[L,T] operates on any point with position vector v thusly: v -> v' = Av = Lv + T (where I am conforming to the operator-on-left convention you have established). Now, in this notation and under this convention, it is trivial to verify that affine transformations are concatenated thusly: A A' = [L,T][L',T'] = [LL', LT' + T] and trivial to verify that an affine transformation is invertible if and only if its linear part L is invertible and in that case its inverse is given by Ainv = [L,T]inv = [Linv, - LinvT], where I use Oinv for the inverse of an operator O. All the foregoing is not specific to the question of transforming a plane, but rather just general basic facts about affine transformations the way I like to think about them, facts which ought to be burned into our brain because we will be using them again and again in our continuing adventures with 3D graphics. One more important general basic fact, equally trivial to verify from the definitions: if u and v are any column vectors (3x1 matrices) and M is any 3x3 matrix then u dot (Mv) = (Mtr u) dot v, where I use Mtr for the transpose of a matrix M. NOW, with those preparations, let's look at how to transform a plane N dot P = D by an affine transformation A = [L,T]. By considering the logic of mappings it ought to be clear that a point P is on the transformed plane if and only if it satisfies the equation N dot (Ainv P) = D (because if P is on the transformed plane then (Ainv P) must be on the untransformed plane and vice versa) or, applying the expression for the inverse of an affine mappig N dot ([Linv, -Linv T]P) = D or, applying the above rule for the action of affine transformations on a vector N dot (Linv P -Linv T) = D or, applying the linearity of dot product (a fundamental algebraic property of dot product which we must never forget) N dot (Linv P) - N dot (Linv T) = D N dot (Linv P) =D + N dot (Linv T)) Then, using the rule on dot product from above (((Linv)tr)N) dot P = D + N dot (LinvT)) or N' dot P = D' (the familiar equation of a plane) where N' = ((Linv)tr)N and D' = D + N dot(Linv T) which is, of course, exactly the same as your result, but derived without any mention of homogeneous coordinates, 4D gradients, the covariant-contravariant dichotomy, and without writing out any ugly 4x4 matrices, but instead couched in terms of the much more elementary and intuitive 3-vector geometry of affine transformations. Moreover, another thing I like about my deriviation and my approach is that they are more manifestly coordinate invariant. (The importance of coordinate invariance is a key theme stressed in the book I am writring). Note that my result holds for ANY invertible affine transformation, not just those whose linear part L is a rotation. Of course, if L is a rotation, or more generally orthogonal, then (Linv)tr = L, yielding some simplification. ```
 Re: [Algorithms] Transforming a [normal, D] plane From: Eric Lengyel - 2000-11-26 01:15:19 ```Ron Levine wrote: > So you are an operator-on-leftist. I can live with that, but remember > that D3D users will have to transpose this. Yeah, I know. I'm an OpenGL guy. Column vectors just seem more natural to me -- must be because I was raised on left handed operators. > IMO, the whole derivation is a lot easier if you do not go via the > roundabout path of homogeneous coordinates and 4D gradients, but > rather stick to intuitive elementary 3D vector geometry. In general, > I think the use of 4x4 matrices and homogeneous coordinates for affine > transformations is pretty silly. Better to keep in mind the intrinsic > geometry of an affine transformation A = [L, T], as a pair consisting > of a 3D linear transformation L (leaving some origin fixed) followed > by a translation defined by a 3-vector T. Of course, when you > introduce a particular coordinate system, then L has expression as a > 3x3 matrix and T as a column vector, or 3x1 matrix, and these can be > combined into a 3x4 matrix that represents the affine transformation, > which you can, if you like, augment to a 4x4 matrix by adding the > useless, information-free last row of 0 0 0 1, but which augmentation > I find silly. I understand where you're coming from. I find using 4x4 matrices to be convenient for doing things like concatenating a perspective projection matrix to an affine transformation matrix. It just gives the whole system a nice uniform feeling. The vector units in next-generation 3D hardware are also very well suited for 4D mathematics. > [long derivation removed] > > which is, of course, exactly the same as your result, but derived > without any mention of homogeneous coordinates, 4D gradients, the > covariant-contravariant dichotomy, and without writing out any ugly > 4x4 matrices, but instead couched in terms of the much more elementary > and intuitive 3-vector geometry of affine transformations. Moreover, > another thing I like about my deriviation and my approach is that they > are more manifestly coordinate invariant. (The importance of > coordinate invariance is a key theme stressed in the book I am > writring). I can appreciate the advantages of your derivation. What book are you writing? (Coincidentally, I am also writing a book at the moment about mathematics for game programming. Of course, I would not jump straight into all this 4D stuff, but I would like to cover it in some way.) -- Eric Lengyel ```