Abstract
We introduce a computationally efficient method for interactive construction of implicitly represented star solids. These solids smoothly approximate control shapes that are defined by exact union and intersections over half-spaces containing the origin. Based on our algorithm, computation of a new solid shape when a new half-space is added or when the position of an existing half-space is changed can be performed in constant time and in space linear in the number of half-spaces. Our implicit shape construction is based on a family of non-polynomials called ray-linears [Akle93b]. Computation of an implicitly represented shape is a root finding process and in general can be extremely difficult. However since ray-linear implicit representations can easily be parameterized, the computation of any ray-linearly represented shape simplifies to evaluation of a parametric equation instead of root finding. But the related parametric equations are non-polynomials and their complexity increases as the number of building blocks (in this case half-spaces) increases. Our algorithm makes the computation of this parametric equation independent of the number of half-spaces. We develop an interactive platform based on our algorithm with which we are able to construct star solids that resemble human faces.
