0

I want to get all the x,y,z coordinates between 2 given points, on a straight line. I need to be able to do this in JavaScript for checking whether a projectile collides in my game.

So, for example:

Point 1: (0,0,0) Point 2: (2,2,2) -> 0,0,0 - 1,1,1, 2,2,2

Edit, here is working code for anybody who is lost. 

def ROUND(a):

return int(a + 0.5)

def drawDDA(x1,y1,z1,x2,y2,z2):

x,y,z = x1,y1,z1

length = (x2-x1) if (x2-x1) > (y2-y1) else (y2-y1) if (y2-y1) > (z2-z1) else (z2-z1)

dx = (x2-x1)/float(length)

dy = (y2-y1)/float(length)

dz = (z2-z1)/float(length)

print (ROUND(x),ROUND(y),ROUND(z))

for i in range(length):

    x += dx
    z += dz
    y += dy

    print(ROUND(x),ROUND(y),ROUND(z))

drawDDA(0,1,2,10,11,12)

Timothy Relson
  • 13
  • 2

2 Answers2

0

Your current approach will need to deal with quadrants in 2D and octants in 3D which is pain in the ass. if you use DDA instead (which is very similar) you will get rid of that. So:

P(t) = P0 + t*(P1-P0)
t=<0.0,1.0

This is also called Linear Interpolation. As there are infinite number of points P(t) between your two endpoints P0,P1 I assume you want just integer ones (representing PIXELS) so you need to select t with single "pixel" step and round or floor the coordinates of P(t). That is simple: 

dP = abs(P1-P0)
dt = 1.0/max(dP.x,dP.y,dP.z)

this is called line rasterization and can be also ported to integer arithmetics without the need for floats. The ported version looks like this:

dP = abs(P1-P0)
T = max(dP.x,dP.y,dP.z)
t = {0,1,2,...,T}
P(t) = P0 + (P1-P0)*t/T

And even this can be improved by exchanging the *t/T by simple conditional increment/decrement inside loop like this:

There are also different algorithms like Bresenham for this but DDA is faster on modern architectures and also much simpler and easily expandable to any dimensionality.

Spektre
  • 49,595
  • 11
  • 110
  • 380
  • I found some demo code for it, any ideas how to convert this into JavaScript? – Timothy Relson Oct 10 '18 at 08:22
  • @YangYing The code looks exactly like 3D DDA on integer math without the division I was writing about. I do not code in JavaScript but My bet is you need to change the header to match JavaScript syntax and also exchange the `setPixel(x0,y0,z0);` with function yor environment uses for pixel rendering ... I suspect something lice `Canvas->Pixels[x][y]`. Also you can not render 3D pixel on 2D screen so you need to either ignore the `z` coordinate or add some kind of projection ... unless you are rendering into volumetric data. – Spektre Oct 10 '18 at 08:31
  • @YangYing take a look at [n-dimensional DDA oon integer math with subpixel start point offset](https://stackoverflow.com/a/54018102/2521214) might interest you – Spektre Jan 03 '19 at 10:56
0

Thanks for all of the help, I was able to solve this using the DDA algorithm that was mentioned. I Put the python version in my question and I'll update it to JavaScript if anybody else wants it.

Timothy Relson
  • 13
  • 2