Raster visibility algorithm

Z-buffer

The Z-buffer or depth memory is one of the most common methods for solving the problem of an objects' visibility in a scene. It has relatively large memory demands because in displaying objects it will keep their z-coordinates in a special two-dimensional field with the dimensions of a table (mostly a display box), where there are stored the coordinates of calculated points. At the beginning, this field is filled in with a maximum value (e.g., maximum z-value of all objects in the display box).

In displaying in a display box we proceed so that we transfer every object into a raster form. In this way, we obtain points with the coordinates x, y a z. Because the display box is only two-dimensional, the objects which are overlapped should not be visible. The Z-buffer serves also to avoid the situation where more distant objects are drawn last and in this way overlap objects standing closer to the observer.

We put into the field all z-coordinates of the relevant points of the given objects. I f during the test of a new point we found out that in the field there is a different value than the starting, then, providing the new value is lower, we write it in.

ALGORITHM:

  • For every image point (x, y) we initialize the Z-buffer to the value of max as well as the bitmap of background.
  • For every surface we assign in the project a polygon; and carry out its decomposition into a raster form, while for every image point of polygon (x, y) we assess a z-coordinate.
  • If the distance of a given pixel (x, y) is lower than the Z-buffer of the relevant pixel, then, we put the value of the given point into the Z-buffer and the color of the point into the bitmap

The order of processed polygons can be any, with every surface being processed only once. This method is hardware implemented in all 3D cards (depth of 16, 24, or 32 bits).


Applet: visibility of objects
Autor : Tomas Hudik E-mail: tomas.h@post.sk
Source code

Line scanning algorithm

A disadvantage of the Z-buffer is its memory demand. The line scanning algorithm reduces memory demands of storage as here it is necessary to store only a field equal to one horizontal line of the screen. This method is based on the decomposition of a polygon into raster form. Here, however, it is necessary to carry out the raster decomposition several times. For each row of the display box we test every surface in a scene, using the given field as a depth memory. An example of the algorithm as described is in [1].


>alt="Your browser understandsthe  APPLET tag but isn't running the applet, for some reason." Your browser is completely ignoring the  APPLET tag!

Applet: Line scanning algorithm

alt="Your browser understandsthe  APPLET tag but isn't running the applet, for some reason." Your browser is completely ignoring the  APPLET tag!

Applet : scan-line algoritmus ( controls: left and rigth mouse buttons)
Author : Tomas Hudik E-mail: tomas.h@post.sk
Source code

Painter algorithm

This algorithm is based on the idea of the consecutive drawing of all surfaces, from the most distant up to the polygons located close to the table; similarly, as a painter over lays gradually individual layers of surfaces. The surface drawn later will overlap the surface below it. The visibility solution is then carried out through 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.


alt="Your browser understandsthe  APPLET tag but isn't running the applet, for some reason." Your browser is completely ignoring the  APPLET tag!

Applet: The painter algorithm. Consecutive drawing of objects.

Division of the display box

In 1969 Warnock designed an algorithm for display subdivision (therefore the Warnock subdivision algorithm). The main idea is vested in the fact that the issue of visibility should be resolved in the display box outright. If it is not possible, then we try to solve it recursive in a smaller window box (where the original box is divided into four new boxes). The algorithm is recursive repeated.

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 <ymin, ymax> 
    For every x from <xmin, xmax> 
    to calculate transformation of projection (x, y, z) to <xi, yi>
    If yi > HOR[xi] then draw the relevant point in the table and HOR[xi]=yi
         If yi < DOL[yi] then draw the relevant point in the table and HOR[xi]=yi
The graph is drawn in the direction of the table.