What do you mean by Hidden Line Surface Removal?
Hidden line and surface removalOR visible line and surface determination (chapter 13)we have polygon faces defined for our object; we need to draw these faces so that faces in front overwrite faces in the backthis is a central problem in graphics and computational geometry: speed!various algorithms devised which are suited to different needs and devices eg. a video technique may differ substantially from that for a pen plotterHidden lines and surfacesalgorithms fall into 2 categories:1. image-precision (device-precision) algorithms: work on a pixel basis by determining visibility at each pixel "sampling": samples object geometry at device-dependent incrementsalgorithm complexity proportional to device resolutionbecause of sampling, can get aliasing problems (ie. "jagged line" error)2. object-precision algorithms: determine visibility via the geometry of the model "continuous": finds most precise answers as possiblecompares n graphical objects with each other: n*n complexityhowever, more complex mathematics, so this is usually slower than image precisionTypes of algorithmsVisible-line determination: examine edge geometry, and determine edge segments that are visible or are hiddenZ-buffer: device-precision algorithm that records the visible object found at each pixelList priority algorithms: object-precise algorithms that sort objects such that when drawn in that order, a correct rendering of hidden surfaces occursScan-line algorithms: image-precise algorithms that determine visibility one scan-line at a timeArea subdivision algorithms: divide-and-conquer applied to object areasRay tracing: determine visible object by tracing line from user eye to each pixel in scene... and othersCoherencesome general principles apply to ALL computer graphics algorithmscoherence: degree to which parts of object exhibit local similaritiesmost parts of the objects in a drawing are more similar than not if you account for this, then changes can be done incrementally & therefore quicklyface coherence: face shading is gradualscan line coherence: each scan line typically changes little from those above and below itarea coherence: adjacent pixels are typically on the same faceframe coherence: in animation, each frame differs very slightly from previous framemany hidden line techniques exploit these factsHidden line removalif you are drawing wireframes, then the hidden line problem is to find the lines or line segments that are obstructed by interceding polygons, and not draw them in full or parteg. functions of 2 variables: y = f(x,z)simple approach: for constant z values, compute values at x intervals, and draw lines between need to remove line portions that are obstructedHidden linesQuick + dirty: if on a CRT, then start at min z value, compute y's for x's and z, rotate & convert to 2D (screen coordinates), and draw it works from screen top to bottom, left to rightbut each time you draw a new y value, erase everything BELOW that pointeffectively removes obstructed parts of drawingdisadvantage: won't work for plotters, and won't work for x-y meshesbetter: horizon line algorithm: keep track of minimum and maximum y coordinates drawn so far in a "silhouette array" draw from front to backwhen you draw a new line segment, see what portions of it lie outsidethese min and max values: those are the parts you see don't draw any part of line within these boundariesalso, need to set new y min and y max for lines outside boundariesproblem: aliasing - when you use device y coordinates, aliasing can occursolution is to use image-precise table insteadExampleHidden linesCan also do this using constant x and z increments: Examplesplit drawing into sections left & right of most vertical line, and draw from back to frontFinally, can combine to create grid effect: Exampleto combine, draw horiz lines L to R, but draw vert lines between each horizontal section you come toHidden surfaceshidden line algorithms only work for strict 2 variable functionsthe more general problem is when you have assorted volumes in 3D space these volumes are not necessarily mathematical functionsgeneral problem: given points P1=(x1,y1,z1), P2=(x2,y2,z2) are P1 and P2 on same projector to viewers eye? and if so, which one is closer (ie. the one the eye sees) and should be drawn?note that this takes into account perspective, as well as colouring, shading, etc, since we draw the actual colour of that object pointhidden surface detection done after model is transformed and perspective applied parallel projection: compare projections (x1, y1) and (x2, y2)perspective projection: apply perspective scaling t', and then compare points (x1', y1') and (x2', y2')different algorithms attempt to make this comparison as efficient as possible eg, prune the # of points/surfaces to compareEfficiency techniquesa) perform volume clipping: then less objects to compareb) check if object extents overlap object extent: the minimum and maximum screen X and Y valuesa quick way to disregard hidden line checkingEfficiency:c) back-facing polygon elimination:polygon normal: the perpendicular ray (direction) from the plane containing the polygonthe equation of this plane determines the side of plane that normal points in graphics, useful to make the normal point towards the front of the poly. if an object defined in terms of planar polygons, and if the object is closed, then we can then disregard drawing polygons whose normals are pointing away from user (neg values)graphics routines: compute normal for the polygon; if it points towards user then use it; otherwise ignore itBackface eliminationthis can be expensive: have to compute normal's direction wrt user eyehowever, there's a trick: when you use simple convex planar polygons, then you can use right-hand rule to determine direction of normaldefine the polygon edges in a counterclockwise orderwhen you wrap right hand fingers in this direction, thumb points at front normalthen, the graphics routine simply checks if the polygon being drawn is being done so in a counterclockwise fashion --> if yes, it is a front-facing one; if not, it is back-facingOpenGL: glFrontFace(GL_CCW); (or GL_CW) specifies clockwise or counterclockwiseglCullFace(GL_BACK); (or GL_FRONT) specifies back or front facing cullingglEnable(GL_CULL_FACE);turns backface elimination onsignificant speedup on O2's: cuts number of polygons to process by halfmake sure that you define your polygons in counterclockwise direction if GL_CCW set(if you see very little of object, you've defined polygon's in clockwiseZ Bufferingz buffering (or depth buffering) is one of the simplest hidden surface algorithmsvia hardware or software, an extra "z" buffer is maintained along with frame buffer. It keeps track of the nearest object at each pixel location.initialized to minimum z value (eg. most negative)then, when object being drawn, if its z coordinate at a point is greater (more positive, less distance to viewer) than z buffer value, it is drawn, and new z coord is saved; otherwise, it is not drawnif a line seg in 3D is being drawn, then the intermediate z values between endpoint z coords are interpolated: linear interpolation for polygons, and can compute z for more complex surfacessome problems: aliasing: limited to size of z buffer word per pixel; can have imprecision at extremely far distances --> important to have as small a viewing volume as possiblepossible to write into and manipulate z buffer memory directly, eg. cursorsZ bufferOpenGL: Z bufferSGI's directly support z buffer: O2's integrated memory z buffer (old systems used software)initialize (GLUT):glutInitDisplayMode(GLUT_RGB | GLUT_SINGLE | GLUT_DEPTH);glEnable(GL_DEPTH_TEST);To use: clear the Z-buffer whenever a new frame is to be drawn:glClear(GL_DEPTH_BUFFER_BIT);can combine with colour clearing:glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);And that's it! must remember to clear the z-buffer whenever you draw a new frameList-Priority algorithmsThese algorithms sort objects in an ordering that, when drawn, causes hidden surface removal.if objects don't overlap, then simply sorting on "z" coordinate and drawing them from farthest to nearest z will workHowever, in general, objects can overlap, so more complex criteria are neededDepth-sortalso called "painter's algorithm": how a painter might paint a scenesort all polygons according to smallest z coordinate of each (ie. distance to viewer)resolve overlaps (split polygons if necessary)scan convert polygons from farthest to nearestalgorithm works for objects that lie in planes of constant z (eg. windowing systems), or those whose z extents do not overlap--> step 2 not required thenotherwise, step 2 must test whether polygons do not overlap, if any of these tests are true: i) polygons' x extents overlapii) polygons' y extents overlapiii) their projection extents on x-y plane overlapiv) one polygon is on one side or the other of other's plane and if so, split them up using clippingwith simple objects and meshes (eg. closed solid volumes), this technique is often quite efficient, because objects can be drawn from furthest to closest without worrying about overlapping polygons.Area subdivision (Warnock's Algorithm)Idea: try to make an easy decision about which polygon is visible in a section of the image (area coherence) If a decision cannot be made, subdivide the area recursively until one can be made.Can be device-precise (stop at pixel) or object-precise (stop at error range)Recursive algorithm: divide image into 4 equal areasfor each area (see tests below):1. are all polygons disjoint from area? (test d) yes --> display background colour2. only one intersecting or contained polygon (tests b, c) yes --> fill with background colour, and then draw contained polygon or intersecting portion3. one single surrounding polygon, no intersecting or contained polygons (test a) yes --> draw area with that polygon's colour4. more than one polygon is intersecting, contained in, or surrounding, but only one polygon is surrounding the area and is in front of others (test a) yes --> draw area with that front polygon's coloure) ELSE --> subdivide the area into 4 equal areas and recurse4 test cases (shaded polygon is to be rendered):Area subdivisionClipping the polygons at step 2 and draw can be done at an object precise or image precise levelQuitting: if none of the test cases have terminated, then you can stop either at image precise or device precise resolution eg. if stopping at pixel resolution, then find the nearest polygon at the centre of the area - colour the pixel that coloureg. for antialiasing, could compute the relative area of the area covered by different polygons and the background, and give an average colourRay TracingFor each pixel, compute the colour that the viewer's eye will see in the scenehidden surface removal is a product of thisray tracing is also effective for photorealistic renderingRay Tracingray tracers need to compute intersection of eye ray with every object, and save the closest object point found recall: ray is a direction in 3D spacerequire various mathematical formulae to compute intersection of ray with planes, spheres, ellipsoids, cylinders, other surfaces and volumescontrast ray tracing with pure Z buffering ray tracing: 1024 by 1024 screen, 100 objects --> 100 Million intersections to computeZ buffering: saves nearest z value of objects that project to that pixel --> no intersections, and only visible pixels usedRay tracing still useful for its ability to calculate lighting & effects, which would have to be done in Z buffering application anywayCan speed up ray tracing by exploiting coherence properties: optimizing intersection calculations, by computing equation values in advance and saving them; exploiting special properties of some geometries;avoiding intersection computations (object extent checks)exploiting spatial partitioningSummary: hidden surfacehardware advances mean that Z buffering is a simple and general means for hidden surface determination when CPU's were slow and memory was expensive, it simply wasn't feasible!However, other approaches are useful / required for different applications: 3D functions - sorting patches is faster than Z bufferpen plotters: require hidden line determination
