1
$\begingroup$

I've been working with Bresenham’s Algorithm in 2D and understand it is derived from the following logic:

y = mx+c

To get the slope error at a given point, the following equation is used:

d2 is the distance from value Y to the whole integer above. d1 is the distance from value Y to the whole integer below.

d1 - d2 = [m(xₖ+1)+c - yₖ]-[yₖ+1-m(xₖ+1)+c]

  • If d1 - d2 < 0, the next pixel should be (xₖ+1, yₖ)
  • If d1 - d2 >= 0, then the next pixel should be (xₖ+1, yₖ+1)

This gets turned into and reduce to the following equation to remove the m variable.:

Pk = 2∆y(xₖ) - 2∆x(yₖ) + 2∆y + 2∆xc - ∆x

The initial value of the error is:

c = y1 - (∆y/∆x)*x₁

enter image description here

With the loops step increasing this decision value by:

enter image description here

The actual value of next is calculated by plugging in (xₖ+1, yₖ+1) and (xₖ+1, yₖ) and subtracting Pknext - Pk. If this value is less than zero, we choose (xₖ+1, yₖ).

When (xₖ+1, yₖ+1) and (xₖ+1, yₖ) are plugged into Pknext, they end up simplifying to 2(∆y-∆x) and 2∆y.

This simplifies this logic into:

Constraints
x₁ < x₂
y₁ < yx₂
∆y/∆x ≤ 1
Given x₁, y₁, x₂, y₂ 
∆x = x₂ - x₁
∆y = y₂ - y₁
P = 2∆y - ∆x # Inital Decision value
while x ≤ x₂
    x = x+1
    IF P  < 0
        Plot(x,y)
        P  = P + 2∆y # Decision value of East
    ELSE
        Plot(x,y+1)
        P  = P + 2∆y - 2∆x # Decision value of North East

How is this logic applied in 3D?

I found this article by geeks for geeks: https://www.geeksforgeeks.org/bresenhams-algorithm-for-3-d-line-drawing/

But it never explained how the math is derived. We can get the value of Y by simply using mx+b and calculating the decision variable from there, but how is the decision variable done in 3D?

$\endgroup$

1 Answer 1

1
$\begingroup$

I will first explain a closely related line drawing algorithm in 2D.

The parametric equation of a continuous line can be written vectorially

P = P0 + t.∆P

where t runs from 0 to 1.

If we want to discretize in such a way that the pixels are contiguous, the increment of t must be the smallest of 1/∆x and 1/∆y, let 1/∆, and we compute the points

Pi = P0 + i.∆P/∆.

Assuming that ∆=∆x, this is

Pix = P0x + i
Piy = P0y + i.∆y/∆x.

(i runs from 0 to ∆x)

For efficiency, the division of i.∆y by ∆x can be done incrementally by keeping the quotient and the remainder (i.∆y = q.∆x + r); for a new i, we add ∆y to the remainder and if it exceeds ∆x, we fix by subtracting ∆x and incrementing the quotient. This explains the if statement in Bresenham, which chooses between a lateral (east) or diagonal (north-east) move.

x+= 1 // East
r+= ∆y
if r ≥ ∆x
    r-= ∆x; y+= 1 // North

Now the generalization to 3D is immediate: choose ∆ = max(∆x, ∆y, ∆z) and, assuming ∆=∆x,

Pix = P0x + i
Piy = P0y + i.∆y/∆x
Piz = P0z + i.∆z/∆x.

A complete discussion must involve the signs of the deltas.

$\endgroup$
1
  • $\begingroup$ Thank you, I was successfully able to create a 3D algorithm with this technique. In the 2D version, both slopes under and over 1 can naturally be calculated with no coordinate swapping. In the 3D version, the same is true. In the 2D algorithm, if x1 is greater than x2, the coordinates need to be swapped. In 3D, this swap isn't as simple. If the algorithm goes from (0,0,6) to (10,5,5), should the y values be swapped at the start, calculated, and then all y values swapped at the end for all points? $\endgroup$
    – M. Nicol
    Jul 30 at 17:58

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.