Page 166 - DCAP504_Computer Graphics

Unit 11: Hidden Surfaces

BSP trees are also used to speed up ray tracing (which will be discussed in the unit further) and in
planning the motion of robots. Let us now focus on what happens in the BSP.
Firstly, the polygons are sorted for display in back to front order. For this sorting Controlling Object
Transparency Test which compares all the vertices of one polygon against the plane of another polygon
is conducted. If the plane intersects the polygon, divide the polygon along the plane and extend the
above test. Take one polygon as the reference polygon and compare all other polygons to it in order to
check whether it lies in front of the reference polygon or behind it. According to the result group then
divide into two groups. Select a polygon for each of these subgroups and use it to separate the
subgroups. Firstly, the polygons are sorted for display in back- to- front order.
Repeat the above process until all polygons have been sorted. The resultant outcome is obtained as a
binary tree. At each node of the tree lies a polygon. The root of the tree is the reference polygon and
where as at each node of the tree, it is a polygon. All the polygons that are in front of the reference
polygon lies in one sub tree or branch. The polygons which lie behind it are in the other branch.
Perform an in-order traversal, so that the polygons can be achieved in back to front order.
A lot of information and storage for sorting of the polygons are required in this algorithm. For
constructing and processing BSP trees we may use hardware implementations.
11.3 Painter’s Algorithm

The Painter’s algorithm works similarly in the manner as an artist who paints his/her canvas with
background and foreground colors. According to the painter’s desire, the canvas is initially painted
with the background color. Then the painter creates objects using foreground colors over the
background color. It is assumed that the background color does not affect the drawing of foreground
objects. The same thing happens even in the frame buffer. Initially, the frame buffer is filled with the
background color. One by one the polygons representing object surfaces are drawn keeping the farthest
from the viewer first and nearest from the viewer last.
This algorithm requires enough computing effort to determine the exact order of the polygons to be
drawn. Each polygon is compared to see which precedes the other.
Order of Polygons
Finding the exact order of all the polygons is a complicated and time consuming task. To simplify it,
different sort of tests have to be applied before applying the sorting process itself. The minimax test or
boxing test can be done to determine whether any two polygons are overlapping. To do this test, let us
consider enclosing two boxes around specific polygons. If these two boxes are not overlapping then this
is true for the polygons also. These boxes in general are defined by the co-ordinates x-max, y-max, x-
min, and y-min. If the minimax test result is true then the polygons do not overlap. However, if the test
result is false, you cannot ascertain whether the polygons overlap or not. Therefore, other tests are
required.
If the minimax test is applied on the Z co-ordinate then the relative ordering of two polygons which
overlap on X-Y plane can be determined. In addition, if the smallest Z value for a polygon is greater
than the highest Z value on the other polygon then the former polygon is in front of the latter.
Algorithm

1. Start.
2. Make a polygon list sorted according to their maximum z-value.
3. Set priorities to the polygons starting from the end of the list.
4. While the list is not empty do
(a) start
(b) identify all polygons P2 whose Z range overlaps with the preceding polygon P1

(c) for each P2 do
obscurity test for P2

LOVELY PROFESSIONAL UNIVERSITY 159