About

XRT is a raytracing based programmable rendering system for photo-realistic image synthesis built around a plug-in architecture design.

Blog

Geek gift or Greek gift?

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

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 below¹.

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 [x_min, x_max, y_min, y_max, z_min, z_max] 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."

ReturnMiss	Exit, reporting no intersection
ReturnAIfCloser	Return the intersection with A if it is closer
ReturnAIfFarther	Return the intersection with A if it is farther
ReturnA	Always return the intersection with A
ReturnBIfCloser	Return the intersection with B if it is closer
ReturnBIfFarther	Return the intersection with B if it is farther
ReturnB	Always return the intersection with B
FlipB	If returning an intersection with B, flip its normal
AdvanceAAndLoop	Continue with the next intersection with A
AdvanceBAndLoop	Continue with the next intersection with B
AdvanceAAndLoopIfCloser	Continue with the next intersection with A if the current intersection with A is closer
AdvanceBAndLoopIfCloser	Continue with the next intersection with B if the current intersection with B is closer

Union	Enter B	Exit B	Miss B
Enter A	ReturnAIfCloser, ReturnBIfCloser	ReturnBIfCloser, AdvanceAAndLoop	ReturnA
Exit A	ReturnAIfCloser, AdvanceBAndLoop	ReturnAIfFarther, ReturnBIfFarther	ReturnA
Miss A	ReturnB	ReturnB	ReturnMiss

Difference	Enter B	Exit B	Miss B
Enter A	ReturnAIfCloser, AdvanceBAndLoop	AdvanceAAndLoopIfCloser, AdvanceBAndLoopIfCloser	ReturnA
Exit A	ReturnAIfCloser, ReturnBIfCloser, FlipB	ReturnBIfCloser, FlipB, AdvanceAAndLoop	ReturnA
Miss A	ReturnMiss	ReturnMiss	ReturnMiss

Intersection	Enter B	Exit B	Miss B
Enter A	AdvanceAAndLoopIfCloser, AdvanceBAndLoopIfCloser	ReturnAIfCloser, AdvanceBAndLoop	ReturnMiss
Exit A	ReturnBIfCloser, AdvanceAAndLoop	ReturnAIfCloser, ReturnBIfCloser	ReturnMiss
Miss A	ReturnMiss	ReturnMiss	ReturnMiss

Programmable photorealistic rendering

Posts by date

Posts by tags

Watchers

Add a new post

About

Blog

Intersection algorithm

Usage

Optimizing render times

Requirements

Algorithm outline

List of actions

Action tables

State machine pseudo-code

Other interesting sites