Visible Surface Determination: Painter's Algorithm

The painter's algorithm is based on depth sorting and is a combined object and image space algorithm. It is as follows:

1. Sort all polygons according to z value (object space); Simplest to use maximum z value
2. Draw polygons from back (maximum z) to front (minimum z)

This can be used for wireframe drawings as well by the following:

1. Draw solid polygons using Polyscan (in the background color) followed by Polyline (polygon color).
2. Polyscan erases Polygons behind it then Polyline draws new Polygon.

Problems with simple Painter's algorithm

Look at cases where it doesn't work correctly. S has a greater depth than S' and so will be drawn first. But S' should be drawn first since it is obscured by S. We must somehow reorder S and S'.:

We will perform a series of tests to determine, if two polygons need to be reordered. If the polygons fail a test, then the next test must be performed. If the polygons fail all tests, then they are reordered. The initial tests are computationally cheap, but the later tests are more expensive.

So look at revised algorithm to test for possible reordering

Could store Zmax, Zmin for each Polygon.

- sort on Zmax

- start with polygon with greatest depth (S)

- compare S with all other polygons (P) to see if there is any depth overlap(Test 0)

If S.Zmin <= P.Zmax then have depth overlap (as in above and below figures)

If have depth overlap (failed Test 0) we may need to reorder polygons.

Next (Test 1) check to see if polygons overlap in xy plane (use bounding rectangles)

Do above tests for x and y

If have case 1 or 2 then we are done (passed Test 1) but for case 3 we need further testing failed Test 1)

Next test (Test 2) to see if polygon S is "outside" of polygon P (relative to view plane)

Remember: a point (x, y, z) is "outside" of a plane if we put that point into the plane equation and get:

Ax + By + Cz + D > 0

So to test for S outside of P, put all vertices of S into the plane equation for P and check that all vertices give a result that is > 0.

i.e. Ax' + By' + Cz' + D > 0 x', y', z' are S vertices

A, B, C, D are from plane equation of P (choose normal away from view plane since define "outside" with respect to the view plane)

If the test of S "outside" of P fails, then test to see if P is "inside" of S (again with respect to the view plane) (Test 3).

Compute plane equation of S and put in all vertices of P, if all vertices of P inside of S then P inside.

inside test: Ax' + By' + Cz' + D &lt0 where x', y', z' are coordinates of P vertices

so for above case:

Then we do the 4th test and check for overlap for actual projections in xy plane since may have bounding rectangles overlap but not actual overlap

For example: Look at projection of two polygons in the xy plane

Then have two possible cases.

All 4 tests have failed therefore interchange P and S and scan convert P before S. But before we scan convert P we must test P against all other polygons. Look at an example of multiple interchanges

Test S1 against S2 and it fails all tests so reorder: S2, S1, S3

Test S2 against S3 and it fails all tests so reorder: S3, S2, S1

Possible Problem: Polygons that alternately obscure one another. These three polygons will continuously reorder.

One solution might be to flag a reordered polygon and subdivide the polygon into several smaller polygons.

Visible Surface Determination
HyperGraph home page.