Fragmentarium - an IDE for exploring 3D fractals and other systems on the GPU.

[Pauldelbrot]

TL;DR: Fragmentarium crashes at least some of the times when the viewpoint is placed inside a "twisted" Mandelbox, and too many indexed textures and/or a division by zero when the distance estimate is zero may be the culprit, but it may also be a library, OS, or video driver bug.

Long version:

A fairly brief (< 20 minutes) examination of 0.8.0 on Vista Home Premium 32-bit quickly revealed a pretty severe bug in ... some layer of the software stack.

Moving the camera sliders for a Mandelbox in such a manner as to hit the box produces a blank white pane when the box is not "twisted" (by changing the bottom rotation slider on the Mandelbox tab) -- acceptable enough behavior. If the box is "twisted", though, and you crash into the box, the entire screen goes blank black for several seconds and things like alt-tab, etc. fail to foreground something else. After the computer has been in this frightening state for several seconds (and assuming you haven't already hit the reboot button by then), the display comes back, accompanied by a "ding" and an error dialog saying the OpenGL library lost contact with the NVidia driver, or something like that (for some reason the awesome dudes who program these MSVC/etc. library error dialogs never seem to include copy and paste capability, or even a way for application programmers to add it), and that there's an error code of 8, whatever the hell that means. Regardless, okaying it exits Fragmentarium, and it fails to provide any other options.

So, basically, moving the viewpoint inside a "twisted" Mandelbox crashes Fragmentarium, and in a manner that makes it look at first like the entire computer crashed. Not good, particularly since it's quite easy for this to happen accidentally while trying to set up an interesting view.

Debugging this is likely to be difficult, unless it's performing a generally-invalid OpenGL operation, as the application code sits on a Qt library that sits, on Windows, on an MSVC library whose graphics-related bits sit on an OpenGL implementation that sits on a Windows HAL that sits on a hardware-dependent video driver, and the problem lies somewhere down in this chain. The error message I saw was apparently NVidia specific, in particular -- not that that means the bug is a specific incompatibility with GeForce cards. It could just be that the error message, or more generally the kind of undefined behavior being triggered, would vary with other cards, and possibly also with other operating systems. But the behavior observed (affecting the display, however temporarily, of other applications and not just Fragmentarium) points to something going seriously wrong at a pretty deep level, where it's quite plausible that the same bug on other system configurations could trigger anything from blue screens, lockups, and reboots to more ordinary application hangs and crashes as well as this sort of funny in-between crash. So, I can envision the bug being almost anywhere; it could be anything from Fragmentarium doing something wrong to a bug in any of the layers beneath it that it merely provokes and that it would have to try to work around, down to and including a hardware bug with the specific graphics card I was using. How readily it, or something similar, reproduces might narrow things down -- for example, if nothing of the sort ever happens except on Windows machines, it's probably in the Windows-specific libraries, the HAL, or the Windows drivers for video cards. Likewise it might be NVidia-specific, pointing to their drivers or hardware as the culprit, or some version of it may afflict most system configurations, pointing to Fragmentarium itself doing something that the OpenGL standard says is a no-no or else the cross-platform Qt and (perhaps) GL libraries containing the error. I don't have access to other systems to test it on, at least for now. In the near future I may have opportunities to see what, if anything, happens under similar circumstances with a Windows 7 Home Premium 64-bit/ATI combination, and also with Windows 7 Home Premium 64-bit and a second NVidia card. If the bug is confined to either NVidia hardware or Vista this fact will be discernible, but not whether it's confined to Windows. Reports from other users will probably be necessary to begin to guess where precisely the problem lies, and/or reproducing it with debugging tools attached.

Cursory googling of elements of the NVidia-specific error message suggests that it can have three causes: 1. Overheating GPU; 2. Failing GPU; 3. Applications using higher RenderMaxTextureIndex than the card supports. The first two wouldn't be specific to a single 3D application, whereas I'm not seeing anything similar in any other 3D applications (e.g., games). So perhaps Fragmentarium is trying to use more indexed textures than the driver reports the card as supporting (Fragmentarium bug) or the driver is misreporting (unfortunately, there is at least one documented instance of a driver reporting a card as supporting 32 that supported only 16). This also allows the bug to be in Fragmentarium, in the driver, and maybe somewhere in the stack between them, but at least it suggests looking at any use of indexed textures by Fragmentarium, though my understanding of these things makes me doubt that pure pixel-shader rendering would need any? Another online discussion suggests that erroneous shader calculations such as array overruns or divisions by zero could cause it -- a division by zero in shader code while the camera is embedded in the Mandelbox and the distance estimate is zero seems like a particularly plausible candidate.

[Syntopia]

Hi Pauldebrot,

The most likely explanation is that the GPU code takes too long to execute and times out. For the default systems in Fragmentarium, this is only likely to happen on older GPU's (unless AA is turned on).

On Windows, there is a GPU Watchdog timer which monitors for how long a single task (in our case a frame rendering) runs. If a task takes more than 2-5 seconds (this seems to depend on drivers and OS settings), Windows will kill the graphics driver and restore it (resulting in unresponsive, possible black, display for another 5-10 seconds).

This restoration process also kills the Fragmentarium process and result in the errors you describe (see the attached screenshot). This is the expected and correct behaviour. It saves you from rebooting the machine to recover GPU access.

It is a fairly common thing when dealing with GPU code - I've experienced it a lot in Adobe's Pixel Bender, and it also applies to e.g. CUDA.

It is possible to turn off, or adjust the GPU timeout, but I wouldn't recommend it unless you know what you are doing - since you might be able to lock the machine completely by doing so. Here is how, anyway: http://www.flickr.com/photos/syntopia/4575335808/

It is possible to render in smaller units (tiles), this is done in Fragmentarium when rendering high-resolution images, but as far as I know, nothing can really guard you against an infinite loop.

[hobold]

as far as I know, nothing can really guard you against an infinite loop.

Useless trivia: in some strict mathematical sense, it is impossible to automatically determine if some arbitrary program is making progress towards termination, or if it will run forever. This is the "halting problem", very closely related to the purely mathematical "incompleteness theorem". Wikipedia will probably have more details if anyone is interested.

But in practice, the most common infinite loops are inherently trivial enough to be detected (as they do not change relevant state between iterations), or you simply use watchdog timers to get a good enough approximation of the impossible thing that you cannot have.

[Pauldelbrot]

On real-world, finite hardware, all infinite loops that don't involve I/O can in principle be detected by using a cycle detection algorithm. (It would have to run in another thread and have privileged access to everything -- the first process's address space, saved registers and stack, etc.) I/O-containing loops can usually be broken out of by a suitable changed input, unless they contain only output (10 PRINT "HELLO, WORLD"; 20 GOTO 10) or won't accept *user* input. Regardless, they interrupt to perform I/O which gives the OS and high-priority processes like Task Manager opportunities to become responsive and let the user kill them, even if the looping process itself has a high priority. Given that many discrete-cycle detection algorithms need only one saved image to compare against periodically, and given that OSes save such images anyway when they page tasks to disk and back into main memory, it's not infeasible in principle for an OS to implement one as part of its job management/scheduler subsystem, though I know of none that currently does so.

On the original topic, the video hardware I have can run Quake 4, Doom 3, and HL2 without poor framerates, so I should hope it suffices for Fragmentarium. How is the tiling enabled, if that's a way to avoid triggering the bug?

[Syntopia]

Well, static code analysis will only detect the trivial cases, and dynamic state cycle detection would be very inefficient on a GPU. The only reasonable solution would be to introduce a preemptive multi-tasking model on the GPU's, where running kernels could be forced to yield time to other kernels.

Pre-emptive multitasking is supported by the Windows WDDM driver model, but AFAIK no graphic cards support it. The Fermi architecture supposedly supports fast context switching, but it is uses only cooperative multi-tasking with the newest drivers. This will probably change at some point.

On the original topic, the video hardware I have can run Quake 4, Doom 3, and HL2 without poor framerates, so I should hope it suffices for Fragmentarium. How is the tiling enabled, if that's a way to avoid triggering the bug?

Rendering a frame in Fragmentarium can be much more expensive than a frame in Quake. It all depends on the fractal and settings, e.g. the max number of raysteps, the iteration count, the AA settings, and so on.

I've used Fragmentarium on a (laptop) Geforce 310M, where it is quite slow, but usable, on a 9800GTX, which works nicely, and on a 570GTX which works great.

Tile rendering is only possible when doing high-resolution renders (the 'Render' menu), but you may adjust the preview slider to render at lower resolution.

[Syntopia]

There is a new version of Fragmentarium out (version 0.9.0).

More info available here:
http://blog.hvidtfeldts.net/index.php/2011/12/fragmentarium-0-9-released/

[knighty]

Yay! A new version!
The new features are awesome!
 

[Syntopia]

Thanks, Knighy. And your new fragment is great. The brings Fragmentarium closer to Structure Synth - but the DE approach yields a lot of new potential. Example picture:

[Syntopia]

Btw, there is now a small FAQ for Fragmentarium:
http://blog.hvidtfeldts.net/index.php/2011/12/fragmentarium-faq/

I'm also upgrading the rendering pipeline in Fragmentarium, so that you can render progressively to accumulated float buffers (HDR). This makes it possible to do distributed raytracing, meaning DOF, bloom, soft shadows (for lights with finite extent), high-quality AA and better AO, is now possible. Here are some example images:
http://blog.hvidtfeldts.net/index.php/2012/01/pseudo-kleinian-blue/

[bib]

@Syntopia, I hadn't realized that you were the author of both Structure Synth and Fragmentarium. You're a real genius! I have tried both programs for less than an hour each, and although a few clicks where enough to get some nice images, I felt a bit lost. Too much coding everywhere! For stupid users like me, Mandelbulb3D is less scary Although I've been coding a little bit when I was younger, now that belongs to the past. So I absolutely need to find the time to play with these jewels, especially when I see Kali's latest images. WOW. Having spent sooo much time on Mandelbulb3D I feel like a dinosaur falling way behind

The digital art community owes you so much, I don't have enough words to thank you!

Best of luck in 2012!

@Knighty: funny, you tried to replicate the image I did in M3D? Impressive!

[knighty]

@bib: yes. thank you . When I like a rendering, I always try to figure out how it was done. Sometimes I succeed. 
Jessy's difs are finally some kind of KIFS instancing. I did similar work some time ago. This technique is even more powerful. In the above picture by syntopia, the instansiated object is a (1 iteration) menger sponge. So it's possible (in principle) to do difs that instansiate another difs and so on. Too bad it gives too symmetric shapes.

@syntipia: Thanks.
I guess it's possible to transform Structure synth objects to RIFS with instancing and use Hart's algorithm to raytrace them. It's also possible to use DE (Hepting's algorithms, but it's also possible to modify Hart's algorithm to give DE). unfortunately, both would be difficult to implement on GPU.
As pointed out by David Makin, Hart's algorithm is much faster than DE but the later should also be usable with non linear transformations (in principle at least).

That progressive rendring feature looks very promising. How much time did it took to render those (pretty) blue kleinians?

[DarkBeam]

Hey awesome people!

I implemented your "Dodecahedron" kifs, but I added more possibilities;

 // Snippet from Frag's script with my tweaks; (z is a vector with x,y,z)
 z *= Rot1;
 for (n2=0; n2<7; n2++) { // this works, the original formula for some reason used 9 cycles
 z-=2.0 * min(0.0, dot(z, n1)) * n1; // n1 = normalizedVec(phi-1,1/(phi-1), -1)
 if style=n2 { z *= Rot2; } // Rotating before the 'fold loop' is finished can be fun!
 flip3D(n1); // flip3d(x,y,z) = (y,z,x), easier way to cycle between the fold styles without additional vecs
 }

 z =+z*Scale - offset*(Scale-1.0);
 if style=7 { z *= Rot2; } // This is Fragmentarium's style.

Try it, it should be better for use instead of the default example.

Have a good time.

[tit_toinou]

This software is exactly what i needed. Thanks !

[Syntopia]

@bib: Thanks a lot for the comments. Btw, Fragmentarium did turn out to become more complex and difficult than I planned when I started out. On the other hand, Mandelbulb3D and Mandelbulber are already so powerful and polished, that I think Fragmentarium makes most sense for people who wants to experiment with code and new formulas.

@knighty: I can see I have some catching up to do! I don't know what RIFS are, nor what the new Mandelbulb3D d.IFS do, or your mdifs.frag. Do you have any pointers? Which one of Hart's paper many papers describe this - is it the 'paradigm' one?

The blue kleinians were rendered using 60 frames (or rays/pixel). So they'd be 60x slower :-) On the other hand this is still only a few seconds on a good GPU.

@darkbeam: You are right - only 7 iterations are necessary! Your solution is elegant, but unfortunately swizzling the normal slows the shader by adding extra operations. Swizzeling z instead is ~13% faster  :-)

Code:

for (int j = 0; j < 7; j++) {
	z.yzx = z-2.0 * min(0.0, dot(z, n1)) * n1;
}

[DarkBeam]

Elegant? I am definitely making progress, for being a spaghetti coder!
Well, the fold takeoff can edventually affect the rotated stuffs, so be careful about that optimization.
Anyway, the option of a rotation that may break the folding regularity may be cool to experiment somewhere.