博文

OpenGL: 3D坐标到屏幕坐标的转换逻辑(gluProject的实现)(2010-11-22 17:36:00)

摘要:遇到需要将3D坐标转换到屏幕坐标的问题,在网上很多朋友也在寻找答案,下面是glu中gluProject函数的实现。(实际上就是mesa的OpenGL实现版本)   // 矩阵按行优先存储 首先说一下opengl中的矩阵表示, 一般在c/c++中定义的矩阵和opengl中的矩阵分别是:
/*****************************************************************************
We define a 4x4 matrix array, OpenGL linear matrix format:
referenced as Row,Column as:

| 0,0   0,1   0,2   0,3 |             |a0 a4 a8 a12|

| 1,0   1,1   1,2   1,3 |             |a1 a5 a9 a13|

| 2,0   2,1   2,2   2,3 |             |a2 a6 a10 a14|

| 3,0   3,1   3,2   3,3 |             |a3 a7 a11 a15| */ 两者行和列正好相反,......

阅读全文(4696) | 评论:0

绕给定轴的旋转插值(2010-06-04 17:08:00)

摘要:有些时候希望从一个向量A绕一给定轴旋转到另一个向量B,并对其进行插值(比如动画)。如果给定轴恰好为AB平面的法向量,则以其为旋转轴可以直接构建四元数,取旋转角度步长为1°或者更小即可。最大旋转角为AB向量之间的夹角。当步长累积超过最大旋转角时,停止插值。但是当给定轴是其他时,最大旋转角为多大呢?     如图所示,P为给定轴,现在要对A绕P旋转到B进行插值。实际上这个问题可以看做是PA平面绕P旋转到PB平面的问题。设PA法向量为N1,PB法向量为N2。因此最大旋转角为N1和N2的夹角(两个平面的夹角)。       示例代码如下:   // vCur为当前旋转向量(in/out),dRotateStep为旋转步长,vAxis为给定轴,vOri为起始向量(A),vTar为终止向量(B)     BOOL InpByQuaternion(Vertex3d& vCur,double dRotateStep,Vertex3d& vAxis,Vertex3d& vOri,Vertex3d& vTar) {        Vertex3d vTempCur = vCur;        vTempCur.Normailize();          Vertex3d vTempNormalOri = vAxis ^ vOri;              // 计算N1        Vertex3d vTempNormalTar = vAxis ^ vTar;   // 计算N2      Vertex3d vTempNormalCur = vAxis ^ vTempCur; // 计算当......

阅读全文(3284) | 评论:2

绕不动点旋转(2010-05-21 18:26:00)

摘要:   玩过Google Earth操作的人都知道,其中键操作非常方便。以中键按下的点为不动点,鼠标操作的方向进行旋转,与仅仅绕场景中心旋转的方式要灵活许多。    
    本文主要介绍了简单的几何实现。  
  如图所示,E为视点,C为场景中心,P为中键按下点。此时如果鼠标沿屏幕X方向移动,表示,场景沿水平方向转动;若沿屏幕Y方向移动,场景在CEE’竖直平面内转动。   1、场景沿水平方向转动比较简单,E和C分别以旋转轴为Z轴,以P为旋转中心,转动的角度按照屏幕X方向移动的距离比例计算出来,通过四元数计算新视点和新的场景中心。   2、场景在CEE’竖直平面内的转动要复杂一点。首先我们要计算P在这个平面内的投影P’。此时E和C分别以P’为旋转中心,PP’为旋转轴,转动的角度按照屏幕Y方向移动的距离比例计算出来,通过四元数计算新视点和新的场景中心。        相关代码如下:   void CCamera::RotateScene(double alpha_add, double beta_add,Vertex3d NonMovePoint) {        // 绕不动点旋转        // 用四元数来实现modified by XWP          Vertex3d vZAxis(0,0,1);        Quaternion qq(-alpha_add*3.1415926,vZAxis);          // 先绕平面上的角度转动        Vertex3d curOrient = NonMovePoint - m_Eye; &n......

阅读全文(2583) | 评论:0

虚拟相机的绘制方法(二)(2010-05-14 17:23:00)

摘要:OpenGL坐标系 上面的代码还是不够的。因为需要对虚拟相机进行模型变换。在OpenGL中,模型变换有三种方式,即glTranslateX, glRotateX, glScaleX. 对于单个变换很容易理解,但是当多种变换组合的时候,初学者就很难分析清楚最后的结果了。   首先我们来讲解一种红宝书上介绍的一种经典情况。即先旋转还是先平移的问题。   glTranslatef(0,0,5);   glRotatef(45, 0,0,1);   显然这段代码如果换个顺序执行结果是不同的。因此红宝书中指出为了方便读者理解,提出了从全局坐标系和局部坐标系来理解这段代码。 如果是全局坐标系理解,那么从下往上执行,结果就应该是先绕z轴旋转45°,紧接着沿着z轴平移5个单位。 如果是局部坐标系理解,那么从上往下执行,结果就应该是先沿z轴平移5个单位,紧接着,建立模型的局部坐标系(第一次局部坐标系与场景的坐标系平行),再绕z轴旋转45°。 这样读者在理解层次上就统一了。   再举上面一例。 glScalef(dPerRatio,1.0,1.0);   glRotatef(45,0,0,1);   这段代码的目标是将一个正方形旋转45°后,x轴方向伸缩dPerRatio倍,变成长方形。     如果从全局坐标系理解是很容易的。但是有人认为,从局部坐标系好像不对劲。因为首先是X轴伸缩了dPerRatio倍。再次旋转45°。显然不是长方形了?              这个理解是有问题的。因为既然从局部坐标系理解,要知道,执行了glScalef之后,局部坐标轴其实也被伸缩了。这样再次旋转45°,结果还是长方形。由于glScalef从局部坐标系一般不容易理解,所以专家建议还是这种变换从全局坐标系理解。 旋转轴      了解了OpenGL中的模型变换之后,我们就要尝试将刚才创建的相机进行变换,即镜头需要从原点移到相机位置,并且使它的轴线与视线方向平行。设变换前轴向量为 AB,变换后轴向量为C......

阅读全文(2770) | 评论:0

虚拟相机的绘制方法(一)(2010-05-14 16:49:00)

摘要:

  一般,我们经常把看到的三维场景类比于相机拍照(OpenGL编程指南第四版),因此视点变换也称为相机变换。后来有些人总是误解“视点”的概念,因为视点既可以理解为“相机(眼睛)所在的位置”,也可以理解为“相机(眼睛)所看到的地方”。前者是指相机位置,而后者则是场景中心(参见gluLookAt函数)。为了方便起见,本文不采用“视点”的概念,而用相机位置来代替说明。     三维漫游的过程实际上就是相机运动的过程,包括相机位置和相机视线的运动改变。人眼所看到的三维动画就好比看到的DV录像。要知道,相机拍照是不会拍到自己的。(除非有镜子,排除这种情况)。但是有些时候,我们希望从全局看到相机本身的运动过程。因此,我们希望在场景中虚拟出这样一个对象来模拟相机的运动,称为“虚拟相机”(Virtual Camera).这样做有2个优点:一来可以帮助我们更好的宏观上了解和定制漫游路线和漫游效果,比如我们想指定,当相机经过A楼大门前,视线必须经过对面马路的红绿灯;另外,也可以检查漫游效果是否平滑,以及不平滑出现的位置和时间等。     虚拟相机的绘制包括两个部分:视锥体和相机体。(参见下图:3DSMax中的虚拟相机)。其中视锥体为由近裁切面和远裁切面为底面构成的棱锥台,其轴线为视线方向。为方便模拟,一般近裁切面直接表示为一个点,该点位于相机体镜头的中心。而远裁切面由于一般设置很大,我们只需要控制在一定距离内进行示意即可,例如100m,或者在路径漫游时,如果用户设定了相机路径和目标路径,那么可以直接把“远裁切面”中心设置在目标路径上。  
                                            图:3DSMax中的虚拟相机 &n......

阅读全文(4093) | 评论:1

四元数插值(2010-03-25 16:34:00)

摘要:先引用《计算机游戏程序设计》中的一段话作为开头:   “关键帧记录了当前姿势的运动变化,例如位置和朝向。……关键帧的插值指从两个已知的关键帧中平滑地产生所有中间帧序列的过程。关键帧动画是基于时间序列的插值。”   三维浏览软件中一个常见的功能就是漫游,可以理解为一种动画。对于漫游来说,假设只有一条相机路径,那么每一帧都需要计算相机位置和相机朝向。相机位置可以通过简单的线性插值来达到要求,但是有时候急拐弯处也会产生一些很大的运动变化,因此经过通过光滑路径的方法来去除一些拐角比较大的点。不过这不是今天讨论的主题。今天讨论的主要是后一种,即相机朝向的插值。   假设在起点处,用户指定此时相机C必须朝向A点,到了路径终点的时候,相机必须朝向B点。如下图所示的一条走下楼梯的路径。如何对这之间的朝向进行平滑和连续的插值成为漫游的关键。  
“对旋转量的插值,一般首先想到的是基于绕x,y,z轴的旋转的欧拉角。但实践证明,基于欧拉角的直接插值很容易导致不连续性,而且它相对于xyz轴的旋转次序不同,得到的旋转结果也不同。……四元数的旋转插值能比基于欧拉角的直接插值产生更为平滑和连续的旋转。”   这段话说明了四元数插值可以应用到我们这里。其实,四元数的球面线性插值,简写为slerp。其几何含义的解释为插值路径为四维的单位球上的较短的圆弧路径,这个圆弧是在由q,r和原点组成的平面和单位球相交的圆周上。q就是起点的朝向,r就是终点的朝向。   q r q r
  具体的计算方法和代码略,在一般的几何库中都会提供。需要注意的是slerp插值方法非常适合两个四元数之间的插值,但是如果有一系列的四元数,使用slerp对四元数进行两两插值会导致插值端点出的值产生变化。      在三维软件中的另外一个应用就是缩略图的使用。在漫游浏览时,当用户到达一个满意的位置和朝向时,想记录下来,那么一般可以直接使用缩略图功能,Google Earth的地标功能与此类型。如果下次想直接到达这个地点,可以直接从当前位置“飞”过去。这里同样可以用到四元数插值。因为......

阅读全文(5089) | 评论:0

关于四元数(2010-03-25 16:21:00)

摘要:
四元数与旋转矩阵和欧拉角相比,除了能够解决万向锁这样的问题和计算方便之外,我认为最大的优点就是符合人们的认知习惯。一轴一角度就和一点一方向一样,成为解决三维几何计算的核心工具。   四元数的历史跟一个人相关,那就是欧拉。他证明了一个旋转序列等价于单个旋转。因此3D中任意角位移都能表示为绕单一轴的旋转。并且四元数成功避免了万向锁问题。我们有些时候不必再去思考“先绕x轴转还是先绕y轴转”这样的问题,因为对于三维空间抽象能力欠缺的新手来说,这是很头疼的一件事情。   记得我刚使用四元数的时候,是为了简化计算。假设给了一个点P,然后需要计算这个点绕某个轴旋转60°以后得到的新点P’坐标。如果利用传统几何来解决,肯定是要计算一大堆sin,cos的问题。后来发现四元数可以很轻松的应付这个问题。再之后就是从Ogre引擎里面找到了这个类Quaternion,使用起来也很方便。   说来惭愧,刚入门的时候,对四元数理解不够深刻。例如,上面那个问题,我可以首先根据旋转轴和旋转角度计算出四元数。然后,我天真的以为,接下来直接将四元数与原来的点坐标进行“乘法”,就得到新的点坐标了。突然,我发现,由于我使用的旋转轴实际上是一个向量,而这个向量,实际上代表了一组平行向量,如此说来,空间中平行的旋转轴,对于同一个旋转角度,构建的四元数都是相同的?难道说,对于同一个点P,绕这么多空间中不同的旋转轴旋转同一个角度,得到的新点P’坐标都是相同的?   显然得到的坐标应该是不同的。我百思不得其解。到底是哪里出了问题?难道我使用四元数的方法有问题?多番求证,发现自己犯了一个很致命的错误。那就是理解上的误区。呵呵。四元数的旋转轴矢量和我们感性理解的固定旋转轴不是一个概念。具体我就不解释了,可以参见一下我以前写在笔记上的一段话:现在看起来虽然很傻,但也是一种思维上的变化,值得回味。       具体四元数在三维软件中的应用就有很多了。例如模型的交互式旋转等等。下一节着重讨论关于四元数插值的应用。......

阅读全文(5045) | 评论:7

空间中三角形到三角形的最短距离求法以及一些思考(2009-10-02 13:32:00)

摘要:   根据上一节线段到三角形的最短距离的证明,我想我们可以大致可以想象出两个三角形的最短距离如何求解了。   (1)三角形S1每条边到S2的3个最短距离。 (2)三角形S2每条边到S1的3个最短距离。     将这6个距离进行比较,最小的就是两个三角形的最短距离。      扩展一下。由于一般的简单几何体均可以拆成三角形构成,那么两个简单几何体的距离也是在理论上可以求得的。不过实际操作中,不能采用三角形遍历求距离的方法,效率太低下了。作者会在后续的章节中继续探讨两个几何体最短距离的求解方法。      下面谈点思路。纵观前2节“空间中线段到线段的最短距离”,“空间中线段到三角形的最短距离”,我们可以发现,我们的求解方案有一些相同的地方。假设求空间基本对象A和空间基本对象B的最短距离,那么我们会首先拆分A为其一级子对象集合,然后求出每个子对象到B的最短距离;同时,拆分B为其一级子对象集合,求出每个子对象到A的最短距离。最后将所有的距离进行比较得到最小值,就是最短距离。举个例子来说明一级子对象。例如多边形由线段构成,那么线段是多边形的一级子对象;线段由点构成,那么点是线段的一级子对象。所以,在求解“空间中线段到线段的最短距离”时,我们会涉及到求点到线段的最短距离;在求解“空间中线段到三角形的最短距离”,会求线段到三角形每条边的最短距离,会求三角形到线段上每个端点的最短距离。当然也要考虑一些特殊情况。由于所有基本对象最终的最底层子对象就是点,而两点之间的距离是可得的,那么任意基本对象的最短距离也都是可以计算的。            谈点技术。如果任意2个几何体的最短距离我们都可以求得,那么相交测试以及所谓的碰撞检测那就相当简单了。只要最短距离等于0,那么肯定相交;反之不相交。但是求距离有时候是很困难,很费时的一件事情,而相交检测则要简单一些。常见的分离轴检测,separating axies test就比求距离要简单一些。作者会在后续章节中继续介绍。但是某些情况下,利用求距离的思想来检测相交,是很方便的一件事情,尤其是涉及到球和胶囊体的时候。球是点在半径范围......

阅读全文(4260) | 评论:3

空间中线段到三角形的最短距离的几何求法与证明(2009-09-26 11:27:00)

摘要:      首先我们来看第一个问题:空间中线段PQ到三角形ABC的最短距离。在这里,想法可不要太简单。如果你从没接触过这种问题,可能你第一个想法就是分别求出P和Q到ABC所在平面的距离PP’和QQ’,然后进行比较,小者胜出。            这显然是不正确的。假设P和Q的投影点P’和Q’都不在三角形内,那么最短距离既不是PP’,也不是QQ’。这时,你可能突然记起以前学过一个东西:点到三角形的最短距离。让我们回忆一下求法:首先找到点X在三角形所在平面的投影X’。如果X’在三角形内,那么XX’就是最短距离。假设X’不在三角形内,就需要分别计算X’到三角形每条边的最短距离,也就是点到线段的最短距离,然后进行比较,小者胜出。几何证明很简单,略去。       那么好,于是我们分别计算P和Q到三角形ABC的距离,然后比较。这次总对了吧。仔细思考一下,发现也是错误的。一种很简单的情况就推翻了刚才的想法。让我们假设PQ和ABC平面严格平行,并且投影点都在三角形外。显然P到ABC的最短距离就是PP1,而PP1就是三角形PAC的高;Q到ABC的最短距离就是QQ1,QQ1就是三角形QCB的高。这样,即使我们比较出谁更小,也不能得到正确的最短距离。因为最短距离恰恰是我们上面第一种情况提到的,最简单的,PP’,当然,也就是QQ’,以及PQ上任意一点到平面的垂直距离,它们都是相等的,因为PQ与平面平行。            想到这里,可能就会比较疑惑了。看来这个距离还不是那么好求的。但是我们还是发现点规律。不管怎么说,这个距离是随着PQ的投影点与三角形的关系而变的。于是,有了新的思路,我们最好来研究一下投影点与三角形的关系。      实际上,只有三种情况。 (1)       P’和Q’都在三角形内。 (2)       P’和Q’中有一个点在三角形内。 (3)  ......

阅读全文(5405) | 评论:2

关于求异面线段间的最短距离(2009-09-21 10:11:00)

摘要:我们知道,异面直线的最短距离指的就是公垂线的长度,计算方法很多,还可以计算出最短距离点对。   但在有的应用中,需要求出异面线段的最短距离。区别在于,异面线段的最短距离不一定就是公垂线的距离。换句话说,异面线段的最短距离点对必须都落在每条线段里面,而不能在线段的延长线上。   那么假设,现在异面线段的最短距离点对没有落在每条线段里面,很显然,公垂线距离就不是最短距离了。该如何求解最短距离呢?实际上,只要我们求出线段的每个端点到另一条线段的最短距离,然后进行比较,最小者即胜出当选。   下面我们来从几何上证明这一点。 第一幅图中,PQ是线段AB和CD的公垂线。由于P,Q分别位于AB和CD线段内,因此PQ就是最短距离。由此我们也可以看出公垂线的一般做法。平移AB与CD相交得Q,从Q向P做垂线,得P。   再来看第二幅图。显然PQ不再是线段AB与CD的最短距离了,因为Q不在CD内。从几何上就可以看出,实际上AB上任一点U到CD上任一点V的距离UV都可以这样求得:设U在CD和A’B’构成的二维平面内的投影为U’,那么UU’,U’V和UV就构成了一个直角三角形。   ED的距离就是这样通过EE’和E’D求得的。由于EE’ (或者UU’)都是相等的,因此最短距离的问题转变为求最小U’V(E’D)的问题。即转化到二维平面上CD和A’B’的最短距离。这就比较简单了。如果CD和A’B’相交,那么最短距离为0,CD和AB的最短距离就是PQ;如果不相交,分别求出端点A’,B’到CD的最短距离和端点C,D到A’B’的最短距离,然后进行比较。当然实际求解中不用那么复杂,从图中可以看出,我们直接求解端点A,B到CD的最短距离和端点C,D到AB的最短距离即可。                因此结论就是: (1)       如果两条线段异面或相交,那么首先判断公垂线的最小距离点对是否分别在两条线段上。如果在,那么公垂线距离为最短距离,直接返回该值。 (2)       如果最小距离......

阅读全文(6018) | 评论:1