Constant Time Updateable Operations for Implicit Shape Modeling

Ergun Akleman and Jianer Chen

Introduction

In this paper, we introduce the concept of constant time updateability for the functional operations that can be used for constructing functions. We believe that constant time updateability will be important in the future for guaranteeing interactive modeling of implicit surfaces that are defined by functional construction of functions. We have developed several tests to determine if a functional operator is constant time updateable. In addition, we have introduced constant time updateable exact and approximate functional set operators.

Motivation

Figure 1. Implicit shapes defined by functions that are constructed by constant time updateable exact set operations. These shapes are obtained by set difference of a sphere with union of four spheres.

For the functions that are constructed by functional operations the complexity of a modeling function increases with the shape complexity. For complex shapes, therefore, function evaluation can be limiting factor. Even if the interactivity is achieved by simple shapes, interactivity cannot be guaranteed for complex shapes.

One of the time consuming process during modeling of implicit surfaces is polygonization of surfaces. Most straightforward approach for polygonization is the sampling of the implicit functions at the corners of discrete grids. We call the corners of discrete grids sampling points. Regardless of the structure of discrete grid, an important portion of the computation cost of polygonization comes from computation of function values on these sample points. This cost is simply multiplication of the number of sampling points, k, with the cost of computing function value at a given sample point.

In this paper, we assume that a discrete grid is used for polygonization, the number and the positions of the sample points do not change during construction and the computation of O(k) can be done in interactive speed. Under this assumption, the question we address in this paper is whether interactivity can be guaranteed during implicit shape construction.

Figure 2. Offset surfaces that are defined as a constant distance from the the shapes from Figure 1.

We observe that in order to guarantee interactivity, function evaluation in any given sample point must take constant time regardless of shape complexity. If the function evaluation time is not constant, it is not possible to guarantee interactivity. In other words, even if a shape modeling system can provide interactivity for simple shapes, when shapes become complicated, achieving interactivity can become impossible.

There are three main operations during construction process: change, add and delete a building block. If an operation is constant time updateable regardless of the number of building block functions and the tree structure, then change, add and delete operations can be done in constant time.

Methodology

In this paper, we introduce simple tests to identify whether a functional operation is constant time updateable. Our tests come from our theorems that an operation is constant time updateable if the functional operation is associative and commutative over the function space and inverse function can be computed in constant time. Based on these tests we develop constant time updateable approximate and exact set operations.