Jump to content
  • Advertisement
Sign in to follow this  
Servant of the Lord

Trouble with line algorithm

This topic is 3836 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm having some trouble with a line plotting algorithm I found on Wikipedia. At certain angles, it doesn't draw properly. The function was actually taken off the discussion page of wikipedia, and here it is in it's entirety:
Function drawLine(x1, y1, x2, y2)
   int dX = Abs(x2 - x1)
   int dY = Abs(y2 - y1)
   int x = x1
   int y = y1

   If (x1 > x2) Then offsetX = -1 Else offsetX = 1
   If (y1 > y2) Then offsetY = -1 Else offsetY = 1

   SetPixel(x,y)

   If (dX > dY) Then
       int error = dX / 2

       While (x != x2)
           error = error - dY

           If (error < 0)
               y = y + offsetY
               error = error + dX
           End If

           x = x + offsetX

           SetPixel(x,y)
       Wend
   Else
       int error = dY / 2

       While (y != y2)
           error = error - dX

           If (error < 0)
               x = x + offsetX
               error = error + dY
           End If

           y = y + offsetY

           SetPixel(x,y)
       Wend
   End IF
   End If
End Function
I converted it to C++, and it now looks like this: (It's part of a class)
void Line::SetPoints(LinePoint start, LinePoint end)
{
	startingPoint = start;
	endingPoint = end;
	
	currentPoint = start;
	
	deltaIncrement.x = 0; deltaIncrement.y = 0;
	offsetPoint.x = 0; offsetPoint.y = 0;
	
	this->_ConfigurePoints();
}

void Line::_ConfigurePoints()
{
	deltaIncrement.x = abs(endingPoint.x - startingPoint.x);
	deltaIncrement.y = abs(endingPoint.y - startingPoint.y);
	
	if(startingPoint.x > endingPoint.x)
		offsetPoint.x = -1;
	else
		offsetPoint.x = 1;
	
	if(startingPoint.y > endingPoint.y)
		offsetPoint.y = -1;
	else
		offsetPoint.y = 1;
	
	if(deltaIncrement.x > deltaIncrement.y)
		error = deltaIncrement.x / 2;
	else
		error = deltaIncrement.y / 2;
}

void Line::Traverse(LineFunctionPointer *callback)
{
	if(!callback)
		return;
	
	LinePoint currentPoint = startingPoint;
	
	if((*callback)(&currentPoint) == true)
		return;
	
	if(deltaIncrement.x > deltaIncrement.y)
	{
		while(currentPoint.x != endingPoint.x)
		{
			error -= deltaIncrement.y;
			
			if(error < 0)
			{
				currentPoint.y += offsetPoint.y;
				error += deltaIncrement.x;
			}
			
			currentPoint.x += offsetPoint.x;
			
			if((*callback)(&currentPoint) == true)
				return;
		}
	}
	else
	{
		while(currentPoint.y != endingPoint.y)
		{
			error -= deltaIncrement.x;
			
			if(error < 0)
			{
				currentPoint.x += offsetPoint.x;
				error += deltaIncrement.x;
			}
			
			currentPoint.y += offsetPoint.y;
			
			if((*callback)(&currentPoint) == true)
				return;
		}
	}
}

The callback function isn't the problem, it works fine. But here are some images knocked up in MSPaint of what's going wrong: In this image, the black square is the starting spot, and the green square is where I told it to go. Instead, it went diagonally down the red line, until it was level with the green square. If you break a circle up into 8 sections, as shown below, the lines draw fine in half of them.(The green segments draw fine, the red do not) I would have thought that the 'else' part of the if statement:
if(deltaIncrement.x > deltaIncrement.y)
{
    //While loop...
}
else
{
    //While loop...
}
Deals with steep lines. What did I do wrong to the code? Here's a actual shot of the line drawing: The green dot is where it is supposed to end at, the red dot is where it starts at. Here's two more examples: I recall having a similar or identical problem in the past, but that was on my old computer, and I've been having trouble finding my source code to most my older projects since I moved them over. Any help that can be offered would be apreciated. On a completely unrelated note, I once again spent 2 hours trying to find a bug that turned out to be an extra semi-colon ; in my code. It was driving me crazy.[lol]

Share this post


Link to post
Share on other sites
Advertisement
I knew it was a stupid mistake I made, I just couldn't see where! At least it's not another semicolon. [smile] That fixed the problem. I was getting annoyed at my sprites not moving properly, thank you!

Share this post


Link to post
Share on other sites
Yep, looks like a particularly strange case of this problem. :)

The way to avoid this kind of thing is to eliminate the code duplication, so that there's nowhere to forget to swap x and y. In C++, we can do this by using references to alias the x and y directions, or (as shown) by (conditionally) swapping the data around to a consistent order, and swapping it back at the end. It's still possible to mess up, but the code that can mess up is localized and minimized.

Also, why not initialize things with a constructor? :) With a few other stylistic cleanups, you could have something like:


Line::Line(const Position& start, const Position& end) : start(start), end(end), deltaIncrement(end - start)
{
// the old 'currentPoint' should not be a member, since the concept is only
// used in Traverse(), where it's a local anyway. Also, you should have a
// constructor and math operators for your Position and Direction objects
// (which could be a typedef to the same thing, or could have carefully
// chosen operator overloads designed to avoid semantic errors).

// Notice that a lot of the absolute-value taking and sign-calculating
// turns out strictly unnecessary... it's just to simplify understanding
// of the math. But actually there's nothing to set up here :)

// Unless, of course, I messed up. It's possible at least ;)
}

// why pass by pointer? :)
void Line::Traverse(const LineFunctionPointer& callback)
{
LinePoint current = start;

// ... either way? :)
if ((callback)(current)) { return; }

bool steep = abs(deltaIncrement.x) > abs(deltaIncrement.y);

// 'error' should be reset for each traversal, so it belongs as a local here.
int d_major = steep ? deltaIncrement.x : deltaIncrement.y;
int d_minor = steep ? deltaIncrement.y : deltaIncrement.x;

int error = d_major / 2;

// We use references here because we want to be able to "write back" to current and end.
int& current_major = steep ? current.x : current.y;
int& current_minor = steep ? current.y : current.x;

int& end_major = steep ? end.x : end.y;
int& end_minor = steep ? end.y : end.x;

while (current_major != end_major) {
error -= d_minor;

// This is the tricky part... we want to check when error "crosses" zero.
if ((d_minor > 0) ? (error < 0) : (error > 0)) {
current_minor += (current_minor < end_minor) ? 1 : -1;
error += d_major;
}

current_major += (current_major < end_major) ? 1 : -1;

if ((callback)(current)) { return; }
}
}

Share this post


Link to post
Share on other sites
Quote:
Original post by Zahlman
Yep, looks like a particularly strange case of this problem. :)

Yeah, that's exactly what happened. Unfortunately, it doesn't offer a good method of avoiding it, as far as I can see.

Quote:
The way to avoid this kind of thing is to eliminate the code duplication, so that there's nowhere to forget to swap x and y. In C++, we can do this by using references to alias the x and y directions, or (as shown) by (conditionally) swapping the data around to a consistent order, and swapping it back at the end. It's still possible to mess up, but the code that can mess up is localized and minimized.

I'll do that, that's a good idea. I rarely use references, so it'll be good for me to use them here to get more familiar with them. I don't see the benefit in passing the callback by reference as opposed to a pointer, though. Why do it that way?

Quote:
Also, why not initialize things with a constructor? :)

Actually, I didn't post the entire class. I had already isolated the bug to Traverse(), and didn't want to just toss my entire code at someone for them to shift through, wasting their time.
The class does optionally initialize using the constructor, or else the constructor sets default values. I want to be able to change the positions of the line later, which is why I have the SetPoints() function. If you decide to initialize it in the constructor, it just calls the SetPoints() function.
Quote:
// the old 'currentPoint' should not be a member, since the concept is only
// used in Traverse(), where it's a local anyway.

'currentPoints' is important, because the class also has a way to step through the line at your own leisure, instead of all at once like Traverse() does. 'error' is needed as a member of the class for the same reason. Traverse() uses 'currentPoints' locally, so you can Step() through the line, and halfway through Traverse() the line, without messing up Step(). The same bug was happening to both Traverse() and Step(), so I posted the function that had all the code in one spot.

My entire class looks like this:
#ifndef LINE_H
#define LINE_H

struct LinePoint
{
int x;
int y;
};

LinePoint NewLinePoint(int x, int y);

typedef bool (LineFunctionPointer)(LinePoint *point);

class Line
{
private:
//Where the line starts.
LinePoint startingPoint;
//Where the line ends.
LinePoint endingPoint;
//The amount to increment the current position by, on each 'step'.
LinePoint deltaIncrement;
//Used to offset the line when calculating the next point.
LinePoint offsetPoint;
//The current position along the line.
LinePoint currentPoint;

//Used by the Step() function.
int error;

void _ConfigurePoints();

public:
Line::Line();
Line::Line(LinePoint start, LinePoint end);
Line::~Line();

//Starts a new line, with a new starting and ending point.
void SetPoints(LinePoint start, LinePoint end);
//Steps along the line 'x' times, where x is 'steps'. Returns false if it reaches the end
//of the line. 'point' points to where the line stopped.
bool Step(LinePoint *point, int steps = 1);
//Returns the point where the line is currently at.
LinePoint GetLastStep();
//Resets the point where the line is currently, back to the starting point.
void Reset();
//Switches the direction the line traverses. (From foreward to backward, or vice versa)
//You may want to call Reset() afterward, to reset the current step, depending on your needs.
//This actually just swaps the ending and starting points.
void Reverse();

//Used to loop through the entire line at one time, calling the callback function on each step.
//If the callback returns true, the function will end.
void Traverse(LineFunctionPointer *callback);
//Used to loop through the line backward, calling the callback function on each step.
//If the callback returns true, the function will end.
void ReverseTraverse(LineFunctionPointer *callback);
};

#endif /* LINE_H */



#include "Line.h"

LinePoint NewLinePoint(int x, int y)
{
LinePoint newPoint;
newPoint.x = x;
newPoint.y = y;
return newPoint;
}

int abs(int value)
{
if(value > 0)
return value;
else
return -value;
}

/////////////////////////////////////////////////////////////////////////////////////////////

Line::Line()
{
startingPoint.x = 0; startingPoint.y = 0;
endingPoint.x = 0; endingPoint.y = 0;
deltaIncrement.x = 0; deltaIncrement.y = 0;
offsetPoint.x = 0; offsetPoint.y = 0;
currentPoint.x = 0; currentPoint.y = 0;
error = 0;
}

Line::Line(LinePoint start, LinePoint end)
{
this->SetPoints(start, end);
}

Line::~Line()
{

}

//Starts a new line, with a new starting and ending point.
void Line::SetPoints(LinePoint start, LinePoint end)
{
startingPoint = start;
endingPoint = end;

currentPoint = start;

deltaIncrement.x = 0; deltaIncrement.y = 0;
offsetPoint.x = 0; offsetPoint.y = 0;

this->_ConfigurePoints();
}

//Steps along the line 'x' times, where x is 'steps'. Returns false if it reaches the end
//of the line. 'point' points to where the line stopped.
bool Line::Step(LinePoint *point, int steps)
{
if(point)
*point = currentPoint;

for(int i = 0; i < steps; i++)
{
if(deltaIncrement.x > deltaIncrement.y)
{
if(currentPoint.x != endingPoint.x)
{
error -= deltaIncrement.y;

if(error < 0)
{
currentPoint.y += offsetPoint.y;
error += deltaIncrement.x;
}

currentPoint.x += offsetPoint.x;
}
else
return false;
}
else
{
if(currentPoint.y != endingPoint.y)
{
error -= deltaIncrement.x;

if(error < 0)
{
currentPoint.x += offsetPoint.x;
error += deltaIncrement.y;
}

currentPoint.y += offsetPoint.y;
}
else
return false;
}
}

return true;
}

//Returns the point where the line is currently at.
LinePoint Line::GetLastStep()
{
return currentPoint;
}

//Resets the point where the line is currently, back to the starting point.
void Line::Reset()
{
currentPoint = startingPoint;
}

//Switches the direction the line traverses. (From foreward to backward, or vice versa)
//You may want to call Reset() afterward, to reset the current step, depending on your needs.
//This actually just swaps the ending and starting points.
void Line::Reverse()
{
LinePoint tempPoint = startingPoint;
startingPoint = endingPoint;
endingPoint = tempPoint;

this->_ConfigurePoints();
}

//Used to quickly loop through the entire line at one time, calling the callback function on each step.
void Line::Traverse(LineFunctionPointer *callback)
{
if(!callback)
return;

LinePoint currentPoint = startingPoint;

if((*callback)(¤tPoint) == true)
return;

if(deltaIncrement.x > deltaIncrement.y)
{
while(currentPoint.x != endingPoint.x)
{
error -= deltaIncrement.y;

if(error < 0)
{
currentPoint.y += offsetPoint.y;
error += deltaIncrement.x;
}

currentPoint.x += offsetPoint.x;

if((*callback)(¤tPoint) == true)
return;
}
}
else
{
while(currentPoint.y != endingPoint.y)
{
error -= deltaIncrement.x;

if(error < 0)
{
currentPoint.x += offsetPoint.x;
error += deltaIncrement.y;
}

currentPoint.y += offsetPoint.y;

if((*callback)(¤tPoint) == true)
return;
}
}
}

//Used to loop through the line backward, calling the callback function on each step.
void Line::ReverseTraverse(LineFunctionPointer *callback)
{
this->Reverse();
this->Traverse(callback);
this->Reverse();
}

void Line::_ConfigurePoints()
{
deltaIncrement.x = abs(endingPoint.x - startingPoint.x);
deltaIncrement.y = abs(endingPoint.y - startingPoint.y);

if(startingPoint.x > endingPoint.x)
offsetPoint.x = -1;
else
offsetPoint.x = 1;

if(startingPoint.y > endingPoint.y)
offsetPoint.y = -1;
else
offsetPoint.y = 1;

if(deltaIncrement.x > deltaIncrement.y)
error = deltaIncrement.x / 2;
else
error = deltaIncrement.y / 2;
}



I'll definitely rewrite it to use references as you showed. I particularily didn't like the double 'while' loop much. Thanks for the tips!

Share this post


Link to post
Share on other sites
Quote:
Original post by Servant of the Lord
I don't see the benefit in passing the callback by reference as opposed to a pointer, though. Why do it that way?


The usual safety benefits. Not having to check for null, etc.

Quote:
I want to be able to change the positions of the line later, which is why I have the SetPoints() function. If you decide to initialize it in the constructor, it just calls the SetPoints() function.


Why not just make a new object? Or use an operator=?

Quote:
'currentPoints' is important, because the class also has a way to step through the line at your own leisure, instead of all at once like Traverse() does.


Fair. A really awesome interface, though, would be to return an iterator that steps along the line when you use ++ and --. :) Then you don't need a Traverse(); you just use std::for_each. You can do this by moving the data members of Line used for the traversal into a nested Line::iterator, and implementing operator++ in terms of Step(). (Bidirectional and/or random access iteration are left as an exercise.) Then Line::begin() creates a Line::iterator with currentPoint set to startingPoint, for example. The operator* would need to return the current position - e.g. a const reference to the iterator's .currentPoint.

Share this post


Link to post
Share on other sites
Quote:
Original post by Zahlman
Quote:
I want to be able to change the positions of the line later, which is why I have the SetPoints() function. If you decide to initialize it in the constructor, it just calls the SetPoints() function.

Why not just make a new object? Or use an operator=?

I don't quite see the point in doing that. I could use the operator=, I suppose. It just seems proper the way I'm doing it. I want to be able to change it later, because I use the Line as a member of another class, to plot out the path to move a ship along. Every so often, whenever the player decides to move that ship, I need to change the Line's starting location to the ship's current location, and the Line's ending point, to where the player right-clicked.

I could do:
Line x = Line(NewLinePoint(locX,locY), NewLinePoint(clickX,clickY));

But I prefer this better:
x.SetPoints(NewLinePoint(locX,locY), NewLinePoint(clickX,clickY));

I still initialize like this though:
Line x(NewLinePoint(locX,locY), NewLinePoint(clickX,clickY));

(Except in the class, since there's nothing to initialize it with, until it's needed)
Quote:
A really awesome interface, though, would be to return an iterator that steps along the line when you use ++ and --. :) Then you don't need a Traverse(); you just use std::for_each. You can do this by moving the data members of Line used for the traversal into a nested Line::iterator, and implementing operator++ in terms of Step().

Hmm, I like that idea alot. I'll want to remake the Line class like that once I finish my current game, but what I have currently, thanks to you and DekuTree64, works fine and is fairly neat as it is.

I really do need to brush up on my referencing, though. I've completely forgotten(or else didn't know) that you can't reassign a reference. [smile] I've pretty much never used it since I first learned of it, and so I've lost that knowledge.

Share this post


Link to post
Share on other sites
Quote:
Original post by Servant of the Lord
I could do:
Line x = Line(NewLinePoint(locX,locY), NewLinePoint(clickX,clickY));


That isn't an assignment, it's a copy-construction of the temporary Line on the RHS. 'x = Line(NewLinePoint(locX,locY), NewLinePoint(clickX,clickY));' is what you're looking for.

Quote:

But I prefer this better:
x.SetPoints(NewLinePoint(locX,locY), NewLinePoint(clickX,clickY));


Could I see the context in which you need to do this, though?

Quote:

I really do need to brush up on my referencing, though. I've completely forgotten(or else didn't know) that you can't reassign a reference.


Only to be expected: the reference is the value, semantically, and syntactically, assigning to the reference assigns to the referred-to value.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!