性8sex亚洲区入口,国产精品免费在线,国产日韩在线看

Blog�U�d��新地址http://www.cnblogs.com/soroman

SoRoMan — Wed, 20 Sep 2006 06:55:00 GMT

http://www.cnblogs.com/soroman

SoRoMan 2006-09-20 14:55 发表评论

探讨�Q�物体绕��L��向量的旋�?四元数法VS.旋�{矩阵法的性能比较

SoRoMan — Tue, 19 Sep 2006 09:11:00 GMT

3D�I�间中的旋�{可用旋�{矩阵、欧拉角或四元数�{��Ş式来表示�Q�他们不�q�都是数学工��P��其中在绕��L��向量的旋转方面，旋�{矩阵和四元数两种工具用的较多�Q�欧拉角�׃��存在万向节死锁等问题�Q��用存在限制�?br />
�Q�本文假讑֝�标系为左手坐标系中，旋�{方向为顺旉��。）

所求问题：

�l�定��L��单位轴q(向量),求向量p(x,y,z)(或点p)饶q旋�{theta角度的变换后的新向量p'(或点p')�Q?/strong>

1.用四元数工具�Q?br />-------------------------------------------------------------------------
�l�论�Q�构造四元数变换p'= q*p*q-1�Q�（p,q是由向量p,q扩展成的四元敎ͼ�。那么，p'转换臛_��应的向量(或点)��是变换后的新向量p'(或点p')�?/p>
其中�Q�p',q,p,q-1均�ؓ四元数。q由向量q扩展,为q=(cos(theta/2),sin(theta/2)*q)�Q�p由向量p扩展,为p=(0,x,y,z),q-1为q的逆，因�ؓq为单位四元数�Q�所以q-1=q*=(cos(theta/2),-sin(theta/2)*q)�?br />-------------------------------------------------------------------------

�Q�这个结论的证明�q�程可以在网上找到。这里略厅R��）
下面看其旉��复杂度：

首先有个三角函数的计��时��_��q�个可以预先计算好，��p��旉��不计。考虑n个四元数�怹�需�q�行4*4*(n-1)=16*(n-1)�ơ乘法，15*(n-1)�ơ加法，因�ؓ加法化费旉��较少�Q�这里仅考虑乘法。这里涉及到三个四元数的乘法�Q�设一�ơ乘法的旉��为T,故花�?6*2=32T

2.旋�{矩阵工具�Q?/strong>
-------------------------------------------------------------------------
�l�论�Q�构造旋转矩阵变换Trot,则变换后的新向量p'(或点p')为p'= p*Trot

其中�Q�p'�Q�x',y',z',1�Q?p(x,y,z,1)为向量p'�Q�p�?D齐次坐标表示�Q�Trot =

|t*x*x + c,       t*x*y + s*z,      t*x*z - s*y,     0|
|t*x*y - s*z,    t*y*y + c,          t*y*z + s*x,    0|
|t*x*z + s*y,   t*y*z - s*x,       t*z*z + c,        0|
|0,                    0,                       0,                    1|

c=cos(theta), s=sin(theta),t=1-c.
-------------------------------------------------------------------------
�Q�这个结论的证明�q�程可以在网上找到。这里略厅R��）

下面看其旉��复杂度：

三角函数的计��时间不计。矩阉|��w�的元素乘法主要是计��t*x和s*x之类�Q�需�q�行12+3=15�ơ乘法。两个矩�늛�乘的需�q�行n*n*n�ơ乘�?�q�里n=4�Q�所以花�?*4*4=64�ơ乘法时�?但这里有个注意的地方��是旋�{矩阵的第4�l�无��考虑�Q�即可简化�ؓ3X3的矩��c��故��p��3*3*3=27�ơ乘法时��_��d��的时间�ؓ15+27=42�ơ乘法时间。cost=42T.

比较来看�Q�还是��用四元数的效率要高出一些，�q�在要变换的点的数目��大�Ӟ��体现的越明显。实际上�Q�有很多3D引擎��Z��利用四元数运��的高效率性，一般先��矩阵�{换成四元数后�q�行�q�算再�{回�ؓ矩阵后，再传�l�DirectX或OpenGL库函数�?br />
关于四元数和矩阵在向量（方向�Q�之间的�q�行插值的效率比较�Q�见下篇�Q?br />探讨�Q�物体绕��L��向量的旋�?四元数法VS.旋�{矩阵法的性能比较

SoRoMan 2006-09-19 17:11 发表评论

探讨:3D透视投媄变换详解-��D��视��^面和屏幕的宽高比问题

SoRoMan — Sat, 16 Sep 2006 16:34:00 GMT

感觉很多书上都没讲清楚透视投媄变换的推��D��E?自己推导了下,以前一直含�p�的关于方�Ş/非方形的视��^面和屏幕的宽高比的问题也有了�{�案.本文�l�织如下�Q?br />
1.相机�I�间到视�q�面的变�?br />2.视��^面到屏幕的变�?br />3.�l�合
4.一般情�?br />
1.相机�I�间到视�q�面的变�?/font>

                       * p (xc,0, zc)
                     / |
                    / |
                   /   |
           X    |/     |
           ^     *p' |(xp,0,zp)
           |   / |      |
           | / |     |
           | /   |     |
C(cam) |/    |     |
--------*----|----*------------->Z
           0    dx   zc
     (X-Z�q�面的投��q��?

a.透视投媄一般的视景体�ؓ��台�Q�相机空间的物体会投影到视��^面z=d�Q�这里考虑左手坐标�p�，矩阵使用行优先方式。如图所�C�，��q��g��角�Ş知识可知相机�I�间中的物体投媄到视�q�面上的坐标为：

xp = xc*(dx/zc)
yp = yc*(dy/zc)

其中,xc,yc,zc为相机空间坐�?xp,yp,zp��q�面坐标�Q�dx�Q�dy为x,y轴向的视距view distance�Q�视�q�面到camera的距��?
故相机空间投影到视��^面上的矩阵Tcp为：

|dx 0 0 0 |

|0 dy 0 0 |

|0 0   1 1 |

|0 0   0 0 |

(验证:Tcp右乘点p(xc,yc,zc,1)得点p'(xc*dx, yc*dy, zc, zc),转换�?D坐标�?xc*dx/zc, yc*dy/zc, 1),正确�?

********************************************************************
注：因�ؓ转换�q�程中点使用的是4D齐次坐标,所以最后需转换�?D坐标�?D齐次坐标(x,y,z,w)转换�?D坐标的方法�ؓ除以w分量�Q�即对应3D坐标�?x/w,y/w,z/w)�?br />********************************************************************

考虑dx/zc和dy/zc��，如果dx != dy,则投影后x,y的比例会发生变化�Q�原因：投媄前坐标比例�ؓxc/yc,投媄后�ؓxp/yp = xc*(dx/zc)/yc*(dy/zc) = xc*dx/yc*dy�Q�，从而投影后的图像的x,y比例会发生变形�?br />
---------------------------------------------
�l�论1�Q�所以，一般都会��od=dx=dy,即x,y向的视距相同。否则，囑փ��q��?br />---------------------------------------------

考虑视角�Q�view angle,或视野filed of view�Q�的问题�Q�视角的大小不会影响到物体投影后的坐标，只会影响可视的范围�?/p>
在视距一��L��情况下，x,y轴的视角可以不一栗��如果一��P��那么视��^面就是一个正方�Ş的。于是有�Q?/p>
tan(theta_x/2) = width_p/d
tan(theta_y/2) = height_p/d

其中�Q�theta_x�Q�theta_y为x,y轴向的视角，width_p�Q�height_p��q�面z=d的宽度（x��_��和高�?y�?�?br />----------------------------------------------------------------
�l�论2�Q�视�q�面的宽高比rp=width_p/height_p = tan(theta_x/2)/tan(theta_y/2)�?br />----------------------------------------------------------------

2.视��^面到屏幕的变�?/font>

下面��是视��^面到屏幕的变换了�Q�这是一�?D�?D的变换（视��^面的坐标需伸羃以填满整个屏�q�空�?卛_��视��^面中出现的所有的点要变换到屏�q�上去，同时x,y轴向的比例还要维持和变换前一��P��以免比例��q��Q�同时视�q�面的坐标原点和屏幕中心点（x0=(width_s)/2, y0=(height_s)/2�Q�对应）�Q�其实，��是一个坐标羃攑֊��q�移的过�E?

xs = xp*kx + x0
ys = -yp*ky + y0

矩阵Tps为：

|kx     0      0 0 |

|0      -ky    0 0 |

|0      0       1 0 |

|x0   y0      0 1 |

(验证:Tps右乘点p(xp,yp,zp,1)得点p'(xp*kx + x0, -yp*ky + y0, zp, 1),转换�?D坐标�?xp*kx + x0, -yp*ky + y0, zp)�Q�正��?

其中�Q�kx,ky(kx>0,ky>0)为x,y轴向的羃攑֛�子（kx=(width_s)/(width_p)�Q?ky = (height_s)/(height_p�Q�，和视距相同，kx,ky的值必��M��P��否则囑փ�的x,y比例又会发生变�Ş。这�?yp*ky是因��Z��般屏�q�的y轴是向下的，跟相机空间和视��^面坐标系中的y轴方向相反�?br />------------------------------------------------------------------------------------------------
�l�论3: 一般��ok=kx=ky�Q�即x,y向的�~�放因子相同。否则，囑փ��q��?br />于是有，width_s/width_p = height_s/height_p�Q�变化等式得�Q�rp = width_p/height_p = width_s/height_s = rs
所以，在x,y轴视距一��L��情况下，要想最后变换到屏幕上的囑փ�x,y比例不失真，必须rp=rs,卌��q�面的宽高比和屏�q�的宽高比一栗��?/strong>
-----------------------------------------------------------------------------------------------

********************************************************************
注：若屏�q�宽高�ؓW,H�Q�当W != H�Q�即屏幕不�ؓ方�Ş的时候，要确保投影到屏幕上的囑փ�x,y比例不失真，则x,y轴视�?或视野FOV)肯定不能相等�?
原因�Q?��q��?,3知，rp=width_p/height_p = tan(theta_x/2)/tan(theta_y/2)=width_s/height_s=rs=W/H�?故由W/H != 1 => theta_x != theta_Y.
********************************************************************

3.�l�合�Q?/font>

相机�I�间点p转换到屏�q�空间点p'�Q�变换公式�ؓ�Q?/p>
xs = xc*(dx/zc)*kx + x0 = xc*(d/zc)*k + x0
ys = -yc*(dy/zc)*ky + y0 = -yc*(d/zc)*k + y0

�l�合变换矩阵(相机�I�间到屏�q�空�?Tcs为：

Tcs = Tcp*Tps =

|d*k    0       0 0 |

|0      -d*k    0 0 |

|x0     y0      1 1 |

|0      0         0 0|

其中�Q�d��距，k为屏�q�宽高比或视�q�面宽高比，x0,y0为屏�q�中心，注：最后需转换�?D坐标�?/p>
(验证:Tcs右乘点p(xc,yc,zc,1)得点p'(xc*d*k + x0*zc, -yc*d*k + y0*zc, zc, zc),转换�?D坐标�?xc*(d/zc)*k + x0, -yc*(d/zc)*k + y0, 1)�Q�正��?

4.一般情形：
************************************
视距�?�Q�x轴视角�ؓ90度，屏幕宽高为W,H.
************************************

代入d=1�Q�theta_x = PI/2,x0= W/2,y0=H/2,则视�q�面宽高为width_p = 2�?br />要确保屏�q�上的图像x,y比例不失真，即rs=rp,�?br />height_p = 2/rp=2/rs=2H/W,
k=kx=ky=width_s/width_p = W/2.

于是,矩阵�?

Tcs1 =

|W/2    0       0 0 |

|0      -W/2    0 0 |

|W/2    H/2   1 1 |

|0      0         0 0 |

�?br />
   |W/2    0                  0 0 |

|0      -H/2*(W/H)    0 0 |

|W/2    H/2              1 1 |

|0      0                   0 0 |

(可以看到�Q�y轴的�~�放因子中乘上了宽高�?aspect ratio))
�q�个矩阵较常用�?br />
---------------------
有什么问�?�Ƣ迎探讨.

SoRoMan 2006-09-17 00:34 发表评论

思考：关于The Tower of Babylon

SoRoMan — Wed, 09 Aug 2006 09:32:00 GMT

今天看到一个网友在谈论一个关于The Tower of Babylon�? �?a href="/sicheng/archive/2006/08/09/11024.html">http://m.shnenglu.com/sicheng/archive/2006/08/09/11024.html�Q�感觉其实就是个按关键字面积插入排序的问题。于是用插入排序��法实现如下�?br />
��单测试了下，应该没问题�?br />We have 4 kinds of blocks, they are:
(1,1,1)
(1,2,3)
(2,3,4)
(2,3,2)
Building the tower of babylon...
The max height of tower is: 18.
Totally 7 blocks are used, they are:
(1) block (1,1,1), area = 1
(2) block (1,2,3), area = 2
(3) block (1,2,3), area = 3
(4) block (2,3,2), area = 4
(5) block (2,3,4), area = 6
(6) block (2,3,4), area = 8
(7) block (2,3,4), area = 12

------------------------------------
TowerOfBabylon.cpp:
------------------------------------
//
// File: [TowerOfBabylon.cpp]
// Description:[This program illustrates how to get the Tower Of Babylon. the Tower Of Babylon: Given N kinds of blocks,
// you need to buid the tower under the condition that every upper block's area should less than the lower one.]
// Author:[SoRoMan]
// Date:[2006-08-08]
// Version:[2.0]
// History: [1.0: initial draft.
// 2.0: add a new type TOWER
// 3.0: chnage the sequence data structure to list structure to avoid memory access violation.]
//

// INCLUDES //////////////////////////////////////////////////////////////////////////
#include "stdio.h"
#include "malloc.h"

// DEFINES //////////////////////////////////////////////////////////////////////////
#define N 4

// TYPES //////////////////////////////////////////////////////////////////////////
typedef struct BLOCK_TYP
{
int x,y,z;
int area;
int height;

BLOCK_TYP *pNext;
} BLOCK, *BLOCK_PTR;

typedef struct TOWER_TYP
{
int height;
int num_block;

BLOCK_PTR pTowerTop;
} TOWER, *TOWER_PTR;

// PROTOTYPES //////////////////////////////////////////////////////////////////////////
TOWER_PTR BuildTower(BLOCK_PTR pBlock, int n);

// FUNCTIONS //////////////////////////////////////////////////////////////////////////
int main(int argc, wchar_t* argv[])
{
BLOCK blocks[N] = {{1,1,1},{2,2,2},{3,3,3},{4,4,4}};

printf("We have %d kinds of blocks, they are:\n", N);
int i;
for(i = 0; i < N; i++)
{
printf("(%d,%d,%d)\n", blocks[i].x, blocks[i].y, blocks[i].z);
}
printf("Building the tower of babylon...\n");

TOWER_PTR pT = BuildTower(blocks, N);
printf("The max height of tower is: %d.\nTotally %d blocks are used, they are:\n", pT->height, pT->num_block );

BLOCK_PTR pBlock = pT->pTowerTop;
for(i = 0; i < pT->num_block; i++)
{
        printf("(%d) block (%d,%d,%d), area = %d, height = %d\n", i+1, pBlock->x, pBlock->y, pBlock->z, pBlock->area, pBlock->height);
  pBlock = pBlock->pNext;
}

getchar();

return 0;
}

////////////////////////////////////////////////////////////////////////////////
// Algorithm of building the Tower Of Babylon.
// Input Parameters: pBlock: pointer variable that identifies blocks sequence.
// n: int variable that identifies how many kinds of blocks.
// Output Parameters: None.
// Return: pointer variable that identifies the built tower.
////////////////////////////////////////////////////////////////////////////////
TOWER_PTR BuildTower(BLOCK_PTR pBlock, int n)
{
int index_block = 0;
TOWER_PTR pTower = new TOWER();
BLOCK_PTR pTop = new BLOCK();
pTower->pTowerTop = pTop;

// initialize tower
pTower->pTowerTop->x = pBlock->x;
pTower->pTowerTop->y = pBlock->y;
pTower->pTowerTop->z = pBlock->z;

pTower->pTowerTop->area = (pBlock->x)*(pBlock->y);
pTower->pTowerTop->height = pBlock->z;
pTower->height = pTower->pTowerTop->height;
pTower->num_block = 1;

for(int i = 1; i < 3*n; i++)
{
index_block = i/3;
if (i%3 == 0) // condition 1, area = x*y, height = z.
{
   (pBlock+index_block)->area = ((pBlock+index_block)->x)*((pBlock+index_block)->y);
   (pBlock+index_block)->height = (pBlock+index_block)->z;
}
else if (i%3 == 1) // condition 2, area = x*z, height = y.
{
   (pBlock+index_block)->area = ((pBlock+index_block)->x)*((pBlock+index_block)->z);
   (pBlock+index_block)->height = (pBlock+index_block)->y;
}
else // condition 3, area = y*z, height = z.
{
   (pBlock+index_block)->area = ((pBlock+index_block)->y)*((pBlock+index_block)->z);
   (pBlock+index_block)->height = (pBlock+index_block)->x;
}

bool bNeedToBeAdded = true;

BLOCK_PTR pB = pTower->pTowerTop;
BLOCK_PTR pPrev = pTower->pTowerTop;
while(pB != NULL)
{
   if ((pBlock+index_block)->area < (pB->area))
   {
// insert new block
BLOCK_PTR pNewBlock = new BLOCK();
    *pNewBlock = *(pBlock+index_block);

if(pB == pPrev)
{
  pNewBlock->pNext = pB;
  pTower->pTowerTop = pNewBlock;
}
else
{
  pNewBlock->pNext = pPrev->pNext;
  pPrev->pNext = pNewBlock;
}

    // increase number of blocks
    pTower->num_block++;
    // increase height of tower
    pTower->height += (pBlock+index_block)->height;

    bNeedToBeAdded = false;
    break;
   }
   else if ((pBlock+index_block)->area == (pB->area))
   {
    if (pB->height < ((pBlock+index_block)->height))
    {
     // increase height of tower
     pTower->height += (pBlock+index_block)->height - pB->height;
     // replace blocks
BLOCK_PTR pNewBlock = new BLOCK();
*pNewBlock = *(pBlock+index_block);

if (pB == pPrev)
{
  pNewBlock->pNext = pB->pNext;
  pTower->pTowerTop = pNewBlock;
}
else
{
   pNewBlock->pNext = pB->pNext;
   pPrev->pNext = pNewBlock;
}
    }

    bNeedToBeAdded = false;
    break;
   }

   pPrev = pB;
   pB = pB->pNext;
}

if(bNeedToBeAdded)
{
   // add new block at the end
   BLOCK_PTR pNewBlock = new BLOCK();
   *pNewBlock = *(pBlock+index_block);

   pPrev->pNext = pNewBlock;
   pNewBlock->pNext = NULL;

   // increase number of blocks
   pTower->num_block++;
   // increase height of tower
   pTower->height += (pBlock+index_block)->height;
}
}

return pTower;
}

SoRoMan 2006-08-09 17:32 发表评论

�W�记�Q�基�Q�向量叉�U�与左右坐标�pȝ��关系

SoRoMan — Tue, 08 Aug 2006 04:53:00 GMT

本文只是读者的一些关于左叛_��标系的探讨，有待�l�箋挖掘�?br />参考资料：Real-Time Rendering second edtion

一般左叛_��标系的定义是�q�样说的�Q?/strong>
在左手坐标系中，坐标轴的定义�W�合左手法则�Q�左手四个手指的旋�{方向从X轴到Y��_��大拇指的指向��是Z轴。但是没有给出数学上的定义。参考一些资�?关于左右坐标�pȝ��定义�Q�涉及到向量叉积与左叛_��标系的关�p�R�?br />
从基说�v�Q?/strong>
基是n�l�的�Ƨ式�I�间中的一�l�线性无关的向量V0,V1,...,Vn-1。关于线性无兛_��量组的定义可以去参考其他资料�?br />
��Z��坐标�pȝ��关系�Q?br />如果一个基的行列式为正�Q�那么它?y��u)��可以�Ş成一个右手坐标系。如果�ؓ负则形成左手坐标�p�R�?br />
向量叉积与三�l�左叛_��标系的关�p�：
那么向量叉积与左叛_��标系的关�p�L��什么关�p�d��Q�由��Z��坐标�pȝ��关系可以推知�Q�比如在三维�Ƨ式�I�间中，设有一个基�Q�向量组�Q?Vx,Vy,Vz)存在�Q�那么我们知道行列式的表辑ּ�|Vx,Vy,Vz|=(Vx*Vy).Vz,可以得知�Q�当向量Vz的方向与向量Vx*Vy(Vx与Vy的叉�U?的夹角在0-PI/2之间的时候，��׃��定会�?Vx*Vy).Vz>0�Q�那么由基（向量�l�）Vx,Vy,Vz�l�成的坐标系��׃ؓ��x��坐标�p�R��其实，说白了，��是向量叉积的方向规定了左右坐标�pȝ��定义�?br />
三维x,y,z左右手坐标系特例�Q?/strong>
令三�l�欧式空间空存在三向量Vx=�Q�x�Q?�Q?�Q?x>0)�Q�Vy=�Q?�Q�y�Q?�Q?y>0)�Q�Vz=�Q?�Q?�Q�z�Q�（注：�q�里规定z轴的正方向和向量Vx*Vy的方向一致。）此时�Q�向量Vx*Vy的方向是�W�合��x��坐标�pȝ��Q�因为向量Vx*Vy的方向与其自�w�的夹角�?�Q�由(Vx*Vy).Vz = xyz可知�Q�当z>0�Ӟ��该向量组�Q�（x�Q?�Q?�Q�，�Q?�Q�y�Q?�Q�，�Q?�Q?�Q�z�Q�）构成��x��坐标�p�R��反之，若z<0�Q�那么由(Vx*Vy).Vz = xyz<0可知�Q�该向量�l�（�Q�x�Q?�Q?�Q�，�Q?�Q�y�Q?�Q�，�Q?�Q?�Q�z�Q�）构成左手坐标�p�R��特例：�Q?�Q?�Q?�Q�，�Q?�Q?�Q?�Q�，�Q?�Q?�Q?�Q�构成右手坐标系�Q�（1�Q?�Q?�Q�，�Q?�Q?�Q?�Q�，�Q?�Q?�Q?1�Q�构成左手坐标系�?/p>

SoRoMan 2006-08-08 12:53 发表评论

�W�记:排序��法

SoRoMan — Mon, 31 Jul 2006 07:14:00 GMT

//
// File: [TestSort.cpp]
// Description:[This file illustrate the sort methods. Make sure the length of the sequence consistent with its contents!]
// Author:[SoRoMan]
// Date:[07/31/2006]
// Version:[1.0]
// History: []
//

// INCLUDES ///////////////////////////////////////////////
#include "stdio.h"

// DEFINES ////////////////////////////////////////////////
#define N 11

// PROTOTYPES /////////////////////////////////////////////
void QuickSort(int *seq, int lenght);
void InsertSort(int *seq, int lenght);
void InsertSort2(int *seq, int lenght);
void ShellSort(int *seq, int lenght);
void IncrementInsertSort(int *seq, int length, int increment);
void HeapSort(int *seq, int length);
void SelectionSort(int *seq, int length);
void BubbleSort(int *seq, int length);
void BiBubbleSort(int *seq, int length);
void AdjustHeap(int *seq, int startIndex, int endIndex);

// GLOBALS ////////////////////////////////////////////////
int nAssignmentOperation = 0; // assignment counter
int nComparsionOperation = 0; // comparsion counter

// FUNCTIONS //////////////////////////////////////////////

int main(int argc, char* argv[])
{
printf("0: Original Sequence\n");
printf("1: Quick Sort\n");
printf("2: Insert Sort\n");
printf("3: Shell Sort\n");
printf("4: Insert Sort2\n");
printf("5: Heap Sort\n");
printf("6: Selection Sort\n");
printf("7: Bubble Sort\n");
printf("8: Bi-Bubble Sort\n");
printf("-1: Exit\n");

int cat = 0;
while (cat != -1)
{
  // clear counter
  nAssignmentOperation = 0;
  nComparsionOperation = 0;

  //int array[N] = {600, 64,6,78,246,445,345,445,7,4885,1,600, 64,6,78,246,445,345,445,7,4885,1,600, 64,6,78,246,445,345,445,7,4885,1,600, 64,6,78,246,445,345,445,7,4885,1,600, 64,6,78,246,445,345,445,7,4885,1,
  //600, 64,6,78,246,445,345,445,7,4885,1,600, 64,6,78,246,445,345,445,7,4885,1,600, 64,6,78,246,445,345,445,7,4885,1,600, 64,6,78,246,445,345,445,7,4885,1,600, 64,6,78,246,445,345,445,7,4885,1};
  int array[N] = {600, 64,6,78,246,445,345,445,7745,4885,1};

  printf("\nPlease select sort method:");
  scanf("%d", &cat);
  printf("-------------------------------------------------\n");

  switch(cat)
  {
   case 0:printf("No Sort. The Original Sequence is\n");
    break;
   case 1:printf("Quick Sort\n"); QuickSort(array, N);
    break;
   case 2:printf("Insert Sort\n"); InsertSort(array, N);
    break;
   case 3:printf("Shell Sort\n"); ShellSort(array, N);
    break;
   case 4:printf("Insert Sort2\n"); InsertSort2(array, N);
    break;
   case 5:printf("Heap Sort\n"); HeapSort(array, N);
    break;
   case 6:printf("Selection Sort\n"); SelectionSort(array, N);
    break;
   case 7:printf("Bubble Sort\n"); BubbleSort(array, N);
    break;
   case 8:printf("Bi-Bubble Sort\n"); BiBubbleSort(array, N);
    break;
   default:printf("Exit...\n");
    return 0;
  }

  for(int i = 0; i < N; i++)
  {
   printf("int = %d\n", array[i]);
  }

  printf("Count of comparsion operation = %d\n", nComparsionOperation);
  printf("Count of assignment operation = %d\n", nAssignmentOperation);
  printf("-------------------------------------------------\n");
}

return 0;
}

inline void Swap(int *pCurrPost, int *pCurrKey)
{
nAssignmentOperation += 3;
int temp;

//swap value
temp = *pCurrPost;
*pCurrPost = *pCurrKey;
*pCurrKey = temp;
}

////////////////////////////////////////////////////////////////////////////////
// Quick Sort algorithm. (By SoRoMan, 2006.7.31)
// 快速排序的基本思想是基于分�ȝ��略的。对于输入的子序列L[p..r]�Q�如果规模��够小则直接进行排序（比如用前�q�的冒��、选择、插入排序均可）�Q�否则分三步处理�Q?br />// 1.分解(Divide)�Q�将待排序列L[p..r]划分��Z��个非�I�子序列L[p..q]和L[q+1..r]�Q��L[p..q]中�Q一元素的��g��大于L[q+1..r]中�Q一元素的倹{��具体可通过�q�样的途径实现�Q�在序列L[p..r]中选择数据元素L[q]�Q�经比较和移动后�Q�L[q]��处于L[p..r]中间的适当位置�Q��得数据元素L[q]的值小于L[q+1..r]中�Q一元素的倹{�?
// 2.递归求解(Conquer)�Q�通过递归调用快速排序算法，分别对L[p..q]和L[q+1..r]�q�行排序�?
// 3.合�ƈ(Merge)�Q�由于对分解出的两个子序列的排序是就地进行的�Q�所以在L[p..q]和L[q+1..r]都排好序后不需要执行�Q何计��L[p..r]��已排好序，卌��然合�q��?
// �q�个解决��程是符合分��L��的基本步骤的。因此，快速排序法是分��L��的经典应用实例之一�?br />// Input Parameters: seq: pointer variable that identifies which sequence will be sorted.
// length: int that identifies the length of the sequence.
// Output Parameters: None.
// Return: None.
////////////////////////////////////////////////////////////////////////////////
void QuickSort(int *seq, int length)
{
if(length <= 1)
{
  return;
}
else
{
  int post = *seq; // set post
  int *pCurrPost = seq; // set current position of post
  int *pCurrKey; // current position of key

  for(int j = length - 1, i = 1; i <= j;)
  {
   // handle the right sub-sequence
   while(i <= j)
   {
    pCurrKey = seq + j;

    if(*pCurrKey < post)
    {
     Swap(pCurrPost, pCurrKey);
     pCurrPost = pCurrKey;

     break;
    }
    else
    {
     j--;
    }

    nComparsionOperation ++;
   }

   // handle the left sub-sequence
   while(i <= j)
   {
    pCurrKey = seq + i;

    if(*pCurrKey > post)
    {
     Swap(pCurrPost, pCurrKey);
     pCurrPost = pCurrKey;

     break;
    }
    else
    {
     i++;
    }

    nComparsionOperation ++;
   }
  }
  // handle two sub sequences recursively
  int lleng = pCurrPost - seq; // left sub sequence
  int rleng = length - lleng - 1; // right sub sequence
  QuickSort(seq, lleng);
  QuickSort(seq + lleng + 1, rleng);
}
}

////////////////////////////////////////////////////////////////////////////////
// Insert Sort algorithm (A special increment insert sort, increment = 1). (By SoRoMan, 2006.7.31)
//插入排序的基本思想是，�l�过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅��L[i]插入L[1..i-1]的适当位置�Q��得L[1..i]又是排好序的序列。要辑ֈ��q�个目的�Q�我们可以用��序比较的方法。首先比较L[i]和L[i-1]�Q�如果L[i-1]�?L[i]�Q�则L[1..i]已排好序�Q�第i遍处理就�l�束了；否则交换L[i]与L[i-1]的位�|�，�l�箋比较L[i-1]和L[i-2]�Q�直到找到某一个位�|�j(1≤j≤i-1)�Q��得L[j] ≤L[j+1]时�ؓ止�?br />//��a��?插入排序��是每一步都��一个待排数据按其大��插入到已经排序的数据中的适当位置�Q�直到全部插入完毕。插入排序方法分直接插入排序和折半插入排序两�U�，�q�里只介�l�直接插入排序，折半插入排序留到“查�䏀�内容中�q�行
// Input Parameters: seq: pointer variable that identifies which sequence will be sorted.
// length: int that identifies the length of the sequence.
// Output Parameters: None.
// Return: None.
////////////////////////////////////////////////////////////////////////////////
void InsertSort(int *seq, int length)
{
IncrementInsertSort(seq, length, 1);
}

void InsertSort2(int *seq, int length)
{
for(int i = 1; i < length; i++)
{
  for (int j = 0; j < i; j++)
  {
   if(*(seq + i) < *(seq + j))
   {
    int temp = *(seq + i);
    nAssignmentOperation ++;

    // insert, move (i-j) items
    for(int k = i; k > j; k-- )
    {
     *(seq + k) = *(seq + k - 1);
     nAssignmentOperation ++;
    }

    *(seq + k) = temp;
    nAssignmentOperation ++;

    nComparsionOperation ++;

    break;
   }
  }
}
}

void IncrementInsertSort(int *seq, int length, int increment)
{
for(int k = 0; k < increment; k++)
{
  for (int i = increment + k; i < length; i+=increment + k)
  {
   int temp = *(seq + i);
   for (int j = i; j > increment - 1;)
   {
    nComparsionOperation ++;

    if(temp > *(seq + j - increment))
    {
     *(seq + j) = *(seq + j - increment);
     nAssignmentOperation ++;
     j-=increment;
    }
    else
    {
     break;
    }
   }

   *(seq + j) = temp;
   nAssignmentOperation ++;
  }
}
}

////////////////////////////////////////////////////////////////////////////////
// Shell Sort algorithm (Increment insert sort, increment = increment/3 + 1.). (By SoRoMan, 2006.7.31)
// Input Parameters: seq: pointer variable that identifies which sequence will be sorted.
// length: int that identifies the length of the sequence.
// Output Parameters: None.
// Return: None.
////////////////////////////////////////////////////////////////////////////////
void ShellSort(int *seq, int length)
{
for(int increment = length; increment > 1;)
{
  increment = increment/3 + 1;
  IncrementInsertSort(seq, length, increment);
}
}

////////////////////////////////////////////////////////////////////////////////
// Heap Sort algorithm. (SoRoMan, 2006.7.31)
//
//1.堆的概念�Q?br />//堆是一个关键字序列{k1,k2,�?kn},它具有如下特性：
//ki ≤k2i, ki �?k2i+1
//或ki �?k2i,ki �?k2i+1(i=1,2,�? └n/2�?
//堆的�Ҏ(gu��)��在完全二叉树中解释为：完全二叉树中��M��l�点的关键字都小于等于（或大于等于）它的左右孩子的关键字�?br />//如下列关键字序列均是堆： {5,23,16,68,94,72,71,73} (��顶�? {96,83,27,38,11,9} �Q�大��堆�Q?由堆的定义可知：若关键字序列{k1,k2,�?kn}是堆�Q�则堆顶元素是n个元素序列中的最��（或最大）元素�?/p>
//2.基本思想�Q?br />//首先��初始待排序记录序列建堆�Q�则堆顶元素必�ؓ含最大关键字或最��关键字的记录，输出该记录，然后��剩余记录再调整为堆�Q�如此反复，直至排序�l�束�?br />//在堆排序主要需解决两个问题�Q?br />//�?如何建堆�Q?在完全二叉树中，所有序号i>└n/2┘的�l�点都是叶子�Q�因此，以这些结点�ؓ根的子树均已是堆�Q�这样只需��以序号为└n/2�? └n/2�?1, └n/2�?2,�?1的结点�ؓ栏V��的子树都调整�ؓ堆即可。在按此�ơ序调整每个�l�点�Ӟ��其左、右子树均已是堆�?br />//�?若ki的左、右子树已经是堆�Q�如何将以ki为根的完全二叉树也调整�ؓ堆？因ki的左、右子树已经是堆�Q�所以必��d��ki 和它的左、右孩子中选出最��（或最大）的结�Ҏ(gu��)��到ki的位�|�上�Q�不妨设k2I关键字最��，��ki与k2I交换位置�Q�而交换之后有可能��D��以k2I为根的子树不再�ؓ堆，于是可重复上�q�过�E�，��以k2I为根的子树调整�ؓ堆，…�?如此逐层下去�Q�最多可能一直调整到树叶�Q�此�Ҏ(gu��)��U�Cؓ"�{�选法"�?/p>
//3.性能分析�Q?br />//堆排序的旉��主要由徏立初始堆和不断重复徏堆这两部分的旉��开销构成。其中：建立初始堆时�Q��d��需�q�行的关键字比较�ơ数 �?4n =O(n) ;排序�q�程中进行n-1�ơ重建堆所�q�行的��L��较次��C��过下式�Q?2*(�?log2(n-1) �?�?log2(n-2) �?�? �?log22 �? < 2n �?log2n �?O(n log2n)因此堆排序�ȝ��旉��复杂度是 O(n+ n log2n)= O(n log2n)�?br />//堆排序在最坏情况下的时间复杂度也是O(nlog2n)�Q�相对于快速排序来��_��q�是堆排序的最大优炏V�?br />//另外�Q�堆排序仅需一个记录大��供交换用的辅助�I�间。由于徏初始堆所需的比较次数较多，所以堆排序不适宜于记录较?y��u)��的文�g�Q�但对n较大的文件还是很有效的�?br />// Input Parameters: seq: pointer variable that identifies which sequence will be sorted.
// length: int that identifies the length of the sequence.
// Output Parameters: None.
// Return: None.
////////////////////////////////////////////////////////////////////////////////
void HeapSort(int *seq, int length)
{
for(int n = length; n > 0; n--)
{
  for(int j = n/2; j > 0; j--)
  {
   AdjustHeap(seq, j, n);
  }

  Swap(seq, seq+n-1);
}
}

void AdjustHeap(int *seq, int startIndex, int endIndex)
{
while(2*startIndex <= endIndex)
{
  int i = startIndex - 1;
  startIndex = startIndex*2;

  nComparsionOperation ++;
  if (startIndex < endIndex && *(seq + startIndex -1) < *(seq + startIndex))
  {
   startIndex++;
  }

  nComparsionOperation ++;
  if(*(seq + startIndex -1) > *(seq + i))
  {
   Swap(seq + startIndex - 1, seq + i);
  }
  else
  {
   break;
  }
}
}

////////////////////////////////////////////////////////////////////////////////
// Selection Sort algorithm. (SoRoMan, 2006.7.31)
// Input Parameters: seq: pointer variable that identifies which sequence will be sorted.
// length: int that identifies the length of the sequence.
// Output Parameters: None.
// Return: None.
////////////////////////////////////////////////////////////////////////////////
void SelectionSort(int *seq, int length)
{
for(int i = 0; i < length; i++)
{
  int k = i;
  for(int j = i+1; j < length; j++)
  {
   nComparsionOperation ++;
   if (*(seq + j) < *(seq + k))
   {
    k = j;
   }
  }

  Swap(seq + k, seq + i);
}
}

////////////////////////////////////////////////////////////////////////////////
// Bubble Sort algorithm. (SoRoMan, 2006.7.31)
// Input Parameters: seq: pointer variable that identifies which sequence will be sorted.
// length: int that identifies the length of the sequence.
// Output Parameters: None.
// Return: None.
////////////////////////////////////////////////////////////////////////////////
void BubbleSort(int *seq, int length)
{
for(int i = 0; i < length; i++)
{
  for(int j = length-1; j > i; j--)
  {
   nComparsionOperation ++;
   if (*(seq + j) < *(seq + j - 1))
   {
    Swap(seq + j, seq + j - 1);
   }
  }
}
}

////////////////////////////////////////////////////////////////////////////////
// Bi-Directinal Bubble Sort algorithm. (SoRoMan, 2006.7.31)
//思想�Q?br />//��Z��在一��排序中�Q�位于最后一�ơ交换关键字的的后面的关键字序列已经是有序的�Q�所以不用再排序�?br />//相对于一般的冒��排序�Q�可以减��关键字比较�ơ数�Q�但交换�ơ数不变�?br />// Input Parameters: seq: pointer variable that identifies which sequence will be sorted.
// length: int that identifies the length of the sequence.
// Output Parameters: None.
// Return: None.
////////////////////////////////////////////////////////////////////////////////
void BiBubbleSort(int *seq, int length)
{
int k,low,up;
low = 0;
up = length-1;
while (up > low)
{
  k = low;

  for(int i = low; i < up; i++)
  {
   nComparsionOperation ++;
   if (*(seq + i) > *(seq + i + 1))
   {
    Swap(seq + i, seq + i + 1);

    k = i;
   }
  }

  up = k;

  for(int j = up; j > low; j--)
  {
   nComparsionOperation ++;
   if (*(seq + j) < *(seq + j - 1))
   {
    Swap(seq + j, seq + j - 1);

    k = j;
   }
  }

  low = k;
}

}

SoRoMan 2006-07-31 15:14 发表评论

SoRoMan — Thu, 27 Jul 2006 03:07:00 GMT

以前看到Bresenham�ȝ��法�Q�直接拿来用�Q�没有去推导�?�q�日,参考一些资�?�Ҏ(gu��)��理其��法推导�q�程如下。各位大虑֦�果知道其�l�节�Q�赶紧闪�q�，不用��费旉��了�?/p>
基本上Bresenham�ȝ��法的思�\如下:

// 假设该线�D�位于第一象限内且斜率大于0��于1,设�v点�ؓ(x1,y1),�l�点�?x2,y2).
// �Ҏ(gu��)��对称�?可推��D��全象限内的线�D?
1.画�v�?x1,y1).
2.准备��M��个点。x坐标�?�Q�判断如果达到终点，则完成。否则，由图中可�?下个要画的点要么为当前点的右��L��?要么是当前点的右上邻接点.
2.1.如果�U�段ax+by+c=0与x=x1+1的交点的y坐标大于M点的y坐标的话,下个点�ؓU(x1+1,y1+1)
2.2.否则,下个点�ؓB(x1+1,y1+1)
3.�ȝ��(U或者B).
4.跛_��W?�?
5.�l�束.

�q�里需要细化的是怎么判断下个要画的点为当前点的右��L��点还是当前点的右上邻接点.

讄��D�|��E�：ax+by+c=0(x1令dx=x2-x1,dy=y2-y1
则：斜率-a/b = dy/dx.

从第一个点开始，我们有F(x,1,y1) = a*x1+b*y1+c=0
下面求线�D�ax+by+c=0与x=x1+1的交�?
由a*(x1+1)+b*y+c = 0, 求出交点坐标y=(-c-a(x1+1))/b
所以交点与M的y坐标差值Sub1 = (-c-a(x1+1))/b - (y1+0.5) = -a/b-0.5�Q�即Sub1的处始��gؓ-a/b-0.5�?/p>
则可得条件当 Sub1 = -a/b-0.5>0时�?即下个点为U.
反之,下个点�ؓB.
代入a/b,则Sub1 = dy/dx-0.5.

因�ؓ是个循环中都要判断Sub,所以得求出循环下的Sub表达�?我们可以求出Sub的差值的表达�?下面求x=x1+2时的Sub�Q�即Sub2
1.如果下下个点是下个点的右上邻接点�Q�则
Sub2 = (-c-a(x1+2))/b - (y1+1.5) = -2a/b - 1.5
故Sub差值Dsub = Sub2 - Sub1 = -2a/b - 1.5 - (-a/b-0.5) = -a/b - 1.代入a/b得Dsub = dy/dx -1;
2.如果下下个点是下个点的右��L��点，
Sub2 = (-c-a(x1+2))/b - (y1+0.5) = -2a/b - 0.5
故Sub差值Dsub = Sub2 - Sub1 = -2a/b - 0.5 - (-a/b-0.5) = -a/b. 代入a/b得Dsub = dy/dx;

于是�Q�我们有了Sub的处始值Sub1 = -a/b-0.5 = dy/dx-0.5,又有了Sub的差值的表达式Dsub = dy/dx -1 �Q�当Sub1 > 0�Q�或 dy/dx�Q�当Sub1 < 0�Q?�l�化工作完成�?/p>
于是pcode可以�l�化如下�Q?/strong>

// Pcode for Bresenham Line
// By SoRoMan
x=x1;
y=y1;
dx = x2-x1;
dy = y2-y1;
Sub = dy/dx-0.5; // 赋初��|��下个要画的点与中点的差�?/p>
DrawPixel(x, y); // 画�v�?br />while(x{
x++;
if(Sub > 0) // 下个要画的点为当前点的右上邻接点
{
Sub += dy/dx - 1; //下下个要�ȝ��点与中点的差�?br /> y++; // 右上��L��点y需�?
}
else// 下个要画的点为当前点的右��L��?br /> {
Sub += dy/dx;
}
// ��M��个点
DrawPixel(x,y);
}

PS:一般优化：
为避免小数�{整数以及除法�q�算�Q�由于Sub只是用来�q�行正负判断�Q�所以可以��oSub = 2*dx*Sub = 2dy-dx,�?br />相应的DSub = 2dy - 2dx�?dy.

思�?:如果Sub = 0�Ӟ��会��生取两个炚w��可以的问题。这个问题还没深入�?/p>

SoRoMan 2006-07-27 11:07 发表评论

SoRoMan — Wed, 26 Jul 2006 08:55:00 GMT

思考：计算机图形学中的左上像素填充�U�定�Q�top-left filling convention for filling geometry�Q?/strong>

我们知道目前昄��器显�C�的原理�Q�光栅化昄��最��的单元是pixel(或者说�_�ֺ�为piexl�Q�，一个pixel所占的区域一般是个正方�Ş�Q�显�C�器上的画面��q��一个或多个�q�样的小�Ҏ(gu��)��l�成。如果以每个��方��gؓ一个单元来制定屏幕坐标的话�Q�问题就来了�Q�因为方格本�w�有大小�Q�不是一个严格意义上�?�?�?br />
问题来源�Q�屏�q�坐标点的选取以及像素�Ҏ(gu��)��本��n的大��?/strong>
如果以方��g��心点为基准制定坐标点�Q�即对于��L��一整数坐标点p(x,y),p必�ؓ某个像素�Ҏ(gu��)��的中心）�Q�以一个方��gؓ跨度来制定屏�q�坐标系的话。如图，屏幕�?X3的方格组成一个正方�Ş的画面，如果按照�Ҏ(gu��)��中心点�ؓ基准制定坐标点，其区域屏�q�坐标�ؓ�Q?�Q?�Q?�Q?�Q�（注意�Q?�Q?�Q?都位于方��g��心，其中�Q�左上角坐标�?0,0)�Q�右下角坐标为（2�Q?�Q�）�Q�而按照数学运��，其上下跨距就�?-0 = 2 pixels�Q�左双��?-0 = 2 pixels�Q�即��d��包含2X2=4个方�?而实际画面中的跨距是3X3�Q�即共包�?个方��|��从最左上端到最右下端）�Q�问题来了，前后矛盾了。左上像素填充约定可以解册��个问题�?br />
问题解决�Q�左上像素填充约�?/strong>
�q�是丑ֈ�才的例子�Q�如果给定左上角坐标�?0,0)�Q�右下角坐标为（2�Q?�Q�的矩�Ş区域�Q�叫昄��讑֤��ȝ��制的话，按照左上像素填充�U�定�Q�在屏幕上填充的像素点将�?�Q?�Q?�Q?�Q?�Q?�Q?�Q?�Q?�Q?�Q?�Q?�Q�这�?X2区域�Q�而非图中所�C�的3X3区域。反�q�来说图中所�C�的3X3区域要用坐标表示的话应该是（0�Q?�Q?�Q?�Q�。简单来��_��在左上像素填充约定下�Q�要填充�Q�x1,y1,x2,y2�Q�（x1,y1,x2,y2为整敎ͼ�的矩形，实际填充的区域会是（x1-0.5,y1-0.5,x2-0.5,y2-0.5�Q?�q�个区域的左上角像素坐标为（x1,y1�Q?右下角像素坐标�ؓ(x2-1,y2-1)�Q�即实际的填充区域会向左和向上各偏移0.5个像素。故�U�左上像素填充约定�?/p>
0 1 2
   0 口口�?br />   1 口口�?br />   2 口口�?br />

D3D, GDI, OpenGL�{�图形库使用左上填充�U�定的，如果接触�q�这些图形库�Q�你可能会知道这个约定。还记得��M��个全屏幕的矩形吧�Q�DrawRectangle(0, 0, Screen_Width-1, Screen_Height-1)�?br />
��x��一�Q?/strong>惛_��别的填充�U�定�Q�比如右上，左下�Q�右下等�Q�这些不知道有哪些系�l��用�?br />
��x��二：如果以像素方格的左上角�ؓ基准制定坐标点（卛_��于�Q意一整数坐标点p(x,y),p必�ؓ某个像素�Ҏ(gu��)��的左上角�Q�，情况怎么��P��q�时�Q�给定（0�Q?�Q?�Q?�Q�，则填充时可以�q�会遇到一��L��问题�Q�填充（0�Q?�Q?�Q?�Q?�Q?�Q?�Q?�Q?�Q?�Q?�Q�，�Q?�Q?�Q�，�Q?�Q?�Q�，�Q?�Q?�Q�，�Q?�Q?�Q�，�Q?�Q?�Q�，最后还是包含了3X3= 9个像素�?br />
��x��三：
to be continued...

SoRoMan 2006-07-26 16:55 发表评论

Self Training - Rendering

SoRoMan — Mon, 24 Jul 2006 09:33:00 GMT

Self Training-Rendering
Tool
   Maya Basic
   Maya Rendering Basic
   Maya API/SDK
Library
   OpenGL Basic
Theory
   Computering Geometry
   Real-Time Rendering
      Graphic Algorithm
         Draw
            Draw Line
            Draw Circle
         Clip
            Object Space
            Image Space
   Linear Math

To be continued...

SoRoMan 2006-07-24 17:33 发表评论

Design Pattern之Singleton模式

SoRoMan — Sun, 16 Jul 2006 15:12:00 GMT
     摘要: <转脓(chu��ng)-To Me>概述 Singleton模式五种实现 ...  阅读全文

SoRoMan 2006-07-16 23:12 发表评论

性8sex亚洲区入口,国产精品免费在线,国产日韩在线看

Blog�U�d��新地址http://www.cnblogs.com/soroman

探讨�Q�物体绕��L��向量的旋�?四元数法VS.旋�{矩阵法的性能比较

探讨:3D透视投媄变换详解-��D��视��^面和屏幕的宽高比问题

思考：关于The Tower of Babylon

�W�记�Q�基�Q�向量叉�U�与左右坐标�pȝ��关系

�W�记:排序���法

Self Training - Rendering

Design Pattern之Singleton模式

�W�记:排序��法