1:
Writing a simple lighting algorithm.
We'll
start our engine at being extremely simple, then as we progress it'll get more
complex. For this tutorial we'll be dealing only with point lights, those that
have a position and range, but no direction or cone, but once you've done point
lights, the rest is fairly easy.
First,
a bit of theory. A point light has a center and a range  therefore we'll only
be lighting those areas that fall within this circle of influence. Also, as
you travel further away from the source the light decreases  it fades out.
This effect is called Attenuation; remember this  it will keep on cropping
up. So, given that information it should be fairly easy to write the first stage.
1a:
Structures.
We will be needing several datatypes to hold information whilst we are rendering
the lighting; we'll need a datatype describing the points (vertices) and a datatype
describing a light. We'll be using these ones:
'//A simple color wrapper
Private Type RGB255
r As Byte
g As Byte
b As Byte
End Type
'//This emulates the Direct3D 0.0 to 1.0 colour values
Private Type RGB0010
r As Single
g As Single
b As Single
End Type
'//A generic Tile
Private Type Tile
X(0 To 3) As Long '//X & Y are simple 2D coordinates
Y(0 To 3) As Long '//there are 03 to simulate a tile with 4 corners...
Z(0 To 3) As Long '//Height
Color(0 To 3) As RGB255 '//The colour that windows/VB uses
D3DColor(0 To 3) As RGB0010 '//The colour that the algorithm uses
End Type
'//The light structure
Private Type Light
X As Long '//Coordinates
Y As Long
Z As Long
sColor As RGB255 '//Start colour
eColor As RGB255 '//End Colour
Range As Long
Active As Boolean '//Do we ignore this light?
End Type
'//The variables
Dim LandTile(199, 199) As Tile
Dim LList() As Light '//Open Ended Array
Dim NLights As Long '//Number of lights




These
structures may seem a little odd, so I'll go through them. We need two types
of RGB colour value. There is the normal 0255 colour value you'll be used to
in windows; and there is the 0.0  1.0 colours that Direct3D uses. The algorithm
works with the Direct3D values, if you try to use the larger values you'll get
overflow errors when you use big variations or colour and large distances...
The rest should be fairly self explanatory...
1b: Distances.
We need to know how far it is from one point to another. This is crucial to
our algorithm. We'll be using 3D pythagorus  it's not greatly important how
it works, but the result will be the distance between the two points that are
put in....
'//Calculate coordinates
X1 = LList(T).X * 2
Y1 = LList(T).Y * 2
Z1 = LList(T).Z
X2 = LandTile(X, Y).X(I)
Y2 = LandTile(X, Y).Y(I)
Z2 = LandTile(X, Y).Z(I)
'//Calculate distance
D = ((X1  X2) ^ 2) + ((Y1  Y2) ^ 2) + ((Z1  Z2) ^ 2) '//pythagorus
If D < 0 Then D = 0  D '//Non negative the number
D = Sqr(D)




At
the end of all that, "D" will be the distance between the light's
position and the vertex's position. The coordinates part will be explained a
little later....
1c:
Attenuation.
After distance, attenuation is the most important factor. we work out the attenuation
based on the difference between the start colour and the end colour; effectively
generating a gradient. If the end colour is set to black it will appear to be
fading away  but if it's set to a different colour, the start colour will merge
into the end colour  allowing for many weird lighting effects.
'//Red component
Atten = ((LList(T).sColor.r / 255)  (LList(T).eColor.r / 255))
/ LList(T).Range
r = (LList(T).sColor.r / 255)  (D * Atten)




above
is the code that calculates the colour and the attenuation. all of the LList(
).*color.* values have the "/255" because it will convert a 0255
value into a 0.0 to 1.0 value, which is required if the formula is to work.
A breakdown of the formula:
(LList(T).sColor.r
/ 255)  (LList(T).eColor.r / 255)
=> This is basically "(Start colour  end colour)", we're
left with the difference between the start and finish colour.
(Result) / LList(T).Range
=> This uses the result from the previous part and divides it by the
range. This then results in "for every 1m you go, it changes by this much"
 a gradient.
(LList(T).sColor.r / 255)  (D * Atten)
=> The first part converts the 0255 value into a 0.0 to 1.0 value.
The next part works out what the colour is based on the distance along the gradient
slope. if you use the same sentence as above: "If you've gone D meters
along you are at this colour value" it then takes away this value from
the start value.
Done;
you now have, stored in "r", the colour value for that vertex from
that light. To get the other colours you just repeat this, substituting the
"r"'s for "g"'s or "b"'s...
1d:
the final colour
This is the final part of the formula. Assuming you have more than one light
 which is very likely; how do you know that the red value you have is not less
than the amount of red already there. We'll need to blend the colours  which
in this case is incredibly simple. we'll only change the master value if the
temporary "r" value is greater than the current "r" value.
Here's the code for all 3 components:
If
r >
LandTile(X,
Y).D3DColor(I).r
Then
LandTile(X,
Y).D3DColor(I).r
= r
If g
>
LandTile(X,
Y).D3DColor(I).g
Then
LandTile(X,
Y).D3DColor(I).g
= g
If b
>
LandTile(X,
Y).D3DColor(I).b
Then
LandTile(X,
Y).D3DColor(I).b
= b 



Done.
You now have all the information, algorithms and formulas that you will require...
1e:
The trimmings
I'll now tidy up the code, and show you how the shell of the algorithm looks...
For
X = 0 to 199 '//or maximum X
For Y = 0 to 199 '//or maximum Y
For I = 0 to 3 '//The 4 corners of the tile
For T = 1 to NLights '//Cycle through each of the
lights
'//Here we process the vertex (I) colour, based on
the (X,Y) coordinates and the Light(T)
Next T
Next I
Next Y
Next X 



Simple
really :)
2:
Modifying it to accept face orientation
The model above is okay; for a simple game it would do. But for a little extra
work a big difference can be gained. What if the tile you are lighting isn't
facing the light  what if the light is behind it. In the previous model it
wouldn't make any difference at all. But in real life the tile shouldn't get
any light. Basically, we want to adapt our algorithm so that it shades each
tile based on the direction it's pointing in  if it's pointing away then there
is no light.
This
has the added advantage of making the shading much better  should you have
a cone shaped mountain; the side facing away will be dark (what we want), the
side facing the light will be very bright, and anything betweem will be either
slightly darker or slightly lighter.
The
theory behind this is a little more complex than the previous incarnation of
the lighting algorithm, but you still need to understand the previous one. You'll
also need to understand what a vertex normal is; I've seen lots of posts on
message boards about these, so I think this'll be our first stop.
A
vertex normal is a vector perpendicular to the surface or the vertex. A vertex
or face normal can tell you which direction it's pointing  which is exactly
what we need for this part of our algorithm. For our algorithm we'll use a face
normal  where the face is the tile. To work out what the face normal we'll
use the Cross product. How this works isn't greatly important either, it takes
two vectors, and the resulting vector is the normal. The two vectors we'll use
are from the vertex 0 to vertex 1, and from vertex 0 to vertex 2; these two
vectors basically describe the surfaces. So, to clear all this up; to calculate
a vector between two points we use the formula:
V.x
= p1.x  p2.x
V.y = p1.y  p2.y
V.z = p1.z  p2.z 



As
for the cross product. There is a function built into the DirectX type library
for doing this; but we'll do it the long hand way:
'A
= first vector, B = Second Vector, N = Normal
N.x = A.y * B.z  A.z * B.x
N.y = A.z * B.x  A.x * B.z
N.z = A.x * B.y  A.y * B.x




At
this point we would be able to get the vertex/face normal. For convenience we'll
just copy this normal to each vertex. This will require us to modify one of
the datatypes that we created earlier, and create a new one.
'//This first one is only needed if you '//Haven't got the Dx7 type library attached '//to your project Private
Type
D3DVECTOR
X As
Single
Y As
Single
Z As
Single
End
Type
'//This is a redefinition of the old datatype. Private
Type
Tile
X(0 To
3) As
Long
Y(0 To
3) As
Long
Z(0 To
3) As
Long
Color(0
To 3)
As
RGB255
D3DColor(0
To 3)
As
RGB0010
N(0 To
3) As
D3DVECTOR '//Vertex Normal *NEW*
End
Type




The
next stage; we need the direction from the light to the vertex. This is fairly
simple, and is done in the same way as the first stage of getting the vertex
normal:
LightDirVector
= LightPos  VertexPos
'//or, when expanded
V.x = p1.x  p2.x
V.y = p1.y  p2.y
V.z = p1.z  p2.z
'//Where p1 = LightPos, and p2 = VertexPos 



We
also want to normalize the two vectors at this point. At the moment it is quite
likely that you're light direction vector and your vertex normal are both of
non1 lengths (ie, a lengh other than 1). There is another function built into
the DirectX type library for normalising a vector; but I'll show it to you long
hand:
'//You use this in the format: LightDirVector
=
VectorNormalize(LightDirVector) Landtile(x,y).N(0)
=
VectorNormalize(LandTile(x,y).N(0)) '//and so on for the other 3
Private
Function
VectorNormalize(dest
As
D3DVECTOR)
As
D3DVECTOR '//You dont really need to know how this works  just be able to use it.
On
Local
Error
Resume
Next
Dim l
As
Double
l =
dest.X
*
dest.X
+
dest.Y
*
dest.Y
+
dest.Z
*
dest.Z
l =
Sqr(l)
If l =
0 Then
dest.X
= 0
dest.Y
= 0
dest.Z
= 0
Exit
Function
End If
dest.X
=
dest.X
/ l
dest.Y
=
dest.Y
/ l
dest.Z
=
dest.Z
/ l
VectorNormalize.X
=
dest.X
VectorNormalize.Y
=
dest.Y
VectorNormalize.Z
=
dest.Z
End
Function




Okay;
we're about ready to work some stuff out now. You've met the Cross product already,
now meet the Dot product. The dot product returns a value between 1 and +1,
which is the scaling factor of our colour. This code will get the intensity
of our light:
Dim
Intensity as Single '//A decimal value to hold our
multiplier
Intensity = VectorDotProduct(VertexNormal, LightDirVector)
'//Expanded:
Private Function VectorDotProduct(a As D3DVECTOR, b As D3DVECTOR) As Single
VectorDotProduct = a.X * b.X + a.Y * b.Y + a.Z * b.Z
End Function 



We
now just multiply all the channels by the "Intensity" value, which,
if you think about it, works as a scaler. for example, if the intensity is 1.0
(the face faces the light) then the colour = colour * 1.0 = colour. Whereas,
if the intensity were 0.5 the colour would be halved. The only thing you need
to bare in mind; if the returned value is <=0 it gets no light at all; as
this means that the surface is facing away from the light.
Sorted.
Should you now run the program; you'll see that it only shades faces fully that
are facing the light....
3:
Modifying it for shadows
Now things start getting interesting. Assuming that we're writing
a Direct3D lighting engine we're now at a point where we will be doing better
than it's own engine  as it doesn't have support for shadows (Not without clever
tricks).
There
is one huge limitation to this technique when implemented with Direct3D  it's
not very accurate; but when combined with the previous iteration of the engine
it shouldn't be very noticable. Because Direct3D blends a colour across the
surface, the ray of light going to a vertex only has to miss the shadowcaster
by a fraction of a meter in order to make 1/4 or the surface appear in full
light.... You can get around this quite easily by using mediumhigh resolution
lightmaps, which look much nicer anyway...
To
calculate whether a vertex is in shadow is basically the same as raytracing.
We will basically trace a line from the light's position to the vertices position;
should this line intersect with another tile we will know that we dont need
to calculate any light. Before we really get started here you need to bare in
mind that this technique is extremely slow; so should only be considered for
prerendered lighting, NOT runtime/realtime lighting. If you have a good knowledge
of Assembler you may well be able to make this go fast, but in pure VB you will
be lucky to get reasonable speeds when compiling the light map. The algorithm
we'll use isn't necessarily the best available, and the methods used aren't
necessarily the fastest  should you want to use this method you can work that
part out !
The
time it takes to work out is proportional to the number of triangles in a model,
and the distance between the light and the vertex. Should you be attempting
to calculate the lighting for a ray going halfway across the level you may
well need to process several thousand triangles.
Lets
get started. First, we want to look at the raytracing algorithm; thinks to 'Rolly' for this  the original author.
Private
Function
RayIntersection(triP1
As
D3DVECTOR,
triP2
As
D3DVECTOR,
triP3
As
D3DVECTOR,
_
startpos
As
D3DVECTOR,
endpos
As
D3DVECTOR,
Accuracy
As
Single)
As
Boolean
Dim
tri As
Triangle
tri.Vect1
=
triP1
tri.Vect2
=
triP2
tri.Vect3
=
triP3
' our ray is in the form origin + t*direction
' where t = time
Dim
direction
As
D3DVECTOR,
temp
As
D3DVECTOR,
pos As
D3DVECTOR
Dim t
As
Single
temp =
VectorSubtract(endpos,
startpos) ' get the vector from startpos to endpos
direction
=
VectorNormalize(temp) ' normalize it to get the direction
Do
While
(pos.X
<>
endpos.X)
And (pos.Y
<>
endpos.Y)
And (pos.Z
<>
endpos.Z) 'Do while we are not at the end point
' Trace a line from startpos to endpos checking for intersections at every point
pos =
VectorScale(direction,
t) ' multiply the direction by time
Call
VectorAdd(pos,
pos,
startpos) ' add the current pos to the startpos
If
Test_Triangle(tri,
pos) =
True
Then 'is this in the triangle?
RayIntersection
=
True 'yes!, return true and bail
Exit
Function
End If
t = t
+
Accuracy ' smaller numbers = greater accuracy = slower
Loop
RayIntersection
=
False 'missed completely
End
Function 



Not
too scary really, is it. We pass the function the three points of our triangle
(triP1, triP2, triP3) and the points defining our line (startpos, endpos) and
the accuracy. The accuracy is incredibly important  the smaller the number
the more accurate the shadows are; for lightmaps this is quite important; as
pervertex shadowing is quite inaccurate anyway, calculating it very accurately
isn't greatly important. Also, the accuracy determines the speed that this thing
takes to render. The final thing to note is that the function returns true if
the ray intersects with a triangle and false if it doesn't...
In
order to use the above function we require two support functions: VectorScale
and VectorAdd, as well as the core processing function, Test_Triangle. The two
support functions are shown below:
'Not greatly complicated this one: Private
Sub
VectorAdd(dest
As
D3DVECTOR,
a As
D3DVECTOR,
b As
D3DVECTOR)
dest.X
= a.X
+ b.X
dest.Y
= a.Y
+ b.Y
dest.Z
= a.Z
+ b.Z
End
Sub
'Neither is this one. Private Function
VectorScale(vA
As
D3DVECTOR,
s As
Single)
As
D3DVECTOR
VectorScale.X
= vA.X
* s
VectorScale.Y
= vA.Y
* s
VectorScale.Z
= vA.Z
* s
End
Function




Finally;
the Test_Triangle procedure:
Private
Function
Test_Triangle(ByRef
tri As
Triangle,
Test_Point
As
D3DVECTOR)
As
Boolean
Dim r
As
Single,
s As
Single,
t As
Single
Dim
normal
As
D3DVECTOR 'Normal vector
Dim
spana
As
D3DVECTOR,
spanb
As
D3DVECTOR,
vec As
D3DVECTOR
Dim
length
As
Single,
length2
As
Single
spana
=
VectorSubtract(tri.Vect2,
tri.Vect1) 'Vector from vect1 to vect2
spanb
=
VectorSubtract(tri.Vect3,
tri.Vect1) 'vector from vect1 to vect3
Call
VectorCrossProduct(normal,
spana,
spanb) 'normal vector
length
=
VectorLength(normal) 'length of normal
spana
=
VectorSubtract(Test_Point,
tri.Vect1) 'Vector from vect1 to the test point
spanb
=
VectorSubtract(tri.Vect3,
tri.Vect1) 'vector from vect1 to vect3
Call
VectorCrossProduct(vec,
spana,
spanb)
length2
=
VectorLength(vec)
s =
VectorDotProduct(vec,
normal)
s = s
/
length
spana
=
VectorSubtract(tri.Vect2,
tri.Vect1)
spanb
=
VectorSubtract(Test_Point,
tri.Vect1)
Call
VectorCrossProduct(vec,
spana,
spanb)
length2
=
VectorLength(vec)
t =
VectorDotProduct(vec,
normal)
t = t
/
length
r = 1
 (s +
t)
If ((r
+ s +
t) =
1)
Then
Test_Triangle
= True
Else
Test_Triangle
=
False
End If
End
Function 



This
basically takes a triangle, and a point and checks if the point is within the
triangle. The point was worked out by the previous function  it's a value somewhere
along the line between startpos and endpos based on the accuracy value. The
theory behind this formula can be found from many of the big game development
sites (http://www.faqs.org/ has a good entry
in the comp.Graphics.Algorithms FAQ).
You'll
also notice that this procedure requires several more functions for it to work
 mostly vector manipulation. VectorSubtract, VectorCrossProduct, VectorLength
and VectorDotProduct. Dot product and Cross product where demonstrated above;
VectorLength and VectorSubtract are shown below:
'A
bit like the VectorAdd  but the other way around :) Private
Function VectorSubtract(vA As D3DVECTOR, vB As D3DVECTOR) As D3DVECTOR
VectorSubtract.X = vA.X  vB.X
VectorSubtract.Y = vA.Y  vB.Y
VectorSubtract.Z = vA.Z  vB.Z
End Function
'Simple pythagorus in use here... Private
Function VectorLength(dv As D3DVECTOR) As Single
VectorLength = Sqr(dv.X ^ 2 + dv.Y ^ 2 + dv.Z ^ 2)
End Function




okay;
so now you can test a triangle if it intersects with a line between the light
and the vertex. We now need to plug this into our existing algorithm. This is
where we need to decide which triangles to test. The method shown below is probably
the slowest that you can do, but in order to keep this article fairly simple
we'll leave it like this. Should you have time I strongly suggest that you modify
this  about 80% of the triangles tested will be well out of the line.
All
we're going to do is run through the rectangle defined by the light position
and the vertex position. Like So:
For
Xray =
Int(X1
/ 2)
To
Int(X2
/ 2)
For
Yray =
Int(Y1
/ 2)
To
Int(Y2
/ 2)
'//First test the triangle defined by points 012
RayTest
=
RayIntersection(VectorMake(LTile(Xray,
Yray).X(0),
LTile(Xray,
Yray).Y(0),
LTile(Xray,
Yray).Z(0)),
_
VectorMake(LTile(Xray,
Yray).X(1),
LTile(Xray,
Yray).Y(1),
LTile(Xray,
Yray).Z(1)),
_
VectorMake(LTile(Xray,
Yray).X(2),
LTile(Xray,
Yray).Y(2),
LTile(Xray,
Yray).Z(2)),
_
VectorMake(LList(t).X,
LList(t).Y,
LList(t).Z),
VectorMake(LTile(X,
Y).X(I),
LTile(X,
Y).Y(I),
LTile(X,
Y).Z(I)),
_
0.1) 'NB: We're using a high accuracy
If
RayTest
= True
Then
r =
AR: g
= AG:
b = AB 'We make the RGB the lowest possible values  Ambient colour
GoTo
OutOfLoop:
End If
'//Now test the triangle defined by the points 132
RayTest
=
RayIntersection(VectorMake(LTile(Xray,
Yray).X(1),
LTile(Xray,
Yray).Y(1),
LTile(Xray,
Yray).Z(1)),
_
VectorMake(LTile(Xray,
Yray).X(3),
LTile(Xray,
Yray).Y(3),
LTile(Xray,
Yray).Z(3)),
_
VectorMake(LTile(Xray,
Yray).X(2),
LTile(Xray,
Yray).Y(2),
LTile(Xray,
Yray).Z(2)),
_
VectorMake(LList(t).X,
LList(t).Y,
LList(t).Z),
VectorMake(LTile(X,
Y).X(I),
LTile(X,
Y).Y(I),
LTile(X,
Y).Z(I)),
_
0.1) 'NB: We're Using a high accuracy
If RayTest = True Then
r =
AR: g
= AG:
b = AB 'We make the ambient colour because that's the lowest...
GoTo
OutOfLoop:
End If
Next Yray
Next
Xray
OutOfLoop: 'Used to break out of the triangle test 



That
segment of code goes after you scale the colours for face orientation, and before
you compile the final colours....
Bare in mind that on my fast computer (700Mhz Athlon) it took 7 secs to do a
complicated scene before shadowing and nearly 20minutes to do the same scene
with shadowing....
Should
you want to do the runtime method; you'll basically need to use the following
methods outlined:
1.
Lock the surface
2. Go through every pixel and get a 0255 colour value for each component Red,
Green and Blue
3. Get the data from the premade lightmap (or generate it now) and get a value
of 0.0 to 1.0 for each colour component
4. Multiply the value you read from the surface by the 0.01.0 value you have
for the lighting. If you think about it, a value of 1.0 (full light) will not
affect the colour (colour*1# = colour), but if the value is 0.5 you will get
half the colour (colour*0.5 = colour/2)...
5. Put the modified values back into the surface.
This,
I'm sure, is how Direct3D does it's lighting when textures are used. Because
it's the same, you'll have the same lighting problems. Think about it, if the
pixel has green light on it (the multipliers will be 0.0, 1.0, 0.0) and the
pixel colour is blue or red the overall colour will be black. As there is no
green 1.0 * 0 = 0, as there is no red light, 255 * 0.0 = 0 and there is no blue
light, 255 * 0.0 = 0 you're final colour will be black  not very pretty. There
are three ways around this.
1. Ambient lighting  in the lighting program alter all light values
so that they dont go below a certain level, ie dark grey, this way you're textures
may well become very very dark, but they wont ever go black.
2. Lighter Textures  if you make you're green grass a very light green
(use the brightness option in your paint program) then there will always be
some of every component  therefore a light will always have some affect, even
if it's very small...
3.
Saturation, this is basically where if a value is above of below a boundary
it is automatically set to another value. For example, a saturation of 75% would
mean that all value >=75% would be set to 100%. The same can be done on the
lower boundaries. You could write a simple algorithm to look at each channel
(r,g,b) in every pixel (of your texture) and if it were below a certain value
you could set it to a new lower boundary. For example, if you want the textures
to always have 100 of a channel, you look through every channel and should it
be less than 100 you alter it to be 100.... simple really...
5:
Using Lighting in 3D  a brief guide
Lighting in Direct3D is easy. It was designed with lighting in
mind after all...
However,
you'll have to use either D3DLVERTEX's (where you can specify the colour) or
the D3DTLVERTEX's (only if you're doing a 2D game). In either case you'll have
to store you're lighting as a 0.0 to 1.0 value in your data file (or convert
it at runtime)  as the "Dx.CreateColorRGB()" function takes colour
values on a 0.0 to 1.0 scale.
Another
advantage or using Direct3D is that it interpolates the colours across a triangle.
therefore the lighting information doesn't need to be at such a high resolution,
which saves on storage space and processing time....
Should
you want to use lightmaps you'll need to store the lightmap as a texture, load
it in as a texture and then use texture blending to apply it to your model.
There are two major limitations to this method:
1. Filesize. Fancy storing a 2000x2000 bitmap for each level? Not pretty.
2. Texture sizes; you'll need to keep the textures to the power of two  512,1024,2048,4096.
The higher they get the more memory required, and the less hardware will support
it. Bare in mind that Voodoo3 cards cant hold textures greater than 256x256
in size...
I
just mentioned storing 2000x2000 bitmaps. You could use a compressed format,
such as JPEG. But unless you're not bothered about clarity JPEG is a bad choice.
JPEG compression is "Lossy"  therefore you're not going to get quite
what you put in back....