Рисование линий с помощью алгоритма Брезенхема
Моя домашняя работа по компьютерной графике - реализовать алгоритмы OpenGL, используя только возможность рисовать точки.
Так что, очевидно, мне нужно получить drawLine() работать, прежде чем я могу нарисовать что-нибудь еще. drawLine() должно быть сделано с использованием только целых чисел. Нет с плавающей точкой.
Это то, чему меня учили. В основном, линии могут быть разбиты на 4 различные категории: положительный крутой, положительный неглубокий, отрицательный крутой и отрицательный неглубокий. Это картина, которую я должен нарисовать:
и вот изображение, которое рисует моя программа:
Цвета сделаны для нас. Нам даны вершины, и нам нужно использовать алгоритм Линии Брезенхэма, чтобы нарисовать линии на основе начальной и конечной точек.
Это то, что я до сих пор:
int dx = end.x - start.x;
int dy = end.y - start.y;
//initialize varibales
int d;
int dL;
int dU;
if (dy > 0){
if (dy > dx){
//+steep
d = dy - 2*dx;
dL = -2*dx;
dU = 2*dy - 2*dx;
for (int x = start.x, y = start.y; y <= end.y; y++){
Vertex v(x,y);
drawPoint(v);
if (d >= 1){
d += dL;
}else{
x++;
d += dU;
}
}
} else {
//+shallow
d = 2*dy - dx;
dL = 2*dy;
dU = 2*dy - 2*dx;
for (int x = start.x, y = start.y; x <= end.x; x++) {
Vertex v(x,y);
drawPoint(v);
// if choosing L, next y will stay the same, we only need
// to update d by dL
if (d <= 0) {
d += dL;
// otherwise choose U, y moves up 1
} else {
y++;
d += dU;
}
}
}
} else {
if (-dy > dx){
cout << "-steep\n";
//-steep
d = dy - 2*dx;
//south
dL = 2*dx;
//southeast
dU = 2*dy - 2*dx;
for (int x = start.x, y = start.y; y >= end.y; --y){
Vertex v(x,y);
drawPoint(v);
//if choosing L, next x will stay the same, we only need
//to update d
if (d >= 1){
d -= dL;
} else {
x++;
d -= dU;
}
}
} else {
cout << "-shallow\n";
//-shallow
d = 2*dy - dx;
dL = 2*dy;
dU = 2*dy - 2*dx;
for (int x = start.x, y = start.y; x <= end.x; x++){
Vertex v(x,y);
drawPoint(v);
if (d >= 0){
d += dL;
} else {
--y;
d -= dU;
}
}
}
}
Я знаю, что моя ошибка будет чем-то глупым, но я, честно говоря, не могу понять, что я делаю неправильно. Почему некоторые линии нарисованы неправильно, как показано выше?
3 ответа
Если кому-то было интересно, в чем проблема, я все еще не знаю, что это было. То, что я в конечном итоге сделал, было повторно проанализировано в моем коде, так что -shallow и -steep использовали тот же алгоритм, что и + shallow и + steep, соответственно. После корректировки координат x,y (отрицая координаты x или y), когда я пошел строить их, я отрицал свое первоначальное отрицание, чтобы оно отображалось в правильном месте.
Вы можете найти полный код на C++, чтобы нарисовать линию, используя алгоритм Брезенхэма, по адресу http://www.etechplanet.com/codesnippets/computer-graphics-draw-a-line-using-bresenham-algorithm.aspx:
/*BRESENHAAM ALGORITHM FOR LINE DRAWING*/
#include<iostream.h>
#include<graphics.h>
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<math.h>
#include<dos.h>
void bhm_line(int,int,int,int,int);
void main()
{
int ghdriver=DETECT,ghmode,errorcode,x1,x2,y1,y2;
initgraph(&ghdriver,&ghmode,"..\\bgi");
errorcode = graphresult();
if(errorcode !=grOk)
{
cout<<"Graphics error:%s\n"<<grapherrormsg(errorcode);
cout<<"Press any key to halt:";
getch();
exit(1);
}
clrscr();
cout<<"Enter the coordinates (x1,y1): ";
cin>>x1>>y1;
cout<<"Enter the coordinates (x2,y2): ";
cin>>x2>>y2;
bhm_line(x1,y1,x2,y2,1);
getch();
}
void bhm_line(int x1,int y1,int x2,int y2,int c)
{
int x,y,dx,dy,dx1,dy1,px,py,xe,ye,i;
dx=x2-x1;
dy=y2-y1;
dx1=fabs(dx);
dy1=fabs(dy);
px=2*dy1-dx1;
py=2*dx1-dy1;
if(dy1<=dx1)
{
if(dx>=0)
{
x=x1;
y=y1;
xe=x2;
}
else
{
x=x2;
y=y2;
xe=x1;
}
putpixel(x,y,c);
for(i=0;x<xe;i++)
{
x=x+1;
if(px<0)
{
px=px+2*dy1;
}
else
{
if((dx<0 && dy<0) || (dx>0 && dy>0))
{
y=y+1;
}
else
{
y=y-1;
}
px=px+2*(dy1-dx1);
}
delay(0);
putpixel(x,y,c);
}
}
else
{
if(dy>=0)
{
x=x1;
y=y1;
ye=y2;
}
else
{
x=x2;
y=y2;
ye=y1;
}
putpixel(x,y,c);
for(i=0;y<ye;i++)
{
y=y+1;
if(py<=0)
{
py=py+2*dx1;
}
else
{
if((dx<0 && dy<0) || (dx>0 && dy>0))
{
x=x+1;
}
else
{
x=x-1;
}
py=py+2*(dx1-dy1);
}
delay(0);
putpixel(x,y,c);
}
}
}
Я реализовал оригинальный алгоритм Брезенхема в C++ и попытался максимально оптимизировать его (особенно в отношении удаления IF из внутреннего цикла).
Он рисует в линейном буфере вместо поверхности, и в этом отношении эта реализация была почти такой же быстрой, как EFLA (алгоритм чрезвычайно быстрой линии) (возможно, на 5% медленнее).
#include <vector>
#include <math.h>
using namespace std;
vector<unsigned char> buffer;
int imageSide = 2048; // the width of the surface
struct Point2Di
{
int x;
int y;
Point2Di(const int &x, const int &y): x(x), y(y){}
Point2Di(){}
};
void drawLine(const Point2Di &p0, const Point2Di &p1)
{
int dx = p1.x - p0.x;
int dy = p1.y - p0.y;
int dLong = abs(dx);
int dShort = abs(dy);
int offsetLong = dx > 0 ? 1 : -1;
int offsetShort = dy > 0 ? imageSide : -imageSide;
if(dLong < dShort)
{
swap(dShort, dLong);
swap(offsetShort, offsetLong);
}
int error = dLong/2;
int index = p0.y*imageSide + p0.x;
const int offset[] = {offsetLong, offsetLong + offsetShort};
const int abs_d[] = {dShort, dShort - dLong};
for(int i = 0; i <= dLong; ++i)
{
buffer[index] = 255; // or a call to your painting method
const int errorIsTooBig = error >= dLong;
index += offset[errorIsTooBig];
error += abs_d[errorIsTooBig];
}
}
Я использую реализацию EFLA:
void drawLine(Point2Di p0, Point2Di p1)
{
bool yLonger=false;
int shortLen=p1.y-p0.y;
int longLen=p1.x-p0.x;
if (abs(shortLen)>abs(longLen)) {
swap(shortLen, longLen);
yLonger=true;
}
int decInc = longLen==0 ? decInc=0 : ((shortLen << 16) / longLen);
if (yLonger) {
p0.y*=imageSide;
p1.y*=imageSide;
if (longLen>0)
for (int j=0x8000+(p0.x<<16);p0.y<=p1.y;p0.y+=imageSide, j+=decInc)
buffer[p0.y + (j >> 16)] = 255; // or a call to your painting method
else
for (int j=0x8000+(p0.x<<16);p0.y>=p1.y;p0.y-=imageSide, j-=decInc)
buffer[p0.y + (j >> 16)] = 255; // or a call to your painting method
}
else
{
if (longLen>0)
for (int j=0x8000+(p0.y<<16);p0.x<=p1.x;++p0.x, j+=decInc)
buffer[(j >> 16) * imageSide + p0.x] = 255; // or a call to your painting method
else
for (int j=0x8000+(p0.y<<16);p0.x>=p1.x;--p0.x, j-=decInc)
buffer[(j >> 16) * imageSide + p0.x] = 255; // or a call to your painting method
}
}