This paper deals with 2D image transformations from a perspective of a 3D heterogeneous shape modeling and computer animation. Shape and image morphing techniques have attracted a lot of attention in artistic design, computer animation, and interactive and streaming applications. We present a novel method for morphing between two topologically arbitrary 2D shapes with sophisticated textures (raster color attributes) using a metamorphosis technique called space-time blending (STB) coupled with space-time transfinite interpolation. The method allows for a smooth transition between source and target objects by generating in-between shapes and associated textures without setting any correspondences between boundary points or features. The method requires no preprocessing and can be applied in 2D animation when position and topology of source and target objects are significantly different. With the conversion of given 2D shapes to signed distance fields, we have detected a number of problems with directly applying STB to them. We propose a set of novel and mathematically substantiated techniques, providing automatic control of the morphing process with STB and an algorithm of applying those techniques in combination. We illustrate our method with applications in 2D animation and interactive applications.

This paper presents a system for user-assisted reverse modeling: from digitized point-cloud to solid models ready to be used in a CAD modeling system. Our approach consists in the following steps: segmentation, fitting, and constructive model discovery. Each of these steps are based on evolutionary algorithms. The obtained objects can then be further edited or parameterized by users and fitted to adapt their shape to different point-clouds.

Abstract Signed distance fields obtained from polygonal meshes are commonly used in various applications. However, they can haveC1discontinuities causing creases to appear when applying operations such as blending or metamorphosis. The focus of this work is to efficiently evaluate the signed distance function and to apply a smoothing filter to it while preserving the shape of the initial mesh. The resulting function is smooth almost everywhere, while preserving the exact shape of the polygonal mesh. Due to its low complexity, the proposed filtering technique remains fast compared to its main alternatives providingC1‐continuous distance field approximation. Several applications are presented such as blending, metamorphosis and heterogeneous modelling with polygonal meshes.

The paper presents a novel technique based on extension of a general mathematical method of transfinite interpolation to solve an actual problem in the context of a heterogeneous volume modelling area. It deals with time-dependent changes to the volumetric material properties (material density, colour, and others) as a transformation of the volumetric material distributions in space-time accompanying geometric shape transformations such as metamorphosis. The main idea is to represent the geometry of both objects by scalar fields with distance properties, to establish in a higher-dimensional space a time gap during which the geometric transformation takes place, and to use these scalar fields to apply the new space-time transfinite interpolation to volumetric material attributes within this time gap. The proposed solution is analytical in its nature, does not require heavy numerical computations and can be used in real-time applications. Applications of this technique also include texturing and displacement mapping of time-variant surfaces, and parametric design of volumetric microstructures.

In this paper we present the SHIVA project which was designed to provide virtual sculpting tools for children with complex disabilities, to allow them to engage with artistic and creative activities that they might otherwise never be able to access. Modern 3D printing then allows us to physically build their creations. To achieve this, we combined our expertise in education, accessible technology, user interfaces and geometric modelling. We built a generic accessible graphical user interface (GUI), a suitable geometric modelling system and used these to produce two prototype modelling systems. These tools were deployed in a school for students with disabilities and are being used for a variety of educational purposes. In this paper, we present the project's motivations, approach and implementation details together with initial results, including 3D printed objects designed by children with disabilities.

Abstract Enabling animators to smoothly transform between animated meshes of differing topologies is a long‐standing problem in geometric modelling and computer animation. In this paper, we propose a new hybrid approach built upon the advantages of scalar field‐based models (often called implicit surfaces) which can easily change their topology by changing their defining scalar field. Given two meshes, animated by their rigging‐skeletons, we associate each mesh with its own approximating implicit surface. This implicit surface moves synchronously with the mesh. The shape‐metamorphosis process is performed in several steps: first, we collapse the two meshes to their corresponding approximating implicit surfaces, then we transform between the two implicit surfaces and finally we inverse transition from the resulting metamorphosed implicit surface to the target mesh. The examples presented in this paper demonstrating the results of the proposed technique were implemented using an in‐house plug‐in for Maya™.

Polygonal models are widely used in computer animation. Static polygonal models are commonly animated using an underlying skeleton controlling the deformation of the mesh. This technique, known as skeletal animation, allows the artist to produce complex animation sequences in a relatively easy way. However, performing complex transitions between arbitrary animated meshes remains a challenging problem. There is a set of established techniques to perform metamorphosis (3D morphing) between static 3D meshes [Lazarus and Verroust 1998], but most of these can not be easily applied to animated meshes. The approach presented in this poster allows us to produce with great ease metamorphosing transitions between animated meshes of arbitrary topology using polygonal-functional hybrids [Kravtsov et al. 2010a]. Our technique uses the meshes of the objects as well as their skeleton animations. As a result we are able to generate metamorphosis animations of time-varying meshes of arbitrary topologies in near real-time.

Most of the existing methods of metamorphosis are based on the interpolation schemes, space-time blending is a geometric operation of bounded blending performed in the higher-dimensional space. It provides transformations between shapes of different topology without necessarily establishing their alignment or correspondence. The original formulation of space-time blending had several problems: fast uncontrolled transition between shapes within the given time interval, generation of disconnected components, and lack of intuitive user control over the transformation process. We improve the original technique to provide the user with a set of more intuitive controls. The problem of the fast transition between the shapes is solved by the introduction of additional controllable affine transformations applied to initial objects in space-time. The approach is further extended with the introduction of an additional non-linear deformation operation. The proposed techniques have been implemented and tested within an industrial computer animation system. We have also implemented our method on the GPU, so that it can be employed in real-time applications.

We propose a new approach to modelling heterogeneous objects containing internal spatial geometric structures with size of details orders of magnitude smaller than the overall size of the object. The proposed function-based procedural representation provides compact, precise, and arbitrarily parametrized models of coherent microstructures, which can undergo blending, deformations, and other geometric operations, and can be directly rendered and fabricated without generating any auxiliary representations (such as polygonal meshes and voxel arrays). In particular, modelling of regular lattices and cellular microstructures as well as irregular porous media is discussed and illustrated. Examples of rendering and digital fabrication of microstructure models are presented.

Abstract In this paper, we address shape modelling problems, encountered in computer animation and computer games development that are difficult to solve just using polygonal meshes. Our approach is based on a hybrid‐modelling concept that combines polygonal meshes with implicit surfaces. A hybrid model consists of an animated polygonal mesh and an approximation of this mesh by a convolution surface stand‐in that is embedded within it or is attached to it. The motions of both objects are synchronised using a rigging skeleton. We model the interaction between an animated mesh object and a viscoelastic substance, which is normally represented in an implicit form. Our approach is aimed at achieving verisimilitude rather than physically based simulation. The adhesive behaviour of the viscous object is modelled using geometric blending operations on the corresponding implicit surfaces. Another application of this approach is the creation of metamorphosing implicit surface parts that are attached to an animated mesh. A prototype implementation of the proposed approach and several examples of modelling and animation with near real‐time preview times are presented.

The problem considered in this work is to find a dimension independent algorithm for the generation of signed scalar fields exactly representing polygonal objects and satisfying the following requirements: the defining real function takes zero value exactly at the polygonal object boundary; no extra zero-value isosurfaces should be generated; C1continuity of the function in the entire domain. The proposed algorithms are based on the binary space partitioning (BSP) of the object by the planes passing through the polygonal faces and are independent of the object genus, the number of disjoint components, and holes in the initial polygonal mesh. Several extensions of the basic algorithm are proposed to satisfy the selected optimization criteria. The generated BSP-fields allow for applying techniques of the function-based modelling to already existing legacy objects from CAD and computer animation areas, which is illustrated by several examples.

This paper describes a technology for modelling and rendering heterogeneous objects containing entities of various dimensionalities within a cellular-functional framework based on the implicit complex notion. Implicit complexes make it possible to combine a cellular representation and a constructive function representation. We describe a formal framework for such a hybrid representation and propose a general structure for implicit complexes. Then, we consider how an implicit complex can be described geometrically and topologically along with its associated attributes. Rendering algorithms for implicit complexes using ray-tracing are also discussed. Finally, we present a case study illustrating the proposed methods and algorithms.

In this paper we describe an approach to computer-aided sculpting concerned with the creation and modification of digital models based on physical abstract sculptures. We begin by presenting a survey of current methods for the creation of computer-aided sculptured artefacts. Then we proceed to present some original methods and tools based on the function representation of geometric models. We introduce a specialized computer language, named HyperFun, which facilitates the modelling of complex objects. As well as presenting computer-generated animated models of pre-existing sculptures by Russian artist Igor Seleznev, we also show how some interesting novel shapes can be generated using the HyperFun system. Finally we outline two advanced projects concerned with creating a sculpture-based augmented reality which allows for the interactive participation of the observer. In this paper, we present experimental results, which hopefully have some artistic appeal. These results were produced by an international team of researchers and students collaborating through the Internet. Copyright © 2005 John Wiley & Sons, Ltd.

We apply topological analysis to functionally based shape metamorphosis. Functionally based methods have two problems: shape interpolation is applied without defining the topological information and the time moments of topological changes are not known. Thus, it is difficult to identify the time intervals for key frames of shape metamorphosis animation. Moreover, information on the types of the topological changes is missing. We present a method of the critical points detection based on the Morse theory and classification using the Hessian matrix for solving these problems. The defining function of the linear metamorphosis is treated as a height function. By analyzing how the critical points are changing at a particular height level, we detect the critical points of the metamorphosis process. The critical points can be used for ease in/ ease out effects in animation. In addition, we classify the detected critical points into maximum point, minimum point, and saddle point types. Using the type of the critical points and the sign of the function time derivative at the critical points, we can define the topological information for the shape metamorphosis. We illustrate these methods using shape metamorphosis in 2D and 3D spaces.

We apply topological analysis to functionally based shape metamorphosis. The time-dependent shape is defined using homotopy. The advantage of this method is the automatic generation of the intermediate shapes between the key shapes of different topology types. To complete the method, we have to find a way to automatically detect the critical points on the time axis while the shape undergoes topological changes. These critical points can be later used for generation of non-linear time steps distribution along the time axis, for example, for providing ease-in/ease-out effects in animation. We present a new method for analysis of shape metamorphosis based on the Morse theory, oriented to analysis of a height function. Although we analyze the shape in an N-dimensional space, the height function is defined in the N+2 dimensional space with N point coordinates and two additional coordinates of the defining function and time values. We can analyze how the critical points are changing in the given height level, which takes only zero value of the shape defining function. In this paper, we present this method in comparison with typical Morse theory analysis using simple objects in 2D and 3D spaces.

We further develop a new approach to shape metamorphosis using bounded blending operations in space-time. The key steps of the metamorphosis algorithm are: dimension increase by converting two input kD shapes into half-cylinders in (k+1)D space-time, applying bounded blending union with added material to the half-cylinders, and making cross-sections for getting intermediate shapes under the transformation. This approach is extended here in two directions. First, the problem of "jump" in animation or the rapid transition between shapes in the given interval is solved using "smoothed" versions of half-cylinders which undergo bounded blending. Second, the approach is extended to 3D initial and final shapes with the bounded blending union operation applied to the corresponding "smoothed" 4D space-time half-cylinders.

We propose a method which helps to fit existing parameterized function representation (FRep) models to a given dataset of 3D surface points. Best fitted parameters of the model are obtained by using a hybrid algorithm combining simulated annealing and Levenberg-Marquardt methods. The efficiency of the approach is shown for recovery of two test items. We show through the CAD model processing an application of the proposed approach to the shape recovery followed by finite element mesh generation and adaptation.

Abstract Issues of digital preservation of shapes and internal structures of historical cultural objects are discussed. An overview of existing approaches to digital preservation related to shape modeling is presented and corresponding problems are considered. We propose a new digital preservation paradigm based on both constructive modeling reflecting the logical structure of the objects and open standards and procedures. Constructive Solid Geometry (CSG) and Function Representation (FRep) are examined and practically applied as mathematical representations producing compressed yet precise data structures, thus providing inter‐operability between current and future computer platforms crucial to archiving. Examples of CSG reconstruction of historical temples and FRep modeling of traditional lacquer ware are given. We examine the application of fitting of a parameterized FRep model to a cloud of data points as a step towards automation of the modeling process. Virtual venues for public access to cultural heritage objects including real time interactive simulation of cultural heritage sites over the Web are discussed and illustrated.

Abstract Shape transformation between objects of different topology and positions in space is an open modelling problem. We propose a new approach to solving this problem for two given 2D or 3D shapes. The key steps of the proposed algorithm are: increase dimension by converting two input kD shapes into half‐cylinders in (k+1)D space–time, applying bounded blending with added material to the half‐cylinders, and making cross‐sections for getting intermediate shapes under the transformation. The additional dimension is considered as a time coordinate for making animation. We use the bounded blending set operations in space–time defined using R‐functions and displacement functions with the localized area of influence applied to the functionally defined half‐cylinders. The proposed approach is general enough to handle input shapes with arbitrary topology defined as polygonal objects with holes and disjoint components, set‐theoretic objects, or analytically defined implicit surfaces. The obtained unusual amoeba‐like behaviour of the shape combines metamorphosis with the non‐linear motion. Copyright © 2004 John Wiley & Sons, Ltd.

New analytical formulations of bounded blending for functionally defined set-theoretic operations are proposed. The blending set operations are defined using R-functions and displacement functions with the localized area of influence. The shape and location of the blend is defined by control points on the surfaces of two solids or by an additional bounding solid. The proposed blending using a bounding solid can be applied to a single selected edge or a vertex. We introduce new types of blends such as a multiple blend with the disconnected bounding solid and a partial edge blend. It is shown to have versatile applications in interactive design.

Function representation (FRep) allows for the construction of quite complex shapes, such as isosurfaces of real-valued functions composed using functionally defined primitives and operations. Calculating such functions in complex cases can be very time-consuming. Interactive extraction and visualization of isosurfaces for them can hardly be imagined. In this paper, we present a method for interactive navigation through a "sculpture garden" containing non-intersecting FRep objects defined in terms of the specialized high-level language HyperFun. Before the actual isosurface extraction and visualization occurs, the objects are voxelized on a regular 3D grid with the possibility of further adaptive voxelization. The polygonization employs a hierarchical representation of the voxelized data and a view-dependent isosurface reconstruction at different levels of detail. To speed up the extraction process, an isosurface is constructed only in the visible part of the data set, with its updates performed incrementally as the observer moves. Due to the low pre-processing costs required for isosurface mesh construction, it is possible to visualize time-dependent objects, if the hardware is capable of calculating the updates in real time.

The paper presents a novel approach for accurate polygonization of implicit surfaces with sharp features. The approach is based on mesh evolution towards a given implicit surface with simultaneous control of the mesh vertex positions and mesh normals.

Abstract The concept of solid texturing is extended in two directions: constructive modeling of space partitions for texturing and modeling of multidimensional textured objects called hypervolumes. A hypervolume is considered as a point set with attributes of both physical (density, temperature, etc.) and photometric (color, transparency, diffuse and specular reflections, etc.) nature. The point set geometry and attributes are modeled independently using real‐valued scalar functions of several variables. Each real‐valued function defining geometry or an attribute is evaluated at the given point by a procedure traversing a constructive tree structure with primitives in the leaves and operations in the nodes of the tree. This approach provides a framework for modeling, texturing and visualization of 3D solids, time‐dependent and multidimensional objects in a completely uniform manner. We introduced a special modeling language and implemented software tools supporting the proposed approach. The concept of constructive hypervolume textures is independent of the geometry representation. We provide examples of textured Frep and BRep objects as illustrations. Copyright © 2002 John Wiley & Sons, Ltd.

There are limitations to the current BRep based "model then animate" paradigm when animating time-dependent (dynamic) objects. This paper describes an approach to modeling dynamic objects directly in space-time or even higher dimensional space. The use of the function representation (FRep) is proposed due to the ease with which it handles higher dimensions. After creating a multidimensional FRep object, it then needs to be mapped to "multimedia" space. In the case of animation this means at least one geometric coordinate must be mapped to a dynamic coordinate (time). A case study is presented to explain the technique and demonstrate its use in the animated metamorphosis between several shapes of differing topology.

The paper focuses on an approach to modeling shapes through the use of evolutionary optimization or genetic algorithms for functionally represented geometric objects. This representation allows us to take into account non-manifold geometry and material distribution inside natural lenses. We use ray tracing as an instrument of the current shape evaluation. We describe a case study of a "four-eyed" fish and discuss problems of using the optimization procedure.

Surface creases provide us with important information about the shapes of objects and can be intuitively defined as curves on a surface along which the surface bends sharply. Our mathematical description of such surface creases is based on a study of extrema of the principal curvatures along their curvature lines. On a smooth generic surface we define ridges to be the local positive maxima of the maximal principal curvature along its associated curvature line and ravines to be the local negative minima of the minimal principal curvature along its associated curvature line. The ridges and ravines are important for shape analysis and possess remarkable mathematical properties. For example, they correspond to the end points of shape skeletons. In this paper we derive formulas to detect the ridges and ravines on a surface given in implicit form. We also propose an algorithm for obtaining piecewise linear approximation of ridges and ravines as intersection curves of two implicit surfaces.

We present our approach to volume modelling which combines volume representations by voxel data and by continuous real functions. We discuss the main differences between direct volume visualization and modelling with voxel data, questions of conversion between two representations including volume reconstruction from contour data. We illustrate the approach by several advanced operations on a volumetric object: set-theoretic operations, sweeping, hypertexturing, feature-based sculpting, splitting, spatial and temporal transformations.

Studies a function representation of point sets swept by moving solids. The original solid-generator is defined by an inequality f(x,y,z,t)/spl ges/0 where x, y, z are Cartesian coordinates and t is treated as the time. 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. In the paper, we did it with superposition of time-dependent affine transformations. To get the function representation F(x,y,z)/spl ges/0 of the swept solid, we apply the concept of an envelope, previously used basically for boundary represented objects. We have reduced the problem of swept solid description to a global extremum search by the t variable. The algorithm for procedural swept solid modeling is discussed. The benefit of our model is that it is applied not only for visualization but allows one to use the swept solid as an argument for other operations. For example, the swept solid can be intersected with other ones that are useful for the implementation of such operations as cutting and drilling. Ordinary texture mapping and hypertexturing can also be applied to it. The possibility of using a functionally defined generator with variable shape allows us to achieve a complexity of swept solids which was hardly possible before.

Abstract This paper presents a novel approach to the reconstruction of geometric models and surfaces from given sets of points using volume splines. It results in the representation of a solid by the inequality f(x,y,z) ≥ 0. The volume spline is based on use of the Green's function for interpolation of scalar function values of a chosen “carrier” solid. Our algorithm is capable of generating highly concave and branching objects automatically. The particular case where the surface is reconstructed from cross‐sections is discussed too. Potential applications of this algorithm are in tomography, image processing, animation and CAD for bodies with complex surfaces.