6
\$\begingroup\$

What is the simplest way to programmatically calculate difference between two points in a 3D game environment?

I am trying to sort a list of light sources by how close they are to an entity, so that only the four closest light sources affect an entity at any given time.

\$\endgroup\$
1
  • \$\begingroup\$ Most vector libraries should have a built in function to compute the (squared) length of a vector. \$\endgroup\$ Commented Jan 20, 2015 at 9:58

4 Answers 4

18
\$\begingroup\$

Compute the vector representing the displacement between the two points p0 and p1:

v = p1 - p0

and then compute the length of that vector:

distance = sqrt(dot(v, v))

A vector in this case is an element of the real 3D coordinate space, so it has three components (X, Y and Z). A point also has the same three coordinates, and we can subtract two points from eachother to get the vector representing the displacement between those points. Both vector and point subtraction is done component-wise, which means you do the operation on each component separately. For the first line above (v = p1 - p0), you're basically doing

v.x = p1.x - p0.x
v.y = p1.y - p0.y
v.z = p1.z - p0.z

where (v.x et cetera are the individual scalar components of the vector, and so on).

In the second equation we're taking the vector dot product of v with itself. The dot product has lots of useful applications but in this case I'm just using it for brevity. The dot product of a 3D vector has a scalar result (a single number), and that number is calculated for two vectors a and b as

(a.x * b.x) + (a.y * b.y) + (a.z * b.z)

which in our specific case translates to

(v.x * v.x) + (v.y * v.y) + (v.z * v.z)

This is the same as "v.x squared plus v.y squared..." When you take the square root of that resulting scalar, you get what is known as the magnitude or length of the vector. The length of the vector is the distance you travel when, starting from some origin (p0 in this case) you displace yourself by the vector arriving at some destination (p1).

It is thus the quantity you want to sort your entities by. Note however that if you only need to compare distances, and not otherwise use the actual accurate value of the distance, you can omit the slightly-costly square root from the computation since it will not change the relative ordering of the values.

\$\endgroup\$
5
  • \$\begingroup\$ I'm not the best with vector math, could you elaborate on the mechanics behind this? What does each step actually do? \$\endgroup\$
    – Bassinator
    Commented Jan 19, 2015 at 17:07
  • 10
    \$\begingroup\$ If you're doing anything in a 3D environment, you'll want to be familiar with this stuff. It's pretty basic and you can find good reference material online or good books about it relatively easy. I strongly recommend you do so. I'll edit my answer to break the above operations down into their component parts, though. \$\endgroup\$
    – user1430
    Commented Jan 19, 2015 at 17:09
  • \$\begingroup\$ At one point I was good with vector math, but that day has long since passed. Calculus seems to have washed it all from my head. Guess I've got some reading to do. \$\endgroup\$
    – Bassinator
    Commented Jan 19, 2015 at 17:11
  • 3
    \$\begingroup\$ In surprised that noone had mentioned that this formula is just applying a translation and the 3D variant of the Pythagoras Theorem. The relation distance^2 = dot(vec, vec) is just Pythagoras Theorem written in terms of vectors distance^2 = x^2 + y^2 + z^2 for three dimensional vector, recalling that dot-product is just notation for element-wise multiplication. Skipping the square rooting is an insight that you'd have if you notice that squaring or rooting a list of positive numbers never change their relative orders. \$\endgroup\$
    – Lie Ryan
    Commented Jan 19, 2015 at 22:54
  • \$\begingroup\$ The sqrt function has poor performance. You should use faster approximations \$\endgroup\$
    – Vinz243
    Commented Jan 23, 2015 at 16:24
2
\$\begingroup\$

abs(x1-x2) + abs(y1-y2), as proposed by this answer will not always be correct. If you are willing to perform two more multiplication, you can perform an exact ordering without the cost of a squareroot.

Consider the distances from (0,0) to the points (3, 4) and (5, 1). The distances are 5 and ~5.09, but the abs algorithm shows (5, 1) as being closer.

If you want to compare absolute differences without performing the square root, compute the square of the euclidian distance like this:

(x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)

\$\endgroup\$
1
  • 5
    \$\begingroup\$ Note that this site isn't a forum, and posting answers "responding" to other posts doesn't work well (you should use comments for that usually), since posts aren't always displayed in an order that would make such a thing readable. I linked the answer you were responding to to try to alleviate future confusion with your response. \$\endgroup\$
    – user1430
    Commented Jan 19, 2015 at 19:11
1
\$\begingroup\$

abs(x1 - x2) + abs(y1 - y2) + abs(z1 - z2) is much more efficient than using square root. If you don't need the actual distance, and just need to compare distances, this is the way to go.

There will be a margin of error here, so it will give you a rough sort. Thanks to David for pointing this out

\$\endgroup\$
11
  • 6
    \$\begingroup\$ Distance from origin to point A (2,2) vs point B (3,0). Actual distance to A is 2.83, and to B is 3.0. A is closer. By "taxicab distance" we'd say that A is further, which is wrong. Sorry! Taxicab distance has its uses, but accurate sorting isn't one of them. \$\endgroup\$ Commented Jan 19, 2015 at 18:26
  • 4
    \$\begingroup\$ What you can do is remove the square root from the chozen answer above, and say M = dot(diff,diff) = (x2-x1)^2+(y2-y1)^2+(z2-z1)^2, instead of sqrt(M), which is sufficient for sorting. \$\endgroup\$ Commented Jan 19, 2015 at 18:47
  • 1
    \$\begingroup\$ That's a good point that I neglected to bring up in my answer, so I added it. \$\endgroup\$
    – user1430
    Commented Jan 19, 2015 at 19:12
  • 1
    \$\begingroup\$ @Evorlor, its bad enough that it should be completely avoided, imo. Just sum the squares, you still avoid the sqrt and you have a list of d_squareds that can be sorted with 100% confidence. \$\endgroup\$
    – Octopus
    Commented Jan 19, 2015 at 23:38
  • 2
    \$\begingroup\$ This is not the Euclidean distance, it's Manhattan distance \$\endgroup\$ Commented Jan 20, 2015 at 9:28
0
\$\begingroup\$

You could use the distance formula:

Formula:

sqrt((p2.x - p1.x)^2 + (p2.y - p1.y)^2 + (p2.z - p1.z)^2)

Code:

Math.sqrt(Math.pow(p2.x - p1.x, 2) + Math.pow(p2.y - p1.y, 2) + Math.pow(p2.z - p1.z, 2))
\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .