What do you mean by Hidden Line Surface Removal?

Hidden line and surface removal

• OR 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 back

• this 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 plotter

Hidden lines and surfaces

• algorithms 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 increments
  • algorithm complexity proportional to device resolution
  • because 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 possible
  • compares n graphical objects with each other: n*n complexity
  • however, more complex mathematics, so this is usually slower than image precision

Types of algorithms

1. Visible-line determination: examine edge geometry, and determine edge segments that are visible or are hidden
2. Z-buffer: device-precision algorithm that records the visible object found at each pixel
3. List priority algorithms: object-precise algorithms that sort objects such that when drawn in that order, a correct rendering of hidden surfaces occurs
4. Scan-line algorithms: image-precise algorithms that determine visibility one scan-line at a time
5. Area subdivision algorithms: divide-and-conquer applied to object areas
6. Ray tracing: determine visible object by tracing line from user eye to each pixel in scene

Coherence

• some general principles apply to ALL computer graphics algorithms
• coherence: degree to which parts of object exhibit local similarities
• most parts of the objects in a drawing are more similar than not
  • if you account for this, then changes can be done incrementally & therefore quickly
• face coherence: face shading is gradual
• scan line coherence: each scan line typically changes little from those above and below it
• area coherence: adjacent pixels are typically on the same face
• frame coherence: in animation, each frame differs very slightly from previous frame
• many hidden line techniques exploit these facts

Hidden line removal

• if 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 part
• eg. 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 obstructed

Hidden lines

• Quick + 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 right
  • but each time you draw a new y value, erase everything BELOW that point
  • effectively removes obstructed parts of drawing
  • disadvantage: won't work for plotters, and won't work for x-y meshes
• better: horizon line algorithm: keep track of minimum and maximum y coordinates drawn so far in a "silhouette array"
  • draw from front to back
  • when you draw a new line segment, see what portions of it lie outside
• these min and max values: those are the parts you see
  • don't draw any part of line within these boundaries
  • also, need to set new y min and y max for lines outside boundaries
  • problem: aliasing - when you use device y coordinates, aliasing can occur
  • solution is to use image-precise table instead
• Example

Hidden lines

• Can also do this using constant x and z increments: Example
• split drawing into sections left & right of most vertical line, and draw from back to front
• Finally, can combine to create grid effect: Example
• to combine, draw horiz lines L to R, but draw vert lines between each horizontal section you come to

Hidden surfaces

• hidden line algorithms only work for strict 2 variable functions
• the more general problem is when you have assorted volumes in 3D space
  • these volumes are not necessarily mathematical functions
• general 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 point
• hidden 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 compare

Efficiency techniques

• a) perform volume clipping: then less objects to compare
• b) check if object extents overlap
  • object extent: the minimum and maximum screen X and Y values
  • a quick way to disregard hidden line checking

Efficiency:

• c) back-facing polygon elimination:
• polygon normal: the perpendicular ray (direction) from the plane containing the polygon
• the 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 it

Backface elimination

• this can be expensive: have to compute normal's direction wrt user eye
• however, there's a trick: when you use simple convex planar polygons, then you can use right-hand rule to determine direction of normal
• define the polygon edges in a counterclockwise order
• when you wrap right hand fingers in this direction, thumb points at front normal
• then, 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-facing
• OpenGL:
  • glFrontFace(GL_CCW); (or GL_CW)
    • specifies clockwise or counterclockwise
  • glCullFace(GL_BACK); (or GL_FRONT)
    • specifies back or front facing culling
  • glEnable(GL_CULL_FACE);
    • turns backface elimination on
  • significant speedup on O2's: cuts number of polygons to process by half
  • make 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 clockwise

Z Buffering

• z buffering (or depth buffering) is one of the simplest hidden surface algorithms
• via 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 drawn
• if 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 surfaces
• some 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 possible
• possible to write into and manipulate z buffer memory directly, eg. cursors
  

Z buffer

OpenGL: Z buffer

• SGI'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 frame

List-Priority algorithms

• These 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 work
• However, in general, objects can overlap, so more complex criteria are needed

Depth-sort

• also called "painter's algorithm": how a painter might paint a scene

1. sort all polygons according to smallest z coordinate of each (ie. distance to viewer)
2. resolve overlaps (split polygons if necessary)
3. scan convert polygons from farthest to nearest

• algorithm 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 then
• otherwise, step 2 must test whether polygons do not overlap, if any of these tests are true:
  • i) polygons' x extents overlap
  • ii) polygons' y extents overlap
  • iii) their projection extents on x-y plane overlap
  • iv) one polygon is on one side or the other of other's plane and if so, split them up using clipping
• with 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 areas
  • for each area (see tests below):
  • 1. are all polygons disjoint from area? (test d)
    • yes --> display background colour
  • 2. only one intersecting or contained polygon (tests b, c)
    • yes --> fill with background colour, and then draw contained polygon or intersecting portion
  • 3. one single surrounding polygon, no intersecting or contained polygons (test a)
    • yes --> draw area with that polygon's colour
  • 4. 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 colour
  • e) ELSE --> subdivide the area into 4 equal areas and recurse
• 4 test cases (shaded polygon is to be rendered):

Area subdivision

• Clipping the polygons at step 2 and draw can be done at an object precise or image precise level
• Quitting: 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 colour
  • eg. for antialiasing, could compute the relative area of the area covered by different polygons and the background, and give an average colour

Ray Tracing

• For each pixel, compute the colour that the viewer's eye will see in the scene
• hidden surface removal is a product of this
• ray tracing is also effective for photorealistic rendering

Ray Tracing

• ray 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 space
  • require various mathematical formulae to compute intersection of ray with planes, spheres, ellipsoids, cylinders, other surfaces and volumes
• contrast ray tracing with pure Z buffering
  • ray tracing: 1024 by 1024 screen, 100 objects --> 100 Million intersections to compute
  • Z buffering: saves nearest z value of objects that project to that pixel
    • --> no intersections, and only visible pixels used
• Ray tracing still useful for its ability to calculate lighting & effects, which would have to be done in Z buffering application anyway
• Can 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 partitioning

Summary: hidden surface

• hardware 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 buffer
  • pen plotters: require hidden line determination