INTRODUCTION
Real time interaction with deformable objects is one of the interesting and
challenging areas of study especially with applications to medical simulation
and interactive training simulators. Augmenting such simulators with haptics
makes it more demanding as it requires more computation. Refresh rate of visual
channel is 30 Hz while haptic channel refresh rate is close to 1 kHz (Peterlik
et al., 2010). Therefore, efficient algorithms are needed for interacting
with soft bodies using force feedback devices.
There are two methods used in computer graphics for modeling deformable objects:
| • |
Geometry based: In geometry based deformation, the
geometry of the model is directly manipulated but the internal physics and
dynamic interactions are not considered. In this category two approaches
used are vertex based and spline based deformation |
| • |
Physics based: These models simulate the physical behavior
of objects and consider the internal and external forces. In physics based,
FEM (Finite Element Method) and Mass Spring System are used in computer
graphics for deformable objects simulation |
Many techniques for surface representation are used for soft body simulation.
One popular technique, among many is subdivision which achieved much attention
in the recent years. Two main categories in subdivision are interpolatory and
approximating schemes. In interpolatory subdivision schemes the original vertices
are carried over to the next level of subdivision while in approximating schemes,
the original vertices are not retained at newer levels of subdivision. Butterfly
(Dyn et al., 1990), Modified Butterfly (Zorin
et al., 1996) and Kobbelt (1996) are interpolatory
subdivision schemes while Doo and Sabin (1978), Catmull
and Clark (1978) and Loop are approximating. These are the popular techniques
in the area of surface subdivision.
These schemes provide global refinement at every subdivision level. Practically,
it is seen that some areas in a mesh become smooth after few subdivisions while
other still need further subdivision to achieve smoothness. In such application,
global refinement leads to a heavy computational load because of subdividing
regions of a mesh which are already smooth. Adaptive subdivision removes this
extra computation while maintaining the smoothness.
Adaptive subdivision first proposed by Muller and Jaeschke
(1998) for Catmull-Clark and Doo-Sabin subdivision schemes. Xu
and Kondo (1999) developed an adaptive scheme based on the Doo-Sabin scheme.
Kobbelt (2000) revised his Kobbelt scheme by introducing
adaptive subdivision and also for v3 subdivision scheme.
Adaptive refinement is also integrated with the Physics based Mass Spring System
for deformable objects. An adaptive mass spring model was used for a piece of
cloth which refine the regions of high curvature (Hutchinson
et al., 1996). O’Brien and Hodgins (1999)
simulated the fracture of glass by adaptively refining the mesh at glass fractures.
Kawai (2001) builds hierarchical mass spring model to
achieve adaptive refinement during object deformation. Another method refines
adaptively triangular mesh which is independent of regularity of the initial
mesh (Choi et al., 2002). The algorithm proposed
by Kahler et al. (2003), dynamically refines
the mesh at high curvature which is integrated with the mass spring model.
An adaptive subdivision is also integrated with mass spring model (Zhang
et al., 2002). The model refines in the region where the external
force is applied by force feedback device. They used Loop subdivision scheme
in the area of interest but the mesh they used in their experiment is regular.
Mass Spring Systems have been largely used for deformable objects because it is easy to implement and because of low computational complexity. However, even with Mass Spring System increasing number of nodes and springs makes the deformation difficult. But for higher resolution and realistic view more nodes are necessary. Therefore, to cope with such problem, a local refinement is a good choice. Previous methods apply local refinement to the whole selected area irrespective of the refinement needs in some of the regions. In this study, we propose an Area based adaptive subdivision algorithm based on Loop subdivision scheme which is integrated in the Physics Based deformation using Mass Spring Model. The algorithm refines the area adaptively for smooth deformation upon contacted by the force feedback device. During subdivision process, the physical properties of the deformable object are maintained. Our algorithm removes unnecessary nodes which ease extra computation in terms of spring forces and also improve smooth deformation.
MASS SPRING SYSTEM
In deformable body simulation, the physics behind must be quick enough to achieve
real time performance. Mass Spring Model is well suited for such simulation
and has been used extensively in medical and virtual reality simulators. A mass
spring model consists of point masses also known as nodes and springs. These
nodes are connected to each other by springs which are source for propagating
energy among these nodes. In our model, the surface is made up of triangles.
Each edge of a triangle acts as a spring and each vertex as node. The spring
connecting two nodes holds it in place. For our model, two meshes are maintained
(Zhang et al., 2002). One mesh called Fixed Mesh
is for maintaining the shape of the object and the other called Deformable Mesh
is used in simulating deformation. Nodes in two meshes are also connected with
springs whose spring stiffness is denoted by kh and there is no spring
force on the point masses in Home Mesh. Home springs come into play when the
mesh is deformed using haptic force feedback by applying force on nodes to bring
it back to the original resting position. The mass spring model used is shown
in Fig. 1.
The dynamics of nodes in a Mass Spring Model is governed by Newton’s law of motion and is given by:
where, ui`, 
and 
are the position, velocity and acceleration vectors of node i, respectively.
mi, ci and ki are scalar and represent mass,
the damping and stiffness coefficient of node i. Fint is the spring
force vector acting on node i, due to springs connecting node i and Fext
is the external force vector exerted on node i, through a haptic force feedback
device.
Rest length l of all the springs in the model that define the original
shape of the model, is pre computed and stored. When a node change its position
from u1 to u2 and its velocity from v1 to v2
then the internal force Fint can be calculated as:
where, F1int and F2int are the
spring forces on node 1 and 2, respectively.
|
| Fig. 1: |
Mass spring model with home and mesh spring |
In Eq. 2, ks is a spring constant and kd
is a damping constant. l is the rest length of the spring. Δu =
u1-u2 is the actual distance between two nodes and Δv = v1-v2 is the difference
of velocities of two nodes. Spring force is proportional to the difference of
length of the spring and damping force is proportional to the difference of
velocity of the node.
There are many techniques which are used for numerical solution. For the numerical solution of Eq. 2, implicit or explicit methods may be used. If the time step is large then implicit methods are good candidates. In deformable and soft object simulation, time step must be small enough so that smooth deformation is achieved. In this case explicit methods are good which guarantees smooth deformation. Here we used Runge-Kutta order 4 methods. General form of Runge-Kutta equation is given as:
Where:
Here h is the step size.
AREA BASED ADAPTIVE REFINEMENT
The model is made manually using Blender 3D modeling software [http://www.blender.org/].
Making a model manually using 3D modeling software, it is not necessary that
all triangles area should be the same. Consider Fig. 2 which
is a portion of 3D model.
It is clear in Fig. 2, that some triangles have larger area
while other has small area. If such mesh is divided by any existing subdivision
techniques then all triangles will be divided irrespective of its area. The
disadvantage is that extra triangles need to be rendered and also extra spring
force computation and integration.
An area based adaptive subdivision technique is proposed which divides only the large area triangles. Each triangle is divided using Mid Point subdivision technique into 4 triangles during each subdivision. This is shown in Fig. 3. For such subdivision, a threshold area (thresholdArea) is used. The threshold area is used to stop the subdivision and is chosen by hit and trial method during several visual experiments.
During a pre-processing step, the area of each triangle is computed and stored.
| The pseudo-code of our algorithm |
|
|
| Fig. 2: |
Coarse triangular mesh of varied triangle areas |
|
| Fig. 3: |
Mid point subdivision |
SETTING PARAMETERS OF MASS SPRING SYSTEM
Setting mass of a new node: In adaptive subdivision, new points are added which needs to be assigned masses such that it balances the forces applied to the coarse triangular mesh.
The mass of newly added point is calculated as:
where, Mold point is mass in the coarse mesh and Mnew is node in the new subdivided mesh. The numOldM is the number of nodes in the contacted region and numNewM is number of new nodes in the same contacted region through Haptic Contact Point.
Setting spring constant: In adaptive refinement the spring constant
ks needs to be recalculated so that the surface reflects the same
force through haptic force feedback as before subdivision, otherwise the surface
will feel stiffer. In our algorithm, when the haptic force feedback contact
a triangle then this triangle and all its neighbors are subdivided meeting the
area condition. So all new nodes must be assigned new spring constant so that
it requires the same force for deformation as before and same force reflection
:
where, N is the number of nodes.
EXPERIMENTAL RESULTS
We used several coarse meshes and applied the proposed area based subdivision algorithm as well as the simple subdivision algorithm. It is shown in Fig. 4.
A coarse mesh is taken and is refined using two levels of mid point subdivision and by proposed area based adaptive subdivision methods. Red dot in the Fig. 4 is a node contacted by a haptic force feedback device. In both cases all neighbors which are directly connected to the Node contacted are chosen for subdivision. Midpoint subdivision divides the region without considering the area of a triangle and so small area triangles are refined more. Our proposed algorithm divides only the triangles whose area is under the threshold and thus gives uniform area triangles which during deformation give realistic view.
Figure 5 shows that for the same coarse mesh, to achieve
same visual deformation, midpoint algorithm produce more triangles as compared
to the proposed algorithm.
|
| Fig. 4(a-c): |
(a) Coarse mesh (b) refined using mid point subdivision and
(c) refined using area based adaptive subdivision |
|
| Fig. 5: |
No. of triangles for the same coarse mesh using mid point
and area based adaptive subdivision |
The proposed algorithm is efficient in terms of time as well as memory.
CONCLUSION
In this study, an area based adaptive subdivision algorithm is proposed and is compared with mid point uniform subdivision algorithm. The algorithm achieves same visual results as mid point uniform algorithm but saves time as well as memory. In haptic environment as the sense response is much higher than visual response, therefore efficient algorithms for deformation are required to meet real time requirement. This algorithm works well for our deformable model because the penetration depth of the haptic probe is not high.
Subscribe Today
