This Article Is Taken From The Game Programming MegaSite, A Definitive Resource For Game Developers!

Voxel Texturing
By: Martin Weiner and Jon Wise

In this paper, we present our new graphical rendering concept called Voxel Texturing. It is a derivative of voxel landscaping and texture mapping. In Voxel Texturing, three-dimensional objects are rendered from a single polygon with a voxel landscape mapped on it. This technique has resulted in both large speed increases and increased quality over flat polygonal rendering. Voxel-textured polygons are very easy to manipulate. Memory requirements are significantly decreased. Complex three-dimensional effects are achieved faster and with greater ease.

Introduction

Voxel Texturing is a derivative of two methods of rendering commonly used today. Voxel rendering^1,2 is commonly used for creating landscapes because of its ability to handle rough surfaces without compromising speed. These landscapes are made of lines, or voxels, drawn from a pixel on a flat bitmap (note: the term ‘voxel’ can also refer to a cubic unit, but for this paper, we assume a line). Texture mapping^3,4,5,6,9 is commonly used in rendering objects with easy manipulation. Texture mapping onto polygons is used in most real-time simulations (for example, games) because of its speed. However, the objects made from these textured polygons can only have a few polygons to maintain an average of fifteen to twenty frames per second. Thus, objects appear "blocky" because the edges are usually easily visible and unrealistic. When voxel landscaping is combined with flat polygonal texturing, the ease of manipulation, speed, and versatility of polygonal rendering is combined with the realism, quality, and ease-of-manipulation of voxels creating a high-speed rendering system with all of the beneficial qualities of both rendering methods with few limitations. We have denominated this rendering system "Voxel Texturing."

We created Voxel Texturing to speed up rendering of objects, to increase quality and definition of rendered objects, and to increase ease of object creation. Voxel Texturing, after testing and rendering, does exceed current rendering in speed, versatility, definition, resolution, and creation. The concept involves replacing the pixels of a textured polygon (in three-dimensional space) with lines perpendicular to the polygon. The height of each of these lines is specified in a height-map. Thus, the final rendered product consists of a voxel landscape mapped onto a polygon. With variable voxel heights, a few voxel-textured polygons (generally two polygons) can make entire objects, whereas with flat polygonal rendering, an equivalent object would need hundreds or thousands of polygons. Thus, rendering speed is significantly increased over flat polygonal rendering. In addition, quality can increase. Since Voxel Texturing involves a surface made of pixels rather than polygons, then the highest definition is exactly one pixel. Therefore, the highest definition possible is easily achieved (lower definition can be achieved by make a level surface) allowing real-time simulations to have movie-quality objects. With flat-polygonal rendering, many small polygons must be created to equal the pixel definition of voxel texturing. Another type of rendering, volume rendering^7,8, can achieve maximum quality. This method involves placing voxels, in this case voxels are referring to a cubic area, or volume element, in three-dimensional positions specified by a three-dimensional array. Volume rendering requires a three-dimensional matrix that requires every pixel to be drawn. For a 100x100x100 object, one million pixels would have to be rendered, making this method too slow for real-time simulation while requiring immense storage and each of the one million pixels to be drawn. Voxel Texturing can replace volume rendering as well, in most cases by achieving equivalent quality but with improved speed. For high-quality rendering, Voxel Texture rendering is most often the best choice. Considering that an object created with Voxel Texturing consists of raised lines, the creation of an object is as simple as drawing a topography map in a paint program with colors representing heights.

In comparison with creating an object with flat polygons, Voxel Textured objects are much easier to create because flat polygons require special hardware (most commonly, a magnetic positioning pen to plot points of an object in the computer) for rendering actual objects. If this hardware is not used, painstaking creation of every vertex to make polygons small enough to create a smooth surface is required. Voxel Texturing only requires a two-dimensional object (for example, a photograph) and a paint program to create voxels. Voxel Texturing is made from a two-dimensional picture instead of chopping up a picture to make each piece or polygon of the picture. As an example of the speed increase with Voxel Texturing, a sphere with one thousand polygons was rendered fifty times faster with Voxel Texturing. With this speed increase being one of the smaller increases in speed clocked, there is little doubt that Voxel Texturing will replace, or at very least augment, every type of rendering in existence today.

Rendering Procedure of a Voxel Textured Polygon

1. 1. A picture (texture) and height map are created (see procedure: "Creating a Voxel Textured Polygon"). The vertices of the polygon are assumed to be co-planar, and the polygon is assumed to be a quadrilateral.
2. 2. Normal polygonal texturing is applied. In the case of perspective-correct rendering, each pixel along the polygon is projected. A line, in the final product, replaces each of these pixels. The corresponding height map is also textured.
3. 3. To ensure that the voxels are perpendicular to the polygon surface, a vector cross product is performed using any three points of the polygon. The returned number is the normal to the polygon.
4. 4. From each point on the polygon, a line is projected parallel to the polygon’s normal. This line has a length equal to the height specified on the height map (at the corresponding point) and a color equal to the corresponding number on the texture map. The line starts from the pixel being extended.
5. 5. Once every line has been drawn, the process is complete.

Creating a Voxel Textured Polygon

1. 1. As normally performed in creating a flat polygon, a picture is created to apply to the polygon as a texture.
2. 2. To create the height map, a paint program can be used to draw a topography map. This can be done by using colors to represent heights considering the colors represent numbers. The numbers (colors) from the topography map are read by the engine as heights.
3. 3. Once the picture and height map are finished, the process is complete and the values are stored. In special programs we have written, a paint program and voxel editor are combined and the values are stored in a single file.

Shading a Voxel Textured Polygon

Note: To achieve shading, the angle of the surface and the vector of a light source are required.

1. 1. The position of a surface pixel and its four adjacent surface pixels must be found (if a pixel is on the side of a height map so that there are fewer adjacent pixels, as many as possible are used).
2. 2. Four vectors must be found by subtracting the four adjacent pixel positions from the center (once again, if there are fewer adjacent pixels, fewer vectors can be found).
3. 3. A cross product is run between the center and two adjacent vectors. Once this cross product is run on each adjacent vector, four normals should now be known.
4. 4. The four normals are averaged to get a single normal representing the center pixel.
5. 5. This normal is normalized.
6. 6. A dot product performed on this new normal and the vector of the light source yields a number between -1 and 1. The closer the number is to -1 or 1, the brighter the pixel should be.
7. 7. The value that is returned is multiplied times the red, blue, and green components of the center pixel’s color. The returned numbers represent the colors of the shaded voxel.
8. 8. Once every voxel has been shaded (steps 1-7), the process is complete.

Procedural Analysis

Since creating a voxel-textured polygon involves simply drawing a height map and a picture, voxel-textured objects are much easier to create than objects composed of flat polygons. Whereas an object rendered with flat polygons would require well over a thousand polygons to appear smooth, Voxel Texturing requires simply raising voxel heights in succession. Flat polygons usually require professionals or expensive equipment to create anything of quality. However, with Voxel Texturing, objects can be created with such ease that almost any person can make extremely high-quality objects. Objects digitized or scanned can be converted into three-dimensional objects simply by raising the pixels of the image. With flat polygons, the digitized image has to be separated and then positioned in three dimensions. Thus, the quality of a real person, object, or just about anything can be copied into the three-dimensional world of the computer with greater speed and ease.

Data

This data represent benchmark tests run with our programs. All data were collected at the same distance (Z) from the camera (viewing point in the computer). The wire frames of the spheres are below (figures 3,4). The wire frame of the voxel-textured sphere would just be a single polygon because voxels are spawned from it. Notice that to make the same object, fewer voxel-textured polygons are needed. To make a sphere, two voxel-textured polygons are laid on top of each other (each with an opposite vector) so two hemispheres can make a full sphere. The reason that voxel-textured polygons can have any definition is that they can easily attain the highest definition by varying voxel heights in many places. By making voxels have constant slopes (an area of constant slope), a lower definition can be attained. According to the data, one voxel-textured polygon is equal to approximately ten flat polygons. However, an entire object can be created with one voxel-textured polygon so that Voxel Texturing will almost always speed up and increase the resolution of an object. If most plain objects use six polygons (cube), if the time for four more polygons were allocated, then a voxel-textured polygon could be used to give the object maximum quality. Also, it is important to realize that the engine used could still greatly benefit from more optimizations. By dividing the high-definition sphere composed of flat polygons (figure 5), which is still not equal to the definition of a voxel-textured polygon, by the voxel-textured sphere, the speed increase is found. By using voxel-textured polygons, the speed increase is greater than 50.5 fold (since the definition of the voxel-textured polygon is still higher). Comparing our data to other engines, such as Micro Lathe’s^« engine, better data turns up. Rendering a 1,000 polygon sphere in Micro Lathe^« took about 5.13 seconds. Thus, using our Voxel Texturing engine would be 142.5 times faster. Once again, the best definition spheres can be created with only two voxel-textured polygons (.036 seconds). A volume rendered sphere took even more time but obtained the same definition possible with Voxel Texturing. A volume-rendered sphere took approximately 6.35 seconds. By using Voxel Texturing, 176.3 fold increase in speed occurs.

Pictures

Figure 1 - A voxel landscape. Notice the smooth surfaces and high definition.

Figure 2 - A polygon made of only a few polygons such as is used in real-time simulations. Notice the "blocky" outline and defined edges.

Figure 3 - A wire frame of a low-definition olygon.

Figure 4 - A wire frame of a high definition polygon.

Figure 5 - A flat polygon sphere with texture mapping.

Figure 6 - A voxel-textured polygon showing a dome shape.

(Notice the smooth curvature. This took 1 voxel-textured polygon. It would probably take 150 flat polygons to equal the quality.)

Figure 7 - A voxel-textured picture of a "smiley face."

The comparison flat is in the upper left. Notice the smooth curvature of the eyes (specified by varying heights on the height map).

Figure 8 - This voxel-textured polygon represents a hemisphere.

(Notice the smooth curvature that would normally require a couple hundred flat polygons.)

Figure 9 - A voxel-textured plane.

As a reminder, this, and all of the previous voxel-textured items, can be rendered in approximately .018 to .036 seconds (depending on complexity).

Uses of Voxel Texturing

Voxel Texturing can replace most methods of rendering. Because Voxel Texturing is extremely fast while maintaining digitized quality and definition, Voxel Texturing is perfect for use in real-time simulations. Walls, floors, and ceilings can be rendered with true texture rather than with artists’ tricks and flat surfaces. Thus, side views of walls and structures show accurate renditions of what the artist intended. Currently, our algorithm supports an average rendering speed of twenty flat polygons to one voxel-textured polygon. This represents preliminary results and can be optimized many times over. As an example, when rendering dice, six polygons would usually be used, each with a different texture, forming a cube. However, dice are not cubes, they are rounded and curved on the edges and have small semi-circles cut out. This holds true for most objects. Thus, it may take an extra hundred polygons to make a perfect, true-to-life die. One voxel-textured polygon can make this same object in a fraction of the time.

Objects that require great detail and work to manipulate, such as faces with changing expressions, can be rendered with Voxel Texturing to create maximum realism. With voxel texturing, an actual face can be rendered onto a head in three dimensions, and the face can change as though it were part of an animation. The height map can also change with the texture to correlate with moving parts.

Since an entire object can be rendered with one voxel-textured polygon, movement requires fewer vertex transformations than with flat polygonal rendering. For an object to be rotated, only a few vertices of the voxel-textured polygon must be rotated; whereas with flat polygonal rendering, it might be necessary to rotate well over a thousand vertices. The same holds true for regular transformations and scaling.

Varying the sizes of the voxels on the height map can create many effects. By lowering values, effects such as weapon blasts can be "carved" out of the Voxel Texture to make the appearance of a blast radius in a wall, ceiling, or floor. By lowering values to zero, a hole can be created in the wall, or perhaps the entire wall could be decimated, in which case the engine should remove the wall from the game to save time. In simulations involving blasts Voxel Texturing supplies the means necessary to show the effects of an explosion easily, cheaply, and quickly.

Voxel Texturing is a perfect solution to the slow speed that exists in the Internet and other low bandwidth networks. By sending over a picture and height-map, only a list of commands must follow to move the object in three dimensions on the client computer. Thus, instead of sending over a picture for every frame (as is done with most Internet animations), only two frames are sent over. After that, commands, which may only take a byte each, can be passed at increased rates. By putting a plug-in on the client’s computer that reads and displays voxel textures, Voxel Texturing could replace most animations and clips on the Internet today.

Three-dimensional animations can be performed simply by altering the texture (as is normally done in videos and animations) and by altering the height map to correspond with the texture. Or, a pseudo method of animation would be to make a base height map which is constant with a changing texture. From a distance, this would appear realistic.

Voxel Texturing has the ability to achieve effects in real-time not attainable with other rendering methods. Our base-shading algorithm (See "Shading a Voxel Textured Polygon"), not including the color transformation, can give the vectors of each surface. These vectors can be used in reflection, shading, and lighting. Reflection is most impressive. By compromising a minute amount of speed, mirrors can be created with dents, ripples, and just about any effect (including changing voxel heights, which creates some interesting effects). By sending out a ray from a surface pixel parallel to its normal, an intersecting pixel can be found. The voxel color is replaced with this pixel so that it appears to be reflecting this pixel. Lighting and shading are based on the algorithm mentioned above ("Shading a Voxel Textured Polygon").

Optimizations

When creating objects with voxel texturing, there is a high probability that only a small fraction of most voxels is seen (that area that is not covered by other voxels). To avoid drawing covered areas, the lowest adjacent voxel height can be found by checking the surrounding heights on the height-map and starting the voxel from that lowest point (as opposed to starting from the underlying polygon).

Voxel Texturing can be used in conjunction with flat polygonal rendering in many instances to achieve better results. When something is perfectly flat or is small enough that a voxel textured polygon is not necessary, flat polygonal rendering is a valid substitute.

Much information can be pre-stored to avoid unnecessary calculations by the engine. The texture and height-map are obviously stored. The vectors of the surface pixels can also be pre-computed. Also, run-length-encoding can be used on the height map because there is a high probability that many values are the same (for example, zero would be a common value for unseen areas).

Collision detection can be greatly enhanced by creating an invisible box (not displayed) that surrounds the voxel texture. This box would specify the minimums and maximums of the voxel texture (in other words, it would be a perfect fit for the voxel texture). Thus, the engine can detect if the surrounding boxes of two voxel-textured polygons are intersecting. If a box does intersect, further collision detection would occur, such as detecting whether or not some voxels intersect.

Most optimizations for flat polygonal rendering can be used for Voxel Texturing. However, a few do not. BSP trees for static objects can be used to specify walls. If the wall is destroyed however, the texture cannot be removed for fear of disrupting the BSP tree (unless it is specially designed to be dynamic). Otherwise, a BSP tree would work as an advantage. Back face culling is not worth implementing for voxel textures. The only case in which a voxel texture could be unseen would be if its vector were equal to the camera’s vector and both their positions were collinear. In most other cases, the voxels may be seen extending from the side. It is recommended, however, that a simulated scene have all voxel-textured polygons that cannot possibly be seen (for example, the other side of a sky) removed or tagged so the engine never draws them.

Conclusion

Voxel Texturing has the speed, versatility, ease-of-creation, resolution, definition, and low storage usage to replace or at least to improve all current forms of rendering. The fact that a voxel-textured polygon is created in a two-dimensional space (the height map and picture) allows this rendering system to be significantly easier to work with than the three-dimensional space required for creating a flat polygonal object. Thus, Voxel Texturing is perfect for Internet use because of the low bandwidth most people have. The quality that Voxel Texturing can easily supply allows for Voxel Texturing to work to create almost any object more efficiently and more quickly. For almost every three-dimensional simulation that exists, Voxel Texturing can supply more quality, speed, and versatility than any other rendering system.

Bibliography

^1,3 De Goes, John (1996). 3D Game Programming With C++. Scottsdale, AZ: Coriolis Group Books

⁴ Walnum, Clayton (1994). Creating Turbo C++ Games. Indianapolis, IN: Que Corporation

^2,5 LaMothe, RatCliff, Seminatore, & Tyler (1994). Tricks of the Game Programming Gurus. Indianapolis, IN: Sams Publishing

⁶ Wright, Richard S. (1996). OpenGL Superbible. Corte Madera, CA: Waite Group Press

⁷ Ladic, Lance (1995). Volume Rendering vs. Surface Rendering. http://www.cs.ubc.ca/spider/ladic/volviz.html

⁸ Lacroute, Philippe & Levoy, Mark (1994). Fast Volume Rendering Using a Shear-Warp Factorization of the Viewing Transformation. http://www-graphics.stanford.edu/papers/shear/

⁹ Ebert, D., Musgrave, K., Peachey, P., Perlin, K., and Worley, S. (1994). Texturing and Modeling: A Procedural Approach. Baltimore, Maryland: AP Professional