2) The Bresenham algorithm seems to be limited to only integers. This isn't going to work for what I need it to do, since the line can begin in end anywhere inside a tile.
Is it possible to modify the algorithm to do these two things, or will I have to find something different? The floating point issue seems to be the biggest limitation.
Modifying the Bresenham Line Algorithm
Author
After thinking about a problem I had I realized the solution was the same thing as drawing a line. Some quick searching on Google lead me to the Bresenham algorithm, but it has a few limitations that I need to get around.
1) I need to figure out every "pixel" (tile of my game world) that is under the line, not just the ones that most closely approximate the line. A lucky hit on Google was this: http://www.ese-metz.fr/~dedu/projects/bresenham/. I understand the Bresenham algorithm, but not enough to make any sense of the article. The picture it has though shows what I need to do:
2) The Bresenham algorithm seems to be limited to only integers. This isn't going to work for what I need it to do, since the line can begin in end anywhere inside a tile.
Is it possible to modify the algorithm to do these two things, or will I have to find something different? The floating point issue seems to be the biggest limitation.
2) The Bresenham algorithm seems to be limited to only integers. This isn't going to work for what I need it to do, since the line can begin in end anywhere inside a tile.
Is it possible to modify the algorithm to do these two things, or will I have to find something different? The floating point issue seems to be the biggest limitation.
Take each squares center to be points in space. Then draw (or calculate rather) a *perpendicular* line from each point to the line. See where the perpendicular line and the origional line intersect. Do a simple bounds check to see if the intersection point is in that boxes area. Then simply repeat this on all the other boxes.
If you need help finding the algorithm try searching in these forums or on google for: Shortest distance between a point and a line ..From that you should be able to deduce everything you need =)
If you need help finding the algorithm try searching in these forums or on google for: Shortest distance between a point and a line ..From that you should be able to deduce everything you need =)
Author
That sounds like brute forcing every tile. I'm looking for a way to modify the Bresenham algorithm to do it.
extending the algorithm for fractional values in the minor direction:
subdivide the pixel finely enough in the minor direction, in n sub-pixels (not in memory). the beginning and the end point must be rounded to the sub pixel boundaries. then you can do the bresenham computations by multiplying all numbers in the bresenham algorithm by n, so all numbers are integers again.
extending this for fractional values also in the major direction:
you only need to compute the intersections of the line with lines parallel to the the minor direction passing through the start and the end point and then use this values as start and end points like in the above paragraph. it's possible that these intersections are already in the pixel above (if x (horizontal, to the right) is the major direction and increments are negative (y vertically pointing down) like in the picture you posted with the left points being the start), i think you have to do special handling here (painting the original start pixel and moving the start pixel to the pixel above for the loop).
(i just notice the green Bresenham line doesn't seem to be correct in your picture if you look at the pixels at the left end)
painting every pixel:
if you select the pixel not lying diagonally to current pixel in a Bresenham iteration, do nothing special.
If you select the one lying diagonally, you have either to color the pixel to the right or above (or the according pixels in the other octants) the current pixel or none of the two if the line goes exactly through the point where the 4 pixels meet. to decide this, you have to do a kind of half-step to get to the pixel boundary: Add only ddy/2; then paint the pixel above if error is bigger than ddx, paint the pixel right if error is smaller, paint none of them if error is exactly ddx.
subdivide the pixel finely enough in the minor direction, in n sub-pixels (not in memory). the beginning and the end point must be rounded to the sub pixel boundaries. then you can do the bresenham computations by multiplying all numbers in the bresenham algorithm by n, so all numbers are integers again.
extending this for fractional values also in the major direction:
you only need to compute the intersections of the line with lines parallel to the the minor direction passing through the start and the end point and then use this values as start and end points like in the above paragraph. it's possible that these intersections are already in the pixel above (if x (horizontal, to the right) is the major direction and increments are negative (y vertically pointing down) like in the picture you posted with the left points being the start), i think you have to do special handling here (painting the original start pixel and moving the start pixel to the pixel above for the loop).
(i just notice the green Bresenham line doesn't seem to be correct in your picture if you look at the pixels at the left end)
painting every pixel:
if you select the pixel not lying diagonally to current pixel in a Bresenham iteration, do nothing special.
If you select the one lying diagonally, you have either to color the pixel to the right or above (or the according pixels in the other octants) the current pixel or none of the two if the line goes exactly through the point where the 4 pixels meet. to decide this, you have to do a kind of half-step to get to the pixel boundary: Add only ddy/2; then paint the pixel above if error is bigger than ddx, paint the pixel right if error is smaller, paint none of them if error is exactly ddx.
Author
I have no clue what you are saying, but whatever it is, thanks! You made me realize that all I have to do is calculate where the ray hits the edge of the tile. Both sides of that edge will contain the ray...that's all there is to it. [smile]
Well, looking at your picture for a second, I worked out a fairly simple method, which I *think* should work universally.
I don't really want to talk about major and minor axises here, so we can just assume that when I say in the y-axis, I mean the minor axis, and x-axis is the major axis. I'm doing it like that because it responds to the OP's diagram. deltaY = maxY - minY, deltaX = maxX - minX.
First off, we must understand that the only difference between your desired output, and the Bresenham algo, is that two pixels must sometimes (usually) be drawn in the y-axis instead of one. The added pixel will either be above or below the output returned by the Bresenham algo, or only one pixel will be drawn. To relate this to the diagram, there is only one pixel drawn at the endpoints, and 2 pixels drawn in the y-axis for every other point.
To determine whether the added pixel will be above, below, or not drawn, we must make liberal use of (deltaY * i) MOD deltaX. i would be your iterator as you go along each pixel in the major axis.
That big if statement is a bit hard to follow, I'll try to explain with an example. Here's a listing of (deltaY * i) % (deltaX) for the OP's diagram (deltaY = 8, deltaX = 11)
0, 8, 5, 2, 10, 7, 4, 1, 9, 6, 3, 0
You can see that the endpoints are 0, which validates the first if statement, and the 2nd if statement (I don't want to explain it TOO fully) means that when the differences between the two pairs preceding the pixel you're drawing have different signs, you must add a pixel below where you're drawing. Example:
0, 8, (5, 2, 10), 7, 4, 1, 9, 6, 3, 0
0, 8, 5, (2, 10, 7), 4, 1, 9, 6, 3, 0
0, 8, 5, 2, 10, 7, (4, 1, 9), 6, 3, 0
0, 8, 5, 2, 10, 7, 4, (1, 9, 6), 3, 0
The third number in each of those triplets will need to have a pixel added below the Bresenham-returned result, the others will have a pixel added above, and the 0's means only one pixel will be drawn.
I hope this was clear enough, and I hope my code isn't broken.
I don't really want to talk about major and minor axises here, so we can just assume that when I say in the y-axis, I mean the minor axis, and x-axis is the major axis. I'm doing it like that because it responds to the OP's diagram. deltaY = maxY - minY, deltaX = maxX - minX.
First off, we must understand that the only difference between your desired output, and the Bresenham algo, is that two pixels must sometimes (usually) be drawn in the y-axis instead of one. The added pixel will either be above or below the output returned by the Bresenham algo, or only one pixel will be drawn. To relate this to the diagram, there is only one pixel drawn at the endpoints, and 2 pixels drawn in the y-axis for every other point.
To determine whether the added pixel will be above, below, or not drawn, we must make liberal use of (deltaY * i) MOD deltaX. i would be your iterator as you go along each pixel in the major axis.
if (((deltaY * i) % deltaX) == 0){//no added pixel}else if ((((deltaY * i) % deltaX)-((deltaY * (i-1))) % deltaX) * (((deltaY * (i-1)) % deltaX)-((deltaY * (i-2)) % deltaX)) < 0){//add pixel below Bresenham line}else{//add pixel above Bresenham line}That big if statement is a bit hard to follow, I'll try to explain with an example. Here's a listing of (deltaY * i) % (deltaX) for the OP's diagram (deltaY = 8, deltaX = 11)
0, 8, 5, 2, 10, 7, 4, 1, 9, 6, 3, 0
You can see that the endpoints are 0, which validates the first if statement, and the 2nd if statement (I don't want to explain it TOO fully) means that when the differences between the two pairs preceding the pixel you're drawing have different signs, you must add a pixel below where you're drawing. Example:
0, 8, (5, 2, 10), 7, 4, 1, 9, 6, 3, 0
0, 8, 5, (2, 10, 7), 4, 1, 9, 6, 3, 0
0, 8, 5, 2, 10, 7, (4, 1, 9), 6, 3, 0
0, 8, 5, 2, 10, 7, 4, (1, 9, 6), 3, 0
The third number in each of those triplets will need to have a pixel added below the Bresenham-returned result, the others will have a pixel added above, and the 0's means only one pixel will be drawn.
I hope this was clear enough, and I hope my code isn't broken.
This is basically what Wolfenstein 3D did to find out what to draw. It's called raycasting. Wolf3D used a ray for each vertical line/column on the screen and calculated intersections between the ray and the walls on a 2D map.
It should be pretty easy to do. If you need any help, take a look at some of the old raycasting tutorials out there (Peroxide had one...)
It should be pretty easy to do. If you need any help, take a look at some of the old raycasting tutorials out there (Peroxide had one...)
So what exactly are you going to use this for, Raloth? Perhaps there is an alternate approach to solve your problem.
do Bresenham's twice, one each way (start->end, end->start). Its something I vaguely remember whilst doing my own research on bresenham, which may or may not work.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
