Project: RRE (Raytrace Rendering Engine)

[moogie]

As a critical part of my next year's entry I am attempting to make a real time raytracing engine which will render my scene.

The objectives of the render are:

- achieve 15fps at 800x600 on a reasonably modern PC
- reflection
- refraction
- simple shadows
- textures
- bump mapping
- fog
- able to handle spherical and triangle primitives
- use a bounding volume heirachy



I now have the render at an inital stage able to display the bounding volumes (spheres) which represent objects.
- no secondary rays are cast yet.

Currently with no code optimisations and only proof of concept frustrum subdivision optmisation implemented it is able to render a scene of 41 viewable objects out of a total of 32767 objects onto a 800x600 screen in 0.2 seconds using a Pentium 4 duel core 3000 mhz (thus really only 1500 mhz thanks to java not utilising both cores).

This seems holds promise. My biggest concern is whether i am able to reduce reduce the class size to fit in 4k and allow a game as well!


Below is a screen shot thus far:


The magenta areas represent the bounding spheres of the objects, the yellow gridded areas show the frustrum subdivision.

The darker the magenta the further away the object is from the camera.

[moogie]

I have implemented an optimisation which tests each corner of a sub divided frustrum to see if all the corners hit the same object. If they do then then all the pixels in that frustum must also hit the object and so we do not need to sub divide further.

This holds true given that all the primitives shapes are concave (which they are).

This optimisation has speed up the render significantly and it is now able to render the same scene in 0.06 seconds!

[Alan_W]

Being a 3D in 4K fan myself, this looks fascinating.  I'm looking forward to seeing how it turns out, even if it doesn't squeeze down into 4k.  Many years ago I made a full real-time raytracer for the Acorn Archimedes in hand tuned machine code (no lighting, no texturing, no reflections, very low resolution), using hand crafted fixed point arithmetic crafted to take advantage of the limited parallelism in the ARMs arithmetic logic unit.  It did work, but was very low resolution and suffered from fish-eye lens distortion, due to some algorithm simplifications.

Not much progress on my 3D entry yet.  I'm using a stripped down version of the terrain raycaster from last year, in conjunction with a new object rendering system.  The object renderer is only a theoretical paper concept, and is a bit unusual so is under wraps at the moment.  There's a nasty square root in the algorithm that gets processed on a per pixel basis, thats probably going to need fixed point and a look-up table.  Game size is currently 2K (compressed) with the basic terrain renderer, but without the object renderer and gameplay elements.  I'm under severe time pressure, so probably no further progress until December.

Games published by our own members! Check 'em out!

[moogie]

I have always had a facination with raytracers. I guess it just makes more sense in my head I have always wanted to try my hand at a real time ray tracer so this 4k comp should give me impetus and motivation to finish it.

I think i may be a little ambitious with all the objectives to fit in 4k, however i hope to at a minimum have:

-sphere and triangle primitives
-reflection
-at least 15 frames at 640x480

I have to think on how to store 3d models sufficiently compressed so that they can be used in a 4k entry. To this end i am going to try and fit the rendering engine in 3k allowing 1k for gameplay and models. Lets see if i can achieve it

That Acorn rtrt sounds crazy! I would not have thought i would be possible to achieve decent frame rates on older hardware such as that! A real credit to you for accomplishing that feat! or should i be backing slowly away from the scary person ?

Yeah, those pseky square roots are trouble. what sort of range does the value being square rooted have? maybe an approximation lookup table would be sufficient?

I am surprised that it seems no one has used view frustrum sub division culling in the manner i am using before. I would have thought that it was a logical progression from normal view frustrum culling.

what i am currenly doing is:

1. initally sub divding the view frustrum into 4x3 sub divisions
2. for each of these sub frustrums see what objects from the parent sub frustrum is potentially visible in the new sub division
3. if there is at least 1 object visible then sub divide the current frustrum into four sub divisions
3a. ray trace each corner of the subdivision to see if each courner hits the same object.
3b. if all corners hit the same object then assume all other pixels in the sub division likewise hit the object
3c. else  repeat 2

To speed up the process, for the inital view frustum i am approximating it as a sphere to cull most objects. Then i approximate the frustrum as a cone to further cull objects and finally i cull the objects using the actual frustrum. Like wise for each subdivision i approximate the sub frustrum as a cone first. It seems to speed things up considerably.

This new object render you speak of does sound intriguging cant wait to see it practise!

[c_lilian]

Hey, good luck with your RTRT !

for my 2005 entry  http://vlsolutions.com/free/bubbleracer2005/ I had to drop so many things to fit into 4k that it was a little bit disapointing.

One day we'll gather and start a special 8k RTRT contest , THAT would be really interesting !

Good luck anyway, and looking forward to see your entry

Lilian

[moogie]

Hehe, i do remeber your posts as you progressed with your entry.

Any chance that i can have a peek at your source code so i an gain inspiration and hopefully avoid pit falls?

[c_lilian]

hehe, you don't really want to have a look at my 4k code (even I don't understand it anymore !)

Lilian

[moogie]

lol i understand!

[nonnus29]

Being a 3D in 4K fan myself, this looks fascinating.  I'm looking forward to seeing how it turns out, even if it doesn't squeeze down into 4k.  Many years ago I made a full real-time raytracer for the Acorn Archimedes in hand tuned machine code (no lighting, no texturing, no reflections, very low resolution), using hand crafted fixed point arithmetic crafted to take advantage of the limited parallelism in the ARMs arithmetic logic unit.  It did work, but was very low resolution and suffered from fish-eye lens distortion, due to some algorithm simplifications.

Not much progress on my 3D entry yet.  I'm using a stripped down version of the terrain raycaster from last year, in conjunction with a new object rendering system.  The object renderer is only a theoretical paper concept, and is a bit unusual so is under wraps at the moment.  There's a nasty square root in the algorithm that gets processed on a per pixel basis, thats probably going to need fixed point and a look-up table.  Game size is currently 2K (compressed) with the basic terrain renderer, but without the object renderer and gameplay elements.  I'm under severe time pressure, so probably no further progress until December.

For my entry-that-wasn't last year I had a 3d polygon renderer with flat shading that came in at just under 2k.  That other 2k doesn't leave much room for gameplay.  That's one reason why I was so impressed with the 3d shooter Ares last year.  Maybe I'll revisit mine if I have time.  But wow, is it hard.

[Alan_W]

Nonnus, I'm not too worried about having used 2k so far, since that includes all the overhead of the class, creating the window, player movement etc. However the size of the object renderer (with object definitions) will be critical. I know how big a triangle renderer can get and I'm amazed you got one in 2k.  For that reason, I won't be pushing triangles, but don't want to say more, in case my plan doesn't work out.  Unfortunately haven't got time to work on it this month, but it should surface sometime in December.

Games published by our own members! Check 'em out!

[LME]

Interesting project, keep us posted on your progress, 32k object is alot! Im trying to develop an interactive raytracer for this year's competition aswell but I've started in the opposite end from you. Im writing the shader code first and then I'll try to optimize it for speed and size.. kinda backwards I know. The previous raytracer I wrote (Prong in the 2004 version of j4k) had severe performance troubles at the time so my goal this time is to write something a bit faster, a bit larger and a bit more fun!

[moogie]

It seems this year will be the year of the 3d engines in 4k

I am sure that there is no "correct" way to make a 4k entry let alone a ray tracer in 4k! It will be interesting to see what happens!

I am not so worried about performance rather than the byte code size the raytracing engine will take. It will be not much use if I only have 300 bytes to make a game with it

[darkprophet]

It will be not much use if I only have 300 bytes to make a game with it

Raytraced Pong!

[moogie]

After spending gads knows how many hours trying to understand why my frustrum division algorithm was only partially working I had a relevation and now have my first hit optimisation algorithm at a state where i now will turn my focus onto secondary rays.

The problem was while  it divided the frustrum correctly until it had a frustrum with contained an object in the scene from then on it always sub divided no matter if the sub divided frustrums contained an object or not!

This meant that there were unnessary subvision and ray intersection checks.

Currently the renderer is able to render the same scene in 0.047 seconds:



I have not implemented any mathematical or coding optimisations at this stage,. I plan to have a working version of the render before I go optmising and byte 'hunting'. I anticipate a further 25% increase in performance after I do optimise.

All in all it is still looking viable Now the big question is to see how much of a hit the reflected rays and refracted rays will cause.

[moogie]

Does anyone have any ideas as to how best repsent an "object" which can consist of 1 or more spheres, triangles and hopefully cylinders?

When i say best i mean in the least total bytes. (including the object 'reader' which would add the object to the rendering engine)

I would imagine seperating each different aspect of the model and then storing like aspects 'close' to each other in a stream (perhaps as a Hexadecimal string) would aid the Deflate mechansim and help reduce the model byte size... But would the gain be lost from the extra byte code needed to interpret the stream...