Knots and Polyhedra

Over at Fractal Forums, DarkBeam came up with a Distance Estimator for a trefoil knot in this thread. Here are a few samples, created using the new ‘soft’ raytracer, I’m working on in Fragmentarium:

These kinds of knots are easy to describe by a parametrized curve, but making a distance estimator for them is impressive – I wouldn’t have guessed it was possible at all.

It is also possible to create several variations:

In the same thread, Knighty came up with an impressive figure-8 knot distance estimator:

In another thread at Fractal Forums, Knighty also published an interesting technique (“Fold and Cuts”) for creating a large variety of distance estimated polyhedra:

(If you wonder about the materials, I’ve added some 3D Perlin noise to the distance estimate – this is simple way to creature a structural texture, and it creates true displacements, not just surface normal perturbations).

The threads linked to above contains Fragmentarium scripts with the relevant distance estimators.

Creating a Raytracer for Structure Synth (Part II)

When I decided to implement the raytracer in Structure Synth, I figured it would be an easy task – after all, it should be quite simple to trace rays from a camera and check if they intersect the geometry in the scene.

And it turned out, that it actually is quite simple – but it did not produce very convincing pictures. The Phong-based lighting and hard shadows are really not much better than what you can achieve in OpenGL (although the spheres are rounder). So I figured out that what I wanted was some softer qualities to the images. In particular, I have always liked the Ambient Occlusion and Depth-of-field in Sunflow. One way to achieve this is by shooting a lot of rays for each pixel (so-called distributed raytracing). But this is obviously slow.

So I decided to try to choose a smaller subset of samples for estimating the ambient occlusion, and then do some intelligent interpolation between these points in screen space. The way I did this was to create several screen buffers (depth, object hit, normal) and then sample at regions with high variations in these buffers (for instance at every object boundary). Then followed the non-trivial task of interpolating between the sampled pixels (which were not uniformly distributed). I had an idea that I could solve this by relaxation (essentially iterative smoothing of the AO screen buffer, while keeping the chosen samples fixed) – the same way the Laplace equation can be numerically solved.

While this worked, it had a number of drawbacks: choosing the condition for where to sample was tricky, the smoothing required many steps to converge, and the approach could not be easily multi-threaded. But the worst problem was that it was difficult to combine with other stuff, such as anti-alias and depth-of-field calculations, so artifacts would show up in the final image.

I also played around with screen based depth-of-field. Again I thought it would be easy to apply a Gaussian blur based on the z-buffer depth (of course you have to prevent background objects from blurring the foreground, which complicates things a bit). But once again, it turned out that creating a Gaussian filter for each particular depth actually gets quite slow. Of course you can bin the depths, and reuse the Gaussian filters from a cache, but this approach got complicated, and the images still displayed artifacts. And a screen based method will always have limitations: for instance, the blur from an object hidden behind another object will never be visible, because the object is not part of the screen buffers.

So in the end, I ended up discarding all the hacks, and settled for the much more satisfying solution of simply using a lot of rays for each pixel.

This may sound very slow: after all you need multiple rays for anti-alias, multiple rays for depth-of-field, multiple rays for ambient occlusion, for reflections, and so forth, which means you might end up with a combinatorial explosion of rays per pixel. But in practice there is a nice shortcut: instead of trying all combinations, just choose some random samples from all the possible combinations.

This works remarkably well. You can simulate all these complex phenomena with a reasonably number of rays. And you can use more clever sampling strategies in order to reduce the noise (I use stratified sampling in Structure Synth). The only drawback is, that you need a bit of book-keeping to prepare your stratified samples (between threads) and ensure you don’t get coherence between the different dimensions you sample.

Another issue was how to accelerate the ray-object intersections. This is a crucial part of all raytracers: if you need to check your rays against every single object in the scene, the renders will be extremely slow – the rendering time will be proportional to the number of objects. On the other hand spatial acceleration structures are often able to render a scene in a time proportional to the logarithm of the number of objects.

For the raytracer in Structure Synth I chose to use a uniform grid (aka voxel stepping). This turned out to be a very bad choice. The uniform grid works very well, when the geometry is evenly distributed in the scene. But for recursive systems, objects in a scene often appear at very different scales, making the cells in the grid very unevenly populated.

Another example of this is, that I often include a ground plane in my Structure Synth scenes (by using a flat box, such as “{ s 1000 1000 0.1 } box”). But this will completely kill the performance of the uniform grid – most objects will end up in the same cell in the grid, and the acceleration structure gets useless. So in general, for generative systems with different scales, the use of a uniform grid is a bad choice.

Not that is a lot of stuff, that didn’t work out well. So what is working?

As of now the raytracer in Structure Synth provides a nice foundation for things to come. I’ve gotten the multi-threaded part set correctly up, which includes a system for coordinating stratified samples. Each thread have its own (partial) screen space buffer, which means I can do progressive rendering. This also makes it possible to implement more complex filtering (where the filtered samples may contribute to more than one pixel – in which case the raytracer is not embarrassingly parallel anymore).

What is missing?

Materials. As of now there is only very limited control of materials. And things like transparency doesn’t work very well.

Filtering. As I mentioned above, the multi-threaded renderer supports working with filters, but I haven’t included any filters in the latest release. My first experiments (with a Gaussian filter) were not particularly successful.

Lighting. As of now the only option is a single, white, point-like light source casting hard shadows. This rarely produce nice pictures.

In the next post I’ll talk a bit about what I’m planning for future versions of the raytracers.

Structure Synth 1.5.0 (Hinxton) Released

It has been more than a year since the last release of Structure Synth, but now a new version is finally ready.

The biggest additions are the new raytracer and the scripting interface for animations. The raytracer is not an attempt to create a feature complete renderer, but it makes it possible to create images in a quality acceptable for printing without the complexity of setting up a scene in a conventional raytracer.

New features:

Minor updates:

  • Added support for preprocessor generated random numbers (uniform distributed).

  • Added ‘show coordinate system’ option.
  • Added ‘Autosave Eisenscript’ option to the Template Export Dialog. The autosaved script includes the random seed and camera settings.
  • Context menu with command help in editor window.
  • Proper sorting of transparent OpenGL objects.
  • Added a patch by François Beaune to support Appleseed.
  • GUI Refactoring.

Binaries for Windows (XP, Vista, and 7) and Mac OS X (10.4 and later, universal app). Linux is source only.

As something new, there is now an installer for Windows. It is still possible to just unzip the archived executable, but the Windows installer offers file associations for EisenScript files.

Comments

The raytracer and JavaScript interface are described in more details in the blog posts linked to above.

The OBJ exporter is simpe to use: Choose ‘Export | OBJ Export…’ from the menu. Since the OBJ format does not support spheres, these must be polygonized before export: it is possible to adjust the resolution for this. OBJ does not directly support colors either, so I’ve made it possible to group the OBJ output into sections according to either color or tags (or both). The group and material will be named after the OpenGL color, e.g.


g #f1ffe3
usemtl #f1ffe3
v 8.27049 2.4216 7.09626
...

Another new feature which probably requires a bit of explanation is the preprocessor generated random numbers. They can be used using the following syntax:


10 * { x 3 } 1 * { s random[1,3] } box

The above fragment will produce ten boxes, with a random size between 1 and 3. But notice that each box will have the same size: the ‘random[1,3]‘ is substituted at compile-time, not run-time.

I’ve had several request for some way to produce random variation each time a rule is called, but this would require rather large changes to Structure Synth, since the EisenScript program is compiled into a binary structure at compile time, and I would essentially need to turn the builder into a parser to accomodate this (which would be slow).

Well, that’s about it.

Download instructions at:
http://structuresynth.sourceforge.net/download.php

For more information see:
http://structuresynth.sourceforge.net/

Scripting in Structure Synth

I’ve added a JavaScript interface to Structure Synth. This makes it possible to automate and script animations from within Structure Synth. Here is an example:



(Image links to YouTube video)

The JavaScript interface will be part of the next version of Structure Synth (which is almost complete), but it is possible to try out the new features right now, by checking out the sources from the Subversion repository.

The rest of this post shows how to use the JavaScript interface.

Continue reading

Assorted Links

Pixel Bender 3D

Adobe has announced Pixel Bender 3D:


If I understand it correctly, it is a new API for Flash, and not as such a direct extension of the Pixel Bender Toolkit. So what does it do?

As far as I can tell, it is simply a way to write vertex and fragment shader for Flash. While this is certainly nice, I think Adobe is playing catchup with HTML5 here – many browsers already support custom shaders through WebGL (in their development builds, at least). Or compare it to a modern 3D browser plugin such as Unity, with deferred lightning, depth-of-field, and occlusion culling…

And do we really need another shader language dialect?

Flash raytracer

Kris Temmerman (Neuro Productions) has created a raytracer in Flash, complete with ambient occlusion and depth-of-field:

Kris has also produced several other impressive works in Flash:

Chaos Constructions

Quite and Orange won the 4K demo at Chaos Constructions 2010 with the very impressive ‘CDAK’ demo:

(Link at Pouet, including executable).

Ex-Silico Fractals

This YouTube video shows how to produce fractals without a computer. I’ve seen video feedback before, but this is a clever setup using multiple projectors to create iterated function systems.


Vimeo Motion Graphics Award

‘Triangle’ by Onur Senturk won the Vimeo Motion Graphics Award. The specular black material looks good. Wonder if I could create something similar in Structure Synth’s internal raytracer?

Creating a Raytracer for Structure Synth

Updated november 17th, 2011

Structure Synth has quite flexible support for exporting geometry to third-party raytracers, but even though I’ve tried to make it as simple as possible, the Template Export system can be difficult to use. It requires knowledge of the scene description format used by the target raytracer, and of the XML format used by the templates in Structure Synth. Besides that, exporting and importing can be slow when dealing with complicated geometry.

So I decided to implement a simple raytracer inside Structure Synth. I probably could have integrated some existing open-source renderer, but I wanted to have a go at this myself. The design goal was to create something reasonably fast, aiming for interesting, rather than natural, results.

The first version of the raytracer is available now in SVN, and will be part of the next Structure Synth release.

How to use the raytracer

The raytracer has a few settings which can be controlled by issuing ‘set’ commands in the EisenScript.

The following is a list of commands with their default values given as argument:

set raytracer::light [0.2,0.4,0.5]

Sets the position of a light in the scene. If a light source position is not specified, the default position is a light placed at the lower, left corner of the viewport. Notice that only a single light source is possible as of now. This light source controls the specular and diffuse lightning, and the hard shadow positions. The point light source model will very likely disappear in future versions of Structure Synth – I’d prefer environment lightning or something else that is easier to setup and use.

set raytracer::shadows true

This allows you to toggle hard shadows on or off. The shadow positions are determined by the light source position above.


Rendering without and with anti-alias enabled

set raytracer::samples 6

This sets the number of samples per pixel. Notice the actual number of samples is the square of this argument, i.e. a value of 2 means 2×2 camera rays will be traced for each pixel. The default value is 6×6 samples for ‘Raytrace (in Window)’ and 8×8 samples for ‘Raytrace (Final)’. This may sound like a lot of samples per pixel, but the number of samples also control the quality of the depth-of-field or ambient occlusion rendering. If the image appears noisy, increase the sample count.


To the left, a render with a single Phong light source. To the right, the same picture using ambient occlusion

set raytracer::ambient-occlusion-samples 1

Ambient occlusion is a Global Illumination technique for calculating soft shadows based on geometry alone. Per default the number of samples is set to 1. This may not sound like a lot, but each pixel will be sampled multiple times courtesy of the ‘raytracer::samples’ count – this makes sense because the ‘raytracer::samples’ will be used to sample both the lens model (for anti-alias and depth-of-field) and the ambient occlusion. And when I get a chance to implement some better shader materials, the samples can also be used there as well. Notice, that as above, the number refers to samples per dimensions. Example: if ‘raytracer::ambient-occlusion-samples = 3′ and ‘raytracer::samples = 2′, a total of 3x3x2x2=36 samples will be used per pixel.


Depth-of-Field example

set raytracer::dof [0.23,0.2]

Enables Depth-Of-Field calculations. The first parameter determines the distance to the focal plane, in terms of the viewport coordinates. It is always a number between 0 and 1. The second parameter determines how blurred objects away from the focal plane appear. Higher values correspond to more blurred foregrounds and backgrounds.

Hint: in order to get the viewport plane distance to a given object, right-click the OpenGL view, and ‘Toggle 3D Object Information’. This makes it possible to fit the focal plane exactly.

set raytracer::size [0x0]

Sets the size of the output window. If the size is 0×0 (the default choice), the output will match the OpenGL window size. If only one dimension is specified, e.g. ‘set raytracer::size [0x600]‘, the missing dimension will be calculated such that the aspect ratio of the OpenGL window will be matched. Be careful when specifying both dimensions: the aspect ratio may be different.

set raytracer::max-threads 0

This determines how many threads, Structure Synth will use during the rendering. The default value of 0, means the system will suggest an ideal number of threads. For a dual-core processor with hyper-threading, this means four threads will be used. Lower the number of threads, if you want to use the computer for other tasks, and it is unresponsive.

set raytracer::voxel-steps 30

This determines the resolution of the uniform grid used to accelerate ray intersections. Per default a simple heuristic is used to control the resolution based on the number of objects. A value of 30 means that a grid with 30x30x30 cells will be used. The uniform grid used by the raytracer is not very efficient for non-uniform structure, and will likely be replaced in a future version of Structure Synth.

set raytracer::max-depth 5

This is the maximum recursion depth of the raytracer (for transparent and reflective materials).

Finally two material settings are available:

set raytracer::reflection 0.0

Simple reflection. A value between 0 and 1.

set raytracer::phong [0.6,0.6,0.3]

The first number determines the ambient lightning, the second the diffuse, and the third the specular lightning. Diffuse and specular lightning depends on the location of the light source.

It is also possible to apply the materials to individual primitives in Structure Synth directly. This is done by tagging the objects.

Consider the following EisenScript fragment:

Rule R1 {
   { x 1 } sphere::mymaterial
   R1
}

The sphere above now belongs to the ‘mymaterial’ class, and its material settings may be set using the following syntax:

set raytracer::mymaterial::reflection 0.0
set raytracer::mymaterial::phong [0.6,0.6,0.0]

An important tip: writing these long parameter setting names is tedious and error-prone. But I’ve added a list with the most used EisenScript and Raytracer commands to the context menu in Structure Synth editor window. Just right-click and select a command.