記錄 5 之 13
Record:   Prev Next
作者 Kallmann, Marcelo., author
書名 Geometric and discrete path planning for interactive virtual worlds / Marcelo Kallmann, Mubbasir Kapadia
出版項 San Rafael, California (1537 Fourth Street, San Rafael, CA 94901 USA) : Morgan & Claypool, 2016
國際標準書號 9781627057561 print
9781627057578 ebook
國際標準號碼 10.2200/S00687ED1V01Y201512VCP023 doi
說明 1 online resource(xix, 181 pages) : illustrations
text rdacontent
electronic isbdmedia
online resource rdacarrier
系列 Synthesis lectures on visual computing, 2469-4223 ; # 23
Synthesis digital library of engineering and computer science
Synthesis lectures on visual computing ; # 23. 2469-4223
附註 Part of: Synthesis digital library of engineering and computer science
Includes bibliographical references (pages 165-179)
Part II. Geometric algorithms and environment representations -- 3. Euclidean shortest paths -- 3.1 Euclidean shortest paths in simple polygons -- 3.2 Visibility graphs -- 3.3 The shortest path tree -- 3.4 Continuous Dijkstra and the shortest path map -- 3.5 Extensions and additional methods -- 4. Navigation meshes and geometric structures with clearance -- 4.1 Geometric structures supporting clearance -- 4.1.1 The Voronoi diagram -- 4.1.2 The medial axis -- 4.1.3 The constrained Delaunay triangulation -- 4.1.4 Local clearance triangulations -- 4.2 Designing navigation meshes -- 4.2.1 Extracting navigation meshes from 3D worlds -- 4.2.2 Selecting a cell decomposition scheme --
Part III. Advanced planning techniques -- 5. Extending basic search techniques -- 5.1 Background -- 5.1.1 Parallel search -- 5.1.2 Hierarchical search -- 5.1.3 Navigation with constraints -- 5.1.4 Potential fields -- 5.1.5 Continuous weighted-region navigation -- 5.1.6 Local collision avoidance -- 5.1.7 Real-time planning in dynamic problem domains -- 5.2 Extensions to classical A* -- 5.2.1 Weighted A* search -- 5.2.2 Anytime search -- 5.2.3 Dynamic search -- 5.3 Anytime dynamic search -- 5.3.1 Plan computation -- 5.3.2 Dynamic events -- 6. Constraint-aware navigation -- 6.1 Problem definition -- 6.2 Environment representation -- 6.2.1 Triangulation -- 6.2.2 Dense uniform graph -- 6.2.3 Hybrid graph -- 6.2.4 Adaptive highway graph -- 6.3 Constraints -- 6.3.1 Problem specification -- 6.3.2 Constraint definitions -- 6.3.3 Multiplier field -- 6.4 Planning algorithm -- 6.4.1 Cost computation -- 6.4.2 Accommodating dynamic constraints -- 6.5 Results -- 6.5.1 Evaluation of hybrid domain -- 6.5.2 Evaluation of adaptive highway domain -- 6.5.3 Constraint system examples -- 6.5.4 Parameter selection and performance -- 6.6 Summary -- 7. Anytime dynamic search on the GPU -- 7.1 GPU planning on uniform grids -- 7.1.1 Method overview -- 7.1.2 GPU-based wavefront algorithm -- 7.1.3 Efficient plan repair for dynamic environments and moving agents -- 7.1.4 Multi-agent planning -- 7.1.5 Results -- 7.2 GPU-based dynamic search on adaptive resolution grids -- 7.2.1 Method overview -- 7.2.2 Method initialization -- 7.2.3 Environment representation -- 7.2.4 Dynamic search on the GPU for adaptive resolution grids -- 7.2.5 Multi-agent and multi-goal planning -- 7.2.6 Results -- 7.3 Summary --
Part I. Introduction to discrete search -- 1. Basic approaches for world representation -- 1.1 Grids -- 1.2 Polygonal decompositions and navigation meshes -- 1.2.1 Triangulations -- 1.2.2 Euler's polyhedral formula -- 1.2.3 Navigation meshes -- 1.3 Roadmaps and waypoint graphs -- 1.3.1 Sampling-based roadmaps -- 1.3.2 Waypoint graphs -- 1.4 Comparison -- 1.5 Addressing 3D environments -- 2. Discrete search algorithms -- 2.1 Dijkstra algorithm -- 2.1.1 Algorithm -- 2.1.2 Step-by-step example -- 2.1.3 Grid example -- 2.1.4 Analysis -- 2.2 A* algorithm -- 2.2.1 Algorithm -- 2.2.2 Grid example -- 2.2.3 Analysis -- 2.3 Extensions and additional methods -- 2.3.1 Grid connectivity -- 2.3.2 Improving A* heuristics -- 2.4 Extensions and additional methods --
Part IV. Planning techniques for character animation -- 8. Dynamic planning of footstep trajectories for crowd simulation -- 8.1 Locomotion model -- 8.1.1 Inverted pendulum model -- 8.1.2 Footstep actions -- 8.2 Locomotion constraints -- 8.2.1 Footstep orientation -- 8.2.2 Space-time collision model -- 8.2.3 User parameters -- 8.3 Cost function -- 8.3.1 Fixed energy rate -- 8.3.2 Ground reaction forces -- 8.4 Planning algorithm -- 8.4.1 Generating discretized footstep actions -- 8.4.2 Short-horizon best-first search -- 8.5 Evaluation -- 8.5.1 Interfacing with motion synthesis -- 9. Planning using multiple domains of control -- 9.1 Overview -- 9.2 Planning domains -- 9.3 Multiple domains of control -- 9.3.1 Static navigation mesh domain -- 9.3.2 Dynamic navigation mesh domain -- 9.3.3 Grid domain -- 9.3.4 Space-time domain -- 9.4 Problem decomposition and multi-domain planning -- 9.4.1 Planning tasks and events -- 9.5 Relationship between domains -- 9.5.1 Domain mapping -- 9.5.2 Mapping successive waypoints to independent planning tasks -- 9.6 Results -- 9.6.1 Comparative evaluation of domains -- 9.6.2 Performance -- 9.6.3 Scenarios -- 10. Motion planning for character motion synthesis -- 10.1 Planning locomotion from motion capture data -- 10.2 Planning motions in high dimensions -- 10.3 Planning manipulation motions -- 10.4 Integrated planning of locomotion and object manipulation -- 11. Epilogue -- Bibliography -- Authors' biographies
Abstract freely available; full-text restricted to subscribers or individual document purchasers
Compendex
INSPEC
Google scholar
Google book search
Mode of access: World Wide Web
System requirements: Adobe Acrobat Reader
Path planning and navigation are indispensable components for controlling autonomous agents in interactive virtual worlds. Given the growing demands on the size and complexity of modern virtual worlds, a number of new techniques have been developed for achieving intelligent navigation for the next generation of interactive multi-agent simulations. This book reviews the evolution of several related techniques, starting from classical planning and computational geometry techniques and then gradually moving toward more advanced topics with focus on recent developments from the work of the authors. The covered topics range from discrete search and geometric representations to planning under different types of constraints and harnessing the power of graphics hardware in order to address Euclidean shortest paths and discrete search for multiple agents under limited time budgets. The use of planning algorithms beyond path planning is also discussed in the areas of crowd animation and whole-body motion planning for virtual characters
Also available in print
Title from PDF title page (viewed on February 19, 2016)
鏈接 Print version: 9781627057561
主題 Virtual reality
path planning
Euclidean shortest paths
shortest path maps
navigation meshes
discrete search
anytime and dynamic search
multi-agent planning
whole-body motion planning
GPU search techniques
Alt Author Kapadia, Mubbasir, 1985-, author
記錄 5 之 13
Record:   Prev Next