The painter's algorithm is based on depth sorting and is a combined object and image space algorithm. It is as follows:
This can be used for wireframe drawings as well by the following:
|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
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:
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 <0 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.