摘要: 无意间在网上看到了线段树,并且对此引发的讨论也是络绎不绝呀~所以自己也对这个感兴趣起来。目前对线段树的应用领域,我可以说是完全不理解的,不过相信这个特辑做完了过后,我就能有初步的理解了,特辑包含理论以及一些关于线段树的题。OK,废话不说,先复制个理论上来。其实理论看起来还是蛮好理解的,不过实践才是王道。 在一类问题中,我们需要经常处理可以映射在一个坐标轴上的一些固定线段,例如说映射在OX轴上的线...  阅读全文

posted @ 2010-10-25 16:28 小火球 阅读(355) | 评论 (0)编辑 收藏

这几天又开始研究新的排序算法,红黑树。工作需要,那就顺便学习了~

前言:

        之所以要写这篇文章,第一个目的是为了各位朋友在查看我写的源代码之前有一个可以理解理论的文章因为红黑树还是有点难的,如果不想搞懂理论,而直接看代码,那绝对是云里雾里,不知所云。
        第二个目的是我觉得网上虽然后不少我文章也在讲,但是我就是理解
不上有点困难,在我参考了很多文章之后,认真阅读才慢慢摸透了其中的原理,所以我想用自己的方式来表达,希望有助于各位的朋友理解。

红黑树由来:

        他是在1972年 由Rudolf Bayer发明的,他称之为“对称二叉B树”,它现代的名字是Leo J. GuibasRobert Sedgewick 1978年写的一篇论文中获得的。
               它是复杂的,但它的操作有着良好的最坏情况运行时间,并且在实践中是高效的:
它可以在O(log n)时间内做查找,插入和删除,这里的n 是树中元素的数目。

红黑树性质

1. 每个结点或红或黑。

2. 根结点为黑色。

3. 每个叶结点(实际上就是NULL指针)都是黑色的。

4. 如果一个结点是红色的,那么它的周边3个节点都是黑色的。

5. 对于每个结点,从该结点到其所有子孙叶结点的路径中所包含的黑色结点个数都一样。

 

讨论的前提:

1我们只讨论往树的左边和从树的左边删除的情况,与之对称的情况一样。

2假设我们要删除一个元素的方法都是采取删除后继节点,而非前驱节点。

3NL或全黑表示黑空节点,也可以不用画出。

4=>这个符号我们用来表示变成的意思。

 

一. 插入

当红黑树中没有节点的时候,新节点直接涂黑就可以了。

当树中已有节点,我们就将新节点涂红,并且底下挂两个黑空节点。

1.1 新节点的父亲为黑色

这种情况最简单,只接插入将新节点可以了,不会出现红色警戒。

1.2 新节点的父亲为红色

这种情况出现红色警戒,并且通过红色的父亲,我们可以推出一定有一个黑色的父, 并且父亲不可能为树根(树根必须为黑)

这种情况需要修复。

1.2.1 新节点的叔叔是红色。(红叔)

1.2.1-1

 


1.2.1-2

注解:在这种情况下,我们可以通过这样的方式来修复红黑树的性质。因为遇到红 色警戒所以我们首先可以想到的就是将父亲变成黑色,但这样祖父的左子树的黑高 就增加了,为了达到祖父的平衡,我们红叔变成黑色,这样祖父就平衡了。但是整 个祖父这颗树的高度增高了,所以再此将祖父的颜色变成红色来保持祖父这颗树的 高度不变。因为祖父变成了红色,因此往上遍历。

      方法:父=>黑;叔=>黑;祖=>红;往上遍历;

 

1.2.2 新节点的叔叔是黑色(黑叔)

1.2.2-1

1.2.2-2

注解:首先可以说明的是,这种情况下我们都可以通过改变颜色和旋转的方式到达 平衡,并且不再出现红色警戒,因为无需往上遍历。图1.2.2-1首先我们将红父变 成黑色,祖父变成红色,然后对祖父进行右旋转。这样我们可以看到,整颗树的黑 高不变,并且这颗树的左右子树也达到平衡。新的树根为黑色。因此无需往上遍历。

方法:图1.2.2-1  =>黑;祖=>红;祖父右旋转;

                1.2.2-2   新=>黑;祖=>红;父左旋转;祖右旋转;


 

插入我们就算做完了,与之对称的右边插入的情况完全一样,请自己下来分析;

 

 

一. 删除

删除是比较经典但也是最困难的一件事了,所以我们必须一步一步地理解。为了中途思想不混乱,请始终记住一点,下面我们删除的节点都已经表示的是实际要删除的后继节点了。因此可以得出一下结论。

 

    首先,可以肯定的是我们要删除的节点要么是红色要么是黑色。

    其次,既然我们要删除的结点是后继节点,那么要删除的节点的左子树一定为空。所以当删除的节点为黑色时只剩下两种情况。

    最后,如果删除的节点为红色,那么它必为叶子节点。(自己好好想象为什么)

 

请在看下面的内容前先牢记上面的结论,这样更加方便让你理解下面的知识。

 

a当删除的节点为黑色时

              删黑a               删黑#p#分页标题#e#b


b当删除的节点为红色时

     上面的几附图都是很简单的。因为你可以将空节点 去掉不看。所就形成了要 删除的节点要么有一个右孩子,要么为叶子节点。


 

下面我们就开始真正的删除操作了。

 

2.1 删除红色节点

 

注解:这种情况是最简单的,因为根据上面的结论我们可以推出子节点     一定为空, 也就是说删除的红色节点为叶子节点。只需将这个旧节点的右孩子付给父亲的左孩子就 可以了,高度不变。

方法:


2.2 删除黑色节点

         遇到黑色节点情况就将变得复杂起来,因此我们一定要慢慢来,仔细分析。

 

 

         2.2.1当删除的节点有一个红色子孩子

注解:这种情况其实就是上面我们分析的三种情况之一,如图"删黑b"。这种情况 是非常简单的,只需将旧节点的右孩子取代旧节点,并将子孩子的颜色变为黑色, 树平衡;

       方法:子取代旧;子=>黑;

 

2.2.2当删除的节点无左右孩子

这种情况其实就是上面我们分析的三种情况之一,如图"删黑a"。我们推出子节点 一定为空,请务必记住这点,不然在后面你将很容易被混淆,父亲的颜 色我们标记为绿色,是表示,父亲的颜色可为红或黑。黄色的子节点其实就 是一个黑空节点,这样方便后面分析。

 

 

a:红兄


注解:当我们删除的节点拥有一个红色的兄弟时,这种情况还相对比较简单,因为 兄弟为黑色,我们可以推出父亲一定为黑色。因为父节点的左树高度减一,所 以我们可以通过左旋转父节点,来将节点1旋转到左边来恢复左边的高度。然 后将父变成,兄变成黑。这样整颗树的高度不变,父节点也平衡记住子节点 为空所以可以删除看,这样便于理解。其实我们也可以推出12为空,但这里没有必要。

      方法:父=>红;兄=>黑;左旋转父节点;

b :黑兄

     遇到黑兄就又麻烦了,我们又必须引入要删除的节点的侄子了。所以我们这里 再次细分为b1: 黑兄 双黑侄 b2: 黑兄 左黑侄右红侄 b3: 黑兄 右黑侄左红侄。 可能你会问b4呢,双红侄的情况呢?其实双红侄的情况同属于b2,b3的情况,所以 可以默认用 b2,b3其中一种情况来处理就可以了。

 

现在我们开始了

     b1黑兄 双黑侄



 

 

 

注解:我们首先可以肯定的是父节点的左子树高度减一了,所以我们必须想方设法 来弥补这个缺陷如果我们把父节点的右子树高度也减一(兄变成红色)那么 父节点这颗树就可以保持平衡了,但整颗树的高度减一,所以我们可以判断, 如果父亲是红色,那么我们可以通过把父亲变成黑色来弥补这一缺陷。但如果 父亲是黑色呢,既然遇到到黑色了我们就只好往上遍历了。

方法:兄=>红;子=黑;    红父=>;

                                 往上遍历(黑父);

 

 

补充:其实子节点就是空节点,没有必要变。就算遍历上去,父节点也为黑

b2黑兄 左黑侄右红侄


注解:绿色表示,颜色不影响修复的方式。依然我们可以肯定父节点的左子树高度减一,所以我们可以通过将父节点旋转下来并且变为黑色来弥补,但由于兄弟被旋转上去了,又导致右子树高度减一,但我们这有一个红侄,所以可以通过红侄变成黑色来弥补。父亲所在位置的颜色不变;(子为空)
方法:兄=>父色;父=>黑;侄=>黑;(子=>黑);左旋转父节点;

b3 黑兄 左红侄右黑侄


注解:绿色表示,颜色不影响修复的方式。依然我们可以肯定父节点的左子树高度减一,同样我们通过父节点左旋转到左子树来弥补这一缺陷。但如果直接旋转的话,我们可以推出左右子树将不平衡(黑父),或者两个红色节点相遇(红父);这样将会更加的复杂,甚至不可行。因此,我们考虑首先将兄弟所在子树右旋转,然后再左旋转父子树。这样我们就可以得到旋转后的树。然后通过修改颜色来使其达到平衡,且高度不变。
方法:侄=>父色;父=>黑;右旋转兄;左旋转父;

 


总结:

如果我们通过上面的情况画出所有的分支图,我们可以得出如下结论

插入操作:解决的是 红-红 问题

删除操作:解决的是 黑-黑 问题

即你可以从分支图中看出,需要上遍历的情况为红红(插入)或者为黑黑黑(删除)的情况,,如果你认真分析并总结所有的情况后,并坚持下来,红黑树也就没有想象中的那么恐怖了,并且很美妙;


 

程序样列:

Þ 通过做某些颜色修改并对p[x]做一次左旋,可以去掉x的额外黑色来把它变成单独黑色,而不破坏红黑性质。将x置为根后,当while循环测试其循环条件时循环结束。
 
参考文献:
博客园
   http://www.cnblogs.com
   http://www.cnblogs.com/abatei/archive/2008/12/17/1356565.html
   http://www.cnblogs.com/abatei/archive/2008/11/17/1335031.html

posted @ 2010-10-08 11:12 小火球 阅读(727) | 评论 (0)编辑 收藏

    首先简要介绍一下AC自动机:Aho-Corasick automation,该算法在1975年产生于贝尔实验室,是著名的多模匹配算法之一。一个常见的例子就是给出n个单词,再给出一段包含m个字符的文章,让你找出有多少个单词在文章里出现过。要搞懂AC自动机,先得有模式树(字典树)TrieKMP模式匹配算法的基础知识。AC自动机算法分为3步:构造一棵Trie树,构造失败指针和模式匹配过程。
    如果你对KMP算法和了解的话,应该知道KMP算法中的next函数(shift函数或者fail函数)是干什么用的。KMP中我们用两个指针ij分别表示,A[i-j+ 1..i]B[1..j]完全相等。也就是说,i是不断增加的,随着i的增加j相应地变化,且j满足以A[i]结尾的长度为j的字符串正好匹配B串的前 j个字符,当A[i+1]B[j+1]KMP的策略是调整j的位置(减小j值)使得A[i-j+1..i]B[1..j]保持匹配且新的B[j+1]恰好与A[i+1]匹配,而next函数恰恰记录了这个j应该调整到的位置。同样AC自动机的失败指针具有同样的功能,也就是说当我们的模式串在Tire上进行匹配时,如果与当前节点的关键字不能继续匹配的时候,就应该去当前节点的失败指针所指向的节点继续进行匹配。
    看下面这个例子:给定5个单词:say she shr he her,然后给定一个字符串yasherhs问一共有多少单词在这个字符串中出现过。我们先规定一下AC自动机所需要的一些数据结构,方便接下去的编程。

 1 const int kind = 26
 2 struct node{  
 3     node *fail;       //失败指针
 4     node *next[kind]; //Tire每个节点的个子节点(最多个字母)
 5     int count;        //是否为该单词的最后一个节点
 6     node(){           //构造函数初始化
 7         fail=NULL; 
 8         count=0
 9         memset(next,NULL,sizeof(next)); 
10     } 
11 }*q[500001];          //队列,方便用于bfs构造失败指针
12 char keyword[51];     //输入的单词
13 char str[1000001];    //模式串
14 int head,tail;        //队列的头尾指针

 

有了这些数据结构之后,就可以开始编程了:
   
首先,将这5个单词构造成一棵Tire,如图-1所示。

 

 1 void insert(char *str,node *root){ 
 2     node *p=root; 
 3     int i=0,index;  
 4     while(str[i]){ 
 5         index=str[i]-'a'
 6         if(p->next[index]==NULL) p->next[index]=new node();  
 7         p=p->next[index];
 8         i++;
 9     } 
10     p->count++;     //在单词的最后一个节点count+1,代表一个单词
11 }

在构造完这棵Tire之后,接下去的工作就是构造下失败指针。构造失败指针的过程概括起来就一句话:设这个节点上的字母为C,沿着他父亲的失败指针走,直到走到一个节点,他的儿子中也有字母为C的节点。然后把当前节点的失败指针指向那个字母也为C的儿子。如果一直走到了root都没找到,那就把失败指针指向root。具体操作起来只需要:先把root加入队列(root的失败指针指向自己或者NULL),这以后我们每处理一个点,就把它的所有儿子加入队列,队列为空。

 1 void build_ac_automation(node *root){
 2     int i;
 3     root->fail=NULL; 
 4     q[head++]=root; 
 5     while(head!=tail){ 
 6         node *temp=q[tail++]; 
 7         node *p=NULL; 
 8         for(i=0;i<26;i++){ 
 9             if(temp->next[i]!=NULL){ 
10                 if(temp==root) temp->next[i]->fail=root;                 
11                 else
12                     p=temp->fail; 
13                     while(p!=NULL){  
14                         if(p->next[i]!=NULL){ 
15                             temp->next[i]->fail=p->next[i]; 
16                             break
17                         } 
18                         p=p->fail; 
19                     } 
20                     if(p==NULL) temp->next[i]->fail=root; 
21                 } 
22                 q[head++]=temp->next[i];  
23             } 
24         }   
25     } 
26 }

    从代码观察下构造失败指针的流程:对照图-2来看,首先rootfail指针指向NULL,然后root入队,进入循环。第1次循环的时候,我们需要处理2个节点:root->next[‘h’-‘a’](节点h) root->next[‘s’-‘a’](节点s)。把这2个节点的失败指针指向root,并且先后进入队列,失败指针的指向对应图-2中的(1)(2)两条虚线;第2次进入循环后,从队列中先弹出h,接下来p指向h节点的fail指针指向的节点,也就是root;进入第13行的循环后,p=p->fail也就是p=NULL,这时退出循环,并把节点efail指针指向root,对应图-2中的(3),然后节点e进入队列;第3次循环时,弹出的第一个节点a的操作与上一步操作的节点e相同,把afail指针指向root,对应图-2中的(4),并入队;第4次进入循环时,弹出节点h(图中左边那个),这时操作略有不同。在程序运行到14行时,由于p->next[i]!=NULL(rooth这个儿子节点,图中右边那个),这样便把左边那个h节点的失败指针指向右边那个root的儿子节点h,对应图-2中的(5),然后h入队。以此类推:在循环结束后,所有的失败指针就是图-2中的这种形式。

  最后,我们便可以在AC自动机上查找模式串中出现过哪些单词了。匹配过程分两种情况:(1)当前字符匹配,表示从当前节点沿着树边有一条路径可以到达目标字符,此时只需沿该路径走向下一个节点继续匹配即可,目标字符串指针移向下个字符继续匹配;(2)当前字符不匹配,则去当前节点失败指针所指向的字符继续匹配,匹配过程随着指针指向root结束。重复这2个过程中的任意一个,直到模式串走到结尾为止。
 1 int query(node *root){ 
 2     int i=0,cnt=0,index,len=strlen(str); 
 3     node *p=root;  
 4     while(str[i]){  
 5         index=str[i]-'a';  
 6         while(p->next[index]==NULL && p!=root) p=p->fail; 
 7         p=p->next[index]; 
 8         p=(p==NULL)?root:p; 
 9         node *temp=p; 
10         while(temp!=root && temp->count!=-1){ 
11             cnt+=temp->count; 
12             temp->count=-1
13             temp=temp->fail; 
14         } 
15         i++;                 
16     }    
17     return cnt; 
18 }
    对照图-2,看一下模式匹配这个详细的流程,其中模式串为yasherhs。对于i=0,1。Trie中没有对应的路径,故不做任何操作;i=2,3,4时,指针p走到左下节点e。因为节点e的count信息为1,所以cnt+1,并且讲节点e的count值设置为-1,表示改单词已经出现过了,防止重复计数,最后temp指向e节点的失败指针所指向的节点继续查找,以此类推,最后temp指向root,退出while循环,这个过程中count增加了2。表示找到了2个单词she和he。当i=5时,程序进入第5行,p指向其失败指针的节点,也就是右边那个e节点,随后在第6行指向r节点,r节点的count值为1,从而count+1,循环直到temp指向root为止。最后i=6,7时,找不到任何匹配,匹配过程结束。

posted @ 2010-10-08 10:52 小火球 阅读(440) | 评论 (0)编辑 收藏

Windows操作系统专门为此提供了6个API函数来对配置设置文件进行读、写:

GetPrivateProfileInt() 从私有初始化文件获取整型数值
GetPrivateProfileString() 从私有初始化文件获取字符串型值
GetProfileInt 从win.ini 获取整数值
GetProfileString 从win.ini 获取字符串值
WritePrivateProfileString 写字符串到私有初始化文件
WriteProfileString 写字符串到win.ini

我们可以把视图类的:OnInitialUpdate() 函数作为程序启动时读取配置文件的入口,配置文件的存储格式如下:

[SECTION 1]
XPos=300
YPos=200

[SECTION 2]
Text=Hello

仅有两个节,XPos和YPos标明了待显示信息的坐标,而待显示的信息存储在第二节的Text项中,用读取访问私有配置设置文件的API函数将其分别读入到变量m_nXPos,m_nYPos和m_strText中,并通过Invalidate()调用OnDraw()函数,在其内用TextOut函数将该信息在读取的坐标位置显示出来:

m_nXPos=GetPrivateProfileInt("SECTION 1", //节名
"XPos", //项名
0, //没找到此项时的缺省返回值
"C:\test\debug\test.ini"); //配置文件的准确路径

m_nYPos=GetPrivateProfileInt("SECTION 1","YPos",0,exeFullPath);
char buf[256];
len=GetPrivateProfileString("SECTION 2", //节名
"Text", //项名
"No Text", //没找到此项时的返回值
buf, //目标缓冲区地址
256, //目标缓冲区长度
"C:\test\debug\test.ini"); //配置文件的准确路径

for(int i=0;i<len;i++)
{
   CString str;
   str.Format("%c",buf[i]);
   m_strText+=str;
}
Invalidate();

一般配置文件是和应用程序存放在同一个目录中的如果用"C:\test\debug\test.ini"的绝对路径进行设置就会出现路径改变后找不到配置文件的问题,所以应动态搜寻配置文件的存放地址:

Tchar exeFullPath[MAX_PATH]; // MAX_PATH在API中有定义,为128
int len=GetModuleFileName(NULL,
exeFullPath, //应用程序的全路径存放地址
MAX_PATH);
CString path="\test.ini"; //配置文件名
::strcpy(exeFullPath+len-13,path); //组合出配置文件的全路径

值得注意的是这里的13是项目名的大小,但是不同项目可能名字不一样,定义这样的长度过于机械化

1    char *= NULL;
2    char exeFullPath[128];
3    int len=GetModuleFileName(NULL,
4        exeFullPath,                128);
5    p=strrchr(exeFullPath, '\\');   
6    *p='\0';
这样,通过strrchr函数屏蔽掉最后出现的'\'就能够把项目名也屏蔽掉了,根据不同的情况当然也有不同的做法。


写配置文件也基本类似,只是需要把数值类型的变量格式化成字符串再行存储:

str.Format("%d",m_nXPos);
WritePrivateProfileString("SECTION 1","XPos",str,exeFullPath);
str.Format("%d",m_nYPos);
WritePrivateProfileString("SECTION 1","YPos",str,exeFullPath);
WritePrivateProfileString("SECTION 2","Text",m_strText,exeFullPath);

我们一定遇到过这样的程序:在执行过一遍以后,重启系统会自动加载该程序,其实除了在启动菜单和注册表添加信息外,也可以用 WriteProfileString()函数向win.ini的"windows"节的"run"项目添加应用程序的全路径来实现,这要比其它两种方法简便的多,而且也比较安全。



二.将信息从INI文件中读入程序中的变量.

1.所用的WINAPI函数原型为:

DWORD GetPrivateProfileString(
LPCTSTR lpAppName,
LPCTSTR lpKeyName,
LPCTSTR lpDefault,
LPTSTR lpReturnedString,
DWORD nSize,
LPCTSTR lpFileName
);

其中各参数的意义:

前二个参数与 WritePrivateProfileString中的意义一样.

lpDefault : 如果INI文件中没有前两个参数指定的字段名或键名,则将此值赋给变量.

lpReturnedString : 接收INI文件中的值的CString对象,即目的缓存器.

nSize : 目的缓存器的大小.

lpFileName : 是完整的INI文件名.

2.具体使用方法:现要将上一步中写入的学生的信息读入程序中.

CString strStudName;
int nStudAge;
GetPrivateProfileString("StudentInfo","Name","默认姓名",strStudName.GetBuffer(MAX_PATH),MAX_PATH,"c:\stud\student.ini");

执行后 strStudName 的值为:"张三",若前两个参数有误,其值为:"默认姓名".

3.读入整型值要用另一个WINAPI函数:

UINT GetPrivateProfileInt(
LPCTSTR lpAppName,
LPCTSTR lpKeyName,
INT nDefault,
LPCTSTR lpFileName
);

这里的参数意义与上相同.使用方法如下:
nStudAge=GetPrivateProfileInt("StudentInfo","Age",10,"c:\stud\student.ini");




贴上自己WIN32测试并通过的一段例子(部分代码,主要功能是如何配置相对路径,后续操作,前面已经有了)
 1    char *= NULL;
 2    char exeFullPath[128];
 3    int len=GetModuleFileName(NULL,
 4        exeFullPath,                    //应用程序的全路径存放地址
 5        128);
 6    p=strrchr(exeFullPath, '\\');        //屏蔽掉项目名称
 7    *p='\0';
 8    p=strrchr(exeFullPath, '\\');        //屏蔽掉DEBUG(实际开发中这个可能不需要)
 9    *p='\0';
10    len = strlen(exeFullPath);
11    string path="\\system.ini";            //配置文件名
12    ::strcpy(exeFullPath+len,path.c_str()); //组合出配置文件的全路径
13
14
15    char ipstr[20];                        //存储IP地址
16    GetPrivateProfileString("Server","ServerIP",NULL,ipstr,20,exeFullPath);
17    int port;
18    port = GetPrivateProfileInt("Server","Port",0,exeFullPath);


下面这段是公司里工作时候写的,做个记录
 1    //////////////////////////////////////////将内容以','分离
 2    string strFream = szFream;
 3    vector<string> strVec;
 4    char cTrim = ',';
 5    std::string::size_type pos1, pos2;
 6    pos2 = 0;
 7    while (pos2 != std::string::npos)
 8    {
 9        pos1 = strFream.find_first_not_of(cTrim, pos2);
10        if (pos1 == std::string::npos)
11            break;
12        pos2 = strFream.find_first_of(cTrim, pos1 + 1);
13        if (pos2 == std::string::npos)
14        {
15            if (pos1 != strFream.size())
16                strVec.push_back(strFream.substr(pos1)); 
17            break;
18        }

19        strVec.push_back(strFream.substr(pos1, pos2 - pos1));
20    }

21    for(int i = 0; i < strVec.size();++i)
22    {
23        int nTemp = atoi(strVec[i].c_str());
24        if(nTemp < m_nFrameNum)
25            m_vecFrame.push_back(nTemp);
26        else continue;
27    }

posted @ 2010-07-23 10:48 小火球| 编辑 收藏

旋转:矩阵,四元数和欧拉角向量

3D引擎中最常见坐标变换是旋转。有几种方式可以实现旋转:矩阵,四元数和角度向量(角度或弧度)。最精确和限制最小的方式是将他们存储在矩阵中。矩阵是一个数学概念,它是一个以行和列形式组织的矩形数学块。当这些数字以正确的顺序与另一个矩阵或数字或引擎中最常见的点进行计算时,就可以改变对应的值。

例如,一个变换矩阵只是将一个点移动到三维空间,这很简单。其他更为复杂的矩阵,比如旋转矩阵可以通过将一个点的坐标设置为新位置使点旋转。当然这只在与一个平移矩阵组合时有用,因为旋转一个(0,0,0)的是不会平移的。如果我们在旋转后再平移,我们将向正确的方向移动。最后一个常见矩阵是缩放矩阵,它只是将缩放到一个特定的尺寸。

现在我们知道了矩阵的工作原理,但我们如何使用它们?好吧,如果你一直在看我写的游戏引擎教程,那么你已经在使用矩阵了。I3DComponent有一个旋转矩阵存储了旋转量,在绘制模型时会计算另外两个位置和缩放向量。这可能是存储位置和缩放的最简单的方法。Vector的三个分量能储存点的三个坐标信息(即点的位置),同理也适用于缩放,我们可以为每个坐标轴存储一个标量。但如何处理旋转?

那么,现在的问题是用一个向量的三个分量存储旋转是错误的做法。这里我不会讨论细节,你只需知道这通常是一个非常不好的主意。

不幸的是,虽然“最好”的方法是用矩阵表示旋转,但这对普通人来说比较抽象。没有人愿意在更新对象的旋转量时计算矩阵中的16个值。最简单的方法是用一个Vector3表示围绕每根坐标轴的旋转量,然后在转化为矩阵(我们将这种Vector3称为欧拉角矢量)。显然我们不想一直做这件事,但如果只用于手工地设置一个变量(如在一个游戏编辑器中)它还是工作良好的。有许多方法可以在矩阵和欧拉角之间转换,但它们并不完美。下面我将详细讲述最可靠的方式。这个想法来自与XNA官方网站的论坛上:http://forums.xna.com/forums/p/4574/23763.aspx

矩阵和欧拉角之间的相互转换

从欧拉角矢量转换很容易,困难的部分是转换回来。XNA提供了一个方法可以创建旋转矩阵,但它并没有提供转换回来的方法,因此我们将不得不自己实现。

首先,我们转换为旋转矩阵,Matrix.CreateFromYawPitchRoll()方法可以做到这一点。如果这里使用欧拉角,我们需要以以下顺序提供坐标:

  • Yaw(偏航):欧拉角向量的y轴
  • Pitch(俯仰):欧拉角向量的x轴
  • Roll(翻滚): 欧拉角向量的z轴

想象一下飞机,yaw指水平方向的机头指向,它绕y轴旋转。Pitch指与水平方向的夹角,绕x轴旋转。Roll指飞机的翻滚,绕z轴旋转。下面的代码演示了这一过程:

// Converts a rotation vector into a rotation matrix
Matrix Vector3ToMatrix(Vector3 Rotation)
{
return Matrix.CreateFromYawPitchRoll(Rotation.Y, Rotation.X, Rotation.Z);
}

这种方法可以提供一个表示旋转的矩阵。下面是最难的部分:将矩阵转换为欧拉角。

这个过程是将矩阵拆散:一个表示位置的Vecto3,另一个表示缩放,而四元数表示旋转。然后,我们必须将这个四元数转换为一个欧拉角矢量。我不打算详细讨论代码背后的数学原理,但如果你有兴趣,可以到前面链接中的网址上去看看。

下面是将旋转矩阵转换为欧拉角的代码。

// Returns Euler angles that point from one point to another
Vector3 AngleTo(Vector3 from, Vector3 location)
{
Vector3 angle = new Vector3();
Vector3 v3 = Vector3.Normalize(location - from);
angle.X = (float)Math.Asin(v3.Y);
angle.Y = (float)Math.Atan2((double)-v3.X, (double)-v3.Z);
return angle;
}
// Converts a Quaternion to Euler angles (X = Yaw, Y = Pitch, Z = Roll)
Vector3 QuaternionToEulerAngleVector3(Quaternion rotation)
{
Vector3 rotationaxes = new Vector3();
Vector3 forward = Vector3.Transform(Vector3.Forward, rotation);
Vector3 up = Vector3.Transform(Vector3.Up, rotation);
rotationaxes = AngleTo(new Vector3(), forward);
if (rotationaxes.X == MathHelper.PiOver2)
{
rotationaxes.Y = (float)Math.Atan2((double)up.X, (double)up.Z);
rotationaxes.Z = 0;
}
else if (rotationaxes.X == -MathHelper.PiOver2)
{
rotationaxes.Y = (float)Math.Atan2((double)-up.X, (double)-up.Z);
rotationaxes.Z = 0;
}
else
{
up = Vector3.Transform(up, Matrix.CreateRotationY(-rotationaxes.Y));
up = Vector3.Transform(up, Matrix.CreateRotationX(-rotationaxes.X));
rotationaxes.Z = (float)Math.Atan2((double)-up.Z, (double)up.Y);
}
return rotationaxes;
}
// Converts a Rotation Matrix to a quaternion, then into a Vector3 containing
// Euler angles (X: Pitch, Y: Yaw, Z: Roll)
Vector3 MatrixToEulerAngleVector3(Matrix Rotation)
{
Vector3 translation, scale;
Quaternion rotation;
Rotation.Decompose(out scale, out rotation, out translation);
Vector3 eulerVec = QuaternionToEulerAngleVector3(rotation);
return eulerVec;
}

应当指出的是,所有的旋转信息都使用弧度。要获得角度(如果与你共事的人不习惯于弧度:比如他不是一个程序员或数学家)可以使用MathHelper.ToDegrees()方法,角度到弧度可使用MathHelper.ToRadians()方法。当处理旋转时请不要忘了转换:

Vector3 RadiansToDegrees(Vector3 Vector)
{
return new Vector3(
MathHelper.ToDegrees(Vector.X),
MathHelper.ToDegrees(Vector.Y),
MathHelper.ToDegrees(Vector.Z));
}
Vector3 DegreesToRadians(Vector3 Vector)
{
return new Vector3(
MathHelper.ToRadians(Vector.X),
MathHelper.ToRadians(Vector.Y),
MathHelper.ToRadians(Vector.Z));
}

您可以通过在对象中设置属性使用这些旋转矩阵的功能,可以使处理起来更简单:

public Vector3 EulerRotation
{
get { return RadiansToDegrees(MatrixToEulerAngleVector3(Rotation)); }
set { Rotation = Vector3ToMatrix(DegreesToRadians(value)); }
}

posted @ 2010-07-22 14:49 小火球 阅读(2580) | 评论 (0)编辑 收藏

仅列出标题
共4页: 1 2 3 4 

posts - 28, comments - 3, trackbacks - 0, articles - 0

Copyright © 小火球