ABSTRACT HAPTIC RENDERING FOR INTERNAL CONTENT OF AN IMPLICIT OBJECT

INTERNAL CONTENT OF AN IMPLICIT OBJECT

Thavida Maneewarn

Department of Electrical EngineeringUniversity of Washington

http://rcs.ee.washington.edu/BRL

Duane W. Storti

Department of Mechanical EngineeringUniversity of Washingtonstorti@u.washington.edu

ABSTRACT

The haptic rendering algorithms for object with implicit surfacerepresentation are proposed. The basic rendering algorithm for aregular two-dimensional manifold is used to represent a solidvolumetric object. For applications where information about theinternal content of an object is concerned, the haptic renderingalgorithm for internal content of an implicit object is developed. Theproposed algorithm is derived from the concept of state transition via‘port’ using manifold with boundary representation. Manifold withboundary is constructed from implicit primitives. The advantage ofimplicit surface representation in haptic applications has beenemphasized. Both algorithms were successfully implemented in thehaptic interface system and were applied to various implicit models.INTRODUCTION

Based on experience in the physical world, it is natural for humansto perceive objects as being more realistic as more of the senses areprovided the feedback normally associated with interactions with aphysical object. Since the goal of any CAD/CAM system is to providea virtual representation of a part, assembly, or environment that isperceived to be as real as possible. In this paper, we concentrate onhaptic feedback which provides the user with tactile sensations thateither simulate interaction with the real version of the virtual object orwhich are designed to assist in communicating characteristics of theobject. In particular, we focus on haptic rendering, the process ofcreating a synthetic force to replicate the reaction force associated withcontacting an object.

Previously introduced haptic rendering algorithms can beclassified according to their reliance on standard surfacerepresentations. Zilles [13] introduced the \"god-object\" approach thatallows polyhedral model to be rendered by restricting the surfacecontact point from passing through the object. Thompson [12] proposeda related algorithm that supports direct haptic rendering of NURBSsurfaces.

Some algorithms employ a local approximation of the surface toreduce computation time. Adachi [1] and Mark [4] use a slowly

Blake Hannaford

Department of Electrical EngineeringUniversity of Washington

http://rcs.ee.washington.edu/BRLMark A. Ganter

Department of Mechanical EngineeringUniversity of Washington

ganter@u.washington.educhanging planar approximation as an intermediate representation of asurface. Zilles [13], Morgenbesser and Srinivasan [7] and Ruspini[10] applied a technique called ‘force shading’, analogous to Phongshading in computer graphics, to render surface curvature byinterpolating surface normal vectors of polyhedral facets.

Methods that do not rely directly on surface representation of ageometric model have also been suggested, such as a potential fieldmethod due to Massie and Salisbury [5] and a voxel-based method [2]that determines haptic interaction forces based on the current positionof the user interaction point. Voxel-based methods are suited forrendering large volumetric objects, but they are memory intensive andmay not be applied to objects with feature sizes comparable to voxelsizes.

Implicit surface representationImplicit surfaces are two-dimensional, geometric shapes thatexist in three-dimensional space. The surface is implicitly describedby an analytic function S(p) as S(p) = 0. The use of implicit surfacesin computer graphics was initially introduced in scan-line renderingof quadric surfaces (Davis et al. [3] and Mittelman [6]). The implicitfunction characterizes volume as well as surface, since value of S(p)indicates the proximity between point P and the surface. Implicitfunctions can not only be used to describe basic geometric shapes.The model of complicate shapes can be achieved by applyingappropriate blending operations to basic implicit primitive [9]. Theuse of implicit surface representation in geometric modeling hasincreased due to its unique properties. These properties include simplecollision detection between a point and the surface that can beachieved from function evaluation. If S(p)<0, point P is enclosedinside the surface. If S(p)>0, point P is outside the surface and if S(p)= 0, point P is on the surface. The gradient of S(p) is proportional tothe surface normal vector pointing in outward direction. The gradientof S(p) can be described by

The surface normal vector indicates the direction of a responsive

∇S(p)=(∂S(p)/∂x,∂S(p)/∂y,∂S(p)/∂z)force from the implicit model. The gradient of an implicit equationcan be calculated both analytically and numerically. Another

interesting property is that the inside/outside can simply be reversed bysign inversion of S(p). This property is very useful in a renderingprocess for some class of objects, which will be discussed in thefollowing section.

The haptic rendering of implicit surfaces was first introduced bySalisbury and Tar[13]. They proposed a method for rendering solidobjects represented by regular two-manifold and extended to addressthe specific problem of rendering finites solid cones or cylinderscreated from intersecting half-spaces with an implicit solid. However,their method only applies to the surfaces enclosing solid volumetricobjects regardless of the internal content that may be confined insidethe surfaces.

In geometric modeling, the non-regularized manifolds such as‘manifold with boundary’ and ‘non-manifold’ are also concerned. Thenon-regularized manifold description can be applied to objects thatconsist of non-uniform or composite materials, mostly used inbiomedical or electronics applications. Manifold with boundary is asurface that locally approximated either by a disk or by a half-disk. Themanifold with boundary represents object that contains openings ordangling edges. The haptic rendering technique proposed in this papercan be applied to more general classes of objects in addition to the solidvolumetric object described by the two-manifold. We would like toemphasize the advantage of implicit representation in haptic renderingwhere the object interior can be haptically displayed. One exampledescribed here is to simulate the effect of having non-solid substanceconfined in the space enclosed by implicit surfaces, such as liquid in acup. The algorithm is very simple to implement and is notcomputationally expensive, which make it appropriate to be performedin real-time. The model can be well described by a small number ofimplicit equations. Thus only small memory space is required in thismethod unlike in voxel-based method or in polyhedral model-basedmethod.

Figure 1.1 A cup that contains liquid inside can be described bymanifold with boundary constructed from implicit primitives.

IMPLICIT HAPTIC RENDERING ALGORITHM

The haptic rendering algorithm for objects defined by implicitsurfaces can be described in two parts, the rendering algorithms for aregular two-dimensional manifold and the rendering algorithm forinternal content of an object using manifold with boundary description.Although the rendering algorithm for regular two-dimensional manifoldproposed here has several aspects that are quite similar to previouswork by Salisbury and Tar [11], our implementation details aredifferent from theirs in various points. For instance, the Lagrangianmultiplier is used, in the method introduced by Salisbury and Tar, in

order to find the surface contact point which minimize distancebetween the seed point (the probe point that is inside the surface forthe first time) and the point on the surface. The problem of using theclosest point on the surface instead of the actual surface crossing pointcan be illustrated in figure (2.1). When the probe point approaches theconvex surface, the surface contact point is established atPo′(k)which is the nearest point from P(k)instead of the actualsurface crossing point at Po(k). The responsive force that iscalculated from Po′(k) may be incorrect and it may cause anundesirable effect. In our algorithm, the binary search is used toestablish the surface contact point at the crossing point between a linesegment and the surface, which will provide better accuracy. Detailsof our haptic rendering algorithm for a regular two-dimensionmanifold will be described in the following section.

P′o(k)Po(k)P(k)P(k−1)Figure 2.1 A situation where surface contact point can be incorrectlyestablished at the closest point between the seed point and the implicitsurface.

Rendering a regular two-dimensional manifold

The rendering algorithm for regular two-dimensional

manifold is an important basis for more complicate renderingalgorithm that will be presented in the next section. Two-dimensionmanifold is often used to describe the surface enclosing solid objectswhere the point-set inside the surface is entirely separate from theoutside space. When the probe point is contacting with solid objects,the responsive force is a force that prevents a probe point frompenetrating into the surface. The responsive force is defined by anequation f=K(Po(k)−Pi(k))−BV(k), where K represents

stiffness and B represents damping of a solid object. Po(k) is thesurface contact point and Pi(k) is the interaction point inside thesurface. V(k) is velocity of the probe point.

f=K(Po(k)−Pi(k))−BV(k)Po(k)Pi(k)Figure 2.2 A responsive force resulted from contacting the surface

The algorithm for calculating the responsive force can be described asfollowed. Po(k) and Pi(k), which are used in force calculation, arefound from algorithm I and II, depends on the condition of the currentposition (P(k)) and the previous position (P(k-1)) of the probe pointinput. The collision occurs when the probe point is inside the surfacefor the first time which means P(k-1) is outside the surface(S(P(k−1))>0) and P(k) is inside the surface (S(P(k))<0). Whenthe collision occurs, algorithm I is used to define the new interactionpoints Po(k) and Pi(k). After the collision and if P(k) still be insidethe surface, algorithm II will be used to define the next interactionpoints. Note that, in the special case where point Po(k)which iscalculated from algorithm II is too far outside the surface ( S(Po(k))>ε), the new interaction points will have to be recalculated asthe surface crossing point on the line segment fromPo(k) to Pi(k)using algorithm I.

Algorithm I is performed when the probe point P(k) collides

with the surface for the first time. The surface contact point Po(k)isestablished at the point where the surface crosses the line segmentbetween point P(k) and P(k-1). The implicit function S(p) evaluateszero at Po(k) . Since the update rate in haptic rendering process is veryhigh, only a small movement is permitted within one interval (i.e.distance between P(k) and P(k-1) is small). The surface crossing pointwhere S(Po(k))=0can be found using binary search along the segmentbetween P(k) and P(k-1). (Figure 2.3)

P(k-1)

P(k)Figure 2.3. The surface contact point Po(k) is found on the linesegment between P(k) and P(k-1)

After the surface contact point Po(k) is founded, the

interaction point inside the surface Pi(k) is established by mapping theprobe point input P(k) onto the surface normal vector at Po(k) so thatthe direction of force vector calculated from Po(k) and Pi(k) isappropriately defined with respect to the implicit surface.

P(k)Po(k)ImplicitSurfaceFigure 2.4 The interaction point inside the surface Pi(k) isestablished from P(k) and the surface normal atPo(k)

It is also important to make sure that Po(k) is not inside the surface.Therefore, when implicit function evaluated at Po(k) is less thanzero, Po(k)has to be moved outside the surface by a very smalldistance (specified by α as shown in algorithm I) in the direction ofsurface normal evaluated atPo(k).

Algorithm I: Find the new interaction point

%% Find Po(k)

If P(k) is inside the object for the first time

%% Binary search for the interaction point on thesurface Do

Po(k) = (P(k)+P(k-1))/2;

Until S(Po(k)) < ε or MAX_N iter.%% Find Pi(k)

%% N(P(k)) is the surface normal vector at pointP(k)

vP(k)=(Po(k)−P(k))

Pk)=P(k)+((vP(k)⋅N(Po(k))

i((Pk))⋅N(PN(Po(k))−vP(k))%%

No(o(k))

check if Po(k) is inside the surface then modifyPo(k)

if S(Po(k)) < 0

Po(k))

o(k)=Po(k)−

αS(PN(Pk))

N(Po(k))

o(return Po(k) and Pi(k)

When the probe point is still inside a surface after the first collisionwith the surface, Algorithm II is used to move the interaction point onthe surface from the previous state Po(k−1) to the new position onthe surface based on the movement of probe point P(k-1) to P(k). Themovement of the probe point inside the surface is used to calculatedthe interaction point Po(k), by mapping the vector from P(k-1) to P(k)onto the tangent plane at Po(k−1). Po(k) is modified by a smalldistance in the direction of the surface normal evaluated at Po(k−1)to guarantee that Po(k)will not be inside the surface.

Pi(k) is also calculated in the same way as in Algorithm I so that thedirection of reactive force is defined correctly with respect to theimplicit surface.

Po(k)P(k)V(k)Tangent Plane P(k-1)ImplicitSurfaceFigure 2.5 The surface contact point Po(k)is established based on themovement of probe point inside the surface

Algorithm II: Find the next interaction point%% Find Po(k)

V(k)=(P(k)−P(k−1))

Po(k)=P)+(V(k)−V(k)⋅N(Po(k−1))o(k−1N(PN(Po(k−))o(k−1))⋅N(Po(k−1

))1

−α⋅(S(PN(Po(k−1))o(k−1

)N(Pk−1

)o())%% Find Pi(k)

vP(k)=(Po(k)−P(k))

P⋅N(Po(k))

i(k)=P(k)+(

(vP(k)N(PPN(Po(k))−vP(k))

o(k))⋅N(o(k))

return Po(k) and Pi(k)

Rendering the internal content of an implicit object

Normally, a solid model is represented by a closed surface

separated the outside space from the inside. In the regular solid model,no information about what contains inside the surface is available. Inpractice, internal content of an object often provides significant amountof useful information, such as property of composite material thatcontained inside the object or a special form of internal structure of theobject. The ability to sense internal content of an object becomes moreimportant in several applications especially in biomedical andelectronics applications.

The internal content of geometric model can be described by

manifold with boundary. The reason that manifolds with boundary areused is so that the transition between internal and external space canonly occur within the restrictive region. Using the manifold withboundary representation, the opening region bounded by the manifoldboundary is defined as ‘port’ where the transition between spaces takesplace. In other word, internal content of an object can only be displayedafter the probe point has entered a defined region called ‘port’. Theconcept of traveling through ‘port’ allows interior and exterior force ofthe geometric model to be distinctively displayed via state transition.

Manifold with boundary is constructed from implicit

surface primitives. Implicit surface representation is required becauseimplicit function posses unique properties that the surface can besimply reversed by a sign inversion and inside/outside can be easilydetermined by evaluating an implicit function. The exterior force isdefined to simulate the responsive force from contacting the exteriorsurface of a geometric model. Haptic rendering process for theexterior surface can be performed in the same way as for a regulartwo-dimensional manifold surface described in the previous section.Internal content can be displayed by various techniques depends onmaterial property or the arrangement of the internal structure. Forexample, viscous effect can be used to represent non-solid viscoussubstance that confined inside the implicit surface or a spatial periodicoscillation can be used to represent a grid-like structure of internalmaterial.

As a basic example, the manifold with boundary

constructed from an implicit half-plane and a sphere is demonstrated(as shown in figure 2.6). The state transition conditions for these twoimplicit primitives are shown in Table I. Four distinctive regions aredefined in the state transition table. State transition is only performedwhen the probe point is traveling through the ‘port’ which defined asan intersect region between a half-plane and a sphere. If the probepoint is inside both surfaces (a sphere and a half-plane), the exteriorsurface of a sphere will be displayed unless the probe point hasentered ‘port’ in the previous state. In that case, the internal content ofa sphere will be displayed instead. In this example, a sphere containerthat contains non-solid viscous substance is simulated. The exteriorforce is calculated as the responsive force from contacting the outershell of a sphere container. The interior force is a combination of theviscous resisting force and contacting force from the surface interior.The viscous resisting force is proportional to velocity of the probepoint, which can be described by the equation Fv=−BvV(k) , where

Bv is the viscous coefficient of a simulated non-solid substance and

V(k) is the probe point velocity. The contacting force from the surfaceinterior is calculated in the same way as the responsive force fromcontacting a regular two-manifold, except that the reversed implicitfunction of sphere is used instead. At each servo loop, collisiondetection between the probe point and implicit surfaces is performedfor each surface in the same way as described in the method for aregular two-manifold. The proper responsive force is calculated basedon the status of the probe point as shown in the state transition table.

A half-planeAn implicit sphere containerFigure 2.6. Manifold with boundary that represents a spherecontainer, constructed from a sphere and a half-plane.

StateSphereHalf-plane1ININ

If (the previous state is 2) ENTER_PORTElse

If (ENTER_PORT has occurred) Find a viscous resisting force Else

Find a contact force of sphere-exterior surface

2INOUTIf (the previous state is 1) EXIT_PORT

3

OUT

IN

If (ENTER_PORT has occurred) Find a contact force of reversed -sphere surfaceElse F = 04OUTOUT

F = 0

Table I. State transition table for 2 implicit primitives

More complex example is illustrated in figure 2.7. Compositematerial is confined inside a cylinder tube. In the case where n implicitsurfaces are required to describe a model, 2n distinctive regions areintroduced. Different material properties will be displayed as the probepoint passes through each layer. Although state transition table for thismodel will be much more complicate than in the previous example, it isbased on the concept where conditions can be tested iteratively. (i.e. theprobe point cannot enter port 2,3,4 unless it has entered port 1,therefore it is not necessary to test every conditions at each servo loop.)The rendering algorithm for complex internal structure within ageometrical model can be simplified by applying this concept of statetransition through ‘port’ model.Port 1Port 2Port 3Port 4Figure 2.7 A cylinder tube that contains composite material can bemodeled using state transition via ‘port’ concept.

State transition via ‘port’ can also be applied to an applicationwhere the ‘flow direction’ is concerned. The flow direction means thatonly a certain direction is allowed to travel within a defined space.According to the state transition via ‘port’ paradigm, arbitrary regioncan not be accessed unless the probe point has traveled through theprior region defined by a sequence of ‘port’.

Objects with complicate shape can be modeled both

externally and internally by applying constructing techniques to basicimplicit primitives as we has discussed earlier. The haptic renderingalgorithm proposed here emphasizes the advantage of implicit surfacerepresentation in haptic applications where the object interior can behaptically displayed as well as the exterior surface.

HAPTIC INTERFACE SYSTEM

The implicit haptic rendering algorithm described above wasimplemented in the haptic interface system at Biorobotics LaboratoryUniversity of Washington using Excalibur, the 3 degree-of-freedomhaptic linear haptic display device (shown in figure 3.1). TheExcalibur was designed and manufactured by HapticTechnologies,Inc. of Seattle, WA. The user can provide the positional input bymoving the handgrip that connects to light linkage elements. The 3-dimensional force feedback is generated from motors mounted on thebase of the mechanism. The Excalibur is using steel cabletransmission that enables high forces and high rigidity in the three-axis translation motions. The workspace of the device is300x300x200 mm3 with the maximum force of 100 N and theposition resolution of 0.008 mm.

The haptic rendering algorithm is implemented on a 266 MHzPentium II processor PC that controlled the Excalibur in real-timewith the update rate of 1 KHz.

Figure 3.1. Excalibur, the 3 degree-of-freedom haptic linear hapticdisplay device

Several examples of implicit models were haptically

rendered using the methods described in the previous section. Theseexamples include

1. Basic shapes such as sphere, ellipsoid, cube and heart.2. Metaballs: 2-5 blended spheres.

3. CSG: union, intersection and difference of basic primitives suchas ellipsoid and cube.

4. Implicit container: A sphere container with the opening on thetop (Figure 3) that contains liquid with adjustable viscouscoefficient.

The user was able to correctly recognize the shape of

rendered objects by using tactile senses alone without graphicalinterface. The proposed algorithm is simple and computationallyinexpensive enough to be performed within 1 millisecond timeinterval. However, undesirable oscillation sometimes occurs in highconvex curvature region. Applying the appropriate adjustment to thenormal vector calculation procedure may alleviate this problem. Thebounding box or localization technique should be implemented in thealgorithm so that more complex model which consists of a largenumber of primitives can be haptically displayed in real-time.CONCLUSIONS

The implicit surface representation is well suited for haptic

applications, especially for modeling the object consisting of quadric

primitives. Constructing techniques in geometric modeling allowcomplex shapes to be haptically displayed as well as basic shapes. Thehaptic rendering methods for a regular two-dimensional manifold andfor the internal content of an object were presented in this paper. Theproperties of implicit surface representation are suitable to be applied tohaptic rending process for both classes of objects. The new concept ofstate transition via ‘port’ model is introduced so that the internalcontent of an object can be rendered haptically. Haptic rendering ofvarious implicit models was demonstrated including the combination ofgeometric primitives and the model of implicit container that containsnon-solid viscous substance. Unfortunately, implicit surfacerepresentation is still not widely used in geometric modeling compareto other well-established methods such as parametric surfacerepresentation or boundary representation. This factor may prevent theimplicit haptic rendering technique to be applied to the existinggeometric modeling system. Hopefully, as the attention of implicitsurface modeling in graphics increases, it will consequently bring moreinterest into implicit haptic rendering applications in the near future.REFERENCES

[1] Y.Adachi, T.Kumano and K.Ogino, Intermediate representation forstiff virtual objects, Proc. Virtual Reality Annual Intl. Symp., (ResearchTriangle Park, NC, Mar 11-15, 1995),203-210.

[2] R.S. Avila and L.M Sobierajski, A haptic interaction method forvolume visualization, Visualization ’96 Proc. (October, 1996).[3] J.R.Davis, R.Nagel and W.Guber, A model making and displaytechnique for 3D pictures, Proc.7th Annual Meeting ofUAIDE,(1968),47-72.

[4] W.R.Mark, S.C.Randolph, M.Finch, J.M.Van Verth, and

R.M.Taylor III, Adding force feedback to graphics systems: issues andsolutions, Proc. SIGGRAPH 96, (New Orleans, Aug 4-91994),447-452.

[5] T.Massie and K.Salisbury, The PHANToM haptic interface: adevice for probing virtual objects, Proc. Of ASME Winter AnnualMeeting, Symp. Haptic Interfaces for Virtual Environment andTeleoperator Systems, (Chicago, IL, Nov. 1994).

[6] P.Mittelman, Computer graphics at MAGI, Computer Graphics 83,(London, Online Publications, 1983), 291-301.

[7] H.B. Morgenbesser and M.A. Srinivasan, Force shading for hapticshape perception, Proc.ASME Winter Annual Meeting, (1996).

[8] H. Nishimura, M. Hirai, T. Kawai, T. Kawata, I. Shirakawa and K.Omura, Object modeling by distribution function and a method of

image generation, Trans. Inst. Of Elec. And Comm. Eng. Of Japan, vol.J68-D, no. 4, (1985), 718-725.

[9] A. Ricci, A constructive geometry for computer graphics, TheComputer Journal, Vol.16, No.2, (1973), 157-160.

[10] D. Ruspini, K.Kolarov and O.Khatib, Robust Haptic Display ofGraphical Environments, in: J.K.Salisbury and M.A. Srinivasan, ed.,Proc. Of the First PHANToM Users Group Workshop, M.I.T. ArtificialIntelligence Laboratory Technical Report AITR-1596, (1996).

[11] K.Salisbury and C. Tar, Haptic rendering of surfaces defined byimplicit functions, Proc. ASME Dyn. Sys. and Control Div., DSC-Vol.61,(1997),61-67.

[12] T.V.Thompson II, D.E.Johnson and E. Cohen, Direct hapticrendering of sculptured models, Proc. Sym. Interactive 3D Graphics,(Providence, RI, April 27-30, 1997) 1-10.

[13] C. Zilles and K. Salisbury, A constraint-based god-object methodfor haptic display, Proc.IROS-95, Vol.3, (Pittsburgh, Aug 6-9, 1995),146-151.