/ V. V. Savchenko / Professor
/ Kenjiro T. Miura / Associate Professor
/ Alexander A. Pasko / Assistant Professor
The Shape Modeling Laboratory is concerned with the research of geometric modeling in two main directions: function representation (F-rep) and Gregory-type patches. The main goal of our project is to be a leading group for advanced research and development in visually-oriented and interactive processes for scientific, applied and educational purposes.
We use shape modeling scheme that provides the power to continuously transform geometric objects and allows to build a rich system of operations closed on function representation. Also the scheme provides the geometric reconstruction from surface points and feature based reconstruction. We have developed and described following operations: blending, offsetting, projection, sweeping, cartesian product, deformation and metamorphosis. To visualize the resulting object we have developed software for polygonization and ray casting on sequential and parallel platforms (transputers, PVM). We have tested our methods on following application problems: aesthetic blends in design, simulation of NC machining, reconstruction of solids from medical images, simulation of a growing mammalian cell colony, modeling hairstyles, animation of a volumetric head.
In 1994, one of our biggest accomplishments is that we have found a very efficient method to convert any Gregory-type patches to NURBS surfaces. This will make our projects more useful and practical because any Gregory-type patches can be approximated by the standard free-form representation method. This guarantees that surfaces generated by our goal system, which will generate free-form surfaces from design sketches, even if they are Gregory-type patches, can be smoothly transfered to other available systems. By this accomplishment, we can use Gregory-type patches as an initial generated surface without loss of general applicability.
In addition to the above mentioned accomplishments, we have improved our ray tracing method and done processing time analysis. Furthermore, we have done an correction of our theory on Rational Boundary $C^2$ Gregory patch and further sophistication of NURBS Boundary $C^2$ Gregory patches. These results will enhance necessary theories to accomplish our primary goal : development of software systems to generate 3D models based on design sketches using Virtual Reality techniques. The ray tracing technique will improve our goal system's interactivity and new types of free-form patches will increase the ability to express complicated shapes like flowers, trees, cars, air plaines and other natural and artifical objects.
Refereed Journal Papers
Various kinds of Gregory-type patches have been developed as free-form surfaces which can be easily connected to each other with G$^1$ or G$^2$ continuity. Although their importance has been recently recognized in the field of CAD/CAGD, many CAD/CAM systems are using NURBS (non-uniform B-spline) surfaces as the representation of free-from surfaces. To share geometric data with these CAD/CAM systems, it is desirable to have a method to convert Gregory-type patches to NURBS surfaces. It is possible to do it exactly, but it requires considerable increases of their degrees. Hence, in this paper, we propose a new method to convert approximately any Gregory-type patches to NURBS surfaces. The method is that first, the patch is subdivied into several subpatches as specified and they are approximated with suitable B\'ezier-type patches. Then, their control points are combined to generate ones of the NURBS surface.
Geometric modeling using a continuous real functions of several variables is discussed. Modeling concepts include sets of objects, operations and relations. Transformations of a defining function are described for set-theoretic operations, blending, offsetting, bijective mapping, projection, cartesian product and metamorphosis. Inclusion, point membership and intersection relations are described. We introduce high-level geometric language that provides extendibility of a modeling system by input symbolic descriptions of primitives, operations and predicates. This approach supports combinations of representational styles, including constructive geometry, sweeping, soft objects, voxel-based objects, deformable and other animated objects. Application examples of aesthetic design, collisions simulation, NC machining, range data processing, and 3D texture generation are given.
This paper presents a novel approach to the geometric model reconstruction from surface points using volume splines. It results in the function representation of a solid by the inequality $f (x,y,z) = > 0$. Volume splines are based on the Green's function and interpolate scalar function values of a chosen "carrier" solid. Our algorithm can generate highly concave and branching objects automatically. The particular case of given object's parallel cross-sections is discussed too. The examples of set-theoretic operations on the reconstructed solids are given. Potential application of this algorithm is tomography, image processing, animation and CAD for bodies with complex surfaces.
We consider a long-standing problem, hair modelling, and show how easy and effectively our functionally based model can be applied there. Modelling hair, we represent it with solid noise and subsequently unify it with the solid being made hairy. The hair and the solid are defined by real functions and the resultant hairy solid is in turn functionally defined and can be an argument for other operations. We are able to control length, thickness and curliness of hair and to obtain different hairstyles varying defining functions and applying set-theoretic operations to solid hair.
This paper presents a new technique to ray trace Gregory-type patches. Standard subdivision-based method may not be used here due to the fact that subpatches of a Gregory-type patch do not possess the same representation. The presented technique is based on bounding volumes for subregions of Gregory-type patches and a new method called Gregory clipping to calculate line/patch intersections. The technique has been implemented for ray tracing C$^2$ Gregory patches.
A new type of free-form surface patch called NURBS boundary C${\rm ^2}$ Gregory patch(NBC${\rm ^2}$G patch) is introduced. An NBC$^{\rm 2}$G patch, whose boundary is defined by four NURBS curves, is an extension of both the C${\rm ^2}$ Gregory patch developed by Miura and Wang, which gives users the capability of designing curvature-continuous(${\rm G^2}$ continuous) surfaces with reasonable flexibilities, and also that of NURBS boundary Gregory patch proposed by Sone et al., which is surrounded by NURBS curves and can be interpolated by specifications of its cross-boundary first derivatives. This new type of surface patch inherits advantages of both the C$^{\rm 2}$ Gregory patch and the NURBS boundary Gregory patch. It is defined so as to connect it with a rational B\'ezier patch and with a rational boundary C$^{\rm 2}$ Gregory patch with G$^{\rm 2}$ continuity when its boundary can be expressed as rational B\'ezier curves. Derivation, properties, and examples of the new type of surface patch are also presented.
We consider set-theoretic operations on 3D solids in relative motion. The approach is proposed to represent the result by a continuous real functions of three variables. We demonstrate the abilities of this approach to simulate processes of NC machining.
This paper studies a function representation of point sets swept by moving solids. The original solid-generator is defined by a real function f(x,y,z,t). This definition allows us to include solids which change their shapes in time. Constructive solids can be used as generators also when described by R-functions. The trajectory of the generator can be defined in parametric form as movement of its local coordinate system. To get the function representation F(x,y,z)=>0 of the swept solid we apply the concept of envelope used before basically for boundary represented objects. We have reduced the problem of swept solid description to global extremum search by t variable.
We combine the agent-oriented approach to geometric modeling with the inductive visualization to explore multidimensional geometric objects. The example is given of constructing 5D object as a section of a bilinear patch of a hypersurface in 6D space.
The definitions of iso-valued, normal and constant-radius offsetting are proposed for solids represented by continuous real functions of several variables. Solids constructed with set-theoretic operations are defined by means of R-functions.
This paper deals with an interactive deformation technique in solid modeling. The problem solved is to control local deformations of a solid by a set of arbitrary points which are assumed to belong to the surface of the resultant solid. The representation of a solid by a real continuous function of three variables is used. The theory of R-functions is applied for set-theoretic operations on solids. In contrast to the existing methods based on space mapping, we construct a displacement function that interpolates values of the defining function in given control points. Then algebraic sum (difference) of the defining function and the displacement function describes the deformed solid. Blobby deformation and deformation by a volume spline are discussed.
Geometric aspects of computer simulation of a growing mammalian cell colony are presented. Cells are modelled as arbitrarily shaped deformable particles with implicit surfaces. Interpenetrating particles deform each other. A particle can be substituted by a pair of new particles that models the process of cell division. Packing of reproducing particles is performed by a genetic algorithm based on collision detection. Volume of an interpenetration area serves as a fitness function. Parallelization of the simulation algorithm on the network of workstations under the PVM system is described. Simulation results are compared with the images of real cell colonies.
This paper presents state of the art of our project on development functionally based constructive geometric modeling paradigm. In particular, we discuss recently obtained results on the following operations closed on the function representation: blending, generalized offsetting, deformation and metamorphosis. These operations are selected to explicitly show the advantages of combining uniformity of the skeletal models with the constructive modeling style developed in CSG.
We describe an algorithm of collision detection for geometric objects defined by real continuous functions of three variables. First, the intersection area of two objects is described using R- functions. Then the numerical procedure is applied to find the maximum of the resulting function. If the maximal value is negative, objects have no collision points. We use pseudo-random points and the spiral quadratic metod to accelerate the search. Example of collisions of the irregular and hairy shapes are given.
We describe our parallel implementation and time performance evaluation results for polygonization of implicitly defined surfaces on the network of workstations under the PVM system. Potential application areas are rendering in CAD systems, surface reconstruction from medical images and function analysis in mathematics.
This paper presents an approach and examples of parallel polygonization of surfaces defined by implicit functions f(x,y,z)=0. We discuss also time performance evaluation results of processing a given object in parallel. The algorithm has been designed to be scalable and has been ported to a transputer network with the toroidal architecture.