Dangxiao Wang · Jing Xiao Yuru Zhang Haptic Rendering for Simulation of Fine Manipulation Haptic Rendering for Simulation of Fine Manipulation Dangxiao Wang Jing Xiao (cid:129) Yuru Zhang Haptic Rendering for Simulation of Fine Manipulation 123 Dangxiao Wang JingXiao YuruZhang Universityof North CarolinaatCharlotte BeihangUniversity Charlotte, NC Beijing USA China Additional material tothis bookcanbedownloaded from http://extras.springer.com/ ISBN 978-3-662-44948-6 ISBN 978-3-662-44949-3 (eBook) DOI 10.1007/978-3-662-44949-3 LibraryofCongressControlNumber:2014950648 SpringerHeidelbergNewYorkDordrechtLondon ©Springer-VerlagBerlinHeidelberg2014 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartof the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation,broadcasting,reproductiononmicrofilmsorinanyotherphysicalway,andtransmissionor informationstorageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilar methodology now known or hereafter developed. Exempted from this legal reservation are brief excerpts in connection with reviews or scholarly analysis or material supplied specifically for the purposeofbeingenteredandexecutedonacomputersystem,forexclusiveusebythepurchaserofthe work. Duplication of this publication or parts thereof is permitted only under the provisions of theCopyrightLawofthePublisher’slocation,initscurrentversion,andpermissionforusemustalways beobtainedfromSpringer.PermissionsforusemaybeobtainedthroughRightsLinkattheCopyright ClearanceCenter.ViolationsareliabletoprosecutionundertherespectiveCopyrightLaw. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publicationdoesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexempt fromtherelevantprotectivelawsandregulationsandthereforefreeforgeneraluse. While the advice and information in this book are believed to be true and accurate at the date of publication,neithertheauthorsnortheeditorsnorthepublishercanacceptanylegalresponsibilityfor anyerrorsoromissionsthatmaybemade.Thepublishermakesnowarranty,expressorimplied,with respecttothematerialcontainedherein. Printedonacid-freepaper SpringerispartofSpringerScience+BusinessMedia(www.springer.com) Foreword Extending the frontier of visual computing, touch-enabled interaction, such as haptic rendering, is an alternative form of human–computer interfaces and infor- mationpresentation,inadditiontographicalandauditorydisplay.Hapticrendering offers a unique, bidirectional communication between humans and interactive systems through tactile sensory cues, providing a more natural and intuitive interface. Following emerging development and recent advances in haptic render- ing,thisbookbyWangetal.presentsthelatestprogressonsix-degree-of-freedom (6-DoF) haptic display for fine manipulation. Most physicalobjects inthe real worldrequire fine manipulationand controlto handle them. Our hands grasp and exert forces to move objects and perform dex- terous manipulation in assembly, inspection, routine maintenance, surgery, and many other complex operations. To perform similar tasks using haptic devices introduces significant computational challenges. This book describes several key concepts and suggests new approaches for performing 6-DoF fine manipulation of rigid and deformable objects with complex geometry using haptic devices. The seamless blending of design, algorithms, and application provides an excellent overview of this important topic for both practitioners and researchers working in fine manipulation and haptic rendering. Chapel Hill, NC, USA, September 2014 Ming C. Lin v Preface Haptic rendering is the process of computing and generating forces in response to user interactions with virtual objects. Six-degrees-of-freedom (6-DoF) haptic ren- dering simulates both forces and torques during physical interactions between a virtual tool moved byahuman user viaahaptic deviceandtheobjects inavirtual environment.Boththetoolandtheobjectscanpossesscomplexshapes.Forcesand torquesexertedonthevirtualtoolarecomputedanddisplayedtothehapticdevice. In this book, we introduce the latest progress on 6-DoF haptic rendering for fine manipulation. Fine manipulation is pervasive in the real environment, such as in surgical operation, mechanical assembly, inspection, and maintenance tasks. 6-DoF haptic simulation of fine manipulation is a difficult problem because of multi-region contacts,narrowspaceconstraints,andrequirementstopreservetheappearanceand tactile sensation offine-features. Compared to the fields of computer graphics and speechsynthesis,hapticrenderingisstillayoungresearchfield.Highperformance rendering methods are needed to simulate physical responses in various fine manipulation scenarios, such as the nonlinear behavior of human tissue during surgical process, or the contact forces from multi-region contacts involving fine geometric features during assembly of complex structures such as an airplane. In this book, we introduce a systematic, constraint-based approach for 6-DoF haptic rendering that is particularly suitable for fine manipulation. We also intro- duce itsapplication tovirtual trainingfordental operations. Weprovide programs, 3Dmodels,andvideosfordownload.Allthesematerialsareavailableonlinefrom the book website http://extras.springer.com/. Thestructureofthisbookisorganizedasfollows.InChap.1,weprovideabrief introduction to the history of haptic rendering and a literature survey on 6-DoF hapticrendering.Wenextintroducetheconceptoffinemanipulationandassociated computational challenges for haptic rendering. In Chap. 2, we introduce a config- uration-basedoptimizationapproachbasedonmodelingnon-penetrationconstraints by sphere-trees, which can realize stable and responsive haptic rendering between rigid objects with 1kHz. In Chap. 3, we extend the approach to simulating fine geometric features, such as sharp edges. In Chap. 4, we extend the approach to vii viii Preface simulating deformable objects and hybrid contacts, which are characterized by simultaneousinteractionsbetweenatoolwithbothrigidanddeformableobjects.In Chap. 5, we introduce a measurement-based approach for achieving objective and quantified evaluation of the fidelity of 6-DoF haptic rendering, which is not only applicable tothe introduced approach inthis book but also toother existing haptic renderingapproaches.Inordertoprovideanintuitiveapplicationandvalidationof the introduced haptic rendering approach, in Chap. 6, we describe the design of a dentalsimulatorthatvalidatestheapproachon6-DoFhapticrenderingandprovides the functions and user evaluation results of the system. Finally, in Chap. 7, we summarize the book by discussing open challenges and possible research topics in this exciting field. Target readers of the book include but are not limited to: (cid:129) Researchers and scholars in the field of haptics; (cid:129) Software developers and engineers for developing haptic applications, including virtual surgery, computer games, virtual product prototyping, upper limb reha- bilitations, etc.; (cid:129) Researchers and developers in dental education and professional training; (cid:129) Graduate students in related majors, such as computer graphics, animation, vir- tual reality, and robotics. We are grateful for the support of the Natural Science Foundation of China (under grant No. 50275003, 50575011, 61170187 and 61190125) to our research on this topic. We also thank our collaborators, Prof. Peijun Lü, Prof. Yong Wang, and Prof. Jianxia Hou in the School and Hospital of Stomatology, Peking Uni- versity, Beijing, China. They provided valuable dental knowledge and support for carryingoutuserevaluationfortheiDentalsurgicalsimulator.Wethankourcurrent and former graduate students, Dr. Ge Yu, Dr. Jun Wu, Ms. Yu Wang, Ms. Renge Zhou, Ms.Wanlin Zhou, Mr. Xin Zhang, Mr. Zhixiang Wang, Mr. Hui Zhao, Ms. ShuaiLiu,Ms.YoujiaoShi,Mr.ZhongyuanChen,Mr.HaoTongandMr.Xiaohan Zhao.Theirhardworkprovidedthefoundationforthisbook.Lastbutnottheleast, wethankDr.LanlanChangforhersupportandvaluablehelpinpreparingthebook, andMs.JaneLifororganizingtheeditingprocessofthebook.Theirinputwasvery helpful for improving the manuscript. July 2014 Dangxiao Wang Jing Xiao Yuru Zhang Contents 1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Haptic Interaction Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1.1 Human Haptic Perception and Manipulation. . . . . . . . . . 1 1.1.2 Classification of Haptic Interfaces. . . . . . . . . . . . . . . . . 3 1.1.3 Overview of Haptic Interaction Systems. . . . . . . . . . . . . 4 1.1.4 Example Applications . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2 Haptic Rendering: A Brief History. . . . . . . . . . . . . . . . . . . . . . 6 1.3 6-DoF Haptic Rendering. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.3.1 Penalty-based Approach. . . . . . . . . . . . . . . . . . . . . . . . 9 1.3.2 Constraint-based Approach. . . . . . . . . . . . . . . . . . . . . . 11 1.3.3 Impulse-based Approach . . . . . . . . . . . . . . . . . . . . . . . 12 1.4 Fine Manipulation and Its Computational Challenges. . . . . . . . . 12 1.4.1 Characterization of Fine Manipulation . . . . . . . . . . . . . . 12 1.4.2 Narrow Space Constraints . . . . . . . . . . . . . . . . . . . . . . 15 1.4.3 Simulation of Fine Features . . . . . . . . . . . . . . . . . . . . . 17 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2 Configuration-based Optimization Approach. . . . . . . . . . . . . . . . . 21 2.1 Overview of the Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.1.1 Problem Formulation. . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.1.2 Framework. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.2 Object and Contact Modeling Using Sphere Trees. . . . . . . . . . . 26 2.2.1 Difficulties of Using Polygonal Meshes to Model Objects. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.2.2 Contact Modeling Based on Sphere Trees . . . . . . . . . . . 30 2.2.3 Construction of Sphere Trees . . . . . . . . . . . . . . . . . . . . 31 2.3 Collision Response. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.3.1 Non-linear Transform from C-Space to Cartesian Space. . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.3.2 Linearized Model of the Non-penetration Constraints. . . . 33 ix x Contents 2.3.3 Active Set Method for Solving Constrained Optimization. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.3.4 Contact Constraint-prediction Algorithm (CCP). . . . . . . . 35 2.4 Six-dimensional Force/Torque Simulation. . . . . . . . . . . . . . . . . 37 2.4.1 Existing Literature. . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.4.2 Force/Torque Computation for Frictionless Contacts . . . . 38 2.4.3 Force/Torque Computation for Frictional Contacts. . . . . . 39 2.5 Experimental Validation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 2.5.1 Results of Accuracy Analysis. . . . . . . . . . . . . . . . . . . . 43 2.5.2 Stability and Update Rate—Exp 1: Dental Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 2.5.3 Stability and Update Rate—Exp 2: Bunny Versus Bunny. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 2.5.4 Stability and Update Rate—Exp 3: Buddha Versus Dragon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 2.5.5 Stability and Update Rate—Exp 4: Bunny Navigating . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 2.5.6 Validation of Friction Simulation . . . . . . . . . . . . . . . . . 51 2.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3 6-DoF Haptic Simulation of Geometric Fine Features. . . . . . . . . . . 59 3.1 Classification and Challenges in Simulating Fine Features. . . . . . 59 3.2 Proposed Approach for Simulating Sharp Features. . . . . . . . . . . 62 3.3 Multi-resolution Sphere-Tree Model for Sharp Features . . . . . . . 64 3.3.1 Perception-based Modeling Method. . . . . . . . . . . . . . . . 64 3.3.2 Hybrid Sphere-Tree Construction . . . . . . . . . . . . . . . . . 65 3.3.3 Sphere List Construction . . . . . . . . . . . . . . . . . . . . . . . 67 3.4 Collision Detection for Objects with Fine Features. . . . . . . . . . . 68 3.4.1 Hybrid Sphere-Tree-Based Collision Detection . . . . . . . . 69 3.4.2 Sphere-Tree-Based Continuous Collision Detection . . . . . 69 3.5 Fast Collision Response with PQP. . . . . . . . . . . . . . . . . . . . . . 71 3.6 Performance Analysis on Simulating Sharp Features. . . . . . . . . . 73 3.6.1 Perception Experiments: Comparative Study. . . . . . . . . . 73 3.6.2 Perception Experiments: Shape Matching. . . . . . . . . . . . 76 3.6.3 Experiments for Objective Evaluation . . . . . . . . . . . . . . 79 3.6.4 Performance of the PQP-based Accelerating Method . . . . 84 3.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 4 6-DoF Haptic Simulation of Deformable Objects . . . . . . . . . . . . . . 89 4.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 4.2 Overview of the Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 4.3 Modeling Using Sphere-Trees with Springs. . . . . . . . . . . . . . . . 93 Contents xi 4.4 Contact Constraint Prediction Method. . . . . . . . . . . . . . . . . . . . 94 4.5 Skeleton-Based Deformation Computation . . . . . . . . . . . . . . . . 95 4.5.1 Computation of the Internal Force. . . . . . . . . . . . . . . . . 96 4.5.2 Computation of the External Force . . . . . . . . . . . . . . . . 96 4.5.3 Computation of Deformation . . . . . . . . . . . . . . . . . . . . 98 4.5.4 Stability Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 4.6 Local Deformation and Hybrid Contacts. . . . . . . . . . . . . . . . . . 100 4.6.1 Local Deformation of Gingiva . . . . . . . . . . . . . . . . . . . 101 4.6.2 Simulation of Hybrid Contacts . . . . . . . . . . . . . . . . . . . 103 4.7 Update of Sphere-Tree Model After Deformation. . . . . . . . . . . . 105 4.8 Performance Analysis and Experimental Results . . . . . . . . . . . . 106 4.8.1 Performance of Global Deformation. . . . . . . . . . . . . . . . 106 4.8.2 Simulating Multi-region Hybrid Contacts. . . . . . . . . . . . 109 4.8.3 Bimanual Operation with Deformation. . . . . . . . . . . . . . 110 4.8.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 4.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 5 Evaluation of Haptic Rendering Methods . . . . . . . . . . . . . . . . . . . 117 5.1 Related Literature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 5.2 Objective Evaluation Based on Measurement Data. . . . . . . . . . . 119 5.2.1 Framework. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 5.2.2 Metrics of Accuracy . . . . . . . . . . . . . . . . . . . . . . . . . . 120 5.2.3 Measurement System for Force and Motion Capture . . . . 121 5.2.4 Computational Model of the Haptic Tool’s Location . . . . 122 5.2.5 Two Example Rendering Methods. . . . . . . . . . . . . . . . . 124 5.2.6 Experimental Results. . . . . . . . . . . . . . . . . . . . . . . . . . 125 5.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 6 Application: A Dental Simulator. . . . . . . . . . . . . . . . . . . . . . . . . . 131 6.1 Background. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 6.2 Overview of iDental Simulation System . . . . . . . . . . . . . . . . . . 133 6.2.1 Function Requirements. . . . . . . . . . . . . . . . . . . . . . . . . 134 6.2.2 Components and Features of the Simulator. . . . . . . . . . . 135 6.3 Modeling Various Tissues and Pathological Changes . . . . . . . . . 138 6.4 Bimanual Periodontal Operation Tasks. . . . . . . . . . . . . . . . . . . 141 6.4.1 Periodontal Pocket Probing Examination . . . . . . . . . . . . 141 6.4.2 Calculus Detection and Removal. . . . . . . . . . . . . . . . . . 143 6.5 Hybrid Evaluation Approach. . . . . . . . . . . . . . . . . . . . . . . . . . 145 6.5.1 Subjective Evaluation Method. . . . . . . . . . . . . . . . . . . . 145 6.5.2 Objective Evaluation Method . . . . . . . . . . . . . . . . . . . . 146