Update position of a point

Question

Hi all. My problem is this:

I have a set of points in 3D space, and their positions are updated from time to time with a certain velocity. But i need to keep a minimal distance between them.

Can you help me with this?

EDIT: I am using C for the implementation of the algorithm.

Thanks in advance.

Answer 1

Updating position given a velocity is easy - just use a first order difference for the velocity and calculate the position at the end of the time step.

"But I need to keep a minimal distance between them" - makes no sense at all. The distance between them will be governed by the physics of the process that gives you the velocity vector. Can you describe what you're trying to do?

Answer 2

If you want to keep a minimal distance d, you can always assume the points are made up of rigid balls of radius d/2. So whenever 2 balls come in contact (i.e. the distance is ≤ d), you change the velocity assuming an elastic collision. Look up your physics textbook for how to change the velocity in case of elastic collision.

(You may need to implement a quad-tree for efficient collision detection.)

Answer 3

The first thing you need to do is to detect when distance between 2 points becomes less than your minimal distance. The second one is to move point in a way to remove collisions.

The first part is circle-to-circle collission* detection basically, so the aproaches are the same: checking distance between every moved point and other points or using continious collision detection*(if points move by some simple laws).

The second part is up to you, there are too many ways.

(*) - googleable

Answer 4

You can also do this using a physics simulation. This gives many more possibilities, but at a higher computational cost.

For example, others here suggest detecting collisions, but in your comment to duffymo you suggest you would might like a smooth deceleration to avoid collision. In this case, you could create an inter-particle force pushing them away from each other, and then calculate your velocity at each time step using a = F/m, and v = v0 + dt a, where F is the sum of the forces of all the particles on each other. For an example inter-particle force you could use something that looks like one of these:

Calculated from the Python code below. But really anything could work as long as it gets large enough near your minimum distance (so the points never come that close together), and it's zero beyond some distance (so the points aren't always repelled from each other).

from pylab import *

def repulse(x, c, rmin=1., fmax=100):
    if x<=rmin:
        return fmax
    try:
        f = c/(x-rmin)-5.
        if f<0.:
            f = 0.
        if f>fmax:
            return fmax        
    except:
        f = fmax
    return f

x = arange(0, 100, .01)
r = 0.*x
for c in range(0, 10):
    for i, xv in enumerate(x):
        r[i] = repulse(xv, 2.**c)
    plot(x, r)
show()

Answer 5

Determining whether two particles will collide. Suppose you have two particles A and B, and you know their positions at time 0 and their velocities. Initially they are farther apart than the distance r; you want to know if and when they will come within r of each other.

Let's define two 3D vectors R and V. R = the position of B relative to A at time 0, B.position - A.position, and V = the velocity of B relative to A, B.velocity - A.velocity. The square of the distance between A and B at time t will be

square_of_distance(t)
    = abs(R + V*t)^2
    = dot(R + V*t, R + V*t)
    = dot(R, R) + 2 * dot(R, V*t) + dot(V*t, V*t)
    = dot(R, R) + 2 * dot(R, V) * t + dot(V, V) * t^2

where dot(v1, v2) is the dot product of two vectors and abs(v) is the vector length.

This turns out to be a simple quadratic function of t. Using the quadratic formula, you can find the times t, if any, when square_of_distance(t) = r². That will tell you if and when the particles approach each other closer than r.

Determining which of a large number of particles will collide first. Of course you can take every possible pair of particles and calculate when they collide. That's O(n²). Improving on that is harder than the simple stuff we've been doing here so far.

Since you only really need to know about the next, say, n seconds, you can calculate a bounding box for each particle's path over that period of time, extend all those boxes by r in each direction, and see which ones, if any, overlap. This can be done using a modified kd-tree. Overlapping bounding boxes do not necessarily indicate actual collisions, only potential collisions. These potential collisions still have to be checked mathematically to see if there are any real collisions; this is just a way to reduce the amount of checking from O(n²) to something more manageable.