4.2.4 원래의 점으로부터의 AABB의 복원

좌표계에서의 축 재조정과 같은 AABB의 크기 재조정이 동적으로 이루어지는 비법이 이번 절에서 설명된다. 꽉 맞는 경계 상자처럼, 기본이 되는 기하적인 경계 객체는 검사를 하고, 경계 상자는 6개의 다른방향의 극점을 찾아서 생성된다. 근접점은 정점벡터에서 방향벡터로의 투영을 통해 계산된다. 그러므로, 정규화는 필요없다. 이 과정은 다음 코드에서 그려지며, 이것은 가장 가까운점과 가장 먼 점을 찾아낸다.

 

void ExtreamPointsALongDirection(Vector dir,point pt[],int n,int *imin,int *imax)

{

float minproj=FLT_MAX,maxproj=-FLT_MAX;

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

{

float proj=Dot(pt[i],dir);

if(proj<minproj){

minproj=proj;

*imin=i;

}

if(proj>maxproj){

maxproj=proj;

*imax=i;

}

}

}

n이 거대할때, O(n)과정은 실행시간에 복잡해진다. 사전계산이 속도를 높여줄수 있다.  또 하나의 간단한 방법은 블록껍데기를 추가함으로써 경계용량을 결정하는데 기여한다.(4.6절 참조) 이 사전계산 단계에서는, 객체의 블록껍데기 위의 모든 k 정점은 저장되기때문에 정점이 남아있기전에 돌아온다. 따라서, 딱맞는 AABB객체는 단 하나의 k 정점의 계산만으로 생성될수 있다. 일반적으로 오목한 용량이 이기지만, 블록한 용량은 이미 블록껍데기에 존재하며, 개선되지 않을것이다.

  추가함므로써, 구조 사전계산, 정점 지정은 O(log n)의 시간동안 진행된다. 예를들어, 돕킨-커크페트릭 단계에서 이목적을 위해 사용된다. 하지만, 구조물에서 여분의 메모리를 필요로 하기때문에, 그들을 가로질러 넘겨버리는것 과같이, 그들은 대부분 순환에서 지나치는 것을 고려해야한다. 확실히 딱맞는 경계 용량은 중요하고, AABB보다 딱맞는 경계 용량은 고려되어야 한다.