경계량

컴퓨터 그래픽스 및 계산 기하학에서 객체 집합의 경계 볼륨은 집합 내 객체의 결합을 완전히 포함하는 닫힌 볼륨입니다.경계 볼륨은 단순한 볼륨을 사용하여 보다 복잡한 개체를 포함함으로써 기하학적 연산의 효율성을 향상시키는 데 사용됩니다.일반적으로 볼륨이 단순할수록 중복을 테스트하는 방법이 단순해집니다.

객체 집합의 경계 볼륨은 결합으로 구성된 단일 객체의 경계 볼륨이기도 합니다.따라서 설명을 비어 있지 않고 경계(유한)가 있다고 가정되는 단일 객체의 경우로 제한할 수 있습니다.

사용하다

경계 볼륨은 특정 종류의 테스트를 가속화하는 데 가장 자주 사용됩니다.

광선 추적에서 경계 볼륨은 광선 교차 테스트에 사용되며, 많은 렌더링 알고리즘에서는 좌골 테스트를 보는 데 사용됩니다.광선 또는 보기 좌절이 경계 볼륨과 교차하지 않으면 안에 포함된 개체와 교차할 수 없으므로 간단한 거부가 가능합니다.마찬가지로, 좌판에 전체 경계 부피가 포함된 경우 추가 테스트 없이 내용을 3회적으로 승인할 수 있습니다.이러한 교차로 테스트는 '표시'되어야 하는 객체 목록을 생성합니다(렌더링; 래스터라이즈됨).

충돌 감지에서 두 개의 경계 볼륨이 교차하지 않으면 포함된 개체가 충돌할 수 없습니다.

일반적으로 경계 볼륨에 대한 테스트는 개체 자체에 대한 테스트보다 훨씬 빠릅니다. 경계 볼륨의 지오메트리가 더 단순하기 때문입니다.이는 '객체'가 일반적으로 다각형 또는 다각형 근사치로 축소된 데이터 구조로 구성되기 때문입니다.어느 경우든 오브젝트가 표시되지 않는 경우 각 폴리곤을 뷰볼륨에 대해 테스트하는 것은 계산상 낭비입니다.(화면 오브젝트는 실제로 표시되는지 여부에 관계없이 화면에 대해 '잘라내야 합니다.)

복잡한 객체의 경계 볼륨을 얻기 위해 일반적인 방법은 장면 그래프 또는 보다 구체적으로 경계 볼륨 계층을 사용하여 객체/씬 그래프)을 사용하여 객체/씬을 세분화하는 것입니다.오비나무이 배경의 기본 아이디어는 뿌리가 전체 장면을 구성하고 각 잎이 더 작은 부분을 ^{[citation needed]}포함하는 나무와 같은 구조로 장면을 구성하는 것입니다.

컴퓨터 스테레오 비전에서는 물체의 실루엣에서 재구성된 경계 볼륨을 "시각 선체"^[1]라고 합니다.

공통형

특정 어플리케이션의 경계볼륨 타입의 선택은 다양한 요인에 의해 결정됩니다.객체의 경계볼륨을 계산하기 위한 계산비용, 오브젝트가 형태나 크기를 이동하거나 변경할 수 있는 어플리케이션에서의 갱신비용, 교차점 결정비용 및 원하는 교차점 정밀도이온 시험교차로 테스트의 정밀도는 보이드 공간이라고 하는 경계 물체와 관련되지 않은 경계 볼륨 내의 공간의 양과 관련이 있습니다.정교한 바운딩 볼륨은 일반적으로 빈 공간을 줄일 수 있지만 계산 비용이 더 많이 듭니다.저렴하고 빠른 테스트용이지만 대략적인 테스트용 등 여러 종류를 조합하여 사용하는 것이 일반적입니다.

여기서 다루는 유형은 모두 볼록한 경계 볼륨을 제공합니다.경계 대상 객체가 볼록한 것으로 알려진 경우 이는 제한이 아닙니다.비볼록 경계 부피가 필요한 경우, 접근법은 그것들을 다수의 볼록 경계 부피의 결합으로 표현하는 것이다.안타깝게도 교차로 테스트는 경계 상자가 정교해짐에 따라 비용이 빠르게 높아집니다.

경계 상자는 객체를 포함하는 입방체 또는 2-D 직사각형입니다.동적 시뮬레이션에서 경계 상자는 교차로 테스트가 상당히 정확해야 할 때 대략 입방체 형태의 물체에 대해 경계 구체나 실린더와 같은 다른 형태의 경계 부피보다 선호된다.예를 들어, 차와 같이 다른 물체에 정지해 있는 경우 이점은 명백합니다. 경계의 구면에는 자동차가 지면과 교차하는 것으로 나타나며, 이는 자동차의 실제 모델에 대한 보다 비싼 테스트에 의해 거부될 필요가 있습니다. 경계의 상자는 차량이 th와 교차하지 않는 것으로 즉시 표시됩니다.eground를 통해 고가의 테스트를 절약할 수 있습니다.

많은 애플리케이션에서 경계 상자는 좌표계의 축과 정렬되며, 그 후 축 정렬 경계 상자(AABB)로 알려져 있습니다.AABB와 일반적인 경우를 구별하기 위해 임의 경계 상자는 때때로 OBB(Oriented Bounding Box) 또는 기존 객체의 로컬 좌표계가 사용될 때 OOBB라고 불립니다.AABB는 OBB보다 교차점 테스트가 훨씬 간단하지만, 모델을 회전시킬 때는 단순히 회전시킬 수 없지만 재계산해야 한다는 단점이 있다.

경계 캡슐은 물체를 포함하는 쓸린 구체(즉, 구가 직선 세그먼트를 따라 이동할 때 취하는 볼륨)입니다.캡슐은 스윕된 구의 반지름과 스윕된 구가 가로지르는 세그먼트로 나타낼 수 있습니다).실린더와 유사한 특성을 가지고 있지만 교차로 테스트가 더 간단하기 때문에 사용하기 쉽습니다.캡슐의 정의 세그먼트와 다른 물체의 일부 특징 사이의 거리가 캡슐의 반지름보다 작을 경우 캡슐과 다른 물체가 교차합니다.예를 들어, 캡슐의 세그먼트 사이의 거리가 반지름의 합계보다 작을 경우, 두 개의 캡슐이 교차합니다.이것은 임의로 회전하는 캡슐을 지탱하기 때문에 실제로 실린더보다 더 매력적입니다.

바운딩 실린더는 물체를 포함하는 실린더입니다.대부분의 애플리케이션에서 실린더의 축은 씬(scene)의 수직 방향과 정렬됩니다.실린더는 수직 축을 중심으로만 회전할 수 있고 다른 축을 중심으로 회전할 수 없는 3D 개체에 적합하며, 그렇지 않으면 변환에 의해서만 이동하도록 제한됩니다.수직 축에 정렬된 두 개의 실린더가 동시에 교차할 때 교차합니다. 두 개의 선분인 수직 축에 대한 투영과 수평 평면에 대한 투영인 두 개의 원형 디스크가 교차합니다.둘 다 테스트하기 쉽습니다.비디오 게임에서는 바운딩 실린더가 똑바로 서 있는 사람들을 위한 바운딩 볼륨으로 종종 사용됩니다.

경계 타원체는 물체를 포함하는 타원체입니다.타원체는 보통 구체보다 촘촘하게 들어맞는다.타원체와의 교차는 타원체의 주축을 따라 다른 물체를 타원체 반지름의 곱셈 역과 같은 양만큼 스케일링함으로써 이루어지며, 따라서 스케일링된 물체를 단위구와 교차시키는 문제가 감소한다.적용된 스케일링에 스큐가 발생할 경우 문제가 발생하지 않도록 주의해야 합니다.스큐는 예를 들어 두 임의의 타원체 간의 충돌과 같은 경우에 타원체의 사용을 비현실적으로 만들 수 있습니다.

경계구(Bounding sphere)는 객체를 포함하는 구입니다.2-D 그래픽에서 이것은 동그라미입니다.경계 구는 중심과 반지름으로 표현된다.중심 사이의 거리가 반지름의 합을 초과하지 않을 때 두 개의 구가 교차합니다.따라서 경계 구는 임의의 수의 차원으로 이동할 수 있는 물체에 적합합니다.

경계 슬래브는 축에 어느 정도 투영되는 볼륨으로, 슬래브가 두 평면 사이에 경계가 있는 것으로 간주할 수 있습니다.경계 상자는 직교 방향 경계 슬래브의 교차점입니다.경계 슬래브는 광선^[2] 추적 속도를 높이기 위해 사용되었습니다.

2-D의 경계 삼각형은 B-스플라인 곡선의 자르기 또는 가시성 테스트 속도를 높이는 데 매우 유용합니다.사용 예는 클리핑(컴퓨터 그래픽) 제목에서 "원 및 B-스플라인 클리핑 알고리즘"을 참조하십시오.

볼록한 선체는 물체를 포함하는 가장 작은 볼록한 부피입니다.물체가 유한한 점 집합의 결합일 경우 볼록한 껍질은 폴리토프입니다.

이산배향폴리토프(DOP)는 경계박스를 일반화한다.k-DOP는 k 방향을 따라 익스텐트의 부울 교차점입니다.따라서 k-DOP는 k 경계 슬래브의 부울 교차점이며 물체를 포함하는 볼록 폴리토프(2-D는 폴리곤, 3-D는 다면체)이다.2-D 직사각형은 2-DOP의 특수한 경우이고, 3-D 박스는 3-DOP의 특수한 경우입니다.일반적으로 DOP의 축은 직교할 필요가 없으며 공간의 치수보다 더 많은 축이 있을 수 있습니다.예를 들어, 모든 모서리와 모서리가 경사져 있는 3D 박스는 13-DOP로 구성할 수 있습니다.일부 면이 퇴화되거나 모서리 또는 정점으로 축소되는 경우 실제 면 수는 2배 k 미만일 수 있습니다.

최소 경계 직사각형 또는 MBR(2-D의 최소 AABB)은 지리(또는 "지리적") 데이터 항목의 설명에 자주 사용되며, 데이터 검색(해당하는 경우 공간 쿼리 포함) 및 표시를 위해 데이터 세트의 공간 범위(지리적 메타데이터 참조)를 단순화한 프록시 역할을 합니다.또한 공간 인덱싱의 R-트리 방법의 기본 구성요소입니다.

기본 교차로 점검

일부 유형의 경계 부피(OBB 및 볼록 다면체)에 대해 효과적인 검사는 분리 축 정리의 검사입니다.여기서의 개념은 물체가 겹치지 않는 축이 존재하면 물체가 교차하지 않는다는 것입니다.일반적으로 체크되는 축은 볼륨에 대한 기본 축(AABB의 경우 단위 축, OBB의 경우 각 OBB의 3개 기준 축)의 축입니다.종종 이전 축의 교차곱(각 객체에서 한 축)도 확인합니다.

AABB의 경우, 이 테스트는 단위 축의 관점에서 단순한 오버랩 테스트 세트가 됩니다.M_x,N에 의해 정의된 AABB와 O,P에 의해 정의된 AABB의 경우 (M > P_x), (O_xy > N_xyy), (M_yz > N), (M > P_z), (O_z > N_z) 또는 (O > N)의 경우에는 M,N이 교차하지 않습니다.

AABB는 예를 들어 길이 L의 가장자리를 가지며 C를 중심으로 축 N을 따라 투영되는 경우 축을 따라 투영할 수도 있습니다.
$displaystyle$$5$$L_{x} N_{x} +0.5$$L_{y} N_{y} +0.5$$L_{z} N_{z}$ $\backslash ,\}$ 및 $b{\displaystyle }$ ${\displaystyle =}$ ${\displaystyle Cn}$N { $displaystyle$ b =$C*N,}$ $또는$ b ${\displaystyle =}$ ${\displaystyle C_{}}$ x ${\displaystyle {}_{}{}_{}{x}_{}}$ + ${\displaystyle C_{}}$ ${\displaystyle {}_{}{}_{}}$ +${\displaystyle {}_{}{}_{}}$ ${\displaystyle z_{}}$ Z { $display$b$$=$C_{x} N$_ {$x}$$C_{y}N_{y}+C_{z$$}N_{$z$\},\}$ $및{\displaystyle }$ m${\displaystyle =}$ ${\displaystyle b}$ -${\displaystyle }$r, ${\displaystyle n=}$ ${\displaystyle b}$+ r {\$displaystyle m=b-r, n=b+$r$$,}. 여기서 m과 n은 최소 및 최대 범위입니다$.$

OBB는 이 점에서 비슷하지만 조금 더 복잡합니다.위와 같이 L과 C를 사용하고 I, J 및 K를 OBB의 베이스 축으로 하는 OBB의 경우, 다음 절차를 수행합니다.

${\displaystyle r=0.5L_{x} N*I +0.5L_{y} N*J +0.5L_{z} N*K,}$

${\displaystyle m=C*N-r{\mbox{및 }}n=C*N+r,}$

m, n 및 o 의 범위에 대해서는, m > p 또는 o > n 의 경우는, 그것들이 교차하지 않는다고 말할 수 있습니다.따라서 각 OBB의 I, J, K축을 따라 2개의 OBB 범위를 투영하여 비교차 여부를 확인함으로써 비교차 검출이 가능하다.이들 축의 교차 곱(I₀×I₁, I₀×J₁, ...)을 추가로 확인함으로써 교차로가 불가능하다는 것을 보다 확실하게 할 수 있다.

축 투영을 사용하여 비교차를 결정하는 이 개념은 볼록 다면체까지 확장되지만, 베이스 축 대신 각 다면체 면의 규범이 사용되며, 축에 대한 각 정점의 최소 및 최대 점곱에 근거한다.이 설명에서는 체크가 월드 스페이스에서 행해지고 있는 것을 전제로 하고 있습니다.

두 k-DOP의 교차는 AABB와 매우 유사하게 계산할 수 있습니다. 각 방향에 대해 두 DOP의 대응하는 두 개의 간격을 확인하기만 하면 됩니다.즉, DOP가 AABB의 일반화인 것처럼 교차 테스트는 AABB 오버랩 테스트의 일반화입니다.두 개의 DOP의 중복 테스트의 복잡도는 O()k에 있습니다.그러나 이것은 두 DOP가 동일한 방향 세트에 대해 주어진다고 가정한다.둘 중 하나가 회전하면 이는 더 이상 사실이 아닙니다.이 경우 2개의 DOP의${\displaystyle {}^{}{}^{}}$,$$({$displaystyle D^{1$},$D^{$2})의$$ $교차점$을 확인하는 비교적 쉬운 방법 중 하나는 회전된 $({$ D$^{2$$})$를 $DOP{\displaystyle {\stackrel{}{}}^{}}$ D$({$의 방향을$$ 기준으로 최소로 둘러싸는 것입니다.e 첫 번째 $DOP{\displaystyle {}^{}}$ $({$ D$^{1$이 순서는 조금 더 복잡하지만, 최종적으로 복잡도 O()k의 행렬 벡터 곱셈이 됩니다.^[3]

「 」를 참조해 주세요.

• 경계구
• 볼록 선체 알고리즘
• 최소 경계 상자
• 최소 경계 직사각형
• 공간 색인

레퍼런스

외부 링크

• epicgames.com의 같은 모델의 여러 DOP 그림