article search result of 'Line' : 2

  1. 2010.12.04 [Draw Line Algorithm] 1. 기본(2) 총정리 (90)
  2. 2010.12.04 [Draw Line Algorithm] 1. 기본(1) (65)

[Draw Line Algorithm] 1. 기본(2) 총정리


[Draw Line Algorithm] 1. 기본(2) 총정리



우선 직선의 방정식은 위와 같다. (공통수학의 정석 554p) 두점 p1 , p2 을 알고 있을때 두점의 방정식이다.
m 은 기울기 이다. 즉 x점과 y점의 변화량이다. 그리고 이 공식에는 x1 과 x2는 같지 않을때 이다.
이때는 값이 무한대가 되거나 에러가 난다. 그래서 적절한 예외 처리를 해주어야 한다.



공식을 적용하여 보면 우선 기본적인 m이 -1보다 크고 1보다 작을때 이다. for 루프로 찍혀질
점(자취) _x의 영역을 잡고 범위 안에서 자취_y를 계산 하여 비트맵 데이터의 점을 찍는다.

이때 직선 방정식의 해의 범위가 실수 인데, 우리가 모니터로 보는 모는 비트맵 영역은 정수
이므로 정수로 타입 케스팅 된다
( 사용하는 언어에 따라 자동으로 타입캐스팅이 안되는 경우가 있다 )

이런 식으로 하나하나의 점이 모여 선이 되는것이다.

그러나 이 방법 대로 코딩을 해보면 특정 영역에서는 선이 이루어 지지 않는 경우가 있다.
예시로는 예전의 글의 데모를 보면 알수 있다 http://scripter.egloos.com/2272309 
특히 p0.x 와 p1.x 가 같아질때는 선이 아에 없어 진다.

그래서 범위를 나누어 처리할 필요가 있다. 
노란색 선은 기울기를 말한다. 기초 수학과 차이점은 원점이 좌측 상단이다 그래서 기초수학과 비교하여
기울기가 서로 반대 이다. (2D 의 경우)

점선은 P0.x 와 P1.x 가 같아질 경우 무한대(+- infinity) 혹은 (ZeroDivisionError) 가 발생할경우 인데 요것 역시  
if 로 처리하여 y= P1.x 꼴로 바꾸면 된다.
영역안에 글자는 if 로 처리할 영역의 조건들이다.

우선 P1을 기준으로 오른쪽은 바로 이전의 그림에서 해결하였다. 그리고 P1의 왼쪽영역은 두점의 예외만 처리하면
된다. 문제는 붉은색 영역이다. 붉은색 영역을 기존의 방법 으로 방정식을 풀면 아래의 그림처럼 나온다. 


for 루프는 _x의 영역만 해당하여 X축 에 해당하는 점은 충실히 찍었으나 위의 그림처럼 _x보다 _y가 클때
 선의 점을 모두 충당하지 못하는 경우가 발생한다. 이유는 아까도 말했드시 비트맵은 정수의 영역이기 때문에.
정수로 처리할수 없는 값이 나오기 때문이다.
이럴경우 점선이 되거나 영역을 벗어 나게 된다. 이는 기울기가 급격해 질수록 간격이 벌어져서 수직이 되면
사라지는 현상이 발생한다

이를 해결하기 위해서는 아래의 그림처럼 ...
X축과 Y축을 90도 돌려서 생각하면 된다. 즉 X성분과 Y성분을 를 서로 바꾸어 생각하면 된다.
유의 할점은 기울기 m 도 x성분과 y성분을 바꾸면 1/m 이 된다. 

위의 구차한? 설명들은 코드로 한방에 생각해 보자
코드를 보면 쉽다.

circle클래스는 단순한 Sprite 에 원을 그리고 글자를 넣은 단순한 클래스 이다.


위의 코드를 컴파일 하면
영역별로 선 색깔을 다르게 했다.

'수학' 카테고리의 다른 글

[Draw Line Algorithm] 1. 기본(2) 총정리  (90) 2010.12.04
[Draw Line Algorithm] 1. 기본(1)  (65) 2010.12.04
[회전변환] 특정좌표를 중심으로 회전변환  (122) 2010.12.04
[삼각함수] 기울어진 그리드의 좌표 구하기  (39) 2010.12.04
정렬  (45) 2010.12.04
atan2 를 "도" 로 환산  (200) 2010.12.04
Yamecoder 야매코더_
수학 2010.12.04 03:40

[Draw Line Algorithm] 1. 기본(1)


[Draw Line Algorithm] 1. 기본(1)

XNA 에 별다른 비트맵 API가 없다는것을 알고 , 한번 픽셀을 다루기로 했다.

우선 브레슨햄 알고리즘 에 들어가기 전에 일반적인 선을 그리는 알고리즘을

살펴 보아야 하겠다.

먼저 우리가 비트맵에 선을 긋기 위해서는 일반적으로 두점을 필요로 한다. 
(물론 한점과 기울기를 이용할수도 있겠지만 특별한 경우가 아니라면 정확한 포인팅이 가능한 두점을 이용한다)  

우선 고등학교 기초 수학에 보면 두점을 알때 직선 방정식은 ..

(공통수학의 정석 p554)

p0(x0 , y0) 와 p1(x1,y1) 을 알때 직선의 방정식은 

Y - y0 = ( y1 - y0 / x1 - x0 ) * ( X - x0)  (단 , x1  !=  x0)

이러하다. 기본적인 Y = m*X 라는 공식에 대힙하면  ( y1 - y0 / x1 - x0 ) 이 기울기 이자

변화량 이란것쯤은 알수있다. 나머지 Y - y0  ,  X - x0  은 평행 이동 이다.

누구나 알고 있을법한 이 방정식을 비트맵 위에 표현해보자.

우선 비트맵은 정수들 "맵" 이다, 위의 공식의 영역은 "실수" 이다.

따라서 정수로 다운캐스팅 하여 표현 해야 한다.


이제 한번 본격적으로 for 루프를 생각해 보자

기본적으로 X 축 변화량을 생각하면 범위를 쉽게 생각할수 있다.
이다. 따라서 for 루프는 다음과 같이 될수 있겠다.

for( var _x:int =p0.x   ; _x < p1.x  ; ++_x)
{
    //
}


이것으로 공식의 우변 _x 를 설정 했다. 그리고 이것을 Y에 넣기 전에 기울기 m을 설정하자

var m:Number = (p1.y-p0.y)/(p1.x-p0.x);

이다

이제 루프를 완성하면

for( var _x:int =p0.x   ; _x < p1.x  ; ++_x)
{
     var _y:int =Math.round(m*(_x-p0.x) + p0.y);
     data.setPixel(_x,_y,0);
}


완성하면 여기서 dataBitmapData 이다.

그리고 위의 직선 공식을 정리하면 _y 값을 얻을수 있는데 

아까도 말했드시 비트맵은 정수를 사용하여서  round 로 반올림을 하여 정수화 했다.

이 공식을 이용하여 간단히 프로그래밍 해보면,.

Bresenham1_as.swf

p0 와 p1을 직접 움직여 보자



와 같은 결과를 낸다.  ( 브라우저에서 해보기 보단 직접 다운하여 로컬에서 추천)

그런데 조건이 있다.

1.
Y - y0 = ( y1 - y0 / x1 - x0 ) * ( X - x0)  (단 , x1  !=  x0)
에서의 조건인데 p0.x 와 p0.y 가 같으면 안되고

2.
또한 위의 결과물에서는 기울기가 (-) 이 되었을때 , 즉( p0.x > p1.x ) 가 되었을때,

3.
x의 변화량 보다 y의 변화량이 클때 , 즉 기울기가 1 보다 클때 비트맵의 양 조절


이렇게 3개 이고 이것에 대해 파생되는 여러 예외를 제어 해야 한다.

'수학' 카테고리의 다른 글

[Draw Line Algorithm] 1. 기본(2) 총정리  (90) 2010.12.04
[Draw Line Algorithm] 1. 기본(1)  (65) 2010.12.04
[회전변환] 특정좌표를 중심으로 회전변환  (122) 2010.12.04
[삼각함수] 기울어진 그리드의 좌표 구하기  (39) 2010.12.04
정렬  (45) 2010.12.04
atan2 를 "도" 로 환산  (200) 2010.12.04
Yamecoder 야매코더_
수학 2010.12.04 03:39
Powerd by Tistory, designed by criuce
rss