# Stereograms : A COOL application of Geometry - Technical Explanation

!!CAUTION: Graphically Intensive Page - Please View in at least 800x600 Resolution!!

Before reading my exposition on the subject of Stereograms, please download my Java program StereoGrinder (and the JDK) so you can follow along with the real source code and make some real stereograms yourself!

NOTE: In the examples, I will write in pseudo-Java. Some things will be simplified, such as casting. All of the messy code that actually works (which, by the way, has a slightly different and less clear naming scheme) is found in the ZIP file that you can download.
 The very basic principle of Stereograms and how the whole 3D effect works can be summed up in the two pictures at left and below, representing the a scan plane of an image.

The way I chose to do this was to paint the depths in greyscale. I used white to mean the closest to your eyes and black to mean the furthest away, that is, black had a lower corresponding Z-value than white. This is a common technique in the back of Magic Eyetm books to tell you "what it is" you're supposed to be seeing, so I sort of copied it from there. If you've ever watched the video-on-CD that comes with the game Myst, you may remember that this is also the technique they used to draw the island.

A Refined View of our Scan Plane: Before we continue, let us refine our picture of a scan plane to our final view of it - you may notice, if you've read the Stereogram FAQ, that we're taking the more mathematically complicated "fixed view" rather than the "floating view" of the eyes. This means that our stereograms will be mathematically correct, but designed to be only viewed straight-on (with the viewer's head center-aligned horizontally with the stereogram. So, without further ado, here is the final picture we will use:

Those red-capped bars represent the depthcells in the current scanline. It's not just you -- I just coined the term depthcell. As pixel means "picture element," I will use depthcell to mean "depth array element," meaning an element that records the Z-depth for its position in the Depth Array. You can also look at a depthcell as the bar extending from the back plane of the depth field to some depth within the depth field. For example, the depthcell on the far left would be generated from the far left pixel in the current line of the image. That far left pixel would be white and hence has the smallest Z-component that an element in the depth field can have. The next depthcell to the right would be generated from a pixel that is dark to mid grey.

The relative coordinates of all of the key points are described in the following diagram. All of the points on the left side have the same Z-coordinates and the opposite (negative) X-coordinates as the right hand counterparts. All coordinates in the diagram are of the form (x,z).

 A Stereogram with Edge Scatter A Clean Stereogram
Edge Scatter and Depth Field Padding: The problem is that the depthcells we get from the greyscale image only occupy the extent that both eyes can see of the Front plane of the Depth field, and thus leave spots without depthcells to either side. The reason we don't just let them strech the entire length of the back plane is because we don't want to lose any data. If the depthcells were allowed to extend the length of the Depth Field the left eye couldn't, for instance, see the far left depthcell in the diagram. The adverse effect of constraining where the depthcells are is that when the depthcells near the sides of the original depth field are low, your view extends to that void space without any depthcells like it is on the right in the diagram. This leads to nothing being generated for the edges of the stereogram, which looks terrible. What happens is that the eyes don't have anything to see at the edges and the whole illusion of depth scatters away. Thus, what we have to do is extend the number of depthcells per scan line by padding the left and right of the scan line with some extra depthcells, which I choose to be of the maximum depth (flat with the back). We will need to add the same number of padding cells to both the left and right so our image centers and our math will work out well.

The Base Image of a Stereogram: If we were to go along our merry way and process each scan line and for each point generate two points of some random color on the screen for each point in our depth array(next discussion), we will not get what we want. What happens is that you overwrite what you have generated by one pixel with what you generate for another. This is exaggerated a bit in the diagrams because of the few number of pixels, but you see what can happen. Pairs become unusable because half or all of them are overwritten. We can limit the effect towards the edges by making sure we get only one depth per left eye pixel, which we will do for efficiency later, but we still have the problem of where the left and right projections "criss-cross" onto the same pixels.
What we do, then, is to first generate some base image either by plotting dots of random color throughout the image or by asking the user for some sort of image file to tile to make the background. (See
my program!) What we will do to make the 3D pairs is to go from left to right across the depth field and set each right pixel to what color is already at the left pixel. Thus, the program would never overwrite what was already in a left position, and have very little overwrite at all. The overwrite the stereogram would have would happen when depth changes suddenly and the only one I could actually see it in real life (look at the white depthcell in the diagram). This we will consider in the Ghost Images section.

```   double orig_cxBack     //The pure virtual width of the back plane, before it is modified for
double cxBack;         //(width of a depthcell)*(the number of depthcells we need)
int orig_dA_Width;     //Width of the original depth array, without the padding
int dA_Width;		  //Width of depth array, including the cell padding
int dA_Height;		  //Height of depth array
int depthArray[orig_dA_Width][dA_Height];
//The original depthArray - an array that is loaded, usually
//from a greyscale image
int scanlineDepths[];
//This will be used for the scanline processing
//it will have dA_Width elements.
int imageArray[][];    //The array for the image - in [Y][X] form
//It will be cyImage by cxImage in the end

double depthcellWidth; //The width of one depthcell in virtual coordinates (diagram coords)
int cyImage;           //The height of the actual Stereogram we will generate
```
To generate our depth array from our image, the first thing we need to do is to set up our variables:
```   cxFront = cxBwtEyes
+ (cxImage-cxBwtEyes)*(czEyesScr+czScrF)/czEyesScr;
orig_cxBack  = cxBwtEyes
+ (cxImage-cxBwtEyes)*(czEyesScr+czScrF+czField)/czEyesScr;
depthcellWidth = cxFront/orig_dA_Width;

= Math.ceil(orig_cxBack/depthcellWidth) - orig_dA_Width;

//We want  the number of added Depthcells to be even

cxBack = dA_Width*depthcellWidth;

cyImage = (dA_Height*cxImage/dA_Width);
cyImage = cyImage*
(cxBwtEyes + (dA_Width*depthcellWidth-cxBwtEyes)*czEyesScr
/(czEyesScr+czScrF+czDepth) )/cxFront;

scanlineDepths = new double[dA_Width];
imageArray = new int [cyImage][cxImage];
```
 The first two lines of code, initializing cxFront and cxBack are based on the Elements, Book VI, Proposition 2. This proposition states that if you take a triangle ABC and construct a line parallel to the base that intersects the other two sides at points D and E, then the triangle ABC is similar to triangle ADE - all of the sides are proportional. To find cxFront and cxBack, we take the middle cxBwtEyes units out of the diagram so the two eyes meet and form a triangle. We then add a height and get the diagram to left. The ratios we then extract are AD:BC = AG:EF = AJ:HI. Translated to our coordinate system, this means that: ```(cxImage-cxBwtEyes):(cEyesScr) = (cxFront-cxBwtEyes):(czEyesScr+czScrF) = (cxBack -cxBwtEyes):(czEyesScr+czScrF+czField)``` Taking it one ratio at a time, converting to fractions, and solving for cxFront and cxBack, we derive the first two lines of code. The rest is simply setting up the data that described how many depthcells are in each scanline, including the padding depthcells, making sure that number is even, and calculating the new width of the back.

The lines to calculate cyImage are a bit odd, and I'll have to walk you through them. In fact, I did not catch an error in these lines until I wrote this article. I had been using an approximation that had left my images, on average, 115% taller than they should have been! First, the program calculates how high the image should be purely based on the ratio of width to height in the depth array. It then multiplies that by the ratio of KL to BC (see diagram). This second calculation is necessary to "square up" the image so that a ball looks round and not ovalish. The reason behind this is that, if a depth array is low (close to the back plane) near the edges, then there are those areas to the edges with no data (as we talked about before). Thus, when the sides of our original image are low, our actual data will only occupy that space between the green lines in the diagrams. So, to shrink the height to be square with the fraction of the entire width that the data occupies, we multiply it by that fraction, which is KL/BC. The formula is directly derived from that ratio by filling in the coordinate data. Originally, what I did was multiply the height by cxFront/cxBack because I had not actually drawn the diagram, and thought that that fraction was correct. The correct fraction was much more complicated.
The final two lines simply allocate the arrays we will use for the depths and the image. I use an array of integers for the imageArray because integers are 32 bits in Java, which hold an RGB triple quite nicely (see the Java docs).

From here we will load each scanline, one at a time, into our scanline depth buffer and work with it:

```for(int y=0; y<cyImage; y++)
{
for(int g=0; g<cxImage; g++)
{
scanlineDepths[g] = czEyesScr+czScrF+czField;
}
for(int g=0; g<orig_dA_Width ;g++)
{
}

int stepX = (czScrF+czEyesScr)/czEyesScr;

for(double curX = -orig_cxBack/2.0; curX < orig_cxBack/2.0; curX+=stepX)
{
int curDApos = Math.floor((cxBack/2.0+curX)/depthcellWidth);
double distToLeftEye = (curX - (-cxBwtEyes/2.0));
double distToRightEye = (curX - cxBwtEyes/2.0);

int imgXa = (int)((cxImage - cBwtEyes)/2.0 +
distToLeftEye*czEyesScr/scanlineDepths[curDApos]);
int imgXb = (int)((cxImage + cBwtEyes)/2.0 +
distToRightEye*czEyesScr/scanlineDepths[curDApos]);

imageArray[y][imgXb] = imageArray[y][imgXa];
}
}
```

In the loop, we first set all of our depthcells to the back of the depth field and fill in those center (non-padding) depthcells with data from the original depthArray. Following that, we iterate over the depth field. Instead of making a projection for each depthcell, we make a projection for each pixel in the image. Why? The pixels are what count! Imagine there are a hundred depthcells, add twenty for padding. Since we can set the width of our image to anything we want, let us also say that we want an image that is 450 pixels wide. This is fine and good, but if we're only going to project 120 depthcells, we certainly aren't going to have a continuous depth effect over our 450 pixels, but have what seem like wavy lines of depth every four pixels or so. So we project approximately one depthcell per pixel from the view of the left eye by starting at the left end of the back and incrementing our x position by stepX until we're past the right end of our array of the back. But how to gauge how big a step we should take? First of all, should our steps all be the same?

The problem simplifies to a question of whether, since our pixels are evenly spaced, the steps in the back are also evenly spaced. Look at the proof that these steps are, in fact, equal, here. Now that we know that the steps we should take should take, I will venture to say that there are some places where *NO* step would be small enough to make sure that each left-eye pixel is accounted for - the reason why is to the right. You might ask - why don't we just project the points up the side of the bar? Well, it would make our program exceedingly complicated. Not nearly as complicated as a ray-tracer, but complicated nonetheless. We will deal with one such problem below, but I thought that tackling this one wouldn't be so important right now. Besides, we're mainly looking down on this thing anyway, so this problem shouldn't be to much. So what we're left with is to decide what a good enough step will be. If all of the depthcells are far away, the projection of one pixel's width onto the back plane will do (see the Evenly-Spaced picture above). But, if all of the depthcells are as near to us as they can be, we will have to have a smaller step (higher resolution). Assuming that we have a fairly smooth depth field, this smaller step will do. If we have some big jumps in the picture, there is no simple way to take care of it, as described above. So, to find this smaller step, we will simply project a unit of one on the Screen to the front plane. And that's how we get stepX. Now that we know how we get the step, we can explain the loop. We start at -orig_cxBack/2.0 and not -cxBack/2.0 because cxBack contains the extra padding which may have spilled over because orig_cxBack is probably not evenly divisible by depthcellWidth. (A refresher of our coordinates at this point might be in order) The main loop then iterates over a bunch of depthcells by incrementing curX and projecting each point until we get to the other end. For each point, we calculate the index of the coordinate in our depth arrray and then use Book VI, Proposition 2 of the Elements to project the difference in x of both of the eyes and the curX from the back plane onto the screen. The only thing that might be new to you would be the use of the mathematical floor function. The rest is pretty straight-forward.