______________________________________________________________________________ | | | Theory and Discussion for real-time Spherical Mapping on a PC | |____________________________________________________________________________| John De Goes Disclaimer: I assume no responsibility for whatever this file, implementation thereof, or use in any manner, is capable of doing to you, your spouse, or any one else related to you or your existence. I shall not be held liable for any damage done to you, your computer, any and all of your possessions, any one (or thing) you know, or any one (or thing) you do not know. No warranty is included with this file, nor is any expressed or implied. USE AND READ THIS FILE AT YOUR OWN RISK! ------------------------------------------------------------------------------- | Introduction | ------------------------------------------------------------------------------- Spherical mapping is a term used to describe the mapping of a texture (the texture map) onto a sphere. When used properly, this effect can look really cool. One application of this type of mapping is 3D games. More specifically, it is possible to draw the "sky" of 3D games using a variety of spherical mapping techniques. ----------------------------------------------------------------------------- | The Methods | ----------------------------------------------------------------------------- The fist technique we'll explore is also the most obvious: using the equation for a circle to produce the desired effect. The standard form of the equation for a circle is as follows: 2 2 2 (x - h) + (y - k) = r Where the coordinate point (h, k) is the center of the sphere, and r is the radius. Solving for r, we get the following: 2 2 r = Square_Root ( (x - h) + (y - k) ) Where Square_Root returns the square root of expression within. This is a 2-dimensional equation, but we would like it's 3-dimensional equivalent. Fortunately, we can represent a 2-dimensional equation with a 3-dimensional equation if the third dimension has no depth. Keeping this in mind, we can extend the equation to 3-dimensions to get the following: 2 2 2 r = Square_Root ( (x - h) + (y - k) + (z - l) ) Where z is the z (depth) coordinate of a point on the sphere, and l is the z coordinate of the center of the sphere. Thus, the center of the sphere becomes (h, k, l). This equation is a fully 3-dimensional equation, and can be used in spherical mapping algorithms. Ideally, we would calculate every possible (x, y, z) coordinate, project that coordinate onto our viewport, and finally apply our texture mapping equations to that point. However, there is an infinite many points on the surface of any sphere, so calculating all of them would require an infinite amount of time, regardless of the speed of the processor. Fortunately, it is not necessary to calculate every (x, y, z) point; only the ones that fall within the viewport. With this in mind, we can see that we will have to step in screen-space to achieve our goal. Stepping in screen-space is simply stepping on each pixel so we do not have to concern ourselves with projecting an infinite many points. Stepping in screen-space requires that we know several things about the sphere we will be mapping the texture on. The following is a list of items we must know before we can texture map our sphere: The world x coordinate (of the sphere) for every pixel in the viewport The world y coordinate (of the sphere) for every pixel in the viewport The world z coordinate (of the sphere) for every pixel in the viewport Because our sphere is representing the sky, we know that it will never move. The sphere will always be centered about the viewer, thus all of this information will remain constant for each pixel. In other words, each pixel will have exactly the same (x, y, z) from one frame to the next. Knowing this, we could calculate 3 giant look-up tables for each of the coordinates. For a 640x480 resolution, this would consume close to 2 mega-bytes, which is obviously out of the question. A little detour is in order... The projection equations that are usually used are based on a view volume of triangular shape. These equations are as follows: xd x' = -- z yd y' = -- z Where x' and y' are the projected points; x, y, and z are the 3-dimensional coordinates being projection; and d is a distance factor. With a little algebraic manipulation, we can write the equations as follows: x'z x = --- d y'z y = --- d These equations tell us that we can generate values of x and y for a every value of z/d. In other words, we can get the 3D x coordinate by multiplying the screen x (x') by z/d. Similarly, we can get the 3D y coordinate by multiplying the screen y (y') by z/d. How does this help, you ask? Well, I'll tell you: there is no need to calculate 3 look-up tables containing the (x, y, z) coordinates; only one look-up table containing a z/d coordinate at each pixel. This brings down our SVGA memory requirement to 600k. A little high, but getting manageable. Furthermore, we can take advantage of the fact that a z value at (x, y) will be exactly the same as a z value at (-x, y), and that a z value at (x, y) will be exactly the same as a z value at (x, -y). This is due to the fact that our spherical equations have lines of symmetry. As a matter of fact, our spherical equations have an infinitely many lines of symmetry. However, it is difficult to take advantage of the all of those lines, so we will not (at present) explore this technique. Basically, it involves using the 2D equation for a circle for generating the z/d values. This means you could reduce your memory requirements down to less than 2 kilo-bytes. Nonetheless, even if we only take advantage of these two lines of symmetry, we will reduce the memory requirements down to 150 kilo- bytes, which is actually usable. Also, if you can get away with using a byte for each pixel, you can reduce the memory requirements to 75 kilo-bytes. We have not concerned ourselves with the actual method of generating z values, but they can be generated using the afore mentioned equations, or with a utility of some kind. You may be wondering why I haven't discussed the actual texture mapping of a sphere, and rightly so. It may come as a surprise to you when I tell you there is no need for traditional texture mapping with this method. We can directly use the (x, y) values (derived from the z/d table) as texture coordinates. In order for this to work, you will have to choose a suitable radius for your sphere, and a matching d value. The values you choose for z and d are entirely dependant upon the size of the texture, the scaling value for the texture, and a host of other variables, so you should derive your own equations for this task. Also, you can use a simple translation when the viewer looks up and down (or turns right and left). This is a 2D translation, and quite trivial. The only thing this method cannot easily handle is rotation about the z axis, which would require one to rotate the bitmap. Depending on the size of the bitmap, this may or may not be fast enough. Spherical mapping is expensive, as you've seen here. However, there are several ways to cut down on that cost, and we'll explore at least of those ways presently. Before tackling a large project, it is advisable to start with a smaller, toned-down version of same. And spherical mapping is certainly a large project. Let's go back in time a few years, and tackle a similar project, one that has an elegant solution that may be applicable to our current dilemma... Suppose we have our 2.5D engine running, and we want to add a horizon in the distance; say a couple of bitmap buildings, or a majestic view of some alien mountain. What can we do? We could draw the mountain using 2D scrolling techniques. This is quite fast, and relatively easy to code. However, if you tried such a technique you would soon discover that the scrolling mountain would look flat, lacking perspective. A few minutes of thought will tell you why this is so. In order to correct this problem, it is necessary to introduce perspective to our mountain bitmap. In other words, we must find a way to use our projection equations on the bitmap. In order for us to do this, we must give our bitmap a z value, representing the distance from the viewer to the bitmap. Once we do this, we can calculate the distance to each vertical strip of the bitmap (because this is a 2.5D engine, each vertical strip has a constant distance). Figure 1 shows a top-down view of this. Figure 1. Bitmap ----------------------- <- Z value \ \ \ <- Line we want to calculate distance of \ \ \ Viewer We can use the Pythagorean Theorem to calculate the distance. If x is the x coordinate of the bitmap (calculated by x'z/d), and z is the z value of the bitmap, the equation becomes the following: Distance = Square_Root ( X * X + Z * Z ) As before, x and z are constant for each pixel, and can be precalculated in a 1-dimensional table. All that's needed is the projection equation: xd x' = -------- Distance Note: since these are vertical strips, there is no need to calculate a y distance. You will always start at the same y location for each strip. Using these equations won't give the expected results. Sure, the bitmap will be scaled according to perspective, but there will be gaping holes in- between the vertical strips (unless your careful). In order to eliminate this problem, you can scale the vertical strip in the x coordinate. A much simpler solution would be drawing copies of the same vertical strip until you came to the position of the next one. The equations I gave you give "perfect" results. In other words, they give accurate values for each vertical strip. I doubt that games actually use such a high degree of accuracy when drawing their horizons. Instead, I suspect that they use an approximation to these perfect projection methods. Most approximation methods start backwards. That is, their designers look at the results the perfect methods give, and they try to emulate it with an approximation. Let's look at figure 2 for a rough approximation of what a perfect method might give us. Figure 2. Viewport __________________ | | | |||| | | | | | | |||| | | | | | | |||| | | | | | | |||| | | | | | | |||| | | | | | | |||| | | | | | | |||| | | | |__|_|_||||_|_|__| Where each vertical strip is actually a texture strip. Obviously, we would scale these strips to fill the holes, but you get the idea. It looks as if we can create a rough approximation by basing the scale on the distance from the origin (center of the screen). A simple equation could be written as follows: Distance_From_Origin = | x' - Center_Of_Screen | X_Scale = Distance_From_Origin / T Where T is an arbitrary number that you can choose visually (trial and error) or mathematically (if you know all the variables). If you look closely at the drawing, you can see that roughly 2/3 of the texture strips are balanced in the center of the viewport. This is the reason for the T term. By choosing T so that 2/3 of the texture strips fall in the center, you can increase the realism of the mapping. Furthermore, if you choose T so that it is a power of 2, you can use a simple shift to accomplish this (or use the look- up-table idea). Now that we've figured out a reasonable approximation to our mountain mapping, let's see if we can apply this technique to our spherical mapping case. We know roughly how spherical mapping should look: just like the 2.5D mapping except in two dimensions. In order for us to find the distance from the origin, it is necessary to use the Pythagorean theorem (or equivalent). This involves one square-root per calculation. Fortunately, there are lines where the z is constant. These lines are circular in appearence. This means we will use a square root a maximum of (Screen_Width / 2) times per frame. In full-screen 640x480, this is 320 square roots per frame, which is reasonable. Furthermore, these square roots are constant from one frame to the next, which means we could use a square root table that gave us the 320 square roots. Because this is only 640-1280 bytes, it is easy to manage. Also, due to the scale of the 2D circles (discussed shortly), we will end up using roughly 1/3 of our square-root table. In order for use to take advantage of these constant z lines, we must draw the sky using circles (not filled in circles, just the border of circles). These are 2D circles, so they can be drawn reasonably fast. The only problem that arises is clipping. As you draw a circle that leaves the viewport (or part thereof), you must clip certain parts of the circle. Also, when drawing the circles, you must be able to handle variable widths. This will make sense if you remember our discussion of "holes", which appear if you don't scale the strips. We working in 2-dimensions (as opposed to 1), so we must scale vertically as well as horizontally. Thus, each circle that is drawn farther from the origin will be drawn slightly wider than the previous one. There are many books that cover the drawing of 2D circles, including variable widths, so we will not concern ourselves with the details. The only thing that's missing is texture mapping. As you're drawing the circles, you must step in the texture map in a circular fashion. We can calculate the actual texture coordinates like we calculated them before: finding the world x and y for each screen point. This looks like two multiplications per pixel. However, you can calculate a single value, and then write a separate circle function to step in the texture coordinates. This means there are absolutely no multiplications per pixel. Only the two circular function increments (which, in most cases, are just additions or error terms). Rotation about the x and y axis is a simple 2D skew of the texture. Rotation on the z axis presents the same problem as our old method: you'll need to rotate the bitmap. Another method you might want to investigate is assigning each texel (textured pixel) a polar coordinate, which you could translate into a Cartesian coordinate. I have seen no way to speed this method up, so I won't explain it in detail. The last method we'll discuss involves calculating a triangular mesh, and mapping the sky onto this triangular mesh (which is circular in appearance). You can eliminate most of the triangles by observing that 1/4 (or less) of the sky is visible in each frame. The only thing that presents a problem is the actual texture mapping. If you have a fast texture mapper, you should consider using this method. ------------------------------------------------------------------------------- | Final Words | ------------------------------------------------------------------------------- This document should provide enough information to get you started in the world of spherical mapping. You will doubtless invent your own ways to do it faster and/or better than the methods I've described. This text is meant to be an introduction, and not a complete tutorial. Thus, several other methods have been left out, mainly because of their relative complexity compared with the techniques described here. I may have gotten a few equations wrong, or even a description. If so, please report them to me so that I may correct them. And with these word I leave you, and go off to some strange world filled with red and blue pages.... Still figuring out which one to trust, -John De Goes - Freelance Game Programmer ////// // // // //// //// // // // // // // // // // // // // // // ////// ////// // ///// // // // // // // // // // // // // // // // // // // // // ///// //// // // ///// //////