Priority Algorithms in computer graphics

In contrast to the scan line and area coherence algorithms, priority algorithms try to discover the depth relations first and then perform the xy calculations only after the visibility has been established. They are similar to the priority algorithms of scan conversion.

Remember the painters algorithm? A painter drawing a painting on a canvas simply keeps painting them beginning from the farthest object. As and when a nearer object gets painted, the hidden areas of the farther objects automatically get covered by the new object

Similarly if one begins scan converting the polygons beginning with the farthest polygon, the hidden lines and hidden surfaces automatically get eliminated. However, if the polygons in the priority list overlap in depth, the things become more complex. Look at the following figure:

Priority Algorithms
Priority Algorithms

Simply sorting them on the basis of Z max would make computations complicated because for certain scan lines. A is nearer than B but for certain others B is nearer than A. Hence the priority list, prepared based only on the depths will have to be rearranged as follows

Consider the last polygon in the A (Say). If it has no overlaps in depths with its predecessors, then it has no overlaps with any other polygons and can remain at the end. Other wise, if it has any depth overlaps with one or more polygons, denoted by the set {b}, then we have to again check if any specific polygon B from this set is obscured by A. If yes, then B has no business to be in that priority since A, which is obscuring B, should have a higher priority than B. Corresponding modifications are to be made to the list.

Based on the considerations, in the above figure A should have a higher priority than B, though the Zmax of B is less than that of A

The question is how to find out the relation “A obscures B”? Apply the following steps in the same order to ascertain that A does not obscure B.

(a) Depth minimax test should indicate that A and B do not overlap in depth and B is closer to the viewpoint than A. This test is implemented by initially sorting by depth all polygons and by the way A and {b} are selected.

(b) Minimax test in xy should indicate that A and B do not overlap in X or Y.

(c) All vertices of A should be farther from the view point than the plane of B. This can be implemented by substituting x,y coordinates of a into the plane equation of B and solving for the depth of B.

(d) All vertices of B should be closer to the viewpoint than the plane of B.

(e) A full overlap test should indicate that A and B do not overlap in x or y

The order is not very important, except that any one of the tests being true indicates that A does not obscure B. Since the latter tests are more involved, it is desirable that the order is followed so that one can avoid the latter tests if possible

Is the “A obscures B” relation sufficient condition to sort polygons? Look at the following sequence of figure.

Priority Algorithms
Priority Algorithms

Leave a Comment