sjo200 - CS 대학원 수업 정리 블로그

index buffer object를 그리기 위해 glDrawElements를 찾다가 stackoverflow에 좋은 글이 있었다.

stackoverflow.com/a/2949191 (Creative Commons BY-SA, Jonathan Hartley)

glDrawElements를 사용해보기 위해 아래 코드로 ㄷ자 모양을 그려보았다.(빈 공간이 -z 방향을 향하도록)

#include  

GLfloat vertex[] = { 
    0.0, 0.0, 0.0, 
    1.0, 0.0, 0.0, 
    1.0, 1.0, 0.0, 
    0.0, 1.0, 0.0, 
    0.0, 0.0, 1.0, 
    1.0, 0.0, 1.0, 
    1.0, 1.0, 1.0, 
    0.0, 1.0, 1.0 
}; 

GLfloat color[] = { 
    0.3f, 0.4f, 0.2f, 
    0.3f, 0.4f, 0.2f, 
    0.3f, 0.4f, 0.2f, 
    0.3f, 0.4f, 0.2f, 
    0.3f, 0.4f, 0.2f, 
    0.3f, 0.4f, 0.2f, 
    0.3f, 0.4f, 0.2f, 
    0.3f, 0.4f, 0.2f 
}; 

GLfloat normal[] = { 
    -1, 0, 0, 
    1, 0, 0, 
    0, 0, -1 
}; 

GLubyte index[] = { 
    0, 4, 7, 3, 
    1, 2, 6, 5, 
    4, 5, 6, 7 
}; 

void displayAxis(float t) { 
    glBegin(GL_LINE_LOOP); 
    glColor3f(t, 0.0, 0.0); 
    glVertex3f(0.0, 0.0, 0.0); 
    glVertex3f(t, 0.0, 0.0); 
    glEnd(); 
    glBegin(GL_LINE_LOOP); 
    glColor3f(0.0, t, 0.0); 
    glVertex3f(0.0, 0.0, 0.0); 
    glVertex3f(0.0, t, 0.0); 
    glEnd(); 
    glBegin(GL_LINE_LOOP); 
    glColor3f(0.0, 0.0, t); 
    glVertex3f(0.0, 0.0, 0.0); 
    glVertex3f(0.0, 0.0, t); 
    glEnd(); 
} 
void displayFaces() { 
    glEnableClientState(GL_VERTEX_ARRAY); 
    glEnableClientState(GL_COLOR_ARRAY); 
    glVertexPointer(3, GL_FLOAT, 0, vertex); 
    glColorPointer(3, GL_FLOAT, 0, color); 
    glNormalPointer(3, 0, normal); 
    glDrawElements(GL_POLYGON, 4, GL_UNSIGNED_BYTE, index); 
    glDrawElements(GL_POLYGON, 4, GL_UNSIGNED_BYTE, &index[4]); 
    glDrawElements(GL_POLYGON, 4, GL_UNSIGNED_BYTE, &index[8]); 
    glDrawElements(GL_POLYGON, 4, GL_UNSIGNED_BYTE, &index[12]); 
} 
void display(void) 
{ 
    glMatrixMode(GL_MODELVIEW); 
    glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT); 
    glLineWidth(2.0); 

    glPushMatrix(); 

    gluLookAt(5.0, 5.0, 5.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0); 

    displayAxis(5.0); 
    displayFaces(); 

    glPopMatrix(); 
    glFlush(); 
} 

void reshape(int x, int y) 
{ 
    glViewport(0, 0, x, y); 
    glMatrixMode(GL_PROJECTION); 
    glLoadIdentity(); 
    gluPerspective(100.0, (GLdouble)x / (GLdouble)y, 5.0, 30.0); 
} 

void idle(void) 
{ 
    display(); 
} 

int main(int argc, char** argv) 
{ 
    glutInit(&argc, argv); 
    glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB); 
    glutInitWindowSize(800, 600); 
    glutCreateWindow("opengl"); 

    glutDisplayFunc(display); 
    glutReshapeFunc(reshape); 
    glutIdleFunc(idle); 
    glutMainLoop(); 
    return 0; 
}

 - 여러 가지 C.D. 논문을 구현한 사이트

http://gamma.cs.unc.edu/research/collision/packages.html

 - 그 중 가장 많이 쓰이고 비교적 매우 빠른 library인 PQP

http://gamma.cs.unc.edu/SSV/

 첨언하자면, 어차피 이런거 안봐도 유니티 같은 플랫폼에서 최단거리, 충돌여부 이런거 다 캡슐화 해서 잘 되있을 것이다(플랫폼은 실제로 안써봄;). 따라서 학계에 관심 없다면 안봐도 된다(PQP 원리는 알고 쓰는걸 추천함). 어차피 실제 어플리케이션 구현 시 제약조건에 따라 BVH 잘 만들거나 PQP만 잘 써도 C.D.는 매우 빠르고 쉽게 된다. 논문에서 쓰이는 건 보통 특별한 케이스(많은 데이터 / 뭔가 아직 해결안된 컨벡스한 모양 등등...)이기 때문이다.

Real-time rendering 의 Chapter 16 내용이다. intersection test 코드는 책의 내용을 참고하도록 하자.

1. 개념

 polygon-polygon intersection test를 하려면 결국 triangle-triangle intersection test를 해야한다. 아니면 사용하는 BV에 따라 AABB, sphere, OBB, k-DOF 등 기본적 구조나 LSS(line swept sphere), TSS(Tetrahedron swept sphere) 등의 복잡한 구조끼리 intersection test를 해야한다(여기서 LSS, TSS는 다루지 않는다). 어떻게 두 BV 또는 triangle 간 intersection test 하는지 알아봐야 하는데, 수가 너무 많아서 Ray-Triangle intersection만 본다.

2. Ray-Triangle intersection

※ 변수가 bold 일 경우, vertex 이다.

 point t(u,v)가 triangle (1-u-v)v_0 + uv_1 + vv_2  에 있다고 하면, 

t(u,v)=(1-u-v)v_0 + uv_1 + vv_2 

으로 나타낼 수 있다(v = 실수, v = vertex of triangle). 그리고, 이 점 t 가 한 직선 위에 있다면 

o + td = (1-u-v)v_0 + uv_1 + vv_2 

와 같이 직선위의 점이자 삼각형 안의 점을 나타낼 수 있다.

선형대수학적으로 나타내면 

(^T를 사용해 column이 긴 행렬을 나타내었다)

[(-d) (v_1-v_0) (v_2-v_0)] * ([t u v]^T) = o - v_0

이고, Cramer's rule을 사용하면 determinant로 쉽게 구할 수 있다.

여기서 구한 u,v의 값이 [0,1]이 아니라던지, Cramer's rule에 사용되는 분모가 0인 경우를 reject 하고, 모두 통과하면 intersection을 반환한다.

3. 참고내용

Ray-Polygon intersection

Plane-Box intersection(AABB, OBB)

Triangle-Triangle intersection(ERIT's method)

Triangle-Box overlap

BV-BV intersection

View frustum intersection

Frustum-Box intersection

line-line intersection

위 intersection 방법 및 코드는 책의 내용을 참고하도록 한다. 그리고 CGAL에 이미 구현되있을 것이므로 알고싶다면 구글링하자.

1. 개념

 컴퓨터 그래픽스로 다양한 물체를 표현하면서, 충돌감지를 하기는 힘든 일이다. 스캔된 데이터가 크면 클수록(vertex 수가 많다거나..) 프로세싱 해야할 face 수도 자연히 늘어날 것이다. 단순하게 생각하면 N개의 vertex, M개의 vertex로 이루어진 두 objects를 collision detection 하는데 이를 단순히 학부 과정에서 생각하려면 힘들 것이다. 따라서 빠르고 정확하게 C.D. 하기위한 방법들을 소개한다. (3D 기준에서 모든 것을 설명할 것이다.)

2. BV

 Bounding Volume은 어떤 polygon으로 이루어진 물체를 포함하는 간단한 형태의 Volume이다. 예를 들어, 단순히 polygon-polygon 충돌감지를 하려면 매 timestep마다 triangle로 분해해서 서로 N*M번 체크하는 방법이 있는데, 멀리 떨어져있고 만날 확률이 적다면 sphere로 감싸서 sphere-sphere 충돌감지를 하는게 훨씬 쉬울 것이다. 왜냐하면 후자는 중심점에서의 거리만 알면 충돌했는지 알 수 있기 때문이다. 물론 엄밀히 알고리즘 상 최악의 시간을 줄이는 것은 아닐 것이다. 다만 대부분의 경우에서 줄여주기 때문에, 실용적인 방법이라고 할 수 있다.

3. BVH

 Bounding Volume Hierarchy는 물체가 여러개 있을때, 더 쉽고 빠르게 C.D. 할 수 있는 BV 여러개를 BV로 감싼 것을 말한다. BVH 간 C.D.는 따라서 여러번 이루어지는데, 이를 BVTT라 한다.

4. BVTT

 Bounding Volume Testing Tree는 'BV tree'(BVH라 생각하면 된다)간 C.D.하는 과정을 트리로 나타낸 것이다. 제일 큰 BV와 충돌했다면, 계속해서 그 밑의 BV로 내려가서 확인하는 것인데 일정 기준으로 두 BV 중 어떤 BV를 쪼개서 그 밑의 BV와 검사할 것인지 선택해야한다. BVTT는 실제로 구현할때 저장한다거나 하는건 아니고 추상적인 개념이다.

 testing시 front line을 저장하는 최적화 방법이 있는데, 이는 BVTT에서 충돌하기 직전의 node 위치를 모두 저장해서 다음 timestep에 충돌검사를 하면 그 위치부터 다시 검사하는 방법이다. 이 노드들의 위치를 front line이라 하여 라인으로 표현한다. 교과서에 소개된 한 논문은 front line을 사용할 때 다음 timestep마다 저장된 노드를 그들의 부모로 바꿔서 테스트 하면 가장 좋다고 한다. front line은 temporal coherence(잠깐동안 많이 움직이지 않았을 것이라는 특성)을 이용한 caching mechanism이다.

 만약 테스팅할게 많은데 timestep에 주어진 시간이 짧다면, 전체 BVTT 레벨의 루트부터 절반을 BFS로 탐색하고, 이후 C.D.된 노드들에 대해서만 DFS 하는 방법이 있다. 이렇게 한다면 충돌 가능성이 있는 부분이라도 대부분 알 수 있기에 사용된다고 한다. 아니면, 원래부터 충돌가능성이 높은 부분의 노드에 높은 priority를 주어 먼저 검사하기도 한다고 한다. 

5. Deformable model

 BV를 기껏 만들었는데, 물체의 모양이 바뀌어버리면 해당 물체의 BVH 모든 구성요소나 해당 물체에 대한 BV를 새로 만들어야한다. 때문에, OBB와 같이 만드는데 시간이 많이 걸리는 BV는 Deformable model에 적합하지 않다. AABB나 Bounding Sphere를 사용해서 빠르게 재구성해야한다.

 여기서도 짚고 넘어가야할 최적화 방법이 있는데, BVH에서 윗부분만을 재구성한다면 시간 절약을 할 수 있다. 아랫부분은 필요할때되서 만드는 방법인데, 이를 통해 굳이 충돌 안할, 재구성 안해도 되는 BV를 만들지 않고 넘어갈 수 있다. 여기서도 윗부분과 아랫부분은 이전 timestep의 BVH 레벨의 절반을 기준으로 나누는 것이 좋다고 한다. 

6. SAT (Separating Axis Theorem)

 어떤 두 convex 물체가 겹치는지 아닌지 확인하려면, 어떤 한 각도(∃angle)에서 바라봤을때(projection 했을 때) 분리되면 겹치지 않는다는 정리이다. 따라서 각진 BV(AABB, OBB 등)가 겹치는지 확인하려면, BV 간에 이룰 수 있는 모든 각도(OBB-OBB라면 한 OBB가 가지는 각 중 어떤 축과 다른 OBB가 가지는 각 중 어떤 축의 cross product로 projection해서 확인한다. 다음에 정확히 설명할 것임)들로 확인해서 분리되면 겹치지 않는 것이다.

BV 종류에 대한 설명은 아래 블로그를 참조하기 바란다.

AABB, Bounding Sphere, OBB, 2D GJK, Minkowski sum

https://m.blog.naver.com/PostView.nhn?blogId=wjdalsdl1016&logNo=220768308382&proxyReferer=https%3A%2F%2Fwww.google.co.kr%2F

3D GJK

https://hamaluik.com/posts/building-a-collision-engine-part-3-3d-gjk-collision-detection/

Applied Geometry for Computer Graphics and CAD 책의 챕터 2.7 "Point and line geometry in homogeneous coordinates" 내용이다. 영문 독해가 되면 가능한 구글링해서 원서 pdf로 보길 권한다.

1. 개념

 homogeneous coordinate를 알기 전에, 좌표의 변환에 대해 먼저 알아야한다. 좌표의 변환에는 세 가지가 있다.

 translation을 선형변환과 똑같은 프로세스(매트릭스 곱셈)로 처리하기 위해, point를 vector와 함께 처리하기 위해 geometry에서는 homogeneous coordinate를 사용하게 된다. homogeneous coordinate는 2차원 공간에서 3차원으로, 3차원 공간에서 4차원으로 좌표를 나타낸 것이다. 

------- 2차원

2. 점

 (x,y,w)로 점의 좌표를 나타내는데, w 항이 1로 되기 위해서는 모두 w로 나눠줘야 한다. 따라서 (x/w,y/w,1)로 공간상의 정확한 좌표를 얻어낸다. 하지만 계산상에서 w가 1 외의 값을 갖는건 허용된다.

3. 선

 선 또한 (x,y,w)로 나타낼 수 있다.  다만 geometry에서는 (a,b,c)로 대신하고, 이를 다음과 같이 식으로 나타낸다.

ax+by+c=0

4. 점 둘로 나타내지는 선

 점 두 개를 지나는 선은 다음과 같이 나타낸다. 

P_1, P_2에 대해, 선 L은

L=P_1×P_2

로 나타낼 수 있다.

L의 노말과 P_1, P_2를 각각 dot product하면 0이 되기 때문에 위와 같은 식을 유도할 수 있다.

<L,P_1>=0, <L,P_2>=0 이므로, L=P_1×P_2

5. 선 둘로 나타내지는 점

 선 두 개를 모두 교차하는 점은 다음과 같이 나타낸다.

L_1, L_2에 대해, 점 P는

P=L_1×L_2

이렇게 단순한 매트릭스의 곱으로 나타낼 수 있다.

------- 3차원

7. 점

 2차원에서 나타낸 바와 같이, (x,y,z,w)로 나타낸다.

8. 면

면 또한 (x,y,z,w)로 나타낼 수 있다.  다만 geometry에서는 (a,b,c,d)로 대신하고, 이를 다음과 같이 식으로 나타낸다.

ax+by+cz+d=0

9. 세 점으로 만드는 면

 다음과 같이 임의의 면에 세 점을 대입한다. 

위와 같이 wedge product로 유도할 수 있다. 이는 아래와 같다.

10. 세 면으로 만드는 점

 위 9번과 같이 wedge product를 하면 된다. 대신 P=n0⋀n1⋀n2 으로 구한다.

11. 투영

 2차원에서 나타낸 투영에 한 차원을 높혔다고 생각하면 된다. 결과 식도 비슷하다.

만약 parallel projection이라면, view V의 w에 1 대신 0을 넣으면 된다.