<제목 차례>
I. Introduction
1. Program
2. Condtions
2. Programming
1. Background
2. Input & Output
3. Procedure
3. Result
<수식 차례>
수식 1 교점에서의 t 값 산출
수식 2 다른 기저를 이용한 벡터의 표현
<그림 차례>
그림 1 버블 정렬 예시
그림 2 ~ 5 Input & Output
그림 6 Point, Triangle, Tetra 클래스 코드
그림 7 ~ 8 Projection 클래스 코드
그림 9 ~ 16 Main 함수 코드
그림 17 모서리만 그려진 사면체
그림 18 면이 칠해진 사면체
I. Introduction
1. Problem
① Viewport에서 3D object를 봤을 때, viewing plane에 투영되는 점들을 구하고 이를 postscript 파일로 출력하여라. 단, 색은 칠하지 않고 선만으로 표현하라.
② 사면체의 각 면에 색을 칠하여 실제 viewport에서 어떻게 보이는지 postscript 파일로 출력하라. 단 칠하는 순서를 결정하는데 사용하는 sorting algorithm은 직접 작성하고 어떤 알고리즘을 썼는지 서술하라.
2. Conditions
다음의 단계를 따라 프로그래밍을 수행하여라.
(1) 3D object인 사면체를 클래스로 정의하고 내부에 Point, Face 정보는 “tetra.txt” 안에 저장되어 있다.
3D object를 투영할 평면에 대한 정보와 viewport의 위치를 정해야 하며, 투영할 평면 위에서 local coordinate로 바꿔줘야 하므로 평면 위의 벡터가 하나 필요하다. 이에 대한 정보는 “projection.txt”에 저장되어 있으며 다음과 같다. 두 파일을 읽어 projection을 수행한다.
(2) Viewing plane 위에 3d object가 투영된 뒤, global coordinate에서 평면 상의 local coordinate으로 변환해야 한다. Local coordinate로 변환할 경우, 평면 상의 두 벡터가 필요한데 하나는 “projection.txt”의 vector of plane을 사용하며, 다른 하나는 앞의 vector와 평면의 normal vector를 외적(cross product)하여 구한다. 두 벡터를 이용하여 투영된 점들을 global coordinate에서 local coordinate으로 변환한다.
(3) 앞의 단계에서 변환한 점들을 postscript 파일 내에 작성한다. postscript 작성 양식은 다음과 같다. Postscript 실행 시 크기가 너무 작아 알아보기가 힘든 경우 scale을 조정하여(min-max box 사용) 확대하여 그린다.
II. Programming
1. Background
① 먼저, 3D object의 point들을 추출하며, point가 주어져 있으므로 생략한다. 먼저, 하나의 point에 대해 projection하는데 다음의 수식을 이용한다.
normal vector : 
, point of plane : 
, viewport : 
, point of 3D object : 
라고 놓으면,
평면의 방정식 : 
직선의 방정식 : 
위를 정리하면,
수식 1 교점에서의 t 값 산출
이때, 이 t의 값을 직선의 방정식에 대입하면 평면과 직선 사이의 교점을 구할 수 있게 된다.
② 어떤 평면 위의 두 단위벡터 
와 
를 기저로 하여 평면 위의 다른 어떤 벡터를 나타내고자 한다. 그 벡터를 
라고 하면, 다음과 같이 나타낼 수 있다.
수식 2 다른 기저를 이용한 벡터의 표현
③ 버블 정렬은 바로 인접해 있는 두 개의 원소를 비교하여 순서가 바뀌어 있으면 서로 위치를 맞바꾸는 작업을 계속하며 순서를 맞추어 가는 것이다. 이때 한 번 작업하는 것을 Pass라고 하는데, 다음 Pass에서는 마지막 순서의 원소는 그대로 둔 채 Pass 작업을 진행하며 정렬이 끝날 때까지 계속 정렬한다. 여기서는 값이 큰 원소가 먼저 오도록 정렬할 것이다.
그림 1 버블 정렬 예시 (출처는 그림에 표기됨)
2. Input & Output
그림 2 프로그램 전체의 Input과 Output
위의 Conditions에서 서술했듯이, tetra.txt에서 점과 평면의 정보를 얻어내고, 이 정보를 토대로 viewport에서 사면체를 투영한 모습을 postscript로 내보내는데, output1.ps에는 면이 색칠되지 않고 선만 출력되어 나오고, output.ps에는 면이 색칠된 상태로 나온다.
그림 3 Projection 클래스 내 crossPoint 함수의 Input과 Output
주어진 점 point와 viewpoint를 잇는 직선과 projection plane 사이의 교점, Point 형태의 cp를 리턴 값으로 내보낸다.
그림 4 Projection 클래스 내 convertToLocal 함수의 Input과 Output
이 함수는 crossPoint으로 계산해낸 교점을 Input으로 받아 결과를 산출해내는 함수인데, projection plane 위의 벡터 vectorplane을 기저의 하나로 두고, vectorplane과 normal 벡터의 외적 벡터를 또다른 기저로 둘 때 교점이 어떻게 표현되는지를 반환하는 함수이다. 로컬 좌표계로 나타내는 함수인 것이다. 이때 그 좌표계의 원점은 Input으로 받은 middle이 되는데, 이 프로그램에서 middle은 모든 교점의 평균점이 된다.
그림 5 Projection 클래스 내 distant 함수의 Input과 Output
이 함수는 3차원 점을 Input으로 받은 뒤, viewport와 그 점 사이의 거리를 구하여 그 값을 d로 리턴하는 함수이다.
3. Procedure
이 코드 내에서 정의된 클래스는 Point, Triangle, Tetra, 그리고 Projection이 있다. 다음은 앞의 셋에 대한 정의를 내리는 코드이다.
class Point
{
public double x, y, z;
public Point() { }
public Point(double a, double b, double c)
{
x = a;
y = b;
z = c;
}
}
class Triangle
{
public int x1, x2, x3;
public Triangle(int a, int b, int c)
{
x1 = a;
x2 = b;
x3 = c;
}
}
class Tetra
{
public
List<Triangle> list = new List<Triangle>();
public Tetra(List<Triangle>
lists)
{
list = lists;
}
}
그림 6 Point, Triangle, Tetra
Point는 3차원 점을 나타내는 클래스이며, x는 점의 x좌표, y는 점의 y좌표, z는 점의 z좌표를 가지게 된다. Triangle은 점들의 리스트에서 인덱스(번호)만을 가져와서 삼각형을 만들어내는 클래스이며, x1과 x2, x3는 삼각형을 구성하는 점들이 리스트에서 어떤 번호를 가지고 있는지 나타내는 값이 된다. Tetra는 이 삼각형의 리스트들을 Input으로 받아 가지는 역할을 한다.
Projection 클래스로 넘어가서 살펴 보면 다음과 같다.
public double[] viewport = new double[3];
public double[] normal = new double[3];
public double[] pv = new double[3];
public double[] vectorplane = new double[3];
public Projection() { }
public Point
crossPoint(Point point)
{
double t = ((normal[0] *
(pv[0] - viewport[0])) + (normal[1] * (pv[1] - viewport[1])) + (normal[2] *
(pv[2] - viewport[2]))) / ((normal[0] * (point.x - viewport[0])) + (normal[1] *
(point.y - viewport[1])) + (normal[2] * (point.z - viewport[2])));
Point cp = new Point(viewport[0] +
t * (point.x - viewport[0]), viewport[1] + t * (point.y - viewport[1]),
viewport[2] + t * (point.z - viewport[2]));
return cp;
}
그림 7 Projection 클래스 코드 1
viewport는 말 그대로 viewport의 좌표를 가지며, normal은 Projection Plane의 법선 벡터를 나타내고, pv는 projection plane이 지나는 점의 좌표, vectorplane은 후에 기저로 쓰일 projection plane 위의 벡터를 나타낸다.
그리고 crossPoint는 상술했듯이 평면과 직선 사이의 교점을 구하는 함수인데, 수식 1을 그대로 이용하여 계산한 뒤, 그 결과를 Point cp로 내보내는 형태를 띠고 있다.
public Point
convertToLocal(Point point, Point middle)
{
Point rp = new Point(point.x -
middle.x, point.y - middle.y, point.z - middle.z);
double[] i = { normal[1] *
vectorplane[2] - normal[2]*vectorplane[1], normal[2]*vectorplane[0] -
normal[0]*vectorplane[2],normal[0]*vectorplane[1]-normal[1]*vectorplane[0] };
double ilength =
Math.Sqrt(Math.Pow(i[0], 2) + Math.Pow(i[1], 2) + Math.Pow(i[2], 2));
i[0] = i[0] / ilength;
i[1] = i[1] / ilength;
i[2] = i[2] / ilength;
double jlength =
Math.Sqrt(Math.Pow(vectorplane[0], 2) + Math.Pow(vectorplane[1], 2) +
Math.Pow(vectorplane[2], 2));
double[] j = {
vectorplane[0] / jlength, vectorplane[1] / jlength, vectorplane[2] / jlength };
Point lp = new Point();
lp.x = (rp.x * i[0]) + (rp.y *
i[1]) + (rp.z * i[2]);
lp.y = (rp.x * j[0]) + (rp.y *
j[1]) + (rp.z * j[2]);
lp.z = 0;
return lp;
}
public double distant(Point
point)
{
double d =
Math.Sqrt(Math.Pow(point.x - viewport[0], 2) + Math.Pow(point.y - viewport[1],
2) + Math.Pow(point.z - viewport[2], 2));
return d;
}
그림 8 Projection 클래스 코드 2
convertToLocal 함수는 Point rp를 가장 먼저 선언하는데, 이 점은 middle 점에 대한 point 점의 상대적 위치를 나타낸다. 그리고 double 배열 i를 선언해서, normal 벡터와 vectorplane, 즉 projection plane 위의 벡터의 외적을 i에 저장한다. ilength라는 변수를 새로 선언하여 벡터 i의 크기를 저장하고, 벡터 i를 ilength로 나눔으로써 i에는 단위벡터가 저장되도록 만들어준다. 그 뒤, jlength라는 변수를 선언하여 이 변수에 vectorplane의 크기를 저장한다. double 배열 j를 이번엔 선언하고, j에는 vectorplane을 jlength로 나눈 단위벡터가 저장되도록 한다. 그리고 수식 2를 이용하여 변환시킨 점을 점 lp에 저장한 뒤, 이를 리턴값으로 넘겨준다.
distant 함수는 viewport와 point 사이의 distance를 계산하는 함수로, 그 거리 값을 double 형 변수 d에 저장하여 리턴한다.
static void Main(string[] args)
{
List<Point> points = new
List<Point>();
List<Triangle> triangles = new
List<Triangle>();
Projection projection = new Projection();
List<Point> cpoints = new
List<Point>();
List<Point> lpoints = new
List<Point>();
Point middle = new Point();
int[] pointid;
double[] pointdist;
int[] faceid;
그림 9 Main 함수 코드 1
Program 클래스의 Main 함수로 넘어오면, 점들의 좌표 리스트인 points, 삼각형, 또는 Face를 이루는 점들의 리스트 번호를 모아 놓는 리스트인 triangles, 그리고 선언된 projection이 있다. 그리고 viewport와 3차원 점을 잇는 선분과 projection plane의 교점 좌표를 저장하는 리스트 cpoints, 이를 로컬 좌표계로 변환하여 그 좌표를 저장하는 lpoints, cpoints에 저장된 교점들의 평균점 middle, viewport와 points에 저장된 점 사이의 거리를 저장하는 pointdist 배열, points에 저장된 점들이 viewport로부터 얼마나 가까운지 0위부터 순위를 매겨 저장하는 pointid 배열, projection.list에 저장된 삼각형들이 viewport로부터 얼마나 먼지 지표를 저장하는 faceid 배열이 있다.
StreamReader sr = new StreamReader("tetra.txt");
int mode = 1;
while(!sr.EndOfStream)
{
string temp =
sr.ReadLine();
string[] tempArr;
if(temp == "//Point")
{
mode = 1;
}
else if(temp == "//Face")
{
mode = 2;
}
else
{
if(mode == 1)
{
tempArr = temp.Split(' ');
double[] numArr1 = new double[tempArr.Length];
for(int i = 0; i <
numArr1.Length; i++)
{
numArr1[i] =
Convert.ToDouble(tempArr[i]);
}
Point pt = new Point(numArr1[0],
numArr1[1], numArr1[2]);
points.Add(pt);
}
else if(mode == 2)
{
tempArr = temp.Split(' ');
int[] numArr2 = new int[tempArr.Length];
for (int i = 0; i <
numArr2.Length; i++)
{
numArr2[i] =
Convert.ToInt32(tempArr[i]);
}
Triangle tri = new
Triangle(numArr2[0], numArr2[1], numArr2[2]);
triangles.Add(tri);
}
}
}
sr.Close();
그림 10 Main 함수 코드 2
StreamReader sr을 선언해서 tetra.txt를 읽도록 한다. 그리고 int 형 변수 mode를 선언하는데, 이는 sr이 읽을 숫자 배열이 점의 좌표를 의미하는지, 또는 평면을 이루는 점의 인덱스를 의미하는지 알려주는 역할을 하게 된다. 우선 줄을 읽고, 그 줄이 “//Points”면 mode를 1, “//Face”면 mode를 2로 바꾸고, 그 둘도 아닌 다른 것이면 mode에 맞게 줄을 읽어 double 배열 형식으로 변환시킨 뒤 점 또는 삼각형을 만들어 이를 맞는 리스트 points 또는 triangles에 저장하게 된다. tetra.txt를 마지막 줄까지 읽은 뒤에는 while문이 끝나면서 이를 읽는 작업도 끝나게 된다.
Tetra tetra = new Tetra(triangles);
StreamReader sr2 = new StreamReader("projection.txt");
sr2.ReadLine();
sr2.ReadLine();
sr2.ReadLine();
sr2.ReadLine();
string temp1;
string[] tempArr1;
temp1 = sr2.ReadLine();
tempArr1 = temp1.Split(' ');
double[] numArr3 = new double[tempArr1.Length];
for (int i = 0; i <
numArr3.Length; i++)
{
numArr3[i] =
Convert.ToInt32(tempArr1[i]);
projection.viewport[i] = numArr3[i];
}
temp1 = sr2.ReadLine();
tempArr1 = temp1.Split(' ');
for (int i = 0; i <
numArr3.Length; i++)
{
numArr3[i] = Convert.ToInt32(tempArr1[i]);
projection.normal[i] =
numArr3[i];
}
temp1 = sr2.ReadLine();
tempArr1 = temp1.Split(' ');
for (int i = 0; i <
numArr3.Length; i++)
{
numArr3[i] = Convert.ToInt32(tempArr1[i]);
projection.pv[i] = numArr3[i];
}
temp1 = sr2.ReadLine();
tempArr1 = temp1.Split(' ');
for (int i = 0; i <
numArr3.Length; i++)
{
numArr3[i] = Convert.ToInt32(tempArr1[i]);
projection.vectorplane[i] =
numArr3[i];
}
그림 11 Main 함수 코드 3
Tetra를 선언해서 위에서 만든 triangles 리스트를 그대로 건네 주면서 코드가 시작된다. 그 뒤에는 StreamReader sr2가 하나 더 생성되는데, 이는 projection.txt를 읽게 된다. txt 윗부분에 있는 주석 부분을 전부 읽어버리고, 차례차례 읽어 나가며 읽은 줄을 temp에 저장하고, tempArr에 temp를 공백에 따라 나눈 배열을 저장한 뒤, tempArr을 수 형식으로 변환시켜 projection의 각 특성에 저장한다.
for(int i = 0; i <
points.Count; i++)
{
cpoints.Add(projection.crossPoint(points[i]));
}
double sum = 0;
for(int i = 0; i <
cpoints.Count; i++)
{
sum += cpoints[i].x;
}
middle.x = sum / cpoints.Count;
sum = 0;
for (int i = 0; i <
cpoints.Count; i++)
{
sum += cpoints[i].y;
}
middle.y = sum / cpoints.Count;
sum = 0;
for (int i = 0; i <
cpoints.Count; i++)
{
sum += cpoints[i].z;
}
middle.z = sum / cpoints.Count;
그림 12 Main 함수 코드 4
projection의 crossPoint 함수를 이용해서 points의 점과 viewport를 잇는 선분과 projection plane 사이의 교점을 구한 뒤 그 교점을 cpoints에 차례차례 추가한다. 그리고 cpoints에 등재된 점들의 평균점을 구해서 middle에 저장하도록 하는데, 그 과정은 다음과 같다. 우선 sum이라는 변수를 정의하고, sum = 0으로 초기화 시킨 뒤, points에 등재된 점들의 x좌표를 for문을 이용해 각각 sum에 더한다. for문이 끝나면 middle의 x좌표에 sum을 cpoints에 등재된 점들의 수로 나눈 값을 대입한다. 다시 sum = 0으로 초기화 시킨 뒤, y와 z좌표에 대해서도 같은 과정을 진행한다.
for (int i = 0; i <
cpoints.Count; i++)
{
lpoints.Add(projection.convertToLocal(cpoints[i], middle));
}
pointdist = new double[points.Count];
for (int i = 0; i <
points.Count; i++)
{
pointdist[i] =
projection.distant(points[i]);
}
pointid = new int[pointdist.Length];
for(int i = 0; i <
pointdist.Length; i++)
{
int rank = 0;
for(int j = 0; j < i;
j++)
{
if(pointdist[i] >
pointdist[j])
{
rank++;
}
}
for(int j = i+1; j <
pointdist.Length; j++)
{
if (pointdist[i] >
pointdist[j])
{
rank++;
}
}
pointid[rank] = i;
}
그림 13 Main 함수 코드 5
for문을 이용해서 cpoints에 등재된 점들을 middle이 원점이 되는 로컬 좌표계에 대한 점이 되도록 변환시키고, 그 값을 lpoints 리스트에 추가시킨다. 그리고 projection의 distant 함수를 이용해서 viewport와 points에 등재된 점 사이의 거리를 구하고, 이 값을 순서대로 pointdist 배열에 넣는다. 다음, pointid를 초기화 시키고, 이중 for문을 이용하여 points에 등재된 점들이 얼마나 viewport로부터 먼 지 순위를 매기고 그 값을 pointid에 저장한다. 그 과정으로 우선, for문과 for문 사이에 rank를 선언하고, 0으로 초기화한다. 그리고 내부 for문을 이용하여 points의 i번째 점이 j번째 점보다 viewport로부터 더 멀리 있다면, rank를 1 증가시킨다. 다 비교한 뒤에는 pointid의 i의 자리에 rank 값을 저장한다.
faceid = new int[tetra.list.Count];
for(int i = 0; i <
tetra.list.Count; i++)
{
faceid[i] = (int)(Math.Pow(2,
pointid[tetra.list[i].x1]) + Math.Pow(2, pointid[tetra.list[i].x2]) +
Math.Pow(2, pointid[tetra.list[i].x3]));
}
그림 14 Main 함수 코드 6
for문을 이용하여 tetra.list의 i의 자리에 저장된 Triangle이 포함하고 있는 점이 viewport로부터 얼마나 가까이 있는지에 대한 순위(viewport에 가까울수록 1위에 가까움)를 지수로 가지는 2의 거듭제곱의 합을 faceid의 i의 자리에 저장한다. 결과적으로, ‘가장 뒤에 있는 평면’일수록 faceid의 값이 커지게 된다.
for(int i = 0; i <
(faceid.Length - 1); i++)
{
for(int j = 0; j <
(faceid.Length - 1 - i); j++)
{
if (faceid[j] <
faceid[j + 1])
{
Triangle swap =
tetra.list[j + 1];
tetra.list[j + 1] = tetra.list[j];
tetra.list[j] = swap;
int swapid = faceid[j +
1];
faceid[j + 1] =
faceid[j];
faceid[j] = swapid;
}
}
}
그림 15 Main 함수 코드 7
버블 정렬을 이용하여 faceid를 정렬하는데, 값이 큰 것이 먼저 오도록 정렬을 한다. faceid를 정렬하는 동시에, faceid에 해당하는 평면을 가지고 있는 tetra.list의 평면 또한 함께 움직이도록 한다. 버블 정렬은 이중 for문을 이용하는데, 바깥 for문은 pace를 다음 pace로 넘기는 역할을 하고, 내부의 for문은 pace 내에서 원소끼리 swap 하는 작업, 즉 어떤 원소에 대해 바로 오른쪽에 있는 원소의 값이 기준이 되는 원소보다 더 크면 서로 자리를 맞바꾸는 작업을 하게 된다. 한 pace가 끝나면 오른쪽 끝은 점점 자기 크기에 맞는 자리들을 차근히 찾아가게 되므로 내부 for문의 j의 한계 값이 다음 pace로 진행될 때마다 1씩 줄어들게 된다.
StreamWriter sw = new StreamWriter("output.ps");
StreamWriter sw1 = new StreamWriter("output1.ps");
sw.WriteLine("%!");
for(int i = 0; i <
tetra.list.Count; i++)
{
sw.WriteLine("newpath");
sw.WriteLine("{0} {1}
moveto", 100+100*lpoints[tetra.list[i].x1].x,
100+100*lpoints[tetra.list[i].x1].y);
sw.WriteLine("{0} {1}
lineto", 100+100*lpoints[tetra.list[i].x2].x, 100+100*lpoints[tetra.list[i].x2].y);
sw.WriteLine("{0} {1}
lineto", 100+100*lpoints[tetra.list[i].x3].x,
100+100*lpoints[tetra.list[i].x3].y);
sw.WriteLine("{0} {1}
lineto", 100+100*lpoints[tetra.list[i].x1].x, 100+100*lpoints[tetra.list[i].x1].y);
sw.WriteLine("closepath");
sw.WriteLine("{0}
setgray", i * 0.25);
sw.WriteLine("fill");
sw.WriteLine("stroke");
}
sw.Close();
sw1.WriteLine("%!");
for(int i = 0; i <
tetra.list.Count; i++)
{
sw1.WriteLine("newpath");
sw1.WriteLine("{0} {1}
moveto", 100+100*lpoints[tetra.list[i].x1].x,
100+100*lpoints[tetra.list[i].x1].y);
sw1.WriteLine("{0} {1}
lineto", 100+100*lpoints[tetra.list[i].x2].x,
100+100*lpoints[tetra.list[i].x2].y);
sw1.WriteLine("{0} {1}
lineto", 100+100*lpoints[tetra.list[i].x3].x,
100+100*lpoints[tetra.list[i].x3].y);
sw1.WriteLine("{0} {1}
lineto", 100+100*lpoints[tetra.list[i].x1].x,
100+100*lpoints[tetra.list[i].x1].y);
sw1.WriteLine("closepath");
sw1.WriteLine("stroke");
}
sw1.Close();
그림 16 Main 함수 코드 8
StreamWriter sw와 sw1을 선언하는데, sw는 output.ps에 면이 색칠된 형태의 사면체를 출력할 것이며, sw1는 output1.ps에 면이 색칠되지 않은 형태의 사면체를 출력하게 될 것이다. tetra.list에 등재된 면을 리스트에 등재된 앞에서부터 차례차례 그려 나가게 되는데, 위에서 버블 정렬로 재정렬하였으므로 결과적으로 viewport로부터 멀리 있는 면, 소위 ‘뒤에 있는 면’부터 postscript로 그리게 될 것이며, 그럼 sw이 그리는 사면체의 경우 ‘가려져서 보이지 않아야 할 부분’은 postscript 결과에서 보이지 않게 된다. 단, 면을 구분하기 쉽게 하기 위해서 setgray의 값을 점점 변화시켰다. sw1은 면이 색칠되지 않았으므로 그냥 사면체의 모서리만 postscript 결과에서 보이게 된다.
이들을 postscript에 출력할 때, 로컬 좌표계를 다시 postscript 좌표계에서 잘 보이도록 사면체를 확대하여 출력하였는데, 로컬 좌표계의 원점이 lpoints 리스트에 있는 점들의 평균점이므로, 그림 16에서처럼 확대하면 사면체의 x좌표에 대한 길이 확대율이 100배, y좌표에 대한 길이 확대율이 100배가 되며, 또 전체적으로 (100,100)만큼 평행이동 하게 된다.
III. Result
색을 칠하지 않은 사면체의 경우 다음과 같이 출력된다.
그림 17 모서리만 그려진 사면체
색을 칠한 사면체의 경우 다음과 같이 출력된다.
그림 18 면이 색칠된 사면체
