Last time it was a voxel playset. This one is a "simplex" playset:
A simplex is the the minimum geometric unit you can have. In 2D they are triangles, in 3D tetrahedrons and in 4D, well, you do not really want to go there.
They matter because when you are looking for a solution to a problem, it is often best to target the simplest element possible. If your solution is based on them, it is likely to be the simplest solution as well.
It is no coincidence we use triangles extensively for rendering. In 3D simplexes are equally useful. For instance, Perlin rewrote his famous noise function to work over simplexes instead of cubes. It resulted in a faster, better looking noise, which Perlin aptly named -you have guessed- "Simplex Noise". At this point in time, there is no reason why someone would use Perlin noise when Simplex noise is available. We also have Marching Tetrahedrons, which improves over Marching Cubes.
In my case I was looking at them because of their role in interpolations. Trilinear interpolation is often done in a cube. If you do it over simplexes you can shave off a few multiplications. When this is in a hot area of your code simplexes can make a difference. And above all you also have an excuse to play with these cool toys. Did I mention they are magnetic?
And the best thing is: try to build a cube out of simplexes (simplices?) in your mind when you can't sleep. On the other side you might go crazy while trying...
ReplyDeleteHey, if it works, it works! XD
ReplyDeleteThe picture from the article and the subjects of this blog reminded me of Patterns : http://lindenlab.com/products/patterns
ReplyDeleteHave you experimented with other shapes than cubes for voxels?
I don't mean to answer for Miguel, and am looking forward to his answer, but I have some insight into this area that I'd like to share.
DeleteI worked on a fine-grained voxel-based graphics engine for a while. For fine-grained voxels, where all you care about is getting the voxels to closely mimic arbitrary real-world shapes, it just doesn't make sense to use anything but cubes. You can represent tetrahedra and hexagonal prisms fairly easily by using a skewed grid, but it's slower, and makes the math harder without actually improving the voxels' ability to represent general shapes.
I should note that performance is actually only affected when you're doing volumetric operations, e.g. "delete all voxels within this sphere". For a system like MineCraft, where almost all of the CPU time is spent converting the voxels into polygons, it's not as big an issue.
For coarse-grained voxel systems, where the voxels are actually used to achieve an aesthetic, like in MineCraft, there's definitely merit in pursuing that avenue of thought. If MineCraft's voxels were hexagonal prisms, each voxel would have 8 sides instead of 6, and this would open up quite a few interesting gameplay possibilities.
One idea that really fascinates me is combining non-cubic voxels with non-euclidean space. Imagine if you could walk a square path on a hexagonal grid without having to cross any tiles diagonally. You'd probably need to use ray-tracing to render it, but I expect any player exposed to a world where Pi = 3.14*3/2 = 4.71 would quickly have their minds blown. But alas, that is not something that fine-grained voxel systems seem to be interested in.
I have not tried enough to be sure of anything.
DeleteMarching Tetrahedrons is supposed to produce less mesh aberrations. Also you need to encode a lower number of cases.
I have not seen dual contouring over simplexes, but I am sure it exists somewhere (If someone has a link it would be appreciated).
I would not know if it performs better, but I could speculate: When using hermite data to reconstruct points inside a cube voxel, you need to feed a maximum of 12 planes to your solver. This is because there are 12 edges in a cube. With Tetrahedrons you have a maximum of 6 edges. That alone could be worth the switch.
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.44.7602&rep=rep1&type=pdf
DeleteI think it could be modified and apllied
Thanks Igor, looks promising. Will have a look later tonight.
DeleteMiguel - we can tile 3d space not only by boxes. Did you think under another type of voxels - like truncated octahedrons
ReplyDeleteYes, I often think about that... then my head starts spinning :)
DeleteHmm... well Hexagons tile nicely.
ReplyDeletehttp://www.i-gami.com/images/hexagon%20sphere2.jpg
DeleteThat bad boy looks more like a dodecahedron (pentagons as sides)
DeleteOh my god, I was looking at your paper and I can see we drew the same diagram at some point. It's the picture of two squares next to 4 smaller ones, right by the blue simplex that is attached to the two red ones, that is on the paper. That's for generating seams. I drew that one about 7 months ago when I was working on seams. That's fun.
ReplyDeleteProof: http://www.reddit.com/r/VoxelGameDev/comments/15m1uc/almost_got_the_lod_working_with_the_surface_nets/c7oa6jk
Ah, doing seams too... I know your pain.
DeleteIt has been one of the biggest pains so far. Any advice?
DeleteAre you doing surface nets? If you were doing marching cubes you can look at transvoxel.
DeleteDual contouring, just not the QEF part yet.
DeleteOK this is the same I use. So you have two sides to the seam, one at double the resolution than the other. This is pretty much like an octree. Dual Contouring can be run over an octree. This is how they do it here: http://www.frankpetterson.com/publications/dualcontour/dualcontour.pdf
DeleteIf you have your data discontinuities under control, this should be all you need.
I guess I do not have the data discontinuities under control, that's what I believe I'm having issues with. I've read the Losasso's paper many times, the trick with seams is in the "minimal edges" that the article talks about. That's basically what that picture that we both drew is dealing with. Downsampling is what causes most of the problems I believe. I downsample using morphological filtering but even that isn't perfect.
DeleteMiguel - want to ask you about this method http://www.youtube.com/watch?v=8sf9soKi7j4
ReplyDeleteWhat do you think about it?
I saw it a while ago. Looks very promising. In their video they say it runs fine on GPUs and also uses octrees for adaptive processing. I don't remember their original paper, not sure if these two are possible at the same time. If they have a simple GPU implementation that works over octrees, this is a HUGE win.
DeleteWhat was the brand/model of the "simplex" toy blocks you bought?
ReplyDeleteAfter unsuccessfully searching Amazon for "simplex" and "tetrahedron" toys a colleague recommended I search for Amazon "popular playthings mag block" which lists two options: 48 pieces and 24 pieces. The 48 pieces contains two complete "cubes". They fit the bill perfectly as each pyramid piece is about 1" x 1.41" x 2" !
Delete