Friday, November 16, 2007
3d fractal object generation process
These objects, as I said previously,
have very small details, so the polygonization grid should be very fine.
The result is that in order to get sufficient detail, a huge number of triangles is generated, even for regions where the surface is locally flat, and in theory a much larger grid could have been used.
I have not found any way of implementing adaptive refinement, so I am left with billions (literally) of triangles. In addition to take a large disk space (1 triangle equals 3 vertices, 1 vertex equals 3 floating point values, this makes 36 bytes per triangle), this amount of triangles is far beyond what is possible to display interactively (I think current limit of graphics hardware is about 10 million tris/second).
The solution is called decimation . It simply consists of generating an object with less triangles, taking into account the fact that some areas are almost flat, and thus require less triangles. Of course this usually comes with variable loss of original shape, but it maybe not noticeable, depending on the quality of the implementation.
Over the years I have found many implementations of meshes decimation, here is a survey of common ones.
The real key point for me is that the decimation implementation must be Out Of Core, that is it must work on data (much) larger than available memory. Not all implementation support this, but I found a little Gem, cluspartred by Heiko Lippmann.
Heiko has been kind enough to send me the Linux executable of his program, and I must say it works very well for my purposes.
Starting from a 1 billion triangle mesh, it can generate a 5 million triangle mesh that is almost perfect looking and usable (displayable) on standard machines.
It creates partitions on disk and loads on demand these partitions to decimate them in memory, handling all the details of contiguous partitions. On a recent machine (Xeon 3.2Ghz, see below full specs), this process only takes a few hours.
I then convert the resulting triangle soup to a custom format that I wrote a viewer for, and eventually convert it to the STL format suitable for 3d Printers.
The generation of the initial triangle soup is multi threaded using Intels'TBB parallel_for, and is very efficient, using a grid size of 12000x9671x8417 only takes a few hours on a 8 core 3.2Ghz 2x6 MB cache 16 GB memory Xeon machine (cpuinfo x5482, not a bad machine...)
have very small details, so the polygonization grid should be very fine.
The result is that in order to get sufficient detail, a huge number of triangles is generated, even for regions where the surface is locally flat, and in theory a much larger grid could have been used.
I have not found any way of implementing adaptive refinement, so I am left with billions (literally) of triangles. In addition to take a large disk space (1 triangle equals 3 vertices, 1 vertex equals 3 floating point values, this makes 36 bytes per triangle), this amount of triangles is far beyond what is possible to display interactively (I think current limit of graphics hardware is about 10 million tris/second).
The solution is called decimation . It simply consists of generating an object with less triangles, taking into account the fact that some areas are almost flat, and thus require less triangles. Of course this usually comes with variable loss of original shape, but it maybe not noticeable, depending on the quality of the implementation.
Over the years I have found many implementations of meshes decimation, here is a survey of common ones.
The real key point for me is that the decimation implementation must be Out Of Core, that is it must work on data (much) larger than available memory. Not all implementation support this, but I found a little Gem, cluspartred by Heiko Lippmann.
Heiko has been kind enough to send me the Linux executable of his program, and I must say it works very well for my purposes.
Starting from a 1 billion triangle mesh, it can generate a 5 million triangle mesh that is almost perfect looking and usable (displayable) on standard machines.
It creates partitions on disk and loads on demand these partitions to decimate them in memory, handling all the details of contiguous partitions. On a recent machine (Xeon 3.2Ghz, see below full specs), this process only takes a few hours.
I then convert the resulting triangle soup to a custom format that I wrote a viewer for, and eventually convert it to the STL format suitable for 3d Printers.
The generation of the initial triangle soup is multi threaded using Intels'TBB parallel_for, and is very efficient, using a grid size of 12000x9671x8417 only takes a few hours on a 8 core 3.2Ghz 2x6 MB cache 16 GB memory Xeon machine (cpuinfo x5482, not a bad machine...)
Thursday, November 15, 2007
More 3d fractal objects
I have ordered and received another object.
These 3d printed objects are the result of some heavy computation.
The basic idea is that the object is an isosurface, where a mathematical function is used to compute values. An introduction to isosurfaces can be found at Hyperfun.
You can find information on the type of 3d fractals used for my objects at Paul Bourke's
While quaternion fractal images have been around for a long time because they are very well suited to the Ray Tracing method, and have been available in the PovRay raytracer for a while now (Hi Skal!), it is much harder to get a polygonal representation of these objects.
A common method to obtain 3d triangles for this kind of objects is called
It consists of computing values on a grid in 3d space, then determining triangles for a given unit cell. Once again Paul Bourke describes this very well.
The problem is that fractal objects have very small details, so the grid should be very fine, requiring huge memory requirement, both for computation and storage.
As an example let's look at an object that is polygonized with a coarse grid (150x120x105). The result is not very nice looking, but already has more than 160 000 triangles.
Going to a grid of 500x402x350 makes the object nicer but gives 1 834 396 triangles, so that we are starting to reach the limits what most graphics cards are capable of.
Refining the grid further would only give minimal aesthetic gains, while increasing storage and lowering framerate to an unsusable level. So this is not the way to go.
Next post will unveil the method I use to get nice looking objects as this one, that has less than 5 million triangles (this one can be printed on a 3d printer):
These 3d printed objects are the result of some heavy computation.
The basic idea is that the object is an isosurface, where a mathematical function is used to compute values. An introduction to isosurfaces can be found at Hyperfun.
You can find information on the type of 3d fractals used for my objects at Paul Bourke's
While quaternion fractal images have been around for a long time because they are very well suited to the Ray Tracing method, and have been available in the PovRay raytracer for a while now (Hi Skal!), it is much harder to get a polygonal representation of these objects.
A common method to obtain 3d triangles for this kind of objects is called
Polygonization of scalar fields.
It consists of computing values on a grid in 3d space, then determining triangles for a given unit cell. Once again Paul Bourke describes this very well.
The problem is that fractal objects have very small details, so the grid should be very fine, requiring huge memory requirement, both for computation and storage.
As an example let's look at an object that is polygonized with a coarse grid (150x120x105). The result is not very nice looking, but already has more than 160 000 triangles.
Going to a grid of 500x402x350 makes the object nicer but gives 1 834 396 triangles, so that we are starting to reach the limits what most graphics cards are capable of.
Refining the grid further would only give minimal aesthetic gains, while increasing storage and lowering framerate to an unsusable level. So this is not the way to go.
Next post will unveil the method I use to get nice looking objects as this one, that has less than 5 million triangles (this one can be printed on a 3d printer):
Subscribe to:
Posts (Atom)