Interactive function-based shape modeling

 

Konstantin Levinski,

Nanyang Technological University, Singapore

P44-0521757@ntu.edu.sg

 

Alexei Sourin,

Nanyang Technological University, Singapore

assourin@ntu.edu.sg   

                        

 

Contents 

 

Abstract

 

This paper addresses interactive function-based free-form shape modeling where relatively small formulas are used rather than thousands of polygons. Interactive modification of the function model with concurrent double-resolution visualization of the respective polygonal mesh lets us provide both the interactivity and any required level of detail leading to photo-realistic appearance of the resulting shapes. We have proposed a rendering algorithm capable of handling local shape modifications with any desired precision. Also, we proposed a few methods, which let us accelerate the final function evaluation—a common bottleneck for the function-based shape modeling. Finally, we have described applications of the interactive function-based shape modeling to photo-realistic virtual crafting.

 

CR Categories: I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling - Curve, surface, solid, and object representations; I.3.7 [Computer Graphics]: Three-Dimensional Graphics and Realism – Visible line/surface algorithms;
I.3.8 [Computer Graphics]: Applications.

 

Keywords: interactive shape modeling, implicit functions, F-Rep, interactive polygonization, virtual computer art.

 

1   INTRODUCTION

 

Dramatic advances in computer technology have driven up the methods and tools of interactive 3D shape modeling where the unique geometric reasoning of the human brain couples with the rapid computing and rendering abilities of the computer. An ability to feel a geometric model through different haptic devices lets the user immerse into the Cyberspace and shape the model like if it could be done in reality. Even using a personal computer, the most computationally expensive operations can be done in hardware leaving a space for new algorithmic performance improvements. Some geometric models, which existed rather theoretically just a few years ago, now revolutionize the ways of shape representation and rendering. Thus, there can be noticed a trend toward free-form modeling based on volume models and implicit functions. The following examples illustrate this point.

FreeForm developed by Sensable [Sensable] is a commercial system for sculpting volumetric models. The system can produce sophisticated volumetric models with using a wide variety of tools and a three degree-of-freedom haptic input device for the force feedback. To achieve the best performance, this system is to run on the computers with advanced configuration.

A computer-based sculpting system Kizamu [Perry and Frisken 2001] based on the original idea of the Adaptively Sampled Distance Fields (ADFs) [Frisken et al. 2000] is capable of making digital characters for the entertainment industry. The authors implemented digital clay—a medium with the characteristics of real clay and the advantages of being digital. The system runs on a standard hardware and produces complex volumetric shapes with fine details. ADFs can be thought of as a further extension of the octrees and, as the authors claim, ADFs integrate volumes and surfaces into a single geometric representation.

Volumetric Sculpting described in [Ferley et al. 2000] lets the user define a complex sculpted shape as an iso-surface of a spatially sampled scalar field. Due to the balanced binary search tree usage, the authors managed to achieve interactivity with low memory requirement. Complex blobby-like shapes result in this system.

After studying these as well as other projects in interactive shape modeling such as [Galyean and Hughes 1991; Fowler 1992; Terzopoulos and Qin 1994; Wang and Kaufman 1995; Baerentzen 1998; Mizuno et al. 1998; Ehmann et al. 2001], we have defined two contradictory requirements. First, any desired level of detail is to be provided when the shape is being interactively created. Second, the image quality must be photo-realistic, especially when the real crafting techniques are being simulated. The first requirement has driven us to the idea of using function-based modeling, while the second one forced us to develop specific rendering methods combining advantages of rapid rendering with photo-realistic quality.

In our project, the extension of implicit functions called F-Rep [F-Rep web-site] is used. F-Rep defines shapes with an inequality ¦(x,y,z)³0, where function ¦ is positive for the points inside the shape, equal to zero on its border and negative outside the shape. Normally, for rendering such function-defined shapes, either ray tracing or polygonization followed by fast polygon rendering is used. Alternatively, the function-defined shapes can be voxelized and rendered as a set of points. A bottleneck of all these rendering methods is in usually large time needed to evaluate the defining functions. A very big number of sample points are to be tested, which makes it really difficult to perform any interactive changes to the shape being modeled. Also, the rendering algorithms are to allow for interactivity.

In this article, we continue the research described in [Sourin 2001a; Sourin 2001b] where interactive ray tracing was used for redrawing only the affected areas of the screen while the rest of the image remained intact. Compared to other methods, the interactive ray tracing provides the required level of detail and photo-realistic quality of the resulting images. However, it works efficiently only when small local interactive modifications of the shape are being done, and requires very large time for rendering the whole shape unless a cluster of parallel computers is used.

In this paper, we consider interactive polygonization (Section 2) and propose an algorithm for interactive rendering of function defined shapes (Section 3), which provides us any desired level of detail and rendering quality while still maintaining the interactivity. It is done in conjunction with developing a few methods accelerating the function evaluation (Section 4) when very complicated function-defined shapes are being created. In Section 5, we apply these methods to virtual crafting, and finally in Section 6 we discuss the algorithm performance.

 

 

2   PROBLEMS OF INTERACTIVE POLYGONIZATION

 

In our project, we simulate with a computer various crafting techniques such as sculpting, carving, embossing, engraving, etc. By analyzing the nature of these crafts, we have imposed certain restrictions on the process of shape modeling, which helped us to find the efficient way of its implementation:

1.     We assume that the original shape is topologically connected like a work-piece before the crafting had begun.

2.     We consider only a surface of the shape and its local gradual modifications imitating the actual crafting.

3.     We are aware of the expected result of each interactive operation like a craftsman anticipates the result of each operation.

All these assumptions have been taken into account when devising the method of interactive function-based shape modeling described in this paper.

For obtaining a polygonal representation of a function-defined shape, a significant amount of points on or near its surface is to be calculated. This task involves multiple function evaluations, which can be time consuming. For parametric function representation, the polygonization is rather a straightforward task, while it is not so obvious for implicit functions. Since in this project we use implicit functions and their modifications, we will further concentrate on the methods of polygonization of implicitly defined shapes.

The requirements for the polygonization method that will be suitable for our case can be phrased as follows:

1.     The algorithm should be able to polygonize only the visible surface of the shape with the fastest possible speed and any required level of detail up to the size of a pixel.

2.     The mesh produced by the algorithm should be optimal in terms of the polygonal quality, i.e. the polygons should have a near-unit aspect ratio.

3.     Robust and seamless local mesh reconstruction is required for interactive polygonization.

4.     There must be devised methods of fast function evaluations, which will be involved when a portion of the shape is being re-polygonized.

The existing algorithms of polygonization differ in terms of their computational complexity, the frequency of the function sampling, and the resulting mesh quality. To achieve interactivity, the polygonization algorithm should sample the function as seldom as possible and update the image on the screen within the interactive rate.

There are two possible ways of interactive updating the polygonal mesh.

The first method assumes re-polygonization of the whole shape. This is a generic and probably the easiest solution but it has a very limited application since quite often the function evaluation takes large time, which may significantly slow down the total algorithm performance. Commonly, only about 100K polygons can be re-built at the interactive rates.

Another possible approach, noted in [Bloomenthal 1997], assumes that only a part of the shape is to be re-polygonized, and the newly obtained polygons will update the existing polygonal mesh at the interactive rate following the respective interactive operations modifying a part of the shape. It assumes availability of more sophisticated algorithms as well as a user’s control over the mesh generation. Such a control is required when automatic methods fail or not applicable. For example, when a function model changes, it is often impossible to detect the area of modification by examining the defining functions directly. In that case, either the whole model is to be re-polygonized or additional interactive information should be used to detect and rebuild the modified area only. Although rebuilding the entire polygonal model after each modification ensures obtaining the correct polygonal surface, the process may take unacceptably long time. On the other hand, if we could find a way of fast detecting the area of modification, the polygonizer can be confined to it, and the running time can be reduced.

Different methods have been used for specifying the area of re-polygonization. In the interactive sculpting system based on the predictor-corrector polygonization [Akkouche and Galin 2001], the oriented bounding box was used to define a part of the space where the modification took place. Then, every polygon of the existing mesh was tested on intersecting the box, and removed from the mesh in case of intersection. Although for several thousand polygons this methods performed well, it will become inefficient for hundreds of thousands of polygons, which are anticipated in our case. The subdivision system in [Galin and Akkouche 2000] defines the modification areas with axes aligned bounding boxes and then re-polygonizes their interior. Although, this method becomes inefficient in case if the modification area is long or has a fancy shape, it still provides a considerable acceleration in other cases. We have further improved this technique in our project.

Another important benefit from the controlled polygonization is in interactive definition of the resolution. In most applications, the resolution in polygonization algorithms is set up automatically, depending on the surface parameters such as curvature, error value, dihedral angle between adjacent polygons, etc. Most of these criteria suffer either from non-generality, undersampling, or heavy function evaluation requirements. In an interactive application, the task of detecting resolution can be transferred to the user. Like changing the eye focal length when shifting the gaze from the whole shape to a little part of it, the size of the polygons may vary depending on the size of the visualization or modification area. In connection with the function-based shape modeling, this problem was addressed in [Kazakov et al. 2001] and has found a different and efficient solution in our work.

 

 

3   FAST RENDERING OF INTERACTIVELY MODIFIED SHAPES

 

3.1  Method description

 

Besides the ability of interactive high resolution rendering of any modified part of the shape, we need to be able to obtain an updated high-resolution image of the whole shape on the screen at an interactive rate when the observer’s position changes. We propose that the following is to be done to achieve this goal.

1.     There must be identified or devised a fast and robust polygonization algorithm most suitable for obtaining the polygonal mesh of our function-defined shape model.

2.     Two different polygonal resolutions–coarse and fine ones–are to be used simultaneously. The coarse resolution will be used when relocation of the whole shape or changing the light condition is required so that the user wants to be able to see the whole shape changing at the interactive rate. The coarse resolution will be dependent on the hardware performance, and may be around 100K polygons. The fine resolution assumes a smaller size of the polygons up to the size of a pixel. It will be used for interactive rendering the modified parts of the shape, as well as for high-quality rendering of the whole shape. The ability to reduce the size of a polygon up to the size of a pixel gives us the point rendering quality with the ability still to use hardware acceleration of polygon rendering.

3.     Both the polygonal meshes are to result from the same polygonization algorithm, as well as are to be linked to the same data structure controlling the polygonization process. Since the size of the polygonal mesh obtained for the fine resolution will be substantial, this mesh will be usually stored and maintained in the secondary memory, while the polygons for the coarse resolution and the respective control data will be stored and maintained in the main memory. Both meshes can be stored in the main memory if a computer with an advanced configuration is used.

The visualization pipeline is illustrated in Figure 1.

 

 

Figure 1: The visualization pipeline.

 

First, for the initial function-defined shape, the coarse resolution mesh will be created, stored in the main memory, and rendered on the screen. Concurrently, the fine resolution mesh will be created in another thread. After the fine mesh is created and stored in the secondary memory, it will be rendered as well, and the respective image will replace the one on the screen produced from the coarse resolution polygons. If the shape is relocated, the coarse resolution mesh will be used for rendering the moving shape while the fine resolution mesh will be rendered as soon as the shape comes to its rest. When any interactive modification is to be done, the defining function will be modified first followed by both the fine and the coarse re-polygonization of the respective area. However, only the fine resolution polygons will be used for updating the image on the screen while the coarse resolution polygons will be only calculated to update the stored coarse mesh for further possible use if relocation of the whole shape is requested. Since the size of the fine polygons is smaller than the size of the coarse polygons, the whole processor power will be used for rendering only these newly created polygons. When rendering these polygons, the respective part of the image on the screen will be updated while the rest of the image will remain intact. This will create an illusion of interactive working in high resolution with the whole shape. Both meshes will be updated respectively and will be readily available for further rendering thus providing the sustained interactive rate.

In fact, in place of the fine resolution polygons we might have used points, but we have chosen to use polygons since it gives us more rendering benefits compared to point rendering even if we reduce the size of polygons to the size of pixel. With a proper memory organization, the size of a mesh will not be much bigger than the size of the respective point array.

Below, we describe the implementation details of the proposed method of rendering. In 3.2 we review the polygonization algorithms, which could be used for our purposes. In 3.3, we propose an optimized continuation algorithm. The details of the algorithm are discussed in 3.3, 3.4 and 3.5.

 

3.2  Polygonization methods

 

A comprehensive survey of the implicit surface polygonization algorithms can be found in [Bloomenthal 1997]. All the variety of algorithms fall into two major classes:

1.     The methods intended for operating on continuous functions.

2.     The methods devised for processing discreetly sampled data.

We are going to follow this classification taking into account the newly published results.

The algorithms, initially designed for continuous data, include particle–based, predictor-corrector and subdivision techniques.

Particle-based techniques were originally designed for interactive modeling. The methods for effective interaction between particles and an implicit surface were developed in [Witkin and Heckbert 1994], while the interactive system based on the technique is described in [Stander and Hart 1997]. Unfortunately, the maximum number of particles that can be operated in real time is only about a few thousands. Therefore, these techniques fail to satisfy our requirement of the fine detail reconstruction.

When a high quality mesh is required, Predictor-corrector methods are to be sought. These methods are based on prediction of the adjacent triangles positions with their consequent placement at the actual surface. The high quality of mesh is achieved by near-equilateral shape of the triangles. The recent works in this area are  [Karkanis and Stewart 2001; Hartmann 1998]. The predictor-corrector method requires initial seeding triangle to be put on the surface—the condition, which could easily be met in our case when we know the original shape. Shape modeling with local mesh updating based on the predictor-corrector algorithm is presented in  [Akkouche and Galin 2001]. In this work only the blobby objects were constructed, since the method was not suitable for models with sharp edges. Using the adaptive polygonization leads to undersampling, i.e. omitting fine details. Moreover, global overlap detection can be expensive when obtaining fine meshes. Therefore, although the shape of polygons is acceptable, we cannot use this method as it will fail to reveal fine details of the model.

Subdivision mesh extraction method is based on recursion. A cell containing the model is subdivided into eight smaller cells followed by testing whether they contain the surface or not. The process repeats until the desired cell level is achieved. All the leaf cells containing the surface are polygonized then. Unlike the predictor-corrector methods, this algorithm does not need an initial point to begin the polygonization with. It detects the surface automatically. The quality of mesh generated by this algorithm is similar to the one generated by the Marching Cubes algorithm, but, like most of the adaptive methods, may suffer from occasional undersampling. The working area is generally limited by the starting cell size. An interactive system utilizing this method was described in [Galin and Akkouche 2000]. The initial cell size restriction was successfully handled by octree growing. For reliable detection of the function-defined surface in a cell, Lipscitz conditions were used. This resolved the undersampling problem, but greatly restricted a possible set of implicit functions. Another point preventing this method from being utilized in our application is a poor mesh quality similar to that of the marching cubes algorithm.

Since the nature of our function-defined model is continuous, we should have restricted our consideration to the continuous methods only, however the algorithms initially designed for discrete data can be successfully applied to polygonizing function-defined shapes as well. Among the most common methods are spatial enumeration and continuation techniques.

Spatial enumeration is probably the oldest algorithm for polygonizing volume data [Lorensen and Cline 1987]. It is perfectly suitable for range data from CT or MRI scans, but for interactive visualization of a large function-defined model, the uniform sampling requirement may become unfeasible due to the high complexity of each function evaluation. Because of our assumption on the model topological connectivity, the search through all the volume becomes redundant.

The second approach named continuation and presented in [Wyvill et al. 1986], exploits spatial coherence for detecting all the cells intersecting the surface. Initially, a seeding set of cells is introduced. Then, at each step the neighboring intersecting cells are examined. To avoid checking the same cell twice, a sort of hashing can be introduced for the cells. The demerit of the continuation method compared to spatial enumeration is in its lack of generality since it requires to place seeding points on each separate surface defined by implicit functions. However, in an interactive application it can be easily implemented.

The continuation algorithm fits our needs quite well. It detects the surface effectively without unnecessary function evaluations. Also, due to its discrete nature, it is very fast and can be extended for quick local re-polygonization. It must be noted, though, that the mesh quality is highly dependent on the way every cell is polygonized, configuration of the cell and optimization algorithms used.

 

3.3  Optimization of the continuation method

 

Commonly, a cubical shape of a cell with its optional tetrahedral decomposition [Bloomenthal 1994] is used in the continuation polygonization algorithms. However, these cells still fail to ensure the sampling uniformity and therefore will not provide us the required mesh quality. The cell shape, which would satisfy our requirement, is a tetrahedron generated by the body-centric lattice (see Figure 2) as it was theoretically proven in [Skala 2000].

 

 

 

 

 


This tetrahedron has been recently used for surface extraction from volumes [Chan and Purisima 1998; Theußl and Moller 2001]. We have applied this tetrahedron to the continuation method. Besides obtaining the required mesh quality, we have also managed to accelerate the whole process of polygonization by detecting the neighboring cells by simple 2D mirroring (points D, B, A and D’ in Figure 2), which makes its propagation nearly as simple, as propagation of a cubic cell. Taking into account that all of the faces are equal isosceles triangles, the continuation algorithm can be simplified even further.

Obtaining a triangular mesh from a set of tetrahedral cells intersecting the surface is a common straightforward task. The surface inside each cell is polygonized piece-wise, and then assembled with other triangles, thus forming the entire mesh. To improve the resulting mesh quality, we have applied a cell clustering method similar to the one described in [Treece 1999]. In this method, each tetrahedral cell produces maximum one triangle. On average, it gives one triangle per three cells. The number of triangles may grow in uneven parts of the surface. This method does not require any additional function evaluation beside those used for the cell detection. The triangles can be linked to the cell set and therefore will become readily available for retrieving when stored in the memory. The example of the set of tetrahedra and the resulting mesh are shown in Figure 3.

The continuation method requires a certain control data structure to avoid cell overlapping when moving along the surface. Usually, a hashing technique based on the integer cell coordinates is employed for fast cell querying. Commonly, such hash data is discarded for the processed cells for the sake of memory conservation. On the contrary, in our approach, we keep and use this hash data for obtaining the fine resolution triangles from the original coarse resolution cells. It is also used for fast surface querying as well as for local mesh updating.

 

 

 

 

 


3.4  Coarse and fine resolutions

 

When we require a fine polygonal mesh with a pixel size for each triangle, we should anticipate a huge memory consumption as well as tremendous computing time for storing and processing the respective hash data structure and the tetrahedral set. However, we have found a solution to this problem by controlling the fine resolution polygonization by the tetrahedral set obtained and stored for the initial coarse resolution. We have achieved it by assigning to the same cell one triangle from the coarse resolution mesh and several respective fine mesh triangles, which are located inside this cell. This is schematically depicted in Figure 4.

 Computation of the coarse mesh does not require any additional function evaluations besides those done for calculating the coarse tetrahedral set. On the contrary, calculating the fine triangles for each cell will require significant time. To avoid slowing down the coarse mesh calculation, we have implemented the fine mesh calculation as a separate process, which runs in parallel with the coarse polygonization.

The refinement process employs the same continuation principle as the general cell detection algorithm. Let us denote the small cell used by this process as a sub-cell. It is smaller than the original cell by 2k times, and it completely tiles the tetrahedron. The value of k is either calculated to match the resolution of a particular display device, or defined by the user. To start the fine polygonization, a seed sub-cell is to be defined inside the coarse seed cell. Then, the sub-cell propagates inside the cell and extracts the fine polygons. For the initial basic shape, new fine polygons will be immediately shown on the screen following the coarse polygons which calculation will be performed much faster. The fine mesh will be stored in the secondary memory for later use. During the propagation process, a sub-cell can occasionally appear to be in another cell next to the one being processed. In this case, the propagation of the sub-cell will be halted, and this sub-cell will be defined to be a seeding sub-cell for the cell, which it penetrated to. If this cell has been already refined, then no further action is to be taken. Otherwise, the cell will be added to the refinement queue, provided it is not there yet. Eventually, the fine mesh for the entire surface will be obtained. The process of creating the fine mesh may involve those tetrahedra that were not used in the original coarse polygonization.

 

 

 

 


Since the fine mesh of the whole shape should have a significant size in terms of the memory required for its storage, we assume that generally it is to be stored in the secondary memory while being addressed through the coarse cells stored in the main memory (Figure 4). Each cell will address a block of a fixed size. The size of the block is to be chosen to accommodate an average amount of the triangles that can be generated from one cell. Extra blocks can be linked to each other whenever the mesh becomes larger than that fitting in one block. A few most recently used blocks may still remain in the main memory in anticipation that they will be required again soon. When the main memory limit is exceeded, these blocks will be removed from it while still being kept in the secondary memory. However, for any reasonably small area on the shape’s surface, the respective fine mesh can be loaded from the secondary memory for further fast rendering.

 

 

 

 

 


 

Figure 5: 

a) Obtaining cells for the bounding surface.

b) Detecting the boundary cells.

c) Removing the inside cells.

d) Obtaining the new inside cells.

 

 

3.5  Local updates and modifications

 

For updating the mesh for the modified part of the shape, we developed an algorithm for detecting and retrieving only those cells that belong to the modification area. Upon retrieval, the respective polygons will be removed from the mesh and replaced with the new ones. The hashed set of cells allows us to retrieve both the coarse and the fine meshes very quickly. Among the different ways of defining the modification area, we have selected perhaps the most generic one: definition by an F-Rep function. Without loss of generality, we assume that the modification area resides in a topologically connected bounding surface defined by a simple function f(x,y,z)³0. We apply the continuation algorithm to this surface and obtain a set of cells containing this surface. Then, every cell in this set is to be checked against the hash table of the initial set to obtain all cells, which intersect both the shape surface and the bounding surface. At this point, the cells intersecting only the bounding surface will be discarded. Using the same continuation algorithm with the initial queue of the cells resulting from the previous step, we can mark for deletion all the cells intersecting the surface of the shape but located inside the bounding surface. A 2D illustration of this approach is given in Figure 5. Note, that up to this point no additional shape function evaluations were needed and the overall complexity was O(n), where n is the number of the recalculated cells. Finally, the algorithm is applied to the modified function with the same starting queue, yielding new cells in place of the old ones. The resulting cell set will not differ from that, which could be created for the whole shape.

 

 

3.6  Rendering

 

The coarse mesh can be rendered easily and quickly with a single OpenGL command. This rendering is performed when the relocations of the whole shape, changing the observer’s position, or changing the lighting conditions is requested so that the user will be able to see the whole shape moving or changing its visual appearance at the interactive rate. After that, or in fact concurrently, the fine resolution rendering will begin processing unrefined cells. After the fine rendering is completed, the resulting image will be saved for further optional interactive re-polygonization. During such an interactive rendering, the tetrahedra and the respective polygons will be stored, while the whole image will still remain on the screen with the respective
Z-buffer depth information. Only the new fine-resolution polygons from the area being modified will be sent to the rendering pipeline and their graphics image will eventually update the respective part of the shape image as on the screen as well as the Z-buffer. Therefore, most of the time there will be no need to redraw the whole scene. Using the Z-buffer is required to avoid artifacts when new polygons have greater depth value than those, which they are replacing. Simple overwriting of the image is also not feasible because in this case we take no advantage of the depth information and visibility detection artifacts are likely to occur as it is illustrated in Figure 6.

 

 

Figure 6: An example of a different polygon depth.


With the proposed method, we have managed to achieve the required interactive feedback even when we had been working with millions of polygons on a computer with a common graphics card.

 

 

 4   FAST FUNCTION EVALUATION

 

In this section we consider the ways of accelerating the function evaluation during the interactive function-based shape modeling.

  

4.1  Definitions

 

During interactive modeling, which often simulates real crafting techniques, the shape defined by function Sbasic is modified with some operations. Usually, these operations are defined by two-place functions of the function being modified and other function defining the shape of the instrument. For example, when cutting or carving a shape, the respective operation can be defined by the set-theoretic subtraction of the shape swept by the instrument from the shape being modified. In further considerations, we will replace these two-place (or possibly multiplace) functions with unary functions, which we will call interactive operations F. In that case, the process of making a shape can be defined as follows:

 

Sfinal = Fn (Fn-1 (Fn-2 (… F2 (F1 (Sbasic ))… ));

 

where Sfinal is a function defining the final shape created by gradual application of interactive operations F1-Fn to the basic shape defined by Sbasic. The implementation of these interactive operations for simulating some artistic techniques will be considered in the next section, while in this section we only consider the generic methods of acceleration applicable to the whole class of these functions.

 

4.2  Accelerating functions

 

The bottleneck of each function representation is usually in the time, which is required for the function evaluation when the number of individual operations used for making the shape is very large. Indeed, thousands of individual strokes of a hammer are to be done to make a carved sculpture, where each stroke is an individual operation in our considerations. However, one can easily observe that each interactive operation has a local area of application with a size often considerably smaller than the size of the whole shape (Figure 7).

 

Therefore, when evaluating function Sfinal, only a few operations compared to the total number of them will actually contribute to the specified part of the shape. However in the straightforward implementation of the function evaluation procedure, all the interactive functions Fi will be processed/evaluated. This observation has driven us to the idea of representing the interactive functions Fi differently so that for each individual function evaluation in point P only those interactive functions Fi will be taken into account, which may contribute to the resulting function Sfinal value in this point. It can be phrased as follows:

 

 

 

Sfinal = Fn (Fn-1 (Fn-2 (…F2 (F1 (Sbasic ))… ));

a=Fi-1 (Fi-2 (…(F1(Sbasic ))… ));

 

 

where for each function Fi, the area of its application is defined by some relatively simple bounding function fi. During each evaluation of function Sfinal, functions Fi are to work like filters bypassing without evaluation those interactive operations Fj, which will definitely not contribute anything to the shape in the point P where function Sfinal is being evaluated. To exclude n interactive functions Fj we have to evaluate m bounding functions fk, where m > n. In case if the complexity of computation of these fk is comparable with that of Fj, there will be a little acceleration achieved. Therefore, it would be beneficial to know that f < 0 is true not only in the selected point P but also in a certain vicinity of it. This will let us use the space coherence and significantly reduce the number of fk evaluations without any loss of precision. To achieve it, we propose to construct functions f according to the Lipschitz condition on their values so that there is some l such that for the given i and any P1 and P2 the following is being hold:

 

|fi(P1) - fi(P2)| < l| P1 - P2|

 

If in some point P we have evaluated fi(P) = f0 < 0, the function fi will remain less than zero for all Pj such that | Pj - P | < -f0 /l. Therefore, the respective interactive functions Fi can be safely bypassed when evaluating function Sfinal in points Pj. Distance functions are usually a good choice for the boundary functions fi, although there could be other functions as well. The examples of constructing such functions f will be considered in the next section.

In 3.4, we introduced a way of using the proposed algorithm for rendering parts of the shape with a higher resolution while keeping the updated polygonal mesh in the secondary memory. When doing the local polygonization, it would be feasible to work only with those interactive functions, which contribute to this local area. It can easily be done with the bounding shapes. First, we will define a sphere including the area being processed. Next, we evaluate bounding functions fi in the center of the sphere. If for some i, fi < Rsphere /l, then the Lipschitz condition guarantees us that this fi will always be less than zero inside the sphere and the respective function Fi can be safely bypassed.

 

 

4.3  Efficient memory layout for acceleration structures

 

To achieve the required computational performance when using the boundary functions, we also have to minimize the number of these function evaluations. Generally, some kind of space subdivision could be used. The methods similar to regular/irregular grids or octrees would probably immediately come to mind. The straightforward implementation of these structures would subdivide the modeling space into a set of cells with a list of respective interactive operations Fi contributing to the respective cells. Given a set of such cells, any new operation Fk will demand a number of the storage units directly proportional to the number of cells which this operation contributes to (Figure 8a). With reducing the size of the cells, this auxiliary storage will become excessive. We found a solution to this problem, which originates from the nature of the algorithm described in Section 3. First, we will naturally use the calculated tetrahedra as a set of cells and therefore will not have to allocate any extra memory for this purpose. Next, with each tetrahedron we will associate only one pointer, regardless of the number of operations contributing to this tetrahedron. This pointer defines a node in the operation tree, by traversing which the whole set of the contributing operations can be obtained (Figure 8b). The tree is created during the interactive modeling when each new interactive operation Fi is defined. For each tetrahedron, the respective function fi will be evaluated for the local areas in the way described above. In case if the tetrahedron is affected by the function Fi, the respective node will be added to the tree. In case if the node already exists, the tetrahedron pointer will be set to this node.

 

 

 

 

Figure 8: Common and proposed data structures.

 

 

4.4  Acceleration for free-form shape modeling

 

Conformance of the bounding functions to the Lipschitz conditions could help us with building an acceleration structure like an octree. This structure is efficient for arbitrary bounding function configurations when we have no information about their parameters. In our case, we expect to benefit from interactivity, which should provide us additional data. We analyzed the typical bounding functions which could be used in interactive free-form shape modeling such as embossing, sculpting, carving, etc. These functions are very simple compared to the whole resulting function, and they are mostly associated with the shapes defining fine details. Therefore, if the polygonization algorithm can calculate tetrahedra along the surface, with a slight modification the same algorithm will track the interiors of the shapes defined with the bounding functions as well (for a schematic view see Figure 9). If the number of tetrahedra containing in the bounding shape is relatively small, the detection can be performed very fast. With the data structure proposed earlier, even a greater number of tetrahedra will not cause excessive memory overhead.

This approach is superior to traditional structures since it fits well for simple functions, which we mostly deal with. The algorithm does not require any additional calculations during cell retrieval, as it incorporates the same tetrahedra and hash table, which we used in the polygonization algorithm. A pointer to the list of participating functions is stored in the same hash table used for querying cells for propagation. In many cases, this structure is updated more efficiently than a tree structure since there is no need for the up and down traversing of the tree for finding the neighbor cells.

For more complex functions the algorithm is inefficient, therefore they are kept separately in an octree. The octree is not severely subdivided and sparsely populated since most of the functions are hold by the proposed cell set. When it comes to calculating the actual function, we have two lists: one of ‘small’ functions and the other list of ‘large’ ones. When using these lists, we apply the functions one by one making sure to apply the earliest first until both the lists are processed. The acceleration achieved for existing models is essential—instead of evaluating thousands of functions at each point, we only have to evaluate just a few. For the fine polygonization, the benefit is even more considerable—while the algorithm is refining a particular tetrahedra it knows the participating functions without any extra evaluations.

 

 

 

 

Figure 9: Acceleration structure for free-form shape modeling.

 

 

 5   INTERACTIVE CRAFTING

The methods and algorithms of the interactive function-based shape modeling discussed in the previous sections have been applied to interactive embossing and carving. These crafts have been implemented with an interactive program where the function model of the shape is gradually modified with offset and set-theoretic operations. The final shape is represented in the data structure as a list of interactive operations over the basic shape. A pressure-sensitive graphics tablet and a six-degree of freedom haptic input device (Figure 10) have been used to realistically simulate the depth of penetration of the tools.

First, let us consider how to model embossing, which is an art of decorating metals from behind, and describe the required interactive operations with the respective bounding shapes. The whole process of embossing will be simulated geometrically by using offset operations over the function Sbasic.=f(x,y,z)³0 defining a basic shape. For example, a basic shape representing a sheet of metal of size 2w´2h´2d is defined as a thin solid plate by intersecting six plane half-spaces as follows:

 

 

 

Figure 10: Virtual crafting with a haptic device.

 

 

Next, let us introduce a function, which will simulate plastic deformations of the metal as follows:

 

fdef(x) =  (2+c) x6 – (3+2c) x4 + c x2 + 1

 

This is a unit C1 continuous function with zero derivatives at both ends (Figure 11).

 

 

Figure 11: Deformation function

 

By varying parameter c as well as by scaling the function, we can mimic the profile of different imprints and embossing techniques. This function fdef will be used to define different local offset operations, which will eventually make the process of embossing.

First, the contours of the drawing are to be pressed down the metal. To model it, we will linearly interpolate each curve through its key-points {P1, P2, …, Pn}, and project these points onto a plane perpendicular to the averaged normals to the surface of the shape at these points. Any point P0, in which the shape function is being evaluated, is to be projected onto this plane as well, and the minimum distance d from this point to the projected segments of the curve is to be found. This is done to ensure that all the following offset operations will superpose the current one. For point P0 the following offset function is to be evaluated:

 

 

where h defines the depth of the incision, r defines the width of the contour, and c defines the profile of the deformation function fdef.. The respective interactive operation will be defined as follows:

 

 

The corresponding bounding shape function for this operation is
f( P ) = r - d( P ). It satisfies the Lipschitz condition with l = 1, and yields foffset=0 when f(P) < 0. The resulting shape after applying this interactive operation will resemble the real pressing down the contours (Figure 12 a).

 

 

a                                  b                                  c

 

Figure 12: Making contours, bossing-up relief, and making a background.

 

 

 

a                                   b                              c

 

Figure 13: Shape relocation and final coloring.

 

 

Next comes raising up the relief areas by rubbing or beating the metal from behind along the area bounded by the contour line pressed down in the previous step. This also can be modeled with the offset operation similar to Eq. 1: