K3DSurf forum

tollingbell · Joined: 11 Sep 2007 Posts: 4 Location: Utah

Hi everyone,

I don't know if you guys know this, but an efficient ray tracing algorithm works for implicits too. Unlike marching cubes, you'll never can never have too "high" a resolution, and many implicit functions will actually be rendered correctly. The technique uses interval arithmetic or affine arithmetic, and requires fairly low precision (i.e. low rendering time) for correct results.

I just got the CPU version of this published at the IEEE ray tracing symposium 2007. Pseudocode is given too. The CPU version is interactive for simple implicits, but it's still much faster than pov-ray:

Since I'm a new poster (i.e. potential spammer) I can't post yet in these forums, but you can find my paper by google-searching for

"Interactive Ray Tracing of Arbitrary Implicits with SIMD Interval Arithmetic"

Coming *very* soon is a tech report of our new GPU implementation, which is about 20 times faster than on the CPU. Running code for Windows, Linux and Mac should be available soon afterwards.

Hope you guys find this interesting Smile

nextstep · Site Admin Joined: 06 Jan 2007 Posts: 539

Hi all,
Welcome tollingbell in the forum Smile

Your work sound very interesting : a hardware implementation of a ray tracer! I've some doubt about the quality of the images in comparison with Pov-Ray (for example) but that still very exciting !
I'm interested because I've a hope that one day we can make some games where the scene and all Characters are described mathematically (that's my dream Razz

) and of course implicit functions are good candidates for this project. I downloaded your paper and will take a closer look on it as soon as possible.
_________________
Cheers,
Abderrahman

tollingbell · Joined: 11 Sep 2007 Posts: 4 Location: Utah

Thanks -- I'm very impressed by what this community has done.

One of the big problems whenever I try to do this work and submit it to the major conferences is that there is this consensus that implicits are dead or useless. This is the case both in the academic and game/film graphics communities.

Personally I think that there is a lot that can be done with implicits, even if it takes a lot of creativity (and that is one of its advantages!). If this sort of program (k3dsurf) had been available in years past, and game/film people didn't think of implicits as just a way to do blobbies, then the situation could well be different!

As for ray tracing, we're in a transitional period. Graphics hardware is (finally) getting better at doing full ray tracing, as opposed to being able to ray trace just a sphere. There's still a lot of work to do, but implicits are a good first step. Meanwhile, they're something that rasterization doesn't really do well at all -- marching cubes or bloomenthal polygonization (what k3dsurf uses, I believe) have some serious limitations.

nextstep · Site Admin Joined: 06 Jan 2007 Posts: 539

Hi all,

tollingbell · Joined: 11 Sep 2007 Posts: 4 Location: Utah

This is very true -- there are better ways of meshing than marching cubes. One can use dual marching cubes or dual contouring, or Lipschitz-like methods with guidance-field meshing methods. These all make much nicer meshes than marching cubes. However, they are all a lot *slower* than marching cubes -- there is a reason that marching cubes is still used everywhere instead of these methods! (it's also really easy to implement).

As for ray tracing, it is true that evaluating the function per-ray is expensive compared to just on the edges of the cubes in MC. It's actually a lot worse than that, since you need to evaluate multiple times per ray, and to get robust results you need to evaluate the interval or affine extension of the function which is at least twice as expensive (though there are other less-general ways of ray tracing). However, with a bit of optimization on the CPU or even now the GPU you can do this very quickly and scalably.

The same cannot be said of marching cubes or any of these extraction methods: ultimately for the smooth quality you want, you'll have many more mesh vertices in 3D than ray samples in 2D. So while MC works great for small meshes and generally continuous implicits, it isn't as good
for high-quality -- it's better to ray trace the function directly. There are many, many advantages to doing that in the long run.

Right now, however, ray tracing is still unpopular because all of graphics is built around mesh rasterization. So it's unlikely marching cubes will go away. Still, it could be useful to build an IA/AA ray tracer into a program like k3dsurf, and in the long run I think all these surfaces will be ray-traced directly on graphics hardware.

tollingbell · Joined: 11 Sep 2007 Posts: 4 Location: Utah

One more comment Smile