Snail - yet another realtime raytracer

Hello,

I've been working on this project for about a year, but only recently i've added support for textures and some dynamic objects on the scene, so i think, it can be shown to wider audience .

Most recent demo (map, animated model and textures are taken from Doom 3) [~13MB]:
http://students.mimuw.edu.pl/~kj219441/rtracer/doom3map_rtdemo.7z
archives contain both windows and linux (32bit and 64bit) binaries.
Source code: http://students.mimuw.edu.pl/~kj219441/rtracer/sources/

Quick info:
- Code is pure C++ with lots of templates (for example: bih::Tree< TreeBox< bih::Tree< TriangleVector > > > )
- I use SSE almost everywhere (with my own vector classes with overloaded operators, so the code still looks nice)
- Binaries for both windows and linux are created with gcc 4.3.2 (crosscompiled for windows)

Some older demos and screenshots:
http://students.mimuw.edu.pl/~kj219441/rtracer/

I'm eager to hear some opinions .

Looks pretty cool. What approach are you taking for texture filtering? I couldn't see any undersampling, so it looks like you're using mipmaps .

[beason]

Seems really fast. Are you using SSE? Also, how fast is the machine that those screenshots (on your blog, with timings) are from?

Seems really fast. Are you using SSE?

- I use SSE almost everywhere

Looks pretty cool. What approach are you taking for texture filtering? I couldn't see any undersampling, so it looks like you're using mipmaps .

Yes, i'm using mipmaps, but without any filtering, looks good enough for me.

Seems really fast. Are you using SSE? Also, how fast is the machine that those screenshots (on your blog, with timings) are from?

Yes, i'm using SSE in BIH packet traversal (I have also something similar to frustum tracing for coherent rays), shading and sampling.
Timings were taken on Core 2 Duo E4300 (1.8GHZ not overclocked).

BTW if you have quad core, you can try the demo yourself, im really curious how it runs on high-end machines .

Looks like very nice work and is obviously well optimized. The binary runs fine in my 64-bit Linux and in Windows.

I think anti-aliasing and better quality texture filtering should be on your high priority list, because especially without lights and with the rough texture quality it reminds me more of Doom 1 than Doom 3 .

Here is my code for adaptive anti-aliasing detection after shooting 1 ray per pixel, if it is of any help:

Code: Select all

// Compare two pixels to determine need for anti-aliasing. rgbsum holds R+G+B for each pixel. ids contains integer id of object at pixel. antialias holds a boolean list of pixels to shoot extra rays for.
inline void pixel_compare(int px1, int px2)
{
if (ids[px1] == ids[px1]) // Pixels part of the same object, no anti-aliasing
        return;

if (fabs(rgbsum[px1] - rgbsum[px2]) > blimit) // blimit should be some fraction of max intensity
        {
        antialias[px1]=true;
        antialias[px2]=true;
        }
}

#pragma omp parallel for // divide work to n_threads amount of big blocks
for (int i=0;i<pixels - pixels_x;i++)
        {
        pixel_compare(i,i+1,blimit);
        pixel_compare(i,i+cam->pixels_x, blimit);
        }


I can also show you code on creating the extra rays and the way I shoot them, which is of course nothing extraordinary, but my code is pretty simple and thus instructive and developing good practices for doings things always takes its time (fast and best possibly image quality).

Only getting about 50% cpu usage here on my 8 thread machine, and I didnt see any 64bit windows exe, but it does run well. 60fps at the starting view, and 30-40 most everywhere else.

64bit windows exe that uses 8 threads would easily be a solid 60fps everywhere I imagine.

Here is my code for adaptive anti-aliasing detection after shooting 1 ray per pixel, if it is of any help: ...

Thx for the code, i will make a use of that .

Only getting about 50% cpu usage here on my 8 thread machine, and I didnt see any 64bit windows exe, but it does run well.

Try running with parameter: -threads 8 (default is 4). 64-bit binary is avaliable only for linux, sorry.

8 threads takes it up to about 82% usage (and even more threads doesnt really change that). I assume you have some non-parallel process that happens once per frame that blocks everything else? One thing I did was double buffer a lot of my data and use a thread do do things like update my BVH, clear the framebuffer, and copy the data up to a texture....that got my CPU usage from 80% like you to nearly 95% and a decent framerate boost to go along with.

I get 50-60fps everywhere without reflections, 40-60fps with reflections. Pretty impressive

Forgot: this is a 4.0ghz core i7

8 threads takes it up to about 82% usage...

Thats good, it means there are some spare cycles for additional effects

I get 50-60fps everywhere without reflections, 40-60fps with reflections. Pretty impressive

yeah

i like how big the actual scene is. with j, one can place new lights, and so i ran around and spread light everywhere.

i tested it on a 2.4ghz quadcore. it was playable all the time (>10fps for sure). not exactly smooth, but playable..

it looks really pretty btw.

[toxie]

Kick ass man!!!
This is really something stunning! (and i like that it uses the BIH )

I didn't look at your demo (will do soon I think ), but one point interests me to the highest degree, the vector SSE class with overloaded operators : how did you do to get maximal performances ? when I had tried, it was really disastrous...

I didn't look at your demo (will do soon I think ), but one point interests me to the highest degree, the vector SSE class with overloaded operators : how did you do to get maximal performances ? when I had tried, it was really disastrous...

http://nadult.linuxpl.eu/stuff/veclib.tar.7z
You can find some quick info in veclib.h

The veclib looks really interesting. I'm finding hard to quickly see how it should be used. Could you show for example how to 1) create a 4xfloat SSE type 2) perform vectorized multiplication and division and then 3) take a sqrt() of the results and 4) look inside a single element (float) of the result. That is:

Code: Select all

4xfloat r,x,y;
r = x*y;
r = r / x;
sqrt(r)
cout <<  r[0]


And do all that ^ keeping the data in SSE registers.

[tbp]

and i like that it uses the BIH

To me that's the first convincing demo

The veclib looks really interesting. I'm finding hard to quickly see how it should be used. Could you show for example how to 1) create a 4xfloat SSE type 2) perform vectorized multiplication and division and then 3) take a sqrt() of the results and 4) look inside a single element (float) of the result. That is:

Code: Select all

4xfloat r,x,y;
r = x*y;
r = r / x;
sqrt(r)
cout <<  r[0]


And do all that ^ keeping the data in SSE registers.

Code: Select all

f32x4 r,x(1.0f,2.0f,3.0f,4.0f),y(5.0f,6.0f,7.0f,8.0f);
r = x*y; r=Sqrt(r/x);
cout << r[0] << ' ' << r[1] << ' ' << r[2] << ' ' << r[3] << '\n';


Another example:

// If 4 rays have common origin, then we can use pvec3f32 (takes only one sse register instead of 3)
// or Vec3<float> instead of Vec3<f32x4>
template <class VecO,class Vec>
typename Vec::TScalar Triangle::Collide(const VecO &rOrig,const Vec &rDir) const {
	typedef typename Vec::TScalar real;
	typedef typename Vec::TBool Bool;

	real out=-1.0f;

	real det = rDir|Nrm();
	VecO tvec = rOrig-VecO(a);
	real u = rDir|(VecO(ba)^tvec); // | is dot product,  ^ is cross product
	real v = rDir|(tvec^VecO(ca));
	Bool test=Min(u,v)>=0.0f&&u+v<=det*real(((float*)&ca)[3]);

	if (ForAny(test)) {
		real dist=-(tvec|Nrm())/det;
		out=Condition(test,dist,out);
	}

	return out;
}

I didn't look at your demo (will do soon I think ), but one point interests me to the highest degree, the vector SSE class with overloaded operators : how did you do to get maximal performances ? when I had tried, it was really disastrous...

I second that. It is probably a bit offtopic here, and might deserve its own thread. Anyway, I created a vector4 class with overloaded operators that use SSE, and did some simple operations with it. I compared the resulting assembler code with code generated using equivalent intrinsics, and it is disastrous indeed. For the Intel C++ compiler, I have to say. Visual C++ generates exactly the same code, up to a single extra instruction ("add esp, 14h") more in the vector class case. It depresses me a bit, since I (obviously) prefer readable code.

I didn't look at your demo (will do soon I think ), but one point interests me to the highest degree, the vector SSE class with overloaded operators : how did you do to get maximal performances ? when I had tried, it was really disastrous...

I second that. It is probably a bit offtopic here, and might deserve its own thread. Anyway, I created a vector4 class with overloaded operators that use SSE, and did some simple operations with it. I compared the resulting assembler code with code generated using equivalent intrinsics, and it is disastrous indeed. For the Intel C++ compiler, I have to say. Visual C++ generates exactly the same code, up to a single extra instruction ("add esp, 14h") more in the vector class case. It depresses me a bit, since I (obviously) prefer readable code.

How disastrous? It wasn't inlined, registers were allocated poorly, or maybe something else? If i remember well Visual C++ generated very poor code if you didn't implement copying constructor and operator= (you have to do this in gcc too, if you have a union inside your class). Besides that, you have to make sure that everything gets inlined, and it should be ok.

Another example:

Thanks! I did little benchmarking by loading 10000 of your f32x4 types in std::vector (and equally long results vector) and then looping over it doing: " r = 1/sqrt(x) * x + x" and comparing that to the same code in scalar.

By using FastRSqrt() the vector path was (40.5+-0.5)x faster!
By using Sqrt() the vector path was(6.2+-0.2)x faster.
Even by just doing " r = x " the vector path was (1.8+-0.1)x faster.

I haven't looked at the implementation and I am not able to read anything of the instruction code outputted by g++ -S, but this looks like a viable way to use SSE for me.

The small benchmark code:

veclibbench.tar.gz

(1.49 KiB) Downloaded 186 times

when I had had a look at the assembly code, there were plenty of register transfers from vectorial to scalar ones when using a union, between each SIMD op in fact.

I second that. It is probably a bit offtopic here, and might deserve its own thread.

How about the "Snippets" sticky thread in "Tools, Demos & Sources"?

I have also had problems with MSVC9 and intrinsics. I tried to write aabb intersection code with intrinsics, and it was no faster than the straight C++ code with branches. (same problem with scalar instructions (stores!!!) between each SSE instruction) Then I tried to write inline assembler, but I haven't used assembler since the 8088 days, so I don't know how to load from the stack into the SSE registers, so that code was also no faster. Anyone want to educate me? (I'll post my existing code for you fix.)

when I had had a look at the assembly code, there were plenty of register transfers from vectorial to scalar ones when using a union, between each SIMD op in fact.

It would be interesting to know in more detail how veclib works in this regard, eg. should it be equivalent in many cases to manual SSE code when used properly, or not. The answer is of course in the source..

nadult: I think you would be interested to know, that I also benchmarked your Vec3<float> type against my so far favorite basic 3D vector implementation boost::cvalarray<float,3> and found that they are in any tested case either equally fast, or cvalarray is faster. Cvalarray is also more flexible allowing eg. float * Vec and Vec * float and not just the latter. Interestingly pure assignment v1 = v2 was about (1.4+-0.05)x faster with cvalarray so you might want to look into it. Otherwise speed differences were pretty small.

[tbp]

I have also had problems with MSVC9 and intrinsics.

I'm going to sound like a broken record, but abandon any residual hope of getting anywhere with msvc9 (in fact any version) and intrinsics. And its braindead inline asm won't be of much help to fix it (because of friction with optimization).
Reading the changelog, for that version or those before, will tell you about Microsoft priorities.

nadult: I think you would be interested to know, that I also benchmarked your Vec3<float> type against my so far favorite basic 3D vector implementation boost::cvalarray<float,3> and found that they are in any tested case either equally fast, or cvalarray is faster. Cvalarray is also more flexible allowing eg. float * Vec and Vec * float and not just the latter. Interestingly pure assignment v1 = v2 was about (1.4+-0.05)x faster with cvalarray so you might want to look into it. Otherwise speed differences were pretty small.

That's interesting indeed, but i am not able to reproduce your results (i tried, but in most cases both libraries ran with the same speed, in some cases veclib was few times faster, because it was automaticly vectorized ).

Update: OK i think i got it. Pure assignment indeed is faster (it is automaticly vectorized) with cvalarray than with veclib, if you compile it on gcc 4.4. Solution was simple: all i had to do was to implement assignment operator and copying constructor in Vec3<> .

Update2: I have uploaded new version of veclib: http://nadult.linuxpl.eu/stuff/veclib.tar.7z. Now Vec3<float> should be as fast as cvalarray<float,3> .

just a question : what license did you choose to use for veclib, if you chose any at the moment ? I didn't find anything related to this in your otherwise passionating code and I didn't understand how it works from the small part I read

just a question : what license did you choose to use for veclib, if you chose any at the moment ? I didn't find anything related to this in your otherwise passionating code and I didn't understand how it works from the small part I read

BSD, that is: do whatever you want to do with the code, just give me some credit

I put your Vec3 type to the ultimate test: I used in my ray tracer instead of boost::cvalarray without changing a line of code in application (except one typedef). Unfortunately this cost me 36fps -> 30 fps in the particular test scene. I have very little idea where this difference comes from, I'm using the vectors in myriads of difference ways. Perhaps cvalarray might be better with temporaries in many sorts of different combinations of types?

My code uses vec[0] access instead of vec.x, so I had to add overloaded [] to Vec3 with a member pointer access:

Code: Select all

   __inline__ base& operator [] (int i)
   {
        static base Vec3<base>:: * const members[3] =
         {
         &Vec3<base>::x, &Vec3<base>::y, &Vec3<base>::z
         };
        return this->*members[i];
   }


Using this gave me identical speed to .x access in couple of static benchmark, but can't be sure this isn't relevant.

I put your Vec3 type to the ultimate test: I used in my ray tracer instead of boost::cvalarray without changing a line of code in application (except one typedef). Unfortunately this cost me 36fps -> 30 fps in the particular test scene. I have very little idea where this difference comes from, I'm using the vectors in myriads of difference ways. Perhaps cvalarray might be better with temporaries in many sorts of different combinations of types?

My code uses vec[0] access instead of vec.x, so I had to add overloaded [] to Vec3 with a member pointer access:

Code: Select all

   __inline__ base& operator [] (int i)
   {
        static base Vec3<base>:: * const members[3] =
         {
         &Vec3<base>::x, &Vec3<base>::y, &Vec3<base>::z
         };
        return this->*members[i];
   }


Using this gave me identical speed to .x access in couple of static benchmark, but can't be sure this isn't relevant.

What compiler are you using? Operator[] looks overcomplicated, try this:

Code: Select all

__inline__ operator base*() { return &x; }

[tbp]

What compiler are you using? Operator[] looks overcomplicated, try this:

Code: Select all

__inline__ operator base*() { return &x; }

That's bogus, and not just hypothetically; GCC, somewhere around 4.1 if i remember, became good enough to sometime produce wrong code for exactly such idiom. If you want an indexable contiguous something, have an array (yes, it's a pain in the behindment in C++03).

my so far favorite basic 3D vector implementation boost::cvalarray<float,3> and found that they are in any tested case either equally fast, or cvalarray is faster. Cvalarray is also more flexible allowing eg. float * Vec and Vec * float and not just the latter. Interestingly pure assignment v1 = v2 was about (1.4+-0.05)x faster with cvalarray so you might want to look into it. Otherwise speed differences were pretty small.

hello,
following the discussion here, I became interested in having a look at this boost::cvalarray class. However, issuing a grep on a boost's svn checkout didn't get any result.
so in the end, boost:cvalarray isn't part of boost?

so in the end, boost:cvalarray isn't part of boost?

Well this is my mistake. There are some connections (search "boost cvalarray") and I originally got it from a Boost hosted download site. The code is at: http://sourceforge.net/projects/cvalarray and it is not part of official Boost libraries.

On my quad core it never runs under 16 fps... really amazing demo!

[ypoissant]

Anyone ever tested and/or compared "Eigen"? I was not aware of this library/template until someone mentioned it on another forum. The author claims regarding the efficiency of the vector implementation are intriguing. And it seems to support SIMD for short vectors.

Cool stuff - like the mip-mapping.

Some questions:

1) How do you filter the mip maps?

2) What's the performance of mip maps compared to not using them

3) How many polygons does your scene have?

Thank you for including a linux version!

Linux , Core 2 Duo (threads=2). Pretty fast (16-20 fps), even with reflections (14-16fps). Good works! I'm waiting for more (better mouse input - i can only look left or right, much larger map!, and jumping ). Antialiasing is missing.

Btw. Thanks for Eigen library link. It looks nice and fast. Anyone interested in D programming language should look at BLADE http://www.dsource.org/projects/mathext ... runk/blade (It is so simple and so fast, amazing)

Cool stuff - like the mip-mapping.

Some questions:

1) How do you filter the mip maps?

I don't filter them Maybe in next version...

2) What's the performance of mip maps compared to not using them

I've benchmarked different samplers using 4096x4096 texture:
Sampling time compared with R8G8B8 with mipmaps:
R8G8B8 no mipmaps: 0.67
R5G6B5 with mipmaps: 0.96
R5G6B5 no mipmaps: 0.59
DXT1 with mipmaps: 1.08
DXT1 no mipmaps: 1.29
SAT (summed area tables): 1.57

Such syntetic benchmark doesn't say much though, so i've compared whole rendering time of doom3 map scene with and without mipmaps: both versions work with the same speed (+-0.5%).
Update: DXT1 with mipmaps isn't much slower either (2%) and it uses only 1/8th of the memory.

3) How many polygons does your scene have?

48K + 1.3K*4
If you want more you can wait for next version or try the older version (http://nadult.linuxpl.eu/blog/?p=3) with pompei.obj scene (~500K tris).

Thank you for including a linux version!

You're welcome .

Anyone ever tested and/or compared "Eigen"? I was not aware of this library/template until someone mentioned it on another forum. The author claims regarding the efficiency of the vector implementation are intriguing. And it seems to support SIMD for short vectors.

indeed it would be nice to know if someone took the time to compare Eigen2 with cvalarray

nadult: I apologize for being OT, but in http://nadult.linuxpl.eu/rtracer/images ... _mesh2.png , you mentioned some 10Msec per frame, which is slower than the walk of a High Speed Sloth. But according to the FPS counter, you probably really mean 10msec, which is as fast as an Elite Meerkat

Pretty good results

Btw, prefixes.

I'm not going to continue this project, so i'm releasing the source code. I guess i should've done it earlier ,but still, better late than never .
http://students.mimuw.edu.pl/~kj219441/rtracer/sources/

You need to download all 4 packages, and besides that: squish (included in gfxlib), glfw, libpng, SCons, and gcc 4.3 at least (i'm using a few C++0x extensions).

I think highly of this openness. I will have to see what can I learn or use from it. Perhaps the .dds loading and looking at how you used veclib at least.