블로그 이미지
앨리삵

앨리삵입니다.

Rss feed Tistory
Coding Note 2013.10.23 18:57

A point within the tetrahedron

출처 : http://steve.hollasch.net/cgindex/geometry/ptintet.html

 

어떤 포인트가 tetrahedron(사면체)안에 있는지 확인하는 방법.

사면체를 이루는 정점 v1, v2, v3, v4과 입력된 포인트 v에 대해서 적절하게 4x4 determinant(행렬식)들을 구해 그 관계를 따져보면 된다.

 

4개의 정점에 대해서 행렬식은 세개의 정점이 이루는 평면을 기준으로 네 번째 점이 평면의 위에있는지, 아래에있는지, 동일평면상(coplanar)인지를 판단하는 잦대가 된다. 예를들어 네개의 정점에 대한 다음 행렬식은,

 

 

V0, V1, V2가 이루는 CCW(Counter-Clock Wise) front face 평면에 대하여 V3의 위치가 행렬식의 값이 음수라면 앞면, 양수라면 뒷면, 0이라면 동일평면상에 존재한다는것을 나타낸다.

(평면을 형성할 기준정점을 무엇으로 선택하냐에 따라 행렬식에 의한 앞, 뒤 위치판단은 달라질 수 있다. 예로 V1, V2, V3을 기준평면 정점으로 잡는다면 행렬식의 값이 양수일때 앞면, 음수일때 뒷면, 0일때 동일평면상을 나타낸다.)

이러한 사실을 바탕으로 5개의 정점(사면체 4개의 정점 + 테스트할 입력정점)에서 나올 수 있는 4가지 정점의 모든 조합에 대한 행렬식들을 구하며 이들의 관계에 따라 입력된 정점이 사면체와 어떤 위치관계를 갖는지를 파악하게된다.

( 행렬식 구하는 방법이 궁금한사람은 바로 전 포스트를 보면 된다. http://alleysark.tistory.com/entry/matrix-determinant  )

 

5가지 행렬식은 아래와 같다.

 

 

D0 == 0 이라면 사면체를 이루는 네 정점은 동일평면상(coplanar)에 존재하는것이다.

Di == 0 이라면 입력정점 V는 V와 Vi를 제외한 세 정점이 이루는 평면과 동일한 평면상에 존재한다.

  동일평면상에 존재하는 경우라면 세 점이 이루는 삼각형의 밖에있는지, 안에있는지, 모서리에 존재하는지 다시 확인해줘야한다.

  3차원 공간에서 삼각형과 포인트의 위치관계는 노말벡터를 이용했다 (행렬식을 이용할수있지 않을까..?)

어떤 Di 중 하나라도 D0와 부호가 다르면 V는 사면체 밖에 존재한다.

모든 Di 와 D0의 부호가 같다면 V는 사면체 않에 존재한다.

 

구현이야 별건 없지만..  일단은 이런식으로 사용하면 된다.

 

더보기

저작자 표시 비영리 변경 금지
신고

'Coding Note' 카테고리의 다른 글

간단한 epoll thread-pooling server  (0) 2014.01.06
Tetrahedron circumsphere from 4 points  (0) 2013.10.28
A point within the tetrahedron  (0) 2013.10.23
matrix determinant  (0) 2013.10.23
[C++] virtual inheritance  (0) 2013.06.29
[Design pattern] 디자인 패턴이란  (6) 2013.03.28
TOTAL 297,534 TODAY 41

티스토리 툴바