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\$
  • \$\begingroup\$ Most vector libraries should have a built in function to compute the (squared) length of a vector. \$\endgroup\$ – CodesInChaos Jan 20 '15 at 9:58
17
\$\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\$
  • \$\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 Jan 19 '15 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\$ – Josh Jan 19 '15 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 Jan 19 '15 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 Jan 19 '15 at 22:54
  • \$\begingroup\$ The sqrt function has poor performance. You should use faster approximations \$\endgroup\$ – Vinz243 Jan 23 '15 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\$
  • 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\$ – Josh Jan 19 '15 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\$
  • 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\$ – david van brink Jan 19 '15 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\$ – david van brink Jan 19 '15 at 18:47
  • 1
    \$\begingroup\$ That's a good point that I neglected to bring up in my answer, so I added it. \$\endgroup\$ – Josh Jan 19 '15 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 Jan 19 '15 at 23:38
  • 2
    \$\begingroup\$ This is not the Euclidean distance, it's Manhattan distance \$\endgroup\$ – CodesInChaos Jan 20 '15 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\$

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.