Page 117 - DCAP313_LAB_ON_COMPUTER_GRAPHICS

Unit 7: Implementation of Hidden Surface in 2D

• Extra work for moving viewer. Notes
• Efficient shading.
• Handles cycles and self-intersections.

7.2.2 Painter’s Algorithm

This algorithm is based on the idea of the repeated drawing of all surfaces, from the most
secluded up to the polygons placed close to the table; similarly, as a painter over lays gradually
individual layers of surfaces. The surface drawn later will overlie the surface below it. The
visibility solution is then carried out during the arrangement of surfaces based on the distance of
the observer. Because the surfaces are 3D objects, it is not possible to arrange definitely according
to the distances. Therefore, we proceed as follows: firstly, we arrange, meaning the indexing of
surfaces according to the lowest z-coordinate of the relevant surface. This series cannot be drawn
directly because there can appear a case when a surface with a lower z-coordinate would overlap
another surface with a larger z-coordinate. The painter algorithm is suitable for more simple
scenes with limited conjunctions of objects, due to its low calculation and memory demands.
After indexing all surfaces, we can start the method of drawing itself. Firstly, the surface from
a list is marked as active, and then, we test it with regard to overlapping with other surfaces.
Displaying Spatial Graphs
Special displaying method on drawing spatial graphs, where visibility is determined by the
floating horizon method. The algorithm uses two auxiliary fields (the upper horizon HOR, and
the bottom horizon DOL) with the dimensions equal to the number of pixels of the table in the
horizontal direction.
Algorithm

1. Initialize HOR by the value plus infinity.
2. Initialize DOL by the value minus infinity.
3. For every y from <y min, y max>

4. For every x from <x min, x max>
5. To calculate transformation of projection (x, y, z) to <xi, yi>
6. If y i > HOR[x i ] then draw the relevant point in the table and HOR[xi]=yi

7. If y i < DOL[y i ] then draw the relevant point in the table and HOR[xi]=yi
7.2.3 Binary Space Partitioning (BSP)
Binary space partition trees (BSP trees) are extremely helpful for people who work with 2D and
3D computer graphics. A BSP tree works by dividing up and organizing the parts of a game
scene and then sorting the parts of the sight into a useful form from which information on how
the parts relate to each other can be quickly accessed.

Building a BSP Tree (in 2D)
BSP Tree Construction
BSP tree make BSP( L: list of polygons )
{
if L is empty
{
return the empty tree
}

LOVELY PROFESSIONAL UNIVERSITY 111