Get a unique result from Bresenham algorithm

Question

I want to rasterize a line using Bresenham's algorihm. My interpolated vertices shouldn't consist of diagonal steps. I did some search on StackOverflow and this topic seems to pretty much the thing I need.

The only problem I have with it is that I need to get the Same result if I changed the order of inputs, I mean if I swap the startPoint and endPoint of line I need to get the same set of interpolated vertices.

//the Method definition
List<Point> plotPoints(Point startPoint, Point endPoint);

//The thing I'm looking for
plotPoints(startPoint, endPoint)==plotPoints(endPoint, startPoint)

The code is almost same as The answer. However I did a bit customization for my purpose:

        private float step=0.5;
        public static List<Vector3> plotPoints(float x0, float y0, float x1, float y1) {
            List<Vector3> plottedPoints = new List<Vector3>();
            float dx = Mathf.Abs(x1 - x0), sx = x0 < x1 ? step : -step;
            float dy = -Mathf.Abs(y1 - y0), sy = y0 < y1 ? step: -step;
            float err = dx + dy, e2; /* error value e_xy */

            for (; ; ) {  /* loop */
                if (x0 == x1 && y0 == y1) break;
                plottedPoints.Add(new Vector3(x0,0, y0));
                e2 = 2 * err;
                if (e2 >= dy) { err += dy; x0 += sx; } /* e_xy+e_x > 0 */
                else if (e2 <= dx) { err += dx; y0 += sy; } /* e_xy+e_y < 0 */
            }

            return plottedPoints;
        }

I added the method. I need to get the same result if I swap the start and end point. — Emad, Mar 02 '18 at 01:43
Does `ants280` approach from linked topic produce the same sequence? (Yes, this is not Bresenham algo) — MBo, Mar 02 '18 at 03:09
@MBo To be honest, I didn't try that approach, But I'll give it a shot and let you know about the result. — Emad, Mar 02 '18 at 03:19
One way would be to swap the endpoints in ypur code so that you always go in increasing x (or if the x's equal in increasing y)/. That way if you swap the arguments in a call, internally the code will swap them back. — dmuir, Mar 02 '18 at 08:27
also see this [Precise subpixel line drawing algorithm](https://stackoverflow.com/a/24682318/2521214) manipulating Bresenham means changing its equation or add a lot of if cases not to mention DDA is not only simpler but also faster than Bresenham on HW at least a decade now. Bresenham was intended to speed up lines on old computer architectures. — Spektre, Mar 02 '18 at 08:33
You are taking high risks with float coordinates and tests for strict equality as the loop exit condition ! — , Mar 02 '18 at 11:45

score 2 · Answer 1 · answered Mar 04 '18 at 16:53

2

As said in the comments, a trick is to normalize the input so that if you swap the endpoints, they will be swapped back automatically.

A possible way is by enforcing that the endpoints are lexicographically ordered (the smallest X first and in case of a tie, the smallest Y).

answered Mar 04 '18 at 16:53

Yea, I already did a trick for swapping points, But you know I more look for a way to get a unique result instead of this trick, because the interpolated points should be in the initial order fo starting to endpoint, so if I swap the start and end, after I got the result, I need to reverse all points again which is a bit time to consume. – Emad Mar 04 '18 at 22:43
@Emad: loop backward (you will need to compute the final values of err and y0, which is doable). You didn't tell this requirement in your question. – Mar 05 '18 at 07:27

score 0 · Answer 2 · 2018-03-05T08:17:54.210

There is no such problem with the DDA algorithm, which can be formulated explicitly as

X = X0 + (k.DX) rnd D
Y = Y0 + (k.DY) rnd D

where D = max(|DX|, |DY|), rnd is a rounding operation and k goes from 0 to D.

If you swap the endpoints, the deltas change sign and you trade

Y0 + (k.DY) rnd D

for

Y1 + ((D-k).(-DY)) rnd D = Y1 - DY + (k.DY) rnd D = Y0 + (k.DY) rnd D.

This means that the algorithm is naturally "reversible".

For this to be true, the rnd operation must enjoy a translation invariance property, rnd(x+n) = rnd(x)+n, which corresponds to (k.DY) rnd D = floor((k.DY + S) / D) where S is some rounding offset (typically 0 or D>>1).

I didn't say that this is the way the DDA must be implemented, the incremental version still holds. I am explaining the mathematical properties. I suspect that with some care the Bresenham algorithm can get the same behavior. — , Mar 05 '18 at 08:15

Get a unique result from Bresenham algorithm

2 Answers2