Before starting the calculation of a SIRDS we first need the z-data of the scene. This can be obtained for example from any raytracer capable of generating a user accessible depth map (for example POVray). We use an integer value depth map to allow the usage of a lookup table for the stereo separation and to increase the performance. A range of 256 possible z-values is suf-ficient for most applications. The eye distance E is set to 2.5 inch and the screen resolution to 75 DPI. The scene and SIRDS size is defined by MAXX and MAXY.
Because dependencies among pixels occur only within scanlines the program can process them one at a time. In a first pass the constraints are recorded in same[]. Initially each pixel is constrained to itself (same[x]=x), if a dependency occurs, same[x] is set to point at the nearest right pixel which has to be colored the same way.
In the second pass pixels are colored from right to left according to the contents of same. If same[x] still points at x the color of the pixel can be chosen randomly. If it points at a pixel further to the right, the color of that pixel has to be used.
During the first pass the x-positions of the left and the right image of the corresponding point of the scene are calculated for every z-value of the scanline. Having a stereo separation s at the current position x within the scanline, the left image is placed at left=x-s/2, the right one at right=left+s or right=x+s-s/2, (right=x+s/2 would be inaccurate using an odd s). If both images are visible, they have to be constrained to have the same color. To reduce the process of resolving the constraints during the second pass to a right to left scan we have to ensure that there are linear "chains" of dependencies with all entries pointing from left to right (same[x]>=x). In our algorithm this is achieved as a side effect of the hidden surface removal. (Hidden surface removal is discussed in detail later). Assuming that a point A is obscured (for one eye) by a point B if itīs image is the same as Bīs we eliminate the case of pixels with multiple constraints (see Figure 9). Although this assumption introduces a small error, it seems to have no visible influence on the generated SIRDS.
The situation of a single pixel having more than one constraint-link is eliminated by our
method for the hidden surface removal.
There are two reasons why images of a point may be not visible: First, one of the images might be outside the screen (left<0 or right>MAXX). Second, the sight of one or both eyes can be obscured by other parts of the scene. Because ignoring this fact would cause unnecessary constraints and introduce echoes (non existing objects appearing in the scene, ex-plained later, also see fig. 10) we need to introduce a method to detect such hidden surfaces. Our method makes use of the fact that at least one of a pointīs images has to be obscured, if the depth seen by the left or the right eye is different from the depth of the point. To perform this check efficiently we introduce two z-buffers (lHidden, rHidden), each for one eye. Before generating the constraints for a scanline we project the original depth-buffer into lHidden and rHidden in a way that the left image of a point is written into lHid-den[left] and the right one into rHidden[right]. By generating lHidden from right to left and rHidden from left to right the images of obscured points are simply overwritten.
Generation of the lHidden buffer for the hidden surface removal