Creating a stereogram based on a three-dimensional model
On Habré already wrote about a simple algorithm for creating stereograms. The stereogram in it is generated on the basis of a height map and an image with a repeating pattern. In this article I want to describe another approach to creating stereograms — based on a three-dimensional model. The main differences of the algorithm described here from the algorithm mentioned above:
A stereogram is an image or a pair of images that, when viewed, creates a stereo effect (the observer has a sense of depth). Stereograms include, for example, anaglyph images and autostereograms. An autostereogram is a stereogram consisting of one image and does not require any additional devices for viewing (like anaglyph glasses or a stereoscope). In this article, we consider exactly autostereograms.
The task is to create such an image on a plane, so that when looking at it both eyes see the same picture as they would see if instead of this image they observed a real three-dimensional object (Fig. 1).
')
Fig. one.
If we assume that the observer has only one eye (the eye will be considered a point), then the task is reduced to the central projection of a three-dimensional object on the plane (the central projection of the object’s point can be obtained by connecting the object’s direct point with the eye’s point - central projection; the point of the eye is called the center of projection). But our observer has two eyes, because both projections of the object will need to be compared with each other.
Consider the point T 1 of a three-dimensional object (Fig. 2). This point is located on the visible part of the object. The projection of this point on the plane for the left eye will be P 1 , for the right one - P 2 . Since for the left eye the visible position of point T 1 coincides on a plane with the visible position of point P 1 , and for the right eye with the position of point P 2 , points P 1 and P 2 should have the same color, which coincides with the color of the point of object T 1 , so that the visual system correctly matches the images from the right and left eyes. Next, we find a point closest to the left eye on the object, so that its projection on the left eye coincides with the point P 2 . This will be point T 2 . Point P 3 is a projection of T 2 onto the right eye, and should be colored the same color as P 1 and P 2 .
Fig. 2
The process of obtaining a sequence of points P 1 , P 2 , P 3 ... is repeated until one of the conditions is fulfilled:
Actually, the algorithm consists in dividing a stereogram into such groups of points and a choice for each group of a certain color (since all points of the group must have the same color, we will call such groups monochrome).
We believe that the eyes are located at the same height and are at the same distance from the plane of the stereogram. As a result, beams of rays emitted from both eyes and passing through a horizontal line on the projection plane will lie in the same plane. Beams of rays passing through different horizontal lines will be in different planes intersecting in a straight line connecting the eyes. Thus, all points P 1 ... P N of one monochrome group will be located on the same horizontal line.
We looked at the object behind the plane of the stereogram. For objects in front of the plane, the method of constructing an image is similar. The only difference is that if for an object lying behind a plane, the next point of the projection P j + 1 lies to the right than P j , then for an object lying in front of the plane, the point P j + 1 , on the contrary, will lie to the left of P j . You can construct a stereogram containing objects lying on both sides of the plane of the stereogram, but it is important to take into account some nuances. Each next point of a certain sequence P 1 ... P N in such a stereogram can be either to the right or to the left of the previous one. Therefore, the formation of cycles is possible. Another consequence is that one monochrome group can contain a fairly large number of points, which can spoil the appearance of the stereogram and complicate its viewing. In general, the simultaneous observation of objects located on both sides of the plane of the stereogram is impossible: when focusing the view behind the plane, objects located in front of the plane will also be visible behind the plane, but with inverted depth. When focusing in front of the plane, there will be a similar problem.
Our stereogram is a rectangle on a plane in three-dimensional space, divided into a grid of rectangular pixels. For convenience, we will continue the grid of pixels in all directions, filling it with the entire plane of the stereogram. We slightly simplify the task - we will consider only those points of space that are before the eyes (for which the ray drawn from the eye intersects the plane of the stereogram). The central projection of an arbitrary point on the plane of the stereogram will fall into one of the pixels. And since we have two eyes, then each point in space corresponds to two pixels containing projections of the point on the left and right eyes. The set of points to which a given pair of pixels corresponds is called a cluster (in fact, such a cluster is the intersection of two body angles emerging from the eyes and tightened by the corresponding pixels). The angular dimensions of the cluster are equal to the angular dimensions of the pixel through which the cluster is visible (see Fig. 3).
Fig. 3. T1 and T2 - clusters, P1, P2, and P3 - pixels.
The algorithm is as follows: for each pixel is the nearest (relative to the eye) point among the points of the object, the projection of which falls into this pixel (in other words, the point visible through this pixel is taken). This is done either by traversing the rays coming out of the eye and passing through each pixel with a shape (suitable for simple shapes like a polygon or a sphere), or by calculating the value of a certain function of the surface at the points of the coordinate grid. Details can be seen by examining the source of the algorithm (see the link at the end of the article). This procedure is performed consistently for each eye. Moreover, the distance to the nearest point found is not stored as a segment length or Z coordinate, but as a cluster coordinate. And since the cluster is defined by the coordinates of two pixels, then for a given pixel it is enough to store the coordinates of a pixel, which is the projection of the cluster to the other eye (and to compare the distances from the eye to the cluster, it is enough to compare the coordinates of another pixel). Thus, for each pixel we store only the coordinates of two other pixels, corresponding to two clusters.
Let us explain what was said on the example of fig. 3. Consider clusters T 1 and T 2 having a common projection P 1 for the left eye. Their projections for the right eye are P 3 and P 2, respectively. But P 2 is to the left than P 3 . Therefore, the cluster T 2 is closer to the left eye than T 1 .
The use of clusters is also convenient in that it makes it easy to get monochrome groups of points. To clarify, we turn again to fig. 3. For P 1, the coordinate of the nearest cluster for the left eye is specified as a pair (P 1 , P 2 ). For P 2, the coordinate of the nearest cluster for the right eye is also (P 1 , P 2 ). This means that the eyes through the pixels P 1 and P 2 see a common cluster, and therefore, the pixels P 1 and P 2 belong to the same monochrome group. For P 3, the coordinate of the nearest cluster for the right eye is (P 1 , P 3 ), which does not coincide with the coordinate of the nearest cluster for the left eye for P 1 . Those. the cluster (P 1 , P 3 ) is shielded from the left eye by a closer cluster, and the pixels P 1 and P 3 belong to different monochrome groups (the pixel P 3 is extreme in its group). One pixel corresponds to no more than one cluster for each eye, and one cluster corresponds to no more than one pixel for each eye, which makes the algorithm for splitting into monochrome groups fairly simple.
It remains to choose colors for monochrome groups. They can be chosen either randomly or based on a background image (and the background image does not need to have duplicate parts). In the described algorithm both variants are implemented (see the source code).
Now let's look at the result of the algorithm (Fig. 4). This stereogram shows several spheres and a plane parallel to the plane of the stereogram as a background. Pixel colors are randomly generated.
Fig.4. By clicking - stereogram in 1024x768 resolution.
If you look at the spheres, then you can see steps on them, as if the spheres consist of planes parallel to the stereogram. The distance between the repetitive parts of the stereogram sets the depth of the objects (the greater the distance, the more distant the object looks). The difference in distance of just one pixel already gives a noticeable difference in depth. This problem can be solved either by increasing the resolution of the device or by modifying the algorithm. We will go the second way. To do this, we will reduce the width of our virtual pixels several times, increasing their number horizontally by the same amount. Then, when generating the image, we will combine several subpixels into one pixel (taking the average color of the subpixels as the pixel color). In fig. 5 you can see that there are no more steps (3 sub-pixels per pixel are taken here, therefore the step of repeating parts of the image is a multiple of 1/3 pixel).
Fig. 5. On click - stereogram in 1024x768 resolution.
In fig. 6 shows an example of a height map image. And in fig. 7 shows a stereogram with an object created on the basis of this height map. The height map is considered as a set of points in space, the coordinates of which are set based on the coordinates of the pixels and their colors. Triangles are created that connect adjacent points (see source for details), making the object look like a solid rather than a set of points. Using an arbitrary basis, you can distort and rotate the object (the coordinates of the point are calculated as V 1 * x + V 2 * y + V 3 * z, where x and y are the coordinates of the pixel on the height map, z is its color, V 1 , V 2 , V 3 - basis). Unlike previous stereograms, here the colors are taken on the basis of a given background image.
Fig. 6. By clicking - the image in the original resolution.
Fig. 7. On click - stereogram in 1024x768 resolution.
- instead of a height map (which is essentially a horizontal pixel displacement map), the objects are specified directly in three-dimensional coordinates;
- There are no restrictions on the number of objects and their location (except that all of them must be in the field of view and at some distance from the plane of the stereogram - so that they can be seen), whereas when using the height map we deal only with one layer;
- the created stereogram has a perspective (the farther the object is from the observer, the smaller it looks);
- the type of object depends on the angle from which it is visible (as for real objects).
Terminology
A stereogram is an image or a pair of images that, when viewed, creates a stereo effect (the observer has a sense of depth). Stereograms include, for example, anaglyph images and autostereograms. An autostereogram is a stereogram consisting of one image and does not require any additional devices for viewing (like anaglyph glasses or a stereoscope). In this article, we consider exactly autostereograms.
The essence of the algorithm
The task is to create such an image on a plane, so that when looking at it both eyes see the same picture as they would see if instead of this image they observed a real three-dimensional object (Fig. 1).
')
Fig. one.
If we assume that the observer has only one eye (the eye will be considered a point), then the task is reduced to the central projection of a three-dimensional object on the plane (the central projection of the object’s point can be obtained by connecting the object’s direct point with the eye’s point - central projection; the point of the eye is called the center of projection). But our observer has two eyes, because both projections of the object will need to be compared with each other.
Consider the point T 1 of a three-dimensional object (Fig. 2). This point is located on the visible part of the object. The projection of this point on the plane for the left eye will be P 1 , for the right one - P 2 . Since for the left eye the visible position of point T 1 coincides on a plane with the visible position of point P 1 , and for the right eye with the position of point P 2 , points P 1 and P 2 should have the same color, which coincides with the color of the point of object T 1 , so that the visual system correctly matches the images from the right and left eyes. Next, we find a point closest to the left eye on the object, so that its projection on the left eye coincides with the point P 2 . This will be point T 2 . Point P 3 is a projection of T 2 onto the right eye, and should be colored the same color as P 1 and P 2 .
Fig. 2
The process of obtaining a sequence of points P 1 , P 2 , P 3 ... is repeated until one of the conditions is fulfilled:
- the projection for the right eye of the next point of the object on the plane lies outside the created image (if we are not going to create a stereogram of infinite size);
- the next point of the object T k is not visible to the right eye, i.e. there is a point closer to the eye, and the projections of the points for the right eye are the same;
- for the next projection point on the right eye P j there is no point on the object, the projection of which on the left eye would coincide with P j (usually this situation is impossible - behind the objects a plane or other figure is created that acts as the background and occupies the entire field of view).
Actually, the algorithm consists in dividing a stereogram into such groups of points and a choice for each group of a certain color (since all points of the group must have the same color, we will call such groups monochrome).
We believe that the eyes are located at the same height and are at the same distance from the plane of the stereogram. As a result, beams of rays emitted from both eyes and passing through a horizontal line on the projection plane will lie in the same plane. Beams of rays passing through different horizontal lines will be in different planes intersecting in a straight line connecting the eyes. Thus, all points P 1 ... P N of one monochrome group will be located on the same horizontal line.
We looked at the object behind the plane of the stereogram. For objects in front of the plane, the method of constructing an image is similar. The only difference is that if for an object lying behind a plane, the next point of the projection P j + 1 lies to the right than P j , then for an object lying in front of the plane, the point P j + 1 , on the contrary, will lie to the left of P j . You can construct a stereogram containing objects lying on both sides of the plane of the stereogram, but it is important to take into account some nuances. Each next point of a certain sequence P 1 ... P N in such a stereogram can be either to the right or to the left of the previous one. Therefore, the formation of cycles is possible. Another consequence is that one monochrome group can contain a fairly large number of points, which can spoil the appearance of the stereogram and complicate its viewing. In general, the simultaneous observation of objects located on both sides of the plane of the stereogram is impossible: when focusing the view behind the plane, objects located in front of the plane will also be visible behind the plane, but with inverted depth. When focusing in front of the plane, there will be a similar problem.
Implementation details
Our stereogram is a rectangle on a plane in three-dimensional space, divided into a grid of rectangular pixels. For convenience, we will continue the grid of pixels in all directions, filling it with the entire plane of the stereogram. We slightly simplify the task - we will consider only those points of space that are before the eyes (for which the ray drawn from the eye intersects the plane of the stereogram). The central projection of an arbitrary point on the plane of the stereogram will fall into one of the pixels. And since we have two eyes, then each point in space corresponds to two pixels containing projections of the point on the left and right eyes. The set of points to which a given pair of pixels corresponds is called a cluster (in fact, such a cluster is the intersection of two body angles emerging from the eyes and tightened by the corresponding pixels). The angular dimensions of the cluster are equal to the angular dimensions of the pixel through which the cluster is visible (see Fig. 3).
Fig. 3. T1 and T2 - clusters, P1, P2, and P3 - pixels.
The algorithm is as follows: for each pixel is the nearest (relative to the eye) point among the points of the object, the projection of which falls into this pixel (in other words, the point visible through this pixel is taken). This is done either by traversing the rays coming out of the eye and passing through each pixel with a shape (suitable for simple shapes like a polygon or a sphere), or by calculating the value of a certain function of the surface at the points of the coordinate grid. Details can be seen by examining the source of the algorithm (see the link at the end of the article). This procedure is performed consistently for each eye. Moreover, the distance to the nearest point found is not stored as a segment length or Z coordinate, but as a cluster coordinate. And since the cluster is defined by the coordinates of two pixels, then for a given pixel it is enough to store the coordinates of a pixel, which is the projection of the cluster to the other eye (and to compare the distances from the eye to the cluster, it is enough to compare the coordinates of another pixel). Thus, for each pixel we store only the coordinates of two other pixels, corresponding to two clusters.
Let us explain what was said on the example of fig. 3. Consider clusters T 1 and T 2 having a common projection P 1 for the left eye. Their projections for the right eye are P 3 and P 2, respectively. But P 2 is to the left than P 3 . Therefore, the cluster T 2 is closer to the left eye than T 1 .
The use of clusters is also convenient in that it makes it easy to get monochrome groups of points. To clarify, we turn again to fig. 3. For P 1, the coordinate of the nearest cluster for the left eye is specified as a pair (P 1 , P 2 ). For P 2, the coordinate of the nearest cluster for the right eye is also (P 1 , P 2 ). This means that the eyes through the pixels P 1 and P 2 see a common cluster, and therefore, the pixels P 1 and P 2 belong to the same monochrome group. For P 3, the coordinate of the nearest cluster for the right eye is (P 1 , P 3 ), which does not coincide with the coordinate of the nearest cluster for the left eye for P 1 . Those. the cluster (P 1 , P 3 ) is shielded from the left eye by a closer cluster, and the pixels P 1 and P 3 belong to different monochrome groups (the pixel P 3 is extreme in its group). One pixel corresponds to no more than one cluster for each eye, and one cluster corresponds to no more than one pixel for each eye, which makes the algorithm for splitting into monochrome groups fairly simple.
It remains to choose colors for monochrome groups. They can be chosen either randomly or based on a background image (and the background image does not need to have duplicate parts). In the described algorithm both variants are implemented (see the source code).
Now let's look at the result of the algorithm (Fig. 4). This stereogram shows several spheres and a plane parallel to the plane of the stereogram as a background. Pixel colors are randomly generated.
Fig.4. By clicking - stereogram in 1024x768 resolution.
If you look at the spheres, then you can see steps on them, as if the spheres consist of planes parallel to the stereogram. The distance between the repetitive parts of the stereogram sets the depth of the objects (the greater the distance, the more distant the object looks). The difference in distance of just one pixel already gives a noticeable difference in depth. This problem can be solved either by increasing the resolution of the device or by modifying the algorithm. We will go the second way. To do this, we will reduce the width of our virtual pixels several times, increasing their number horizontally by the same amount. Then, when generating the image, we will combine several subpixels into one pixel (taking the average color of the subpixels as the pixel color). In fig. 5 you can see that there are no more steps (3 sub-pixels per pixel are taken here, therefore the step of repeating parts of the image is a multiple of 1/3 pixel).
Fig. 5. On click - stereogram in 1024x768 resolution.
In fig. 6 shows an example of a height map image. And in fig. 7 shows a stereogram with an object created on the basis of this height map. The height map is considered as a set of points in space, the coordinates of which are set based on the coordinates of the pixels and their colors. Triangles are created that connect adjacent points (see source for details), making the object look like a solid rather than a set of points. Using an arbitrary basis, you can distort and rotate the object (the coordinates of the point are calculated as V 1 * x + V 2 * y + V 3 * z, where x and y are the coordinates of the pixel on the height map, z is its color, V 1 , V 2 , V 3 - basis). Unlike previous stereograms, here the colors are taken on the basis of a given background image.
Fig. 6. By clicking - the image in the original resolution.
Fig. 7. On click - stereogram in 1024x768 resolution.
Links
- en.wikipedia.org/wiki/Autostereogram - general information about autostereograms;
- github.com/Domanser/AutoStereogramDemo - the source code of the described algorithm (C # 4.0), as well as examples of creating stereograms in this article, and some others.
Source: https://habr.com/ru/post/151655/
All Articles