/ V. V. Savchenko / Professor
/ Fuhua Cheng / Visiting Professor
/ Kenjiro T. Miura / Associate Professor
/ Alexander A. Pasko / Assistant Professor
Problems of shape modeling possess high computational requirements and contain large amounts of inherent parallelism. Our investigations show that these problems can be effectively solved on parallel computers. Our research intentions are: 1) to make distributed systems as easy for programming as conventional systems and to provide an introduction for teaching students new design concepts of parallel algorithms and codes exemplified by problems in shape modeling; 2) to provide an opportunity to focus on the research and development in a transputer environment. First year results are presented below.
1) Mesh generation.
Mesh generation is a process of generating finite element models. Since the accuracy of the FE solution is dependent on the element mesh layout, and the cost of the analysis becomes prohibitively expensive if the number of elements in the mesh is too large, a good mesh generating method should let the user generate a mesh that is just fine enough to give an adequate solution accuracy. We have developed a new mesh subdivision algorithm based on the vertex label assignment scheme which makes the mesh generation in parallel.
2) 3D surface analysis and synthesis.
The function representation of geometric objects is a basic model in this research. We hope that function representation can help to overcome the barrier between well known methods of geometric modeling and relatively new methods based on implicit functions and volumetric data. Many new operations like 3D metamorphosis, hypertexturing and free-form deformations can be directly applied to CSG or swept objects. On the other hand, any objects defined by implicit functions can be used now for sweeping, set-theoretic operations, offsetting and blending. Dimension independence of the representation serves for effective combination of shape modeling and animation. One of the ways of considerably cutting down the calculation time in surface modeling consists of resorting to parallel computing. The following approach lies at the base of our algorithm. The geometric surface is represented by an implicit function of three variables. The function domain is divided by cubic cells. Patches of the surface are detected in every cell using a trilinear interpolation technique. This algorithm is implemented on a transputer toroidal network.
Ray tracing Gregory-type patches creates a 2D image by tracing imaginary rays of light from the view point to the objects in the scene. Our concern here is the ray tracing problem for objects represented by Gregory-type patches, i.e., Gregory patch, rational boundary Gregory patches. We have developed a new method named Gregory clipping which is based on constructing bounding volumes for subpatches of a Gregory-type patch and performing subdivision without increasing the degree of the patch.
3) Geometric collisions
To represent virtually any surface the function representation is used. Set-theoretic operations between bodies are implemented on the base of special technique of R-functions. Parallel execution is achieved by dividing modeling space into patches. The OCCAM-2 language is used for software shell writing since it involves the most powerful and simple facilities for organization of parallel calculations.
4) Data processing for computerized tomography
The beam diagnostic and control based on low energy electron or ion beams uses the deflection of probing particles due the fields of the beam to be investigated to provide tomography data about transverse charge distribution. Instruments for beam diagnostic are highly precise and have wide perspectives. CT allows for determination and observation of the complete charge distribution and neutralization.
The algorithms and software tools developed in Shape Modeling Laboratory can be applied in intelligent CAD, animation and virtual reality systems.
Refereed Journal Papers
A parallel implementation of Chebyshev method is presented for the B-spline surface interpolation problem. The algorithm finds the control points of a uniform bicubic B-spline surface that interpolates m x n data points on an m x n mesh-connected processor array in constant time. Hence, it is optimal. Due to its numerical stability, the algorithm can successfully be used in finite precision floating-point arithmetic.
It is well known that a rational composite Bezier curve of degree n can be represented as a NURBS curve with knots of multiplicity n. We present an algorithm to reduce the degree of multiplicity of some knots to n-1. This reduced-knot NURBS representation is based on the reparametrization of the Bezier curve segments.
Gregory patch is a kind of free-form surface patch developed by Miura and Wang in order to generate surfaces with the continuity of curvature, i.e., continuity. Since neither the subregion of a Gregory nor Gregory patch can be generally expressed by its formulation, the subdivision method can not be applied to either Gregory or Gregory patch without modifications for calculating patch/line, patch/plane, or patch/patch intersections. Therefore, we have proposed certain bounding volumes of the subregions of Gregory and Gregory patches and have developed a new method called Gregory clipping by use of it to calculate patch/line intersections. We have applied it for ray tracing Gregory patches.
Refereed Proceeding Papers
An algorithm for the construction of a non-uniform cubic B-spline curve that interpolates a set of 2D data Di is presented. Each Di is either a point of a region. If Di is a point, the curve interpolates it. Otherwise, the curve passes through the region specified by Di. The curve is constructed based on minimizing the energy of each its components. The parametric knots of the curve are parametrized using the centripetal model. These processes facilitate the geometric smoothness and fairness of the curve. The new technique allows a user to design a curve with more flexibility and fewer trial-and-error iterations than conventional approach. This work is a continuation of the paper "Interproximation: Interpolation and Approximation Using Cubic Spline Curves" publisshed in 1991.
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 Gregory patches.
This paper introduces a new type of free-form patches named rational boundary Gregory patch. It can be said an extension of Gregory patch developed by Miura and Wang, which gives users the capability of designing curvature-continuous surfaces ( continuous surfaces) with reasonable flexibilities, and also that of rational boundary Gregory patch proposed by Chiyokura et al., which is surrounded by rational Bezier curves and can be interpolated with the continuity of tangent planes ( continuity). As the name of the patch implies, its boundary consists of rational Bezier curves. Its derivation is explained and methods for continuity are proposed to connect it with a rational Bezier patch and with another patch. Finally, a continuous interpolation method based upon such patches is discussed.
In certain applications of Computer-Aided Geometric Design, the continuity of curvature, i.e., continuity is required when two surface patches are connected. Although tangent-continuous, or continuous surfaces look smooth, reflection lines have generally been broken at points where curvature is not continuous and they may cause functional defects such that as flow separation, turbulence, or abrupt changes in acceleration. In order to generate continuous surfaces easily, we have developed a system with use of Gregory patch which is an extension of the Gregory-patch formulation.
The continuous analytical description of the blending set-theoretic operations is proposed for geometric objects with implicit surfaces. We use the theory of R-functions for this. Intuitive shape control and aesthetic blend by hand drawn strokes are supported. Offsetting operation is applied in the particular case of constant-radius blending.
A new approach to interactive geometric modeling is proposed. It is based on the agent-oriented modeling technique. Our modeling system uses the function representation and R-functions in particular. This supplies a high-level symbolic description of the n-dimensional geometric model being updated the during modeling process. Our approach to building a definitive geometric language to allow incremental and extensible modeling is described.
"Solid noise" defined by a continuous stochastic function of three variables is used for producing new shapes of solid objects by means of functionally based constructive solid geometry (CSG). We have applied the theory of R-functions to implement set-theoretic operations over three-dimensional objects with implicitly defined surfaces. Geometric operations producing moss, snow drifts, crushed and furry objects are represented.
The approach called 'Empty Case' technology is discussed to provide the possibility for each student to create and exploit his personal geometric modeling system using basic instrumental software according to his interests and level of education. Geometric concepts and instrumental system based on the "function representation" supporting exploratory geometric modeling are described. Usage of the high-level geometric language with symbolic definition of a descriptive function is illustrated by several examples.
Implementation of the parallel computers with the toroidal transputer architecture for simulation of geometric collisions between rigid bodies is presented. We have developed the distributed version of particle-in-cell (PIC) model. To represent virtually any surface implicit function representations are used. Visualization of complex objects is based on the ray-marching algorithm applied to implicitly defined surfaces. Potential application of this software algorithm is a numerical analysis for the bodies with various physical characteristics and complex surfaces.
The appearence of parallel architecture has made it possible to have mathematical modeling which allows us to simulate complex systems in real time on a cost effective basis. Yet, we are witnessing a shortage of applied software despite the rapid growth in computer performance enable by parallel architectures. To fill the gap the authors have used the ``Serialization" approach as a basis for a problem-oriented software written in 3LC which allows to produce a simple and effective design of applied software.
Organizer and session chair of Computation Tessellation and Modeling of NURB Surfaces SIAM Conference on Geometric Design, November 1-5, 1993, Radisson Hotel, Tempe, Arizona.
Reviewer for Journal of Japan Society for Precision Engineering.
Guest Reviewer for Journal of Japan Society for Design Engineering.
Reviewer for the Visual Computer. Computer Graphics Society.
Reviewer for Eurographics.
Session speaker of Computation, Tessellation, and Modeling of NURB Surfaces, SIAM Conference on Geometric Design, Radisson Hotel, Tempe, Arizona.
Invited lecture: ``Functionally based constructive representation for geometric modeling and image processing on parallel computers", University of Warwick, Coventry, UK.
New Computation Techniques for Shape Modeling and Design, National Science Foundation (USA), 4/15/94-4/14/97, US$270,000.
Scholarship: The Telecommunications Advancement Foundation Oversea Presentation Scholarship.
Scholarship: Foundation for C and C Promotion Oversea Presentation Scholarship.