Construction and Rendering of Implicit Complexes

 

 

 

E. Kartashevaα, V. Adzhievβ, P. Comninosβ, A. Paskoγ, B. Schmittδ

α Institute for Mathematical Modeling, Russian Academy of Science, Moscow, Russia, ekart@imamod.ru
β The National Centre for Computer Animation, Bournemouth University, Poole, UK, {vadzhiev&peterc}@bournemouth.ac.uk
γ Faculty of Computer and Information Sciences, Hosei University, Tokyo, Japan, pasko@k.hosei.ac.jp
δ Computer Graphics Research Institute, Hosei University (Digital Media Professionals), Tokyo, Japan, schmitt_benjamin@yahoo.fr

 

Contents

 

 

 

Abstract:

This paper describes a technology for modelling and rendering of heterogeneous objects containing entities of various dimensionality 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. First, we describe a formal framework for such a hybrid representation and propose a general structure for implicit complexes. Then, we consider in detail how an implicit complex can be described geometrically and topologically along with its associated attributes. The attachment operation which is the main mechanism allowing the construction of implicit complexes is described in detail. Two types of rendering algorithms for implicit complexes using polygonization and ray-tracing are also described. Finally, we present some examples illustrating the proposed methods and algorithms.

Categories and Subject Descriptors (according to ACM CCS): I.3.5 [Computer Graphics]: Curve, Solid, and Object Representations; I.3.7 [Three-Dimensional Graphics and Realism]: Ray-tracing

 

 

1. Introduction

 

Heterogeneous object modelling is becoming an important research topic in different application areas such as volume modelling and rendering, modelling of objects with multiple and varying materials in CAD and rapid prototyping, representing results of physical simulations, geological and medical modelling. Such objects are heterogeneous from two points of view: their internal structure and dimensionality. Varying materials and other attributes of an arbitrary nature constitute a heterogeneous internal structure. A dimensionally heterogeneous object in 3D space can include elements of different dimensions (points, curves, surfaces and solids) combined into a single entity from the geometric point of view (i.e. a point set) and the topological point of view (i.e. a cellular complex). A model of a flower can be considered as a typical cellular complex with a 3D receptacle, 2D petals, 1D filaments [KIP*03], and attributes defining its colour distribution.

A model of objects with fixed dimensionality and heterogeneous internal structure (multidimensional point sets with multiple attributes or so-called constructive hypervolumes) was proposed in [PAS*01]. This model uses real functions of point coordinates (scalar fields) to represent both the object geometry and its attributes. The hybrid cellular-functional model [AKK*02] allows for representing a heterogeneous object as a cellular complex with both explicit and implicit cells (cellular domains) of different dimension. Such an object is called an implicit complex, which is defined as the union of properly joined cellular domains. Explicit cells can be represented as parametric surfaces, parametric curves, and point lists. Implicit cells can be implicit surfaces and their patches, intersection curves of implicit surfaces, or functionally represented (FRep) solids [PAS*95].

An important, yet largely unexplored, problem is concerned with the conformity between the object’s geometry and its attributes representing its non-geometric properties. If there are some singularities in the distribution of some non-geometric properties (e.g. material and medium boundaries or load application points), then there is a need for consideration of some real or imaginary geometric elements, perhaps with different dimensionality, which only serve to describe those non-geometric properties. Note that introducing such subsidiary elements can change the topology of the model. For instance, when we deal with a heterogeneous model such as a pot with water containing a heating element immersed in it, we may need to consider a dynamic interaction between different surfaces (3D pot, water, heater – can be in the form of 2D spiral, boiling 2D bubbles growing on the spiral, floating to the water surface and once there bursting). Such a model assumes dealing with a complex and dynamically reconfigurable scene consisting of many structurally different components but unified into a single model.

In this paper, we describe a technology for modelling and rendering of heterogeneous objects in the form of implicit complexes. First, we introduce a general structure of implicit complexes. Then we consider in detail how they are constructed. Two types of rendering algorithms for implicit complexes using polygonization and ray-tracing are also described. Finally, we present some examples illustrating the proposed methods and algorithms.

 

 

 

 

2. Related works

 

In this paper, we consider a hybrid model combining the advantages of cellular and functional representations of objects, which are heterogeneous in their topology, dimension, material and other attributes representing non-geometric properties. Below, we briefly discuss approaches for modelling dimensionally heterogeneous objects using various cellular representations and previously published work on modelling objects with varying distribution of material and other attributes.

A typical technique for describing heterogeneous objects is to represent them as collections of homogeneous components. Thus, a set of primitives homogeneous in their descriptions is used in computer graphics to define complex geometric shapes. To describe complex topology, different spatial subdivisions, topological stratifications [MRG00, Ros94] and complexes [OK01, PBC*93, GRF03] have been used. Strata and elements of complexes are homogeneous in their topological properties. Types of stratifications and complexes differ in the constraints imposed on the topology of their elements and on the connections between these elements.

Topological complexes and their construction methods are discussed in a number of publications on shape modelling and solid modelling. Multidimensional simplicial complexes are used in [PBC*93] for dimension-independent geometric modelling for various applications. A Selective Geometric Complex (SGC) [RO90] is a non-regularised non-homogeneous point set represented through enumeration as the union of mutually disjoint connected open subsets of the real algebraic variety. A SGC provides a framework for representing objects of mixed dimensionality possibly having internal structures and incomplete boundaries. The Djinn API for solid modelling [ABC*00] is based on objects partitioned in a cellular way and containing mutually disjoint cells which are manifold point-sets of differing dimensionality in 3D. In [GH95] an extension of B-spline surfaces to surfaces of arbitrary topology is proposed. Polyhedral complexes are used to describe the surface topology. A procedure for designing cellular models based on CW-complexes with the emphasis on the topological validity of the resulting shapes is considered in [Kun99, OK01].

To specify non-geometric properties of objects, spatial subdivisions are also used in computer graphics and in finite element analysis (FEA) as the underlying structures for piecewise analytical descriptions of attribute functions. Usually a basic topological subdivision is selected, which can be described by a topological stratification [ABC*00, RO90], a cell complex [KBD*99, CDM*02], or a voxel model [CT00]. Different types of functions can be used to describe attributes [JLP*99, PCB01, ST02].

Another approach to modelling heterogeneous objects is based on using real functions of point coordinates. For example, the constructive hypervolume model [PAS*01] supports uniform constructive modelling of point set geometry and attributes using such functions. However, this model is homogeneous from the object topology description point of view. Then a theoretical framework combining a cellular representation and a constructive function representation has been proposed [AKK*02]. An independent cellular and functional representation of the same object is useful, but not enough in certain applications. For example, in the above mentioned flower model, each dimensionally homogeneous component (3D receptacle, 2D petals, 1D filaments) can be functionally represented. However, without additional information one cannot separate individual functions for the components from the single function describing the entire object. This additional information about objects components, their dimensions, and attachments to each other are used in applications such as finite element mesh generation, animation, and rendering. The above was the motivation for introducing in [AKK*02] a hybrid cellular functional model based on the notion of an implicit complex, which allows the flexible combination of cellular and functional object geometry models and attribute models. In the current paper, we examine in more detail the construction of implicit complexes and describe algorithms for the discretization and rendering of heterogeneous objects represented in this form.

 

 

3. Implicit Complexes: the Theoretical Framework

Here we provide a systematic description for theoretical framework for representation of implicit complexes.

 

3.1 A Hybrid Representation of Geometry

The hybrid geometrical model of heterogeneous objects presented in [AKK*02] combines a cellular representation and a constructive representation using real-valued functions. Formally, the hybrid representation for a geometric object  is defined as follows:
:
where is a modelling space and  is an implicit p-dimensional complex. The definition of an implicit complex is based on the concepts of cellular spaces and CW-complexes [FK97, Mas67]. A CW-complex provides a general representation for different topological complexes including polyhedral and cellular complexes.

Let us outline the formal framework that we are going to use herein after. A geometric object D is defined as a closed cellular space (domain) and can be represented as a carrier of a CW-complex K such that D=|K|. This implies that the CW-complex defines a topological subdivision of the object D and . Reflecting the requirement of representing a number of homogeneous components forming the heterogeneous object, we consider a union of subcomplexes of the CW-complex, where each subcomplex corresponds to a homogeneous component. So one can introduce  with the following properties: (1) ; (2) the intersection of any two subcomplexes  satisfies the condition that either or . We assume that all the subcomplexes are closed.

By definition, for each subcomplex one can specify the point set , which is the carrier of the subcomplex. So  and  is a subset of . Thus with respect to the domain  one can construct the set of subdomains  that corresponds to the set of subcomplexes  introduced above. By analogy with conditions (1) and (2) for , one can formulate the following conditions for : (1); (2) for any two  either or .

So the hybrid representation scheme can be defined in the form of the pair represented through union operation as , and we can use different representation schemes for various  pairs. Suppose that for some subdomains we use the cellular representation. Such subdomains and their subdivisions are called explicit and are denoted by and . Then for the other domains, denoted by, we use FRep; so their cellular representation denoted by  is not necessarily known but can, in principle, be defined using some method. We call such domains as well as their subcomplexes implicit. Then the point set D is represented as the union , and the complex K is also represented as the union of the corresponding explicit subcomplexes  and the implicit subcomplexes . Thus, . Note that the complex containing implicit subcomplexes is also called implicit.

 


a                                                     b                                                            c

Fig. 1. Examples of subdivisions
a) 2D subdomains (rectangles abcd, lefm, gefk), 1D subdomains (polyline gefk, segment gk) and 0D subdomains (points g, k)
b) 2D subdomain (rectangle abcd ), 1D subdomains (segments ke, eg ) and 0D subdomains (points e, g, k)
c) 2D subdomains (rectangles abcd, gkfe) and 1D subdomain (contour gkfe)

A cellular complex derived from an implicit one can be defined ambiguously, but even in such a case it has to be conformed to other subcomplexes of K. This implies that it is necessary to impose constraints on the domains boundaries similar to those for subdomains. So in addition to the constraints (1) and (2) specified above, the following conditions must hold true: (3) for any  either or ; (4) for any  either or where the symbol  denotes a boundary. If the conditions (1) to (4) are satisfied, subdomains can overlap each other and some subdomains can be located inside the others. Fig. 1 shows examples of such subdivisions.

 

 

 

3.2 A Formal Definition of Implicit Complexes

Despite the fact that the internal structure of implicit subcomplexes are not detailed, their relationships to each other and to the explicit subcomplexes are defined and well-structured. This allows us to consider any implicit subcomplex as an implicit cell of the complex K. In the general case, a p-dimensional implicit complex  is expressed as , where  are cells of all the explicit subcomplexes of  and  are implicit cells such that each  is the point set coinciding with the carrier of an implicit subcomplex of  . So for any  there exist such that .

Explicit cells  are defined with respect to the definition of the CW-complex. So they are relatively open point sets of the modelling space and the intersection of any two explicit cells is empty. The shape of each explicit cell  is defined by a characteristic mapping, and its boundary is mapped onto a subcomplex  with dimensionality . Note that the subcomplex  contains only explicit cells that satisfy the definition of the CW-complex. Each implicit cell  is a closed point set defined by an FRep. The boundary of implicit cell  is not necessarily mapped onto any subcomplex of and can contain both explicit and implicit cells. Cells of the implicit complex  satisfy the same conditions as the subdomains of D. Explicit cells are indivisible elements of a subdomain subdivision containing no other cells. However as each implicit cell describes the entire subdomain which can contain other cells, we allow some cells of an implicit complex to lie inside implicit cells of the complex.

 

 

3.3 Reduction to Cellular Complexes

Let us show how an r-dimensional implicit complex can be reduced to a cellular one. We assume that each implicit cell  (where ) can be discretized. The corresponding methods was described in detail in [KAP*03]. The discretization of an implicit complex is an iterative process. At each step we subdivide one implicit cell and replace it in  with the explicit subcomplex . This process repeats until there are no implicit cells left in. We subdivide implicit cells in order of increasing dimensionality. Moreover for two implicit cells  such that the cell  contains the cell () the cell  has to be discretized before .

So when we start to subdivide cell we already know what explicit cells of  lie inside and on the boundary of . Let explicit subcomplex () include all the boundary cells of and explicit subcomplex () contain all the cells belonging to the interior of . Subdivision of each implicit cell  includes the following steps: (1) discretization of the cell and generation of the cellular complex ; (2) refinement of the complexes  and  for making the complexes compatible by subdividing their cells in order of increasing dimensionality (a solution and proof of existence of such a refinement process were discussed in detail in [RO90]). After this step, the complex transforms to the complex ; (3) subdividing the cells of the complexes  and  in order of increasing dimensionality for making the complexes compatible. After these steps we get the complex which is compatible with the refined complex , so we can replace with . The proposed reduction algorithm guarantees that any implicit complex can be converted into a cellular one.

 

4. The Implicit Complex Description

 

Here we provide a detailed description of a 3D implicit complex structure, namely the topology of the complex, the geometry of its cells and the attributes defined on it.

 

 

4.1 The Topology Description

Implicit complex topology is described by relations between its elements. By definition, a 3D implicit complex  consists of 0D, 1D, 2D and 3D cells. Let  be a set of -dimensional cells . Such a set contains both explicit and implicit cells. Let us consider in more detail the main relations defined on a 3D implicit complex, namely the boundary relation and the “to contain” relation. They establish relationships between cells of different dimensionalities.
Denote by  the boundary relation between p-dimensional and s-dimensional cells, , . Pair () belongs to   if  is a proper face or boundary element of the cell that is belongs to the boundaryof . So altogether six different boundary relations can be defined. Denote the relation “to contain” by , , . Pair  belongs to if  and . The whole structure of 3D implicit complexes is described by nine different “to contain” relations.

The boundary and “to contain” relations are formed in the process of the implicit complex construction through adding new cells and describing their shapes. They serve as a basis for defining others relations between the elements of the complex and are used to define various operations on the implicit complexes and the HRep objects. For example, the coboundary relation and the relation “to be contained” denoted respectively by and  can be defined as   and .

Then we can introduce incidence and adjacency relations. Two cells are incident if one of them is a proper face of another or if one of them contains another. Two cells of complex are adjacent if there exists another cell in the complex which is incident to both these cells. Thus one can reach the conclusion that only boundary relations and the relations “to contain” need to be stored explicitly and that all other relations can be derived from these.

 

4.2 0D Cell Description

An explicit cell  is described by its coordinates. An implicit cell  is defined in FRep with an inequality of the form . In  space, the function for 0D cells (points) can be described using functions representing the intersection of three surfaces, the intersection of a curve and a surface, or directly as , where d is the distance from a given point X0. An implicit cell  can be also described as an image of a point functionally defined in 2D space.

4.3 1D Cell Description

An explicit 1D cell  is defined by a characteristic mapping, which maps the segment  in the space of the real parameter into a curvilinear and perhaps a closed segment in the  space. Functions  are similar to those traditionally used in CAD for the representation of curve segments. The end points of the segment  are mapped onto 0D cells ,  which are related to the 1D explicit cell , so  and .
An implicit cell  can be described in two ways. It can be defined as an FRep object in  by an inequality of the form . In such a case, the 1D cell takes the form of an arbitrary curve defined as the intersection of two surfaces in . Alternatively, the cell  can be represented as an image of an FRep curve described in 2D space  by an inequality of the form , where . This mapping is given by a function of the form .

 

 

4.4 2D Cells Description

Explicit 2D cells are represented as images of triangles and quadrilaterals resulted after characteristic mapping. For each cell , we define the characteristic mapping , which takes the rectangle  in the parameter space and maps it onto a surface patch in . A variety of parametric surface patch representations can be used for defining the mapping (i.e. Coons, Bezier, NURBS or other patches). The function has to map the boundary of  onto the union of explicit cells with dimensionality , which form the boundary of the cell  in the complex.

An implicit 2D cell  can also be described in two ways. It can be defined in FRep in  by an inequality of the form . Alternatively, one can use a functional description of the form  in  with the subsequent mapping of the form .

 

4.5 3D Cells Description

To represent an explicit 3D cell, a variety of maps of the form  can be used to describe the shape of curvilinear polyhedrons. Such maps are extensively used in describing finite element sets. It is also necessary to keep boundary conditions. So the maps have to provide attaching 3D cells to their boundary cells in the complex. Once again, an FRep of the form  is used to describe the implicit cell .

 

4.6 Attribute Description

To describe the non-geometric properties of a heterogeneous object, represented by an implicit complex, we use the cellular-function model of attributes introduced in [AKK*02]. Each attribute  is defined by a function of the form , where  is a set of attribute values (which can be a vector or tensor space).  is embedded into a real-valued space of a proper dimension mi. Thus,. Attributes assigned to an implicit complex K are described by functions  in a piece-wise manner, i.e. .

Each local function  can be either a separate function defined on a single cell of the complex  or a restriction of a more general function defined on several cells of  or on the entire modelling space.

 

5. Implicit Complex Construction

In this section we give a systematic account of the construction of an implicit complex (IC). In general we proceed as follows. To create the IC, it is necessary to describe the shapes of all its elements and to specify all the boundary and the “to contain” relations between its elements. To generate the IC, the attachment operation is introduced allowing the creation of the IC in a component-wise manner, in order of increasing dimensionality of its components. The nature of this process is both constructive (i.e., it can be described in the form of constructive tree) and iterative (i.e., it is repeated time and again until the IC is completely defined).

We start with an empty complex , and then at each construction step i we attach a new component  to the already formed subcomplex , thus creating a new complex  which is a subcomplex of the target complex. Note that both a separate cell and the entire complex (containing a set of cells) can serve as a component being attached. Accordingly, we introduce two types of attachment operation: cell attachment and complex attachment. These operations are based on the attachment operation introduced for CW complexes [Kun99, OK01].

 

5.1 The Cell Attachment Operation

This operation assumes that at each step i of the process another cell  is attached to the complex . First we define the shape of this cell using one of the methods described above. Then, we have to modify the relations. So for all implicit and explicit cells  lying on the boundary of we add the pairs  to the boundary relations  (where ). Then for each implicit cell  (where ) that contains  we have to add the pair  to the “to contain” relation  (where). Finally, only if is an implicit cell, for all implicit and explicit cells  (where ) lying inside  we add the pairs  to the “to contain” relation  (where ). The shape of implicit cells is described independently of its relations with other cells of the complex. So, implicit cells can be attached to the complex in random order.

 

5.2 The Complex Attachment Operation

The procedure of attaching the complex  to the complex  results in the union of two complexes. This operation is valid only for properly joined complexes. Assuming that  is properly joined to the complex  that is (where C is a subcomplex of both and ). Thus we have to create a complex , . First, we define an attachment map  that relates the equivalent cells of the initial complexes. Then, we obtain the sets of the complex as quotient sets of the union of the corresponding sets of the initial complexes by the quotient map  as follows:,  (). Each cell has its prototype , such that or  or  belongs to both the complexes. Next, we define the boundary and “to contain” relations of the complex . We set that for any cells the pair belongs to or to if  the pair of their prototypes  belongs to the corresponding relation of the complex  or

 

6. Examples and Discussion

In this section we provide two examples to illustrate the principles and discuss the results of the proposed approach.

6.1 The Flower Model

Let us consider a flower fragment consisting of the receptacle, the pistil, a petal and a stamen (Fig. 2). The receptacle is described by the 3D cell , the pistil – by the 3D cell , the stamen – by the 3D cell , the filament is described by the 1D cell , and the petal is described by the 2D cell . We assume that the RGB colour attribute is described by the function  in a piece-wise manner, so that .

Altogether, the complex  describes the entire heterogeneous model of the flower and includes the following cells of various dimensionalities (with the assigned attribute functions being specified in brackets):


Fig. 2. The Heterogeneous ‘Flower’ model.

Let us provide a more detailed description of all the introduced cells. The 3D cells , () are described functionally by the inequalities . The cell  represents the disk that is the intersection of the cylindrical solids and . This cell is described by the pair . The inequality defines a disk in 2D space, and the map  can be given as , whereis the matrix of the affine transformation.

The 0D cells , ,  are defined by their Cartesian coordinates:  where i=1,2,3. These coordinates are set with according to the constraints of the form , ,,  because the 0D cells lie on the boundaries of the 3D solids.

The 1D explicit cell describes the boundary of the disk . To define  we use the following characteristic map: , . The function  is the subject of the following boundary constraint: . The 1D cell  is given by their characteristic map, for instance, where  are vector coefficients defining the shape of the curve. The following conditions must be satisfied to guarantee the attachment to the end nodes:
,

The implicit cells , ,  and  altogether describe the model of the petal. We describe the 2D cell  as , where  is the function defining the object on the  parameter plane, and  is its map taking it to . The following system of constraints: is imposed for the cell . In the functional form it is equivalent to the description of the cell  in the form , where  and denotes R-function defining the set-theoretic intersection. Therefore, the cell  is described in the implicit form as . In the same way the following system of constraints for the nodes represented by 0D cells  и  can be derived:

To distinguish two different points satisfying this system of constraints we introduce an additional constraint for  and  for , where defines a signed distance from some separating line on the UV plane. Finally, the 0D cells , 

 

6.2 The Pot Filled with Water Model

In this subsection we give an example of an implicit complex with nested cells. Let us consider a 2D heterogeneous object shown in Fig 3a. This object can be represented as a carrier of the implicit complex which includes the following cells: . All the implicit cells are described within the FRep framework by the functions . All the 0D explicit cells are defined by their coordinates and all the 1D explicit cells are represented as segments of parametric curves.

   
(a)                                                (b)

Fig. 3. a) The pot filled with water model with nested cells and b) The 2D cells extracted

Let us consider in detail the description of the implicit cells. Implicit cell  represents a pot. This cell is defined by function. Cell   represents a disk described implicitly in the form . The extracted implicitcells are shown in Fig. 3b and Fig 4. We assume that the cell  is defined as the intersection of the cell  with some 2D solid represented by the inequality  so .

In this case the function  takes the form . Then the functions defining the 0D and 1D implicit cells are defined on the basis of the description of the 2D cells as follows:
;
; ;

Note that each of the cells ,  and  consists of two disconnected components. This does not contradict the implicit complex definition and is useful in some applications (e.g., rendering). However, if it is necessary to provide simple connectedness, then one can introduce additional subdividing objects. The attributes here are defined though their RGB colour components

Fig. 4. The pot filled with water: the 0D and 1D cells extracted.

 

6.3 Discussion

Note the important distinctions between the proposed approach and the previously known frameworks for describing heterogeneous models. The models described in SGC [RO90] and STC [Ros97] also make use of subcomplexes derived from the basic cellular subdivision of the heterogeneous object. However, they first require the explicit building of the cellular subdivision of the modelling space and then use this to describe the subcomplexes representing the components of the object. In our framework the internal structure is described only for those components which really require such a detailed cellular representation. Other components are described using only the FRep of the corresponding point sets.

The models described in [ABC*00, MRG00] make use of the topological stratification. Our framework does not need to exploit stratification-based structures since no strong topological restrictions on the subdomains that can be dimensionally heterogeneous non-manifolds are imposed. The main criterion for the choice of the subdomains is based on the specifics of their mathematical description. However, the proposed framework can be used to describe the topological stratification structures provided that the subdomains forming the object subdivision are manifolds with the topological homogeneity.

Also note that, as the example in 6.2 demonstrates, nested cells are valid within our framework. This means that cells can intersect each other or lie inside other cells. For instance, in that example one part of the disc is inside the water and another is outside. To deal with such a model, we may either break the disk into two parts by removing the whole disk from the complex or subdividing the disk into two parts without deleting the whole disk. The latter case allows us to deal simultaneously both with the disk as a whole and with its parts and it is perfectly valid within the implicit complexes framework. Moreover, this allows for a flexible reconfiguration of the components of the model that promises interesting animation applications.

 

 

7. Rendering Implicit Complexes

In this section, we describe rendering algorithms for individual cells and for implicit complexes composed of cells of various dimensions and not fully opaque cells.

7.1 Rendering Individual Cells

Several techniques are known for rendering cells of different dimensions. Explicit cells in the form of parametric curves and surfaces, and polygonal meshes are widely used in CAD systems and computer graphics in general. Similarly, several algorithms exist for rendering 3D implicit cells. If we are only interested in the surface of the object (and thus assumes the object to be fully opaque), polygonization [LC87, PAS88], ray tracing [Blo97], or splatting [ZPvB*01a] algorithms are available. If we are only interested in a volumetric visualization assuming that the object can be defined with a variable opacity, several volume rendering techniques can be used, such as volume tracing [MPW*00] and volume splatting [ZPvB*1b].

The main difficulty is to render 1D and 2D implicit cells. In the case of a functional description in 2D space and subsequent mapping to 3D space (see section 4), existing tools can be used to extract the planar iso-contour or iso-surface of the cell. Here, we consider another case of 2D cells defined as trimmed implicit surfaces [Pas98] by the intersection of a carrier implicit surface fc(x) =0 and a trimming solid fs(x)≥ 0, where fc and fs are defining functions of some 3D FRep solids. Below we describe extensions of polygonization and ray-tracing algorithms for 1D and 2D implicit cells based on such a trimming operation.

7.2 Polygonization of 2D and 1D Implicit Cells

The algorithm, which we propose for the visualization of 2D implicit cells as trimmed implicit surfaces, is composed of two steps. The first step is the traditional polygonization of a carrier implicit surface defined by the function fc. The polygonization generates a set of triangles approximating the carrier implicit surface. The following procedure is applied to each triangle. The defining function fs of the trimming solid is evaluated at the vertices of the triangle. If the three function values at the triangle vertices are negative, the triangle is completely outside the trimming solid and thus it is removed. A triangle with three positive function is completely inside the trimming solid and thus it is preserved. If the function values have different signs, the triangle intersects the trimming solid and an adaptation procedure is applied to it.

In latter case, the adaptation of the triangle can be done as in [Pas98], where the triangle is recursively subdivided. The main drawback of this approach is that it may lead to a quite large number of triangles. A simpler but yet efficient solution is to perform a search for the intersection point along the edges of the triangle. A simple binary search along the edge is performed to find the zero point of the defining function fs of thetrimming solid. In the case where only one vertex of the triangle has a negative function value, the two vertices with positive function fs values are removed, and two new vertices are added, corresponding to the computed zero points of the function fs along the two edges, and the initial triangle is replaced by a new triangle. In the case where only one vertex has positive function value, a vertex is removed, two new vertices are computed, and two new triangles replace the original triangle.

A 1D implicit cell can be defined as an intersection curve of the carrier implicit surface and the trimming surface. To polygonize such a curve, the above algorithm can be applied with minimal changes. The processing of the second case, when the three function values are positive needs to be modified. Instead of preserving the triangle, we discard it. While in the third case, instead of creating a new triangle, we only create a line segment, whose extremities are defined as the roots resulting from the search along the edge. Fig. 5 shows an example of trimming an implicit surface. In Fig. 5a, a carrier surface is shown modelled as a tapered and twisted ellipsoid blended with a block. In Fig. 5b, a trimming solid is shown, which is defined as a set-theoretic combination of twisted and tapered cylinders. Figs. 5d and 5e show the polygonized intersection curves and the polygonized trimmed surface respectively.

Fig. 5. Trimming an implicit surface (a) the carrier surface; (b) the trimming solid; (c) 2D cells: the ray-traced trimmed surface; (d) 1D cells: polygonized intersection curves; (e) 2D cell as a polygonized trimmed surface.

 

7.3 Ray Tracing Trimmed Implicit Surfaces as 2D Cells

Here, we consider only ray tracing of 2D implicit cells defined as trimmed implicit surfaces by given carrier surfaces and trimming solids (see example in Fig. 5c). The ray tracing algorithm for implicit surfaces [Blo97] is used as a framework, and is slightly modified. We use a sign function δ, equal to -1 or 1, to help to determine whether a point is on the carrier surface or not. The sign function δ is first set to 1. As the carrier surface is defined using an FRep model, we assume that the defining function of the object fc is negative outside the object. The first intersection point P of the ray with the surface is found when δ× fc≥0. For the intersection point P, the defining function fs of the trimming solid is evaluated.  If fs(P) ≥0, then P belongs to the carrier surface and to the trimming solid. The next ray is cast if the surface is fully opaque, or if the surface is not fully opaque, colours and opacity are accumulated, and the next step is performed along the current ray. In the case where P does not belong to the trimming solid, or in the case of a not fully opaque surface, then the sign function δ is set to –δ, and the ray marching continues (using the defining function δ× fc≥0). The ray marching stops when the termination conditions are met (i.e., when the ray exits the bounding box, or full opacity is reached).

 

7.4 Rendering Techniques for Implicit Complexes

Using the rendering techniques presented above and others that can be found in the literature, one can render any explicit or implicit cells. Below, we assume that the implicit complex contains cells with different opacity values. In the case of fully opaque cells, these can be rendered individually and combined together with the standard use of an appropriate Z-buffer. The example shown in Fig. 6 has been rendered with a ray tracing algorithm similar to the one proposed in [Blo97] extended to support trimmed implicit surfaces as described above and a Z-buffer. This implicit complex corresponds to the example from section 6.1. Each cell of the implicit complex was rendered individually. The filaments were explicitly defined as spline curves (1D cells). The stamen was modelled as a 3D cell defined as an algebraic sum of an ellipsoid and a solid noise function (Gardner’s solid noise). The pistil and receptacle were also defined as 3D cells using real values functions (mainly ellipsoids and solid noise) and a bending operation for the carpel. The petals (coloured yellow and magenta) and the sepals (coloured green) were 2D cells, defined in a 2D space and mapped to 3D space using characteristic maps. 2D and 3D cells were defined using the constructive hypervolume model. The attributes were the colour and the opacity. The opacity was constant for all the cells, and the function defining the colour variation was based on a procedural texture.

 

Fig. 6. Rendering an implicit complex. Different views of a flower model made of 1D, 2D and 3D cells.

In the case of cells with different opacity values, a single Z-buffer is not enough, and direct visualization techniques (polygons and graphic hardware) can not be used. Indeed, not only a z-value has to be stored, but rather z intervals, in order to properly accumulate the opacity for a correct blending operation. Note that the order for rendering cells depends on their dimension. Therefore, to render implicit complexes, volume rendering techniques [MPW*00] are also required, in addition to surface rendering techniques.

Explicit or implicit 1D and 2D cells are rendered first using traditional surface rendering techniques (see previous subsections), as well as 3D explicit cells. Given a ray, all the z intersections have to be stored for each cell (a cell can intersect the ray several times). In the case of explicit 3D cells, z intervals are stored. It is sufficient to store only the set of z intervals for a 3D explicit cell, as inside such a cell opacity is constant by definition. At this stage of the rendering process, for the given ray several z values and z intervals along with the information that indicates the correspondence of the z value with its cell are stored.


(a)

(b)                                       (c)  

Fig. 7.(a) Rendering an implicit complex composed of cells of different dimension and semi-opaque cells. (b) 2D implicit cell defined as a trimmed surface. (c) Trimmed line and cell resulting from the intersection of the trimmed surface shown in (b) and the water model inside the pot.

Then, 3D implicit cells are rendered, depending on the stored values, with a volume rendering technique based on ray tracing. Using the previously stored information, z testing along the ray, one can determine if the current opacity and colour is accumulated depending only on the 3D implicit cell or whether the colour and opacity of another cell has to be used for the given point. In the case of cells of a dimension lower or equal to 2, their colour and opacity are accumulated directly instead of the attribute values of the 3D implicit cell. In the case of 3D explicit cells, their attributes are accumulated along the stored z-interval. The z test along the ray and therefore the accumulation is performed until the traditional termination conditions have been met.

Fig. 7a shows an example of rendering of an implicit complex that contains cells of various dimensions and of various opacities. It also illustrates the theoretical example proposed in 6.2, extended to 3D cells. The implicit 3D cells correspond to the grey cylinder and the pot-shape object. The colour of the object is based on Perlin’s noise function. The opacity varies along the vertical axis. Note that inside the pot there is a blue area (representing the water). This area, on the base of the constructive hypervolume model, is defined as a half-ellipsoid combined with a noise function. The 2D implicit cell is defined as a trimmed surface, namely an Escher’s spiral defined as a sphere surface trimmed by four swept solids. There are also 1D explicit cells shown in red Fig. 7a that connect the 2D implicit cell and the 3D implicit cells (i.e., the cylinder). The 1D cells, shown in blue in Fig. 7c are defined as the intersection of the Escher trimmed surface and the iso-surface corresponding to the water.

 

Conclusion

 Implicit complexes make it possible to combine a cellular representation and a constructive function representation into a uniform model. In this paper, we have described the theoretical framework and the practical techniques of construction and rendering such models. The general structure of an implicit complex and attachment operations were presented in detail and illustrated.For rendering, polygonization and ray-tracing algorithms for 2D and 1D cells in the form of trimmed implicit surfaces were described. The general algorithm for rendering of implicit complexes including opaque and semi-transparent cells of arbitrary dimensions was proposed and illustrated.

Future work directions include the development of specific operations applicable to entire implicit complexes, an extension of the model to time-dependent implicit complexes, and further development of the multidimensional version of the model and its applications, and implementation of a specialized modelling language.

 

References

[ABC*00] Armstrong C., Bowyer A., Cameron S. et al.: Djinn. A Geometric interface for solid modeling. Information Geometers, Winchester, UK, 2000.

[AKK*02] Adzhiev V., Kartasheva E., Kunii T., Pasko A., Schmitt B.: Hybrid cellular-functional modeling of heterogeneous objects, Journal of Computing and Information Science in Engineering, Transactions of the ASME 2, 4 (2002), 312-322.

[Blo97] Bloomenthal J. et al.: Introduction to Implicit Surfaces. Morgan Kaufmann, 1997.
[CT00] Chen M., Tucker J.: Constructive volume geometry. Computer Graphics Forum 19, 4 (2000), 281-293.
[CDM*02] Cutler B., Dorsey J., McMillan L., Mueller M., Jagnow R.: A procedural approach to authoring solid models. In Proc. SIGGRAPH’02, ACM TOG 21, 3 (2002), 302-311.
[FK97] Fomenko A.T., Kunii T.L.: Topological modeling for visualization, Springer-Verlag, Tokyo and Heidelbrg, 1997.
[GRF03]. García, Á, Ruiz de Miras J., Fieto F.: Free-form solid modelling based on extended simplicial chains using triangular Bézier patches. Computers & Graphics 27, 1 (2003), 27-39
[GH95] Grimm C.M., Hughes J.F.: Modeling surfaces of arbitrary topology using manifolds. In Proc. SIGGRAPH '95, (1995), Vol. 29, 359-368.
[JLP*99] Jackson T., Liu H., Patrikalakis N., Sachs E., Cima, M.: Modeling and designing functionally graded material components for fabrication with local composition. Control, Materials and Design 20, 2/3 (1999), 63-75.
[KAP*03] Kartasheva E., AdzhievV.,Pasko, A., Fryazinov O., Gasilov V.: Surface and volume discretization of functionally-based heterogeneous objects. Journal of Computing and Information Science in Engineering, Transactions of the ASME 3, 4 (2003), 285-294.
[Kun99] Kunii T.: Valid computational shape modeling: design and implementation. International Journal of Shape Modeling 5, 2, (1999), 123-133.
[KIP*03] Kunii T.L., Ibusuki M., Pasko G., Pasko A., Terasaki D., Hanaizumi H.: Modeling of conceptual multiresolution analysis by an incrementally modular abstraction hierarchy. Transactions of Institute of Electronics, Information and Communication Engineers E86-D, 7, (July 2003), 1181-1190.
[KBD*99] Kumar V., Burns D., Dutta D., Hoffmann C.: A framework for object modeling. Computer-Aided Design 31, 9, (1999), 541-556.
[LC87] Lorensen W., Cline H.: Marching cubes: A high resolution 3D surface construction algorithm. In Proc. SIGGRAPH ’87 (1987), Vol. 21, 163-169.
[Mas67] Massey W.S.: Algebraic topology: An introduction. Harcourt, Brace&World, Inc., New York-Chicago-San Francisco-Atlanta, 1967.
[MPW*00] Meissner M., Pfister H., Westermann R., Wintenbrink C.M.: Volume visualization and rendering techniques. Eurographics’00 Conference Tutorial, 2000.
[MRG00] Middleditch A., Reade C., Gomes A.: Point-sets and cell structures relevant to computer aided design. International Journal of Shape Modeling 6, 2, (2000), 175-205.
[OK01] Ohmori K., Kunii T.: Shape modeling using homotopy. In Proc. International Conference on Shape Modeling and Applications, IEEE Computer Society, 2001, 126-133.
[PCB01] Park S. M., Crawford R., Beaman J.: Volumetric multi-texturing for functionally gradient material representation. In Proc. Sixth ACM Symposium on Solid Modeling and Applications, D. Anderson, K. Lee (Eds.), ACM Press, 2001, 216-224.
[PAS88] Pasko A., Pilyugin V., Pokrovskiy V.: Geometric modelling in the analysis of trivariate functions. Computers and Graphics 12, 3/4 (1988), 457-465.
[PAS*95] Pasko A., Adzhiev V., Sourin A., Savchenko V.: Function representation in geometric modeling:  concepts, implementation and applications. The Visual Computer 11, 8 (1995), 429-446.
[Pas98] Pasko A.: On Escher's spirals - polygonization of 2-manifolds with boundaries. In Proc.Implicit Surfaces '98, Eurographics/ACM SIGGRAPH Workshop, J. Bloomenthal and D. Saupe (Eds.), University of Washington, Seattle, USA, 1998, 77-80.
[PAS*01] Pasko A., Adzhiev V., Schmitt B., Schlick C.: Constructive hypervolume modeling. Graphical Models 63, 6 (2001), 413-442.
[PBC*93] Paoluzzi A., Bernardini F., Cattani C., Ferrucci V.: Dimension-independent modeling with simplicial complexes. ACM TOG 12, 1 (1993), 56-102.
[Ros94] Rossignac J.: Through the cracks of the solid modeling milestone. From Object Modelling to Advanced Visualization, Eds. S. Coquillart, W. Strasser, P. Stucki, Springer Verlag, 1994, 1-75.
[Ros97] Rossignac J.: Structured Topological Complexes: A feature-based API for non-manifold topologies. In Proc. the ACM Symposium on Solid Modeling, 1997, 1-9.
[RO90] Rossignac J., O’Connor M. SGC: A dimension independent model for pointsets with internal structures and incomplete boundaries. In Geometric modeling for product engineering, ed. by M. Wozny, J. Turner, K. Preiss, 1990.
[ST02] Siu Y.K., Tan S.T.: “Source-based” heterogeneous solid modeling. Computer-Aided Design 34, (2002), 41-55
[ZPvB*01a] Zwicker M., Pfister H., van Baar J., Gross M.: EWA volume splatting. In Proc. IEEE Visualization ‘01, San Diego, October 2001, 29-36.[ZPvB*1b] Zwicker M., Pfister H., van Baar J., Gross M.: Surface splatting. In Proc. SIGGRAPH ‘01, 2001, 371-378.