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...)

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

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):

3d Fractals for real

For a while, I have been interested in 3d fractals.
Recent 3d printing technology development has allowed me to get some of these printed for real, and for relatively cheap.

Getting a file suitable to a 3d printer is a very complicated process.

Here is a picture of me at my home desk holding a SLS object of size 15 cm, printed by 3DProd for 269 euros.

On the desk is an older smaller object (the same that is on the screen), printed on a ZCorp printer.

Integrating your own gigapixel images in Google Earth

I have found that the processing necessary to integrate very large images in Google Earth 4.2 is, if not easy, possible.

All you need is create a version of your image padded to a power of two in both dimensions, then scale by 2 recursively until image fits in a 256x256 pixels tile.

Then you have to subdivide each image in single tiles.

Finally you have to create a suitable KML file.

The documentation for this feature can be found here.

I have some scripts that automate the process for a given TIFF image.

Google Maps like nagivation of images

Viewing images on the Web is not always very user friendly, mainly because Web Browsers do not allow arbitrary zooming and panning in images.

A more and more common way to solve this problem is the use of JavaScript with custom nagigation of images, using concepts such as pyramidal organization of images.

A well known implementation of this concept is Google Maps.

While not directly related to very large images, because zooming does not refine information (images are not so-called very large), an interesting work has been conducted by Siva Dirisala, on a variety of Nasa images.

By using more and more of these ideas, we should expect more and more very large images (and more generally all images) to be really in-place zoomable, a nice addition to content of Web pages.