1
$\begingroup$

I'm having trouble understanding the mechanics of the midpoint algorithm. I understand the gist of what it does; it keeps us within a half a pixel of where the actual line should be printed. It does this by updating this $d$ value for each pixel that we traverse.

However, even after drawing some samples and observing what the $d$ value does, I can't figure out the true inner workings of it, and how updating it by these $\Delta_e$ and $\Delta_{ne}$ symbols (which are also a bit of a mystery to me) keeps our pixel placement in check.

Can someone summarize it in simple terms for the good of all humanity?

The Algorithm:

Line (x1, y1, x2, y2)
    begin
    int x, y, dx, dy, d, deltaE, deltaNE;
    x <- x1;        y  <- y1;
    dx <- x2 - x1;  dy <- y2 - y1;
    d <- 2*dy - dx;
    deltaE <- 2*dy;     deltaNE <- 2*(dy - dx);

    PlotPixel(x, y);
    while ( x < x2) do
        if (d < 0) then
        begin
            d <- d + deltaE;
            x <- x + 1;
        end;
        else begin
            d <- d + deltaNE;
            x <- x + 1;
            y <- y + 1;
        end;
        PlotPixel (x, y);
    end;
end;
$\endgroup$
  • 1
    $\begingroup$ It appears that you copied the algorithm from somewhere else, but you didn't mention the source. StackExchange's policy is that copying of substantial material from other sources requires proper attribution, so I suggest that you attribute the source of the algorithm. Remember, quoting or copying from others always requires suitable attribution of your source. See, e.g., meta.stackexchange.com/q/160077/160917 and meta.stackexchange.com/q/160071/160917. (It is also your responsibility to check whether you have permission to make this available under cc-wiki copyright.) $\endgroup$ – D.W. Nov 19 '13 at 19:06
  • $\begingroup$ I voted to close as off topic. See help: Questions about how a particular piece of software or hardware works aren't science. $\endgroup$ – Guy Coder Dec 20 '13 at 0:37
  • 2
    $\begingroup$ It's not a question about how a particular piece of software works: it's a well-known, generic algorithm in computer graphics. $\endgroup$ – David Richerby Dec 20 '13 at 9:22
  • 1
    $\begingroup$ I do not understand the close votes. The P.O. is asking for more information on a specific algorithm, which is clearly described. Why should this question be off topic? $\endgroup$ – J.-E. Pin Dec 26 '13 at 9:55
1
$\begingroup$

This is not a self-contained answer, but you can find all the details and pictures in the link below. However, I'll give a summary of the idea behind this algorithm.

Take $F(x,y) = (x-x_1)dy - (y-y_1)dx$ as the line function. Let $p=(x_p,y_p)$ be the last pixel we turned on, then $m=(x_p+1,y_p+0.5)$ is the point exactly between the right and the right-top neighbouring pixels. This is the middle point as the title suggests.

Now, if $F(x_m,y_m) > 0$ then the line is above $m$ and if $F(x_m,y_m) < 0$ then it is below $m$, otherwise the line passes through $m$. In the first case we turn on the pixel above the midpoint (i.e. top-right of $p$), and the pixel bellow $m$ (right of $p$) for the second case, and an arbitrary one for the third case.

$d$ initially is the value of $2.F(x,y)$ for the first midpoint (the reason for doubling it to get an integer and avoid floating point calculations), so $d$ is guiding us which direction (N or NE) we should go next. At each iteration instead of recalculating $d$, depending on our last choice of direction we just need to add $\Delta_{NE}$ or $\Delta_E$ to get the new value for $d$.

http://www.dgp.toronto.edu/~karan/courses/csc418/fall_2002/notes/lines.html

I hope it helps.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.