Realtime Ray Tracing in Freebasic

[Voltage]

Howdy all,

I've been doing some research and a little coding, and I have come up with a realtime raytracer in FB.

Does anyone here have any previous experience with ray tracing?  I have a coupla questions, specifically to do with optimizations. 

I don't have the code with me right now, but I'll post some code and an .exe a bit later.

EDIT: Added source and .exe

[ferris]

I've done 5 different versions, my latest (complete version) being done in FB with a hell of alot of inline ASM.

If you have any questions try to get on msn or something; some of the techniques that are really important in RTRT are really hard to explain in posts. But if I have to I'll try to explain them here

Feel free to ask.

[ferris]

Looks like you need to familiarize yourself with adaptive subsampling

Contrary to what most people believe, normal raytracer optimizations *WILL NOT* work well enough for RTRT's in demos. Trust me

But, adaptive subsampling is the father of all raytracer optimizations. And since virtually nobody has done any good explanations on how it's done, I will

First, you must divide the screen into squares. I use 8x8 to start. What you do is loop through the screen in these squares. For each square, trace only the corners of each square. If the rays hit the same object and were all either inside/outside a shadow, just bilinearly interpolate colors/shading/texture coords/etc. accross the square. Else, divide the square into 4 more squares; each half the original's size. Then call your square routine for each new square. This continues until the the original criteria has been met or the square is 1x1 pixel in size.

Any questions?

[Voltage]

Looks like you need to familiarize yourself with adaptive subsampling

I get it, and I like it.  That was a very clear explaination, thanks matey matey.

Plus after I implement it, I can say that I've done "adaptive subsampling", and that rocks!

Do you have your engines available for downloading somewhere or do you care to share?

[ferris]

Do you have msn?

Right now I don't have access to them.

Basically, there's things to remember when coding a RTRT:

1. You are insane for trying to do triangles in realtime . The only primitives mine support (except my first tracer thta wasn't RT) are spheres, planes, and cylinders.
2. You can't be entirely against giving up looks for speed.
3. Think differently - one method may look like nice code but could be very slow.
4. Because of number 1, when you get pretty far in your tracer, we'll talk about CSG.
5. You're off to a great start

[Voltage]

msn + Voltage = FALSE

I can't get a damned account/passport with them for some strange reason, I have tried on more than one occasion.  Way back in the day, I had voltage@hotmail.com but due to lack of use, it expired.

I have been using Yahoo Messenger, without a hiccup for 5 years-ish, so if you Yahoo, my user name is voltage_123, or mail at voltage_123 @ yahoo dot com

1) Yes I am insane.  But I didn't realise that tri's were so computationally expensive! Thanks for the heads up.
2) I am willing to give up looks for speed.
3) While I am learning, I will stick to clean readable code, but I am more than willing to inline ASM the shit out of it, when the time comes.
4) Sounds great, I understand the concepts but I have never implemented them, bring on the CSG
5) Thanks mate.

I'll go and have toy with adaptive subsampling

[Clyde]

@Thygrion + Voltage: With the newer versions of MSN Messenger, you can add Yahoo Contacts.

Welldone Voltage on your Ray Tracing!

[Jim]

It can depend a lot on what you want to raytrace.  One thing you might consider is called 'first hit optimisation'. You render your scene into a 1bit buffer using standard triangle rasterisation instead of raytracing, and where the 1bits are you trace a ray for that pixel, for the 0 bits you draw the background.
Other people here have done more work on it.  Specular reflection can be accelerated with some success.  The more diffuse effects you want, the harder it gets (multiple rays need to be spawned at each intersection).

Jim

[Voltage]

@Clyde:  Thanks mate, and thanks for the MSN tip.

@Jim:  I had considered something similar to 1st hit optimisation, like a mask, it would work esp well if there was a lot of background being drawn.  With spheres you could actually use a scaled sprite to cover the sphere as the mask, that would be very fast.  That combined with subsampling could produce some funky optimisations.  I'm like a kid in a candy shop at the moment.   I've wanted to do realtime raytracing for about 10 years.

[rdc]

I noticed you were using PSet, which is quite slow. I don't know if you'll eventually use something like tinyptc but you can replace the Psets with direct access to the screenbuffer which will speed things up a bit.

Code Select Expand


Sub PutPixel(x As Integer, y As Integer, clr As Uinteger)
    Dim As Integer Ptr scrbuff
   
    scrbuff = Screenptr
   
    Screenlock
    Poke Integer, scrbuff + (x + y * 320), clr
    Screenunlock
End Sub


And of course there are some asm examples posted on the board as well.

[rdc]

I messed around with your code a bit and put the screen updates inline. This draws a page and then displays it. My changes are marked RDC. This is a bit faster on my machine. Anyway, just some ideas.

Code Select Expand


'Ray Tracer v0.1
'by Voltage 21/3/2007

'****************** NEED to update the surface normals after moving the triangles !! ******** Then lighting should work

'*** TO DO ***
'Current Goals
'DONE! - Cast a ray through each screen coord
'DONE! - Check for intersection with triangle
'DONE! - Find closest triangle that intersected
'DONE! - Draw appropriate diffuse colour
'DONE! - Basic Shadows

'Specular lighting
'Texture maps
'Reflection
'Spheres
'Optimizations - Bounding boxes/other?

'Option Explicit

Type VectorType
  x As Double
  y As Double
  z As Double
End Type

Type RayType
  origin As VectorType
  Dir As VectorType
  ShadowRay As Integer
  CurrentObject As Integer
End Type

Type IntersectionType
  Dist As Double
  Object As Integer
  u As Double
  v As Double
End Type

Type TriangleType
  v1 As VectorType
  v2 As VectorType
  v3 As VectorType

  Plane As RayType
 
  R As Ubyte
  G As Ubyte
  B As Ubyte
End Type

Declare Function Vec_Length(v As VectorType) As Double
Declare Function Vec_Normalize(v As VectorType) As VectorType
Declare Function FindClosestIntersection(Ray As RayType) As InterSectionType
Declare Function TriangleIntersect(R As RayType, T As TriangleType) As IntersectionType
Declare Function Vec_CrossProduct(v1 As VectorType, v2 As VectorType) As VectorType
Declare Function Vec_DotProduct(v1 As VectorType, v2 As VectorType) As Double
Declare Function Vec_Subtract(v1 As VectorType, v2 As VectorType) As VectorType
Declare Sub SetupScene
Declare Function CalculateColour(Object As Integer, R As RayType, L As Double) As Integer


Const SCR_W=640
Const SCR_H=400
Const ViewDistance = 300
Const NUMTRIANGLES = 5
Const EPSILON=0.000001
Const TRUE = -1
Const FALSE = 0
Const SP=4

Screen 14,32

Dim MyRay As RayType
Dim MyIntersection As IntersectionType
Dim Shared Triangles(1 To NUMTRIANGLES) As TriangleType
Dim As Integer x,y,a,colour
Dim Shared As VectorType LightSource

'RDC'
dim sbuff as integer ptr
dim baseclr as uinteger = rgb(20, 20, 20)
'**************************************************************************************************************
'**************************************************************************************************************
'**************************************************************************************************************
'**************************************************************************************************************
'**************************                                                ************************************
'**************************                   MAIN CODE                    ************************************
'**************************                                                ************************************
'**************************************************************************************************************
'**************************************************************************************************************
'**************************************************************************************************************
'**************************************************************************************************************


'Light Source
LightSource.x = 30
LightSource.y = -100
LightSource.z = -90

'View point
MyRay.origin.x=100
MyRay.origin.y=100
MyRay.origin.z=-ViewDistance
MyRay.ShadowRay = FALSE ' This ray is not checking InShadow
MyRay.CurrentObject=-1

SetupScene

'RDC'
sbuff = screenptr
Do
    'RDC'
    screenlock
  For y=0 To 200
    For x=0 To 200
 
      'Setup Ray for each screen pixel
      MyRay.Dir.x = x - MyRay.origin.x
      MyRay.Dir.y = y - MyRay.origin.y
      MyRay.Dir.z = 0 - MyRay.origin.z
 
      'Normalize the direction ray
      MyRay.Dir = Vec_Normalize(MyRay.Dir)
 
      'Find the closest interection (if any)
      MyIntersection = FindClosestIntersection(MyRay)
      If MyIntersection.Dist>0 Then
        Colour = CalculateColour(MyIntersection.Object,MyRay,MyIntersection.Dist)
        'RDC'
        poke integer, sbuff + (x + y * 320), Colour
        'PSet (x,y), Colour
      Else
        'RDC'
        poke integer, sbuff + (x + y * 320), baseclr
        'PSet (x,y),rgb(20,20,20)
      End If
     
      If Inkey$=Chr$(27) Then
        'RDC'
        screenunlock
        Exit Do
      end if
     
    Next x
  Next y
  'RDC'
  screenunlock
 
  Triangles(3).v2.y+=SP
  If Triangles(3).v2.y>200 Then Triangles(3).v2.y=0
  Triangles(3).v1.x+=SP
  If Triangles(3).v1.x>200 Then Triangles(3).v1.x=0
  Triangles(3).v3.x-=SP
  If Triangles(3).v3.x<0 Then Triangles(3).v3.x=200

  Triangles(2).v2.y-=SP
  If Triangles(2).v2.y<0 Then Triangles(2).v2.y=200
  Triangles(2).v1.x+=SP
  If Triangles(2).v1.x>200 Then Triangles(2).v1.x=0

  Triangles(1).v2.x+=SP
  If Triangles(1).v2.x>200 Then Triangles(1).v2.x=0

  For a=1 To NUMTRIANGLES
    Triangles(a).Plane.Dir = Vec_Normalize(Vec_CrossProduct(Vec_Subtract(Triangles(a).v2,Triangles(a).v1),Vec_Subtract(Triangles(a).v3,Triangles(a).v1)))
  Next a
Loop

'**************************************************************************************************************
'**************************************************************************************************************
'**************************************************************************************************************
'**************************************************************************************************************
'**************************                                                ************************************
'**************************            FUNCTIONS AND SUBS                  ************************************
'**************************                                                ************************************
'**************************************************************************************************************
'**************************************************************************************************************
'**************************************************************************************************************
'**************************************************************************************************************

Function Vec_Length(v As VectorType) As Double
  Vec_Length=Sqr(v.x*v.x+v.y*v.y+v.z*v.z)
End Function

Function Vec_Normalize(v As VectorType) As VectorType
  Dim l As Double
 
  l=Vec_Length(v)

  v.x=v.x/l
  v.y=v.y/l
  v.z=v.z/l

  Vec_Normalize = v
End Function

Function FindClosestIntersection(Ray As RayType) As InterSectionType
  Dim Result As InterSectionType
  Dim a As Integer
  Dim Intersect As InterSectionType

  'Set the default return values
  Result.Dist=-1
  Result.Object=-1

  For a=1 To NUMTRIANGLES
    If Ray.ShadowRay = TRUE Then
      'The next check is so we don't check for intersections with the intersect point object
      If a<>Ray.CurrentObject Then
        Intersect = TriangleIntersect(Ray, Triangles(a))
        If Intersect.Dist>0 Then
          Result.Dist = 1
          Exit Function
        End If
      End If
    Else
      Intersect = TriangleIntersect(Ray, Triangles(a))
      If Intersect.Dist>0 Then
        If Result.Dist<>-1 Then
          If Intersect.Dist < Result.Dist Then
            Result.Dist = Intersect.Dist
            Result.Object = a
            Result.u = Intersect.u
            Result.v = Intersect.v
          End If
        Else
          Result.Dist = Intersect.Dist
          Result.Object = a
          Result.u = Intersect.u
          Result.v = Intersect.v
        End If
      End If
    End If
  Next a
 
  FindClosestIntersection = Result
End Function

Function TriangleIntersect(R As RayType, T As TriangleType) As IntersectionType
  Dim Result As IntersectionType
  Dim As VectorType Edge1, Edge2, TVec, PVec, QVec
  Dim As Double Det, Inv_Det

  Edge1 = Vec_Subtract(T.v2 , T.v1)
  Edge2 = Vec_Subtract(T.v3 , T.v1)

  PVec = Vec_CrossProduct(R.Dir, Edge2)

  Det = Vec_DotProduct(Edge1, PVec)

  If Det > EPSILON Then
    TVec = Vec_Subtract(R.Origin, T.v1)
    Result.u = Vec_DotProduct(TVec, PVec)
    If Result.u<0.0 Or Result.u>Det Then
      Result.Dist = -1
      TriangleIntersect = Result
      Exit Function
    End If
    QVec = Vec_CrossProduct(TVec, Edge1)
    Result.v = Vec_DotProduct(R.Dir, QVec)
    If Result.v<0.0 Or (Result.u + Result.v)>Det Then
      Result.Dist = -1
      TriangleIntersect = Result
      Exit Function
    End If
  Else
    If Det < (-EPSILON) Then
      TVec = Vec_Subtract(R.Origin, T.v1)
      Result.u = Vec_DotProduct(TVec, PVec)
      If (Result.u>0.0 Or Result.u<Det) Then
        Result.Dist = -1
        TriangleIntersect = Result
        Exit Function
      End If
      QVec = Vec_CrossProduct(TVec, Edge1)
      Result.v = Vec_DotProduct(R.Dir, QVec)
      If (Result.v>0.0 Or (Result.u + Result.v)<Det) Then
        Result.Dist = -1
        TriangleIntersect = Result
        Exit Function
      End If
    Else
      Result.Dist = -1
      TriangleIntersect = Result
      Exit Function
    End If
  End If

  Inv_Det = 1.0 / Det

  Result.Dist = Vec_DotProduct(Edge2, QVec) * Inv_Det
  Result.u = Result.u * Inv_Det
  Result.v = Result.v * Inv_Det

  TriangleIntersect = Result
End Function

Function Vec_CrossProduct(v1 As VectorType, v2 As VectorType) As VectorType
  Dim Result As VectorType
 
  Result.x = v1.y * v2.z - v1.z * v2.y
  Result.y = v1.z * v2.x - v1.x * v2.z
  Result.z = v1.x * v2.y - v1.y * v2.x

  Vec_CrossProduct = Result
End Function

Function Vec_DotProduct(v1 As VectorType, v2 As VectorType) As Double
  Vec_DotProduct = v1.x*v2.x + v1.y*v2.y + v1.z*v2.z
End Function

Function Vec_Subtract(v1 As VectorType, v2 As VectorType) As VectorType
  Dim Result As VectorType
 
  Result.x = v1.x - v2.x
  Result.y = v1.y - v2.y
  Result.z = v1.z - v2.z

  Vec_Subtract = Result
End Function

Sub SetupScene
  Dim a As Integer

  For a=1 To NUMTRIANGLES
    Read Triangles(a).v1.x
    Read Triangles(a).v1.y
    Read Triangles(a).v1.z

    Read Triangles(a).v2.x
    Read Triangles(a).v2.y
    Read Triangles(a).v2.z

    Read Triangles(a).v3.x
    Read Triangles(a).v3.y
    Read Triangles(a).v3.z

    Triangles(a).Plane.Origin = Triangles(a).v1
    'Calc the plane normal from the verts
    Triangles(a).Plane.Dir = Vec_Normalize(Vec_CrossProduct(Vec_Subtract(Triangles(a).v2,Triangles(a).v1),Vec_Subtract(Triangles(a).v3,Triangles(a).v1)))

    Read Triangles(a).r
    Read Triangles(a).g
    Read Triangles(a).b
  Next a
End Sub

Function CalculateColour(Object As Integer, R As RayType, L As Double) As Integer
  Dim As Double DP
  Dim As VectorType I,IL
  Dim As IntersectionType AnIntersection
  Dim As RayType ARay
 
  'Get the intersection point
  I.x=R.Origin.x + r.Dir.x * L
  I.y=R.Origin.y + r.Dir.y * L
  I.z=R.Origin.z + r.Dir.z * L

  'Create a vector from the intersection point to the light source
  IL = Vec_Normalize(Vec_Subtract(LightSource,I))
 
  'Get the dot product of the normal and this new vector
  DP = Abs(Vec_DotProduct(IL, Triangles(Object).Plane.Dir))
  If DP>0 Then
 
    'Check if intersection point is in the shadow of another object
    ARay.Origin = I
    ARay.Dir = IL
    ARay.ShadowRay = TRUE
    ARay.CurrentObject = Object
    AnIntersection = FindClosestIntersection(ARay)
   
    'In shadow?
    If AnIntersection.Dist>0 Then
      'Use these results to calc the light value
      DP=DP/3
    End If

    CalculateColour = Rgb(Triangles(Object).r*DP,Triangles(Object).g*DP,Triangles(Object).b*DP)
  Else
    CalculateColour = 0
  End If
End Function

'**************************************************************************************************************
'**************************************************************************************************************
'**************************************************************************************************************
'**************************************************************************************************************
'**************************                                                ************************************
'**************************                      DATA                      ************************************
'**************************                                                ************************************
'**************************************************************************************************************
'**************************************************************************************************************
'**************************************************************************************************************
'**************************************************************************************************************

'Triangle Data (v1,v2,v3,r,g,b)
Data 5,5,0
Data 195,100,0
Data 80,160,0
Data 255,0,0

Data 50,20,-20
Data 140,125,0
Data 40,190,20
Data 0,255,0

Data 160,180,-20
Data 60,50,0
Data 140,45,20
Data 0,0,255

Data 0,180,-100
Data 0,180,100
Data 200,180,100
Data 255,255,00

Data 200,180,100
Data 200,180,-100
Data 0,180,-100
Data 255,255,0

'BESETTINGS (don't change!):
'BECURSOR=70A
'BETOGGLE=111111111
'BETARGET=1


Oh, and I compared this to tinyptc and this method was actually faster than both tinyptc and tinyptc_ext, at least on my machine.

[Jim]

Thing is with thousands of calculations for intersections, reflections and colours, per pixel, the overhead for pset is totally irrelevant.

Jim

[Voltage]

@RDC - I ran the profiler on my original code, and PSET didn't even reach 0.1% of the execution time. Thanks anyway, but the maths/algorithm need to optimised well before the drawing functions in this situation.

[Shockwave]

What a great thread! And Voltage, great work and thanks Thygrion for the explanations. Without wanting to sound too harsh though, if you're going to pimp msn here then I might as well close the site and turn it into a chat room.

Harsh?

Sorry, it's not meant to be and of course, msn can be really helpful to explain this sort of stuff, the trouble with it is always that everyone else on the forum wonders how things are going and only one person benefits from the advice.

In fact, I even go as far as this when somebody PM's me with a question on coding, I always give a deliberately vague answer and ask the person to post the question on the board.

I hope that you'll carry on with the topic here, I can't force you of course, but it would be a shame to solicit something as interesting as this away from here.

Cheers

[ferris]

Sorry Nick

I myself have never done first-hit optimisation, simply because all my scenes I used in my tracers had objects that covered the entire screen.

I believe it's faster NOT to use it anyway. I mean, with adaptive subsampling and first-hit optimisation, one kinda ruins the other. I prefer subsampling because it has more possibilities than first-hit.

Just my opinion.

As far as CSG goes, I'm going to keep that under wraps for now. I'll explain it when the tracer evolves to a point where it's ready, simply because I don't want to present algorithms that will severely complicate the code before the code works correctly without them.

[rdc]

I was just pointing out that PSet is slower compared to other methods for display in FB, not that it would make the program a speed demon. I just thought I would try and be helpful.

[ferris]

Oh I was totallynot trying to flame you, I meant I wouldn't use first-hit optimisation.

I was sharing an opinion and giving different views on different optimisations, that's all. Sorry!!

[Jim]

I think it's probably me he's talking to.  Sorry mate.

Another possibility with first hit is to render the surface normals into a buffer (by interpolation), instead of having to work them out for each pixel.

Jim

[Voltage]

Here's the next version.  It uses a basic sub sampling algorithm to halve the number of rays being traced. 

I wrote a big long explaination but again IE crashed on me when using these forums.   

[rain_storm]

That is quite noticeably faster I didnt know that raytracing could be done in realtime. Are you planning on including reflections and refractions at some point? Good work on those optimisations btw.