Clipping & Scan ConversionCSE167: Computer GraphicsInstructor: Steve RotenbergUCSD, Fall 2005Project 2Render a 3D hand (made up of individual boxes) using hierarchical transformations (push/pop)The hand should perform some simple motion, such as opening and closing the fingersEnable some basic lightingUse object oriented classes for:Model (like project 1)Hand (& Finger if you want)CameraLightExample: YawA spaceship is floating out in space, with a matrix W. The pilot wants to turn the ship 10 degrees to the left (yaw). Show how to modify W to achieve this.Example: YawWe rotate W around its own b vector, using the ‘arbitrary axis rotation’ matrix. In addition, we pivot the rotation about the object’s position (d vector):where Ra(a,θ)=( ) ( ) ( )WMWdWTbWRdWTM⋅=′−⋅°⋅= .10,..a−++−−−−−−++−+−−−−+10000)1()1()1(0)1()1()1(0)1()1()1(222222zzxzyyzxxzyyyzyxyzxzyxxxacasacaasacaasacaaacasacaasacaasacaaacaθθθθθθθθθθθθθθθTriangle RenderingThe main stages in the traditional graphics pipeline are:TransformLightingClipping / CullingScan ConversionPixel RenderingTransformationIn the transformation stage, vertices are transformed from their original defining object space through a series of steps into a final ‘2.5D’ device space of actual pixels( )vDvvvWCPv′′⋅=′′′′′′′′′=′′⋅⋅⋅=′−wzwywxDvvvvvv14Transformation: Step 1v: The original vertex in object spaceW: Matrix that transforms object into world spaceC: Matrix that transforms camera into world space (C-1 will transform from world space to camera space)P: Non-affine perspective projection matrixv′: Transformed vertex in 4D un-normalized viewing spaceNote: sometimes, this step is broken into two (or more) steps. This is often done so that lighting and clipping computations can be done in camera space (before applying the non-affine transformation)( )vWCPv ⋅⋅⋅=′−14DTransformation: Step 2In the next step, we map points from 4D space into our normalized viewing space, called image space, which ranges from -1 to 1 in x, y, and zFrom this point on, we will mainly think of the point as being 2D (x & y) with additional depth information (z). This is sometimes called 2.5D′′′′′′=′′wzwywxvvvvvvvTransformation: Step 3In the final step of the transformation stage, vertices are transformed from the normalized -1…1 image space and mapped into an actual rectangular viewport of pixelsvDv′′⋅=′′′Transformation( )vDvvvWCPv′′⋅=′′′′′′′′′=′′⋅⋅⋅=′−wzwywxDvvvvvv14Clipping & CullingClippingSome triangles will be completely visible on the screen, while others may be completely out of viewSome may intersect the side of the screen and require special handlingThe camera’s viewable space forms a volume called the view volume. Triangles that intersect the boundary of the view volume must be clipped.The related process of culling refers to the determination of which primitives are completely invisibleThe output of the clipping/culling process is a set of visible triangles that lie within the dimensions of the display deviceClippingTriangles are generally clipped one at a time, although more complex implementations might do them in groupsWe will just consider the clipping of a single triangleBoth perspective and orthographic view volumes are bounded by 6 planes, and so can be treated very similarlyA single triangle could potentially intersect all 6 planes (although it would be pretty uncommon for a triangle to intersect more than 2 in practice)The number of planes isn’t actually that important, since the basic algorithm clips to each plane one at a timeClippingIf a triangle intersects a particular clipping plane, it will become either one or two new trianglesThese are then tested against the remaining clipping planesInsideOutsideClippingTo clip a triangle to a particular clipping plane, we first have to determine which of the triangle’s 3 vertices are on which side of the planeIf all 3 vertices are on the ‘inside’, then the triangle doesn’t need to be clippedIf all 3 vertices are on the ‘outside’, then the triangle is completely invisible and gets thrown away (culled)If only 1 vertex is inside, then two new vertices must be (temporarily) created and a single new triangle is createdIf 2 verts are inside, then two new vertices must be created as well as two new trianglesBoth of the clipping cases involve finding where 2 edges of the triangle intersect the plane, and so can be treated very similarlyClipping: Inside/Outside TestingA clipping plane can be defined by a point p on the plane and a unit length normal n, (we will choose n so that it points towards the inside of the view volume)To test if a triangle’s verts are inside or outside of the clipping plane, we compute a signed distance to the plane for each of the 3 vertices, v0, v1, and v2A positive (or 0) distance indicates that the vertex is inside the view volume, and negative distance indicates that it is outside( )( )( )npvnpvnpv⋅−=⋅−=⋅−=221100dddClipping: Edge/Plane IntersectionTo find point x where an edge intersects a plane, we need the two verts va and vb that make up the edge, as well as their signed distances da and db( )baabbttdddtvvx −+=−=1Clipping: SpacesClipping can be done in just about any space desiredIt is common to perform clipping in camera space, as it is a regular 3D space and the clipping planes are conveniently described in this spaceThis necessitates transforming verts into camera space, then clipping, then transforming them into 4D un-normalized view spaceIf one is clever, this can be sped up and clipping can be performed in 4D un-normalized space, eliminating the need to transform the vertex through two separate matricesClipping: SetupIn preparation for the clipping process, it is useful to pre-compute the normals for the 6 planes in the view volumeThese can be done once per frame when the projection matrix is specified (before the actual rendering begins)CullingIn computer graphics, culling refers to the process of determining what is not visibleThe sooner we can detect that a triangle is not going to be visible, the less time has to be
View Full Document