| 
 General: 
  Lighting Engines 
By: Jack Hoxley (Ray-Tracing by Rolly) 
Written: October 2000
   
 
This 
  could either be extremely difficult, or extremely easy. Depending on how far 
  you go it tends to get more complicated. You may also be thinking that this 
  should be in the Direct3D section - after all, lighting is a huge part of 3D 
  games; well, I've seen many 2D games use this technique - with a little memory 
  access it would actually be extremely easy to modify this for use in DirectDraw. 
Having 
  cool lighting effects in any games graphics engine is certainly an eye-catcher 
  when it comes to screenshots. Anyone can use lighting in Direct3D - it does 
  it for you; however, there are several cases where it's best not to rely on 
  built in functions: 
  - Where 
    you want something a little bit special; such as reflections and shadows, 
    or you just aren't happy with the Direct3D lighting engine
 
  - You 
    want your lighting pre-rendered. You dont want to have to setup/use the Direct3D 
    lighting engine at run-time. Games like Quake do this
 
  - You 
    want abnormal lights - As a lighting engine is just maths, you can do some 
    very un-light like things... (bendy lights?)
 
  - Hold 
    On. I dont use Direct3D - I want a lighting engine for my 2D game.
 
 
I'll 
  go over the several stages required to create your own lighting engine. Bare 
  in mind that this is taken directly from my up-coming game "The Man With 
  The Digital Gun" - so if you like the lighting in that, this is it. 
  - Writing 
    a very simple lighting Algorithm
 
  - Modifying 
    it to accept face orientation
 
  - Modifying 
    it for shadows
 
  - Using 
    lighting in 2D - a brief guide
 
  - Using 
    Lighting in 3D - a brief guide
 
 
                                        
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 data-types 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 0-3 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 0-255 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 0-255 
  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 0-255 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 re-definition 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 
  non-1 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 shadow-caster 
  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 medium-high resolution 
  lightmaps, which look much nicer anyway... 
To 
  calculate whether a vertex is in shadow is basically the same as ray-tracing. 
  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 
  pre-rendered 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 half-way across the level you may 
  well need to process several thousand triangles. 
Lets 
  get started. First, we want to look at the ray-tracing 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 
  per-vertex 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.... 
4: Using 
  lighting in 2D - a brief guide
 
  Using these techniques in a 2D game is slightly more difficult 
  than in Direct3D. Assuming you're using DirectDraw; you'll either have to pre-render 
  all the map as one massive bitmap/jpeg with lighting built in, or you'd have 
  to lock the surface and manipulate all the pixels depending on a pre-made lightmap. 
  Also; as DirectDraw doesn't interpolate colours across an area you're lightmap 
  will need to be up to 10x higher definition - which means MUCH more processing 
  time and much more data to store.... 
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 0-255 colour value for each component Red, 
  Green and Blue 
  3. Get the data from the pre-made 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.0-1.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.... 
                                       |