변환 된 구체에 대한 AABB 계산

Question

필자는 객체 공간에서 중심점과 반지름으로 표현 된 구를 가지고 있습니다. 구체는 스케일, 회전 및 변환을 포함 할 수있는 변형 행렬로 세계 공간으로 변형됩니다. 월드 공간에서 구의 바운딩 박스를 만들 필요가 있지만 어떻게해야할지 모르겠습니다.

public void computeBoundingBox() { 
    // center is the middle of the sphere 
    // averagePosition is the middle of the AABB 
    // getObjToWorldTransform() is a matrix from obj to world space 
    getObjToWorldTransform().rightMultiply(center, averagePosition); 

    Point3 onSphere = new Point3(center); 
    onSphere.scaleAdd(radius, new Vector3(1, 1, 1)); 
    getObjToWorldTransform().rightMultiply(onSphere); 

    // but how do you know that the transformed radius is uniform? 
    double transformedRadius = onSphere.distance(averagePosition); 

    // maxBound is the upper limit of the AABB 
    maxBound.set(averagePosition); 
    maxBound.scaleAdd(transformedRadius, new Vector3(1, 1, 1)); 

    // minBound is the lower limit of the AABB 
    minBound.set(averagePosition); 
    minBound.scaleAdd(transformedRadius, new Vector3(-1,-1,-1)); 
} 

그러나, 나는이 항상 작동 것이라고 회의적 :

는 여기에 몇 가지 경우에 작동 나의 현재의 접근 방식이다. 균일하지 않은 스케일링에 실패하면 안됩니까?

Answer 1

일반적으로 변환 된 구형은 일종의 타원체입니다. 정확한 바운딩 박스를 얻는 것은 그리 어렵지 않습니다. 모든 수학을 통과하지 않으려는 경우 :

• 참고 M 것을는
• 과 같이
• 컴퓨팅 R 아래 S의 정의를 읽어 당신의 변환 행렬 (스케일, 회전, 번역 등)입니다 최후에 기술 된 바와 같이 R에 기초하여 x, y 및범위를 계산한다. (분야 및 그 변형을 포함) 대칭의 4x4 행렬로 표현 될 수

---

일반 코닉 : 균질 점 p는 코닉 S 때 p^t S p < 0 안에.다음과 같이 M이 S 행렬을 변환 행렬하여 공간 변형 (아래 협약 점 열 벡터이다이다)

A unit-radius sphere about the origin is represented by: 
S = [ 1 0 0 0 ] 
    [ 0 1 0 0 ] 
    [ 0 0 1 0 ] 
    [ 0 0 0 -1 ] 

point p is on the conic surface when: 
0 = p^t S p 
    = p^t M^t M^t^-1 S M^-1 M p 
    = (M p)^t (M^-1^t S M^-1) (M p) 

transformed point (M p) should preserve incidence 
-> conic S transformed by matrix M is: (M^-1^t S M^-1) 

대신 포인트 비행기에 적용되는 원추의 이중는로 표시되는 S의 역함수; (행 벡터로 표현) 평면 질문에 대한 :

let (M S^-1 M^t) = R = [ r11 r12 r13 r14 ] (note that R is symmetric: R=R^t) 
         [ r12 r22 r23 r24 ] 
         [ r13 r23 r33 r34 ] 
         [ r14 r24 r34 r44 ] 

axis-aligned planes are: 
    xy planes: [ 0 0 1 -z ] 
    xz planes: [ 0 1 0 -y ] 
    yz planes: [ 1 0 0 -x ] 

하는 XY 정렬 비행기를 찾으려면 : 그래서

plane q is tangent to the conic when: 
0 = q S^-1 q^t 
    = q M^-1 M S^-1 M^t M^t^-1 q^t 
    = (q M^-1) (M S^-1 M^t) (q M^-1)^t 

transformed plane (q M^-1) should preserve incidence 
-> dual conic transformed by matrix M is: (M S^-1 M^t) 

, 당신은 변환 된 원뿔 곡선 (이차 곡선)에 접하는 축 정렬 평면을 찾고 R 접선 :

 y = (r24 +/- sqrt(r24^2 - r44 r22))/r44 

,369,136 :

[0 0 1 -z] R [ 0 ] = r33 - 2 r34 z + r44 z^2 = 0 
       [ 0 ] 
       [ 1 ] 
       [-z ] 

    so, z = (2 r34 +/- sqrt(4 r34^2 - 4 r44 r33))/(2 r44) 
     = (r34 +/- sqrt(r34^2 - r44 r33))/r44 

마찬가지로 XZ 평면 정렬 용3210

와 YZ 정렬 된면이 당신에게 변환 된 영역에 대한 정확한 경계 상자를 제공

 x = (r14 +/- sqrt(r14^2 - r44 r11))/r44 

.

Answer 2

비 균일 스케일링에는 작동하지 않습니다. 라그란 지 승수 (KKT 정리)로 임의의 역변환 가능한 아핀 변환을 계산할 수 있으며, 추악해질 것이라고 생각합니다.

그러나 정확한 AABB가 필요합니까? 구의 원래 AABB를 변환하고 AABB를 가져 와서 근사값을 구할 수 있습니다. 정확한 AABB보다 커서 응용 프로그램에 맞을 수 있습니다. 구형의 AABB를 얻을 것이다

GetAABB(sphere) : 우리는 세 가지 의사 기능이 필요이를 위해

.

GetAABB(points-list)은 주어진 점 집합 (모든 점에 대한 최소/최대 좌표)의 AABB를 가져옵니다.

GetAABBCorners(p, q)은 AABB의 8 개 모서리 점을 모두 가져옵니다 (p와 q는 그 중 하나입니다).

(p, q) = GetAABB(sphere); 
V = GetAABBCorners(p, q); 
for i = 1 to 8 do 
    V[i] = Transform(T, V[i]); 
(p, q) = GetAABB(V); 

Answer 3

@ comingstorm의 답변은 훌륭하지만 많은 부분을 단순화 할 수 있습니다. M이 영역의 변환 후 1 인덱스 매트릭스,

x = M[1,4] +/- sqrt(M[1,1]^2 + M[1,2]^2 + M[1,3]^2) 
y = M[2,4] +/- sqrt(M[2,1]^2 + M[2,2]^2 + M[2,3]^2) 
z = M[3,4] +/- sqrt(M[3,1]^2 + M[3,2]^2 + M[3,3]^2) 

경우 (이것은이 변형되기 전에 영역은 반경 1 원점에서 중심을 가지고 가정합니다.) 내가 함께 블로그 포스트를 작성

합리적인 스택 오버플로 (Stack Overflow) 대답에 비해 너무 길다는 증거 인 here.