realtime raytracer project

[ferris]

In my opinion, kd-trees in rtrt is just a waste of time - on modern processors all they've been to me is overhead.

But, it's very nice to see someone else trying this for once - I've been trying to imitate heaven 7's for at least a year and a half now

Good luck with finishing this project.

[ferris]

P.S. About wierd artifacts for textures in a tracer, if you set the threshold low enough with adaptive subsampling you can still get high speeds and it will look good - because when you interpolate accross the square you interpolate texture coords, not colors.

This can be seen very well in two 64k intros:
http://www.pouet.net/prod.php?which=5 <- Heaven Seven by Exceed &
http://www.pouet.net/prod.php?which=1324 Fresnel 2 by Kolor.

Both of these intros were produced before 2002 and you can see how sweet they are. Fresnel 2 also uses opengl to do their interpolation - something I may have to try one of these days.

Once again, good luck.

[frea]

In my opinion, kd-trees in rtrt is just a waste of time - on modern processors all they've been to me is overhead.

Don't tell me that for high-poly statical scene a kd-tree is waste of time .
What would you use instead? Octrees?

[ferris]

In raytracing, at least if you want it realtime, you have to understand that modern machines, even if you're coding a rtrt using shaders on the GPU, high-poly scenes are simply out of the question.

I'd be willing to bet with modern technology that 60fps can't be acheived rendering 100 spheres or more. Which is why any kind of scene-dividing scheme, such a kd-trees or octrees, is out of the question.

If anyone can prove this wrong, I'd like to see some evidence, because I think I'm underestimating hardware today.

[frea]

Ingo Wald published his phd thesis in which he shows how he did rtrt. He achives, if i recall correcltly, from 10 to 90 milions of rays per a second. That should be enough for 100 spheres .

There's also somewhere a publication of rtrt on a GPU reporting about 20 milons rays per second. Still enough .
All ofcourse use kd-trees,

Although he doesn't have 60 fps, i don't see why much simpler scenes couldn't be rendered enough fast.

[taj]

I'd be willing to bet with modern technology that 60fps can't be acheived rendering 100 spheres or more. Which is why any kind of scene-dividing scheme, such a kd-trees or octrees, is out of the question.

A small mental exercise.
I can achieve 60fps (and more) with 12 spheres on x1850 @ 1280 x 768, one light source, shadows, 3 levels of reflection. Spheres move, camera moves - no cheating. Spheres fill 1/3 - 1/2 of the screen. I estimate I am getting in excess of 50 million rays per second.

So, an SLI,8800, about 8x the shader speed (2 cards, each 4x the 1850), running at lower resolution (800x600) can do the same at (8x x 2x x 60) at 960 fps I guess. At that stage, obviously more spheres could be tested. Though I cant be sure, my guess is that 100 spheres in a simple standard accelerating structure could easily be updated in real time on the cpu and sent to the graphics card to render at 60fps.

Right lunch over, back to work...

[Jim]

10million rays per second = 200000 rays per frame.  If I'm running at 640x480 (300000pixels) that's less than 1 ray per pixel per frame.  Not really that impressive.

Jim

[taj]

Hi,

We need to be careful here. Ferris you are talking about the most trivial possible raytracer using a few spheres or whatever: a toy. Kd isnt going to help here. The same is true of my raytracer. A single ray here is doing very little (lets say 10-20 trivial objects to intersect) so I would say 100 million rays is achieveable. 60 fps is easy and yet still its not impressive to me.

On the other hand, Frea, you talk about hugely complex scenes. In essence a ray is intersecting tens (even hundreds) of thousands of objects. The objects themselves (triangles) are more complex than the ones Ferris and I are talking about.

Heres are examples of the kinds of scenes Ingo is tracing to clear this up, straight from his thesis:
http://www.sci.utah.edu/~wald/Publications/2007///FastBuild/teaser/full_teaser5.png
(This is an example of the "teapot in a football stadium" scene which is the hardest for raytracers)
http://www.sci.utah.edu/~wald/Publications/2004///WaldPhD/teaser/full_sunflowers_1.png
http://www.sci.utah.edu/~wald/Publications/2004///WaldPhD/teaser/full_officeIGI.png
http://www.sci.utah.edu/~wald/Publications/2004///WaldPhD/teaser/full_hella.png
http://www.sci.utah.edu/~wald/Publications/2004///WaldPhD/teaser/full_conferenceIGI.png

10-90 million rays in such scenes knocks my socks off Jim: to me this is impressive. As you say, at 640x480 it would run at less than 1 frame a second (for 10 million) so from that point of view its not impressive. Some of these scenes would run faster in polygon hardware. I really think it depends how you look at it if its impressive or not. For me, its more impressive than _anything_ I've seen in the demoscene.

One more thought exercise. Lets assume that raytracing becomes useful at about 2 rays per pixel. Most pixels use 1 ray but some do refraction and reflection, making the average around 2. (I'm excluding shadow rays here as they can perform much faster).
2 per pixel at 1024 x 768 x 60fps = ~100 million rays needed.
If Freas numbers are right (20 million) then thats just two generations of hardware from now (with quite some power left over for post processing shaders) for real time raytraced games. I wonder if any company will be brave enough, my guess is only a small start-up, not one of the giants.

Taj

[ferris]

Thanks for clearing that up Taj

Sorry Frea if I sounded like an ass "attacking" you, I just thought (mostly from what I've seen in realtime yet) that (and this is on the CPU only, not GPU) :
1. Triangles, as of yet, are virtually impossible in RTRT.
2. Taj would agree with me on this; our "toy" raytracers only intersect 10-20 simple objects (spheres, planes, cones, cylinders, etc.) and that's why they're fast.

For large scenes kd-trees or octrees or any spacial subdivision techniques are great, but overhead if you're doing simpler scenes which most RTRTs have done in the past 7 years or so.

And again, sorry

[relsoft]

Hey, guys, I'm more of an octree(for levels) and spheretree(for object) guy. 

Some helpful source for tree building up to quadtree(I think)
http://www.rel.betterwebber.com/index.php?action=contents&item=Tutorials

What is the main difference between the octree and the kd tree?  Of course the octree limits it's children to just 8 adjacent "boxes" for as lonf as there is a particular vertex in the said box.  Is the kd-tree also composed of boxes?


Here's the octree demo with texture branching(FFP only no shaders)

http://www.rel.betterwebber.com/junk.php?id=88

[frea]

because octrees use always the same size of the cube it sometimes stores huge empty space in many nodes. kd-tree uses no fixed size ( streched cubes ) so it can store the empty space in lesser amount of nodes.
Also the transvesal code is easier in some parts. You don't need to decide in which of the 8 subnodes you want to enter, but only in which 2. ( kd-trees always divides subspace into two subspaces )

Ferris: nothing happend .

[Jim]

Taj, you're right, those scenes at 10m rays/sec would be amazing.  Are there any videos?
Jim

[taj]

Taj, you're right, those scenes at 10m rays/sec would be amazing.  Are there any videos?
Jim

I couldnt see any from his thesis but there are other things there so maybe you can find something:
http://www.sci.utah.edu/~wald/Publications/

[relsoft]

because octrees use always the same size of the cube it sometimes stores huge empty space in many nodes. kd-tree uses no fixed size ( streched cubes ) so it can store the empty space in lesser amount of nodes.
Also the transvesal code is easier in some parts. You don't need to decide in which of the 8 subnodes you want to enter, but only in which 2. ( kd-trees always divides subspace into two subspaces )

Ferris: nothing happend .

Actually that's not how octrees are optimized.  With octrees, you only subdivide if the number of vertices exceeds the maximum threshold a "box" can contain. So in essence, the empty space you're talking about is stored in just one node an not even drawn.

So kd-trees are like axis-aligned BSP trees?

[frea]

Imagine a 2d scene 0x0 to 16x16, with 5 triangles in the 0x0 to 1x1 square and 5 triangles in 15x15 to 16x16 square.
Let's say that the quadree wil stop dividing only if the amount of triangles in the box is less or equal to 4.
The quadree will be having two subtrees going in the direction of the 2 corners. In the end it will make:
4 subnodes at the first time.
8 subnodes at the second time ( dividing the top right and bottom left nodes )
8 same as above.
8 as above
and next 8 dividing only the squares 0x0 to 1x1 and 15x15 to 16x16.

now a kd-tree, using a bad heuristic, searching for the median.
First split is just in the middle, so 2 nodes.
Now we divide 0x0 to 8x8 and 8x8 to 16x16 independantly.
each of these parts is divided only once in the middle of the groups of the triangles. So in total this gives
6 nodes, 4 leafs. This is a much smaller number.

[taj]

So kd-trees are like axis-aligned BSP trees?

Exactly.

[relsoft]

Imagine a 2d scene 0x0 to 16x16, with 5 triangles in the 0x0 to 1x1 square and 5 triangles in 15x15 to 16x16 square.
Let's say that the quadree wil stop dividing only if the amount of triangles in the box is less or equal to 4.
The quadree will be having two subtrees going in the direction of the 2 corners. In the end it will make:
8 subnodes at the first time.
16 subnodes at the second time ( dividing the top right and bottom left nodes )
16 same as above.
16 as above
and next 16 dividing only the squares 0x0 to 1x1 and 15x15 to 16x16.

now a kd-tree, using a bad heuristic, searching for the median.
First split is just in the middle, so 2 nodes.
Now we divide 0x0 to 8x8 and 8x8 to 16x16 independantly.
each of these parts is divided only once in the middle of the groups of the triangles. So in total this gives
6 nodes, 4 leafs. This is a much smaller number.

Then how is it that most of the pro-games of today are using octrees and not kd-trees?  I really can't see a speed increase with using a kd-tree in my case since with octrees you only need to check node and see if it has a triangle and if it does not, all the child nodes are empty so you don't even need to traverse it.   

[taj]

Then how is it that most of the pro-games of today are using octrees and not kd-trees? 

Erm because they dont raytrace the scene?

[frea]

kd trees are good at statical scenes, while octrees at dynamical. I would hate to play a completly statical game.
in the example i gave you, you need to traverse more in quadtree than in kd-tree. Best case scenario for quadtree is 5 steps, for kd tree worst case is 4.