코헨-서더랜드의 알고리즘 이야기
탐구생활/Delphi어지간한 컴퓨터 그래픽 이론책자에 빠짐없이 등장하는 이 알고리즘은 1967년도에 만들어진 대표적인 클리핑 알고리즘이다.
컴퓨터라는 물건 자체가 일반적이지 않던 시절, 직선을 뷰포트에 맞추어 잘라주기 위해 이런 고민을 했다는 사실이 그저 놀랍기만 하다.
졸업연구 과제를 선택할 때, 밑천이 필요없는 과제를 고르다보니 컴퓨터 프로그램을 만들게 되었고
배운게 도둑질이라고 설계->가공 과정에서 뭔가 건드려볼만한 주제라고 선택한 것이
오토캐드의 DXF 파일을 가공용 NC 코드로 바꿔보자는 시도였다.
당시까지 짜본거라고는 오토캐드의 리습과 배치파일밖에 없던 무식한 시절,
일년 후배 여모씨를 족쳐가며 익숙치않은 터보C로 겉모습만 그럴듯한 DXF뷰어를 만들어가는데...
아... 이거 이상하다. 줌인/줌아웃 기능을 넣고 선을 확대하다보니 엉뚱한 곳에 찌꺼기 선이 죽죽 그려진다.
지금 생각하면 뷰포트를 한참 벗어나는 선을 그릴 때 사용한 변수값이 오버플로해서 생겨난 현상일텐데,
인터넷이 없던 시절이라 어디 물어볼 곳도 마땅치 않고 그저 냉가슴만 앓을 뿐...
그러다 눈에 띈 책이 지금도 보물처럼 간직하고 있는 이 책.
꾸벅꾸벅 졸면서 들었던 컴퓨터 그래픽스 개론이라는 수업의 교재.
수업시간에는 그저 지루해 죽겠더니만, 막상 상황이 닥치니 어쩌면 그렇게 머리에 쏙쏙 들어오는 옳은말만 적혀있는지...
뷰포트 클리핑을 적용한 뒤 마음껏 확대해도 더 이상 쓰레기 정보가 나타나지 않는다는 사실이 어찌나 신기하던지...
그리하여 이 알고리즘은 책의 내용을 실제 코드로 만들어 본 최초의 경험이 되었다.
뭐 지금은 세월이 하도 좋아져서... 어지간한 확대기능 정도로는 당시 경험했던 오버플로는 구경할 수도 없다.
게다가 3D API를 쓰면 삼각형의 클리핑도 하드웨어에서 구현되버리니 이 알고리즘은 예전 추억과 함께 봉인!!
살면서 다시 써 볼 일이 있을까 싶었는데...
(그런데 그 일이 실제로 일어났습니다!!!)
먹고 사는 이야기니 자세한 내용은 말할 수 없고,
좀 많이 넓은 높이맵과 이 위를 지나가는 물체와의 충돌점을 계산해야 하는 상황에 처했다.
물체가 지나가는 경로상의 셀들을 추출하는 문제는 브랜슨햄, 또는 GPG의 네비메시 코드를 써먹으면 되는데
문제는 물체의 이동경로가 아주 길거나 높이맵과 전혀 상관없는 곳을 지나갈 때,
검사범위를 높이맵 이내로 제한하거나 아예 검사를 생략하려면 어떻게 해햐 할까.
자연스럽게 이 캐캐묵은 알고리즘이 떠올랐다.
선분과 뷰포트의 관계에 따라 아예 그리지 않거나 뷰포트 이내로 잘라 그리게 하는 절묘한 비법.
이 비법을 쓰면 물체의 긴 이동경로 중 높이맵과 관계된 부분만 잘라내거나
이동경로가 높이맵과 관계없다면 버릴 수도 있게 된다.
위키백과를 열어보자.
http://en.wikipedia.org/wiki/Cohen%E2%80%93Sutherland
친절한 C코드도 제공된다. 아이조아~
이 코드는 우리가 산수시간에 배웠던 1사분면 좌표계를 기준으로 하므로 좌하단이 원점이다.
내가 사용하는 좌표계는 무조건 좌상단이 원점이므로 이 부분만 주의해 델파이로 옮겨보자.
테스트는 대충 다음과 같이.
뷰포트는 윈도 클라이언트 영역에서 80픽셀씩 안쪽으로 잡았다.
마우스를 두 번 눌러 입력받은 선분을 그려주고 클리핑을 통과한 선은 빨간색으로 조금 굵게 그려주자.
전역 변수 따로잡기 귀찮으니 J+ 지시자를 써서 상수를 static으로 처리.
결과는 다음과 같다. 파란 뷰포트 안에 포함되는 직선만 굵고 붉게!! 그려진다.
아이~ 아름다워라~
방문자를 위한 마지막 조공짤은 위키백과에서 찾은 이반 서더랜드옹의 사진
그래. 대머리와 흰머리도 그 속에 채워진게 많으면 저렇게 간지가 좔좔 넘치잖아??!!
마누라가 아무리 압박해도 염색따위는 하지 말자!!! (귀찮아서가 아님!!!)
컴퓨터라는 물건 자체가 일반적이지 않던 시절, 직선을 뷰포트에 맞추어 잘라주기 위해 이런 고민을 했다는 사실이 그저 놀랍기만 하다.
졸업연구 과제를 선택할 때, 밑천이 필요없는 과제를 고르다보니 컴퓨터 프로그램을 만들게 되었고
배운게 도둑질이라고 설계->가공 과정에서 뭔가 건드려볼만한 주제라고 선택한 것이
오토캐드의 DXF 파일을 가공용 NC 코드로 바꿔보자는 시도였다.
당시까지 짜본거라고는 오토캐드의 리습과 배치파일밖에 없던 무식한 시절,
일년 후배 여모씨를 족쳐가며 익숙치않은 터보C로 겉모습만 그럴듯한 DXF뷰어를 만들어가는데...
아... 이거 이상하다. 줌인/줌아웃 기능을 넣고 선을 확대하다보니 엉뚱한 곳에 찌꺼기 선이 죽죽 그려진다.
지금 생각하면 뷰포트를 한참 벗어나는 선을 그릴 때 사용한 변수값이 오버플로해서 생겨난 현상일텐데,
인터넷이 없던 시절이라 어디 물어볼 곳도 마땅치 않고 그저 냉가슴만 앓을 뿐...
그러다 눈에 띈 책이 지금도 보물처럼 간직하고 있는 이 책.
꾸벅꾸벅 졸면서 들었던 컴퓨터 그래픽스 개론이라는 수업의 교재.
수업시간에는 그저 지루해 죽겠더니만, 막상 상황이 닥치니 어쩌면 그렇게 머리에 쏙쏙 들어오는 옳은말만 적혀있는지...
뷰포트 클리핑을 적용한 뒤 마음껏 확대해도 더 이상 쓰레기 정보가 나타나지 않는다는 사실이 어찌나 신기하던지...
그리하여 이 알고리즘은 책의 내용을 실제 코드로 만들어 본 최초의 경험이 되었다.
뭐 지금은 세월이 하도 좋아져서... 어지간한 확대기능 정도로는 당시 경험했던 오버플로는 구경할 수도 없다.
게다가 3D API를 쓰면 삼각형의 클리핑도 하드웨어에서 구현되버리니 이 알고리즘은 예전 추억과 함께 봉인!!
살면서 다시 써 볼 일이 있을까 싶었는데...
(그런데 그 일이 실제로 일어났습니다!!!)
먹고 사는 이야기니 자세한 내용은 말할 수 없고,
좀 많이 넓은 높이맵과 이 위를 지나가는 물체와의 충돌점을 계산해야 하는 상황에 처했다.
물체가 지나가는 경로상의 셀들을 추출하는 문제는 브랜슨햄, 또는 GPG의 네비메시 코드를 써먹으면 되는데
문제는 물체의 이동경로가 아주 길거나 높이맵과 전혀 상관없는 곳을 지나갈 때,
검사범위를 높이맵 이내로 제한하거나 아예 검사를 생략하려면 어떻게 해햐 할까.
자연스럽게 이 캐캐묵은 알고리즘이 떠올랐다.
선분과 뷰포트의 관계에 따라 아예 그리지 않거나 뷰포트 이내로 잘라 그리게 하는 절묘한 비법.
이 비법을 쓰면 물체의 긴 이동경로 중 높이맵과 관계된 부분만 잘라내거나
이동경로가 높이맵과 관계없다면 버릴 수도 있게 된다.
위키백과를 열어보자.
http://en.wikipedia.org/wiki/Cohen%E2%80%93Sutherland
친절한 C코드도 제공된다. 아이조아~
이 코드는 우리가 산수시간에 배웠던 1사분면 좌표계를 기준으로 하므로 좌하단이 원점이다.
내가 사용하는 좌표계는 무조건 좌상단이 원점이므로 이 부분만 주의해 델파이로 옮겨보자.
function CohenSutherlandLineClip(var x1, y1, x2, y2: Single; const xmin, ymin, xmax, ymax: Single): Boolean;
const
V_INSIDE = 0;
V_LEFT = 1;
V_RIGHT = 2;
V_BOTTOM = 4;
V_TOP = 8;
function ComputeOutcode(const x, y: Single): LongWord;
begin
Result := V_INSIDE;
if x < xmin then Result := Result or V_LEFT else
if x > xmax then Result := Result or V_RIGHT;
if y < ymin then Result := Result or V_TOP else
if y > ymax then Result := Result or V_BOTTOM;
end;
var
OutCode1, OutCode2: LongWord;
ChkCode: LongWord;
x, y : Single;
begin
Result := false;
OutCode1 := ComputeOutcode(x1, y1);
OutCode2 := ComputeOutcode(x2, y2);
while true do
begin
// Bitwise OR is 0. Trivially accept and get out of loop
if not Boolean(OutCode1 or OutCode2) then
begin
Result := true;
Break;
end else
// Bitwise AND is not 0. Trivially reject and get out of loop
if Boolean(OutCode1 and OutCode2) then
begin
Break;
end else
begin
// At least one endpoint is outside the clip rectangle; pick it.
if Boolean(OutCode1) then
begin
ChkCode := OutCode1;
x := x1;
y := y1;
end else
begin
ChkCode := OutCode2;
x := x2;
y := y2;
end;
// Now find the intersection point;
// use formulas y = y0 + slope * (x - x0), x = x0 + (1 / slope) * (y - y0)
if Boolean(ChkCode and V_TOP) then
begin
x := x1 + (x2 - x1) * (ymin - y1) / (y2 - y1);
y := ymin;
end else
if Boolean(ChkCode and V_BOTTOM) then
begin
x := x1 + (x2 - x1) * (ymax - y1) / (y2 - y1);
y := ymax;
end else
if Boolean(ChkCode and V_RIGHT) then
begin
y := y1 + (y2 - y1) * (xmax - x1) / (x2 - x1);
x := xmax;
end else
if Boolean(ChkCode and V_LEFT) then
begin
y := y1 + (y2 - y1) * (xmin - x1) / (x2 - x1);
x := xmin;
end;
// Now we move outside point to intersection point to clip
// and get ready for next pass.
if ChkCode = OutCode1 then
begin
x1 := x;
y1 := y;
OutCode1 := ComputeOutCode(x1, y1);
end else
begin
x2 := x;
y2 := y;
OutCode2 := ComputeOutCode(x2, y2);
end;
end;
end;
end;
테스트는 대충 다음과 같이.
뷰포트는 윈도 클라이언트 영역에서 80픽셀씩 안쪽으로 잡았다.
마우스를 두 번 눌러 입력받은 선분을 그려주고 클리핑을 통과한 선은 빨간색으로 조금 굵게 그려주자.
전역 변수 따로잡기 귀찮으니 J+ 지시자를 써서 상수를 static으로 처리.
......
{$J+}
procedure TForm1.FormMouseDown(Sender: TObject; Button: TMouseButton;
{$J+}
procedure TForm1.FormMouseDown(Sender: TObject; Button: TMouseButton;
Shift: TShiftState; X, Y: Integer);
const
CLICK_COUNT : Integer = 0;
LAST_POS: TPoint = (x:-100; y:-100);
var
x1, x2, y1, y2: Single;
xmin, ymin, xmax, ymax: Single;
begin
case CLICK_COUNT of
0: LAST_POS := Point(X, Y);
1:
begin
Canvas.Pen.Width := 1;
Canvas.Pen.Color := clBlack;
Canvas.MoveTo(LAST_POS.X, LAST_POS.Y);
Canvas.LineTo(X, Y);
xmin := 80;
ymin := 80;
xmax := ClientWidth - 80;
ymax := ClientHeight - 80;
x1 := LAST_POS.X;
y1 := LAST_POS.Y;
x2 := X;
y2 := Y;
if CohenSutherlandLineClip(x1, y1, x2, y2, xmin, ymin, xmax, ymax) then
begin
Canvas.Pen.Width := 2;
Canvas.Pen.Color := clRed;
Canvas.MoveTo(Round(x1), Round(y1));
Canvas.LineTo(Round(x2), Round(y2));
end;
end;
end;
Inc(CLICK_COUNT);
CLICK_COUNT := CLICK_COUNT mod 2;
end;
procedure TForm1.FormPaint(Sender: TObject);
begin
Canvas.Brush.Style := bsClear;
Canvas.Pen.Color := clBlue;
Canvas.Pen.Width := 1;
Canvas.Rectangle(80, 80, ClientWidth-80, ClientHeight-80);
end;
......
......
결과는 다음과 같다. 파란 뷰포트 안에 포함되는 직선만 굵고 붉게!! 그려진다.
아이~ 아름다워라~
방문자를 위한 마지막 조공짤은 위키백과에서 찾은 이반 서더랜드옹의 사진
그래. 대머리와 흰머리도 그 속에 채워진게 많으면 저렇게 간지가 좔좔 넘치잖아??!!
마누라가 아무리 압박해도 염색따위는 하지 말자!!! (귀찮아서가 아님!!!)
