×

### Let's log you in.

or

Don't have a StudySoup account? Create one here!

×

or

## Computer Graphics

by: Khalil Conroy

30

0

11

# Computer Graphics CAP 4720

Khalil Conroy
University of Central Florida
GPA 3.76

Staff

These notes were just uploaded, and will be ready to view shortly.

Either way, we'll remind you when they're ready :)

Get a free preview of these Notes, just enter your email below.

×
Unlock Preview

COURSE
PROF.
Staff
TYPE
Class Notes
PAGES
11
WORDS
KARMA
25 ?

## Popular in System Engineering

This 11 page Class Notes was uploaded by Khalil Conroy on Thursday October 22, 2015. The Class Notes belongs to CAP 4720 at University of Central Florida taught by Staff in Fall. Since its upload, it has received 30 views. For similar materials see /class/227225/cap-4720-university-of-central-florida in System Engineering at University of Central Florida.

×

## Reviews for Computer Graphics

×

×

### What is Karma?

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/22/15
Fast Extraction of Viewing Frustum Planes from the World ViewProjection Matrix Authors in alphabetical order Gil Gribb Klaus Hartmann ggribb ravensoftcom k hartmann osnabrueck netsurfde 1 Introduction We present an algorithm for extracting the six viewing frustum planes directly from the combined world view and projection matrices The algorithm is fast accurate and general It allows one to quickly determine the frustum planes in camera space world space or object space The paper is divided into two main chapters The first chapter quotPlane Extraction in Direct3D shows how to extract the viewing frustum planes in Direct3D and the second chapter quotPlane Extraction in OpenGLquot shows how to do the same in OpenGL In addition there are two appendices Appendix A reviews some of the maths behind plane equations and Appendix B contains sample implementations of the plane extraction algorithm for both Direct3D and OpenGL We hope you enjoy this short paper Gil Gribb Klaus Hartmann 06152001 2 Plane Extraction in Direct3D We start off by extracting the frustum planes from the projection matrix only That is the world and view matrices are both identity matrices This means that the camera is located at the origin of the world coordinate system and we are looking along the positive zaxis Let V x y Z w 1 be a vertex and let M my be a 4X 4projection matrix Transforming the vertex V with the matrix M results in the transformed vertex V 39 x y 239 w This can be written as T T xmnym21zm31wm41 Vocol1 VvVM3xv yr Zr WV xMZy39m22Z39m32w39m42 v6012 cm13ym23zm33wm43 Vocol3 xmmym24zm34wm44 Vocol4 where 0 denotes the dot product and col j m1 j m2 m3 m denotes the vector represented by the jm column of matrix M For example V 0 col2 denotes the dot product of Vwith the vector represented by the 2nd column of matrix M After this transformation the vertex V39 is in homogeneous clipping space In this space the viewing frustum actually is an axisaligned box whose size is APTspecific If vertex V 39 is inside this box then the untransformed vertex V is inside the 39untransformed39 viewing frustum Using Direct3D the vertex V 39 is inside the box if the following inequalities are all true for the components of V39 w39 lt x lt w w lt y lt w 0 lt z lt w There are a couple conclusions we can draw from these inequalities They are listed in the following table If w lt x then 39 is in the insidehalfspace of the left clipping plane If x lt w then is in the insidehalfspace of the right clipping plane If w lt y then is in the insidehalfspace of the bottom clipping plane If y lt w then is in the insidehalfspace of the top clipping plane If 0 lt 239 then 39 is in the insidehalfspace of the near clipping plane NN lt ltgtltgtlt If 239 lt w then is in the insidehalfspace of the far clipping plane Now suppose that we wanted to test if x is in the insidehalfspace of the left clipping plane This is the case if the following inequality is true w lt x Using the information from the beginning of this chapter we can rewrite this inequality as v o 0014 lt V0 coll This in turn is equal to 0 lt V00014Vocoll And finally 0 lt Vocol4 0011 This already represents the plane equation for the left clipping plane of the 39untransformed39 viewing frustum xm14 mn ym24 m21 zm34 m31 wm44 m 0 Since w l we can simplify this as follows xm14 mnym24 m21zm34 m31m44 m 0 This gives a standard plane equation axbyczd 0 where am14m119 bm24m21a cm34m319 dm44m41 We have now shown that the left clipping plane of the viewing frustum can be directly extracted from the projection matrix It is important to note that the resulting plane equation is not normalized ie the plane s normal vector is not a unit vector and that the normal vector is pointing to the inside halfspace This means that 0 lt ax by CZ d if the vertex V is in the inside halfspace of the left clipping plane We can now repeat the above steps for the other inequalities to determine the plane equations for the remaining clipping planes Clipping plane Inequality Coef cients for the plane equation left w lt x a m14 m11 V0 0014 lt v0 coll b m24 m21 0 lt V00014Vocoll CW134m31 0 lt vo0014coll cim44m41 right x lt w ami4m11 Vocoll lt vocol4 bm24 m21 0 lt V00014 vocoll cm34 m31 0 lt Vo0014 coll almM m41 bottom w39 lt yr a m14 mu V0 0014 lt v0 col2 b m24 m22 0 lt V00014vocolz crr134m32 0 lt Vo0014colz cim44m42 top y39 lt w amM m12 Vocol2 lt Vocol4 bm24 m 0 lt V00014 vocolz cm34 m32 0 lt Vo0014 colz cim44 m42 near a mm 0 lt ZV b Mn 0 lt V o col3 C mas d m43 far 239 lt w amM m13 v0 col3 lt Vocol4 b m24 m23 0 lt V00014 V00013 cm34 m33 0 lt Vo0014 c013 cimM m43 21 Supporting NonIdentity World and View Matrices Until now we have assumed that both the world and the view matrix are identity matrices However the goal obviously is to make the algorithm work for an arbitrary view This is in fact so easy that it s almost unbelievable If you think about it for a moment then you ll immediately understand it and that s why we are not going to explain this in any great detail All we are giving to you is this 1 If the matrixM is equal to the projection matrix P ie M P then the algorithm gives the clipping planes in view space ie camera space 2 If the matrixMis equal to the combined view and projection matrices then the algorithm gives the clipping planes in world space ie M V P where V is the view matrix and P is the projection matrix 3 If the matrix Mis equal to the combined world view and projection matrices then the algorithm gives the clipping planes in object space ie M W V P where W is the world matrix V is the view matrix and P is the projection matrix 4 and so on 3 Plane Extraction in OpenGL We start off by extracting the frustum planes from the projection matrix only That is the modelview matrix is an identity matrix This means that the camera is located at the origin of the world coordinate system and we are looking along the positive zaxis Let V x y Z w1T be a vertex and let M my be a 4gtlt4projection matrix Transforming the T vertex Vw1ththe matrix Mresults1nthe transformedvertex V39x39 y 239 w Th1scanbewr1ttenas Cy JC VVIII l J VVIIZ l Z I VIl3 l39lV I Vl14 V39rOlV1 Jy X m Z m V39rOW 21 22 23 24 2 Z X n lm l J VVISZ l Z I VlSS l39lV I Vl34 V39rOlV3 w xm41ym42zm43wm44 Vorow4 where 0 denotes the dot product and row mm mm m3 m1 4 denotes the vector represented by the I39m row of matrix M For example V 0 row2 denotes the dot product of V with the vector represented by the 2quotd row of matrix M After this transformation the vertex V39 is in homogeneous clipping space In this space the viewing frustum actually is an axisaligned box whose size is APTspecific If vertex V 39 is inside this box then the untransformed vertex V is inside the 39untransformed39 viewing frustum Using OpenGL the vertex V39 is inside the box if the following inequalities are all true for the components of V39 w39 lt x lt w w39 lt y39 lt w w ltz ltw There are a couple conclusions we can draw from these inequalities They are listed in the following table If w lt x then 39 is in the insidehalfspace of the left clipping plane If x lt w then is in the insidehalfspace of the right clipping plane If w lt y then is in the insidehalfspace of the bottom clipping plane If y lt w then is in the insidehalfspace of the top clipping plane If w lt 239 then is in the insidehalfspace of the near clipping plane NN lt ltgtltgtlt If Zlltwl then is in the insidehalfspace of the far clipping plane Now suppose that we wanted to test if x is in the insidehalfspace of the left clipping plane This is the case if the following inequality is true w lt x Using the information from the beginning of this chapter we can rewrite this inequality as v 0 row lt V o rowl This in tuIn is equal to 0 lt VOFOW4VOVOW1 And finally 0 lt V o row4 rowl This already represents the plane equation for the left clipping plane of the 39untransformed39 viewing frustum xm41 mn ym42 mu zm43 m13 wm44 m 0 Since w l we can simplify this as follows xm41 mnym42 muzm43 rr113m44 m 0 This gives a standard plane equation axbyczd 0 where am41m119 bm42m129 cm43m139 dm44mm We have now shown that the left clipping plane of the viewing frustum can be directly extracted from the projection matrix It is important to note that the resulting plane equation is not normalized ie the plane s normal vector is not a unit vector and that the normal vector is pointing to the inside halfspace This means that 0 lt ax by CZ d if the vertex V is in the inside halfspace of the left clipping plane We can now repeat the above steps for the other inequalities to determine the plane equations for the remaining clipping planes Clipping plane Inequality Coef cients for the plane equation left w lt x a quot141 mil V 0 row lt V o row1 b m42 m12 0 lt VOFOW4VOVOW1 cm43m13 0 lt V0VOW4VOW1 alm44m14 right x lt w am41 m11 Vorow1 lt vorow4 bm42 m12 0 lt VOFOW4 VOVOW1 cm43 m13 0 lt V0VOW4 VOW1 almM m14 bottom w lt y a quot 41 mzi V 0 row lt V o row2 b m42 m22 0 lt VOVOW4VOFOW2 cm43m23 0 lt V0VOW4VOW2 alm44m24 top y39 lt w a m41 m Vorow2 lt Vorow4 bm42 m 0 lt VOVOW4 VOVOW2 cm43 m23 0 lt V0VOW4 VOW2 dm44 m near w lt Z39 a m41 m31 V 0 row lt V 0 row3 b m42 m32 0 lt VOVOW4VFOW3 cm43m33 0 lt V0row4 row3 d m44 m34 far 2 lt w am41 m31 V o row3 lt V0 row4 b m42 m32 0 lt VOVOW4 VOFOW3 cm43 m33 0 lt V0VOW4 VOW3 almM m34 31 Supporting a NonIdentity Modelview Matrix Until now we have assumed that the modelview matrix is an identity matrices However the goal obviously is to make the algorithm work for an arbitrary view This is in fact so easy that it s almost unbelievable If you think about it for a moment then you ll immediately understand it and that s why we are not going to explain this in any great detail All we are giving to you is this 1 If the matrixM is equal to the projection matrix P ie M P then the algorithm gives the clipping planes in view space ie camera space 2 If the matrixMis equal to the combined projection and modelview matrices then the algorithm gives the clipping planes in model space ie V P M where V is the modelview matrix and P is the projection matrix Appendix A Plane Equations Given a fixed pointp and a nonzero normal vector 11 a plane is defined as the set of all points X x y Z such that nox p 0 In English that means that the vector from pto any point X is orthogonal perpendicular to the plane s normal vector 11 if the point X is on the plane Remember that the dot product of two vectors is zero if the angle between those two vectors is 90 degrees We are now going to bring the plane equation 11 0 X p 0 into another form nox p0 ls equal to nx np0 If n a b c then we can rewrite the above as axbycz nop 0 The term n 0 p is constant and we now define that d n 0 p Thus the plane equation becomes axbyczd 0 It should be noted that many people prefer to use the form ax by CZ d In this case the constant 61 is defined as d nop For use in a computer language we can store such a plane equation in a simple structure struct Plane float a b C d l A1 Halfspaces A plane cuts threedimensional space into two separate parts These parts are called halfspaces The halfspace the plane s normals vector points into is called the positive halfspace and the other halfspace is called the negative halfspace A2 Normalizing the Plane Equation Normalizing a plane equation ax bycz d 0 means to change the plane equation such that the normal vector 11 a b 0 becomes a unit vector ie 1 All we need to do to normalize a vector is to divide each of its components by the magnitude of the vector However in order to normalize a plane equation it is not enough to simply divide the coefficients a b c by the magnitude of the normal vector 11 We also need to divide the constant 61 by the magnitude of the normal vector 11 n o x p 0 First we normalize n by dividing its components by the magnitude of n moo pm ll39I nxJt upio This is equal to If n a b c then we can rewrite the above as ixiyiz iop 0 Hull llnll llnll llnll Now define 61 nop ixiyLzi 0 IIIquot Hull Hull Hull Which is equal to a b c d x l l lazb2c2 Ja2b2czy aZb2c2 lazb2c2 Now simplify ax by 02 d la2 12 So in order to normalize a plane equation we need to divide the coefficients a bc and the constant 61 by the 0 magnitude of the normal vector 11 a b c It is useful to have a function that does this for you void NormalizePlanePlane amp plane float mag mag sqrtplanea planea planeb planeb planec planec planea planea mag planeb planeb mag planec planeC mag planed planed mag A3 The Signed Distance From a Plane to a Point It is more than often necessary to compute the shortest signed distance from a given plane CDC by CZ d 0 to a point p x y Z As it turns out we can simply plug the coordinates of the point p into the plane equation and the result is the signed distance from the plane top This distance however is not necessarily a 39true39 distance Instead it is the signed distance in units of the magnitude of the plane s normal vector 11 a b c So in order to obtain a 39true39 distance you need to normalize the plane equation float DistanceToPointconst Plane amp plane const Point amp pt return planeaptx planebpty planecptz planed If the plane equation is not normalized then we can still get some valuable information from the 39non true distance dist 1 If dist lt 0 then the point p lies in the negative halfspace 2 If dist 0 then the point p lies in the plane 3 If dist gt 0 then the point p lies in the positive halfspace This gives us another useful function that also works for nonnormalized plane equations enum Halfspace NE GAT IVE l oNiPLANE 0 POS IT IVE l l Halfspace ClassifyPointconst Plane amp plane const Point amp pt float d d planeaptx planebpty planecptz planed if d lt 0 return NEGATIVE if d gt 0 return POSITIVE return ONiPLANE Appendix B Implementation In the following we are going to give sample implementations of the plane extraction method for both OpenGL and Direct3D Note that the normal vectors of the resulting planes are pointing to the inside of the viewing frustum If you prefer planes where the normal vectors are pointing to the outside then all you need to do is to negate the coefficients a b c and the constant d of each plane equation 31 Plane Extraction for OpenGL struct Matrix4x4 The elements of the 4x4 matrix are stored in column major order see quotOpenGL Programming Guidequot 3m edition pp 106 glLoadMatrix float ll 21 31 4l float 12 22 32 42 float 13 23 33 43 float 714 724 734 744 l void ExtractPlanesGL ane piplanes const Matrix4x4 amp comboMatrix bool normalize Left clipping plane B2 Plane Extraction for Direct3D p7planesOa comboMatrix p7planesOb comboMatrix p7planesOo comboMatrix p planesOd comboMatrix7 Right clipping plane p7planes1a comboMatrix p planes1 b comboMatrix pplanes1o comboMatrix p planes1 d comboMatrix7 Top clipping plane p7planes2a comboMatrix p planes2b comboMatrix piplanes2o comboMatrix piplanes2d comboMatrix7 Bottom clipping plane p7planes3a comboMatrix p7planes3 b comboMatrix p7planes3o comboMatrix p planes3 d comboMatrix7 Near clipping plane p planes4a comboMatrix pplanes4 b comboMatrix p planes4c comboMatrix piplanes4 d comboMatrix7 Far clipping plane p planes5a comboMatrix piplanes5b comboMatrix pplanes5o comboMatrix p planes5d comboMatrix7 Normalize the plane equations if normalize true NormalizePlane p7planes NormalizePlane NormalizePlane NormalizePlane NormalizePlane NormalizePlane p7planes pplanes struct Matrix4x4 comboMatrix 11 comboMatrix12 comboMatrix 13 comboMatrix14 comboMatrix711 comboMatrix 12 comboMatrix13 comboMatrix714 comboMatrix721 comboMatrix 22 comboMatrix723 comboMatrix24 comboMatrix 21 comboMatrix22 comboMatrix 23 comboMatrix24 comboMatrix 31 comboMatrix32 comboMatrix 33 comboMatrix34 comboMatrix 31 comboMatrix732 comboMatrix33 comboMatrix734 if requested The elements of the 4x4 matrix are stored in row major order float 711 712 713 714 float 21 22 23 24 float 31 32 33 34 float 741 742 743 744 void ExtractPlanesD3D Plane piplanes const Matrix4x4 amp comboMatrix bool normalize Left clipping plane piplanesOa comboMatrix piplanesOb comboMatrix piplanesOc comboMatrix p planesOd comboMatrix7 Right clipping plane p planesla comboMatrix p planeslb comboMatrix pplaneslc comboMatrix p planesld comboMatrix7 Top clipping plane piplanes2a comboMatrix p planes2b comboMatrix pplanes2c comboMatrix p planes2d comboMatrix7 Bottom clipping plane piplanes3a comboMatrix p planes3b comboMatrix pplanes3c comboMatrix p planes3d comboMatrix7 Near clipping plane p planes4a comboMatrix pplanes4b comboMatrix p planes4c comboMatrix piplanes4d comboMatrix Far Clipping plane p planes5a comboMatrix pplanes5b comboMatrix p planes5c comboMatrix piplanes5d comboMatrix 14 24 34 44 Normalize the plane equations if normalize true NormalizePlane piplanes NormalizePlane NormalizePlane NormalizePlane NormalizePlane NormalizePlane piplanes pplanes comboMatrix ll comboMatrix2l comboMatrix 31 comboMatrix4l comboMatrix ll comboMatrix72l comboMatrix3l comboMatrix74l comboMatrix7l2 comboMatrix 22 comboMatrix32 comboMatrix742 comboMatrix7l2 comboMatrix 22 comboMatrix32 comboMatrix742 comboMatrix l3 comboMatrix23 comboMatrix 33 comboMatrix43 if requested

×

×

### BOOM! Enjoy Your Free Notes!

×

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

Jim McGreen Ohio University

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Kyle Maynard Purdue

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made \$280 on my first study guide!"

Jim McGreen Ohio University

Forbes

#### "Their 'Elite Notetakers' are making over \$1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!
×

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com