Hacker News Reader

Comment by samsaga2 | Hacker News Reader

It seems that he is using marching cubes [http://http.developer.nvidia.com/GPUGems3/gpugems3_ch01.html]

Nope - good guess though. :) Funny story about marching cubes: in 2004, when I was creating my first major game engine, I "invented" the marching cubes algorithm without knowing that it already existed (and at that time, was patented) - a testament to how stubborn I am about learning on my own.

I am actually using ray-cast volumes, rendered to a hexagon (6 tris). Each vertex in the hexagon contains two points, a front and back location of the equivalent cube. (If you look a a cube in isometric perspective, it looks just like a hexagon which is why I used this technique -- another thing I'm sure that has been done before me). :) Another optimization over a standard cube is that a cube contains 12 triangles, and would have double redundancy on fill time.

> and at that time, was patented

Is it no longer patented today? Who held the patent and was it released or did it just expire?

The patent expired in 2005.

you wouldn't have a link to the actual patent do you?

https://www.google.com/patents/US4710876

Looks like a bullshit patent to me, anyway. Isn't it an obvious procedure to go from voxel to voxel in order to create a mesh from a 3D texture?

@sspiff (can't reply because it is nested too deep I guess?) -- I think it expired in 2005 or 2006 if I remember correctly.

(The reply link doesn't show up until a few minutes after a comment is posted.)

But can we have a more in-depth post about how you do do it? Are you tessellating on the CPU? When you say "on the GPU", do you mean you have a geometry shader? What platform are you using? I mean, I'm hoping for a lovely technical blog post with a few illustrations ;)

Excellent work, keep it up! Gorgeous :)

Thanks! The only thing that uses triangles directly is the grass (I could do some shader magic and perhaps render all the grass on a single quad, but it probably would not be worth it in terms of performance or visual results). Everything else is ray cast. It renders voxel data to a 2D render target, and does path tracing on that target to get the results. It more or less all happens in texture memory/FBOs with shaders. :) I will try to provide more details time willing! (Not much free time these days obviously :D)

ray casting or ray marching?

I ask as I've done a bit of fractal rendering using distance-estimators before.

I hate to say it but I always misuse the terms. It uses marching.

The Feynman approach. Nice :)

Could you elaborate or link to the relevant paper? Feynman did so many things that looking for the particular thing you have in mind probably is like looking for a needle in a needlestack.

It's not a paper, just an anecdote - in one of the many stories about him he mentions that he liked to independently solve problems that other people had already solved in order to learn the subject in question better, and to advance his problem solving skills. Sorry for lack of source, I'm quite tired... if you can't find it let me know and I'll try to dig it up tomorrow.

Oh, in that sense! I thought you implied he had solved some math problem that happened to be useful in voxel engines or something.

I actually went through the same thing! I was also working on a voxel engine a good few years ago and when going through all the ways of turning voxels into meshes I invented my own version of marching cubes as well.

When I finally found the right search terms to Google on the issues I ran into I came across the real marching cubes algorithm and was actually happy I figured out most of it on my own. A good boost for my self-confidence. The fact that the patent just had ran out was nice as well.

If you scroll to the end of this page you can see some screenshots: http://github.com/aerique/okra

I'm sure many people have done this, which is why John Carmack's quote on patents is so relevant.

I have a funny story also. I "invented" mmx, and markov chains. Well, MMX didn't exist when I envisioned it, it came 10 years later. Markov chains, I have no idea how long they've been around, but I'd had the idea about 6 years ago. If only once I can generate a new idea, I'd be happy.

:) I invented the Hadamard transform once. Only later realized it had been invented couple of decades earlier.

Quite likely.

Reply on news.ycombinator.com