Page 114 - DCAP313_LAB_ON_COMPUTER_GRAPHICS

Lab on Computer Graphics

Notes • Must perform tests at high precision
• Resulting information is resolution-independent
Complexity
• Must compare every pair of objects, so O(n2) for n objects
• For an mxm display, have to fill in colours for m2 pixels.
2
• Overall complexity can be O (k obj n + k disp dispm ).
2
• Best for scenes with few polygons or resolution-independent output
Implementation
• Difficult to implement!
• Must carefully control numerical error
Object Order vs. Image Order
Object order
• Consider each object only once - draw its pixels and move on to the next object
• Might draw the same pixel multiple times
Image order
• Consider each pixel only once - draw part of an object and move on to the next pixel
• Might compute relationships between objects multiple times

7.1 Visibility Algorithm Categorization

Sutherland, Sproull and Schumacker termed the visibility algorithms according to their
approaches and principles used. They are either image area or object area types. According to
the visibility algorithms can be split depending on the form of output data.
a. Line Algorithm (Hidden line eliminator)
We receive a set of abscissas representing visible edges. The advantage of this solution is the
fact that we have a set of vectors, and we are not limited due to issues of resolution. In this case,
we can scale the scene without any loss in quality.
b. Raster Algorithm (Hidden surface eliminator)
We receive a set of pixels representing the specific points of the scene in the fixed given resolution,
without any option to scale the scene. Here it is, however, possible to draw also surfaces with
shading and lighting.
Pre-processing of Data
It is time demanding to compute all algorithms; at the beginning it is necessary to examine the
object in the view. This is called data pre-processing. First, all objects outside the visual angle,
are excluded and all polygons of which the scalar vector product (of the normal vector of the
polygon and the direction of view) is positive, and the given polygon is then reversed.

7.1.1 Line Visibility Algorithms
Robertson algorithm one of the first algorithms is the Robertson algorithm; originally aimed
for the solution of visibility of a group of convex polyhedrons. This algorithm subsequently
processes individual edges of the body. It tests every edge, whether it is not overlapped by
another body. If it is hidden only partially, then this edge is split into two parts (one hidden,
the other unhidden). Every unhidden part becomes a new tested edge.
7.1.2 Apple Algorithm

This algorithm works in the area of objects and is based on the fact that every edge is a conjunction
of two polygons. The first step is to remove invisible polygons. First, we split polygons into

108 LOVELY PROFESSIONAL UNIVERSITY