Efficiency of different raster set representations is studied. The key point of view is an amortized complexity of the JOIN operator used in front-to-back scene traversals. Each pixel of a raster window must not be processed more than once!
The JOIN operator computes both the DIFFERENCE (an area that needs processing) and the UNION (an update of the processed-mask). Several data structure organizatoins were tested (and some other are going to be tried in the future).
Source code of the JOIN test program
(together with test scripts and raw output files):
March 5th 1997 version (52KB)
Sample output images:
12.6.1997, send comments/requests to pepca.at.cgg.mff.cuni.cz