Построение окружности по алгоритму Брезенхэма

circle

Задача: построить окружность с помощью алгоритма Брезенхэма.

Разберем алгоритм в частном случае: пусть (0, 0) - координаты центра окружности и r - ее радиус. Точка с которой начнем рисование - (0, r), назовем ее текущей. Текущими будут все точки близкие к кривой с координатой y не менее r / 2, т.е мы построим 1 / 8 окружности, а все остальные точки будут получаться симметричным отображением относительно различных прямых. На каждом шаге алгоритма с текущей точкой (x, y) рассматриваются 3 точки: (x + 1, y), (x, y - 1), (x + 1, y - 1). Находим расстояния от этих 3 точек до кривой окружности, как r * r - (a * a + b * b), где (a, b) - одна из 3 точек возможного перехода, возводим значения в квадрат, чтобы избежать вычислений корня каких-либо значений. Выбираем из этих расстояний минимальное и переходим в точку, соответствующую этому расстоянию ( она объявляется текущей ).

main.cpp:

#include "openGL.h"
 
Int width = 800, height = 800; // ширина и высота окна
 
class Circle
{
	public:
		Circle(Int _x0 = width + 1, Int _y0 = height + 1, Int _r = 0) { x0 = _x0; y0 = _y0; r = _r; } // конструктор класса
		void drawCircle(); // функция-член рисования окружности
		void drawPixel(Int &, Int &); // закрасить пиксель и симметричные ему ( 8 точек на кривой )
		Int x0, y0, r; // (x0, y0) - координаты центра окружности, r - радиус
};
 
Circle _circle; // создание объекта _circle типа Circle
 
Int dis(Int x, Int y)
{
	return x * x + y * y; // Вычисление расстояния от (0, 0) до (x, y), возведенное в квадрат
}
 
void Circle::drawPixel(Int & x, Int & y)
{
	glColor3f(1, 1, 1); 
	glBegin(GL_POINTS);
		glVertex2i(x0 + x, y0 + y);
		glVertex2i(x0 - x, y0 + y);
		glVertex2i(x0 + x, y0 - y);
		glVertex2i(x0 - x, y0 - y);
		glVertex2i(x0 + y, y0 + x);
		glVertex2i(x0 - y, y0 + x);
		glVertex2i(x0 + y, y0 - x);
		glVertex2i(x0 - y, y0 - x);
	glEnd();
}
 
void Circle::drawCircle()
{
	Int x = 0, y = r; // начинаем рисовать окружность с точки (0, r). Смещение окружности через координаты центра учитывается в функции Circle::drawPixel(Int &, Int &). В дальнейшем (x, y) - это текущая точка рисования
	while(y >= (r >> 1)) // текущая координата y изменяется от r до r / 2 (строим 1/8 окружности)
	{
		drawPixel(x, y); // по текущей точке рисования получаем 8 точек на кривой окружности и закрашиваем их
		Int move[3]; // массив расстояний до 3 точек, в которые можно перейти из текущей для последующего их закрашивания
		move[0] = abs(dis(x + 1, y) - r * r); // вычисляем расстояние от (x + 1, y) до кривой окружности
		move[1] = abs(dis(x, y - 1) - r * r); // вычисляем расстояние от (x, y - 1) до кривой окружности
		move[2] = abs(dis(x + 1, y - 1) - r * r); // вычисляем расстояние от (x + 1, y - 1) до кривой окружности
		switch(min_element(move, move + 3) - move) // switch ( X ), X принадлежит {0, 1, 2}, где move[X] - это min(move[0], move[1], move[2]). То есть определяем позицию в массиве move с минимальным значением
		{
			case 0: x++; break; // Если эта позиция = 0, т.е move[0] > move[1] и move[0] > move[2], то перемещаемся в точку (x + 1, y)
			case 1: y--; break; // Если эта позиция = 1, т.е move[1] > move[0] и move[1] > move[2], то перемещаемся в точку (x, y - 1)
			case 2: x++; y--; break; // Если эта позиция = 2, т.е move[2] > move[0] и move[2] > move[1], то перемещаемся в точку (x + 1, y - 1)
		}
		// Полученная точка (x, y) - текущая
	}
}
 
void display() // функция вывода на экран изображения
{
	glClear(GL_COLOR_BUFFER_BIT);
	_circle.drawCircle(); // вызываем метод drawCircle объекта _circle
	glutSwapBuffers(); 
}
 
void reshape(Int w, Int h) // функция смещения и изменения размеров окна
{
	glClearColor(0, 0, 0, 0); 
	glViewport(0, 0, min(w, h), min(w, h));
	glMatrixMode(GL_PROJECTION);
	glLoadIdentity();
	glOrtho(0, width, 0, height, -1, 1); // используем ортографическую проекцию
}
 
void timer(Int)
{
	display();
	glutTimerFunc(60, timer, 0);
}
 
void mouse(Int button, Int state, Int x, Int y)
{
	if(button == GLUT_LEFT_BUTTON && state == GLUT_DOWN)
		_circle = Circle(width / 2, height / 2, 100); // при нажатии левой кнопки мыши - рисуем окружность центре окна, в точке (width / 2, height / 2) с радиусом 100
	if(button == GLUT_RIGHT_BUTTON && state == GLUT_DOWN)
		_circle.x0 = width + 1, _circle.y0 = height + 1, _circle.r = 0; // при нажатии правой кнопки мыши удаляем окружность
}
 
void key(Int key, Int x, Int y)
{
	if(key == GLUT_KEY_UP && _circle.r + 5 < width / 2)
		_circle.r += 5; // при нажатии клавиши UP на клавиатуре увеличивается радиус на 5
	if(key == GLUT_KEY_DOWN && _circle.r - 5 > 0)
		_circle.r -= 5; // при нажатии клавиши DOWN на клавиатуре уменьшается радиус на 5
}
 
 
int main()
{
	glutInitDisplayMode(GLUT_RGB | GLUT_DOUBLE);
	glutInitWindowPosition(200, 200);
	glutInitWindowSize(800, 800);
	glutCreateWindow("lab4");
	glutReshapeFunc(reshape);
	glutDisplayFunc(display);
	glutMouseFunc(mouse);
	glutSpecialFunc(key);
	glutTimerFunc(60, timer, 0);
	glutMainLoop(); 
	return 0;
}

openGL.h:

#pragma comment(lib, "opengl32.lib")
#pragma comment(lib, "glut32.lib")
#pragma comment(lib, "glu32.lib")
#pragma comment(linker, "/STACK:500000000")
#include <windows.h>
#include <glut.h>
#include <gl\GL.h>
#include <gl\GLU.h>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <list>
#include <time.h>
#include <stdlib.h>
#define Int GLint
#define Float GLfloat
#define inf 0x3f3f3f3f
using namespace std;

Ключевые слова: 
Окружность, Брезенхэм, кривая, растр, opengl, circle, Bresenham, c++
ВложениеРазмер
circle.rar30.96 кб