ERCIM News No.44 - January 2001 [contents]
ERCIM News No.44 - January 2001 [contents]
by Pavel Chalmoviansky
Scientists at Comenius University, Bratislava, are developing techniques for efficient and robust manipulation of the geometric properties of shapes, a task that has been particularly problematic in the past.
Construction using subdivision surfaces is a technique in geometric modelling which combines both computational simplicity and ease of control. Although there are some unsolved problems, this appears to be a growing trend in recent years. After the era of mainly parametric, implicit and functional modelling, there is now a method which offers more flexible (than in the case of implicit surfaces) and more intuitive (than in the case of integral or rational surfaces) control and modelling of the final shape. Moreover, the final surface can be easily represented as a multiresolution model.
The first subdivision method was developed more than 20 years ago, but the method achieved more popularity only in the 90ís. During these years the mathematical foundations were laid and several problems (eg of continuity and parameterisation) were solved. However, success was only achieved with static subdivision methods.
The principle is to refine the structure of the surface representation up to a state with which we are content. We start with cell complex K(0) and function p(0) on the vertices of K(0). The refinement or subdivision has two phases: We construct K(i+1) from K(i) and p(i+1) from p(i). The rules are usually local and simple, hence the new complex and the new function can be easily computed. In the figure below, the whole process of the subdivision can be seen. Usually several iterations are enough for high accurate results.
There are several known schemes of this type published by Loop, Catmull-Clark, Doo-Sabin, Kobbelt and others. All of them work on an almost regular cell complex with triangular or quadrilateral faces. Final surfaces can interpolate the values of p(i) at vertices and one can also mark special edges which play the role of boundaries during the construction and thus other rules are applied upon them. There are also so-called combined schemes which take special care at the boundaries of the surface. The schemes produce surfaces of lower degree (if they are polynomials) and lower order of continuity. This is however not enough for some applications and further schemes are sought.
The main open problems are to be found when we consider the manipulation of these objects. As the number of cells increases exponentially, it would not be possible to maintain a high number of objects at their full representation. Adaptive methods represent objects using several layers. The more layers one displays, the more details one can see. The cell that will be cancelled in a layer can be computed according to variational calculus. More efficient methods are still required. Modelling inside CAD systems in this area produces more problems: during the intersection of two surfaces we create objects that are not primarily products of the subdivision scheme. The solution for this situation should be compatible with the whole modelling system. Mainly in CAD systems, high order continuity surfaces are required. The known methods suffer from huge numbers of vertices involved in the computation of the next iteration.
A wide range of unsolved questions arise if we consider also irregular cell complexes. The set of solutions is very sparse here. Subdivision surfaces were also used in real applications. In 1997 the first animation using only subdivision surfaces was made by Pixar - Geriís Game, and Toy Story II also used them.
Please contact:
Pavel Chalmoviansky - SRCIM / Comenius University
Tel: +421 7 6029 5229
E-mail: chalmo@fmph.uniba.sk