Breshenham 라인 알고리즘 및 응용

Breshenham 라인 알고리즘 은 Bresenham 이 제시 한 정확 하고 효과 적 인 래 스 터 라인 생 성 알고리즘 으로 이 알고리즘 은 증분 정수 로 만 계산 합 니 다.
원리: 경사 율 이 1 보다 적 을 때 x 는 1, y 는 0 또는 1 을 증가 하기 때문에 y 가 0 또는 1 을 증가 했다 고 판단 해 야 한다.
 
알고리즘: 선분 (x0, y0) 부터 (xEnd,  yEnd), 선형 방정식 y = mx + b
표시 할 픽 셀 이 (x k, y k) 에 있다 고 가정 하면 다음 단 계 는 열 x 에 있 는 지 확인 해 야 합 니 다.(k+1) = x_k + 1 에 어떤 픽 셀 을 그립 니까? 위치 (x k + 1, y k) 입 니까? 아니면 (x k + 1 입 니까?  y_k + 1）。
y = m (x k + 1) + b, y 상하 두 픽 셀 의 편 량
d_lower = y - y_k
d_upper = (y_k+1) - y
d_lower - d_upper = y - y_k - ( y_k + 1 - y )
                               = 2*y - 2*y_k - 1
                               = 2*m(x_k + 1) + 2b - 2*y_k - 1    // y = mx + b
m = dy/dx    // 0 < m < 1
설정 Pk = dx*(d_lower - d_upper)        //약 Pk 가 0 보다 작 으 면 y 리 yk 가 더 가 깝 고 다음 픽 셀 추출 (x k + 1, y k), 반대로 도 마찬가지 입 니 다.
          = 2*dy*x_k - 2*dx*y_k + c   |   c = 2*dy - 2*b*dx - dx
P_(k+1) = 2*dy*(x_k+1) - 2*dx*y_(k+1) + c    // 당 xk + 1 시, yk 는 0 또는 1 을 추가 할 수 있 기 때문에 y(k+1) - y_이 가능 하 다, ~ 할 수 있다,...
P_(k+1) - P_k = 2*dy - 2*dx*( y_(k+1) - y_k )
P_(k+1) = P_k + 2*dy - 2*dx*( y_(k+1) - y_k )  // 이렇게 하면 이전 P 에 따라 다음 P 를 구 할 수 있 고, P0 만 알 면 모든 P 를 구 할 수 있다.
P0 은 xk = x0 네 P 값, 이때 yk = y0 = m * x0 + b, 위 Pk 식 은 P0 을 구 할 수 있 습 니 다.
P0 = 2*dy*x0 - 2*dx*y0 + 2*dy - 2*b*dx - dx
     = 2*dy*x0 - 2*dx*(m*x0 + b) + 2*dy - 2*b*x0 + b
     = 2*dy - dx
Pk < 0 시, y(k+1) - y_k = 0， P_(k+1) = P_k + 2*dy
Pk > 0 시, y(k+1) - y_k = 1， P_(k+1) = P_k + 2*dy - 2*dx
 
헤더 파일

#ifndef GRAPHICS_H
#define GRAPHICS_H

//    
void setPixel(int x, int y);
int intRound(float a);

//  
void line(int x1, int y1, int x2, int y2);
// 
void circle(int xc, int yc, int r);
//  
void ellipse(int xCenter, int yCenter, int x, int y);

#endif

공통 함수

#include 
#include "Graphics.h"

void setPixel(int x, int y)
{
    glBegin(GL_POINTS);
    glVertex2i(x, y);
    glEnd();
}

int intRound(float a)
{
    return int(a + 0.5);
}

선분

#include 
#include 
#include "Graphics.h"

void ResetTwoPoints(int& x1, int& y1, int& x2, int &y2)
{
    int temp;
    if (x2 < x1) {
	temp = x1;
	x1 = x2;
	x2 = temp;
	temp = y1;
	y1 = y2;
	y2 = temp;
    }
}

//0 < k < 1
//P(0) = 2dy - dx
//P(k) < 0; P(k+1) = P(k) + 2dy
//P(k) > 0; P(k+1) = P(k) + 2dy - 2dx

void line(int x1, int y1, int x2, int y2)
{
    ResetTwoPoints(x1, y1, x2, y2);    // x2 > x1,     
    int x = x1, y = y1;
    int dy = y2 - y1, dx = x2 - x1;
    int p;
    float k;

    if (x1 == x2 || y1 == y2 || abs(dx) == abs(dy)) {
        //        xy  ，   DDA        
	int incrementx, incrementy, step;
	if (abs(dx) >= abs(dy))
	    step = abs(dx);
	else
	    step = abs(dy);
	incrementx = dx / step;
	incrementy = dy / step;

	setPixel(x, y);
	for (int k = 0; k < step; k++) {
            x += incrementx;
	    y += incrementy;
	    setPixel(x, y);
        }
    }else {
        float k = float(dy) / float(dx);

	if (fabs(k) < 1) {
	    p = 2 * abs(dy) - dx;
	    setPixel(x, y);
	    while (x < x2) {
	        x++;
	        if (p < 0)
	            p += 2 * abs(dy);
	        else {
	            if (dy > 0)    //  y       
		        y++;
		    else
	                y--;
		    p += 2 * abs(dy) - 2 * dx;
		}
		setPixel(x, y);
	    }
	}else {
	    ResetTwoPoints(y1, x1, y2, x2);    //k>1 ，  x y
	    p = 2 * abs(dx) - dy;
	    setPixel(x, y);
	    while (y < y2) {
	        y++;
	        if (p < 0)
    	            p += 2 * abs(dx);
	        else {
		    if (dx > 0)    //  x       
		        x++;
		    else
		        x--;
		    p += 2 * abs(dx) - 2 * dy;
	        }
	        setPixel(x, y);
	    }
        }
    }
}

둥글다

#include 
#include "Graphics.h"

//45-90       k -1 0; P(k+1) = P(k) + 2x(k+1) + 1 - 2y(k+1)
void circle(int xc, int yc, int r)
{
    void circlePlotPoints(int x, int y, int xc, int yc);

    int x = 0, y = r;
    int p = 1 - r;

    circlePlotPoints(x, y, xc, yc);
    while (x <= y) {
        x++;
        if (p < 0) {
	    p += 2 * x + 1;
	}else {
	    y++;
	    p += 2 * x + 1 - 2 * y;
	}
	circlePlotPoints(x, y, xc, yc);
    }
}

void circlePlotPoints(int x, int y, int xc, int yc)
{
	setPixel(xc + x, yc + y);
	setPixel(xc - x-1, yc + y);
	setPixel(xc + x, yc - y-1);
	setPixel(xc - x-1, yc - y-1);

	setPixel(xc + y, yc + x);
	setPixel(xc - y-1, yc + x);
	setPixel(xc + y, yc - x-1);
	setPixel(xc - y-1, yc - x-1);
}

타원

#include 
#include "Graphics.h"

//    
//region 1
//2Ry*Ry*x >= 2Rx*Rx*y
//P(0) = Ry*Ry + 0.25Rx*Rx - Rx*Rx*Ry
//P(k) < 0; P(k+1) = P(k) + 2*Ry*Ry*x(k+1) + Ry*Ry
//P(k) > 0; P(k+1) = P(k) + 2*Ry*Ry*x(k+1) + Ry*Ry - 2Rx*Rx*y(k+1)

//region 2
//2Ry*Ry*x < 2Rx*Rx*y
//P(0) = Rx*Rx + 0.25*Ry*Ry - Rx*Ry*Ry
//P(k) < 0; P(k+1) = P(k) + 2*Rx*Rx*y(k+1) + Rx*Rx
//P(k) > 0; P(k+1) = p(k) + 2*Rx*Rx*y(k+1) + Rx*Rx + 2Ry*Ry*x(k+1)

void ellipse(int xCenter, int yCenter, int Rx, int Ry)
{
    int Rx2 = Rx * Rx;
    int Ry2 = Ry * Ry;
    int twoRx2 = 2 * Rx2;
    int twoRy2 = 2 * Ry2;
    int p;
    int x = 0;
    int y = Ry;
    int px = 0;
    int py = twoRx2 * y;
    void ellipsePlotPoints(int, int, int, int);

    ellipseMidpoint(xCenter, yCenter, x, y);
    p = intRound(Ry2 - (Rx2*Ry) + float(0.25*Rx2));
    while(px < py){
	x++;
	px += twoRy2;
	if (p < 0)
	    p += Ry2 + px;
	else {
	    y--;
	    py -= twoRx2;
	    p += Ry2 + px - py;
	}
	    ellipsePlotPoints(xCenter, yCenter, x, y);
    }

    x = Rx; y = 0;
    px = twoRy2 * x; py = 0;
    ellipseMidpoint(xCenter, yCenter, x, y);
    p = intRound(Rx2 + 0.25*Ry2 - Rx * Ry2);
    while (px > py) {
	y--;
	py += twoRx2;
	if (p < 0)
	    p += Rx2 + py;
	else {
	    x--;
	    px -= twoRy2;
	    p += Rx2 + py - px;
	}
	ellipsePlotPoints(xCenter, yCenter, x, y);
    }
}

void ellipsePlotPoints(int xCenter, int yCenter, int x, int y)
{
    setPixel(xCenter + x, yCenter + y);
    setPixel(xCenter - x, yCenter + y);
    setPixel(xCenter + x, yCenter - y);
    setPixel(xCenter - x, yCenter - y);
}