ABSTRACT

Haptic rendering is referred to as an approach for complementing graphical model of the virtual object with mechanicsbased properties. As a result, when the user interacts with the virtual object through a haptic device, the object can graphically deflect or deform following laws of mechanics. In addition, the user is able to feel the resulting interaction force when interacting with the virtual object. This paper presents a study of defining the levels-of-detail (LOD) in point-based computational mechanics for haptic rendering of objects. The approach uses the description of object as a set of sampled points. In comparison with the finite element method (FEM), point-based approach does not rely on any predefined mesh representation and depends on the point representation of the volume of the object. Different from solving the governing equations of motion representing the entire object based on pre-defined mesh representation which is used in FEM, in point-based modeling approach, the number of points involved in the computation of displacement/deformation can be adaptively defined during the solution cycle. This frame work can offer the implementation of the notion for levels-of-detail techniques for which can be used to tune the haptic rendering environment for increased realism and computational efficiency. This paper presents some initial experimental studies in implementing LOD in such environment.

1. Introduction

Interactive virtual training environment has been gaining a great popularity over the past decades. One of the main challenges of such development is the modeling of deformable objects such as soft tissues, organs, tendon, and skin. The two main requirements for modeling of such objects is the availability of material and biological properties and the need for the efficient/fast computational framework for achieving an interactive computational frame rate. In general, when interacting with the rigid model of the virtual object, the computational framework should support the graphic rendering rate of 20 - 30 Hz and the haptic force feedback rate of about 1 KHz [1]. However, when interacting with deformable or flexible objects, the force feedback rate can be comparably reduced in order to create a realistic haptic feedback. Developing an efficient and realistic computational model of deformable object is one of the main challenges for achieving an efficient haptic interaction environment.

Two main approaches have been followed in the past for modeling deformable objects. One of the approaches is based on the mass-spring methodology which represents the object as discretized mass points with spring connectivity. For example, [2,3] modeled a 1D suture object, and [4-7] modeled a deformable cloth-like object representing soft tissues. In general mass-spring modeling approach offers a simple and computationally efficient framework for developing interactive virtual training environment. Another approach for modeling deformable or flexible objects is based on finite element methods (FEM) and its various extensions. For example, [8] presented a simplified computational set-up for realtime simulation of soft tissue, [9-11] presented a fast linear solution for real-time user interaction with deformable objects. In general, due to the existence of large sizes of system matrices and the definition of shape functions, most of the solution approaches require an increased computational load which is in general not suitable for realtime interactive applications. For example, [12] developed an algorithm for enhancing the computational efficiency of the solution which still results in a very with limited extension to an interactive application.

Given the material properties of the object (e.g. Young’s module and Poisson ratio), FEM can still offer a more accurate representation of the physical objects in comparison with the mass-spring model. The main challenge of implementing FEM remains to be the design and development of a fast an efficient computational framework which may allows real-time application in the area of multi-modal haptic user interaction.

An approach for modeling deformable objects is referred to as the meshless method [13] which uses descretized element nodes (or points) to construct the object and uses the governing equations of motions through usage of radial basis weighting functions. [14] presented one of the earlier meshless methods in physics-based animation of objects. [15] presented a meshless elastic and plastic deformation framework. [16] proposed a meshless paradigm for modeling the point-sampled deformable object in real time. [17] proposed a similar meshless framework for modeling multiple deformable objects for user interaction purposes. One of the extensions of meshless method is referred to as the point-based (or particlebased) approach. [18] proposed a point-based modeling approach for graphic simulation of elastic and plastic objects. [19] presented a point-based approach for animating elasto-plastic solids, where a novel computational scheme based on displacement gradient is introduced using neighborhood optimization. In this analysis it was shown the point-based approach can give comparable results to that of approach based on FEM and hence can be used as an accurate representation and solution in haptic interaction [20]. In this paper, we demonstrate the implementation of a similar approach suitable for haptic rendering. Comparing with mass-spring model, the pointbased approach incorporate the material properties object implicitly in the modeling framework which has a significant advantage on the degree of accuracy of model. Comparing with FEM, the proposed modeling formwork can be potentially applied to real time rendering applications by adaptively including sample points in the computational model at the interactive rate.

The paper is organized as follow: Section 2 presents an overview of the point-based computational mechanics; Section 3 presents a definition for LOD which was used in this paper; Section 4 presents some experimental studies of our proposed LOD and Section 5 presents some concluding remarks.

2. Point-Based Mechanics

Point-based approach discretizes the control volume of the object into distributed points with no predefined connectivity or meshes (Figure 1). In contrast to FEM which defines an interpolation function (shape function) between the fixed defined nodes associated with a particular element [21], in point-based approach, functions such as Radial Basis Functions (RBF) is selected for interpolation of a continuous function based on a set of distinct arbitrary sample points defined in the control volume of the object [22].

Initially, through a weighting function, each point is defined to have a given mass in relation to its neighbor points. This given mass is computed by dividing the mass of the object by the number of points which needs

to be maintain during each solution cycle. The governing equation of motion of the object can be written as:

(1)

where is defined as the spatial gradient of strain energy function with respect to displacement vector. The following equation defines the computation of strain which is used in the definition of (strain energy function).

(2)

where is the displacement vector of a point.

One of the main computational challenges for the solution of Equation (1) is the computation of the gradient () defined in the Equation (2). In RBF approaches, Smoothed Particle Hydrodynamics (SPH) [23] is commonly used for the numerical computation of gradient function. Moving least square (MLS) is a computational tool belonging to the RBF methodologies which reconstructs continuous functions from a set of unorganized point samples (discrete points). In addition, a weighting function can be defined to weight the least squares measure and bias the computation towards the region around a point at which the reconstructed value is being evaluated [24,25].

The selection of weighting functions used in the computational model plays a very important role. In modeling deformable and flexible objects, there are several criterion which can be used for choosing a suitable weighting function. First the value of the weighting function should always be positive since for example, the mass and density of points are always defined as a positive integer; secondly, the weighting function should be decreasing in its value when the distance between the reference point and its neighbor points increases (i.e. the influence is local and vanishes as the distance increases).

In general, several weighting functions can be defined which is a modified version of composite quadratic tensor-product weight function defined in [26,27]. Some examples can be:

(3)

(4)

(5)

(6)

where is the distance between any two points (i.e. one being a reference point) and is a defined cut-off value. The cut off value in the weighting function has two main purposes. First, when is decreasing, it localizes the weights to points which are within the reduced neighborhood of the current reference point. When increases, it can offer a uniform and smooth contribution to the neighbor points. In general, weighting functions (4) and (5) are used for fluid modeling. (4) is used for solving a class of particle clustering problem and (5) is used for viscosity computation. (6) is also for modeling elastic object.

As an example, in Equation (1), the density of each point i is computed as:

(7)

where is the distance between point and. The volume of each point can now be computed as:

(8)

In Equation (2), the gradient of the displacement is defined as:

(9)

where, and

are the three row vectors denote the derivatives with respect to (x, y and z).

Using MLS, the basic idea is to expand the displacement about a point using Taylor Series expansion and define the displacement of the adjacent points in terms of the current point and up to the first order expansion of the series. The interpolated displacement is then define by value which minimizes the square of the error (Appendix). The overall computation results of evaluated at the point can be written as:

(10)

where for example, denotes the x-component of the displacement vector at the point.

In the above is a 3 × 3 matrix which can be precomputed at point and defined as:

(11)

where is a distance vector between points and expressed in the reference coordinate frame. Given the value strain from Equation (2) the strain energy stored computed at a point can be written as

.

The body force defined by used in Equation (1) is a function of displacement vector at point and the displacements of all the neighbors. Taking the derivative with respect to these displacements yields the forces acting at a point and all its neighbors:

(12)

where is the body force at a point, is the strain energy at a point and is the volume of a point. Based on Newton’s third law, the body force acting on a point is computed as the negative sum of all the body forces acting at its neighbor points,

(13)

Using the expression for and, we can determine the final expression of. The final expressions for the internal body forces can be written as:

(14)

where, and,

and are the volumes of the points and. In the above expression, the Jacobian matrix is computed from:

Preliminarily Comparison Study

In this section, we present the results of a haptic interaction environment based on the proposed framework. We also present some comparison study of evaluating tip deflection of the cantilever bean under constant load using point-based mechanics and FEM. The experimental setup consists of a desktop computational platform with Intel P4 3.0 GHz CPU, 1G RAM and the Phantom Omni haptic device. We define a collection of rectangular cross sectional objects composed by 90 points ((3 × 3 × 3)) points per cross section). The foundation points are evenly distributed with the spatial distance between each point of 0.015 m. In this experiment, both ends of the objects were fixed and represented with the red spheres.

In our experiment, we study the effect of different weighting functions defined in Equations (3)-(6). For example, Figure 2(a) shows the computation of foundation points based in the weighting function defined in Equation (3). This Figure also shows a virtual probe which represents the presence of the user in the haptic rendering environment. As shown in Figure 2(b), the user can interact with the point-based model of the block through haptic feedback device. When the contact is made between the virtual probe and the object, the point-based model of the object can deform and the resultant interaction forces is feb-back to the haptic device. In this Figure, green sphere represent the contacted point which the user is interacting with. Figure 2(c) shows and example of such haptic interaction. The Figure shows a plot of haptic force which was fed-back to the user over the duration of a part of the experiment.

In order to validate the computational model of the object based on the point-based mechanics approach, we conducted an experimental comparison with a commercially available standard FEM package. Our experimental model is similar to our haptic interaction model except we have constrained one end of the block while making the other end free of any constraints (i.e. a cantilever model). We have selected Young’s Modulus to Pa and Poisson’s ratio to 0.4. For the point-based mechanics model, we also have selected the cut off distance, , in Equation (3) to be 0.1 m. At each experiment, we have recorded the shape and the tip deflection of the model under a constant load. For the FEM, we also have defined the same object using the same boundary conditions and loading condition using a commercial FE software Comsol (http://www.comsol.com/). Figure 3 shows both the visualization and the results of our comparative study.

Figure 4 compares the magnitude of the deflection of a point at the tip of the cantilever. The axes are the magnitude of deflection under four constant load conditions. As it can be seen, under the same constant tip load force, both methods can yield to comparable results.

3. Definition of Levels-of-Detail

The proposed framework offers an approach where global deformation of an object can be computed using small number of points used in the local deformation solution. In order to establish relationships between the global and local deformation of object as a function of the sampled points, we study how the resolution of the object base model (i.e. object defined by foundation points) can affect the haptic frame rate through increasing the reso-

lution of the base point. The major computational challenge in our approach is the computation of the displacement gradient tensor for each of the points. Intuitively the basic approach is that we assume that the local deformation affects the points closer to the contact region. The contact force propagate through-out the body and the resultant internal forces are less propagated to the points beyond certain threshold. A localization or levels-of-detail (LOD) can be then be implemented to capture the above motivation where one should be able to both increase the realism of the haptic interaction while maintaining a high haptic rate. We propose an approach by defining influence ranges as a function of the distance of a point from the contact area. For example, in Figure 5 and at the instant of contact a dense sample of points of object inside a volume located at the tip of a probe can be considered as points located at the proximity of the contact area.

The local and internal deformation can propagate from the contact region to points defining the boundary of the object. Our initial algorithm associates the larger radius of propagation influence to smaller number of points being sampled from the foundation points comparing to the in between regions. We proposed a pseudo-random point selection algorithm which selects points within preset ranges/radii under pre-defined weighting factors defined through a random number generator. For example, the selection weighting factor for the localization range (i.e. range within the contact area) is set to be large since we require a high density of points in this range. On the other hand, the selection weighting factor for the influence range is set to be small since we only need a limited number of points to propagate the deformation from the contact region to the boundary points. This approach is analogous to the LOD scheme used in the finite element model, where the mesh density varies from fine mesh in

the region of interest to the coarse mesh in the boundary region. Figure 6 illustrates the schematic of the localization distance threshold. The points are selected based on their distance to the point of contact.

We define localization distance to be a linear function of the cut-off distance, and we use two different constants (and) to define the threshold of the localization distances as the selection ranges. Once being defined, and will remain constant through-out the computation. Similarly, we define propagation distance, , where indicates the level of propagation. We also define to be a linear function of. By changing the constants, the threshold distance of each propagation level can vary.

Once the contact is detected, the dynamic selection algorithm initiated to select the points in terms of the contact region and the propagation of deformation. After the selection, we incorporate selected points into the computation model and render the deformation effect. The selection function first generates a random number between 0 and 10 and determines the selection weighting factor. Then, it determines the distances between the current positions of neighbor points and the contact point. After that, it selects the points by comparing the distances with the threshold distance based on the selection weighting factor. If the distance is less than, the selection weighting factor is 1, and the point is directly selected. If the distance is between and, the weighting factor of selection is 0.8 (the probability of is). The points within the propagation levels are also selected based on the weighting factor of the propagation level. is a monotonically increasing integer in terms of propagation level, which controls the weighting factor of the propagation points being selected. The weighting factor of selection for level

is. The upper bound of is set to be 10.

Experimental Analysis

We conduct an experimental study to compare and analyze how the number of the propagation levels and the selection factors can affect the LOD model in haptic rendering. Figure 7 shows the initial foundation points which were used to represent the experimental object. Figures 8 and 9 show some examples of our experimental results comparing the different propagation levels and their selection weighting factors along with the system update rate. In the experiment, we apply a constant pulling force at the 111th point in the model, and plot the magnitudes of the displacements of all the points in the model at the 9th second in run time. The localization distances and remain unchanged and the selected

neighbor points are shaded in brown and blue.

We analyze how different cut-off distances of the localization can affect the frame rate in the LOD model. Table 1 compares the run time of the different localization cut off distances on different foundation points. As we increase the distance thresholds and, the rendering time per frame increases since more points are incorporated into the computation of deformation.

4. Conclusion

One of the main challenges of haptic rendering of virtual objects is methods for their realistic representation which can also offer a fast interactive computational framework. This paper investigated an approach which can be a bridge

between the realism and computational efficiency. The paper presents an overview of point-based mechanics approach and also demonstrated its implementation in a typical haptic interaction environment. In addition it is shown that the point-based mechanics approach can be defined and modeled which can give a comparable computational results to that of standard FEM. Another key advantages of the point-based method is that one can initialize a control volume of an object with collection of points where only subset of these points can be sampled during the simulation process. This is an important feature since during the run-time of simulation process, one can adaptively sample more points in the computational model for increased accuracy. In this paper, we investigated a 3D point-based object modeling approach for haptic rendering. It was shown that this approach can offer a comparable results to that of the FEM [20]. The proposed framework allows interaction where user can manipulate the point-based object model using a haptic device. We present a notion of levels-of-detail (LOD) where foundation points which can represent the object can be grouped into different levels. For this early study, we have presented an approach were base on the distance of points from the contact area. Points can be populated with different densities in various geometrical regions away from the contact point while including regions defined by the boundary points. Feasibility of the proposed LOD approach was studied to investigate the practicality of the proposed approach in changing the resolution of the points during the haptic interaction. This framework allows both inclusion of the material properties of the object and also direct mapping to various medical imaging modalities where scanned point-clouds can be mapped to the haptic interaction framework.

REFERENCES

Appendix

For derivation of the numerical solution of used in Equation (1), we utilized use the simplified expression defined in Equation (10) which treats the 3 × 3 matrix as three row vectors, and respectively. In the following, we define an approach where we can solve for these three vectors separately.

For example, let us evaluate the differential form of the x-component of the displacement vector. By definition, method based on MLS is first order accurate. Using the first order Taylor expansion of in the neighborhood of the point, we have:

(15)

where is the position vector of the point, is the small change in position, is the derivative evaluated at point which is written as

.

Suppose that and are known. By replacing in Equation (15) using the distance vector between point and, of the neighbor point of point can be approximated as,

(16)

where is the approximated value of. The measure of the error of the above approximation is given by a sum of the squared differences

(, since all the neighbor points j of point need to be taken into consideration and weighted by the weighting function as:

(17)

Substitute Equation (16) into Equation (17), we have:

(18)

Given point and its x-component displacement, the solution for the gradient is the one which minimizes the error. This becomes an optimization problem. By setting the derivative of with respect to to zero we can write:

(19)

We can solve for as:

(20)

where is computed as

(21)

which is a 3 × 3 matrix. e.g. is the x-component of distance vector). The spatial gradient of the other two components of the displacement vector (and) can be computed in the same derivation. In the main context of the thesis, we use denoting and denoting for simplicity.