Virtual Environments are becoming more realistic and more functional with today’s constant technological advances.
These advances allow for virtualworlds to closely resemblereality. Therefore, new areas of usage andapplication of virtual environments are found every day.
The interiors of submarines, cargoships, powerplants, oilplatforms, airports and many other environments can today be replicated and used in various training applications, pre-construction simulations and many more.
Table of Contents
1 Introduction
2 Virtual Environments
2.1 Virtual Humanoids
2.2 Path Planning
2.3 Motion Synthesis
2.4 Summary
3 Path Planning
3.1 World Description
3.1.1 Wavefront Planner
3.1.2 Quadtree
3.1.3 Cell Decomposition
3.1.4 Visibility Graph
3.1.5 Global Roadmap
3.1.6 World Description Overview
3.2 Path Adjustment
3.2.1 Rubber Banding
3.2.2 Path Smoothing
3.3 Summary
4 Motion Synthesis
4.1 Motion Description
4.2 Organization of Motion Data
4.2.1 Motion Graphs
4.2.2 Motion Generation from Examples
4.2.3 Annotations
4.2.4 Data Organization Overview
4.3 Motion Modification
4.3.1 Motion Warping
4.3.2 Spacetime
4.3.3 Retargetting Motion
4.3.4 Motion Modification Overview
4.4 Motion Transition Detection
4.4.1 Similarity Metric
4.4.2 Window of Frames Approach
4.4.3 Transition Detection Overview
4.5 Summary
5 Framework
5.1 Framework Layers
5.2 Network Distribution
5.3 Path Planning module
5.3.1 Wavefront
5.3.2 Quadtree
5.3.3 Global Roadmap
5.4 Motion Synthesis Module
5.4.1 Motion data reader
5.4.2 Motion transition detection
5.4.3 Motion modification and blending
6 Results
6.1 Path Planning Module Analysis
6.1.1 Wavefront analysis
6.1.2 Quadtree analysis
6.1.3 Global Roadmap analysis
6.1.4 Comparative analysis
6.2 Motion Synthesis Module Analysis
7 Conclusion
A Tools
A.1 FXMotionViewer
A.2 FXSplineEditor
A.3 FXMotionMerge
A.4 FXNavigator
Research Objectives and Core Topics
The primary goal of this master thesis is to research and implement state-of-the-art algorithms for path planning and motion synthesis in virtual environments, with a specific focus on achieving real-time responsiveness and interactivity for virtual humanoid characters.
- Analysis and comparison of world decomposition algorithms for path planning.
- Implementation of motion synthesis techniques for realistic animation.
- Integration of developed modules into the ViSTA VR-toolkit and the VRZula character system.
- Development of tools for testing and evaluating path planning and motion synthesis algorithms.
- Evaluation of system performance and interactivity in dynamic virtual environments.
Excerpt from the Book
3.1.2 Quadtree
Since existence of too many cells creates a significant problem, obeying the following rule becomes quite sensible:
The Bigger Is Better Law of Spatial Decomposition for Path Planning (BIBLOSD): Use the largest convex regions you can as the basis for search-based path planning [Dav00].
The bigger the regions, the fewer there are. Thus, the number of regions becomes significantly smaller and so it is easier to search through them. Assuming that there is some predefined minimum obstacle size, there will be some minimal acceptable cell size, therefore simply making the uniform cells bigger doesn’t achieve all of the goals of Path Planning, namely fast planning and good paths.
There is a vast number of different convex decompositions that can be used. However, a Quadtree structure provides a good combination of fast pre-computation and recomputation and a great decrease in the number of cells from a uniform grid [Dav00]. There is also a nice bonus of a fairly straightforward implementation compared to many other convex decompositions. Figure 7 shows an illustration of a Quadtree Representation of a simple virtual world.
Summary of Chapters
1 Introduction: Provides an overview of virtual environments and the importance of believable, realistic virtual humanoids for user acceptance.
2 Virtual Environments: Discusses the fundamentals of virtual worlds and defines the challenges related to humanoid presence, path planning, and motion synthesis.
3 Path Planning: Explores various state-of-the-art algorithms for world decomposition and path finding, including Wavefront, Quadtree, and Global Roadmap.
4 Motion Synthesis: Examines techniques for motion description, organization, modification, and transition detection to create natural-looking human movements.
5 Framework: Details the design and implementation of the integrated framework, focusing on modularity and network distribution for real-time performance.
6 Results: Presents an experimental analysis and evaluation of the implemented path planning and motion synthesis algorithms in various environments.
7 Conclusion: Summarizes the contributions of the thesis and suggests areas for future research and improvements.
A Tools: Describes the development of support tools like FXMotionViewer, FXSplineEditor, FXMotionMerge, and FXNavigator used for testing and validation.
Keywords
Virtual Reality, Humanoid Animation, Path Planning, Motion Synthesis, World Decomposition, Quadtree, Global Roadmap, Motion Capture, Motion Graphs, Motion Warping, Spacetime Constraints, Real-time Interaction, ViSTA, VRZula, Path Smoothing.
Frequently Asked Questions
What is the primary focus of this thesis?
The thesis focuses on improving the realism and believability of virtual humanoids in virtual environments by addressing two core challenges: path planning and motion synthesis.
What are the main thematic areas covered?
The study covers spatial decomposition for navigation, path adjustment, motion capture data organization, motion modification using warping or spacetime constraints, and motion blending for seamless transitions.
What is the central research question?
The research asks how state-of-the-art algorithms for path planning and motion synthesis can be effectively implemented and integrated to achieve real-time responses and high interactivity for virtual characters.
Which scientific methods are employed?
The author analyzes various graph-based path planning algorithms and motion synthesis techniques, implements them within a modular framework, and evaluates their performance through quantitative testing and visual observation.
What does the main part of the work address?
The main part is divided into theoretical analysis and practical implementation of algorithms, including world representation (Wavefront, Quadtree, Global Roadmap) and motion modification (Warping, Spacetime).
Which keywords best describe this research?
Virtual Reality, Path Planning, Motion Synthesis, Humanoid Animation, and Real-time Interactivity are the central concepts of the work.
Why was the Global Roadmap algorithm considered superior for path planning?
Experimental results showed that the Global Roadmap provided a superior, unbiased distribution of graph nodes, maintained consistency regardless of environmental complexity, and avoided the scaling issues associated with grid-based or biased approaches.
What is the purpose of the tools created in the appendix?
The tools, such as FXMotionViewer and FXSplineEditor, were designed to facilitate the testing, visualization, and validation of motion data, spline blending, and path planning algorithms, ensuring the framework's reliability before full integration.
- Quote paper
- Predrag Stojadinović (Author), 2005, Interactive path planning and real-time motion synthesis for articulated humanoid characters in virtual environments, Munich, GRIN Verlag, https://www.grin.com/document/88981
