移动机器人自主导航仿真系统的研究与设计.doc

中南大学硕士学位论文 摘 要
I

摘 要

随着计算机科学技术以及多媒体应用技术的飞速发展，虚拟现实
技术和仿真技术越来越受到人们的广泛关注。它们广泛应用于工业、
国防、教育、医疗以及娱乐等方面。本文旨在应用虚拟现实技术来设
计一个仿真系统，仿真智能机器人在未知环境中的自主导航。
通过对移动机器人导航仿真系统所涉及的机器人学、计算机图形
学、3D数学建模以及Direct3D相关的技术与理论进行研究，本文将
问题主要分成四个部分：虚拟对象模型创建、设计对象模型的着色器、
碰撞检测和运动控制。本文研究内容和取得的成果如下：
1.对创建虚拟对象的数学模型的过程进行详细描述，其中包括机
器人模型的创建，虚拟地形模型生成以及虚拟环境的制作三个部分。
2.利用可编程的着色器语言——HLSL(High Lever Shader
Language)及其开发工具Fx Composer，编写了机器人模型、虚拟地
形和天空盒的着色器(Shader)，从而可以在编程过程中动态地调整对
象模型的渲染参数，使虚拟场景在视觉上更具有真实感。
3.研究了相关的碰撞检测算法，比较了基于包围球、包围方盒与
基于凸包的边缘包围盒三种封装模型的方法。利用基于凸包的边缘包
围盒来封装对象模型，使用HS-jump算法来进行碰撞检测。
4. 采用Visual Studio. NET并基于DirectX9 SDK建立了仿真系
统框架、绘制了对象模型以及虚拟机器人自主避障。该三维模拟系统
完全可以使用户从不同角度不同位置观看场景并与用户有着良好的
交互性。
此系统实现了机器人在不同场景中运动的视觉效果，可以生动地
呈现移动机器人在未知环境中的自主导航特征。

关键词 Direct3D,虚拟现实,碰撞检测,HLSL,着色器

中南大学硕士学位论文 ABSTRACT
II

ABSTRACT

With the rapid developments of computer science and multi-media
technique, virtual reality and simulation technique are more and more
being attached Importance to. They can be widely applied in industry,
national defense, medical care and entertainment etc. The paper presents
a simulation system based on virtual reality technique so as to simulate
the automatic navigation of an intelligent robot in unknown environment.
Through studying of robotics, computer graphics, 3D modulation and
corresponding knowledge on Direct3D technique and theories which
refers to simulation system of mobile robot, the project is divided into
four parts: construction of virtual objects, design of the shader of an
object, collision detection and movement control. The content and results
are:
A) It describes in detail the construction process of mathematics
model of virtual objects. It is composed of three parts: the
construction of robot model, virtual terrain model, and virtual
environment.
B) Using HLSL (high level shader language) and relating tools—Fx
Composer, we design the shader of robot model, virtual terrain,
and skybox. The effect parameters can be coordinated dynamically
during programming. Virtual scene is authenticating in vision.
C) It Studies collision detection algorithm, compares bounding sphere,
bounding box, and convex hull to bounding. It investigates how to
encapsulate object model by using convex hull,

and how to detect
collision according to HS-jump algorithm.
D) Using Visual Studio.NET and Direct3D SDK, we design a
framework of simulation system, which renders object model and
realizes obstacle avoidance of the virtual robot. The circumstances
can be viewed from different viewpoints. The simulation system is
interactive.
The simulation system realizes visual effects of robots in various

中南大学硕士学位论文 ABSTRACT
III
scenes. It demonstrates vividly automatic navigation of robots in
unknown environments.

KEY WORDS Direct3D,virtual reality, collision detection, HLSL,
Shader

中南大学硕士学位论文 目 录
i

目 录

第一章 绪 论................................................................................................1
1.1 课题的研究背景...................................................................................1
1.2 移动机器人以及虚拟环境的研究概况...................................................1
1.2.1 移动机器人的研究概况...............................................................1
1.2.2 虚拟3D环境的研究现状..........................................................2
1.3 DirectX技术.........................................................................................2
1.3.1 DirectX概述................................................................................2
1.3.2 DirectX 9.0C版本的新特性.........................................................4
1.4论文的主要内容与结构安排..................................................................5
第二章 Direct3D基本原理...............................................................................6
2.1 Direct3D中的几何描述........................................................................6
2.1.1 3D图元.......................................................................................6
2.1.2 Direct3D中的变形操作...............................................................8
2.2 Direct3D 的体系结构...........................................................................9
2.3绘制管道............................................................................................11
2.3.1虚拟相机...................................................................................11
2.3.2绘制管道框架............................................................................12
第三章 3D模型创建.......................................................................................14
3.1对机器人建模.....................................................................................14
3.1.1创建机器人骨骼........................................................................14
3.1.2对骨骼进行蒙皮........................................................................16
3.1.3对模型进行UV映射..................................................................19
3.1.4进行纹理贴图............................................................................19
3.1.5加入动画...................................................................................20
3.2创建3D地形......................................................................................20
3.2.1如何描述地形............................................................................21
3.3.2 加入纹理..................................................................................22
3.2.3加入光照效果............................................................................22
3.2.4利用CLOD进行处理................................................................23
3.3 使用天空盒........................................................................................25
第四章 使用可编程的着色器..........................................................................27
4.1顶点着色器与象素着色器...................................................................27
4.1.1顶点着色器虚拟机.....................................................................27
4.1.2象素着色器虚拟机.....................................................................28
4.2 HLSL的特性以及编辑工具FX Composer..........................................31
4.2.1 HLSL的优点.............................................................................31
4.2.2着色器编辑工具FX Composer..................................................31
4.3编写着色器.........................................................................................33
4.3.1光的类型与属性........................................................................33
4.3.2材质..........................................................................................36
4.3.3纹理..........................................................................................37

中南大学硕士学位论文 目 录
ii
4.3.4编写天空盒的着色器.................................................................40
4.3.5编写机器人的着色器.................................................................40
第五章 碰撞检测............................................................................................43
5.1碰撞检测概述.....................................................................................43
5.2碰撞检测算法.....................................................................................44
5.2.1边界球法...................................................................................44
5.2.2边界方盒法................................................................................45
5.2.2基于凸包的边界盒法.................................................................46
5.3 视点与地形碰撞检测..........................................................................48
第六章 系统实现............................................................................................49
6.1选择开发工具.....................................................................................49
6.2基于DirectX的Windows框架程序....................................................49
6.3载入网格体以及其对应的着色器.........................................................51
6.3.1 载入网格体...............................................................................51
6.3.2装载效果文件以及绘制模型图像...............................................52
6.4 实现运动控制....................................................................................52
第七章 结论与展望........................................................................................56
7.1结论....................................................................................................56
7.2展望....................................................................................................57
参考文献........................................................................................................58
致 谢............................................................................................................61
攻读研究生期间主要研究成果........................................................................62

中南大学硕士学位论文 第一章 绪 论
1
第一章 绪 论
1.1 课题的研究背景
本文“移动机器人自主导航仿真系统”来源于国家自然科学基金重点项目：
“未知环境下移动机器人导航控制的理论与方法研究”。未知环境中的移动机器
人导航控制理论和方法的研究目的是在机器学习、环境认知、在线规划、运动控
制等方面的理论和方法上有突破性进展，推动认知科学、模式识别、非线性控制
等学科的前沿问题研究，提供新的设计理论和技术[1][2]。
本文的研究目的在于为“未知环境下移动机器人导航控制的理论与方法研
究”提供一个模拟演示平台，由于此机器人在近一段时间内不能被发送至火星上
去，因此如果建立一个虚拟的火星场景和机器人模型，则可以模拟机器人在火星
的特殊环境下自主运动的情形。
1.2 移动机器人以及虚拟环境的研究概况
1.2.1 移动机器人的研究概况
移动机器人技术的发展经过了较长的历程[3]。从六十年代，美国俄亥俄州立
大学进行车辆自动驾驶控制技术的研究开始，英国和日本的一些研究机构也相继
进入这个研究领域，如英国的PATH(Program on Advanced Technology for the
Highway)研究实验室、日本MITI的机械工程实验室等。到了八十年代，移动机
器人技术发展迅速，众多的国家开始研制自主移动机器人，并且取得了很多有意
义的研究成果。九十年代至今，有更多的国家加入到智能移动机器人技术的研究，
主要研究热点是将各种智能控制方法应用到移动机器人的控制。
我国自“八五”期间开始进入这一研究领域，机器人技术与自动化工艺装备
等方面已取得了突破性进展，缩短了同发达国家的差距，但是在机器人的核心及
关键技术的原创性研究、高性能关键工艺装备的自主设计和制造能力、高可靠性
基础功能部件的批量生产应用等方面，同发达国家相比，我国仍存在较大的差距
[4]。

中南大学硕士学位论文 第一章 绪 论
2

1.2.2 虚拟3D环境的研究现状
随着现代计算机科学技术的飞速发展，虚拟3D技术越来越受到人们的广泛
关注。这项技术可将因时空限制人类无法直接看到的场景，或迄今为止尚不存在
的虚拟场景以3D的立体的方式呈现在观察者面前[5]。自90 年代以来,虚拟现实
的进步和发展对科学进步和社会发展产生了深远的影响。这些领域包括航空航天
技术、工业产品的创新设计、气象及自然灾害的精确预报、军事训练和仿真、常
规和战略武器的研制、药物设计和手术模拟等。
目前,国际上对该领域的研究工作非常活跃。美国是从事虚拟现实研究最早、
研究范围和水平最高、相关研究对国家发展贡献最大的国家,从事虚拟现实的大
学包括MIT、Stanford 大学、华盛顿大学、University of Illinois at Chicago、CMU
等几乎所有著名的大学,其研究内容侧重新概念发展(如虚拟现实的概念模型) 、
单项关键技术(如触觉反馈) 和系统实现,并参加了许多有关虚拟现实的国家项
目。其研究的许多成果已被国家研究机构用来解决国家的战略问题[6][7]。我国的
研究人员从90年代初开始这方面的研究和开发工作,主要单位有浙江大学、清华
大学、中科院软件所/自动化所/计算所、北京航空航天大学、国防科技大学、大
连海事大学等单位。
1.3 DirectX技术
1.3.1 DirectX概述
在 Windows 操作系统的体系构架中，在内核与硬件之间有一层抽象层，专
门对硬件进行屏蔽抽象，所以用户不再被允许对硬件进行直接访问。这样做以后，
大大地提高了操作系统的抗破坏性和抗干扰性，但这样以来，使硬件操作的效率
大打折扣，许多新硬件的新特性无法直接使用，这对多媒体和计算机图形技术的
发展显然是一种障碍。DirectX 是微软公司(Microsoft Corp.)提供的一套优秀的应
用程序编程接口(Application Programming Interfaces简称 APIs)，用于联系应用程
序和硬件自身，它对发展 Windows 平台下的多媒体应用程序、计算机图形应用
程序以及电脑游戏起到了关键的作用。在DirectX中的X是代表很多东西，实际
上DirectX就是一个由显示(Direct Graphics)、声音(DirectSound )和输入
(DirectInput)三大部分组成的一种应用程序接口，也可以将DirectX简单的看成是
一个提高系统性能的加速软件，它可以让以Windows为平台的游戏或多媒体程

中南大学硕士学位论文 第一章 绪 论
3
序获得更高的执行效率，加强3D图形和声音效果，最大限度地发挥最新PC硬
件多媒体应用的性能。其中DirectX的显示部分又分为Direct Draw和Direct
3D(Direct 3-Dimension)，前者主要负责2D加速，比如看DVD就是用的Direct
Draw，但人们一直都把目光放在了Direct3D身上，因为后者才是真正负责3D
加速的。
DirectX最早的版本1.0开发于1994年底到1995年9月，当时显卡芯片制造
商在软件支持方面没有一个强而且统一的标准。唯一统一的标准是BIOS INT10，
那个标准只支持640x480x16或320*240*256以下的显示模式。而当时的显卡芯
片则在不同程度上提供超越这个标准的能力。另一个标准是VESA的标准，这个
标准的问题是它只规定像素级别的操作，对块操作则没有什么支持。这种局面对
软件开发商，硬件开发商，以及用户都造成了不利的影响。软件开发商得根据不
同的显卡来编写不同的代码，硬件开发商则要为那些大牌应用程序开发驱动程
序，这些驱动程序的要求又各不相同。最终用户则不知所措，没有什么可以保证
你的显卡和应用程序能够一起工作。因此为了在硬件开发商，软件开发商以及最
终用户之间找到平衡点，微软制定了这一套标准。

表1-1 DirectX发展简史
DirectX版本 标志性技术 标志性硬件 标志性效果
1.0 --- --- ---
2.0 Direct2D成熟 Trident 9680，S3 2D动态效果
3.0 Direct3D 雏形 Riva128，i740 简单3D效果
5.0 基本3D技术 Riva TNT 雾化(Fog Effect)，
阿尔法混合(α-Blend)
6.0 成熟3D技术 TNT，TNT2 双线性过滤/Mipmap过滤
(Bilinear/Mipmap
Filtering )
7.0 T&L Geforce 256,Radeon 凹凸映射
8.0 象素着色器(Pixel
Shader) 和顶点着色
器(Vertex Shader)
Geforce 3 Ti，
Radeon8500
水波纹
8.1 象素着色器，顶点着色
器的升级
Geforce 4，
Radeon9500
大纹理水波纹
9.0 象素着色器3.0，顶点
着色器3.0
NV40，R420 皮毛效果

中南大学硕士学位论文 第一章 绪 论
4

经过十年的时间，DirectX从出现至今已将近十年，经过了9个版本的改进，
从它的发展简史[8](表1-1)可以看出DirectX从刚开始默默无闻的1.0到初露锋芒
的3.0再到奠定API霸主地位的7.0，以及现在统领大局的9.0，每一次API的升
级，都会给显示芯片带来新的标准和规范，而这往往就成了升级显卡的最大理由，
客观上带动了显卡的更新换代。DirectX9.0的出现也不例外，正如上文对它的技
术上革新的肯定，它的出现，直接催生了NVIDIA (NVIDIA Corp.)公司和ATI(ATI
Technologies Inc.)公司的王牌产品——NV40、R420的面世，在随后各大媒体对
它们的测试来看，接近电影般画质的效果的确令人叹为观止，这其中，DirectX 9.0
新技术的作用可谓是功不可没。
表1-1中Riva128、RivaTNT、TNT2、Geforce系列和NV40是NVIDIA公司
的产品，Radeon是ATI公司的产品。
1.3.2 DirectX 9.0C版本的新特性
微软公司于2004年10月发布了最新的DirectX版本9.0 C，并于2004年10
月发布了至今为止最新的软件开发包(Software Development Kit)——DirectX 9.0
SDK Update October 2004。DirectX9.0C除了在以上提出的可编程的顶点着色器
和象素着色器以外，在DirectX Graphics，DirectXSound中都有一些新的特点和
新增强的特性。
DirectX Graphics的新的特性有如下几点：
(1) 可以更加有效地绘制多实例几何体
在一个包含多对象的场景中，用户可以绘制一些不同方向、大小、颜色
的实例，这些实例出自同一个几何体。并且绘制出的效果以及其性能将
会更优。
(2) 效果系统(Effect System)增加了预着色(Preshaders)和“”参数快(Parameter
Blocks)
预着色是一项利用预计算常量着色来提升着色效率的技术，其功能的改
进使得的着色器只需更少的常量寄存器(Constant Registers)，可以提高5
％到20％的性能。
(3) HLSL(High-Lever Shader Language)可以支持到着色器模式3.0版本
HLSL是一种语法类C/C++的面向过程的语言，其针对顶点着色器和象
素着色器引擎进行开发。它支持vs_3.0和ps_3.0意味着用户针对硬件开
发引擎时不必使用固定函数通道(Fixed Function Pipeline)，且使得开发变
得更容易，代码更可读。

中南大学硕士学位论文 第一章 绪 论
5
(4) 应用程序框架(Sample Framework)的改进
应用程序框架是指用户开发Windows程序界面以及消息传递时所需的一
些APIs。它的改进使得应用程序界面更加美观，功能更加完全。
1.4论文的主要内容与结构安排
本学位论文的内容安排如下：
第一章主要介绍了论文的研究背景、意义，研究现状，本文所做的主要工作
以及论文的结构安排。
第二章从理论的角度介绍Direct3D的几何学原理，及其相关的数学其所需
要的数学理论支持。两种不同的角度来分析讨论了Direct3D 的体系结构，并介
绍了Direct3D的绘制管道。
第三章首先介绍如何创建机器人模型以及使用相关的工具对其进行纹理贴
图。其次讨论如何生成虚拟3D地形，着重讨论了CLOD中的Geomipmapping
算法，以及如何使用其对虚拟地形进行精简，从而使得地形在虚拟场景中更加具
有现实性以及提高绘制效率。最后介绍如何制作天空盒。
第四章主要介绍了HLSL的特性和相关技术及其相关的编辑器Fx
Composer，介绍了如何编辑顶点着色器和象素着色器。讨论了如何使用HLSL
来编辑天空盒的着色器，机器人模型的着色器。
第五章主要介绍机器人漫游过程中的重要的问题——碰撞检测，对机器人进
行碰撞检测可避免其在漫游过程中出现穿墙而过、车轮远离地面或陷入地面的情
况。首先简单介绍边缘球法和边缘方盒法，再根据系统的特殊要求，讨论基于凸
包来封装机器人模型以及使用HS-jump算法进行碰撞检测。
第六章讨论了如何实现该虚拟系统。接着介绍基于DirectX的虚拟习用的程
序框架，如何载入网格体及其相应的着色器，最后介绍如何在程序中控制模型的
运动。
第七章在全面概括本文所开展的工作的同时还对该系统中存在的一些不足
以及将来所需要开展的工作做了总结和展望。

中南大学硕士学位论文 第二章 Direct3D基本原理
6
第二章 Direct3D基本原理
前面已经简单的讨论了DirectX技术是由Direct Graphics，Direct Sounds，
Direct Inputs这三大部分组成的，由于本系统是建立一个虚拟的场景，并且主要
是在3D模型以及图形图像上做工作，因此也只运用Direct Graphics中Direct3D
的相关APIs和接口(Interfaces)，所以在本文中只具体介绍与系统紧密联系的
Direct3D相关内容。Direct3D是一种低