1학기 결산-게임엔진프로그래밍활용

이미지
1. 브레젠험 직선 알고리즘 컴퓨터에서 계산이 느린 실수 연산을 사용하지 않고 직선을 그리기 위해 만들이진 알고리즘입니다. 평면을 아래와 같이 8분 면으로 나누어 직선을 그립니다. 링크:  https://sulinep.blogspot.com/2020/05/bresenhams-line-algorithm.html 2. 엔진 기초 수학 여기서는 본격적으로 구현에 들어가기 전 기초 수학 지식을 쌓았습니다.  수학에서의 체는 대수적 구조의 하나로 덧셈, 뺄셈, 곱셈, 나눗셈의 사칙연산을 집합 안에서 소화할 수 있는 집합을 의미합니다. 체를 이루기 위한 조건과 체라는 개념을 알아보았습니다. 처음에 체 라는 개념이 뭔가 머릿속에서 애매했는데 이후 갈로이스 체에 대해 배운 후 조금 더 명확해졌습니다. 스칼라 는 벡터를 정의하기 위한 필수 요소이고 크기만 있고 방향이 없는 성분이다. 벡터는 크기와 방향을 포함하는 표현 도구이다. 겨기서 벡터의 기본 연산자들을 알아보았습니다. 선형성 은 직선처럼 똑바른 도형 또는 그와 비슷한 성질을 가진 대상이라는 뜻으로 함수의 경우 함수가 진행하는 모양이 직선이라는 의미로 사용된다. 선형성을 만족하려면 두 가지 조건을 만족해야 하는데 균질성과 첨가성이다. homogeneity (균질성):   additivity (첨가성): 선형이라고 부르는 수식들은 중첩의 원리 가 적용된다는 특징이 있다. 이때 행렬과 선형 변환의 관계에 대하여도 알아보았었는데 선형 변환과 행렬은 1:1 대응된다. 기저 란 어떤 벡터 공간을 선형 생성하는 선형 독립인 벡터들이다. 각각의 원소들이 다시 벡터 공간을 생성할 수 있어야하고 일차 독립이어야 한다. 표준 기저 는 많은 기저들 중 성분 1개만이 1이고 나머지 성분이 모두 0인 표준 적인 벡터이다. 여기서 벡터 공간 R의 기저를 구성하는 원소의 개수가 해당 공간의 차원 이다. 행렬 은 열기반 행렬과 행기반 행렬 중 어떤 걸 사용하느냐에 따라 계산 방식이 달라진다. 여기서는 벡터의 크기, 회전, 밀기, 선형 변환에 대하여

[알고리즘] 코헨 서더랜드 알고리즘(Cohen–Sutherland algorithm)

이번 글은 코헨 서더랜드 알고리즘에 관한 글입니다.


1. 코헨 서더랜드 알고리즘

이 알고리즘은 라인 클리핑에서 사용되는 컴퓨터 그래픽 알고리즘 입니다.
2차원 공간은 아래의 그림처럼 9개의 영역으로 분할 한 다음 볼 수 있는 선의 부분을 효율적으로 연산합니다.

상 = 1000
하 = 0100
좌 = 0001
우 = 0010













이 알고리즘이 선을 클리핑 하는 방식은 다음과 같습니다.
1. 선을 그리는 두 개의 점을 입력 받고 각 점이 위치한 영역을 체크합니다.
2. 위의 체크한 결과에서 두 점이 모두 0000 이 나오면 선은 모두 화면 안에 있으므로 바로 선을 그립니다.
3. 두 점의 검사 결과를 비트연산 &(and)를 통해 0000 이 나오지 않는 다면 해당 선은 화면 바깥에 있으므로 선을 그리지 않습니다.
4. 나머지 경우는 두 점중 하나만 화면안에 있는 경우로 클리핑 작업이 필요합니다.
직선의 기울기 방정식을 이용해 각 점을 계산한 후 최종 선을 그립니다.

예시 그림으로 한번 살펴 봅시다. (모두 스크린 좌표, 스크린 사이즈는 가로 800 세로 400)



















위 그림의 붉은 색 선을 그린다고 가정하고 위의 알고리즘 순서에 따라 가보겠습니다.

1. 각 점이 위치한 영역을 체크합니다. 일단 P1은 스크린 좌표 안에 있으므로 0000이라는 결과 값이 나옵니다. 그리고 P2의 좌표는 (1000, 100) 이므로 그려줄 스크린 최대 넓이를 벗어납니다. 위의 그림을 봤을 때 결과값은 0100 이 나옵니다.

2. 1번에서 체크 했던 결과 두 점 모두가 0000이 아니므로 넘어갑니다.

3. 두 점의 영역 결과를 &(and) 연산 해줍니다.

     결과는 0000 이 나와 다음 과정으로 넘어갑니다.

4. 위에서의 기타 과정이 끝나고 라인 클리핑이 필요하다는 것이 결정되었습니다. 이제 실제로 라인 클리핑이 이루어져야합니다.




















화면 정 가운데가 원점 (0,0) 이라고 했을때 최소 범위는 (-400, -200) 이고 최대 범위는 (400,200) 입니다.

먼저 직선의 기울기를 구해줍니다.


위의 경우 P2 의 X 좌표가 최대 범위를 넘어가기 때문에 X의 값은 최대 값인 400 입니다.
그럼 P2 Y 값은 P1 X의 값이 400일때의 값을 구해야합니다.
Y의 값을 구하는 것은 두 점의 교점을 구하는 식을 쓰면 간단합니다.

(시작 Y 좌표) + ((높이) * ((변한 X좌표의 값) - (시작 X 죄표))/(넓이))
즉, P2.Y = -100 + (250 * (400-(-40))/640) = 71.875 입니다.

최종적으로 P2의 클리핑된 좌표는 (400, 71.875)로
직선은 (-40,-100) 에서 (400,71.875)의 위치로 그려집니다.

2. 구현

int exeptCount = 0;

// 영역 검사
int startTest = TestRegion(InOutStartPos, InMinPos, InMaxPos);
int endTest = TestRegion(InOutEndPos, InMinPos, InMaxPos);

while (true)
{
 // 안전장치
 if (exeptCount > 4)
  return false;

 // 모든 점이 화면 안에 있을때
 if ((startTest == 0) && (endTest == 0))
 {
  return true;
 }
 else if (startTest & endTest) // 모든 점이 바깥에 있을때
 {
  return false;
 }

 Vector2 clipPos;
 int currentTest = startTest ? startTest : endTest;
 float width = InOutEndPos.X - InOutStartPos.X;
 float height = InOutEndPos.Y - InOutStartPos.Y;

 // 좌우 검사
 if (currentTest < 0b0100)
 {
  // 왼쪽이면 MinPos.X 가 되고 오른쪽이면 MaxPos.X 가 된다.
  clipPos.X = currentTest & 0b0001 ? InMinPos.X : InMaxPos.X;
  clipPos.Y = InOutStartPos.Y + height * (clipPos.X - InOutStartPos.X) / width;
 }
 else // 상하 검사
 {
  // 위쪽이면 MaxPos.Y가 되고 아래쪽이면 MinPos.Y 가 된다.
  clipPos.Y = currentTest & 0b1000 ? InMaxPos.Y : InMinPos.Y;
  clipPos.X = InOutStartPos.X + width * (clipPos.Y - InOutStartPos.Y) / height;
 }
 // 결과 값을 대입
 if (currentTest == startTest)
 {
  InOutStartPos = clipPos;
  startTest = TestRegion(InOutStartPos, InMinPos, InMaxPos);
 }
 else
 {
  InOutEndPos = clipPos;
  endTest = TestRegion(InOutEndPos, InMinPos, InMaxPos);
 }
 exeptCount++;
}

위에서 예시로 활용했던 좌표로 선 그리기 및 클리핑


회전

























(SoftRenderer 는 강의 시간 활용 목적으로 교수님께서 제공 해주신 엔진입니다...)

댓글

이 블로그의 인기 게시물

[알고리즘] 브레젠험 직선 알고리즘 (Bresenham's line algorithm)

오일러 각, 로드리게스 회전 공식, 평면의 방정식