November | 2009 | Alberto's Blog

Raydiant: realtime mutithreaded global illumination

2009-11-08 at 11:04 | Posted in Computer path | Leave a comment
Tags: 3D, C++, density distribution, fractal, game, global illumination, path tracing, procedural, ray tracing

The global illumination tracer module has been finally completed/debugged and is working. So the new ideas applied to Raydiant engine about realtime steradian controled stem count to improve performance are now proved to be useful. Also the generic multithreaded tracer than can hold any other tracer inside (like the global illumination one) and transparently clone it and make it work at any number of threads simultaneously without synchronization penalties is completed and debugged. The result is that now you can interactively move yourself around in a synthetic scenario with true realtime global illumination in a i7. This opens far-reaching possibilities: games that look as if you where there is one I’m really attracted to. Also now that Fermi platform from Nvidia is here the Raydiant engine can be compiled at one of those 512 CPU cards and see what happends… . Because there is no precalcs the scene lights can be instantly moved around. And any number of ligths can be put at a secenario with no performance penalty, in fact is the inverse. On some of these screenshots the new light dispersion capability of the Raydiant engine can be clearly appreciated.

Raydiant: custom probability distribution

2009-11-07 at 11:11 | Posted in Computer path | 1 Comment
Tags: 3D, C++, density distribution, fractal, game, procedural, ray tracing

It was very useful to be able to transform a constant normalized random distribution (same probability for every number between 0 and 1) into another one with personalized density distribution. This has been used to create materials choosing photon bouncing directions. Also used on objective depth of field effects of different types. This is the way I did it (and really enjoyed deducing this one):

Lets suppose we have a random generator with a density probability distribution : D(x)=1 for all 0<=x<1, and lets call ‘r’ the random numbers generated by this distribution.

We want to get another density probability distribution called E(x), of course definite integral of E(x) between x=0 and x=1 must be exactly 1.

Lets call ‘t’ to the random numbers generated by E(x) distribution.

I found the relationship between r and t is: r = definite integral of E(x) between x=0 and x=t. This is to say the area defined between E(x) and the horizontals axis between x=0 and x=t must be exactly r.

So just substitute your E(x) and solve the equation for t.

Applied example 1: find a random distribution that applied to a radius and given uniform random angles gives a homogeneous surface distribution at the plane inside a radius 1 circle:
- Solution: t = sqrt(r/pi)

Applied example 2: find a random distribution that applied to a radius and given uniform random angles gives a homogeneous surface distribution at the plane inside a washer of radius r0 and r1 with r0<r1:
- Solution: t = (-b+sqrt(b^2+2ar))/a with a = (2(r1-r0))/(r0+r1) and b = 1-(r1-r0)/(r0+r1)

As exercise: can you calculate ‘t’ for a random distribution which is completely lineal between x=0 and x=1?

These are some screen shoots of custom random distributions made by my wife María with the same Raydiant engine:

Raydiant: Random generators

2009-11-07 at 10:09 | Posted in Computer path | 3 Comments
Tags: 3D, C++, fractal, game, procedural, pseudorandom, random generator, ray tracing

I find delightful the art of pseudorandom number generation. A bunch of generators has been tested before choosing one for the Raydiant engine. Some of them have been found to be not so random by the simple method of drawing random points in an accumulation buffer. These are the bad sheep (see the screen shoots just to be sure):

Park-Miller “minimal standard” 31 bit pseudo-random number generator, implemented with David G. Carta’s optimization: with 32 bit math and without division.

Lehmer random number generator. For more details see: “Random Number Generators: Good Ones Are Hard To Find” by Steve Park and Keith Miller, Communications of the ACM, October 1988.

Concatenation of following two 16-bit multiply with carry generators: x(n) = a*x(n-1)+carry mod 2^16 and y(n) = b*y(n-1)+carry mod 2^16. Number and carry packed within the same 32 bit integer. Pass all of the tests in Marsaglia’s “Diehard” battery of statistical tests.

Combination of a Multiply with carry generator and a simple multiplicative generator. Returns x(n) + z(n) where x(n) = x(n-1) + x(n-2) mod 2^32 and z(n) = 30903 * z(n-1) + carry mod 2^16. Pass all of the tests in Marsaglia’s “Diehard” battery of statistical tests.

On the other hand there were other generators that didn’t show their true predictive nature and insisted on appearing as true random numbers:

ANSI C pseudorandom number generator.
Mersenne Twister pseudorandom number generator.
Robert Jenkins’ IBAA generator. Pass all of the tests in Marsaglia’s “Diehard” battery of statistical tests.
Combination of lagged Fibonacci generator and a multiply with carry generator. Returning x(n)+y(n) mod 2^32 where x(n)=x(n-99)*x(n-33)mod2^32, x’s odd and y(n)=30903*y(n-1)+carrymod2^16. Pass all of the tests in Marsaglia’s “Diehard” battery of statistical tests.
A Combination of 2 multiple recursive generators. Has parameters for 3 different combos. Source: Pierre
* L’Ecuyer, “Good Parameter Sets for Combined Multiple Recursive Random Number Generators.” Operations Research, vol.47 no.1 (1999), pp.159–164. Pass all of the tests in Marsaglia’s “Diehard” battery of statistical tests.
Combination of 3 Tausworthe generators — assumes 32-bit integers, Source: Pierre L’Ecuyer, “Maximally
Equidistributed Combined Tausworthe Generators”. Mathematics of Computation, vol.65, no.213(1996), pp203–213. Pass all of the tests in Marsaglia’s “Diehard” battery of statistical tests. Strong theoretical backing so far.
Combination of 4 tausworth generators — assumes 32-bit integers, Sources: Pierre L’Ecuyer, “Tables of
Maximally-Equidistributed Combined LFSR Generators.” Mathematics of Computation, vol.68, no 225(1999), pp.261–269. Pass all of the tests in Marsaglia’s “Diehard” battery of statistical tests. Strong theoretical backing so far.

Other merits considered to choose the perfect one were fastness of set seed operation, low memory usage, length of period and of course random number generation performance. And the winner is…

Combination of a shift-register sequence on a 32-bit vector, a linear congruential generator, and a multiply with carry sequence. Returns y+x+z where y(n) = b xor (b<<5), b = a xor (a>>17), a = y(n-1) xor (y(n-1)<<13)), x(n) = 69069*x(n-1)+1mod2^32 and z(n) = 2*z(n-1)+z(n-2)+carry mod 2^32. The period is > 2^127. Extremely high quality, extremely fast, ultra fast set seed, 32 bit random numbers. Pass all of the tests in Marsaglia’s “Diehard” battery of statistical tests.

These are the bad sheep, to appreciate the defects is imperative you see them at full size and 1 pixel per texel zoom. A couple billion points have been accumulated on each one:

: Park-Miller “minimal standard”

: Lehmer

: Multiply with carry 16

: Multiply with carry

Raydiant IV

2009-11-07 at 09:54 | Posted in Computer path | Leave a comment
Tags: 3D, C++, fractal, game, procedural, ray tracing

Those are the last tests just before starting completing and debugging the HQ render with radiosity. This waiting is killing me but discipline is not a luxury but a necessity when dealing with hundred of thousands of C++ lines. The main components of the engine are the ethers, materials and chromes. Simply put ethers are the shape of things, materials define how light interact with things and chromes define the color of each point. These 3 main elements can be freely combined between them so any new one that is implemented provokes a combinatory explosion of new possibilities. To improve performance an automatic steradian dispersion ray calculator has been included so the optimum child ray count are generated in each photon bouncing.

Raydiant III

2009-11-07 at 09:27 | Posted in Computer path | Leave a comment
Tags: 3D, C++, fractal, game, procedural, ray tracing

OK, after a lot of debugging the Raydiant engine is starting to behave, so much so that even transparent, translucent and diffuse reflective materials look good even on preview mode. And preview mode generates frames at an interactive rate, I’m having so much fun moving around in this test scenario. At this stage of developing only 1 thread is still currently being used. I can’t wait to increase that number to 8, the optimum for my i7. Of course once this mechanism is coded and debugged you will be able to select any number of threads, something appropriate for your particular system.

Raydiant II

2009-11-07 at 09:18 | Posted in Computer path | Leave a comment
Tags: 3D, C++, fractal, game, procedural, ray tracing

The new Raydiant engine will be able to accurately simulate light dispersion and coupling a new architecture several times faster with the new multithreaded ability with no synchronization overhead things are looking good. The ability to visualize the recursive grid spatial partition has been very useful for debugging and intellectual enjoyment also. But all this is still theory because by now only preview mode interactive and static renders had been obtained:

i7 2930MHz 4x2threads: Raydiant

2009-11-06 at 21:57 | Posted in Computer path | Leave a comment
Tags: 3D, C++, fractal, game, procedural, ray tracing

So after finishing and using the Raydiosity engine I could see some ways to improve the quality and performance of the renders. And with the new true multikernel CPUs may be even realtime true radiosity interactive movement could be achieved, a game can be made… . As with the previous Raydiosity engine a fundamental feature is a strong and easy procedural geometry and texture generation API. This time I linked with Qt library. After 6 months of redesign and heavy coding this are some of the screen shoots of the new Raydiant engine in preview mode (most of them are obtained at interactive rates):

Pentium IV 3000MHz V: Raydiosity fruit

2009-11-05 at 19:50 | Posted in Computer path | Leave a comment
Tags: 3D, C++, fractal, game, procedural, ray tracing

Many experiments involving procedural generation of geometry were conducted with the Raydiant engine, some of them may be technically interesting or aesthetical. A bunch of them:

Pentium IV 3000MHz IV: Raydiosity GUI

2009-11-05 at 18:25 | Posted in Computer path | Leave a comment
Tags: 3D, C++, fractal, game, procedural, ray tracing

The Raydiosity engine was a pure command line program so I developed a front end on top. It allowed for interactive frame generation on preview mode so you could move around and explore the procedural scenarios, this are some screen shoots:

Pentium IV 3000MHz III: Raydiosity

2009-11-05 at 18:17 | Posted in Computer path | Leave a comment
Tags: 3D, C++, fractal, game, procedural, ray tracing

So I put myself to work very carefully, stayed designing on paper and CASE tools the Raydiosity engine about 2 months before starting writing a single line of C++. Raydiosity engine is a path tracer and was linked with no library except standard C++ basic libraries so everything on it is built from scratch. The engine was prepared to be executed on any number of computers at the same time and on each computer any number of instances of the engine could be launched simultaneously. Everything was controled with a front-end. Most of the renders were synthesised with a K7 (1 Raydiant instance) and a P4 (2 Raydiant instances). It took 6 months to get the engine working. I prefer equations and algorithms to hand-made mouse design so a great amount of effort has been put on the geometry and texture procedural API. Almost without exception all Raydiosity renders use exclusively procedural entities. Wanted to translate to reality some images I had in my mind to share them with friends, here they are: