Working with Bresenham's algorithm in 3D

I am currently working on a program that uses Bresenham’s line algorithm in order to plot the points between two 3D points.

I found the following article from geeksforgeeks which describes the process of the algorithm. The conditional logic provided only works for the X-Driving axis.


Image of Bresenham X-Drive Instructions from geeksforgeeks

How would I change the else if logic in order to account for a y or z driving axis? I don’t completely understand why math works, but I need to use it for a program I am writing.

The values of pk+1 would be the following for plotting with a y-axis drive (my best guess):

(x, y+1, z)
(x+1, y+1, z)
(x+1, y+1, z+1)
(x, y+1, z+1)

When it comes to condiations:

pyk < 0 and pzk < 0 (x-drive)

Would change into:

pxk < 0 and pzk < 0 (y-drive)

However, a condiation such as:

pyk > 0 and pzk < 0 (x-drive)

Could have two possiblities:

pxk > 0 and pzk < 0 (y-drive)

or

pxk < 0 and pzk > 0 (y-drive)

How would I know which one to pick?

The geeksforgeeks website provides a working python program (with code) that uses different logic to accomplish the same result, but I am not sure if converting that program into JS is considered plagiarism.


If you are interested in the program I have so far created to test this, here is it below:

I have so far created a javascript program to follow this algorithm, but have so far only programmed it for x-drive. Note: This repl.it has a 2d variant at the top and at the bottom has a 3d variant which is what I am currently working on.

https://replit.com/@Michael_Nicol/Bresenhams-Algorithm#index.js

let p1 = [0, 0, 0]
let p2 = [20, 20, 10]
// Highest value of x will activate the x -drive, highest value of y will activate the y drive, etc in the p2 coordinate. Best to keep p1 0 for now.
function brensen3d(p1, p2) {
  let dx = Math.abs(p2[0] - p1[0])
  let dy = Math.abs(p2[1] - p1[1]) 
  let dz = Math.abs(p2[2] - p1[2])
  let xc = p2[0] > p1[0] ? 1 : -1
  let yc = p2[1] > p1[1] ? 1 : -1
  let zc = p2[2] > p1[2] ? 1 : -1
  let pointList = [[...p1]]
  let pk = [...p1]
  console.log(dx, dy, dz)
  if (dx >= dy && dx >= dz) {
    console.log("dx drive")
    let pyk = (2 * dy) - dx
    let pzk = (2 * dz) - dx
    for (let k = 0; k < dx - 1; k++) {
      pk[0] += xc
      pyk += (2 * dy)
      pzk += (2 * dz)
      if (pyk > 0 && pzk < 0) {
        pk[1] += yc;
        pyk -= (2 * dx)
      } else if (pyk === 0) {
        pk[2] += zc;
        pzk -= (2 * dx)
      } else {
        pk[1] += yc;
        pk[2] += zc;
        pyk -= (2 * dx)
        pzk -= (2 * dx)
      }
      pointList.push([...pk])
    }
  } else if (dy >= dx && dy >= dz) {
    console.log("dy drive")
    let pxk = (2 * dx) - dy
    let pzk = (2 * dz) - dy
    for (let k = 0; k < dy - 1; k++) {
      pk[1] += yc
      pxk += (2 * dx)
      pzk += (2 * dz)
      if (pxk < 0 && pzk < 0) {
        // condiation body
      }
      // missing condiation
      pointList.push([...pk])
    }
  } else if (dz >= dy && dz >= dx) {
    console.log("dz drive")
    let pxk = (2 * dx) - dz
    let pyk = (2 * dy) - dz
    for (let k = 0; k < dz - 1; k++) {
      pk[2] += zc
      pxk += (2 * dx)
      pyk += (2 * dy)
      if (pxk < 0 && pyk < 0) {
         // conditaion body
      }
      // missing condiation
      pointList.push([...pk])
    }
  }
  pointList.push([...p2])
  return pointList
}

I also asked this question on math stack overflow

But I am not sure if that is the correct place to receive a response.

This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.