|
August 22, 2005
Looking to write an E.A.R. (efficient and
robust) C++ program for the bresenham line algorithm, I
found a good one at
Wikipedia (gotta love that site: look up, for instance, "Negreponte.")
Here's there Pascal code for the algorithm I found there, which serves as a nice pseudocode for a C version. I've added
the comments.
// The line is defined
by its endpoints (x0,y0) and (x1,y1)
function
line(x0, x1, y0, y1)
// First decide whether the line is steep
// (reference angle > 45 degrees) or not.
// Pay close attention to the
order of computations here.
// it's very cleverly efficient to cover all cases with a
// minimum of code.
boolean
steep := deltay > deltax
// If it is a steep line, then
step pixels along the y-axis.
// Rather than writing all new code for this, it's simpler (?)
// to just swap parameters and use the same code. Later,
// you'll need to swap again to plot the points.
if
steep then
swap(x0, y0)
swap(x1, y1)
// Now that you know which mode (steep or not,) compute
// these, but note: if in steep mode, they're swapped.
int
deltax := abs(x1 - x0)
int
deltay := abs(y1 - y0)
// Here "error" initializes what will be
half of what
// Hearn&Baker call the "decision parameter," Pk.
int
error := 0
// In this version of the algorithm, which is equivalent to
Hearn&Baker
// You initialize Po = 0 and then iterate
// if Pk<0, then don't increase the y pixel and increment Pk by
deltay
// else, increment the y pixel by 1 and decrement Pk by deltax -
deltay
int
x := x0
int
y := y0
// Of course, if you're headed down
instead of up, or left instead of right,
// you'll need to reorient to the opposite:
if
x0 < x1 then
xstep := 1
else xstep :=
-1
if
y0 < y1 then
ystep := 1
else ystep :=
-1
// Plot the first
point.
if
steep then
plot(y,x) else
plot(x,y)
while
x != x1
x := x + xstep
error := error + delty
// If Pk
is positive...or the equivalent
if
2×error ≥ deltax
y := y
+ ystep
error
:= error - deltax
if
steep then
plot(y,x) else
plot(x,y)
It took entirely too long to come to grips with
this simple algorithm. I've finally understood it as a
terrific device for avoiding floating point operations (by sticking
to integer additions) and producing the proper average of ups per
rights (or ups per lefts, downs per rights or downs per lefts.) I've
written some C++ code and have some
interesting graphics/numerical output data to analyze, so let's get to it!
I'd like to
compare the Bresenham line with the DDA (digital differential
analyzer) for goodness of fit (FOR GOODNESS' SAKE!) and for
simplicity of computation. One observation is that the '0'
case for the decision parameter could really go either way: would it
then improve the fit to make it alternate, even randomly?
Anyway, here's the darn C++ code I'm using now.
/* CS 365 Lab 1 OpenGL Template
* Look for ??? to see where your code goes!
* (Cribbed and modified from one used at Utah,
* written by Kristi Potter) */
#include <stdio.h>
#include <stdlib.h>
#include <GL/glut.h>
#include <cmath>
//------------------------------------------
// Standard functions and callbacks
//-----------------------------------------
/* Initialize GL (defined below) */
void initGL();
/* Called while program is idle */
void idle();
/* Put your draw functions here */
void redraw();
/* All functions for display, calls redraw
*/
void display();
/* Called when a key is pressed */
void keyEvent(unsigned
char key,int x,int
y);
/* Called when mouse button pressed */
void mouse(int
button,int state,int
x,int y);
/* Called when the mouse moves */
void mouseMotion(int
x,int y);
//----------------------------------------------------------
// USER DATA TYPES
//---------------------------------------------------------
/* The location of a single point */
typedef struct {
int x, y;
} point;
/* Struct to hold a single pixel (as three
color bytes) */
typedef struct {
unsigned char r, g, b;
/* use 256 colors */
} rgb_pixel;
//--------------------------------------
// USER FUNCTION FORWARD DECLARATIONS
//------------------------------------
void draw_lineDDA(point p0, point
p1);
//void draw_lineBres(point p0, point p1);
void draw_lineBres(int,int,int,int);
void fill_triangle(point a, point
b, point c);
void swap(int
* const, int
* const);
//-----------------------------------------------------------
// GLOBAL VARIABLES
//-----------------------------------------------------------
/* Dimensions of the screen */
#define SCREENWIDTH 600
#define SCREENHEIGHT 500
const int screenWidth = SCREENWIDTH;
const int screenHeight =
SCREENHEIGHT;
//-------------------------------------
// USER GLOBAL VARIABLES
const rgb_pixel bgcolor =
{210, 210, 255}; /* Light blue */
/* ??? other user global variables */
rgb_pixel black = {0, 0, 0};
rgb_pixel red = {255, 0, 0};
rgb_pixel green = {0, 255, 0};
rgb_pixel blue = {0,0,255};
//-------------------------------------------------
// Pixel buffer representing the whole picture
// The LOC macro converts (x,y) to an index into this buffer
rgb_pixel canvas[SCREENWIDTH * SCREENHEIGHT];
#define LOC(X,Y) ((Y)*screenWidth +
(X))
//---------------------------------------------------
// MAIN PROGRAM
// draws model, calls phantom code
int main(int
argc, char **argv) {
int i;
/* Initialize glut */
glutInit(&argc,argv);
/* Initialize GL */
initGL();
/* Makes each pixel the background color. */
for(i = 0; i < screenWidth*screenHeight; i++) {
canvas[i] = bgcolor;
}
// event loop starts here
glutMainLoop();
return 0;
}
//----------------------------------------------------------------------
// init
void initGL() {
// use red/green/blue, double
buffered
glutInitDisplayMode(GLUT_DOUBLE | GLUT_RGB );
// Set Main Graphics Window Size
glutInitWindowSize(screenWidth, screenHeight);
// Set the main Graphics Window
Position.
glutInitWindowPosition(200,100);
// the window name is an unsigned int that works
like a handle
glutCreateWindow("CS 365 Lab 1");
// initializes callbacks for glut
glutDisplayFunc(display);
glutMotionFunc(mouseMotion);
glutIdleFunc(idle);
glutMouseFunc(mouse);
glutKeyboardFunc(keyEvent);
}
//+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+
// Idle
// Sets up the idle function for glui stuff.
//+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+
void idle() {
// Redraw the contents of the
display window
glutPostRedisplay();
}
//+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+
// redraw
// Called to refresh and draw onto the screen.
//+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+
void redraw() {
//glPushMatrix();
// Put all drawing stuff
here.
// For this assignment we
just dump our pixel map to the window
/* Rows of pixel data are
all packed together, no word-alignment */
glPixelStorei(GL_UNPACK_ALIGNMENT, 1);
/* Draws the canvas array to the image buffer. */
glDrawPixels((GLsizei)screenWidth, (GLsizei)screenHeight,
GL_RGB,
GL_UNSIGNED_BYTE, canvas);
// glPopMatrix();
}
//+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+
// display
// Sets and refreshes the window and swaps buffers.
//+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+
void display() {
// Clear the buffers
glClear(GL_COLOR_BUFFER_BIT );
//Load the projection matrix
glMatrixMode( GL_PROJECTION );
// Set the projection matrix to the identity matrix
glLoadIdentity();
/* Simplest Orthographic 2D projection */
gluOrtho2D(-1.0, 1.0, -1.0, 1.0);
redraw();
// Swap the double buffers
glutSwapBuffers();
// Flush all drawing to the screen
glFlush();
}
//+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+
// keyEvent
// Registers specific input characters from the keyboard.
//+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+
void keyEvent(unsigned
char key,int x,int
y)
{
switch (key) {
// Quit
case 'Q':
case 'q':
exit(0);
break;
default:
//do
nothing on the default
break;
}
/* ??? Add other keyboard events to the above
switch as needed */
glutPostRedisplay();
}
//+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+
// mouse
// Registers when the mouse buttons are pressed.
//+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+
int i = 1;
point triangle[3];
void mouse(int
button,int state,int
x,int y)
{
if(button == GLUT_LEFT_BUTTON && state ==
GLUT_DOWN) {
/* ??? Here is where you accumulate
triangle points
* and draw a
triangle when you get all three points.
*/
//glColor3f(1.0,1.0,0.0);
if(i%3 ==
1) {
triangle[0].x = x;
triangle[0].y = screenHeight - y;
canvas[LOC(x,screenHeight - y)] = red;
}
if(i%3 == 2) {
triangle[1].x = x;
triangle[1].y = screenHeight - y;
draw_lineDDA(triangle[0],triangle[1]);
draw_lineBres(triangle[0].x,triangle[1].x,
triangle[0].y, triangle[1].y);
//draw_lineBres(triangle[0],triangle[1]);
/*glBegin(GL_LINES);
glVertex2iv(triangle[0]);
glVertex2iv(triangle[1]);
glEnd();*/
}
if(i%3 == 0) {
triangle[2].x = x;
triangle[2].y = screenHeight - y;
draw_lineDDA(triangle[1],triangle[2]);
//draw_lineBres(triangle[1],triangle[2]);
draw_lineDDA(triangle[2],triangle[0]);
draw_lineBres(triangle[1].x,triangle[2].x,
triangle[1].y, triangle[2].y);
draw_lineBres(triangle[2].x,triangle[0].x,
triangle[2].y, triangle[0].y);
//printf("color
= %s\n", "black");
//canvas[LOC(x,screenHeight - y)] = black;
/*glBegin(GL_TRIANGLES);
glVertex2iv(triangle[0]);
glVertex2iv(triangle[1]);
glVertex2iv(triangle[2]);
glEnd();*/
}
++i;
printf("i = %d\n", i);
}
if(button == GLUT_LEFT_BUTTON && state ==
GLUT_UP)
{
}
if(button == GLUT_RIGHT_BUTTON && state ==
GLUT_DOWN)
{
/* ??? Make a note that
this button is down */
}
if(button == GLUT_RIGHT_BUTTON && state ==
GLUT_UP)
{
/* ??? Make a note that
this button is back up */
}
}
//+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+
// mouseMotion
// Registers when the mouse is moved.
//+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+
void mouseMotion(int x,int
y)
{
if ((x < 0) | (x >= screenWidth) | (y < 0) |
(y >= screenHeight)) return;
/* ??? Here insert code to move triangle if
(x,y) is within
* a triangle and the
proper mouse button is down
*/
}
/* Define these functions???
void draw_line(point p0, point p1);
void fill_triangle(point a, point b, point c);
*/
void draw_lineDDA(point firstPt,
point lastPt) {
int dx = lastPt.x - firstPt.x;
int dy = lastPt.y - firstPt.y;
int steps, k;
float xIncrement, yIncrement, x = firstPt.x,
y = firstPt.y;
if(abs (dx) > abs (dy)) steps = abs (dx);
else steps = abs (dy);
xIncrement = float (dx) / float (steps);
yIncrement = float (dy) / float (steps);
canvas[LOC(int(x),int(y))] = black;
for(k = 0; k < steps; ++k) {
x += xIncrement;
y += yIncrement;
canvas[LOC(int(x),int(y))] = black;
}
}
void draw_lineBres(int
x0, int x1,
int y0, int y1) {
int xstep, ystep;
bool steep = abs(y1 - y0) > abs(x1 - x0);
if (steep) {
printf("steep");
swap(&x0, &y0);
swap(&x1, &y1);
}
int deltax = abs(x1 - x0);
int deltay = abs(y1 - y0);
int error = 0;
//int deltaerr = deltay;
int x = x0;
int y = y0;
if (x0 < x1) xstep = 1;
else xstep = -1;
if (y0 < y1) ystep = 1;
else ystep = -1;
// Plot the first point
if (steep) {
printf("x = %d",y);
printf(" y = %d\n",x);
canvas[LOC(y,x)] = blue;
}
else {
printf("x = %d",x);
printf(" y = %d\n",y);
canvas[LOC(x,y)] = red;
}
// Plot the rest of the line.
while (x != x1) {
x += xstep;
error += deltay; // add this each time
// This is the condition for increasing
y
if (2*error >= deltax) {
y += ystep;
error -= deltax;
}
if (steep) {
printf("x = %d",y);
printf(" y = %d\n",x);
canvas[LOC(y,x)] = blue;
}
else {
printf("x = %d",x);
printf(" y = %d\n",y);
canvas[LOC(x,y)] = red;
}
}
}
void swap(int
* const a,
int * const b) {
int temp = *b;
*b = *a;
*a = temp;
}
/*
void draw_lineBres(point firstPt, point lastPt) {
int dx = lastPt.x - firstPt.x;
int dy = lastPt.y - firstPt.y;
if(abs(dx) > abs(dy)) {
int p = 2*dy + dx; //initial value of p at start position
int twiceDy = 2*dy;
int twiceDyDxDiff = 2*(dy-dx);
int x,y,xEnd;
// Determine which endpoint to start at
if(lastPt.x < firstPt.x) {
x = lastPt.x;
y = lastPt.y;
xEnd = firstPt.x;
}
else {
x = firstPt.x;
y = firstPt.y;
xEnd = lastPt.x;
}
canvas[LOC(int(x),int(y))] = red;
while(x < xEnd) {
x++;
if(p < 0)
p += twiceDy;
else {
y++;
p += twiceDyDxDiff;
}
canvas[LOC(int(x),int(y))] = red;
}
}
// The next section is like the previous, only x & y are
reversed.
else {
int p = 2*dx + dy; //initial value of p at start position
int twiceDx = 2*dx;
int twiceDxDyDiff = 2*(dx-dy);
int x,y,yEnd;
// Determine which endpoint to start at
if(lastPt.y < firstPt.y) {
x = lastPt.x;
y = lastPt.y;
yEnd = firstPt.y;
}
else {
x = firstPt.x;
y = firstPt.y;
yEnd = lastPt.y;
}
canvas[LOC(int(x),int(y))] = red;
while(y < yEnd) {
y++;
if(p < 0)
p += twiceDx;
else {
x++;
p += twiceDxDyDiff;
}
canvas[LOC(int(x),int(y))] = red;
}
}
}*/
|