精品伊人久久大香线蕉,开心久久婷婷综合中文字幕,杏田冲梨,人妻无码aⅴ不卡中文字幕

一、包圍盒簡介：

          包圍盒是一個簡單的幾何空間，里面包含著復雜形狀的物體。為物體添加包圍體的目的是快速的進行碰撞檢測或者進行精確的碰撞檢測之前進行過濾（即當包圍體碰撞，才進行精確碰撞檢測和處理）。包圍體類型包括球體、軸對齊包圍盒（AABB）、有向包圍盒（OBB）、8-DOP以及凸殼。

包圍盒廣泛地應用于碰撞檢測，比如射擊、點擊、相撞等，每一個物體都有自己的包圍盒。因為包圍盒一般為規則物體，因此用它來代替物體本身進行計算，會比直接用物體本身更加高效和簡單。

         目前廣泛應用的是AABB和OBB包圍盒，其中AABB包圍盒更常見。因為它的生成方法很簡單，因它與坐標軸是對齊的。但它也有不足，它不隨物體旋轉，可以看出當圖中的老虎沿著Z軸方向站立時，AABB包圍盒還和老虎比較貼合，但當老虎轉了一個角度后，AABB包圍盒便增加了較大的空隙，對于較精確的碰撞檢測效果不太好。這時就需要OBB包圍盒，它始終沿著物體的主成分方向生成最小的一個矩形包圍盒，可以隨物體旋轉，可用于較精確的碰撞檢測。

二、OBB包圍盒生成思路：

OBB的生成思路簡單來說就是根據物體表面的頂點，通過PCA（主成分分析）獲得特征向量，即OBB的主軸。

主成分分析是一種通過正交變換，將一組可能相關的變量集合變換成一組線性不相關的變量集合，即主成分。

在這里就要引入協方差矩陣的概念，如果學過線性代數就會知道。協方差表示的使兩個變量之間的線性相關程度。協方差越小則表示兩個變量之間越獨立，即線性相關性小。

通過協方差的計算公式，可以得到協方差矩陣。

主對角線的元素表示變量的方差。主對角線的元素較大則表示強信號。非主對角線的元素表示變量之間的協方差。較大的非對角線元素表示數據的畸變。

為了減小畸變，可以重新定義變量間的線性組合，將協方差矩陣對角化。協方差矩陣的的元素是實數并且對稱。

協方差矩陣的特征向量表示OBB包圍盒的方向。大的特征值對應大的方差，所以應該讓OBB包圍盒沿著最大特征值對應的特征向量的方向。

例：

有如下一些點：

(3.7, 1.7), (4.1, 3.8), (4.7, 2.9), (5.2, 2.8), (6.0, 4.0), (6.3, 3.6), (9.7, 6.3), (10.0, 4.9), (11.0, 3.6), (12.5, 6.4)

計算得到協方差矩陣：

對角化協方差矩陣：

于是可以得到特征向量，也就是OBB的坐標軸：

再計算得到OBB的中心點（8.10，4.05)，長寬的半長度分別為4.96 和1.49。即可一畫出二維平面若干點生成的OBB包圍盒。

關于講解詳細地可以查閱協方差矩陣和PCA分析的相關文章。我參考了如下兩篇：

1、OBB generate via PCA：  https://hewjunwei.wordpress.com/2013/01/26/obb-generation-via-principal-component-analysis/

2、PCA的數學原理：    http://blog.csdn.net/xiaojidan2011/article/details/11595869

三、代碼實現：

思路：

首先計算出協方差矩陣，用雅可比迭代法求出特征向量，再進行施密特正交化。

1、計算協方差矩陣

<span style="font-size:14px;">public Matrix3 computeCovarianceMatrix(Vector3[] pVertices,int numVertices) throws CloneNotSupportedException{		Matrix3 covariance=new Matrix3();			Vector3[] pVectors=new Vector3[numVertices];				//Compute the average x,y,z		Vector3 avg=new Vector3(0.0f,0.0f,0.0f);		for(int i=0;i<numVertices;i++){			pVectors[i]= (Vector3)pVertices[i].clone();			avg.add(pVertices[i]);		}		avg.divide(numVertices);		for(int i=0;i<numVertices;i++)			pVectors[i].sub(avg);				//Compute the covariance 		for(int c=0;c<3;c++)		{			float data[]=new float[3];			for(int r=c;r<3;r++)			{				covariance.setColRow(c, r, 0.0f);				float acc=0.0f;				//cov(X,Y)=E[(X-x)(Y-y)]				for(int i=0;i<numVertices;i++)				{					data[0]=pVectors[i].x;					data[1]=pVectors[i].y;					data[2]=pVectors[i].z;					acc+=data[c]*data[r];				}								acc/=numVertices;				covariance.setColRow(c, r, acc);				//symmetric				covariance.setColRow(r, c, acc);			}					}		return covariance;			}</span>

2、雅可比迭代法求出特征向量：

	public void jacobiSolver(Matrix3 matrix,float[] eValue ,Vector3[] eVectors ){		float eps1=(float)0.00001;		float eps2=(float)0.00001;		float eps3=(float)0.00001;				System.out.println("----------the 1.e-5----------");		System.out.println(eps1);				float p,q,spq;		float cosa = 0,sina=0;  //cos(alpha) and sin(alpha)		float temp;		float s1=0.0f;    //sums of squares of diagonal		float s2;          //elements				boolean flag=true;  //determine whether to iterate again		int iteration=0;   //iteration counter				Vector3 mik=new Vector3() ;//used for temporaty storage of m[i][k]		float[] data=new float[3];		Matrix3 t=new Matrix3();//To store the product of the rotation matrices.		t=Matrix3.identity();		do{						iteration++;						for(int i=0;i<2;i++)			{				for(int j=i+1;j<3;j++)				{					if(Math.abs(matrix.getColRow(j, i))<eps1)						matrix.setColRow(j, i, 0.0f);					else{						q=Math.abs(matrix.getColRow(i, i)-matrix.getColRow(j, j));						if(q>eps2){							p=(2.0f*matrix.getColRow(j, i)*q)/(matrix.getColRow(i, i)-matrix.getColRow(j, j));							spq=(float)Math.sqrt(p*p+q*q);							cosa=(float)Math.sqrt((1.0f+q/spq)/2.0f);							sina=p/(2.0f*cosa*spq);						}						else							sina=cosa=INV_SQRT_TWO;										for(int k=0;k<3;k++){						temp=t.getColRow(i, k);						t.setColRow(i, k, (temp*cosa+t.getColRow(j, k)*sina));						t.setColRow(j, k, (temp*sina-t.getColRow(j, k)*cosa));					}					for(int k=i;k<3;k++)					{						if(k>j){							temp=matrix.getColRow(k, i);							matrix.setColRow(k, i, (cosa*temp+sina*matrix.getColRow(k, j)));							matrix.setColRow(k, j, (sina*temp-cosa*matrix.getColRow(k, j)));						}						else						{							data[k]=matrix.getColRow(k, i);							matrix.setColRow(k, i, (cosa*data[k]+sina*matrix.getColRow(j, k)));														if(k==j)								matrix.setColRow(k, j, (sina*data[k]-cosa*matrix.getColRow(k, j)));						}					}					data[j]=sina*data[i]-cosa*data[j];										for(int k=0;k<=j;k++)					{						if(k<=i)						{							temp=matrix.getColRow(i, k);							matrix.setColRow(i, k, (cosa*temp+sina*matrix.getColRow(j, k)));							matrix.setColRow(j, k, (sina*temp-cosa*matrix.getColRow(j, k)));													}						else							matrix.setColRow(j, k, (sina*data[k]-cosa*matrix.getColRow(j, k)));											}					}					}			}			s2=0.0f;			for(int i=0;i<3;i++)			{				eValue[i]=matrix.getColRow(i, i);				s2+=eValue[i]*eValue[i];			}						if(Math.abs(s2)<(float)1.e-5||Math.abs(1-s1/s2)<eps3)				flag=false;			else				s1=s2;		}while(flag);				eVectors[0].x=t.data[0];		eVectors[0].y=t.data[1];		eVectors[0].z=t.data[2];		eVectors[1].x=t.data[3];		eVectors[1].y=t.data[4];		eVectors[1].z=t.data[5];		eVectors[2].x=t.data[6];		eVectors[2].y=t.data[7];		eVectors[2].z=t.data[8];				System.out.println("----------------eVector without transform-----------");		for(int i=0;i<3;i++)			printVector(eVectors[i]);		System.out.println();				mik.x=data[0];		mik.y=data[1];		mik.z=data[2];		Vector3 cross=new Vector3();		Vector3.cross(cross, eVectors[0], eVectors[1]);		if((Vector3.dot(cross, eVectors[2])<0.0f))				eVectors[2].inverse();			}

3、施密特正交化：

//Schmidt orthogonal	public void schmidtOrthogonal(Vector3 v0,Vector3 v1,Vector3 v2){		v0.normalize();		System.out.println("------------v0 normalized--------------");		printVector(v0);				//v1-=(v1*v0)*v0;		System.out.println("------------v1 dot v0--------------");		System.out.println(v1.dot(v0));		v1.sub(Vector3.multiply(v1.dot(v0),v0));		v1.normalize();		Vector3.cross(v2,v0, v1);	}

將各點的（X，Y，Z）坐標投影到計算出的坐標軸上，position由累加所有點再求均值得到。求出center和半長度。

              <pre name="code" class="java">                float infinity=Float.MAX_VALUE;		Vector3 minExtents =new Vector3(infinity,infinity,infinity);		Vector3 maxExtents=new Vector3(-infinity,-infinity,-infinity);				for(int index=0;index<numVertices;index++)		{			Vector3 vec=vertices[index];			Vector3 displacement =Vector3.sub(vec, position);						minExtents.x=min(minExtents.x, Vector3.dot(displacement, orientation.getRowVector(1)));			minExtents.y=min(minExtents.y, Vector3.dot(displacement, orientation.getRowVector(2)));			minExtents.z=min(minExtents.z, Vector3.dot(displacement, orientation.getRowVector(3)));						maxExtents.x=max(maxExtents.x, Vector3.dot(displacement, orientation.getRowVector(1)));			maxExtents.y=max(maxExtents.y, Vector3.dot(displacement, orientation.getRowVector(2)));			maxExtents.z=max(maxExtents.z, Vector3.dot(displacement, orientation.getRowVector(3)));					}		//offset = (maxExtents-minExtents)/2.0f+minExtents 		Vector3 offset=Vector3.sub(maxExtents, minExtents);		offset.divide(2.0f);		offset.add(minExtents);				System.out.println("-----------the offset-------------");		printVector(offset);

<span style="white-space:pre">		</span>//中心點		position.add(orientation.getRowVector(1).multiply(offset.x));		position.add(orientation.getRowVector(2).multiply(offset.y));		position.add(orientation.getRowVector(3).multiply(offset.z));		//半長度		halfExtents.x=(maxExtents.x-minExtents.x)/2.0f;		halfExtents.y=(maxExtents.y-minExtents.y)/2.0f;		halfExtents.z=(maxExtents.z-minExtents.z)/2.0f;

上傳了一份JAVA的源碼，下載鏈接：點擊打開鏈接

轉自：http://www.cnblogs.com/iamzhanglei/archive/2011/09/23/2185627.html