HETEROGENEOUS OBJECTS MODELLING AND VISUALIZATION USING IMPLICIT COMPLEXES

E. KARTASHEVAa, V. ADZHIEVb, P. COMNINOSb, A. PASKOb, B. SCHMITTc

 a  The Institute for Mathematical Modeling, Russian Academy of Science, Moscow, Russia

b The National Centre for Computer Animation, Bournemouth University, Poole, UK
c Computer Graphics Research Institute, Hosei University (Digital Media Professionals), Tokyo, Japan.

 

Contents

1.           Introduction

2.           Related Works

3.           Modelling Using Implicit Complexes

3.1.     Hybrid Representation of Geometry

3.2.      Definition of Implicit Complexes

3.3.      Implicit Complex Description

3.4.      Implicit Complex Construction

4.           Model Case Study and Discussion

4.1.      The Pot Filled with Liquid Model

4.2.      Discussion

5.           Rendering Implicit Complexes

6.                 Conclusions

7.                 References

 

Abstract

This paper describes a technology for modelling and visualization of 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.


1.           Introduction

Modelling and visualization of heterogeneous objects have become important research topics in different application areas such as CAD and rapid prototyping, volume modelling and rendering, representing results of physical simulations, geological and medical modelling (see [2], for example). Such objects are heterogeneous in their internal structure and dimensionality. 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). Varying materials and other attributes of an arbitrary nature constitute a heterogeneous internal structure.

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 [10]. This model uses real functions of point coordinates (scalar fields) to represent both the object geometry and its attributes. The hybrid cellular-functional model [1] 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 [9].

An important, yet largely unexplored, problem is concerned with the conformity between the objects 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 liquid containing a heating element immersed in it, we may need to consider a dynamic interaction between different surfaces (3D pot, liquid, heater - can be in the form of 2D spiral, boiling 2D bubbles growing on the spiral, floating to the liquid 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 visualization of heterogeneous objects in the form of implicit complexes (IC). First, we introduce a general structure of implicit complexes. Then we consider in detail how they are constructed. Rendering algorithms for implicit complexes using ray-tracing are also described. Finally, we present a case study illustrating the proposed methods and algorithms.

2.           Related Works

Let us briefly discuss approaches for modelling dimensionally heterogeneous objects using various cellular representations and related works 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. To describe complex topology, different spatial subdivisions, topological stratifications [6], and complexes [7, 8] are used.

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 [8] for dimension-independent geometric modelling for various applications. A Selective Geometric Complex (SGC) [11] 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 procedure for designing cellular models based on CW-complexes with the emphasis on the topological validity of the resulting shapes is considered in [3, 7].

Another approach to modelling heterogeneous objects is based on using real functions of point coordinates. For example, the constructive hypervolume model [10] supports uniform constructive modelling of point set geometry and attributes using such functions. Then, a theoretical framework combining a cellular representation and a constructive function representation was proposed in [1]. An independent cellular and functional representation of the same object is useful, but not sufficient in certain applications. 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 [1] a hybrid cellular functional model based on the notion of an implicit complex, which allows for the flexible combination of cellular and functional object geometry models and attribute models. In the current paper, we examine in more detail the construction and rendering of implicit complexes.

3.           Modelling Using Implicit Complexes

Here we provide a brief description of a theoretical framework for the representation of implicit complexes. A more formal and detailed consideration can be found elsewhere [1]. In this paper we present novel material concerned with theoretical and practical matters of the description and construction of ICs.

3.1.     Hybrid Representation of Geometry

The hybrid geometrical model of heterogeneous objects presented in [1] 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 [5]. A CW-complex provides a general representation for different topological complexes including polyhedral and cellular complexes

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|. The hybrid representation scheme can be defined in the form of the pair represented through a union operation as . 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 an FRep; so their cellular representation denoted by  is not necessarily known but can, in principle, be built using some known method. We call such domains as well as their subcomplexes implicit ones. Then the point set D is represented as the union . The complex K is also represented as the union of the corresponding explicit subcomplexes  and the implicit subcomplexes :

.

Note that if the intersection of two cells of an IC is not empty, then it consists of a collection of cells of this complex. The same is true concerning the boundaries of cells. It is necessary to impose constraints on the domain boundaries similar to those for subdomains. If these conditions are satisfied, subdomains can overlap each other and some subdomains can be located inside the others. Fig. 1 shows examples of such subdivisions.

 

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)
 
 

3.2.      Definition of Implicit Complexes

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 ). Thus, for any  there exist such that .

Explicit cells  are defined with respect to the definition of the CW-complex. The shape of each explicit cell  is defined by a characteristic mapping, and its boundary is mapped onto a subcomplex  with dimensionality .

Each implicit cell  is a closed point set defined by an FRep. The boundary of the implicit cell  is not necessarily mapped onto any subcomplex of and can contain both explicit and implicit cells. Explicit cells are indivisible elements of a subdomain subdivision containing no other cells. Some cells of an implicit complex can lie inside implicit cells of the complex. Note that an r-dimensional implicit complex can be reduced to a cellular one. We assume that each implicit cell  (where ) can be discretized.

3.3.      Implicit Complex Description

IC topology is described by relations between its elements. The general structure of a 3D IC is illustrated by Fig. 2. By definition, a 3D IC consists of 0D, 1D, 2D and 3D cells. Let  be a set of -dimensional cells . Such a set contains both explicit and implicit cells. There are two main types of relations that establish connections between cells of different dimensionalities: the boundary relation and the “to contain” relation.

Fig. 2. The general structure of a 3D IC
 
 

We denote by  the boundary relation between p-dimensional and s-dimensional cells, , . The pair () belongs to  if  belongs to the boundary of . The relation “to contain” is denoted by , , . The pair belongs to if  and . The entire structure of 3D IC is defined by six different boundary relations and nine different “to contain” relations. Other relations are the co-boundary, the “to be contained”, the incidence and the adjacency relations. These can be derived from the boundary and the "to contain" ones using various operations on relations.

The geometry of ICs is described as follows. 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 the formulation , where d is the distance from the given point X0. An implicit cell  can also be described as an image of a point functionally defined in 2D space.

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. 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 .

Explicit 2D cells are represented as images of triangles and quadrilaterals resulting from 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 . An implicit 2D cell  can also be described in two ways. It can be defined with 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 .

To represent an explicit 3D cell, a variety of maps of the form  can be used to describe the shape of curvilinear polyhedrons. Maps of this kind have been extensively used in describing finite element sets. Such maps can be used to describe the cells and attach them to the boundary cells of the complex by obeying certain boundary conditions. Once again, an FRep of the form  is used to describe the implicit cell .

And finally, to describe the non-geometric properties of a heterogeneous object, represented by an IC, we use the cellular-function model of the attributes introduced in [Adz02]. 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. .

3.4.      Implicit Complex Construction

To create an IC, it is necessary to describe the shapes of all its elements and, to specify the entire boundary and the “to contain” relations between its elements. The attachment operation is introduced allowing the creation of the IC in a component-wise manner, in order of increasing dimensionality of its components. This process is constructive and iterative.

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. We introduce two types of the attachment operation based on the one defined for CW complexes [3, 7].

The cell attachment 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, and 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 complex attachment operation deals with the procedure of attaching the complex  to the complex . Assume 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:, (). Finally, we define the boundary and the “to contain” relations of the complex.

4.           Model Case Study and Discussion

In this section we give an example of an implicit complex with nested cells.  Then, we discuss the difference between the proposed approach and the known heterogeneous object models.

4.1.      The Pot Filled with Liquid Model

Let us consider a 2D heterogeneous object shown in Fig 2. 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.

Let us consider in detail the description of the implicit cells. The extracted implicit cells 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.

   
                   (a)                                   (b)

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

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 liquid: the 0D and 1D cells extracted
 
 

4.2.      Discussion

Note the important distinctions between the proposed approach and the previously known frameworks for describing heterogeneous models. The models described in [11] 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 [6] 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 above example 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 liquid 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.

5.           Rendering Implicit Complexes

Using the known rendering techniques such as polygonization and ray tracing, one can render any individual explicit or implicit cell. Below, we assume that the implicit complex contains cells with different opacity values. In the case of fully opaque cells, they can be rendered individually and combined together with the standard use of an appropriate Z-buffer. The example shown in Fig. 4 has been rendered with a conventional ray tracing algorithm extended to support trimmed implicit surfaces as 2D cells [12] and a Z-buffer. 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 are also required, in addition to surface rendering techniques.

Explicit or implicit 1D and 2D cells are rendered first using traditional surface rendering techniques, 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.

Then, 3D implicit cells are rendered, depending on the stored values, with a volume rendering technique based on ray tracing. See, for instance, [4] for more details on general volume rendering. 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. 5 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 section 4, 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 liquid). 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 that connect the 2D implicit cell and the 3D implicit cells (i.e., the cylinder). Note that the trimmed implicit surface intersects the 3D cell representing liquid as it is allowed in our model

Fig. 5. Rendering an implicit complex composed of cells of different dimension and semi-opaque cells.
 
 

6.                 Conclusions

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 and illustrated. 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

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

[2]     Heterogeneous Objects Modelling and Applications, Collection of Papers on Foundations and Practice, Lecture Notes in Computer Science, vol. 4889, Eds. Pasko A., Adzhiev V., Comninos P., 2008, 285 p.

[3]     T. Kunii (1999) Valid computational shape modeling: design and implementation, International Journal of Shape Modeling, vol. 5, No. 2, pp. 123-133.

[4]     B. Lichtenbelt, R. Crane and S. Naqvi (1998), Introduction to Volume Rendering, Prentice Hall PRT publisher, Hewlett-Packard Company.

[5]     W. S. Massey (1967), Algebraic topology: An introduction, Harcourt, Brace&World.

[6]     A. Middleditch , C. Reade, A. Gomes (2000), Point-sets and cell structures relevant to computer aided design, Int.  Journal of Shape Modeling, vol. 6, No. 2, pp. 175-205.

[7]     K. Ohmori, T. Kunii (2001), Shape modeling using homotopy, In Proc. Int. Conf. on Shape Modeling and Applications, IEEE Computer Society, pp. 126-133.

[8]     A. Paoluzzi, F. Bernardini, C. Cattani, V. Ferrucci (1993), Dimension-independent modeling with simplicial complexes. ACM TOG, vol. 12, No. 1, pp. 56-102.

[9]     A. Pasko, V. Adzhiev, A. Sourin, V. Savchenko (1995), Function representation in geometric modeling: concepts, implementation and applications, The Visual Computer, vol. 11, No. 8, pp. 429-446.

[10]  A. Pasko, V. Adzhiev, B. Schmitt, C. Schlick (2001), Constructive hypervolume modeling, Graphical Models, vol. 63, No. 6, pp. 413-442.

[11]  J. Rossignac, M. O’Connor (1989), 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, pp. 145-180.

[12]  B. Schmitt, A. Pasko, G. Pasko, T. Kunii (2004), Rendering trimmed implicit surfaces and curves, In Proc. Afrigraph 2004, South Africa , ACM SIGGRAPH publication, pp. 7-13.