4.3.2 경계 구 계산

경계구의 첫번째 간단한 검사는 AABB의 모든점을 통해 할수 있다. AABB의 중점은 구의 중심점으로 선택되고 반지름은 중심점에서 가장 먼거리로 결정된다. 참고로 AABB 중점 대신 기하적 중심을 사용하는 것은 아주 안좋은 경게구를 만들 수 있다. 빠른 방법임에도 불구하고, 정확성은 시각적 방법보다 안좋다.

  간단한 경계구의 계산의 대안으로는 [Ritter90]이 있다. 이 알고리즘은 대부분의 경계구의 좋은 시작점을 찾으려고 시도하고, 모든점을 경계하는 것보다 좀더 개선된다. 이 알고리즘의 진척은 2가지 길이 있다. 첫번째 길은 6개의 극점의 좌표축을 찾는것이다. 6개점 바깥에는, 점쌍의 가장 먼곳이 선택된다. 구의 중심은 이 두점의 중점에 선택되며, 반지름은 그들의 반으로 설정된다.

void MostSeparatedpointsOnAABB(int &min,int &max,Point pt[],int numPts)

{

int minx=0,maxx=0,miny=0,maxy=0,maxz=0;

for(int i=1;i<numPts;i++){

if(pt[i].x<pt[minx].x) minx=i;

if(pt[i].x>pt[maxx].x) maxx=i;

if(pt[i].y<pt[miny].y) miny=i;

if(pt[i].y>pt[maxy].y) maxy=i;

if(pt[i].z<pt[minz].z) minz=i;

if(pt[i].z>pt[maxz].z) maxz=i;

}

 

float dist2x=Dot(pt[maxx]-pt[minx],pt[maxx]-pt[minx]);

float dist2y=Dot(pt[maxy]-pt[miny],pt[maxy]-pt[miny]);

float dist2z=Dot(pt[maxz]-pt[minz],pt[maxz]-pt[minz]);

 

min=minx;

max=maxx;

if(dist2y>dist2x && dist2y>dist2z){

max=maxy;

min=miny;

}

if(dist2z>dist2x&&dist2z>dist2y){

max=maxz;

min=minz;

}

}

void SphereFromDistantPoints(Sphere &s,point pt[],int numPts);

 

s.c=(Pt[min]+pt[max])*0.5f;

s.r=Dot[pt[max]-s.c,pt[max]-s.c);

s.r=sqrt(s.r);

}

  두번째 길은, 모든점은 다시 순환한다. 현재 구의 바깥의 모든점은 바깥점과 이전의 구를 아우르는 구가 갱신된다. 다시말해서, 각각의 이전의 구의 중심인 바깥점의 반대의 뒷면의 점간의 면으로부터 새로운 구의 반지름이 생긴다.

 

void SphereOfSphereAndPt(Sphere &s,Point &p)

{

Vector d=p-s.c;

float dist2=Dot(d,d);

 

if(dist2>s.r*s.r){

float dist=Sqrt(dist2);

float newRadius=(s.r+dist)*0.5f;

float k=(newRadius-s.r)/dist;

s.r=newRadius;

s.c+=d*k;

}

}

  요약된 경계구의 계산 코드이다.

 

void RitterSphere(Sphere &s,Point pt[],int numPts)

{

SphereFromDistantPoints(s,pt,numPts);

for(int i=0;i<numPts;i++)

SphereOfSphereAndPt(s,pt[i]);

}

  참된 경계구의 요약의 더좋은 시작으로, 경계구의 결과는 ㄷ더 세밀해진다. 시작점의 전략은 다음 절에서 다룬다.