C++ 使用 Bresenham 线算法绘制线
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/10060046/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Drawing lines with Bresenham's Line Algorithm
提问by ToastyMallows
My computer graphics homework is to implement OpenGL algorithms using only the ability to draw points.
我的计算机图形作业是仅使用绘制点的能力来实现 OpenGL 算法。
So obviously I need to get drawLine()to work before I can draw anything else. drawLine()has to be done using integers only. No floating point.
所以很明显我需要开始drawLine()工作才能画其他东西。 drawLine()必须仅使用整数来完成。没有浮点。
This is what I was taught. Basically, lines can be broken up into 4 different categories, positive steep, positive shallow, negative steep and negative shallow. This is the picture I am supposed to draw:
这是我被教导的。基本上，线条可以分为 4 个不同的类别，正陡峭、正浅、负陡和负浅。这是我应该画的图：
and this is the picture my program is drawing:
这是我的程序正在绘制的图片：
The colors are done for us. We are given vertices and we need to use Bresenham's Line algorithm to draw the lines based on the start and end points.
颜色是为我们完成的。我们得到了顶点，我们需要使用 Bresenham 的 Line 算法根据起点和终点绘制线。
This is what I have so far:
这是我到目前为止：
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;
}
}
}
}
I know my error is going to be something silly, but I honestly cannot figure out what I am doing wrong. Why are some of the lines drawn incorrectly as shown above?
我知道我的错误将是愚蠢的，但老实说我无法弄清楚我做错了什么。为什么有些线条绘制不正确，如上图所示？
采纳答案by ToastyMallows
In case anyone was wondering what the problem was, I still don't know what it was. What I ended up doing was re-factored my code so that the -shallow and -steep used the same algorithm as +shallow and +steep, respectively. After adjusting the x,y coordinates (negating the x or y coordinate), when I went to plot them I negated my original negation so that it plotted in the right spot.
万一有人想知道问题是什么，我仍然不知道它是什么。我最终做的是重构我的代码，以便 -shallow 和 -steep 分别使用与 +shallow 和 +steep 相同的算法。在调整 x,y 坐标（否定 x 或 y 坐标）后，当我去绘制它们时，我否定了我原来的否定，以便它绘制在正确的位置。
回答by Avi
You can find the complete code in C++ to draw a line using Bresenham Algorithm at http://www.etechplanet.com/codesnippets/computer-graphics-draw-a-line-using-bresenham-algorithm.aspx:
您可以在http://www.etechplanet.com/codesnippets/computer-graphics-draw-a-line-using-bresenham-algorithm.aspx 上找到使用 Bresenham 算法绘制一条线的 C++ 完整代码：
/*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);
}
}
}
回答by Adriel Jr
I implemented the original Bresenham's algorithm in C++ and tried to optimize as much as I could (especially regarding removing the IF from the interior loop).
我在 C++ 中实现了原始的 Bresenham 算法，并尝试尽可能多地优化（特别是关于从内部循环中删除 IF）。
It draws in a linear buffer instead of a surface, and for this matter, this implementation was almost as fast as EFLA (Extremely Fast Line Algorithm)(maybe 5% slower).
它绘制了一个线性缓冲区而不是一个表面，就此而言，这个实现几乎和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];
}
}
The EFLA implementation that I am using is:
我正在使用的 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
}
}
