경계 용량

기하적으로 떨어진 두개의 객체를 서로가 서로에게 충돌여부를 검사하는것은 매우 많은 연산을 필요로  하고, 특히 객체가 수백,수천개의 폴리곤으로 구성할 경우 기하급수적으로 연산량이 늘어납니다.

 연산량을 줄이기 위해, 객체 경계 용량은 종종 기하적 교차 검사가 이루어지기 전에 먼저 겹쳐지는지 검사를 합니다. 하나의 경계 용량은 복잡한 자연의 객체를 하나 혹은 여러개의 간단한 단일 용량으로 압축한 형태입니다. 이 아이디어는 복잡한 객체의 경계를 좀더 간단한 연산으로 대체할수 있도록 해줍니다. 경계 용량은 사용하면 겹침 거부 검사를 할수 있습니다. 왜냐하면 경계 용량은 오직 복잡한 경계 구조물이 한번의 검사만을 통해서 적절한 결과값을 반환해주기 떄문입니다.(4.1절 참조)

  물론, 객체가 정말로 겹쳐졌다면, 추가적인 검사가 이루집니다. 하지만, 대부분 경우에 적은 객체만이  경계용량에 겹쳐집니다. 그러므로, 경계용량을 사용하는 것은 일반적이며, 복잡한 객체의 세밀한 검사를 줄임으로써, 빠르게 연산을 하면서 적절한 결과값을 얻을수 있습니다.

  B객체에 대한 A객체의 검사는 일반적으로 O(n^2)의 식을 갖습니다. 그러므로,많은 폴리곤들이 검사량을 반으로 줄이면, 작업량은 75% 정도 감소합니다. 6장에서, 경계 용량 계층에서, 어떻게 가지치기 검사를 하는지, 그리고 검사를 최소화시키는지에 대해 다룹니다. 이장에서는, 경계 용량 한쌍에 관해서만 다룹니다. 더나아가,  이장의 검사는 주로 같은 타입의 경계 용량간의 검사에 대해서 다룹니다. 

다양한 타입의 경계용량간의 검사가 낯설겁니다. 다양한 경계용량타입간의 교차검사는 다음장에서 다룹니다.

  많은 기하적인 형태들은 경계 상자로 나타낼수 있습니다. 이번장에서는 가장 빈번히 사용되는 모양에 집중하였습니다. 다시말해, 상자, 블록형태용량을 말합니다. 적잖이 사용되는 경계용량은 4.7절에서 다룹니다.