Recursive Surface Algorithm (RSurf)

Overview

This algorithm approximates the zero level set of a function of three variables. That is, given a function from R^3->R, this algorithm computes the level set of zero associated to that function.

How Recursive Surface Works

The algorithm is implemented recursively. The basic step of RSurf is to subdivide a cube into eight smaller cubes. The initial cube is the bounding domain. The algorithm starts by replacing the initial cube and all that result until all the cubes have some minimum required depth. (A cube's depth is the depth it has in the octree that results from the cube replacement.) The algorithm continues by subdividing when both of the following two conditions are satisfied:

a cube has not reached the maximum allowed depth and,
the eight numbers that result from evaluating the function at the vertices of the cube do not have the same sign.

Once a cube has reached its maximum depth, a polygonal approximation to the surface is made by:

Finding an edge with a sign crossing. That is, the function is positive on one endpoints of the edge, and is negative at the other endpoint.
Tracing from that edge in order to determine which other cube edges are positive (both endpoints positive), negative (both endpoints negative) or must be split by the surface.

The polygon is then made from the edges which are intersected by the surface.

The panel that controls the recursive surface algorithm.

Controlling the algorithm from Pisces

The Pisces panel to the RSurf algorithm has 3 parameters:

MinDepth: All cubes are divided until they have at least minimum depth.
Example: If MinDepth is 3, then the original cube (the bounding domain) is divided into 8 cubes, each of the 8 into 8 cubes, and each of the resulting 64 into 8 cubes resulting in 512 cubes filling the original bounding domain.
Default Value: 3
MaxDepth: No cubes are allowed to have depth greater than the maximum depth.
Example: If the MaxDepth is 5, then if a cube has depth 5 it will not be subdivided any further, but rather a polygonal approximation to the surface will result instead.
Default Value: 5
Bisection_Epsilon: When bisecting the edge of a cube to find out where the surface crosses the edge, the bisection process stops on an interval of Bisection_Epsilon.
Default Value: 0.0001

Known Bugs

Sometimes a memory allocation error in RSurf will cause Pisces to crash. If you can systematically reproduce this crash, we would like that information so that we can fix the problem. Please send bug reports to software@geom.umn.edu.

Acknowledgements

The algorithm was implemented by Daniel B. Krech . The algorithm was inspired after working on implementing a brute force method for finding curves in the plane. The method involved dividing each "scan line" up into n segments, doing bisection on any segment where the functions sign changed and drawing the pixel that results from the bisection. This "scanning algorithm" was suggested by Auden Holme.

Next: Two-Parameter Continuation
Previous: User Interface

The Pisces Home Page