RayTracer Theory and Practice

Hades · Post by **Hades** » Mon Jul 18, 2005 2:42 pm

Yes, kd-tree is great, but you should think about if you want static scenes only, or moving objects too. Moving something in a tree structure without having to recompute the whole tree can be tricky. :roll:

By choosing to go triangle only you could get rid of a lot if's and procedure calls -> more speed

.
But I love that perfect sphere's so much.

I love to optimize an algorithm, and I could do some assembler porting if you need a helping hand.

Ok, I take a look at your refraction problem now. Maybe I find something, but following someone else's code isn't my strongest side.

Edit: Ok, refracion work's fine now, anything else that stops you from doing your work ?

Dreglor · Post by **Dreglor** » Mon Jul 18, 2005 10:07 pm

NICE!
What was the problem?
can you pm me the fixed code
maybe we can team up and opmitize all of this together personally i don't have any assembly skills and i keep hearing it almost always improve the code you do by some huge percentange

some odd also that callfunctionfast() makes it render slower :\ im not sure why though

Hades · Post by **Hades** » Mon Jul 18, 2005 10:44 pm

Your math was right, you just did some copy / past errors. I PM the corrected section to you.
Assembler can help a lot, but it can't do wonders though.

CallFunctionFast only helps if you avoid If's or Select by using it. Branching isn't the fastest thing a CPU can do...

I'd be glad to help out, but it's your project. My time is limited, so I can only do some optimizing tasks. But I would love to do that.

Dreglor · Post by **Dreglor** » Mon Jul 18, 2005 11:00 pm

ok
but my code is open for you and everyone else to optimize here i will try and keep my code up to date

Hades · Post by **Hades** » Mon Jul 18, 2005 11:27 pm

Hm... that could get messy.
The best way would be if you give me a task to optimize, so I don't mess with something you want to change or drop.

I could try to get your TestTriangle Procedure going. Ok, it's not really optimizing, but I just don't know where else to start.

Dreglor · Post by **Dreglor** » Mon Jul 18, 2005 11:31 pm

the triangles i was starting long ago but dropped becasue i decided to work with reflections and other things and it kind of dropped off the list :\ im sure triangles would make a nice addition to the primitives.
also im not going to drop anything now till i get everything i want working like kd-trees,triangles, ect

I didn't get the PM it should of came instanly if im not mistaken

Hades · Post by **Hades** » Mon Jul 18, 2005 11:39 pm

Ups

I hope I didn't sent it someone else.

Ok. I'll try again.

Edit: ... nothing ?

Dreglor · Post by **Dreglor** » Tue Jul 19, 2005 12:38 am

hmm did you use the pm button under my posts?
email it to me if you have to, theres button at the bottem for that also

another option is to post it here

Hades · Post by **Hades** » Tue Jul 19, 2005 1:07 am

Yes, i did use the Button. Don't know what's wrong.

Code: Select all

              If ObjectList()\Material\Refract>0
                n.f=RefractBefore/ObjectList()\Material\RefractIndex
                Norm\x=Normal\x*ObjectTest
                Norm\y=Normal\y*ObjectTest ;reverses the normal when inside
                Norm\z=Normal\z*ObjectTest ;ObjectTest is from TestBool, TestBool is -1 when inside and 1 when outside
                
                CosI.f = -(Norm\x * *Direction\x + Norm\y * *Direction\y + Norm\z * *Direction\z)
                SinT2.f = 1-n*n*(1-CosI*CosI)
                If SinT2>0
                  tv\x=(n**Direction\x)+(n*CosI-Sqr(SinT2))*Norm\x
                  tv\y=(n**Direction\y)+(n*CosI-Sqr(SinT2))*Norm\y
                  tv\z=(n**Direction\z)+(n*CosI-Sqr(SinT2))*Norm\z
                  
                  rayo\x=Intersection\x+tv\x*#EPSILON
                  rayo\y=Intersection\y+tv\y*#EPSILON
                  rayo\z=Intersection\z+tv\z*#EPSILON
                  
                  
                  TraceRay(rayo,tv,depth+1,ObjectList()\Material\RefractIndex,RefractColor)
                  result\Red=result\Red+RefractColor\Red ;transparency is not included yet
                  result\Green=result\Green+RefractColor\Green
                  result\Blue=result\Blue+RefractColor\Blue
                EndIf
              EndIf

You sure know where to put it.

Edit: OMG, I just found out the hard way that your Vector Cross Product Procedure is wrong. My triangle procedure produced strange results, and on first view your routine seemed ok, so I checked my code a hundred times. That's exactly the reason why I just wanted to optimize existing code. :roll:

Vector cross product should be :

Code: Select all

  *result\x = *a\y * *b\z - *a\z * *b\y
  *result\y = *a\z * *b\x - *a\x * *b\z
  *result\z = *a\x * *b\y - *a\y * *b\x

Ok, TestTriangle seemes to work now, I have to verify that, then I will optimize it.
I have implemented Moller-Trumbore's algorithm. It's fast without the need to precompute something. For really massive models this is faster because of the lower memory footprint of the 3D data. So, now you have a reason to implement the kd tree.

Dreglor · Post by **Dreglor** » Wed Jul 20, 2005 9:50 am

well i figured out that out my self to..
i didn't realize until i started testing my code for the triangles when i found it

why don't you post your code on the triangle intersection, because mine isn't perfect theres a trianglar figure in the shadows it makes, but its really buggy and messes the scene up and i don't accally see the triangle
im also using a diffrent method i think

i also started the frame work for texturing
i even implemented the floating point texture format (and tested it) its a huge 96bit format :O
included a converter

i did it so its native to the color format internally

also if you want to opmtizing things like the math in shadows, reflect, refract, diffuse, spectacular shading it would be nice becasue im not dropping any of those any time soon those are also the biggest hit in performace.

im all up to small snip its of optimizations

Hades · Post by **Hades** » Wed Jul 20, 2005 12:11 pm

I haven't done any assembly coding yet, but I have 4 versions of the intersection code.
Two witch use your vector math, two with inlined math. Each a version with and without backfaceculling.
With backfaceculling only Objects ( like a cube ) work fine, because you only see the triangle from one side, and it only casts a shadow to one side.

Without backfaceculling you get in trouble with the normal vector, because it points in the wrong direction, when you look from behind.

Maybe you should use the "TestBool=#InPrimitive" trick from your refraction routine to flip the normal vector.
I have prepared the non backfaceculling procedures for that. You just have to uncommend the corresponding line and clear the one before.

And here it goes :

Code: Select all

; Moller-Trumbore algorithm, inline version.
Procedure.f TestTriangle(*Origin.xyz,*Direction.xyz,*Triangle.Object)
  spana.xyz
  spanb.xyz
  PVec.xyz
  TVec.xyz
  QVec.xyz
  TestBool=#Miss
  
  *Tri.Triangle = *Triangle\Primitive ; Nicer and faster than PeekF
  
  spana\x = *Tri\v2\x - *Tri\v1\x
  spana\y = *Tri\v2\y - *Tri\v1\y
  spana\z = *Tri\v2\z - *Tri\v1\z
  spanb\x = *Tri\v3\x - *Tri\v1\x
  spanb\y = *Tri\v3\y - *Tri\v1\y
  spanb\z = *Tri\v3\z - *Tri\v1\z
  
  PVec\x = *Direction\y * spanb\z - *Direction\z * spanb\y
  PVec\y = *Direction\z * spanb\x - *Direction\x * spanb\z
  PVec\z = *Direction\x * spanb\y - *Direction\y * spanb\x
  
  Det.f = spana\x * PVec\x + spana\y * PVec\y + spana\z * PVec\z
  
  If Det > #EPSILON ; Frontfacing
    
    TVec\x = *Origin\x - *Tri\v1\x
    TVec\y = *Origin\y - *Tri\v1\y
    TVec\z = *Origin\z - *Tri\v1\z
    
    U.f = TVec\x * PVec\x + TVec\y * PVec\y + TVec\z * PVec\z
    If U < 0.0 Or U > Det
      ProcedureReturn 0.0 
    EndIf
    
    QVec\x = TVec\y * spana\z - TVec\z * spana\y
    QVec\y = TVec\z * spana\x - TVec\x * spana\z
    QVec\z = TVec\x * spana\y - TVec\y * spana\x
    
    V.f = *Direction\x * QVec\x + *Direction\y * QVec\y + *Direction\z * QVec\z
    
    If V < 0.0 Or U + V > Det
      ProcedureReturn 0.0 
    EndIf
    TestBool=#Hit
    
  ElseIf Det < #EPSILON ; Backfacing 
    
    TVec\x = *Origin\x - *Tri\v1\x
    TVec\y = *Origin\y - *Tri\v1\y
    TVec\z = *Origin\z - *Tri\v1\z
    
    U.f = TVec\x * PVec\x + TVec\y * PVec\y + TVec\z * PVec\z
    If U > 0.0 Or U < Det
      ProcedureReturn 0.0 
    EndIf
    
    QVec\x = TVec\y * spana\z - TVec\z * spana\y
    QVec\y = TVec\z * spana\x - TVec\x * spana\z
    QVec\z = TVec\x * spana\y - TVec\y * spana\x
    
    V.f = *Direction\x * QVec\x + *Direction\y * QVec\y + *Direction\z * QVec\z
    
    If V > 0.0 Or U + V < Det
      ProcedureReturn 0.0 
    EndIf
    TestBool=#Hit
    ; TestBool=#InPrimitive
    
  Else  ; ray parallel triangle
    ProcedureReturn 0.0
  EndIf
  InvDet.f = 1.0 / Det
  
  t.f = (spanb\x * QVec\x + spanb\y * QVec\y + spanb\z * QVec\z) * InvDet
  ; U = InvDet * U    ; texture coordinates
  ; V = InvDet * V    ; 
  ProcedureReturn t
EndProcedure

; Moller-Trumbore algorithm, inline version. With backface culling
Procedure.f TestTriangleBFC(*Origin.xyz,*Direction.xyz,*Triangle.Object)
  spana.xyz
  spanb.xyz
  PVec.xyz
  TVec.xyz
  QVec.xyz
  TestBool=#Miss
  
  *Tri.Triangle = *Triangle\Primitive ; Nicer and faster than PeekF
  
  spana\x = *Tri\v2\x - *Tri\v1\x
  spana\y = *Tri\v2\y - *Tri\v1\y
  spana\z = *Tri\v2\z - *Tri\v1\z
  spanb\x = *Tri\v3\x - *Tri\v1\x
  spanb\y = *Tri\v3\y - *Tri\v1\y
  spanb\z = *Tri\v3\z - *Tri\v1\z
  
  PVec\x = *Direction\y * spanb\z - *Direction\z * spanb\y
  PVec\y = *Direction\z * spanb\x - *Direction\x * spanb\z
  PVec\z = *Direction\x * spanb\y - *Direction\y * spanb\x

  Det.f = spana\x * PVec\x + spana\y * PVec\y + spana\z * PVec\z
  
  If Det < #EPSILON ; backfacing or ray parallel triangle
    ProcedureReturn 0.0
  EndIf
  
  TVec\x = *Origin\x - *Tri\v1\x
  TVec\y = *Origin\y - *Tri\v1\y
  TVec\z = *Origin\z - *Tri\v1\z

  U.f = TVec\x * PVec\x + TVec\y * PVec\y + TVec\z * PVec\z
  If U < 0.0 Or U > Det
    ProcedureReturn 0.0 
  EndIf
  
  QVec\x = TVec\y * spana\z - TVec\z * spana\y
  QVec\y = TVec\z * spana\x - TVec\x * spana\z
  QVec\z = TVec\x * spana\y - TVec\y * spana\x
  
  V.f = *Direction\x * QVec\x + *Direction\y * QVec\y + *Direction\z * QVec\z
  
  If V < 0.0 Or U + V > Det
    ProcedureReturn 0.0 
  EndIf
  
  InvDet.f = 1.0 / Det
  TestBool=#Hit
  
  t.f = (spanb\x * QVec\x + spanb\y * QVec\y + spanb\z * QVec\z) * InvDet
  ; U = InvDet * U    ; texture coordinates
  ; V = InvDet * V    ; 
  ProcedureReturn t
EndProcedure

; Moller-Trumbore algorithm, prototype version. Just to get going.
Procedure.f TestTriangleProto(*Origin.xyz,*Direction.xyz,*Triangle.Object)
  spana.xyz
  spanb.xyz
  PVec.xyz
  TVec.xyz
  QVec.xyz
  TestBool=#Miss
  
  *Tri.Triangle = *Triangle\Primitive ; Nicer and faster than PeekF
  
  VectorSubtract(*Tri\v2,*Tri\v1,spana) ; This could easily be done per frame, or at creation time.
  VectorSubtract(*Tri\v3,*Tri\v1,spanb) ; You could store spana / spanb instead of v2 / v3, because you don't need them.
  
  VectorCrossMuiltply(*Direction,spanb,PVec)
  Det.f = VectorDotProduct(spana,PVec)
  
  If Det > #EPSILON ; Frontfacing
    
    VectorSubtract(*Origin,*Tri\v1,TVec)
    
    U.f = VectorDotProduct(TVec,PVec)
    If U < 0.0 Or U > Det
      ProcedureReturn 0.0 
    EndIf
    
    VectorCrossMuiltply(TVec,spana,QVec)
    V.f = VectorDotProduct(*Direction,QVec)
    
    If V < 0.0 Or U + V > Det
      ProcedureReturn 0.0 
    EndIf
    TestBool=#Hit
    
  ElseIf Det < #EPSILON ; Backfacing 

    VectorSubtract(*Origin,*Tri\v1,TVec)
    
    U.f = VectorDotProduct(TVec,PVec)
    If U > 0.0 Or U < Det
      ProcedureReturn 0.0 
    EndIf
    
    VectorCrossMuiltply(TVec,spana,QVec)
    V.f = VectorDotProduct(*Direction,QVec)
    
    If V > 0.0 Or U + V < Det
      ProcedureReturn 0.0 
    EndIf
    TestBool=#Hit
    ; TestBool=#InPrimitive
    
  Else  ; ray parallel triangle
    ProcedureReturn 0.0
  EndIf
  
  InvDet.f = 1.0 / Det
  t.f = VectorDotProduct(spanb,QVec) * InvDet
  ; U = InvDet * U    ; texture coordinates
  ; V = InvDet * V    ; 
  ProcedureReturn t
EndProcedure

; Moller-Trumbore algorithm, prototype version. Just to get going. With backface culling
Procedure.f TestTriangleBFCProto(*Origin.xyz,*Direction.xyz,*Triangle.Object)
  spana.xyz
  spanb.xyz
  PVec.xyz
  TVec.xyz
  QVec.xyz
  TestBool=#Miss
  
  *Tri.Triangle = *Triangle\Primitive ; Nicer and faster than PeekF
  
  VectorSubtract(*Tri\v2,*Tri\v1,spana) ; This could easily be done per frame, or at creation time.
  VectorSubtract(*Tri\v3,*Tri\v1,spanb) ; You could store spana / spanb instead of v2 / v3, because you don't need them.
  
  VectorCrossMuiltply(*Direction,spanb,PVec)
  Det.f = VectorDotProduct(spana,PVec)
  
  If Det < #EPSILON ; backfacing or ray parallel triangle
    ProcedureReturn 0.0
  EndIf
  
  VectorSubtract(*Origin,*Tri\v1,TVec)
  
  U.f = VectorDotProduct(TVec,PVec)
  If U < 0.0 Or U > Det
    ProcedureReturn 0.0 
  EndIf
  
  VectorCrossMuiltply(TVec,spana,QVec)
  V.f = VectorDotProduct(*Direction,QVec)
  
  If V < 0.0 Or U + V > Det
    ProcedureReturn 0.0 
  EndIf
  
  InvDet.f = 1.0 / Det
  TestBool=#Hit
  t.f = VectorDotProduct(spanb,QVec) * InvDet
  ; U = InvDet * U    ; texture coordinates
  ; V = InvDet * V    ; 
  ProcedureReturn t
EndProcedure

Have fun.

PS: You shouldn't have problems integrating them, because i have used all your conventions. But if you get in trouble, just ask.

Dreglor · Post by **Dreglor** » Wed Jul 20, 2005 12:55 pm

thank hades

also i realized that my code i had before was the same method, and it did work i made a mistake of not setting the diffuse so it was completely black :roll:

your code is a tad bit faster (proably becasue of the peekf replacement)

so tomorrow im going to attempt adding textures and maybe a 3ds or some form of triangle mesh loading
im also going to do a quick optimization to triangles and the branching code for intersections (by replacing it

and any small optimizations i can make on the fly

it also seams that triangles are fastest intersections in my code heh

i don't think i be able to add kdtrees until sunday or saturday im busy for the next 3 days :\

so heres an upload with the newest code

PBRay7-20-05.zip
screens for all to see

Hades · Post by **Hades** » Wed Jul 20, 2005 1:11 pm

SUNDAY or SATURDAY ??? Witch week, witch month ?? You must be kidding !

No, seriously, I think you should plan a lot more time for that, or you will get frustrated. Or maybe your just much more productive than me. :roll:

Ok, while you are on triangles I stay away from that, and take a look at other parts of your program.

Edit: Oh, you updated your post with a picture.

The bottom line of the triangle isn't smooth as it should be. Thats because of the inaccuracy of the floating point math, and happens only if your near z=0. I absolutly don't know what to do against that at the moment. You have to make shure, when you build Objects from triangles, that all triangles are clockwise, or all are counterclockwise orientaded, or you get holes inside the object.

Edit2: Ok, what about a mesh loader? I could do a simple .asc loader. Maybe .obj, but please don't ask for .3ds. That's crap.

Edit3: Just something I just saw. You should trace your rays trought the centre of the pixels.

Like this:

Code: Select all

Procedure CalulateCameraVectors(*Scene.Scene,*ViewPort.Camera)
  Dim CameraVectors.xyz(*Scene\ScreenWidth,*Scene\ScreenHeight)
  For x=-*Scene\HalfScreenWidth To *Scene\HalfScreenWidth
    For y=-*Scene\HalfScreenHeight To *Scene\HalfScreenHeight
      x2.f=(x+0.5)*0.01 ; <<<
      y2.f=(y+0.5)*0.01 ; <<<
      CameraVectors(*Scene\HalfScreenWidth + x, *Scene\HalfScreenHeight + y)\x=x2-*ViewPort\Origin\x
      CameraVectors(*Scene\HalfScreenWidth + x, *Scene\HalfScreenHeight + y)\y=-y2-*ViewPort\Origin\y
      CameraVectors(*Scene\HalfScreenWidth + x, *Scene\HalfScreenHeight + y)\z=-*ViewPort\Origin\z
      VectorNormalize(CameraVectors(*Scene\HalfScreenWidth + x, *Scene\HalfScreenHeight + y))
    Next
  Next
EndProcedure

Dreglor · Post by **Dreglor** » Wed Jul 20, 2005 8:31 pm

in my last post it came out wrong about the kdtrees i ment i wouldn't be able to start until then

also today is havoc so i won't be doing much either but i did replace the intersection branch code it seams to work for inital tracing but when i apply it for the shadows it screwes it all up...

here is how i test for objects
intersectionmethod is added to the object structure
and it initalized when a object is added
this works

Code: Select all

For Object=0 To CountList(ObjectList()) - 1
      NextElement(ObjectList())
      CallFunctionFast(ObjectList()\IntersectionMethod, *Origin,*Direction,@ObjectList(),IntersectionResults) 
      IntersectionResults\result
      IntersectionResults\objectHandle=Object
      If IntersectionResults\result=#Hit Or IntersectionResults\result=#InPrimitive
        If IntersectionResults\t<Closest\t Or Closest\t=-1
          Closest\objectHandle=Object
          Closest\t=IntersectionResults\t
          Closest\result=IntersectionResults\result
        EndIf
      EndIf
    Next Object

here is the code for the shadows test this doesn't work

Code: Select all

For shadow=0 To CountList(ObjectList()) - 1
              NextElement(ObjectList())
              If @ObjectList()<>*Old_Element3 ;disables self shadowing because it cause werid problems...
                If ObjectList()\IsLight=#False
                  CallFunctionFast(ObjectList()\IntersectionMethod,rayo,rayd,@ObjectList(),IntersectionResults) ;hmm weird, doesn't want to work :|
                  ; If ObjectList()\Type=#ObjectType_Sphere
                    ; TestSphere(rayo,rayd,@ObjectList(),IntersectionResults)
                  ; ElseIf ObjectList()\Type=#ObjectType_Plane
                    ; TestPlane(rayo,rayd,@ObjectList(),IntersectionResults)
                  ; ElseIf ObjectList()\Type=#ObjectType_Triangle
                    ; TestTriangle(rayo,rayd,@ObjectList(),IntersectionResults)
                  ; EndIf
                  If IntersectionResults\result=#Hit
                    shade=ObjectList()\Material\Refract
                    Break
                  EndIf
                EndIf
              EndIf
            Next shadow

Hades · Post by **Hades** » Wed Jul 20, 2005 9:22 pm

As I don't have your newest version it is very hard for me to tell what is wrong and why.

But you should check also for shadow
If IntersectionResults\result=#Hit Or IntersectionResults\result=#InPrimitive

Could you upload the whole source for me to check?