interactive ray tracing of implicits

 
Post new topic   Reply to topic    K3DSurf forum Forum Index -> K3DSurf Discuss/Discussions
View previous topic :: View next topic  

If you could ray trace implicits interactively instead of drawing a mesh, would you?
Absolutely yes!
40%
 40%  [ 2 ]
Maybe, if it was just as fast.
0%
 0%  [ 0 ]
Maybe, if it was more correct.
20%
 20%  [ 1 ]
Maybe, if it was more dynamic.
40%
 40%  [ 2 ]
Nope.
0%
 0%  [ 0 ]
Total Votes : 5

Author Message
tollingbell



Joined: 11 Sep 2007
Posts: 4
Location: Utah

PostPosted: Wed Sep 12, 2007 12:43 pm    Post subject: interactive ray tracing of implicits Reply with quote

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
Back to top View user's profile Send private message AIM Address
nextstep
Site Admin


Joined: 06 Jan 2007
Posts: 538

PostPosted: Thu Sep 13, 2007 5:53 am    Post subject: Reply with quote

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
Back to top View user's profile Send private message
tollingbell



Joined: 11 Sep 2007
Posts: 4
Location: Utah

PostPosted: Thu Sep 13, 2007 6:24 am    Post subject: Reply with quote

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.
Back to top View user's profile Send private message AIM Address
nextstep
Site Admin


Joined: 06 Jan 2007
Posts: 538

PostPosted: Sun Sep 16, 2007 9:48 am    Post subject: Reply with quote

Hi all,

tollingbell wrote:

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.

I want just to add some precisions to your comments, especially for those who are not involved in the field :
1) There are some extensions to the Marching Cube algorithm (MC) that resolve most of it's artifacts : "Extended Marching Cubes" and especially the "Dual Marching Cubes". The real advantage of the MC over the ray-trace algorithm is it's speed, where the ray-trace algorithm has the advantage of the images quality.
2) The MC is well suited for real time manipulations even without a hardware implementation. Also, the MC is usually used to boost the speed of a ray-tracer by generating a 3D mesh (a ray tracer is faster when manipulating a mesh than processing the 3D structure itself) : For example, K3DSurf can generate a 3D mesh for PovRay and PovRay is faster when manipulating a mesh than using it's internal isosurface structure.
tollingbell wrote:
There's still a lot of work to do, but implicits are a good first step.

Implicits are effectively a good first step...as far as they aren't too much complicated formulas: as you know, the ray-tracer is based on series of tests and every tests need an implicit evaluation.
Implicit can then be a hell for a raytracer (compared to a 3d mesh ). The solution? a hardware implementation of a mathematical functions parser or even better , the use of the "geometrical parser" Very Happy
_________________
Cheers,
Abderrahman
Back to top View user's profile Send private message
tollingbell



Joined: 11 Sep 2007
Posts: 4
Location: Utah

PostPosted: Sun Sep 16, 2007 10:07 am    Post subject: Reply with quote

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.
Back to top View user's profile Send private message AIM Address
tollingbell



Joined: 11 Sep 2007
Posts: 4
Location: Utah

PostPosted: Sun Sep 16, 2007 10:13 am    Post subject: Reply with quote

One more comment Smile
Quote:
For example, K3DSurf can generate a 3D mesh for PovRay and PovRay is faster when manipulating a mesh than using it's internal isosurface structure.

For arbitrary implicits, PovRay uses a method called Sturmian sequences that is very slow. Clearly, PovRay is much faster ray-tracing the mesh directly -- in fact any good ray tracer should be faster at rendering a 1st-order mesh than any arbitrary high-order implicit!

However, if you compare the time/quality of extracting and ray tracing a *good* to that of ray tracing it directly, I think that eventually ray tracing directly, if done properly using these IA/AA methods, will win out.
Back to top View user's profile Send private message AIM Address
Display posts from previous:   
Post new topic   Reply to topic    K3DSurf forum Forum Index -> K3DSurf Discuss/Discussions All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


2005 Powered by phpBB © 2001, 2005 phpBB Group


Start Your Own Video Sharing Site

Free Web Hosting | Free Forum Hosting | FlashWebHost.com | Image Hosting | Photo Gallery | FreeMarriage.com

Powered by PhpBBweb.com, setup your forum now!
For Support, visit Forums.BizHat.com