Post Lists

2019년 1월 1일 화요일

Bullet Physics의 Terrain Physics를 slightly하게 분석하기

Bullet Physics 2.82 버전에 들어있는 DemoTerrain의 코드를 기반으로 공부했다.

코드가 상당히 방대하고 어려웠지만, 계속해서 공부하고 보다보니 적응이 됐다.
내가 파악한 바로는 이것이 맞는 것 같다. 여기에서 정리를 해보고,
내 코드에 적용시켜 해봐야겠다.

Bullet Physics는 Dynamic AABB Tree를 활용하여 Terrain Physics를 하려고 하는데,
나는 처음에 Terrain에 있는 모든 삼각형을 AABB로 바꾸어서 넣는지 알았다. 그러나 그런게 아니였다.

Terrain Init부분을 봐보면, Terrain 전체에 대해서, AABBmin과 AABBmax를 설정해 놓는다.
그래서 그거를 그냥 BroadPhase의 DynamicAABB Tree에 넣는다. 그래서, Terrain의 AABB 밖에 어떤 Dynamic Object들이 있지 않는 이상 그 AABB 안에 있을 때 다 검사하게 될 것이다.

여기까지는 간단했다. 그리고 BroadPhase에서 Dynamic AABB Tree가 하듯이, AABB Test를 하고 Overlapping Pair를 보내주고, Narrow Phase가 시작된다.

이 Narrow Phase가 시간을 절약해야 하는 중요한 부분인데, 그것에 대한 코드는 다음과 같다.


  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
/// process all triangles within the provided axis-aligned bounding box
/**
  basic algorithm:
    - convert input aabb to local coordinates (scale down and shift for local origin)
    - convert input aabb to a range of heightfield grid points (quantize)
    - iterate over all triangles in that subset of the grid
 */
void btHeightfieldTerrainShape::processAllTriangles(btTriangleCallback* callback,const btVector3& aabbMin,const btVector3& aabbMax) const
{
 // scale down the input aabb's so they are in local (non-scaled) coordinates
 btVector3 localAabbMin = aabbMin*btVector3(1.f/m_localScaling[0],1.f/m_localScaling[1],1.f/m_localScaling[2]);
 btVector3 localAabbMax = aabbMax*btVector3(1.f/m_localScaling[0],1.f/m_localScaling[1],1.f/m_localScaling[2]);

 // account for local origin
 localAabbMin += m_localOrigin;
 localAabbMax += m_localOrigin;

 //quantize the aabbMin and aabbMax, and adjust the start/end ranges
 int quantizedAabbMin[3];
 int quantizedAabbMax[3];
 quantizeWithClamp(quantizedAabbMin, localAabbMin,0);
 quantizeWithClamp(quantizedAabbMax, localAabbMax,1);
 
 // expand the min/max quantized values
 // this is to catch the case where the input aabb falls between grid points!
 for (int i = 0; i < 3; ++i) {
  quantizedAabbMin[i]--;
  quantizedAabbMax[i]++;
 } 

 int startX=0;
 int endX=m_heightStickWidth-1;
 int startJ=0;
 int endJ=m_heightStickLength-1;

 switch (m_upAxis)
 {
 case 0:
  {
   if (quantizedAabbMin[1]>startX)
    startX = quantizedAabbMin[1];
   if (quantizedAabbMax[1]<endX)
    endX = quantizedAabbMax[1];
   if (quantizedAabbMin[2]>startJ)
    startJ = quantizedAabbMin[2];
   if (quantizedAabbMax[2]<endJ)
    endJ = quantizedAabbMax[2];
   break;
  }
 case 1:
  {
   if (quantizedAabbMin[0]>startX)
    startX = quantizedAabbMin[0];
   if (quantizedAabbMax[0]<endX)
    endX = quantizedAabbMax[0];
   if (quantizedAabbMin[2]>startJ)
    startJ = quantizedAabbMin[2];
   if (quantizedAabbMax[2]<endJ)
    endJ = quantizedAabbMax[2];
   break;
  };
 case 2:
  {
   if (quantizedAabbMin[0]>startX)
    startX = quantizedAabbMin[0];
   if (quantizedAabbMax[0]<endX)
    endX = quantizedAabbMax[0];
   if (quantizedAabbMin[1]>startJ)
    startJ = quantizedAabbMin[1];
   if (quantizedAabbMax[1]<endJ)
    endJ = quantizedAabbMax[1];
   break;
  }
 default:
  {
   //need to get valid m_upAxis
   btAssert(0);
  }
 }

 
  

 for(int j=startJ; j<endJ; j++)
 {
  for(int x=startX; x<endX; x++)
  {
   btVector3 vertices[3];
   if (m_flipQuadEdges || (m_useDiamondSubdivision && !((j+x) & 1))|| (m_useZigzagSubdivision  && !(j & 1)))
   {
        //first triangle
        getVertex(x,j,vertices[0]);
        getVertex(x+1,j,vertices[1]);
        getVertex(x+1,j+1,vertices[2]);
        callback->processTriangle(vertices,x,j);
        //second triangle
      //  getVertex(x,j,vertices[0]);//already got this vertex before, thanks to Danny Chapman
        getVertex(x+1,j+1,vertices[1]);
        getVertex(x,j+1,vertices[2]);
        callback->processTriangle(vertices,x,j);    
   } else
   {
        //first triangle
        getVertex(x,j,vertices[0]);
        getVertex(x,j+1,vertices[1]);
        getVertex(x+1,j,vertices[2]);
        callback->processTriangle(vertices,x,j);
        //second triangle
        getVertex(x+1,j,vertices[0]);
        //getVertex(x,j+1,vertices[1]);
        getVertex(x+1,j+1,vertices[2]);
        callback->processTriangle(vertices,x,j);
   }
  }
 }

 

}

이것도 어려울 수 있겠지만, 요점은 다음과 같다. 현재 충돌 가능성이 있는 어떤 Dynamic Object의 AABB를 Terrain AABB의 Local Coordinate로 바꾼 후에, 어떤 Grid Vertex 쯤에 있는지를 확인한다. 이것이 아마 Quantize 부분에서 실행되는 것 같다.

그리고 나서, 그 어디쯤에 있는지 확인한 정보를 가지고, 삼각형 정점을 구한 다.

그래서 세개의 정점들이 구해지면, processTriangle 콜백함수를 실행시켜서, 먼저 EarlyExit으로 AABB와 Triangle의 테스트를 해준다.

Early Exit을 통과해서 이제 제대로 해야 한다면 Convex와 Convex의 충돌탐지의 경우 Bullet Physics에서는 GJK 함수를 이용하여 충돌탐지 작업을 해주고 있다.

그래서 Contact manipold를 형성해주고, 그것을 constraint solver에 보내서 해결하는 것 같다.

그래서 정리하자면 다음과 같은 프로세스로 Terrain Physics를 처리하고 있다:

1. Init : 전체 Terrain에 대해 Local AABB min, max를 구해서 BroadPhase에 넣기

2. Collision Detection
1) Broad Phase
Terrain AABB 안에 있으면 모두 검사 해봐야할 것이기 때문에, Overlapped Pair로 보낸다.

2) Narrow Phase
Dynamic Object의 AABB를 Terrain Local AABB 좌표에 맞추어 좌표변환을 해주고, Grid의 어디에 있는지 확인한 후, 정점 번호들을 구한다. 그리고 해당 삼각형들을 구해서

- 삼각형과 AABB Early Exit

만약 Early Exit을 통과했다면

- GJK알고리즘을 이용한 Convex Vs Convex 알고리즘

3. Solve the constraints

그래서 결과는 이렇게 된다.

그렇다면 내가 해야할 일은 다음과 같이 된다.

1. Terrain AABB min max 작업
2. Narrow Phase에서 AABB vs Triangle 구현
3. Narrow Phase에서 OBB vs Triangle, Sphere vs Triangle

그런데 가장 중요한 것은
Broad Phase에서 얻은게 이제 Narrow Phase로 갈 때, 삼각형을 Quantize해서, 해당 Grid의 삼각형들을 구하는 것인데, 이것은 어떻게 할지 많이 고민해서 최적화를 많이 하도록 해야겠다.

어쨋든 정리 되었으니 이렇게 구현을 해보도록 한다!
시간:
라벨:

댓글 없음:

댓글 쓰기

피드 구독하기: 댓글 (Atom)