5.2 초기 3D 골격 다각형 생성
5.3.3 외곽선 중심점 계산
초기 3D 골격 다각형의 개선을 위해 우선적으로 유효한 교차 외곽선을 갖는 적합 노드 점을 해당 외곽선의 중심점으로 위치시키는 과정을 수행한다. 그림 32는 외곽선의 중심점을 계산하는 절차를 나타낸다.
그림 32. 외곽선 중심점 계산 절차
혈관의 외곽선은 평면-메쉬 간 교점들로 이루어진 다각형이다. 따라서, 외곽선이 볼록한 경우, 무게 중심(centroid)이 외곽선의 중심점이 되지만, 외곽선이 오목한 경우에는 무게중심이 외곽선 밖에 위치할 수 있으므로 별도의 중심점 계산이 요구된다. 노드 점 p에 대한 외곽선 C의 중심점 계산을 위해 먼저 외곽선 C에 대한 2D 다각형 C 을 구한다. 그림 33에서와 같이 외곽선을 구성하는 교점들 l q 을 벡터 i n 에 수직인 교차평면 f 상의 2D 점들
q
li로 변환한다. 노드 점 p에서 가장 먼 교점이qmax일 때, 점 p에서의 지역 좌표계 형성을 위한 좌표축 단위벡터는 식(5.4)와 같이 정의된다.
= z n
(
max)
max= -
-x q p q p
(5.4)= ´ y z x
z축은 벡터 n와 나란하고, xy축은 평면 f 위에 놓인다. 이를 통해 외곽선 C을
구성하는 교점 q 에 대한 지역 좌표계 상의 2D 점 i
q
li은 다음과 같이 구해진다.그림 33. 노드 점에 대한 지역 좌표계
그런 다음, 식(5.5) 의거하여 2D 다각형 C 의 무게중심 l cl=
( )
x ylc, cl 을 계산한다[48].1
1 1
0 1
1 1 1
0 1
1 1 1
0
1 ( )
2
1 ( )( )
6
1 ( )( )
6
n
i i i i
i l n
c i i i i i i
i l n
c i i i i i i
i
A x y x y
x x x x y x y
A
y y y x y x y
A
-+ +
=
-+ + +
=
-+ + +
=
=
-= +
-= +
-å å
å
(5.5)
다각형이 볼록(convex)이라면, 무게중심을 다각형 중심점 ml =
(
x yml, ml)
으로 삼는다.즉, ml=c 으로 한다. 다각형이 오목(concave)한 경우, 그림 34(a)에서와 같이 l 무게중심 c 이 다각형 내부에 있지 않을 수 있다. 이를 해결하기 위해 그림 l 34(b)에서와 같이 다각형에 대한 삼각형화 (triangulation)을 수행하여 다각형을 삼각형들로 분할한 후, 무게중심 c 에 근접한 삼각형 한 개를 선택하고, 해당 l 삼각형의 내부점(inner point)을 다각형 중심점 ml 으로 삼는다. 그리고 다각형 중심점 ml 에 대한 3차원 점 m p= +xlmx+ymly 을 외곽선 C의 중심점으로 삼는다.
다각형 삼각형화를 위해 제약된 Delaunay 삼각형화(constrained Delaunay Triangulation)을 채택하였다[49].
(a) 오목 다각형의 중심점 (b) 다각형의 삼각형화 그림 34. 오목 다각형에 대한 중심점 계산 및 삼각형과 결과
제약된 Delaunay 삼각형화는 평면 위의 점들을 삼각형으로 분할했을 때, 모든 내각의 합이 최소가 되도록 하는 분할 방식으로 세 점의 외접원을 이용하는데, 해당 삼각형의 세 정점으로 이루어진 외접원이 다른 삼각형의 정점을 포함하지 않는 것을 원칙으로 한다. 삼각형화 과정은 다음과 같다.
(1) 임의의 점을 기준으로 최소 길이를 지닌 변(edge) 하나를 찾아, 후보 변 집합(CE)에 저장한다.
(2) 저장된 새로운 변을 선택한다. 새로운 변이 없다면 절차를 끝낸다.
(3) 선택된 변의 정점들과 반시계 방향을 만족하는 정점 하나를 선택하여 임의의 삼각형을 생성한 다음, 외접원을 구한다.
(4) 반시계 방향을 만족하는 다른 점이 원 속에 포함되는지 검사하고, 포함된다면 다른 정점에 대해 (3)로 돌아가 반복한다.
(5) 포함되지 않는 다면, 생성된 삼각형의 변을 CE에 저장하고, (2)로 돌아가 반복한다.
Delaunay 삼각형화를 통해 분할된 삼각형들을 이용하여 무게중심이 다각형의 내부 또는 외부에 있는지, 그리고 특정 삼각형의 내부 또는 모서리 위에 있거나 꼭지점과 일치하는지를 알 수 있다. 무게중심이 특정 삼각형 내부에 존재하는 경우, 해당 삼각형이 선택된다. 무게 중심이 다각형 외부에 있거나, 삼각형의 모서리 위 또는 꼭지점에 위치할 경우, 무게중심에 가장 가까운 삼각형이 선택된다. 무게중심과 삼각형 간의 거리는 무게중심과 삼각형 꼭지점들 간의 평균거리로 정의된다.
본 장에서는 선택된 삼각형의 내부점 계산을 위해 그림 35에서와 같이 삼각형의 이웃 관계를 고려한 이원적 계산 방식을 도입하였다.
(a) 인접 삼각형이 2개인 경우
(b) 인접 삼각형이 3개인 경우 그림 35. 선택된 삼각형 내부점 계산
그림 35(a)에서와 같이 선택된 삼각형과 인접한 이웃 삼각형들이 2개인 경우, 인접 삼각형이 존재하지 않은 모서리의 중심
(
12(
q2l +q3l) ) 과 모서리를 마주보는 꼭지점
( )
q1l 을 잇는 선분의 중심(
12 1 14 2 14 3)
l = l + l + l
m q q q 을 해당 삼각형의 내부점으로 정한다.
그림 35(b)에서와 같이 선택된 삼각형과 인접한 삼각형들이 3개 인 경우, 삼각형의 모서리 길이를 고려하여 꼭지점에서의 가중치를 산정하고, 식(5.6)과 같이 세 꼭지점의 가중치 합으로 삼각형의 내부점을 정한다.
1 1 2 2 1 3 l
= w
l+ w
l+ w
lm q q q
( )
( )
( )
1 12 1 1 2 3
2 12 2 1 2 3
3 12 3 1 2 3
1 / ( )
1 / ( )
1 / ( )
w l l l l
w l l l l
w l l l l
= - + +
= - + +
= - + +
(5.6)
그림 36(a)는 그림 34의 오목 다각형에 대한 중심점 계산 결과로서 그림 34(a)의 삼각형 내부 점 계산 방식이 적용된 결과를 나타내며, 그림 36(b)와 (c)는 그림 35(a)와 (b)의 삼각형 내부 점 계산 방식의 적용 예를 각각 나타낸다.
(a) 그림 33에 대한 다각형 중심점 계산 결과
(b) 인접 삼각형이 2개인 경우 (c) 인접 삼각형이 3개인 경우 그림 36. 선택된 삼각형의 내부점 계산 예제
외곽선 중심점 계산에 의한 노드 점 개선은 유효한 외곽선을 갖는 적합 노드 점에 한해서만 수행되며, 그림 37은 외곽선 중심점 계산 방안을 적용한 결과로 그림 36(a)는 외곽선 중심점 계산 전의 적합 노드 점들을 나타내며, 그림 36(b)는 계산 후 개선된 적합 노드 점들을 나타낸다.
(a) 초기 적합 노드 점 (b) 개선된 노드 점 그림 37. 적합 노드에 대한 개선 결과