Next: Image Processing Laboratory Up: Department of Computer Previous: Computer Graphics Laboratory

Shape Modeling Laboratory

/ 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

  1. K. T. Miura, J. Sone, and H. Chiyokura. Approximate conversions of gregory-type patches to nurbs surfaces. Trans. IPSJ , 36(4), 1995.

    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.

  2. A. Pasko, V. Adzhiev, A. Sourin, and V. Savchenko. Function representation in geometric modeling: concepts, implementation and applications. The Visual Computer (accepted) , 1995.

    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.

  3. V. Savchenko, A. Pasko, O. Okunev, and T. Kunii. Function representation of solids reconstructed from scattered surface points and contours. Computer Graphics Forum , 14(4):181--188, 1995.

    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.

  4. A. Sourin, A. Pasko, and A. Savchenko. Hair modelling by real functions. Computers and Graphics , 20(1), 1996.

    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.

Refereed Proceeding Papers

  1. K. T. Miura. Ray tracing gregory-type patches. In Gigante M. and Rogers D. F., editors, CG International'94. Computer Graphics Society, June 1994.

    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.

  2. K. T. Miura and H. Chiyokura. NURBS boundary c$^2$ gregory patch. In International Conference on Computer Aided Geometric Design. School of Mathematical and Computer Sciences, Universiti Sains Malaysian, Baltzer, July 1994.

    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.

  3. A. I. Sourin and A. A. Pasko. Time dependent set-theoretic operations for functionally represented solid objects. In Proceedings of IEEE TENCON'94, pages 222--229. IEEE, 1994.

    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.

  4. A. Sourin and A. Pasko. Function representation for sweeping by a moving solid. In C. Hoffmann and J. Rossignac, editors, Third ACM SIGGRAPH Symposium on Solid Modeling and Applications, pages 383--391. ACM, ACM Press, 1995.

    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.

  5. A. Pasko and V. Adzhiev. Interactive exploring multidimensional geometric data. In HCI International'95, 6th International Conference on Human-Computer Interaction, Yokohama, Japan, July 9-14, 1995 (accepted), 1995.

    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.

  6. A. Pasko and V. Savchenko. Offsetting operations for the functionally based constructive geometry. In K. Suzuki and K. Yoshida, editors, Proceedings of 6th International Conference on Engineering Computer Graphics and Descriptive Geometry (ICECGDG), volume 1, pages 201--204. American Society for Engineering Education, 1994.

    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.

  7. A. Pasko and V. Savchenko. Algebraic sums for deformation of constructive solids. In C. Hoffmann and J. Rossignac, editors, Third ACM SIGGRAPH Symposium on Solid Modeling and Applications, pages 403--408. ACM, ACM Press, 1995.

    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.

  8. V. V. Savchenko, A. G. Basnakian, A. A. Pasko, S. V. Ten, and R. Huang. Simulation of a growing mammalian cell colony: collision-based packing algorithm for deformable particles. In R. A. Earnshaw and J. A. Vince, editors, Computer graphics: developments in virtual environments, pages 437--447. Computer Graphics Society, Academic Press, 1995.

    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.

  9. A. Pasko and V. Savchenko. Constructing functionally defined surfaces. In M. P. Gascuel and B. Wyvill, editors, First International Workshop on Implicit Surfaces, Grenoble, France, April 18-19, 1995, pages 97--106. Eurographics Association, INRIA, 1995.

    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.

  10. V. V. Savchenko and A. A. Pasko. Collision detection for functionally defined deformable objects. In M. P. Gascuel and B. Wyvill, editors, First International Workshop on Implicit Surfaces, Grenoble, France,April 18-19, 1995, pages 217--221. Eurographics, INRIA, 1995.

    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.

  11. S. V. Ten, V. V. Savchenko, and A. A. Pasko. Time performance evaluation of implicit surfaces polygoniztion on distributed systems. In J. P. Gray and F. Naghdy, editors, Parallel Computing: Technology and Practice, pages 183--193. Australian Transputer and Occam User Group, IOS Press, 1994.

    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.

  12. V.Savchenko and A. Pasko. Parallel polygonization of implicit surfaces on transputers: algorithm, time performance evaluation and rendering results. In H. Arabnia, editor, Transputer Research and Applications, pages 22--30. North American Transputer Users Group, IOS Press, 1994.

    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.

Technical Reports

  1. K. T. Miura. Bounding volumes of gregory-type patches and their applications to ray tracing. 94-1-017, University of Aizu, 1994.

  2. W. K. Cheung and K. T. Miura. The multi-model-based prototyping tool: Prototyper's workbench. 94-1-40, University of Aizu, 1994.

  3. K. T. Miura and Hiroaki Chiyokura. A new c2 gregory-type patch bounded by nurbs curves. 94-1-41, University of Aizu, 1994.

  4. K. T. Miura. Development of gregory-type patches. 94-1-42, University of Aizu, 1994.

  5. V. V. Savchenko, A. A. Pasko, O. G. Okunev, and T. L. Kunii. Function representation of solids reconstructed from scattered surface points and contours. 94-1-032, University of Aizu, 1994.

  6. V. P. Shestak, Savchenko A. V., and V. V. Savchenko. Novel diagnostics for ion beam implantation technology. 94-1-027, University of Aizu, 1994.

  7. I. S. Sedukhin, S. G. Sedukhin, A. A. Pasko, V. V. Savchenko, and N. N. Mirenkov. Parallel rendering of functionally represented geometric objects with the network Linda system. 95-1-001, University of Aizu, 1995.


  1. Kenjiro Takai Miura. Ministry of education scientific research fund. Reserach by Young A, No. 06780279, Engineering Computer Science, 1994.

Academic Activities

  1. Kenjiro Takai Miura, Journal of Japan Society for Precision Engineering. Reviewer, 1994.

  2. Kenjiro Takai Miura, Computer Graphics Society, CGS. Reviewer for the Journal 'Visual Computer' (1993.4 - ), 1994.

  3. Kenjiro Takai Miura, International Workshop ``Shape Modeling: Parallelism, Interactivity and Applications", The University of Aizu, September 13-15, Japan. Member of the organization committee, September 1994.

  4. Alexander A. Pasko, International Workshop `Shape Modeling: Parallelism, Interactivity and Applications' The University of Aizu, September 13-15, Japan. Member of the organization committee, September 1994.

  5. Vladimir V. Savchenko, International Workshop `Shape Modeling: Parallelism, Interactivity and Applications', The University of Aizu, September 13-15, Japan. Member of the organization committee, September 1994.

  6. Vladimir V. Savchenko, International Symposium `Parallel Algorithms/ Architecture Synthesis', The University of Aizu, March 15-17, Japan. Member of the organization committee, March 1995.

  7. Vladimir V. Savchenko, 2-nd Workshop on Syntific Worlds, Institute for the Sciences of Complexity, January 25-27, Paris, France. Invited talk on Geometric modeling of human cell colony, body and hair, January 1995.

  8. Vladimir V. Savchenko, Computer Graphics Society, CGS. Reviewer for Pacific Graphics'95 International Conference, 1995.

  9. Vladimir V. Savchenko, Computer Graphics Society, CGS. Reviewer for the Journal Visual Computer , 1994.

Next: Image Processing Laboratory Up: Department of Computer Previous: Computer Graphics Laboratory
January 1996