출처 : http://dnvy0084.github.io/update/2015/01/29/linedraw.html

 

두 점 사이를 잇는 점들을 구하고 싶습니다.

function lineTo( ax, ay, bx, by )
{
    //code
};

위와 같이 두점 사이의 픽셀들을 구하는 방법은 3가지 정도로 압축할 수 있습니다.

 

1차 함수 

직선의 방정식을 이용해 선을 그립니다. (m≠0) 일 때 y=mx+b 를 이용해 x가 ax 부터 1씩 증가하면 그에 맞는 y를 구할 수 있습니다. 이때 y절편 b는 −m×ax+ay가 됩니다.

y의증가분은 x의 증가분 * 기울기 (m=by−ay/bx−ax)와 같기 때문에 (y−ay) = m(x−ax)라는 식을 세울 수 있습니다.

이걸 풀어서 y로 정리하면 y = mx−m×ax+ay 가 됩니다. 여기서 뒷부분 −m×ax+ay 는 b로 치환할 수 있는 상수 입니다.

위 식을 간단히 javascript로 정리하면

var m = (by - ay) / (bx - ax),
    b = -m * ax + ay,
    y;

for( var x = ax; x <= bx; x++ )
{
    y = m * x + b;
    drawPixel( x, Math.round( y ) );
}

로 나타낼 수 있습니다.  (단 dy > dx||ax > bx||bx−ax = 0 인 경우에 대한 예외처리는 필요합니다. )

 

DDA - Digital differential analyzer

dda 알고리즘은 기울기를 이용합니다. x가 1씩 증가할 때 y의 n번째 위치는 그 전 y의 기울기 m만큼 더한 값과 같다 라는게 기본 아이디어입니다.

y = yn−1+my = yn−1+m

라는 식을 세울 수 있는데요, javascript로 정리하면

var m = (by - ay) / (bx - ax),
    y = ay;

for( var x = ax; x <= bx; x++ )
{
    drawPixel( x, Math.round( y ) );
    y += m;
}

위 식과 비교해서 곱하기 연산이 하나 줄고 b를 계산할 필요도 없어졌습니다. 초당 60번씩 몇백개의 선을 그리는 그래픽 라이브러리에서 봤을 땐 꽤 괜찮은 성능향상인 것 같네요.

 

Bresenham algorithm

Bresenham 알고리즘은 yn+1의 y위치가 이전보다 0.5가 크면 y=y+1 작으면 y=y가 기본 아이디어입니다.

위 그림처럼 e라는 값을 따로 두고, x가 증가할 때 마다 e도 기울기(m)만큼 증가하면서 e가 0.5보다 커지면 y를 1증가하는 방법으로 Math.round 연산을 대신 할 수 있는데요, code로 보자면

var dx = bx - ax,
    dy = by - ay,
    y = ay,
    e = 0;

for( var x = ax; x <= bx; x++ )
{
    drawPixel( x, y );

    e += dx;
    if( ( e << 1 ) > dx ) // 곱하기 2는 비트연산으로 대체 
    {
        e -= dx;    // e를 초기화
        y++;        // y 증가
    }
}

DDA와 비교해서 코드와 연산만 늘어났을 뿐 좋아진 점이 보이지 않네요.

위 코드에서 float 연산 부분을 모두 int 연산으로 바꿀 수 있다면 성능향상을 기대할 수 있을것 같은데요, m은 기울기(by−ay/bx−ax)라 특별한 경우가 아니라면 대부분 실수일테니 e=e+m과 e>0.5 비교 부분을 정수로 바꿔주면 될 것 같습니다.

dx = bx−ax, dy = by−ay 일때,

e = e+m을 e = e+(dy/dx) 로 보고 양변에 dx를 곱해주면 {e⋅dx=(e+(dy/dx))⋅dx}

e⋅dx = e⋅dx+dy 가 됩니다.

여기서 양변에 나오는 e⋅dx 를 새로운 e인 e′으로 놓으면

e′=e′+dy 라는 식으로 바꿀 수 있습니다.

두번째로 e>0.5 부등식 양변에 2dx 를 곱해주면 e⋅2dx>dx 로 바꿀 수 있는데, 좌변 e⋅2dx를 e′으로 바꿔주면 2⋅e′>dx 라는 부등식이 됩니다. e의 시작은 0이기 때문에 e′을 e로 둬도 위코드는 변함이 없는데요, 다만 e=e−1부분의 e는 e⋅dx로 바꿔줘야 합니다.

e=e−1 양변에 dx를 곱하면 e⋅dx = e⋅dx−dx→e′ = e′−dx로 바꿀 수 있습니다.

javascript code

var m = (by - ay) / (bx - ax),
    y = ay,
    e = 0;

for( var x = ax; x <= bx; x++ )
{
    drawPixel( x, y );

    e = e + m;
    if( e > 0.5 )
    {
        e = e - 1; // e를 초기화
        y = y + 1; // y 증가
    }
}

실제 성능을 비교해 보진 않았지만 bresenham`s line algorithm은 "extremely fast"하다고 하네요.

실제로 선을 그리는 함수를 개발할 일이 많지 않을텐데요, 직선 방정식을 loop내에서 기울기만으로 처리하거나 정수 연산으로 바꿔주는 등의 최적화 과정은 눈여겨 볼 만한 것 같습니다.

 

 

관련 소스 입니다.

<!DOCTYPE html>
<head>
	<meta charset="utf-8">
	<style>canvas { border:2px solid magenta; }</style>
</head>
<body>
	<canvas id="canvas" width="400" height="400"></canvas>
	<script>
window.onload = function() {

  var canvas = document.getElementById("canvas");
  var ctx = canvas.getContext("2d");

  // 2점의좌표
  let p1 = {x:100, y:150}
  let p2 = {x:390, y:300}
  let n = 20 // 직선을 n개의 점으로 그리기
  if(p1.x > p2.x){
    let tmp = p2
    p2 = p1
    p1 = tmp
  }
  
  // 직선을 n개의 점으로 그리기
  let obj = {};
  let gab = (p2.x - p1.x) / n
  let m = (p2.y - p1.y) / (p2.x - p1.x)
  let y = p1.y
  for( let x = p1.x; x <= p2.x; x += gab ){
    ctx.strokeRect( x , y, 2,2);
    y += (m * gab);
  }  
  ctx.strokeStyle = 'red';
  ctx.stroke();
}
	</script>
</body>
</html>

 

저작자표시 비영리

'프론트엔드 개발 놀이터 > etc' 카테고리의 다른 글

세 점을 지나는 원호 그리기 - js  (0) 2022.07.29
[VSCode] ESLint + Prettier : Expected indentation of 2 spaces but found 4  (0) 2021.11.03
특정 프로그램이 죽었을 때 자동으로 재시작하게 하는 배치파일  (0) 2020.10.19
[casperjs] 윈도우 환경 실행시 did you install phantomj  (0) 2020.10.13
[크롬인텐트] 모바일 웹에서 앱 실행하기 (앱 미설치 시 마켓으로 이동)  (0) 2020.09.24

+ Recent posts

티스토리툴바