Hi
I am a hobby programmer writing a ray tracer as a follow on from some work I did
at university. I have an object (utah teapot) made out of 6000 triangles and I
want to make a image of 1000 pixels by 1000 pixels.

Using pov ray as a comparison rendering the teapot at 1280*1024 with lighting
and no bounding box takes about 2 seconds. My ray tracer takes about 7 minutes.
But on investigation I discovered something I find very confusing. I
experimented with my code to speed it up and I decided to time just the empty
for loops which loop through the pixels and triangles. The code is as below.


 clock_t start = clock();

 int i;
 int x_res = 1000;

 int j;
 int y_res = 1000;

 int t;
 int numberOfTriangles = 6000;

 for(i=x_res; i!=0; i--){
  for(j=y_res; j!=0; j--){
   for(t=numberOfTriangles; t!=0; t--){

    //empty loop
   }
  }
 }

 printf("Time elapsed %f\n", (double)(clock() - start)/1000);


This takes 18 seconds run. The inner "triangle" loop is executed 6 billion times
here and is we think in each loop there is a few instructions like decrement the
counter, check the condition, jump to the top of the loop, then there is around
(say 10 instructions a loop) 60 billion instructions and on my 2.3GHz Core i3
processor this should take around 25 seconds which is in the area of what I am
getting.

Now if we return to the POV Ray if you add the vector maths into the loop then
this is probably more like 100 instructions per loop giving 60 billion
instructions and so how is this executed in only a couple of seconds?

Can somebody shed some light on how pov ray is apparently running so much faster
than my processor.

I am not a computer scientist so maybe I am mistaking something about processor
architecture.

Kind regards,

Post a reply to this message

rf242 <nomail@nomail> wrote:
> I am not a computer scientist so maybe I am mistaking something about processor
> architecture.

  No, you are not mistaken about the processor. You are mistaken about the
raytracing algorithm. POV-Ray does not test each triangle for each pixel.
It only tests a small subset of all the triangles.

-- 
                                                          - Warp

Post a reply to this message

Warp <war### [at] tagpovrayorg> wrote:
> rf242 <nomail@nomail> wrote:
> > I am not a computer scientist so maybe I am mistaking something about processor
> > architecture.
>
>   No, you are not mistaken about the processor. You are mistaken about the
> raytracing algorithm. POV-Ray does not test each triangle for each pixel.
> It only tests a small subset of all the triangles.
>
> --
>                                                           - Warp
Thanks Warp,

Ok so how does pov ray decide which triangles are in this subset or can you
direct me to where in the pov ray source code this happens.

regards rf242

Post a reply to this message

rf242 <nomail@nomail> wrote:
> Ok so how does pov ray decide which triangles are in this subset or can you
> direct me to where in the pov ray source code this happens.

  IIRC it puts the triangles in an octree, so testing a ray against the
entire mesh requires on average testing against about O(log n) triangles.

http://en.wikipedia.org/wiki/Octree

  Another commonly-used data container is a K-d tree:

http://en.wikipedia.org/wiki/Kd-tree

  (The basic difference between an octree and a K-d tree is that an octree
is always subdivided into 8 parts at each level, while a K-d tree is divided
only into two. It's just that each subsequent division is made alternatively
on each of the three axes, so the end result is similar, but more efficient.)

-- 
                                                          - Warp

Post a reply to this message