삼각형 - 평면 충돌

프로그래밍 2007. 11. 20. 22:31
며칠간 3차원 벡터로 정의되는 세 정점으로 이루어진 삼각형과 임의의 평면과의 교점들을 찾기 위해 고군분투하고 있었습니다. (삼각형-평면 충돌) 평면과 각각 정점과의 거리를 구한 값들(각 정점에 해당하는 세 개의 값)의 부호를 검사하는 것은,

#define ISALLSAMESIGN(x, y, z) ( ((x > 0) == (y > 0)) && ((y > 0) == (z > 0)) )

과 같은 식으로 처리할 수 있었는데, 이것만으로는 어떤 정점이 평면의 다른 방향에 존재하는지(세 값 중에 어떤 값이 나머지 두 값과 다른 부호를 가지고 있는지) 알 수가 없더라구요. 흑흑.

그래서 과연 어떤 값이 혼자 튀는지 검사할 수 있는 방법을 몇가지 생각해봤습니다. 매크로로 나타낼 수 있을 정도로 간단하면 좋을텐데. a, b, c를 넣으면 결과값으로 n번째 수가 부호가 다르다고 말해줄 수 있는 그런 놈이요. 일단 간단하게 생각해서 세 값의 부호를 각각 0과의 비교를 통해서 boolean으로 나타낼 수 있다고 생각했습니다. 그리고 세 개의 boolean 을 나열하면 3bit의 정수(0 ~ 7)로 나타낼 수 있겠죠.
세 부호가 같은지 판별하기 위해서는 이 결과값이 111(7)이나 000(0)인 경우만 추려내면 될 겁니다. ( result%7 == 0 ) 하지만 문제는 그 반대에서 조금 더 뻗어나가죠. 세 개의 bit 중에서 다른 두 bit 와 다른 bit 의 서수(ordinal)을 알아내야 합니다. 어쩌죠? (….)

#define WHOISTHECRIMINAL(a, b, c) ( (a*b < 0) + (b*c < 0)*2 + (c*a < 0)*4 )

생각한 방법은 결과값 3bit 를 가지고 0과 7과의 비트연산을 통해서 2bit의 값(0, 1, 2)을 얻어 그것을 서수로 사용하는 것이었습니다. 이것 역시 비교문을 쓰지 않기 위해서 생각해 낸 방법입니다. 하지만 대체 어떻게 연산해야 001 ~ 110 의 값을 차례대로 서수로(그것도 순차적인 서수가 아닌 0, 1, 2, 2, 1, 0 의 순으로) 바꿀 수 있는 걸까요? 적잖이 생각해보았지만 이건 좀 어려울 것 같습니다.

그런데 문제는 이거죠. 구현도 중요하지만 성능도 중요한 게 문제죠. CPU 비용이 얼마나 작은지. 결과값의 신뢰도가 어느정도인지. 고심(하면서 딴짓)하던 끝에 ary[] = { 0, 1, 2, 2, 1, 0 } 으로 배열을 선언하고 위의 결과값을 배열의 첨자로 사용하는 방법으로 결정했습니다. 제가 만들고 있는 프로그램은 데스크탑에서 실행될 거고, 메쉬의 모든 삼각형에 대해서 행해질 연산이니까요. 네.


: