Geek gift or Greek gift?

Posted: 1283004403|%e %B %Y, %H:%M|agohover
Tags: implicit surface

chmutov97.jpg

Most renderers deal only with a very limited subset of primitives: points, curves, polygons, nurbs, subdivision surfaces. Beyond this tiny set, there exists an almost ignored mathematical realm: implicit surfaces.

An implicit surface in 3D is defined as the set of solutions of an equation $f(x,y,z) = 0$ where $f$ can be any algebraic or non algebraic expression. It is called implicit because you cannot compute explicitely points on the surface: you have to solve for the equation first. The fact that $f$ can be pretty much anything you want lets you guess the variety of shapes that can be explored. As you can see in the implicit surfaces section of the gallery, most of them are of little practical use but have real aesthetic value.

Intersection algorithm

XRT implicit surface plugin implementation is based on a publication by Knoll et al. [1] where the inclusion property of interval arithmetic is used to define an efficient rejection algorithm briefly summarized below1.

A fundamental theorem of interval arithmetic states that, for any function f defined by an arithmetical expression, the corresponding interval evaluation function F is an inclusion function of f. In other words, if you define X, Y, Z as three intervals containing respectively the bounding values for x, y, z and evaluate $f(X, Y, Z)$ using interval arithmetic, the resulting interval is guaranteed to contain all possible values of $f(x, y, z)$ for any combination of (x, y, z) within the bounding box defined by (X, Y, Z). Using bounding boxes defined by ray segments and a recursive bisection algorithm (a binary search), it is possible to compute an intersection:

  • if a interval evaluation does not contain 0, the input ray segment is discarded.
  • if it does, the input ray segment is subdivided in two halves which are in turn evaluated.

When an interval evaluation contains 0 and the desired precision is reached, an intersection is returned. If no interval evaluation contains 0, there is no intersection.

XRT implementation is using GOAL for interval arithmetic computations.

Usage

Shape( "implicit") instantiates the "implicit" shape plugin and creates a new implicit surface. Accepted parameters are:

  • "string name": the name of the surface. This parameter is required.
  • "string function": the arithmetic expression in C code that defines the implicit surface. Using this C code, the "implicit" plugin generates a function plugin that provides a floating point evaluation function and an interval evaluation function. This parameter is required.
  • "float[6] bounds": the domain [xmin, xmax, ymin, ymax, zmin, zmax] where the surface is defined. This parameter is required because most implicit surfaces have an infinite domain. It also serves as a starting point for the bisection algorithm.
  • "float precision": the bisection algorithm stops recursing when an interval containing 0 with this width is met. This parameter is optional. The default value is 0.001 and is small enough for most functions.

Pyg format example:

Shape("implicit", "string name", "dingdong", 
    "string function", "sqr(x) + sqr(y) + z * (1 - sqr(z))", 
    "float[6] bounds", (-3, 3, -3, 3, -3, 3))

defines a implicit surface "dingdong" whose equation is $x^2 + y^2 + z(1 -z^2) = 0$ over the domain [ -3, 3 -3, 3 -3, 3].

This surface (and many more) is available in the implicit surfaces section of the gallery.

Optimizing render times

There are two main rules to decrease render times:

  • provide tight bounding boxes. Interval evaluation is a costly operation. Computing these evaluations for void space wastes CPU cycles.
  • provide optimized code for function evaluation. Minimizing the number of operations when evaluating a function interval is a key point which will yield huge savings:
    1. Try to factorize expressions.
    2. Remember that pow() is a very expensive operation and that sqr() or * are not.
    3. Use Horner's rule to rewrite polynomial expressions.

Let's provide two significant examples with Chmutov surfaces:

  • The Chmutov surface of order 6 is defined by the equation $T{_6}(x)+T{_6}(y)+T{_6}(z)=0$ where $T{_6}(x) = 32x^6-48x^4+18x^2-1$. Using rule 1, this expression can be rewritten as $T{_6}(x) = 2x^2(3-4x^2)^2-1$.
  • The Chmutov surface of order 7 is defined by the equation $T{_7}(x)+T{_7}(y)+T{_7}(z)+1=0$ where $T{_7}(x) = 64x^7-112x^5 +56x^3-7x$. Combining rules 2 and 3, this expression can be rewritten as $T{_7}(x) = x(x^2 (x^2(64x^2-112)+56)-7)$.

In both cases, rendering times with these optimized expressions are decreased by an order of magnitude over "naive" expressions.

Requirements

To generate a function plugin, you need to have a C++ compiler installed (see Downloads section for more details). However, the implicit shape plugin will not rebuild an already generated function plugin.

Bibliography
1. A. Knoll, Y. Hijazi, C. D. Hansen, I. Wald, and H. Hagen. "Interactive ray tracing of arbitrary implicit functions". In Proceedings of the 2007 Eurographics/IEEE Symposium on Interactive Ray Tracing, 2007.
2. Jag Mohan Singh and P. J. Narayanan, "Real-Time Ray-Tracing of Implicit Surfaces on the GPU". Tech Rep. IIIT/TR/2007/72. July 2007

Rendering implicit surfaces is a bit addictive. Internet ressources are so numerous that you end up filling your hard drive with pictures, rising your CPU to insane temperatures and depriving you from sleep without ever paying attention.

"Abandon all hope, ye who enter here."

Rate this post:

rating: 0+x

Comments: 0