Alain can be reached at CSC Computer Sciences, Avenue Lloyd Gearge 7, B-1050 Brussels, Belgium.
Ray tracing is a computer-graphics technique for generating realistic three-dimensional images. It is based on the premise that a "scene" is created when light rays from multiple sources strike individual objects. Depending on surface characteristics of the objects, the rays can either change direction or color, reflect or refract into a finite number of rays, or diffuse into an infinite number of rays.
In this article, I present RAY, a ray-tracing program written in C++. While I've limited the objects illuminated to spheres and planes, you can easily add cones, cubes, cylinders, and other objects. The light model I implement consists of diffuse, specular, and reflected components. RAY also performs hidden-surface removal and simulates shadow and semishadow effects to produce images of dazzling realism like that in Figure 1. Images the program generates can be saved in true color (16.7 million colors) in standard TARGA files supported by most commercial image-manipulation software. Since RAY uses an associative palette of colors, it can display 256 colors in real time. It also supports the VESA standard (see the accompanying text box entitled, "Encapsulating VESA Services"), so the program is compatible with most Super VGA cards. RAY also displays images in 256 levels of gray scale and stores those images in TARGA files with color maps.
There are two basic approaches to ray tracing--forward and backward. As Figure 2 illustrates, forward ray tracing involves sending simulated rays from light sources, computing their interaction with encountered objects, and determining which light rays actually reach the eye of the observer. In the real world, few rays actually reach the observer, so backward ray tracing operates in the reverse--from the observer to the objects and light sources; see Figure 3. This involves scanning pixel by pixel, sending a ray from the observer to a pixel, and computing the corresponding RGB color based on the interactions of the ray with all objects, starting with the nearest.
While many factors affect the image's realism--how you model objects, colors, vector operations, and the like--I'll focus on the light model because its quality ultimately determines the degree of realism. Assume, for instance, that you want to compute the color of a point P on an object in the scene. This point is met by ray ![[vbar]](vbar.gif)
, issued from the observer, and is illuminated by a light source following the direction ![[sbar]](sbar.gif)
. The normal at the object at point P is aligned following the direction ![[nbar]](nbar.gif)
, and the reflection direction that is the symmetrical of relative to is represented by the vector ![[rbar]](rbar.gif)
; see Figure 4. Light variations of point P depend on the roughness and material of the object surface.
Ambient light is constant for the entire scene. It represents the sum of the light not taken into account from other contributions.
Diffuse light slightly penetrates the surface of the encountered object and is reemitted uniformly in all directions. Interaction between the light and the solid is high, and the color of the ray is changed by the color of the surface. Diffuse light is modeled using Lambert's Law: I=
(INrd(![[ubar]](ubar.gif)
S![[dot]](dot12.gif)
N)), where IN is the color of the object with components RGB, rd is the diffuse reflection factor for its surface, S is the vector normalized, N is the vector normalized, and is the sum computed for all light sources. The scalar product (SN) is proportional to the cosine of the angle that separates from , and goes from 0 for a horizontal illumination to 1 for light from the normal direction.
Specular light represents the mirror effects given by a light that does not penetrate the shiny surface of an object, but is reflected directly on its outer surface in a manner that indicates the source's location. The color of the specular light comes from the color of the source that illuminates the object: I=(ISrs(RV)f), where IS is the color of the light source with components RGB, rs is the specular reflection factor associated with the surface of the object, R is the vector normalized, V is the vector normalized, f is an empirical exponent that determines the level of specular reflection (depending on the physical characteristics of the surface), and the sum is computed for all light sources.The scalar product (RV) is proportional to the cosine of the angle that separates from , and is thus maximal when the reflected ray is aligned along the direction coming from the observer. The exponent f allows you to rapidly decrease this effect when the alignment disappears.
The presence of several objects in a scene usually means that one object will be in the illumination path of another. For the object that is then in a position of shadow relative to the light source, the diffuse and specular contributions of the light source are zeroed, leaving ambient light and reflected rays.
To implement shadow and semishadow effects, you have to draw secondary rays from the point to the source (following ) and check that no other objects are in the path. If none are, the diffuse and specular components do not have to be computed for the source.
Some shiny surfaces reflect incoming light rays. Consequently, a ray can bounce from one object to another before reaching the observer's eye. The chromatic information carried by the ray will depend on the multiple interactions of the ray with the different surfaces encountered: I=IRrr, where rr is the reflection factor of the surface of the object. The intensity IR is computed by sending a new ray from the point P, aligned along the direction ![[wbar]](wbar.gif)
, which is the symmetrical of relative to . This means that IR will be evaluated by means of a recursive call to the module that computes the illumination of a point.
RAY currently models geometric objects such as points and spheres, along with rays, planes, colors, and vector operations. Since the point is the basic object (both geometrically and programmatically), I'll focus on it. To characterize the behavior of an object, you must compute both the intersection of a light ray (a 3-D vector) with the surface of the object and the orientation of the normal at the point of intersection; see the accompanying text box entitled, "Modeling Objects." Because I use C++, you have only to program these two rules to add new objects in the software.
In object-oriented (as opposed to geometric) terms, the point is the base object that holds all basic characteristics of all other objects. All other objects inherit the characteristics of the basic point via inheritance.
A point with the coordinates [x, y, z] has a position in 3-D space. The constructor of a point initializes it and automatically places it in a linked list with two sentinels, Head and Trail. The destructor of a point removes it from the linked list and if necessary resets the values of Head and Trail.
This has two consequences: First, you only have to declare an object of type point to automatically store it in a linked list in memory and make it automatically disappear when going out of scope; second, since all other objects inherit from the point, all objects of the list will be placed in the same linked list and will have the same behavior.
A C++ function scans this linked list, calling a method for each object. If the method has been declared as virtual, the compiler will automatically call the method corresponding to the actual type of the object found (late binding).
For instance, with a linked list of one plane and one sphere, you can call the method Intersect() for each object in the list. The compiler will then automatically call the method Intersect() of the Plane object in the first case, and Intersect() of the Sphere object in the second.
As each ray is cast from the observer's point of view, the object list is scanned and the corresponding Intersect() method called. The object with the smallest time value is identified as closest to the observer, and the interaction of the ray with the corresponding surface is then computed.
The two methods attached to the object Point are the two routines needed to characterize the behavior of the object as previously defined: Intersect() computes the intersection of the object with a 3-D vector , and GetNormal computes the normal of the object in a given point P.
Although powerful, the basic RAY ray-tracing program is concise, due largely to the object-oriented nature of C++. For example, I use operator overloading to simplify vector operations; see Table 1. To generate an image, you simply declare an object of type scene, create several objects of type light vector, and attach the light vector objects to the scene object. You then declare the objects to be represented (spheres or planes), call the RayTrace() method for the scene, and display the image on the screen or store it to disk.
The RAY ray-tracing program includes the following modules:
Listing One is the include file RAY.H. The main parameters that allow you to alter the behavior of the program are A, the size of the associative palette array (normally 31 or 63) and A0, a threshold of visibility. Below this value, all colors are considered black in order to spare palette entries for more-significant colors.
The #define constants Diffuse, Specular, Shadow, and Reflections allow you to selectively activate or deactivate the different contributions in the light model. Object-specific parameters are given in the objects' constructors (with appropriate default values): Rd (the diffuse reflection factor), Rs (the specular reflection factor), and Rr (the reflection factor), all of which depend on the characteristics of the surface. MaxRef is the maximum number of reflections that a light ray can have. This limits the level of recursiveness in the computations. The program allows any value here, but empirically, since each additional reflection is attenuated by the factor rr, a value of 1 already gives astonishing results.
Finally, parameters are given to RayTrace(). Spread is the radius used for the associative palette algorithm. Values can range from 0 (for a simple image, no specular reflection or reflection) to 7 (complex images, full light model with multiple reflections). Search is used by the associative palette algorithm to look for an approximate color when the palette is full.
Listing Two, RAY1.CPP, generated Figure 1--a full light model that produces multiple reflections. Listing Three is RAYOBJ.H, and Listing Four is RAYOBJ.CPP, which provides the various classes for the objects to be illuminated (points, spheres, planes, scenes, and the like), along with base classes for color.
Most RAY computations are done using floating-point numbers. Consequently, high performance depends on the presence of a math coprocessor in the target PC. For instance, Figure 1 (available electronically, along with the sample image files) was computed in one to three minutes on a 33-MHz 486DX PC. On a 25-MHz 486SX, however, this can take up to an hour.
Finally, I would like to thank my brother, Jean-Michel Mangen, for his assistance on this project.
The VESA standard defines the behavior of video screens and graphical cards. Most graphics cards are now bundled with either hardware or software that emulates this standard, accounting for differences in video modes and performing video bank switching for the SVGA modes.
In RAY, I've encapsulated VESA calls in the RAYSVGA module. While Table 2 lists all VESA modes, RAY only supports the VESA 256-color ones. Table 3 lists the RAY routines that provide VESA services.
Since the video palette is dynamically filled in real time during program execution, activating the video palette in two individual steps allows you to buffer palette changes. This prevents flickering on the video screen during the repeated changes of the colors in the palette. Also, loading the video palette in the VGA-card hardware can be slow on some boards, so buffering these changes globally optimizes program performance.
--A.M.
Synthesized images are almost always postprocessed for video integration or conversion to another file format. Thus, you only have to implement two uncompressed TARGA formats to keep the TARGA interface modules simple--the size of the images on disk isn't an issue since they're only temporary files.
Consequently, the TARGA interface can be implemented in a single page of C++ code. I use two different TARGA formats: type 1 (uncompressed, color-mapped images) for the gray-scale images (see Table 4) and type 2 (uncompressed, RGB images) for true-color images (Table 5). I chose type 1 for gray-scale images instead of type 3 (uncompressed, black-and-white images) because type 3 is less likely to be supported in commercial applications.
TARGA files are converted by the C++ object TGAFile. The TGAFile constructor opens the file in Write mode and writes the file header. The destructor closes the TARGA file.
The method WritePixel() copies an array of uncompressed pixels into the TARGA file. This function is optimized using fwrite() to perform the disk operation in one step. Also, the file is buffered using a dynamically allocated area of 32 Kbytes in memory, which optimizes the overall speed of the application.
--A.M.
One feature of the ray-tracing rendering algorithm presented here is its ability to handle geometric objects using their exact mathematical expressions. To characterize the behavior of an object, you must compute the intersection of a light ray (a 3-D vector) with the surface of the object and determine the orientation of the normal at the point of intersection.
When modeling the ray, if is a 3-D vector defined by its origin 0=[x0, y0, z0] and its direction d=[xd, yd, zd], the equation of the ray as a function of time t is (t)=0+dt, where t>0 and d is normalized. As t increases, the ray point moves farther from the observer's eye. If the ray encounters several distinct objects in its path, the closest object to the observer will correspond to the lowest value of t. This means you can "depth sort" the objects to compute the hidden-surface removal by comparing the time values of the intersections. Objects with a negative value of t are located behind the observer and can be ignored. Miscellaneous objects composing the scene can interpenetrate each other: The intersection of the ray will be automatically computed with the resulting outermost surface.
When modeling the sphere, consider a sphere S with its center c=[xc, yc, zc] and its radius Sr. Replacing a point of the light ray (t) in the equation of the sphere in Figure 5(a) yields the equations in Figures 5(b) and 5(c). If the discriminator (B2--4AC) is negative, the equation has no solution and the ray misses the sphere. Otherwise, the lowest positive value between t0 and t1 represents the nearest intersection, and the intersection point P=[xP, yP, zP]=[x0+xdt, y0+ydt, z0+zdt]. The normal in the point P is then given by the equation in Figure 5(d). If both t0 and t1 are negative, then the object is located behind the observer and need not be represented on the screen.
To optimize the sphere, you can rewrite the equations in Figure 5 by computing the vector 
=c-0, going from the origin of the light ray to the center of the sphere. Then compute the distance of the point of the ray nearest to the center of the sphere (Figure 6). This approach requires fewer computations and, by considering the sign of t2dc, more quickly determines whether or not there is an intersection
The equation for a plane (considered an infinite surface in all directions) is Ax+By+Cz+D=0, where A2+B2+C2=1. Replacing a point of the light ray yields the equation in Figure 7. If the denominator is 0, the scalar product of the ray with the normal [A, B, C] to the plane is 0, and the ray is parallel to the plane. If t is greater than 0, the point of intersection P=[xP, yP, zP]=[x0+xdt, y0+ydt, z0+zdt]. The normal in P is then =[A, B, C] with possibly a reversed sign.
--A.M.
Figure 1 A sample image generated by the RAY ray-tracing program (see Listing One).
Figure 2 Forward ray tracing.
Figure 3 Backward ray tracing.
Figure 4 The light model.
Figure 5 (a) General equation for a sphere; (b) replacing a point of the light ray (t) in the equation in (a) and solving for t0; (c) solving for t1; (d) the normal in the point P.
Figure 6 Computing the distance of the point nearest to the center of the sphere.
Figure 7 Replacing a point of the light ray in the plane equation.
Table 1 Overloaded vector operations.
Mode Definition Colors
-------------------------------------
GetMaxX X GetMaxY
0x100 640X400 256
0x101 640X480 256
0x102 800X600 16
0x103 800X600 256
0x104 1024X768 16
0x105 1024X768 256
0x106 1280X1024 16
0x107 1280X1024 256
Routine Description
-------------------------------------------------------------------------
int VESA_Close() Closes VESA mode and returns to text mode.
int VESA_GetMode() Returns current VESA mode.
void VESA_PutPixel Displays a pixel of color color at
the position (x,y).
(int x, int y, int color)
void VESA_WritePixel Displays a line of n pixels starting at (x,y).
Optimized to copy
(int x, int y, int n, char *color)
pixel value color in one or two operations
using direct-memory
addressing to video memory.
void VESA_ShowPalette() Displays palette contents by drawing one
horizontal line using
each available color.
void VESA_LoadBlackPalette() Initializes memory palette so that all
displayed colors are black.
void VESA_LoadBWPalette() Initializes memory palette to hold
graduated shading of gray scale.
void VESA_LoadColor Loads a color in the memory palette entry i,
with the given RGB components.
(int i, int R, int G, int B)
void VESA_ActivatePalette() Activates memory palette and copies all
predefined entries to video
palette in VGA card.
int VESA_SetMode (int Mode, Initializes a given VESA mode. See Table 1.
int GetMaxX, int GetMaxY)
Field Bytes Uncompressed
Color-mapped Images
---------------------------------------------
1 1 Number of bytes in field 6
2 1 Color-map type: 1
3 1 Image-type code: 1
4 5 Color-map specification
2 4.1. Color-map origin: 0
2 4.2. Color-map length: 256
1 4.3. Color-map entry size: 24
5 10 Image specification
2 5.1. X-Origin: 0
2 5.2. Y-Origin: 0
2 5.3. Width of the image
2 5.4. Height of the image
1 5.5. Image pixel size: 8
1 5.6. Image descriptor: 0x20
6 Variable Identification field
7 Variable Color-map data (RGB):
3 bytes/entry in map
8 Variable Image data: 1 byte/pixel
Field Bytes Uncompressed RGB Images
---------------------------------------------
1 1 Number of bytes in field 6
2 1 Color-map type: 0
3 1 Image-type code: 2
4 5 Color-map specification
2 4.1. Color-map origin: 0
2 4.2. Color-map length: 0
1 4.3. Color-map entry size: 0
5 10 Image specification
2 5.1. X-Origin: 0
2 5.2. Y-Origin: 0
2 5.3. Width of the image
2 5.4. Height of the image
1 5.5. Image pixel size: 24
1 5.6. Image descriptor: 0x20
6 Variable Identification field
7 0 Color-map data (RGB): empty
8 Variable Image data: 3 bytes RGB/pixel
/***********************************************************************/ /*** (C) Copyright A.MANGEN 1994 ***/ /*** PROJECT : RAY TRACING PROGRAM ***/ /*** PROGRAM NAME: RAY.H 1.1 ***/ /*** DESCRIPTION : Ray Tracing - Main Include File ***/ /***********************************************************************/ /* Constants for associative palette */ const A=63; /* Size of the associative palette */ const A0=10; /* Minimum level of visibility */ /* Constants for Ray Tracing */ #define Diffuse /* Implement diffuse light */ #define Specular /* Implement specular light */ #define Shadow /* Implement objects shadows */ #define Reflections /* Implement ray reflections */
/***********************************************************************/
/*** (C) Copyright A.MANGEN 1994 ***/
/*** PROJECT : RAY TRACING PROGRAM ***/
/*** PROGRAM NAME: RAY1.CPP 1.1 ***/
/*** DESCRIPTION : Ray Tracing Main Program ***/
/*** Generate one single image on screen ***/
/***********************************************************************/
#include <stdio.h>
#include "raysvga.h"
#include "rayobj.h"
#define RD 0.9 // Diffuse reflection factor
#define RS 0.9 // Specular reflection factor
#define RR 0.9 // Reflection factor
#define MAXREF 1 // Maximum number of reflections
extern unsigned _stklen = 16384U;
void main()
{ Color Ambient(40,40,40);
Scene MyScene(320,-150,240,Ambient);
Color CWhite(200,200,200);
Color CGreen(0,200,0);
Color CRed(200,0,0);
Color CBlue(0,0,200);
Vector MyLight(700,-400,800,-0.5,-1,0);
MyScene.AddLight(!MyLight,CWhite);
Sphere S0(-1900,2700,240,1300,CRed,RD,RS,RR,MAXREF);
Sphere S1(2400,2700,240,1300,CBlue,RD,RS,RR,MAXREF);
Sphere S2(320,1800,300,300,CGreen,RD,RS,RR,MAXREF);
Plane P0(0,0,1,1500,CGreen,RD,RS,RR,MAXREF);
MyScene.RayTrace(VESA_640x480x256,640,480,0,NULL,7,3);
}
/***********************************************************************/
/*** (C) Copyright A.MANGEN 1994 ***/
/*** PROJECT : RAY TRACING PROGRAM ***/
/*** PROGRAM NAME: RAYOBJ.H 1.1 ***/
/*** DESCRIPTION : Ray Tracing Objects - Include File ***/
/***********************************************************************/
#include <math.h>
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
typedef float Coord; // Point Coordinate
/*** Color: Base class for color. Overloaded operators are declared inline
in order to optimize speed. ***/
typedef float Col; // Color Component
class Color
{
public:
Col R,G,B; // Red,Green,Blue Colors
Color(Col r=0,Col g=0,Col b=0) // Inline Constructor
{ R=r; G=g; B=b; }
Color operator +(Color & C) // Overloaded + operator
{ return Color(R+C.R,G+C.G,B+C.B); }
Color operator *(Col f) // Overloaded * operator
{ return Color(f*R,f*G,f*B); }
Col GrayScale() // GrayScale function
{ Col W=0.39*R+0.50*G+0.11*B;
return min(255,W);
}
Col Associate(int Spread,int Search); // Associate function
};
/**** Vector: Base class for vector. Overloaded operators are declared inline
in order to optimize speed. ***/
class Vector
{
public:
Coord X,Y,Z,dX,dY,dZ; // Vector Direction
Vector(Coord x=0,Coord y=0,Coord z=0, // Inline Constructor
Coord dx=0,Coord dy=0,Coord dz=0)
{ X=x; Y=y; Z=z; dX=dx; dY=dy; dZ=dz; }
Vector operator *(Coord f) // Overloaded * : fV
{ return Vector(X,Y,Z,f*dX,f*dY,f*dZ); }
Vector operator ^(Coord f) // Overloaded ^ : V(t)
{ Coord N=sqrt(dX*dX+dY*dY+dZ*dZ);
return Vector(X+f*dX/N,Y+f*dY/N,Z+f*dZ/N,dX,dY,dZ); }
Coord operator *(Vector V) // Overloaded * : Scalar product
{ return(dX*V.dX+dY*V.dY+dZ*V.dZ); }
Vector operator +(Vector V) // Overloaded + : Vector addition
{ return Vector(X,Y,Z,dX+V.dX,dY+V.dY,dZ+V.dZ); }
Vector operator -(Vector V) // Overloaded - : Vector substraction
{ return Vector(X,Y,Z,dX-V.dX,dY-V.dY,dZ-V.dZ); }
Vector operator !() // Overloaded ! : Norm
{ Coord N=sqrt(dX*dX+dY*dY+dZ*dZ);
return Vector(X,Y,Z,dX/N,dY/N,dZ/N);
}
Vector operator -() // Overloaded - : Unary -
{ return Vector(X,Y,Z,-dX,-dY,-dZ); }
Coord Length() // Length of vector
{ return sqrt(dX*dX+dY*dY+dZ*dZ); }
};
/*** Point : Generic base class with linked list ***/
#define NO_INTERSECTION 1e99
#define DEFAULT_RD 0.9 // Diffuse reflection factor
#define DEFAULT_RS 0.0 // Specular reflection factor
#define DEFAULT_RR 0.0 // Reflection factor
#define DEFAULT_MAXREF 0 // Maximum number of reflections
class Point
{
protected:
Point *Prev,*Next; // Integrated linked list
Coord X,Y,Z; // Point Coordinates
public:
Color C; // Point Color
Col Rd; // Diffuse reflection factor
Col Rs; // Specular reflection factor
Col Rr; // Reflection factor
int MaxRef; // Maximum number of reflections
int MakeShadow; // Gives shadow or not
Point(Coord x,Coord y,Coord z, // Constructor
Color c,
Col rd=DEFAULT_RD,
Col rs=DEFAULT_RS,
Col rr=DEFAULT_RR,
int maxref=DEFAULT_MAXREF,
int makeshadow=TRUE);
~Point(); // Destructor
Point *GetNext() // Get Next Point in linked list
{ return Next; };
virtual Coord Intersect(Vector V) = 0; // Intersection method - designed
// to be overridden by descendants
virtual Vector GetNormal(Vector P) = 0; // Get normal
};
/*** Sphere : Inherited Point for spheres ***/
class Sphere:public Point
{
Coord R; // Radius of the sphere
public:
Sphere(Coord x,Coord y,Coord z, // Inline Constructor
Coord r,Color c,
Col rd=DEFAULT_RD,
Col rs=DEFAULT_RS,
Col rr=DEFAULT_RR,
int maxref=DEFAULT_MAXREF,
int makeshadow=TRUE)
:Point(x,y,z,c,rd,rs,rr,maxref,makeshadow) { R=r; };
virtual Coord Intersect(Vector V); // Intersection method
virtual Vector GetNormal(Vector P) // Get normal
{ return Vector(P.X,P.Y,P.Z,P.X-X,P.Y-Y,P.Z-Z); }
};
/*** Plane : Inherited Point for planes ***/
class Plane:public Point
{
Coord D; // Position of the plane
public:
Plane(Coord x,Coord y,Coord z, // Inline Constructor
Coord d,Color c,
Col rd=DEFAULT_RD,
Col rs=DEFAULT_RS,
Col rr=DEFAULT_RR,
int maxref=DEFAULT_MAXREF,
int makeshadow=TRUE)
:Point(x,y,z,c,rd,rs,rr,maxref,makeshadow) { D=d; };
virtual Coord Intersect(Vector V); // Intersection method
virtual Vector GetNormal(Vector P) // Get normal
{ return Vector(P.X,P.Y,P.Z,X,Y,Z); }
};
/*** Scene : Scene object ***/
const MAX_LIGHT=10;
class Scene
{ Coord CameraX,CameraY,CameraZ; // Position of the camera
Color Ambient; // Ambient luminosity
int NLight; // Number of lights
Vector LightV[MAX_LIGHT]; // Lights orientation
Color LightColor[MAX_LIGHT]; // Lights color
char ScreenLine[VESA_Max_Width]; // Screen buffer
char TGALine[3*VESA_Max_Width]; // TARGA File buffer
public:
Scene(Coord camerax,Coord cameray,Coord cameraz,Color ambient);
int AddLight(Vector V,Color I);
Coord ClosestIntersect(Vector V,
Point **ObjectMin,int ShouldMakeShadow=FALSE);
void Ray(int N,Vector V,Coord f,Color & I);
void RayTrace(int Mode,int GetMaxX,int GetMaxY,int BW,
char *FileName=NULL,int Spread=0,int Search=1);
};
/***********************************************************************/
/*** (C) Copyright A.MANGEN 1994 ***/
/*** PROJECT : RAY TRACING PROGRAM ***/
/*** PROGRAM NAME: RAYOBJ.CPP 1.1 ***/
/*** DESCRIPTION : Ray Tracing Objects ***/
/***********************************************************************/
#include <stdio.h>
#include <stdarg.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include "ray.h"
#include "raysvga.h"
#include "raytga.h"
#include "rayobj.h"
/*** Error : Standard Error Routine ***/
#define Here __FILE__,__LINE__
void Error(char *File,int Line,char *Format,...)
{ va_list arg_ptr;
va_start(arg_ptr,Format);
printf("(%s,%d) ",File,Line);
vprintf(Format,arg_ptr);
va_end(arg_ptr);
exit(1);
}
/*** Color : Base class for color ***/
int AssociativeAllocated; // Allocation index
char huge AssociativePalette[A+1][A+1][A+1]; // Associative Palette
void Init_AssociativePalette() // Initialize palette
{ AssociativeAllocated=1;
_fmemset(AssociativePalette,0,sizeof(AssociativePalette));
}
Col Color::Associate(int Spread,int Search) // Search a color in palette
{ int C;
int R0=(int) R*(A+1)/256; R0=min(A,R0); R0=max(A0,R0);
int G0=(int) G*(A+1)/256; G0=min(A,G0); G0=max(A0,G0);
int B0=(int) B*(A+1)/256; B0=min(A,B0); B0=max(A0,B0);
if((C=AssociativePalette[R0][G0][B0])!=0) // Found an existing color
return(C);
else if(AssociativeAllocated==255) // Palette is full
{ for(int R1=R0;R1<=min(A,R0+Search);R1++)
for(int G1=G0;G1<=min(A,G0+Search);G1++)
for(int B1=B0;B1<=min(A,B0+Search);B1++)
if((C=AssociativePalette[R1][G1][B1])!=0)
return(C); // Look for an approximate
for(R1=max(0,R0-Search);R1<=R0;R1++)
for(int G1=max(0,G0-Search);G1<=G0;G1++)
for(int B1=max(0,B0-Search);B1<=B0;B1++)
if((C=AssociativePalette[R1][G1][B1])!=0)
return(C); // Look for an approximate
return(0); // Found nothing
}
else // Allocate a new one
{ VESA_LoadColor(AssociativeAllocated,
min(63,R/4),min(63,G/4),min(63,B/4));
if(AssociativeAllocated%10==1) // Avoid video flickering
VESA_ActivatePalette(); // Activate VGA palette
for(int R1=R0;R1<=min(A,R0+Spread);R1++) // Spread color
for(int G1=G0;G1<=min(A,G0+Spread);G1++)
for(int B1=B0;B1<=min(A,B0+Spread);B1++)
if(AssociativePalette[R1][G1][B1]==0)
AssociativePalette[R1][G1][B1]=AssociativeAllocated;
return(AssociativeAllocated++); // Return new index
}
}
/*** Point : Generic base class with linked list ***/
Point *Head=NULL; // Linked List Header
Point *Trail=NULL; // Linked List Trailer
// Point Constructor
Point::Point(Coord x,Coord y,Coord z,
Color c,Col rd,Col rs,Col rr,int maxref,int makeshadow)
{ X=x; Y=y; Z=z; C=c; // Data Encapsulation
Rd=rd; Rs=rs; Rr=rr; MaxRef=maxref; MakeShadow=makeshadow;
Next=NULL; // Build up linked list
if(Head==NULL) Head=this;
if(Trail!=NULL) Trail->Next=this;
Prev=Trail; Trail=this;
};
Point::~Point()
{ if(Head==this) // Clean up linked list
Head=Next;
if(Trail==this)
Trail=Prev;
if(Prev!=NULL)
Prev->Next=Next;
if(Next!=NULL)
Next->Prev=Prev;
}
/*** Sphere : Inherited Point for spheres ***/
Coord Sphere::Intersect(Vector V)
{ Vector OC(X,Y,Z,X-V.X,Y-V.Y,Z-V.Z);
Coord tpp=OC*V;
Coord tdc2=R*R-(OC*OC-tpp*tpp);
if(tdc2>0) // Is there an intersection
{ tdc2=sqrt(tdc2);
Coord t=min(tpp-tdc2,tpp+tdc2);
if(t>0) return(t); // If in front of observer
else return(NO_INTERSECTION); // Else behind observer
}
else return(NO_INTERSECTION); // No intersection found
};
/*** Plane : Inherited Point for planes ***/
Coord Plane::Intersect(Vector V)
{ Coord Denom=X*V.dX+Y*V.dY+Z*V.dZ;
if(Denom==0) return(NO_INTERSECTION); // No intersection found
else
{ Coord t=-(X*V.X+Y*V.Y+Z*V.Z+D)/Denom;
if(t>0) return(t); // If in front of observer
else return(NO_INTERSECTION); // Else behind observer
}
};
/*** Scene : Scene object ***/
Scene::Scene(Coord camerax,Coord cameray,Coord cameraz,Color ambient)
{ CameraX=camerax; CameraY=cameray; CameraZ=cameraz; // Data Encapsulation
Ambient=ambient; NLight=0;
};
int Scene::AddLight(Vector V,Color I)
{ if(NLight<MAX_LIGHT)
{ LightV[NLight]=V; // Add a new light in scene
LightColor[NLight]=I;
NLight++;
return(TRUE);
}
else return(FALSE); // Too many lights
} // See constant MAX_LIGHT
Coord Scene::ClosestIntersect(Vector V, // Search for the
Point **ObjectMin,int ShouldMakeShadow) // closest intersection
{ Coord t,tmin=NO_INTERSECTION;
Point *Object=Head;
*ObjectMin=NULL;
do
{ if(!ShouldMakeShadow || Object->MakeShadow)
{ t=Object->Intersect(V);
if((t<tmin)&&(t>0))
{ tmin=t; *ObjectMin=Object; }
}
Object=Object->GetNext();
} while (Object!=NULL);
return(tmin);
}
void Scene::Ray(int N,Vector V,Coord f,Color & I)
{ Point *ObjectMin=NULL,*ObjectShadowMin=NULL;
Coord t=ClosestIntersect(V,&ObjectMin); // Compute intersection tmin
if(ObjectMin!=NULL) // with closest ObjectMin
{
#ifdef Diffuse
Vector P=V^t; // Point of intersection
Vector Un=!ObjectMin->GetNormal(P);
for(int i=0;i<NLight;i++) // Now compute the color
// for each light source
{ Vector Us(P.X,P.Y,P.Z,LightV[i].X-P.X,LightV[i].Y-P.Y,LightV[i].Z-P.Z);
#ifdef Shadow
Coord tshadow=ClosestIntersect((!Us)^0.01,&ObjectShadowMin,TRUE);
Coord Dist=Us.Length();
if((ObjectShadowMin==NULL)||(tshadow>Dist))
#endif // No other object found
{ Coord Diff=(!Us)*Un; // on lightening path
I=I+ObjectMin->C*f*ObjectMin->Rd*max(0,Diff);
#ifdef Specular
if((N==0)&&(ObjectMin->Rs>0))
{ Vector Ur=Un*2*(Us*Un)-Us; // Specular reflection
Coord Spec=(!Ur)*(-V);
I=I+LightColor[i]*f*ObjectMin->Rs*pow(max(0,Spec),20);
}
#endif
}
}
#ifdef Reflections // Check maximum number of reflections/refractions
if((N<ObjectMin->MaxRef)&&(ObjectMin->Rr>0))
{ Vector Uw=-Un*2*(V*Un)+V;
Uw=Uw^0.01; // Add some distance along the vector to
// avoid intersection with the same object
Ray(N+1,Uw,f*ObjectMin->Rr,I);
}
#endif
#endif
}
}
void Scene::RayTrace(int Mode,int GetMaxX,int GetMaxY,int BW,
char *FileName,int Spread,int Search)
{ if(!VESA_SetMode(Mode,GetMaxX,GetMaxY))
Error(Here,"Cannot set VESA mode 0x%x (%dx%d)",Mode,GetMaxX,GetMaxY);
switch(BW)
{ case 0:VESA_LoadBlackPalette(); break;
case 1:VESA_LoadBWPalette(); break;
}
VESA_ActivatePalette(); // Initialize screen palette
Init_AssociativePalette(); // Initialize memory palette
TGAFile TGA(FileName,GetMaxX,GetMaxY,BW); // Create TARGA file
for(int Z=GetMaxY;Z>0;Z--) // Scan all pixels
{ for(int X=0;X<GetMaxX;X++)
{ // Build vector from camera to (X,0,Z)
Vector V(CameraX,CameraY,CameraZ,X-CameraX,0-CameraY,Z-CameraZ);
Color I=Ambient;
Ray(0,!V,1.0,I); // Cast a ray
switch(BW)
{ case 0:
ScreenLine[X] =I.Associate(Spread,Search);
TGALine[3*X] =min(255,(int) I.B);
TGALine[3*X+1]=min(255,(int) I.G);
TGALine[3*X+2]=min(255,(int) I.R);
break;
case 1:
TGALine[X]=ScreenLine[X]=I.GrayScale();
break;
}
}
VESA_WritePixel(0,GetMaxY-Z,GetMaxX,ScreenLine);
TGA.WritePixel(GetMaxX,TGALine);
}
VESA_ActivatePalette(); // Freshen screen palette
Beep();
if(FileName==NULL)
{ (void) getchar();
VESA_ShowPalette();
}
VESA_Close();
printf("Colors used : %d\n",AssociativeAllocated);
};
Copyright © 1994, Dr. Dobb's Journal