Visibility - Part IBack-Face CullingPainter's Algorithm Lecture 14 Slide 1 6.837 Fall '00Lecture 14 --- 6.837 Fall '00http://graphics.lcs.mit.edu/classes/6.837/F00/Lecture14/Slide01.html [11/7/2000 4:35:53 PM]Visibility ProblemThe problem of visibility is to determine which transformed, illuminated, and projectedprimitives contribute to pixels on the screen. In many cases, however, rather than solving thedirect problem of determining what is visible, we will instead address the converse problem ofeliminating those primitives that are invisible.A primitive can be invisible for one ofthree reasons:It lies outside of the field of view1. It is a back-facing component of aclosed object2. It is occluded by some object closer tothe viewpoint3. Lecture 14 Slide 2 6.837 Fall '00Lecture 14 --- 6.837 Fall '00http://graphics.lcs.mit.edu/classes/6.837/F00/Lecture14/Slide02.html [11/7/2000 4:36:03 PM]Outside the Field-of-ViewClipping, as we discussed the lecture before last, addresses the problem of removing thoseobjects outside of the field of view. Outcode clipping attempted to remove all those objects thatwere entirely outside of the field of view (it came up a little short of that goal, however).Frustum clipping, as demonstrated by the plane-at-a-time approach that we discussed, removedportions of objects that were partially inside of and partially outside of the field of view. Lecture 14 Slide 3 6.837 Fall '00Lecture 14 --- 6.837 Fall '00http://graphics.lcs.mit.edu/classes/6.837/F00/Lecture14/Slide03.html [11/7/2000 4:36:05 PM]Back-Face CullingBack-face culling addresses a special case of occlusion called convex self-occlusion. Basically,if an object is closed (having a well defined inside and outside) then some parts of the outersurface must be blocked by other parts of the same surface. We'll be more precise with ourdefinitions in a minute. On such surfaces we need only consider the normals of surfaceelements to determine if they are invisible.We can apply back-face culling to any orientable two-manifold. Orientable two-manifolds havethe following properties.Everywhere on their surface, they are locally like a plane. They have no holes, cracks,or self-intersections.1. Their boundary partitions 3D space into interior and exterior regions.2. In our case, manifolds will be composite objects made of many primitives, generally triangles.Back-face culling eliminates a subset of these primitives & assumes that you are outside of allobjects.Lecture 14 Slide 4 6.837 Fall '00Lecture 14 --- 6.837 Fall '00http://graphics.lcs.mit.edu/classes/6.837/F00/Lecture14/Slide04.html [11/7/2000 4:36:06 PM]Removing Back-FacesIdea: Compare the normal of each face with the viewing directionGiven n, the outward-pointing normal of Fforeach face F of object if (n . v > 0) throw away the faceDoes it work?Lecture 14 Slide 5 6.837 Fall '00Lecture 14 --- 6.837 Fall '00http://graphics.lcs.mit.edu/classes/6.837/F00/Lecture14/Slide05.html [11/7/2000 4:36:07 PM]Fixing the ProblemWe can't do view direction clipping just anywhere!Downside: Projection comes fairly late in the pipeline. It would be nice to cull objects sooner.Upside: Computing the dot product is simpler. You need only look at the sign of the z.Lecture 14 Slide 6 6.837 Fall '00Lecture 14 --- 6.837 Fall '00http://graphics.lcs.mit.edu/classes/6.837/F00/Lecture14/Slide06.html [11/7/2000 4:36:09 PM]Culling Technique #2Detect a change in screen-space orientation. If all face vertices are ordered in a consistentway, back-facing primitives can be found bydetecting a reversal in this order. One choiceis a counterclockwise ordering when viewedfrom outside of the manifold. This isconsistent with computing face normals(Why?). If, after projection, we ever see aclockwise face, it must be back facing. This approach will work for all cases, but it comes even later in thepipe, at triangle setup. We already do this calculation in our trianglerasterizer. It is equivalent to determining a triangle with negative area.Lecture 14 Slide 7 6.837 Fall '00Lecture 14 --- 6.837 Fall '00http://graphics.lcs.mit.edu/classes/6.837/F00/Lecture14/Slide07.html [11/7/2000 4:36:10 PM]Culling Plane-TestHere is a culling test that will work anywhere in the pipeline. Remove faces that have the eyein their negative half-space. This requires computing a plane equation for each face considered.We will still need to compute the normal (How?). But we don'thave to normalize it.How do we go about computing a value for d? Once we have the plane equation, we substitute the coordinate of the viewing point (the eyecoordinate in our viewing matrix). If it is negative, then the surface is back-facing.Lecture 14 Slide 8 6.837 Fall '00Lecture 14 --- 6.837 Fall '00http://graphics.lcs.mit.edu/classes/6.837/F00/Lecture14/Slide08.html [11/7/2000 4:36:11 PM]Handling OcclusionFor most interesting scenes and viewpoints, some polygons will overlap; somehow, we mustdetermine which portion of each polygon is visible to eye. Solving the occlusion problem used to be one of the BIG PROBLEMS in computergraphics.Lecture 14 Slide 9 6.837 Fall '00Lecture 14 --- 6.837 Fall '00http://graphics.lcs.mit.edu/classes/6.837/F00/Lecture14/Slide09.html [11/7/2000 4:36:12 PM]A Painter's AlgorithmThe painter's algorithm, sometimes called depth-sorting, gets its name from the process which anartist renders a scene using oil paints. First, the artist will paint the background colors of the sky andground. Next, the most distant objects are painted, then the nearer objects, and so forth. Note that oilpaints are basically opaque, thus each sequential layer completely obscures the layer that its covers. A very similar technique can be used for rendering objects in athree-dimensional scene. First, the list of surfaces are sorted according to theirdistance from the viewpoint. The objects are then painted from back-to-front.While this algorithm seems simple there are many subtleties. The first issue iswhich depth-value do you sort by? In general a primitive is not entirely at asingle depth. Therefore, we must choose some point on the primitive to sort by.Lecture 14 Slide 10 6.837 Fall '00Lecture 14 --- 6.837 Fall '00http://graphics.lcs.mit.edu/classes/6.837/F00/Lecture14/Slide10.html [11/7/2000 4:36:13 PM]Implementation import Raster; public abstract interface Drawable { public abstract void Draw(Raster r); public abstract float zCentroid(); } public final float zCentroid() {
View Full Document
Unlocking...