Z-buffering

From Wikipedia, the free encyclopedia

(Redirected from Z buffer)

Jump to: navigation, search

Z-buffer data

In computer graphics, z-buffering is the management of image depth coordinates in three-dimensional (3-D) graphics, usually done in hardware, sometimes in software. It is one solution to the visibility problem, which is the problem of deciding which elements of a rendered scene are visible, and which are hidden. The painter's algorithm is another common solution which, though less efficient, can also handle non-opaque scene elements.

When an object is rendered by a 3D graphics card, the depth of a generated pixel (z coordinate) is stored in a buffer (the z-buffer). This buffer is usually arranged as a two-dimensional array (x-y) with one element for each screen pixel. If another object of the scene must be rendered in the same pixel, the graphics card compares the two depths and chooses the one closer to the observer. The chosen depth is then saved to the z-buffer, replacing the old one. In the end, the z-buffer will allow the graphics card to correctly reproduce the usual depth perception: a close object hides a farther one.

The granularity of a z-buffer has a great influence on the scene quality: a 16-bit z-buffer can result in artifacts (called "z-buffer fighting") when two objects are very close to each other. A 24-bit or 32-bit z-buffer behaves much better. An 8-bit z-buffer is almost never used since it has too little precision.

Additionally, precision in the z-buffer distance values is not spread evenly over distance. Nearer values are much more precise (and hence can display closer objects more properly) than values which are farther away. Generally, this is desirable, but sometimes it will cause artifacts to appear as objects become more distant. A variation on z-buffering which results in more evenly distributed precision is called w-buffering.

At the start of a new scene, the z-buffer must be cleared to a defined value, usually 1.0, because this value is the upper limit (on a scale of 0 to 1) of depth, meaning that no object is present at this point through the viewing frustum.

The invention of the z-buffer concept is most often attributed to Edwin Catmull. Actually, also Wolfgang Straßer described this idea in his 1974 Ph.D. thesis¹.

On recent PC graphics cards (1999-2005), z-buffer management uses a significant chunk of the available memory bandwidth. Various methods have been employed to reduce the impact of z-buffer, such as lossless compression (computer resources to compress/decompress are cheaper than bandwidth) and ultra fast hardware z-clear that makes obsolete the "one frame positive, one frame negative" trick (skipping inter-frame clear altogether using signed numbers to cleverly check depths).

Texture Mapping

Introduction

Mapping is a technique used to add surface detail to otherwise flat and featureless faces without increasing the polygon count. Mapping information is stored in two dimensions and applied to a polygon using various interpolations.

Texture Mapping

Colour Mapping would be a more accurate term to describe this technique, but the name Texture Mapping is in more common usage. The technique allows the user to apply an image or a pattern to a flat face or a series contiguous polygons. E.g. apply a 'brick' pattern to a wall or a company logo to a racing car. Textures can be created in any convenient drawing package and usually stored as an array of colour triplets (BitMap).

A texture is accessed as a 2D array of color information, i.e. the RGB components of diffuse reflection. Textures can be of arbitrary size. Each component of the array is known as a texture element or texel. A pair of values are used to index the texture, are know as texture coordinates and are scaled to lie the range . Usually textures are associated with faces in the modeling phase the artist associates each vertex of a polygon with a texture coordinate, however there are techniques to automatically map textures to polygons. Mapping parametric surfaces is a trivial operation as there can be a direct correspondence between surface parameters and texture coordinates.

Inverse Mapping

There are two main approaches to the texture mapping problem. One technique is to map the texture to an object in world-coordinates and then to project each part of the object's surface onto a pixel, effectively 'stretching' the texture over the object. This approach is known as forward mapping. The main drawback with forward mapping is that the texel do not correspond to the pixel boundaries and will require fractional pixel calculations.

Forward Texture Mapping

The more natural approach to integrate with existing renderers is to find a correspondence between a polygon's pixel and a coordinate in texture space, this is inverse mapping.

The role of the renderer is to map a polygon's internal pixels to texture coordinates. This process is usually performed in parallel with an interpolative shading algorithm (e.g. Gouraud). Once the texel corresponding to a pixel is found, the colour information is used in a local lighting model to help compute the colouring for that pixel.

Lecture 9. Adding Realism Through Texture. 2. GR2-00. Adding Realism. Objects rendered using Phong reflection model and Gouraud or Phong interpolated ...

Advanced Computer Graphics AGR. Lecture 3. Viewing - Projections. 2. GR2-00. Viewing. Graphics display devices are 2D rectangular screens ...

Homogeneous Coordinates

One of the many purposes of using homogeneous coordinates is to capture the concept of infinity. In the Euclidean coordinate system, infinity is something that does not exist. Mathematicians have discovered that many geometric concepts and computations can be greatly simplified if the concept of infinity is used. This will become very clear when we move to curves and surfaces design. Without the use of homogeneous coordinates system, it would be difficult to design certain classes of very useful curves and surfaces in computer graphics and computer-aided design.

Let us consider two real numbers, a and w, and compute the value of a/w. Let us hold the value of a fixed and vary the value of w. As w getting smaller, the value of a/w is getting larger. If w approaches zero, a/w approaches to infinity! Thus, to capture the concept of infinity, we use two numbers a and w to represent a value v, v=a/w. If w is not zero, the value is exactly a/w. Otherwise, we identify the infinite value with (a,0). Therefore, the concept of infinity can be represented with a number pair like (a, w) or as a quotient a/w.

Let us apply this to the xy-coordinate plane. If we replace x and y with x/w and y/w, a function f(x,y)=0 becomes f(x/w,y/w)=0. If function f(x,y) = 0 is a polynomial, multiplying it with wⁿ will clear all denominators, where n is the degree of the polynomial.

For example, suppose we have a line Ax + By + C = 0. Replacing x and y with x/w and y/w yields A(x/w) + B(y/w) + C = 0. Multiplying by w changes it to

Ax + By + Cw = 0.

Let the given equation be a second degree polynomial Ax² + 2Bxy + Cy² + 2Dx + 2Ey + F = 0. After replacing x and y with x/w and y/w and multiplying the result with w², we have

Ax² + 2Bxy + Cy² + 2Dxw + 2Eyw + Fw² = 0

If you look at these two polynomials carefully, you will see that the degrees of all terms are equal. In the case of a line, terms x, y and w are of degree one, while in the second degree polynomial, all terms (i.e., x², xy, y², xw, yw and w²) are of degree two.

Given a polynomial of degree n, after introducing w, all terms are of degree n. Consequently, these polynomials are called homogeneous polynomials and the coordinates (x,y,w) the homogeneous coordinates.

Given a degree n polynomial in a homogeneous coordinate system, dividing the polynomial with wⁿ and replacing x/w, y/w with x and y, respectively, will convert the polynomial back to a conventional one. For example, if the given degree 3 homogeneous polynomial is the following:

x³ + 3xy² - 5y²w + 10w³ = 0

the result is

x³ + 3xy² - 5y² + 10 = 0

This works for three-dimension as well. One can replace a point (x, y, z) with (x/w, y/w, z/w) and multiply the result by w raised to certain power. The resulting polynomial is a homogeneous one. Converting a degree n homogeneous polynomial in x, y, z and w back to the conventional form is exactly identical to the two-variable case.

An Important Notes

Given a point (x,y,w) in homogeneous coordinates, what is its corresponding point in the xy-plane? From what we discussed for converting a homogeneous polynomial back to its conventional form, you might easily guess that the answer must be (x/w,y/w). This is correct. Thus, a point (3,4,5) in homogeneous coordinates converts to point (3/5,4/5)=(0.6,0.8) in the xy-plane. Similarly, a point (x,y,z,w) in homogeneous coordinates converts to a point (x/w,y/w,z/w) in space.

Conversely, what is the homogeneous coordinates of a point (x,y) in the xy-plane? It is simply (x,y,1)! That is, let the w component be 1. In fact, this is only part of the story, because the answer is not unique. The homogeneous coordinates of a point (x,y) in the xy-plane is (xw, yw, w) for any non-zero w. Why is this true? Because (xw, yw, w) is converted back to (x,y). As a result, the following is important for you to memorize:

Converting from a homogeneous coordinates to a conventional one is unique; but, converting a conventional coordinates to a homogeneous one is not.

For example, a point (4,2,3) in space is convert to (4w, 2w, 3w, w) for any non-zero w.

The Dimensionality of Homogeneous Coordinates

You perhaps have discovered that homogeneous coordinates need 3 and 4 components to represent a point in the xy-plane and a point in space, respectively. Therefore, a point in space (resp., the xy-plane) in homogeneous coordinates actually has four (resp., third) components. Adding a fourth (resp., third) component whose value is 1 to the coordinates of a point in space (resp., the xy-plane) converts it to its corresponding homogeneous coordinates.

Ideal Points or Points at Infinity

As mentioned at the very beginning of this page, homogeneous coordinates can easily capture the concept of infinity. Let a point (x,y) be fixed and converted to a homogeneous coordinate by multiplying with 1/w, (x/w,y/w,1/w). Let the value of w approach to zero, then (x/w,y/w) moves farther and farther away in the direction of (x,y). When w becomes zero, (x/w,y/w) moves to infinity. Therefore, we would say, the homogeneous coordinate (x,y,0) is the ideal point or point at infinity in the direction of (x,y).

Let us take a look at an example. Let (3,5) be a point in the xy-plane. Consider (3/w,5/w). If w is not zero, this point lies on the line y = (5/3) x. Or, if you like the vector form, (3/w,5/w) is a point on the line O + (1/w)d, where the base point O is the coordinate origin and d is the direction vector <3,5>. Therefore, as w approaches zero, the point moves to infinity on the line. This is why we say (x,y,0) is the ideal point or the point at infinity in the direction of (x,y).

The story is the same for points in space, where (x,y,z,0) is the ideal point or point at infinity in the direction of (x,y,z).

The concept of homogeneous coordinates and points at infinity in certain direction will become very important when we discuss representations of curves and surface.

A Simple Geometric Interpretation

Given a homogeneous coordinate (x,y,w) of a point in the xy-plane, let us consider (x,y,w) to be a point in space whose coordinate values are x, y and w for the x-, y- and w- axes, respectively. The line joining this point and the coordinate origin intersects the plane w = 1 at a point (x/w, y/w, 1). Please verify this fact yourself. The following figure illustrates this concept.

This transformation treats a two-dimensional homogeneous point as a point in three-dimensional space and projects (from the coordinate origin) this three-dimensional point to the plane w=1. Therefore, as a homogeneous point moves on a curve defined by homogeneous polynomial f(x,y,w)=0, its corresponding point moves in three-dimensional space, which, in turn, is projected to the plane w=1. Of course, (x/w,y/w) moves on a curve in plane w=1.

The above figure also shows clearly that while the conversion from the conventional Euclidean coordinates to homogeneous coordinates is unique, the opposite direction is not because all points on the line joining the origin and (x,y,w) will be projected to (x/w,y/w,1). This is also an important concept to be used in later lectures.

1 Computer Graphics Problems. We’ll begin the study of homogeneous coordinates by describing a set of problems from three-dimensional ...

We will need the dot product as well as the magnitudes of each vector. ... The dot product gives us a very nice method for determining if two vectors are ...

How did we know that the cross product pointed in the direction that we’ve ... First, as this figure, implies the cross product is orthogonal to both of the ...

Clipping (computer graphics)

From Wikipedia, the free encyclopedia

Jump to: navigation, search

In rendering, clipping refers to an optimization where the computer only draws things that might be visible to the viewer.

Contents [hide] 1 Examples 2 Non-triviality 3 Video games 4 Algorithms 5 See also

[edit]

Examples

In 2D graphics for example, if the user of an image editing program is modifying an image of the Mona Lisa and has "zoomed in" the view to display only the top half of the painting, there is no need for the program to spend any CPU time doing any of the calculations or memory moves needed to display the bottom half. By clipping the bottom half of the painting and avoiding these calculations, the program runs faster.

In 3D graphics, in a city street scene the computer may have model, texture, and shader data in memory for every building in the city; but since the camera viewing the scene only sees things within, say, a 90° angle, or field of view, the computer does not need to transform, texture, and shade the buildings that are behind the camera, nor those which are far enough to the side that they are off the screen. The clipping algorithm lets the rendering code skip all consideration of those buildings, and the program runs faster.

[edit]

Non-triviality

Clipping is non-trivial, especially for 3D animations: if the objects are built up of, say, polygons, a routine is needed that determines for each polygon whether it is visible within the viewport (i.e. the part of the 3D "world" displayed) or out off the borders. Special care is needed for the case of polygons intersected by the viewport border as their shape has to be adjusted.

While the term "clipping" is generally used to mean avoiding the drawing of things outside the camera's field of view, a related technique is back-face culling, in which polygons within the field of view are not drawn if they would be occluded by other polygons. For example, there is no need to render the polygons comprising the side of a building facing away from the player; they are all completely occluded by the front of the building. Hence the game can save significant rendering time by doing a back-face culling pass before deciding which polygons to draw.

The clipping and back-face culling optimizations both present interesting problems in scenes with a reflective surface visible. For example, problems would ensue if the 3D scene contained a mirror that showed the reflection of a building that had been clipped because the building was behind the camera. To deal with 'true' reflective surfaces (as opposed to the 'fake' reflections of environment maps), the clipper might do a clipping and rendering pass from the point of view of the mirror, and then the normal clipping pass for the camera.

[edit]

Video games

Good clipping strategy is important in the development of video games in order to maximize the game's frame rate and visual quality. Despite GPU chips that are faster every year, it remains computationally expensive to transform, texture, and shade polygons, especially with the multiple texture and shading passes common today. Hence, game developers must live within a certain "budget" of polygons that can be drawn each video frame. (Normally there are 60 video frames drawn per second on an American or Japanese (NTSC) video game console, or 50 video frames per second on a European (PAL) console.) To maximize the game's visual quality, developers prefer to establish the highest possible polygon budget; therefore, every optimization of the graphics pipeline benefits the polygon budget and therefore the game.

In video games, then, clipping is a critically important optimization that speeds up the rendering of the current scene, and therefore allows the developer to increase the renderer's polygon budget. Programmers often devise clever heuristics to speed up the clipper, as it would be computationally prohibitive to use line casting or ray tracing to determine with 100% accuracy which polygons are and are not within the camera's field of view. One of the most popular methods for optimization is the use of Octrees to partition scenes into rendered and non-rendered areas.

The clipping problems introduced by reflective surfaces are generally avoided in games as of 2005 by simulating reflections without actually doing all the calculations that would be necessary for accurate reflections.

[edit]

Algorithms

Several clipping algorithms have been devised.

• Line clipping algorithms:
  • Cohen-Sutherland
  • Liang-Barsky
  • Nicholl-Lee-Nicholl

• Polygon clipping algorithms:
  • Sutherland-Hodgman
  • Weiler-Atherton

[edit]

See also

• Bounding volume

Very useful in understanding how this method of clipping works. Make sure you have Java installed otherwise your computer will cry about it.

Ray Tracing: Graphics for the Masses

by Paul Rademacher

Although three-dimensional computer graphics have been around for many decades, there has been a surge of general interest towards the field in the last couple of years. Just a quick glance at the latest blockbuster movies is enough to see the public's fascination with the new generation of graphics. As exciting as graphics are, however, there is a definite barrier which prevents most people from learning about them. For one thing, there is a lot of math and theory involved. Beyond that, just getting a window to display even simple 2D graphics can often be a daunting task. In this article, we will talk about a powerful yet simple 3D graphics method known as ray tracing, which can be understood and implemented without dealing with much math or the intricacies of windowing systems. The only math we assume is a basic knowledge of vectors, dot products, and cross products. We will skip most of the theory behind ray tracing, focusing instead on a general overview of the technique from an implementation-oriented perspective.

What is Ray Tracing?

Ray tracing is a technique for rendering three-dimensional graphics with very complex light interactions. This means you can create pictures full of mirrors, transparent surfaces, and shadows, with stunning results. We discuss ray tracing in this introductory graphics article because it is a very simple method to both understand and implement. It is based on the idea that you can model reflection and refraction by recursively following the path that light takes as it bounces through an environment


Figure 1. Ray traced image

Some Terminology

Before presenting the full description of ray tracing, we should agree on some basic terminology. When creating any sort of computer graphics, you must have a list of objects that you want your software to render. These objects are part of a scene or world (Fig. 2), so when we talk about ``looking at the world,'' we're not posing a philosophical challenge, but just referring to the ray tracer drawing the objects from a given viewpoint. In graphics, this viewpoint is called the eye or camera. Following this camera analogy, just like a camera needs film onto which the scene is projected and recorded, in graphics we have a view window on which we draw the scene. The difference is that while in cameras the film is placed behind the aperture or focal point, in graphics the view window is in front of the focal point. So the color of each point on real film is caused by a light ray (actually, a group of rays) that passes through the aperture and hits the film, while in computer graphics each pixel of the final image is caused by a simulated light ray that hits the view window on its path towards the eye. The results, however, are the same.

As you may have guessed, our goal is find the color of each point on the view window. We subdivide the view window into small squares, where each square corresponds to one pixel in the final image. If you want to create an image at the resolution of 640x400, you would break up the view window into a grid of 640 squares across and 400 square down. The real problem, then, is assigning a color to each square. This is what ray tracing does.


Figure 2. The eye, view window, and world.

How it works

Ray tracing is so named because it tries to simulate the path that light rays take as they bounce around within the world - they are traced through the scene. The objective is to determine the color of each light ray that strikes the view window before reaching the eye. A light ray can best be thought of as a single photon (although this is not strictly accurate because light also has wave properties - but I promised there would be no theory). The name ``ray tracing'' is a bit misleading because the natural assumption would be that rays are traced starting at their point of origin, the light source, and towards their destination, the eye (see Fig. 3). This would be an accurate way to do it, but unfortunately it tends to be very difficult due to the sheer numbers involved. Consider tracing one ray in this manner through a scene with one light and one object, such as a table. We begin at the light bulb, but first need to decide how many rays to shoot out from the bulb. Then for each ray we have to decide in what direction it is going. There is really an infinity of directions in which it can travel - how do we know which to choose? Let's say we've answered these questions and are now tracing a number of photons. Some will reach the eye directly, others will bounce around some and then reach the eye, and many, many more will probably never hit the eye at all. For all the rays that never reach the eye, the effort tracing them was wasted.


Figure 3. Tracing rays from the light source to the eye. Lots of rays are wasted because they never reach the eye.
In order to save ourselves this wasted effort, we trace only those rays that are guaranteed to hit the view window and reach the eye. It seems at first that it is impossible to know beforehand which rays reach the eye. After all, any given ray can bounce around the room many times before reaching the eye. However, if we look at the problem backwards, we see that it has a very simple solution. Instead of tracing the rays starting at the light source, we trace them backwards, starting at the eye. Consider any point on the view window whose color we're trying to determine. Its color is given by the color of the light ray that passes through that point on the view window and reaches the eye. We can just as well follow the ray backwards by starting at the eye and passing through the point on its way out into the scene. The two rays will be identical, except for their direction: if the original ray came directly from the light source, then the backwards ray will go directly to the light source; if the original bounced off a table first, the backwards ray will also bounce off the table. You can see this by looking at Figure 3 again and just reversing the directions of the arrows. So the backwards method does the same thing as the original method, except it doesn't waste any effort on rays that never reach the eye.

This, then, is how ray tracing works in computer graphics. For each pixel on the view window, we define a ray that extends from the eye to that point. We follow this ray out into the scene and as it bounces off of different objects. The final color of the ray (and therefore of the corresponding pixel) is given by the colors of the objects hit by the ray as it travels through the scene.

Just as in the light-source-to-eye method it might take a very large number of bounces before the ray ever hits the eye, in backwards method it might take many bounces before the ray every hits the light. Since we need to establish some limit on the number of bounces to follow the ray on, we make the following approximation: every time a ray hits an object, we follow a single new ray from the point of intersection directly towards the light source (Fig. 4).


Figure 4. We trace a new ray from each ray-object intersection directly towards the light source

In the figure we see two rays, a and b, which intersect the purple sphere. To determine the color of a, we follow the new ray a' directly towards the light source. The color of a will then depend on several factors, discussed in Color and Shading below. As you can see, b will be shadowed because the ray b' towards the light source is blocked by the sphere itself. Ray a would have also been shadowed if another object blocked the ray a'.

Reflection and Refraction

Just as shadows are easily handled, so are reflection and refraction. In the above example, we only considered a single bounce from the eye to the light source. To handle reflection we also consider multiple bounces from objects, and to handle refraction we consider what happens when a ray passes through a partially- or fully-transparent object.

If an object is reflective we simply trace a new reflected ray from the point of intersection towards the direction of reflection. The reflected ray is the mirror image of the original ray, pointing away from the surface. If the object is to some extent transparent, then we also trace a refracted ray into the surface. If the materials on either side of the surface have different indices of refraction, such as air on one side and water on the other, then the refracted ray will be bent, like the image of a straw in a glass of water. If the same medium exists on both sides of the surface then the refracted ray travels in the same direction as the original ray and is not bent.


Figure 5. (a) Reflected ray. (b) Refracted ray

The directions of the reflected and refracted rays are given by the following formulas. For a ray with direction V, and a surface with normal N (the normal is just the direction perpendicular to the surface - pointing directly away from it), the reflected ray direction Rl is given by

c1 = -dot_product( N, V )
Rl = V + (2 * N * c1 )

Note that since V, N, and Rl are vectors with x, y, and z components, the arithmetic on them is performed per-component. The refracted ray direction Rr is given by

n1 = index of refraction of original medium
n2 = index of refraction of new medium
n = n1 / n2
c2 = sqrt( 1 - n² * (1 - c1²) )

Rr = (n * V) + (n * c1 - c2) * N

Recursive Reflection and Refraction

Figure 6. Recursive reflection and refraction
Figure 6 shows an example of objects that are both reflective and refractive (it does not show the rays from each intersection to the light source, for the sake of clarity). Note how much more complicated the rays become once reflection and refraction are added. Now, each reflected and refracted ray can strike an object which spawns another two rays, each of these may spawn another two, and so on. This arrangement of rays spawning subrays spawning subrays leads to the idea of a tree of rays. The root node of this tree is the original ray (a in the figure) from the eye, and each node in the tree is either a reflected or a refracted ray from the ray above it. Each leaf of the tree is either where the ray hit a non-reflective and non-transparent object, or where the tree depth reached a maximum. As complicated as it seems, there is actually a very simple way to implement this tree of rays: with recursive function calls. For each point on the view window we call a function trace_ray(), passing it the ray from the eye through the point. If the first object intersected by the ray is non-reflective and non- transparent, the function simply determines the color at the intersection point and returns this color. If this ray strikes a reflective object, however, the function invokes trace_ray() recursively, but with the reflected ray instead. If the intersected object is transparent, the function also calls trace_ray() with the refracted ray as a parameter. The colors returned by these two function calls are combined with the object color, and the combined color is returned. This can be easily expressed in pseudo-code as:

Color trace_ray( Ray original_ray )
{


Color point_color, reflect_color, refract_color
Object obj

obj = get_first_intersection( original_ray )
point_color = get_point_color( obj )

if ( object is reflective )

reflect_color = trace_ray( get_reflected_ray( original_ray, obj ) )
if ( object is refractive )

refract_color = trace_ray( get_refracted_ray( original_ray, obj ) )

return ( combine_colors( point_color, reflect_color, refract_color ))

}

where a Color is the triple (R, G, B) for the red, green, and blue components of the color, which can each vary between zero and one. This function, along with some intersection routines, is really all that is needed to write a ray tracer.

Intersections

One of the basic computations needed by the ray tracer is an intersection routine for each type of object in the scene: one for spheres, one for cubes, one for cones, and so forth. If a ray intersects an object, the object's intersection routine returns the distance of the intersection point from the origin of the ray, the normal vector at the point of intersection, and, if texture mapping is being used, a coordinate mapping between the intersection point and the texture image (discussed later in Texture Mapping). The distance to the intersection point is needed because if a ray intersects more than one object, we choose the one with the closest intersection point. The normal is used to determine the shade at the point, since it describes in which direction the surface is facing, and therefore affects how much light the point receives (see Color and Shading).

Intersecting a Sphere

For each type of object that the ray tracer supports, you need a separate intersection routine. We will limit our ray tracer to handling spheres only, since the intersection routine for a sphere is among the simplest. The following derivation of a sphere intersection is based on [Glassner90], page 388.


Figure 7. Intersection of a ray with a sphere.
Fig. 7 shows the geometry of a ray R (with origin at E and direction V) intersecting a sphere with center at O and radius r. According to the diagram,

v² + b² = c² and d² + b² = r² (by simple geometry)

and so

d = sqrt( r² - (c² - v²))

To determine whether an intersection occurs, we compute the value of d. If d >= 0, then a valid intersection occurs. If the ray does not intersect, then d will be less than zero. After finding the value of d, the distance from E to the intersection point P is (v - d). The pseudocode for all this is:

v = dot_product( EO, V )
disc = r2 - ((dot_product( EO, EO ) - v2 )
if ( disc < 0 )
no intersection
else
d = sqrt( disc )
P = E + (v - d) * V

Color and Shading

There are many different ways to determine color at a point of intersection. Some methods are very simple - as in flat shading, where every point on the object has the same color. Some techniques - such as the Cook-Torrance method [Cook82] - are fairly complex, and take into account many physical attributes of the material in question. We will describe here a simple model known as Lambertian shading or cosine shading. It determines the brightness of a point based on the normal vector at the point and the vector from the point to the light source. If the two coincide (the surface directly faces the light source) then the point is at full intensity. As the angle between the two vectors increases, as when the surface is tilted away from the light, then the brightness diminishes. This model is known as ``cosine shading'' because that mathematical function easily implements the above effect: it returns the value 1 when given an angle of zero, and returns zero when given a ninety degree angle (when the surface and light source are perpendicular). Thus, to find the brightness of a point, we simply take the cosine of the angle between the two vectors. This value can be quickly computed because it is equal to the dot product of the two unit-length vectors. So by taking the dot product of the surface normal and the unit-length vector towards the light, we get a value between -1 and 1. The values from -1 to 0 indicate that the surface is facing away from the light source, so it doesn't receive any light. The value of 0 means the surface is directly perpendicular to the light source (it is at grazing incidence), and so again does not receive any light. Values above 0 indicate that the surface does receive some light, with maximum reception when the dot product is 1.

In case the result of the dot product is zero or below zero, we still may not want that part of the object to be pitch-black. After all, even when an object is completely blocked from a light source, there is still light bouncing around that illuminates it to some extent. For this reason we add a little bit of ambient light to every object, which means that the minimum amount of light that an object can receive is actually above zero. If we set the ambient coefficient to 20%, say, then even in total shadow an object will receive 20% illumination, and will thus be somewhat visible. If 20% illumination is always present, then the remaining 80% is determined by cosine shading. The value 80% in this case is known as the diffuse coefficient, which is just (1 - ambient coefficient). The final color computation is then:

shade = dot_product( light_vector, normal_vector )
if ( shade < 0 )
shade = 0
point_color = object_color * ( ambient_coefficient +

diffuse_coefficient * shade )

Texture Mapping

So far we've assumed that every point on a given object has the same basic color, varied only through cosine shading to make it lighter or darker. However, there is another way to color objects, which assigns entire images to them instead of single colors. Known as texture mapping, in effect we ``paste'' images to the surfaces of objects. An example of this which certainly everyone will recognize is in the ``Doom''-style games, where walls are drawn using stone or metal patterns instead of single colors. These program start off with small images of those patterns (called textures), and then cover the walls with these images. This covering is called a mapping because it maps pixels from the image onto the points comprising the walls. Texture mapping is much slower than assigning a single color to every object, since it requires determining and then fetching the appropriate texture pixel corresponding to every point we draw. It has become very common in the last few years, however, thanks to advances in processor speeds and faster graphics algorithms.

While texture mapping produces very nice effects, it is not a difficult feature to implement. All that is needed is a routine which returns the coordinates of a texture pixel given the coordinates of a point on an object. The texture coordinates are refered to as (u, v), where u is the horizontal location of the point in the image, and v is the vertical location of the point. The ray tracer then fetches the pixel at (u,v) from the texture image, and adjusts it as necessary using cosine shading to make it lighter or darker.

Texture Mapping Spheres

The easiest way to texture map onto a sphere is by defining v to be the latitude of the point and u to be the longitude of the point on the sphere. This way, the texture image will be ``wrapped'' around the sphere, much as a rectangular world map is wrapped around a globe.


Figure 8. Mapping a rectangular world map onto a globe

Figure 9. Mapping a texture image onto a sphere
First we find the two unit-length vectors V_n and V_e, which point from the center of the sphere towards the ``north pole'' and a point on the equator, respectively. We then find the unit-length vector V_p, from the center of the sphere to the point we're coloring. The latitude is simply the angle between V_p and V_n. Since we noted above that the dot product of two unit-length vectors is equal to the cosine of the angle between them, we can find the angle itself by

phi = arccos( -dot_product( Vn, Vp ))

and since v needs to vary between zero and one, we let

v = phi / PI

We then find the longitude as

theta = ( arccos( dot_product( Vp, Ve ) / sin( phi )) ) / ( 2 * PI)
if ( dot_product( cross_product( Vn, Ve ), Vp ) > 0 )

u = theta
else

u = 1 - theta

The last comparison simply checks on what side of the equator vector V_e the point is (clockwise or counterclockwise to it), and sets u accordingly. Now the color of the point is the pixel at (u * texture_width,v * texture_height ) within the texture image. For more info on this, read [Glassner89], page 48.

Putting it All Together

Now that we've covered the basic of ray tracing, intersections, color, and texture mapping, it is still probably not very obvious how to piece these concepts together into a working program. Here, then, is an overview of how a simple ray tracing program might work:

First, we need to define the scene we want to render. We create a text input file that describes the objects in the scene by specifying the location, attributes (such as radius for spheres), color, and optional texture map of each object. We then specify where the camera and the view window should be located. For simplicity, we can assume that the camera is always on the Z axis pointing towards the origin, and that the view window is located at the origin. We also need to determine the size of the view window, which is specified by a field of view (FOV) parameter. The field of view determines the view window's size, and therefore how much of the scene is visible. Based on these parameters, we can calculate the top-left and bottom-right corners of the window.

Now that we have the top-left and bottom-right points, we divide the window into the resolution required for our output picture, e.g., 640 by 400. We step through each of the 640x400 points on the view window, defining a ray from the eye to that point. For each ray, we calculate its intersection with all the objects in the scene. If it does not intersect any objects, we set the ray - and therefore the corresponding pixel - to the background color. Otherwise, we choose the object with the closest intersection. If the object is reflective, we call the ray-tracing function again recursively, passing it the reflected ray direction. If the object is transparent, we do the same thing with the refracted direction. The calling function then computes the color for the object it is dealing with, and combines this color with the reflected and refracted rays' colors.

When the original ray-tracing call from the eye to the view window returns, the color will be the final color for that pixel - taking into account reflection, refraction, and shadows. This pixel color is then written out to the output file. When all points on the view window have been processed this way, you will have a finished ray-traced picture.

Sample images

Here are some images created with the simple code available online. They demonstrate the techniques described in this article. For some truly astounding images created with full-featured, free ray tracers, check out the links in the Internet Resources section below.

Internet Resources

There are many ray tracing resources on the Internet. Here's some of the best:

• There's a free, powerful ray tracing program called POV-Ray (for Persistence of Vision Ray Tracer), available for almost every platform at http://www.povray.org. It comes in both binary and source form, and their web page has links to other ray tracing information as well as a beautiful gallery of images created with POV-Ray.
• Radiance ( http://radsite.lbl.gov/radiance/HOME.html ) is a ray tracer geared towards analysis of lighting, rather than just making pretty pictures.
• Rayshade ( http://www-graphics.stanford.edu/~cek/rayshade/rayshade.html) is a fast ray tracer with support for parallel processing.
• The Blue Moon Rendering Tools ( http://www.seas.gwu.edu/student/gritz/bmrt.html) is a ray tracer that implements the Renderman shading language. This language is used by such companies as Industrial Light & Magic and Pixar to create just about every mind-blowing computer special effect in the last twenty years. The professional software is rather expensive, so this free package by Larry Gritz is an ideal way to play with the Renderman language.
• A good general ray tracing page can be found at http://www.cm.cf.ac.uk/Ray.Tracing/, with links to ray tracing information and more ray-tracing software.
• The Ray Tracing News ( http://www.acm.org/tog/resources/RTNews/html/index.html ) is a electronic publication with lots of good info on Ray Tracing.

References and Suggested Reading

1

Cook, R.L., and Torrance, K.E. A Reflectance Model for Computer Graphics. ACM Trans. on Graphics 1, 1 (Jan 1982)

2

Foley, J. D., and Van Dam, A. Computer Graphics: Principles and Practice, Second Edition. Addison-Wesley New York, N.Y. 1990.

3

Glassner, A. (ed) An Introduction to Ray Tracing. Academic Press New York, N.Y. 1989.

4

Glassner, A. (ed) Graphics Gems. Academic Press New York, N.Y. 1990.

5

Watt, A., and Watt, M. Advanced Animation and Rendering Techniques. Addison-Wesley New York, N.Y. 1990.

---

The Algebraic Solution

The mathematical equation for a sphere is given as
(x-a)² + (y-b)² + (z-c)² = r²
Where (x,y,z) is any point on the sphere, (a,b,c) is the location of the sphere's center and r is the sphere's Radius. We can also say that
X=x_o+x_dt
Y=y_o+y_dt
Z=z_o+z_dt
Where (x_o,y_o,z_o) is the origin of the ray and (x_d,y_d,z_d) is the camera ray's direction. Substituting the ray's equation into the sphere's equation, we get
(x_o+x_dt-a)²+ (y_o+y_dt-b)²+ (z_o+z_dt-c)² = r²
Which simplifies to
(x_d² + y_d² + z_d²)t²+ [2[x_d(x_o - a) + y_d (y_o - b) + z_d (z_o - c)]]t + [(x_o - a)² + (y_o - b)² + (z_o - c)² - r²] = 0
We can then solve for t in order to determine whether the sphere is intersected with the quadratic formula (At² + Bt + C = 0) Where
A = x_d² + y_d² + z_d²
B = 2[x_d(x_o - a) + y_d (y_o - b) + z_d (z_o - c)]
C = (x_o - a)² + (y_o - b)² + (z_o - c)² - r²
Then
T = -B+-sqrt(B²-4AC)
     ------------------------
                   2A
If B²-4AC<0, then ray and sphere do not intersect (the intersections are imaginary numbers)
If B²-4AC=0, then the ray intersects the sphere at exactly 1 point
If B²-4AC>0, then the ray intersects the sphere at exactly 2 points (the only result that we will continue to solve)
The two solutions to this equation are:
T₁=-B+sqrt(B²-4AC)
     ------------------------
                   2A
T₂=-B-sqrt(B²-4AC)
     ------------------------
                   2A
Let t_c equal the lesser of t₁ and t₂ (as long as it isnt less than 0, which means that the intersection is behind the origin of the ray.) T_c is the distance from the origin of the ray to the closest intersection between the ray and the sphere.
Finally, from t_c, we can find the point of intersection, which will be useful later:
X_i = x_o + x_dt_c
Y_i = y_o + y_dt_c
Z_i = z_o + z_dt_c
Where (x_i,y_i,z_i) is the intersection

If this makes no sense at all, dont worry about it. The geometric solution has pictures! Later i will derive the intersection of a ray and a plane, which is like the above, but simpler. Once you understand that, come back to this.

The geometric solution

First, even though i said i would assume you know vectors, i will briefly explain how to get the dot product between two vectors (though not what the dot product is. Ill give a little more when we go into shading.) The dot product is an operation performed on two vectors that returns a scalar (non-vector) number. If vector a is defined by the components (a_x,a_y,a_z) and vector b is (b_x,b_y,b_z) And s=a · b (that is, the scalar s is equal to the dot product of Vectors a and b,) then s = a_x * b_x + a_y * b_y + a_z * b_z.

The information we need to determine intersection is the ray's origin and direction and the sphere's center and radius (fig 1.)
Let the vector from the origin of the ray to the center of the sphere be oc. Oc = sc - ro, where sc is the center of the sphere and ro is the origin of the ray. Let the closest approach of the ray to the sphere be tca. Tca = oc · rd where rd is the direction of the ray (fig 2.) If tca is less than 0, then the intersection with the sphere Is behind the origin of the ray and should be discarded
Let the length of oc squared be loc2. Loc2 = oc · oc Let the distance from the center of the sphere to the closest approach be d. Because of the pythagorean theorem, d2 = loc2 - tca2 (figure 3.)
Let half of the length of the cord formed by the intersection of the ray and the sphere be thc. Thc2 = sr2 - d2 (figure 4.) If thc2 is less than 0 (which Is mathematically impossible,) then the ray misses the sphere. If not, then the distance from the origin of the ray to the closest intersection of the sphere (assuming that the ray does not originate within the sphere, which is a special case That i will leave as an exercise to the reader,) is equal to tca - thc. In other words, t = tca - sqrt(thc2)

Constructive solid geometry

From Wikipedia, the free encyclopedia

Jump to: navigation, search

The light cycles from the movie Tron were constructed using Constructive Solid Geometry

Constructive solid geometry (CSG) is a technique used in solid modeling. CSG is often, but not always, a procedural modeling technique used in 3D computer graphics and CAD. Constructive solid geometry allows a modeler to create a complex surface or object by using Boolean operators to combine objects. Often CSG presents a model or surface that appears visually complex, but is actually little more than cleverly combined or decombined objects. (In some cases, constructive solid geometry is performed on polygonal meshes, and may or may not be procedural and/or parametric.)

The simplest solid objects used for the representation are called primitives. Typically they are the objects of simple shape: cuboids, cylinders, prisms, pyramids, spheres, cones. The set of allowable primitives is limited by each software package. Some software packages allow CSG on curved objects while other packages do not.

It is said that an object is constructed from primitives by means of allowable operations, which are typically Boolean operations on sets: union, intersection and difference.

[edit]

Operations

In modeling packages, basic geometric objects such as the cube or 'box', sphere or ellipse, torus, and a number of other shapes that can be described using a mathematical formula, are commonly known as primitives. These objects can typically be described by a procedure which accepts some number of parameters; for example, a sphere may be described by the coordinates of its center point, along with a radius value. These primitives can be combined into compound objects using operations like these:

Operations in constructive solid geometry
Boolean union	Boolean difference	Boolean intersection
The merger of two objects into one.	The subtraction of one object from another.	The portion common to both objects.

[edit]

Applications of CSG

Constructive solid geometry has a number of practical uses. It is used in cases where simple geometric objects are desired, or where mathematical accuracy is important. The Unreal engine uses this system, as do Hammer (the mapping engine for the Source engine) and Quake. (Hammer actually started out as an editor for Quake.) BRL-CAD is a solid modeling CAD package that is fundamentally based on CSG modeling techniques. CSG is popular because a modeler can use a set of relatively simple objects to create very complicated geometry. When CSG is procedural or parametric, the user can revise their complex geometry by changing the position of objects or by changing the Boolean operation used to combine those objects.