/ 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.
Unrefereed Papers
Technical Reports
Academic Activities
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.
Others
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.