블로그 이미지
이태원에서 사는 다섯식구의 무직 가장. 흰둥에미

카테고리

분류 전체보기 (184)
Itaewon (2)
ryu's?? (1)
20121210이전 (20)
20130827이전 (147)
soo'study (13)
Total34,023
Today5
Yesterday5

'충돌'에 해당되는 글 3건

  1. 2013.01.21 1. 충돌 (3. 고급 충돌)
  2. 2013.01.21 1. 충돌 (2. 기본 충돌)
  3. 2013.01.21 1. 충돌 (1. 기하학) (1)

Bounding Sphere

- 오브젝트를 감싸는 구를 만들고, 그 구를 이용해 충돌 판정을 함.


AABB와 OBB

- AABB(Axis Aligned Bounding Box)

  - 한 오브젝트의 vertex 좌표값 중, 중심에서 가장 먼거리에 있는 X, Y, Z의 최소/최대값을 구한 후,

    8개의 점을 이용해, 육면체 박스를 만들어 줌.

    이 육면체에 대해 충돌을 검출

    X, Y, Z축에 따라 경계박스를 만들기에 모델의 움직임이나 회전에 따라, 비효율적인 공간이 많이 생김.

- OBB

  - AABB를 임의 방향으로 회전한 기울어진 경계 상자

    중심점과, 박스를 구성하는 세 방향 벡터와 중심점에서 각 면까지의 거리로 구성

  - OBB 충돌 검사

    두 OBB 중심으로 방향을 가진 직선 L 벡터를 생성하여, L에 박스의 꼭지점들을 투영하여 겹치는 공간이 있는지를 검사

- 쉬운 OBB 구하기

  - 모델을 만들 때에 정확히 세워진 모델의 AABB값을 구한 후, 모델의 변형을 AABB값들에 동일한 변환을 해줌.

    OBB에 필요한 세 방향 벡터(au, av, aw)도 초기에 세워진 상태에선 x, y, z축임.


DX에서 지원하는 함수

- HRESULT D3DXComputeBoundingBox(...);

  HRESULT WINAPI D3DXComputeBoundingSphere(...); 


Arvo 알고리즘

- 구와 박스의 충돌을 검출하는 방법으로

  "각 축에 대해 구의 중심이 최소값보다 작거나, 최대값보다 클 경우는, 구의 중심과 박스까지의 거리의 제곱을 계산한 후,

  이 합이 반지름의 제곱보다 작으면 구와 박스는 겹친다"를 전제로 함.

  구의 반경이 박스 안에 있는지 없는지를 판단하는 알고리즘


계층 충돌

- 최적화와 비슷한 개념으로, 오브젝트의 충돌 검출을 위한 Sphere를 부모, 자식으로 관리함

  전체 Sphere(부모)로 충돌 체크후, 충돌이라고 판정되면, 분할된 Sphere(자식)으로 충돌 체크

  tree 구조 충돌 처리


충돌 처리 최적화

- 먼저 계산할 수 있거나 간단한 계산으로 결과가 나올 수 있는 부분은 먼저 계산하라.

  제곱근, 삼각함수, 나누기 연산 등의 수행시간이 오래 걸리는 연산은 최대한 자제하라.

  미리 계산할 수 있는 것은 미리 계산해서 데이터를 가지고 있는다.

  연산량이 적은 충돌 검사를 선택하라.

  차원을 줄이거나 원점 이동 같은 트릭을 활용하라.


    

    


신고

'20130827이전 > 3D공간구조프로그래밍' 카테고리의 다른 글

2. 외부 지형 (3. 카메라와 공간)  (0) 2013.01.24
2. 실외 지형 (2. 하늘)  (1) 2013.01.24
2. 실외 지형 (1. Height map)  (1) 2013.01.24
1. 충돌 (3. 고급 충돌)  (0) 2013.01.21
1. 충돌 (2. 기본 충돌)  (0) 2013.01.21
1. 충돌 (1. 기하학)  (1) 2013.01.21
Posted by 흰둥에미

Plane to Plane

- Line to Plane 충돌을 이용하면 쉽게 구할 수 있음

  한 평면의 사각 테두리의 직선 벡터 v0, v1, v2, v3를 구해, 다른 한 평면과의 교점을 구함.


Triangle to Triangle

- Moller의 Interval Overlap Method와 ERIT 2가지가 있음

  그 외 Brute-force는 2-30% 느리고, SAT방식은 교차한 부분의 선분을 알 수 없음.

  Moller의 Interval Overlap Method

  - 두 삼각형이 속한 평면을 이용, 두 평면이 만나는 직선에 삼각형을 투영해 충돌을 판단.

    1. 삼각형 2의 평면의 방정식을 구하고,

    2. 삼각형 1의 점들이 평면 2에 대해 같은 방향인지 아닌지를 판별

    3. 삼각형 1의 평면의 방정식을 구하고,

    4. 삼각형 2의 점들이 평면 1에 대해 같은 방향인지 아닌지를 판별

    5. 교차선을 구하고, 가장 평행한 좌표축으로 투영

    6. 삼각형들의 교차 구간 구함(T1 : t2, t2 T2 : t3, t4)

    7. 구간 겹침 검사(t1~t2, t3~t4 두 구간이 겹치면 충돌)

  ERIT 이론

  - 첫 삼각형이 속한 평면과 다른 삼각형의 교점 선분이 첫 삼각형 안에 존재하는지 여부로 충돌을 판단

  Brute-force

  - 각 삼각형의 꼭지점 직선 ab, ac, bc로 하는 직선이 다른 삼각형과의 1개 이상의 교점이 있다면 두 삼각형은 충돌


삼각형이 만나지 않는 경우

 - 두 삼각형이 평행

    만나지 않는 경우

    삼각형 내부에 다른 삼각형이 존재


Sphere to Sphere

- 구의 두 중심 간의 거리를 계산해서 두 구의 반지름의 합보다 크면 만나지 않음.


Sphere to Line

- 직선의 방정식과 구의 방정식을 이용해 정리

  직선의 방정식의 매개변수 t에 대해 정리 후, 이차 방정식의 해를 이용해 교차 판정

  b^2-c > 0이면 두 점에서 만남

      "    = 0이면 한 점에서 만남

      "    < 0이면 만나지 않음.

  BOOL WINAPI D3DXSphereBoundProbe(...); // DX에서 지원하는 함수


 





신고

'20130827이전 > 3D공간구조프로그래밍' 카테고리의 다른 글

2. 외부 지형 (3. 카메라와 공간)  (0) 2013.01.24
2. 실외 지형 (2. 하늘)  (1) 2013.01.24
2. 실외 지형 (1. Height map)  (1) 2013.01.24
1. 충돌 (3. 고급 충돌)  (0) 2013.01.21
1. 충돌 (2. 기본 충돌)  (0) 2013.01.21
1. 충돌 (1. 기하학)  (1) 2013.01.21
Posted by 흰둥에미

3D 게임 공간의 분류 --- 물체(Object)처리

                              -- 배경 or 지형 처리 --- 실외 지형(Terrain)

                                                             -- 실내 지형(Dungeon)

                                                             -- 복합


실외 지형을 만드는 방법

- Height Map : 지형의 높이를 나타내는 이미지로 지형을 만드는 방법

  Quad Tree : 4진 트리라고도 하며 외부 지형 처리의 최적화 기법

  LOD : Level of Detail 거리에 따른 Polygon 처리 방식

  하늘 : 3D공간상의 실외 지형의 하늘(dome, box, plane) 처리


3D 공간상의 물체의 구현과 처리

- 충돌 : 3D상의 Object간의 충돌 처리

  컬링 : 보이지 않는 Polygon에 대한 처리 기법

  billboard : 실외 지형 위에 놓는 객체 처리 기법


기하학

- 수학에서 사용되는 기본 도형(점, 선, 면)과 관계된 수식이나 이론


직선의 교점

- ray tracing

  - 한 직선과 만나는 점이 있는 오브젝트가 있을 때의 처리

    카메라에서 보이는 물체에 대한 처리(옛날 3D 엔진에서 썼던 시각 판별, 컬링이나 보이지 않는 물체에 대한 처리)

    총구에서 총알이 발사해서 물체에 맞음 처리

    총알이 맞은 자국 처리

    칼과 칼이 부딪히는 판별

    쉐도우나 미러, 라이트 처리등.

- 직선과 점

  직선과 직선 : 2개의 칼이나 막대 광선이 부딪쳤는지 판별

  직선과 평명 : 총이나 광선이 특정 폴리곤이나 바닥과 충돌 지점을 알아내고 거기에 총탄 자국 등을 남길 때

  직선과 삼각형 : 특정 오브젝트에 총이나 광선에 맞았는지 판별 혹은 마우스 선택(픽킹)


점과 직선 최단 거리

- P1(x1, y1, z1), P2(x2, y2, z2)를 지나는 직선을 P라고 했을 때, 직선의 방정식(매개변수 u) P = P1 + u(P2 - P1)

  한 점을 P3(x3, y3, z3)라고 할 때 P3에서 최단거리는 수직이므로,

  (P3-P) dot (P2-P1) = 0 이 됨.(즉 P3에서 직선 P로 향하는 벡터와 직선 P의 내적이 0)

  위 식에 P를 대입하면, (P3 - P1 - u(P2 - P1)) dot (P2 - P1) = 0 가 됨.

  위 식에서 u를 구할수 있고, P의 교점 x, y, z는

  x = x1 + u(x2 - x1),  y = y1 + u(y2 - y1),  z = z1 + u(z2 - z1)로 구할 수 있다.

  위에서 구한 교점과 P3와의 거리가 0이면 점과 직선은 충돌한 것임.


직선과 직선 최단 거리

- 2D상에서 P1과 P2에 대한 직선과 P3와 P4의 직선의 방정식은

  Pa = P1 + ua(P2 - P1),   Pb = P3 + ub(P4 - P3) 가 됨.

  교차함에 의해 Pa = Pb(ua와 ub는 모름)가 되고, 이를 X와 Y에 대해서 정리하면

  x1 + ua(x2 - x1) = x3 + ub(x4 - x3),   y1 + ua(y2 - y1) = y3 + ub(y4 - y3) 

  ua = (x4-x3)(y1-y3) - (y4-y3)(x1-x3) / (y4-y3)(x2-x1) - (x4-x3)(y2-y1)

  ub = (x2-x1)(y1-y3) - (y2-y1)(x1-x3) / (y4-y3)(x2-x1) - (x4-x3)(y2-y1) 가 됨.

  따라서 교점은 x = x1 + ua(x2-x1), y = y1 + ua(y2-y1)이 되며,

  ua나 ub가 0일 경우는 수평, u > 1이면 만나지 않고, 0 < ua(b) < 1 일 경우에 교점이 구해짐.

  교점이 구해지면 충돌이라고 판정.

- 3D상에서 두 직선을 가정할 때, 각 직선의 방정식은

  L1 : P(s) = P0 + s(P1 - P0) = P0 + su

  L2 : Q(t) = Q0 + t(Q1 - Q0) = Q0 + tv

  w(s, t) = P(s) - Q(t)

  wc = P(sc) - Q(tc) = w0 + scu - tcv

  a = u dot u, b = u dot v, c = v dot v, d = u dot w0, e = v dot w0

  따라서 Sc = be-cd/ac-b^2, Tc = ae-bd/ac-b^2 이고 정리하면, 아래와 같음


직선과 평면의 교점 충돌

- 미완

직선과 삼각형의 교점

- 먼저 삼각형이 속한 평면과의 교점이 있는지를 판별한 후에 교점이 삼각형 안에 있는지 여부를 판단


충돌이나 교점 관련 DX 함수

- D3DXVECTOR3 *WINAPI D3DXPlaneIntersectLine(...);

  BOOL WINAPI D3DXIntersectTri(...);


신고

'20130827이전 > 3D공간구조프로그래밍' 카테고리의 다른 글

2. 외부 지형 (3. 카메라와 공간)  (0) 2013.01.24
2. 실외 지형 (2. 하늘)  (1) 2013.01.24
2. 실외 지형 (1. Height map)  (1) 2013.01.24
1. 충돌 (3. 고급 충돌)  (0) 2013.01.21
1. 충돌 (2. 기본 충돌)  (0) 2013.01.21
1. 충돌 (1. 기하학)  (1) 2013.01.21
Posted by 흰둥에미

최근에 달린 댓글

최근에 받은 트랙백

글 보관함

티스토리 툴바