基础对象与算法.docx
《基础对象与算法.docx》由会员分享,可在线阅读,更多相关《基础对象与算法.docx(34页珍藏版)》请在冰点文库上搜索。
基础对象与算法
第二章基础对象与算法
本章讲述Intra3D最底层功能的设计与实现。
这些功能看起来很简单,但对于交互式3D软件开发工具而言都是必不可少的。
读者不禁要问:
“OpenGL那么优秀,为什么不提供Intra3D的功能呢?
”
真是因为OpenGL很优秀,所以才不提供Intra3D的功能。
有两个主要理由:
(1)OpenGL雄心勃勃地想成为国际通用的图形标准,它必须能在所有流行的平台上运行,即做到与窗口系统无关。
因此,OpenGL舍弃了诸如处理文字、数字图像这类常用的功能。
(2)OpenGL必须提供一套高性能的API,这些API全是“精明能干”的C函数。
就象设计CPU指令一样,OpenGL的API不是越多越好,而是要恰到好处。
否则OpenGL就会臃肿得象中国的行政机构,让人不堪负重。
OpenGL发展了十年,API只增加了几个,可见其系统设计之卓越。
2.1图形变换基础运算
本节是全书唯一出现数学公式的地方。
大多数程序员害怕数学公式,我也害怕。
所以咱们是同一条战线的,你就不用担心看不懂。
在图形学中,常用矩阵运算来实现图形变换。
采用4*4的齐次矩阵就可以用统一的矩阵相乘来表示平移、比例与旋转变换。
OpenGL提供了glMultMatrix、glRotate、glTranslate、glScale等函数来实现常规的图形变换。
但是矩阵难以表示图形变换的状态与过程,例如给出前后两个矩阵,就无法判断平移量、缩放量、旋转量各是多少。
可见仅使用矩阵运算并不满足交互式3D图形系统的需求。
Intra3D使用四元组(Quaternion)表示旋转变换的状态,再用两个矢量分别表示平移变换与比例变换的状态。
即总共用10个浮点变量就可以完全确定图形变换的状态与过程。
在交互式3D图形系统中,常需要用二维的输入设备模拟三维操作。
鼠标跟踪球算法就是用鼠标来实现三维旋转变换的一种方法。
本节将重点介绍四元组运算与鼠标跟踪球算法。
由于矢量运算与矩阵运算是大家熟知的,本节仅列出相应的函数。
2.1.1矢量运算
Intra3D2.0C++类库中矢量运算的程序见Intra3D-DLL\Include\Layer1\Algebra\Vector.h和Intra3D-DLL\Layer1\Algebra\Vector.cpp。
COM库的程序见Intra3D-COM\Layer1\Vector.h和Vector.cpp。
矢量的数据结构定义如下:
classVECTOR
{
public:
floatx,y,z;
VECTOR(floatx=0.0,floaty=0.0,floatz=1.0);
};
例如X、Y、Z方向的单位矢量A、B、C可以定义如下:
VECTORA(1,0,0),B(0,1,0),C(0,0,1);
矢量运算的函数如表2.1所示。
floatVectorMagnitude(VECTORA);
功能:
矢量求模
输入:
A
返回:
A的模|A|
voidVectorNormalize(VECTOR*A);
功能:
矢量归一化
输入:
A
输出:
如果|A|=0,输出矢量仍为A;否则输出矢量为A/(|A|)
VECTORoperator+(VECTORA,VECTORB);
功能:
矢量相加
输入:
A,B
返回:
A+B
VECTORoperator-(VECTORA,VECTORB);
功能:
矢量相减
输入:
A,B
返回:
A–B
VECTORoperator*(VECTORA,floats);
VECTORoperator*(floats,VECTORA);
功能:
矢量缩放
输入:
A,s
返回:
s*A
VECTORVectorCross(VECTORA,VECTORB);
VECTORoperator*(VECTORA,VECTORB);
功能:
矢量叉积
输入:
A,B
返回:
A与B的叉积
floatVectorDot(VECTORA,VECTORB);
floatoperator^(VECTORA,VECTORB);
功能:
矢量点积
输入:
A,B
返回:
A与B的点积
表2.1矢量运算函数
2.1.2矩阵运算
Intra3D2.0C++类库中矩阵运算程序见Intra3D-DLL\Include\Layer1\Algebra\Matrix.h和Intra3D-DLL\Layer1\Algebra\Matrix.cpp。
COM库的程序见Intra3D-COM\Layer1\Matrix.h和Matrix.cpp。
矩阵运算的函数如表2.2所示。
voidMatrixAdd(float*M,constfloat*A,constfloat*B,inti=4,intj=4);
功能:
矩阵相加
输入:
矩阵A(i,j)与B(i,j)
输出:
M=A+B
voidMatrixSub(float*M,constfloat*A,constfloat*B,inti=4,intj=4);
功能:
矩阵相减
输入:
矩阵A(i,j)与B(i,j)
输出:
M=A-B
voidMatrixMultiply(float*M,constfloat*M1,constfloat*M2,inti1,intj1,inti2,intj2);
功能:
矩阵相乘
输入:
矩阵M1(i1,j1)与M2(i2,j2)
输出:
M(i1,j2)=M1*M2
约束:
i2=j1,否则不计算M
voidMatrixTranspose(float*M,constfloat*A,inti=4,intj=4);
功能:
矩阵转置
输入:
矩阵A(i,j)
输出:
M(j,i)=A的转置
BOOLMatrixInverse(float*A,intn=4);
功能:
矩阵求逆
输入:
A(n,n)
输出:
A=A的逆
返回:
TRUE表示求逆运算成功;FALSE表示该逆矩阵不存在,此时A保持不变。
voidMatrixIdentity(float*A,intn=4);
功能:
矩阵归一化
输入:
A(n,n)
输出:
A=A的归一化矩阵
VECTORVectorTransform(VECTORV,floatM[16]);
功能:
矢量的矩阵旋转变换
输入:
初始矢量V,变换矩阵M[16]
返回:
V经过M变换后为V',函数返回V'
表2.2矩阵运算函数
2.1.3四元组运算与旋转变换
一、复数概念
记Z为一复数,Z′为Z的共轭复数,|Z|为Z的模,则有:
Z=a+bi
Z′=a–bi
其中i*i=-1。
两个复数Z1,Z2相乘可表示为:
Z1=a1+b1i
Z2=a2+b2i
Z1*Z2=(a1*a2-b1*b2)+(a1*b2+b1*a2)i
二、四元组概念
四元组是复数的一种扩展。
记q为一四元组,q′为q的共轭四元组,|q|为四元组的模,
为q的逆(即为1/q),则有:
q=w+xi+yj+zk
q′=w-xi-yj-zk
|q|=1→
=q′
(q1*q2)*q3=q1*(q2*q3)
q1*q2≠q2*q1
其中
i*i=-1
j*j=-1
k*k=-1
i*j=-j*i=k
j*k=-k*j=i
k*i=-i*k=j
四元组还可以表示为如下形式:
q=w+xi+yj+zk=[xyzw]=(s,v)
s=w
v=[xyz]
两个四元组q1和q2相乘可表示为:
q1=(s1,v1)
q2=(s2,v2)
q1*q2=(s1*s2-v1·v2,s1*v2+s2*v1+v1×v2)
三、用四元组表示旋转变换
设一旋转变换的旋转轴为u(单位矢量),旋转角度为θ。
则与此旋转变换等价的四元组q为:
q=(s,v)
s=cos(θ/2)
v=usin(θ/2)
如果将空间一点p表示成四元组的形式P=(0,p),则P点经过q旋转得到点Protated:
Protated=q*P*
设有两个四元组q1,q2分别表示前后两个旋转变换,则有:
Protated=q2*(q1*P*
)*
=(q2*q1)*P*(
*
)
=(q2*q1)*P*
可见,两个四元组q1,q2的旋转结果就相当于一个四元组(q2*q1)表示的旋转变换。
这与用矩阵相乘来表示旋转变换非常相似,事实上四元组q(w,x,y,z)等价于如下旋转矩阵:
w*w+x*x-y*y-z*z2*x*y+2*w*z2*x*z–2*w*y0
2*x*y–2*w*zw*w–x*x+y*y-z*z2*y*z+2*w*x0
z*x*z+2*w*y2*y*z–2*w*xw*w–x*x–y*y+z*z0
000w*w+x*x+y*y+z*z
有关四元组更深入的论述可参考文献[Hearn1997][Downs1998]。
四、程序设计
C++类库中四元组运算程序见Intra3D-DLL\Include\Layer1\Algebra\Rotation.h和Intra3D-DLL\Layer1\Algebra\Rotation.cpp。
COM库中四元组运算程序见Intra3D-COM\Layer1\Rotation.h和Rotation.cpp。
四元组的数据结构定义如下:
classQUATERNION
{
public:
floatx,y,z,w;
QUATERNION(floatx=0.0,floaty=0.0,floatz=1.0f,floatw=0.0);
};
四元组运算的函数如表2.3所示。
floatQuaternionMagnitude(QUATERNIONA);
功能:
四元组求模
输入:
四元组A
返回:
|A|
voidQuaternionInverse(QUATERNION*A);
功能:
四元组求逆
输入:
四元组A
输出:
如果|A|=0,不改变A;否则输出为A的逆
voidQuaternionConjugate(QUATERNION*A);
功能:
四元组求共扼
输入:
四元组A
输出:
A的共扼
QUATERNIONoperator*(QUATERNIONA,QUATERNIONB);
功能:
四元组相乘
输入:
四元组A与B
返回:
A*B
voidQuaternionToMatrix(floatM[16],QUATERNIONQ);
功能:
求四元组等价的旋转矩阵
输入:
四元组Q
输出:
M为与四元组Q等价的旋转矩阵
表2.3四元组运算函数
四元组运算的程序如下:
constfloatDELTA_ROT=1.0E-10;//允许存在的误差
floatQuaternionMagnitude(QUATERNIONA)
{
returnfloat(sqrt(A.x*A.x+A.y*A.y+A.z*A.z+A.w*A.w));
}
voidQuaternionNormalize(QUATERNION*A)
{
floatmagnitude=float(sqrt(A->x*A->x+A->y*A->y+A->z*A->z+A->w*A->w));
if(magnitude>=DELTA_ROT)
{
A->x=A->x/magnitude;
A->y=A->y/magnitude;
A->z=A->z/magnitude;
A->w=A->w/magnitude;
}
}
voidQuaternionInverse(QUATERNION*A)
{
floatmagnitude2=A->x*A->x+A->y*A->y+A->z*A->z+A->w*A->w;
if(magnitude2>=DELTA_ROT)
{
A->x=-A->x/magnitude2;
A->y=-A->y/magnitude2;
A->z=-A->z/magnitude2;
A->w=A->w/magnitude2;
}
}
voidQuaternionConjugate(QUATERNION*A)
{
A->x=-A->x;
A->y=-A->y;
A->z=-A->z;
}
QUATERNIONoperator*(QUATERNIONq1,QUATERNIONq2)
{
QUATERNIONQ;
Q.x=q1.w*q2.x+q1.x*q2.w+q1.y*q2.z-q1.z*q2.y;
Q.y=q1.w*q2.y+q1.y*q2.w+q1.z*q2.x-q1.x*q2.z;
Q.z=q1.w*q2.z+q1.z*q2.w+q1.x*q2.y-q1.y*q2.x;
Q.w=q1.w*q2.w-q1.x*q2.x-q1.y*q2.y-q1.z*q2.z;
returnQ;
}
voidQuaternionToMatrix(floatM[16],constQUATERNIONquat)
{
floatm[4][4];
floatwx,wy,wz,xx,yy,yz,xy,xz,zz,x2,y2,z2;
//calculatecoefficients
x2=quat.x*2.0f;
y2=quat.y*2.0f;
z2=quat.z*2.0f;
xx=quat.x*x2;xy=quat.x*y2;xz=quat.x*z2;
yy=quat.y*y2;yz=quat.y*z2;zz=quat.z*z2;
wx=quat.w*x2;wy=quat.w*y2;wz=quat.w*z2;
m[0][0]=1.0f-(yy+zz);
m[0][1]=xy+wz;
m[0][2]=xz-wy;
m[0][3]=0.0f;
m[1][0]=xy-wz;
m[1][1]=1.0f-(xx+zz);
m[1][2]=yz+wx;
m[1][3]=0.0f;
m[2][0]=xz+wy;
m[2][1]=yz-wx;
m[2][2]=1.0f-(xx+yy);
m[2][3]=0.0f;
m[3][0]=0;
m[3][1]=0;
m[3][2]=0;
m[3][3]=1;
for(inti=0;i<4;i++)
for(intj=0;j<4;j++)
M[i*4+j]=m[i][j];
}
由于四元组的(x,y,z,w)变量并不直观,Intra3D提供更加简明的旋转结构ROTATION来表示旋转变换。
ROTATION的数据结构定义如下:
classROTATION
{
public:
VECTORaxis;//旋转轴,为单位矢量
floatangle;//旋转角度,0-360度
ROTATION(floatx=0.0,floaty=0.0,floatz=1.0,floatangle=0.0);
ROTATION(VECTORaxis,floatangle);
};
ROTATION运算是通过四元组运算来实现的,函数如表2.4所示。
ROTATIONoperator*(ROTATIONR1,ROTATIONR2);
功能:
ROTATION相乘,先执行R1旋转,后执行R2旋转。
输入:
R1,R2
返回:
R1与R2的旋转合成
VoidRotationToMatrix(floatM[16],ROTATIONR);
功能:
求与ROTATION结构等价的旋转矩阵
输入:
R
输出:
M为与R等价的旋转矩阵
VECTORVectorTransform(VECTORV,ROTATIONR);
功能:
矢量的旋转变换
输入:
初始矢量V,旋转结构R
返回:
V经过R变换后为V',函数返回V'
表2.4ROTATION运算函数
ROTATION运算的程序如下:
//将ROTATION结构表示成QUATERNION
QUATERNIONRotationToQuaternion(constROTATIONR)
{
QUATERNIONQ;
floattheta=R.angle/180.0f*3.14159f;
floatcosValue=cos(theta/2.0f);
floatsinValue=sin(theta/2.0f);
Q.x=sinValue*R.axis.x;
Q.y=sinValue*R.axis.y;
Q.z=sinValue*R.axis.z;
Q.w=cosValue;
returnQ;
}
//将QUATERNION结构表示成ROTATION
ROTATIONQuaternionToRotation(constQUATERNIONQ)
{
ROTATIONR;
floathalfTheta=acos(Q.w);
floatsinValue=sin(halfTheta);
if(sinValue<=DELTA_ROT)
{
R.angle=0.0f;
R.axis.x=0.0f;
R.axis.y=0.0f;
R.axis.z=1.0f;
returnR;
}
R.angle=halfTheta*2.0f*180.0f/3.14159f;
R.axis.x=Q.x/sinValue;
R.axis.y=Q.y/sinValue;
R.axis.z=Q.z/sinValue;
returnR;
}
ROTATIONoperator*(ROTATIONR1,ROTATIONR2)
{
//如果旋转角度近似为0
if((R1.angle>-DELTA_ROT)&&(R1.anglereturnR2;
elseif((R2.angle>-DELTA_ROT)&&(R2.anglereturnR1;
ROTATIONR;
QUATERNIONQ1=RotationToQuaternion(R1);
QUATERNIONQ2=RotationToQuaternion(R2);
QUATERNIONQ=Q2*Q1;//注意顺序
R=QuaternionToRotation(Q);
returnR;
}
voidRotationToMatrix(floatM[16],constROTATIONR)
{
QuaternionToMatrix(M,RotationToQuaternion(R));
}
//将矢量(三维空间的一点)表示成四元组
QUATERNIONVectorToQuaternion(constVECTORV)
{
QUATERNIONQ;
Q.x=V.x;
Q.y=V.y;
Q.z=V.z;
Q.w=0.0f;
returnQ;
}
//V经过Q变换后为V',函数返回V'
VECTORVectorTransform(constVECTORV,constQUATERNIONQ)
{
QUATERNIONA,B,C;
A=VectorToQuaternion(V);
B=Q;
QuaternionInverse(&B);
C=Q*A*B;
VECTORV;
V.x=C.x;
V.y=C.y;
V.z=C.z;
returnV;
}
//V经过R变换后为V',函数返回V'
VECTORVectorTransform(constVECTORV,constROTATIONR)
{
if((R.angle>-DELTA_ROT)&&(R.angleQUATERNIONQ;
Q=RotationToQuaternion(R);
returnVectorTransform(V,Q);
}
2.1.4鼠标跟踪球算法
用鼠标在窗口中转动一个形体,记窗口的宽度为w,高度为h,形体的转动中心坐标为(cx,cy),鼠标的起点坐标为P1(mx1,my1),终点坐标为P2(mx2,my2)。
跟踪球算法的目的就是要计算出旋转轴矢量u,与旋转角度θ。
将P1、P2投影到以(cx,cy)为中心的一个半球面上得到P1′与P2′,P1′与P2′在半球面上的矢量表示记为v1与v2。
可以近似地认为旋转轴矢量u即为v1与v2的叉积(CrossProduct):
u=v1×v2
旋转角度θ即为v1与v2的夹角,可用矢量点积(DotProduct)求出θ:
θ=180*acos(v1·v2)/π
问题的关键在于求出任一鼠标坐标(mx,my)在半球面上的投影矢量v,该算法的程序如下: