rasterizing isosurfaces
category: code [glöplog]
I understand that by doing raymarching you can do isosurfaces easily. However I would like to ask if anyone has implemented marching polyhedra algorithm for rasterizers before? And if they knows the pro's and con's in relationship to the marching cubes algorithm.
I did a typo. i meant "marching tetrahedra" instead of polyhedra.
I think i open a similar topic some weeks ago (not sure you want exactly same thing)
There have been marching tetrahedron-based demos/intros. One I can think of is this 1k-intro by Kalms: http://www.pouet.net/prod.php?which=63491
I think the short version is that tetrahedra needs more intersection-checks and generates more polygons for the same grid than cubes, so it is slightly less efficient.
I believe the original reason for using tetrahedra was that marching cubes was patented.
Since the patent has now expired, there really is no reason to use tetrahedra anymore.
I think the short version is that tetrahedra needs more intersection-checks and generates more polygons for the same grid than cubes, so it is slightly less efficient.
I believe the original reason for using tetrahedra was that marching cubes was patented.
Since the patent has now expired, there really is no reason to use tetrahedra anymore.
Tigrou: I found your thread, so yes maybe. My idea which i've had for some years now (but never had the time to implement) is to iterate over all points in a tetahedral grid.
Im playing with the thought to update isosurfaces using regular tetrahedra (where the triangles are equilateral) or if its not optimum speed-wise, use tetrahedra inside grid/boxes. The points are either interpolating or just moving in (in x, y and z) based on a fast updating function using neighbourhood rules.
Im playing with the thought to update isosurfaces using regular tetrahedra (where the triangles are equilateral) or if its not optimum speed-wise, use tetrahedra inside grid/boxes. The points are either interpolating or just moving in (in x, y and z) based on a fast updating function using neighbourhood rules.
one only needs 3 bits per point to know in which direction to move.
example: X Y Z
0 0 0 - moves(-1,-1,-1)
0 0 1 - moves(-1,-1,1)
0 1 0 - moves(-1,1,-1)
etc...
if this works, this would be very fast for many points. one would have 20 points in a 64-bit register. i wonder if these bits also can represent normals at the same time (which would be great!). the drawback is for slower-cpu's or graphic hardware the rasterization time is dependent on the amount of triangles. anyway, i have to run..
example: X Y Z
0 0 0 - moves(-1,-1,-1)
0 0 1 - moves(-1,-1,1)
0 1 0 - moves(-1,1,-1)
etc...
if this works, this would be very fast for many points. one would have 20 points in a 64-bit register. i wonder if these bits also can represent normals at the same time (which would be great!). the drawback is for slower-cpu's or graphic hardware the rasterization time is dependent on the amount of triangles. anyway, i have to run..
We used Marching Tetrahedrons in Haumea, though not in realtime.
One advantage of MT compared to MC is that it is simpler to implement - it has much fewer cases and requires no big tables, making it ideal for 4k intros.
See also this thread.
One advantage of MT compared to MC is that it is simpler to implement - it has much fewer cases and requires no big tables, making it ideal for 4k intros.
See also this thread.
Quote:
One advantage of MT compared to MC is that it is simpler to implement - it has much fewer cases and requires no big tables, making it ideal for 4k intros.
Does that really make that much of a difference?
In my implementation of marching cubes, the base cases are encoded in less than 200 bytes estimated. Then a few simple loops expand that to all possible cases.
Things should compress quite nicely as well, since it's all in the range of 0-12.
(Mine is not a size-optimized implementation, I just thought it was sloppy to hardcode the full tables when you can generate it at startup in no time at all).
Blueberry: Nice. Fewer cases and simplicity is what I need for this idea.
Scali: Actually, the compression-ratio is not actually the key point here, but to proceduraly generate the isosurfaces in the simplest way possible. Also, check this out:
Quote from Marching Tetrahedra: "In fact, it has been proven that any geometric cell can be deconstructed into a series of tetrahedra, making marching tetrahedra a generic solution for isosurface extraction on all grid types."
In my last post, what I meant in words is to generate complexity out of simple discrete algorithms; that is reconstruct the vertex-data on the grid. Intuitively I believe fewer cases are better for exactly this approach.
Scali: Actually, the compression-ratio is not actually the key point here, but to proceduraly generate the isosurfaces in the simplest way possible. Also, check this out:
Quote from Marching Tetrahedra: "In fact, it has been proven that any geometric cell can be deconstructed into a series of tetrahedra, making marching tetrahedra a generic solution for isosurface extraction on all grid types."
In my last post, what I meant in words is to generate complexity out of simple discrete algorithms; that is reconstruct the vertex-data on the grid. Intuitively I believe fewer cases are better for exactly this approach.
Quote:
Scali: Actually, the compression-ratio is not actually the key point here, but to proceduraly generate the isosurfaces in the simplest way possible.
That was not my point.
MC is mostly table-driven, the actual code to generate the triangles is quite compact anyway. The number of cases mainly affect the size of the tables, not the actual code.
And since the tables can be generated from just a few hundred bytes of uncompressed seed-data, I was wondering if it really was that much of an issue for a 4k intro.
I mean, how many bytes can you really save?
Our whole Marching Tetrahedrons code - generating interpolated vertices and triangles from uniform grid values - is around 200 bytes compressed, including a tiny table.
I don't know how much the MC would be, but I would expect somewhat more, if you start out with using, say, 100 bytes compressed for the reduced table, and it also needs to include code for unfolding the table.
(I made a MC on Amiga 12 years ago, also from a reduced table of 215 bytes uncompressed (reduced by rotational symmetry) and the code for that does seem significantly bigger, though it is difficult to compare fairly.)
I don't know how much the MC would be, but I would expect somewhat more, if you start out with using, say, 100 bytes compressed for the reduced table, and it also needs to include code for unfolding the table.
(I made a MC on Amiga 12 years ago, also from a reduced table of 215 bytes uncompressed (reduced by rotational symmetry) and the code for that does seem significantly bigger, though it is difficult to compare fairly.)
Yes, marching tetrahedrons will be smaller, but the way I look at it, the difference will be in the range of 100-200 bytes. If you really want to go all-out in a 4k, I suppose it makes sense. But it's just not as big a deal as it would be in the 1k intro that Kalms made for example (which is uncompressed).