Distance to line

Sup,



While trying to calculate a distance to a line, I’m failing to do it (at least I think that’s the point where I’m failing). I’m trying to calculate if a target is within a certain distance between the projection of the source’s future position. Something like that image.



http://www.red3d.com/cwr/steer/gdc99/figure7.gif



Todo so, I’m trying to use a Line. Given the following inputs:



[java]Vector3f location, Vector3f velocity, float collisionRadius, float speed[/java]



Where LOCATION is the location in the world of the source spatial.

VELOCITY is the a direction telling wich is the source is pointing to

COLLISIONRADIUS is the diameter of the spatial’s collision radius (a sphere)

SPEED determines the spatial’s current speed



So, to solve this problem, I generated this code:



[java]float cautionRange = speed * 15;

Line line = new Line(location, velocity);

Plane plane = new Plane(velocity, collisionRadius / 4);

Vector3f closest = Vector3f.POSITIVE_INFINITY;



for (Vector3f target : targets) {

Vector3f loc = target.subtract(location);



// If the obstacle isn’t ahead of him, just ignore it

if (plane.whichSide(loc) != Side.Positive) {

continue;

}



// Check if the target is inside the check range

if (location.distance(target) <= cautionRange) {

// Check if the target will collide with the source

if (line.distanceSquared(target) - (collisionRadius / 2) <= 0) {

// Store the closest target

if (target.distanceSquared(location) < closest.distance(location))

closest = target;

}

}

}



// If any target was found

if (!closest.equals(Vector3f.POSITIVE_INFINITY)) {



// Find in wich side the target is

// To do that, we do a signed distance by

// subtracing the location from the target

// and the dot product between the line’s normal

float dot = closest.subtract(location).dot(line.getDirection().cross(Vector3f.UNIT_Y));



if (dot <= 0)

return velocity.cross(Vector3f.UNIT_Y);

else

return velocity.cross(Vector3f.UNIT_Y).negate();



}



// No target found, just return a zero value

return Vector3f.ZERO;



[/java]



But the problem is that, for some reason, it’s only detecting a target when it’s really, really close to the source. I don’t know what else to do. Thoughts and attemps:


  • Maybe I’m messing up while instantiating the Line?
  • I’ve tried to set cautionRange to near positive infinite values (the default entry is something like 1-2 * 15, so I’ve tried from 1f to 100000f), but nothing was changed (really nothing). Changing to near zero obsviously disables the code.
  • In the end, does the distance method checks distance from the ORIGIN of the Line, or from the closest point of the line relative to the given point?



    Can someone help me into this, I need to fix this algo to make progress, and it need to detects targets that are more far away than the current. If it helps, take a look at the running example: http://dl.dropbox.com/u/3279456/dist.7z (if offline, it’s because it’s still uploading).

I’d like to help but I don’t understand the problem…



What are A, B and C? The line… I’m not sure either. The arrow I guess is the distance from the line to A (or its origin)? What are the relationships of A, B and C? Is there any relationship between those circles/spheres?

2 Likes

http://hub.jmonkeyengine.org/javadoc/com/jme3/math/Line.html#distance(com.jme3.math.Vector3f)

Or do you mean an unending line? The above was just for a line segment.



A general line distance is pretty simple, I think.

I recognize that picture.

Here is that steering code implemented if you would like: https://jmonkeyplatform-contributions.googlecode.com/svn/trunk/AI

It has many of those steering influences implemented, but not all. It works quite well as far as steering is concerned.

@pspeed said:
http://hub.jmonkeyengine.org/javadoc/com/jme3/math/Line.html#distance(com.jme3.math.Vector3f)


Nevermind me. Sometimes I answer posts without reading them. :brainsout:
@madjack said:
I'd like to help but I don't understand the problem...

What are A, B and C? The line.. I'm not sure either. The arrow I guess is the distance from the line to A (or its origin)? What are the relationships of A, B and C? Is there any relationship between those circles/spheres?


The origin is the arrow, that's the vehicle, the source object, a player, for example. A B and C are obstacles that the green arrow should avoid, where A should be ignored, and only be should be taken into account because he's the closest obstacle in the way.

@pspeed said:
http://hub.jmonkeyengine.org/javadoc/com/jme3/math/Line.html#distance(com.jme3.math.Vector3f)


I have look into it yesterday, but it has no javadocs, and I don't know if that distance is cauculated from any point in the line, I just don't know. That's why I've attached a link with the running example. And yes, distance from an unending line :/ Or at least something I can calculate for, just like that image (a projection of the green arrow path).

@pspeed said:
Or do you mean an unending line? The above was just for a line segment.

A general line distance is pretty simple, I think.


I thought it was, until I failed trying to calculate what is the closest point in the line given another point in space.

@Sploreg said:
I recognize that picture.
Here is that steering code implemented if you would like: https://jmonkeyplatform-contributions.googlecode.com/svn/trunk/AI
It has many of those steering influences implemented, but not all. It works quite well as far as steering is concerned.


I'm using that library. Actually, this is part of my final job for my completing my undergraduation, and, as a theme, I'm working with pathfinding, specially combining A* and Steering Behaviors. I'm using that library, plus the NavMesh from the MonkeyZone, but I'm improving them, since they have some problems here and there. I'm improving it, so later I can released a good project =] That's what I'm hoping.


If you want to understand the problem, here it's extracted from the paper (http://www.red3d.com/cwr/steer/gdc99/):

Obstacle avoidance behavior gives a character the ability to maneuver in a cluttered environment by dodging around obstacles. There is an important distinction between obstacle avoidance and flee behavior. Flee will always cause a character to steer away from a given location, whereas obstacle avoidance takes action only when a nearby obstacle lies directly in front of the character. For example, if a car was driving parallel to a wall, obstacle avoidance would take no corrective steering action, but flee would attempt to turn away from the wall, eventually driving perpendicular to it.

The implementation of obstacle avoidance behavior described here will make a simplifying assumption that both the character and obstacle can be reasonably approximated as spheres, although the basic concept can be easily extend to more precise shape models. Keep in mind that this relates to obstacle avoidance not necessarily to collision detection. Imagine an airplane trying to avoid a mountain. Neither are spherical in shape, but it would suffice that the plane’s bounding sphere avoids the mountain’s bounding sphere. A decomposable hierarchy of bounding spheres can be used for efficient representation of shapes for collision detection [Hubbard 96], and presumably for obstacle avoidance too. An unrelated obstacle avoidance technique is described in [Egbert 96].

The geometrical construction of obstacle avoidance behavior bares some similarity to the offset pursuit behavior described above. It is convenient to consider the geometrical situation from the character’s local coordinate system. The goal of the behavior is to keep an imaginary cylinder of free space in front of the character. The cylinder lies along the character’s forward axis, has a diameter equal to the character’s bounding sphere, and extends from the character’s center for a distance based on the character’s speed and agility. An obstacle further than this distance away is not an immediate threat. The obstacle avoidance behavior considers each obstacle in turn (perhaps using a spatial portioning scheme to cull out distance obstacles) and determines if they intersect with the cylinder. By localizing the center of each spherical obstacle, the test for non-intersection with the cylinder is very fast. The local obstacle center is projected onto the side-up plane (by setting its forward coordinate to zero) if the 2D distance from that point to the local origin is greater than the sum of the radii of the obstacle and the character, then there is no potential collision. Similarly obstacles which are fully behind the character, or fully ahead of the cylinder, can be quickly rejected. For any remaining obstacles a line-sphere intersection calculation is performed. The obstacle which intersects the forward axis nearest the character is selected as the “most threatening.” Steering to avoid this obstacle is computed by negating the (lateral) side-up projection of the obstacle’s center. In Figure 7 obstacle A does not intersect the cylinder, obstacles B and C do, B is selected for avoidance, and corrective steering is to the character’s left. The value returned from obstacle avoidance is either (a) the steering value to avoid the most threatening obstacle, or (b) if no collision is imminent, a special value (a null value, or the zero vector) to indicate that no corrective steering is required at this moment.


Can anyone help me trying to figure out how to fix this algorithm. Maybe the problem isn't in the line itself, it's just a suposition, cause I don't know where the problem is. What I do know is what is hapenning in that running example.

- The red circle shows the obstacle the white vehicle is trying to avoid
- The Cyan line is the velocity vector
- The orange line is a projection of the line being constructed (visual representation)

I have the same problem with obstacle avoidance, pls solve the problem for me :stuck_out_tongue:

(I will look at it tomorrow and try to help you)

@ogerlord said:
I have the same problem with obstacle avoidance, pls solve the problem for me :P
(I will look at it tomorrow and try to help you)


Are you improving this library also? Or with Steering perharps? We could try to combine our works :P

I’m going to describe how I might do this at a high level. I’ve only skimmed your code so forgive me if I repeat some stuff you’ve already done… but I did notice you do some more complicated things than I would.



One way to handle this is to calculate the point along the movement vector that comes closest to the object to potentially avoid. This is pretty straight forward because that is exactly what a dot product will give you.



vRelative = vObject - vUs;

float projection = normalizedDir.dot(vRelative);



If “projection” is negative then it is behind you and you can stop.



The point that is closest to the direction line is:

vPoint = vUs.add( normalizedDir.mult(projection) );



The distance between vObject and vPoint is the distance vObject is from the line down the direction vector. If this distance is smaller than your radius plus the radius of the object then you need to steer away.



A dot product with your right vector (the vector 90 degrees to the right of your dir vector) will tell you if you need to steer left or right. Negative dot product = object to left, positive = object to right. A left vector works too, obviously… I’m going from memory and I don’t remember if JME provides easy access to left or right.



All of that is from my head. Hopefully I haven’t left out something important. Use copious logging. :slight_smile:

1 Like

Note: the above presumes your steering is 2D. And if so, then the dot with left/right can also probably replace the distance calculation and everything above it… if elevation is not a factor.

1 Like

I think you need to normalize the direction for the line, otherwise you get wrong distance values.

Line line = new Line(location, velocity.normalize());

1 Like
While trying to calculate a distance to a line, I’m failing to do it (at least I think that’s the point where I’m failing).


Apparently Ogerlord knows his lines. He must have spent a lot of time in solitude, pondering the nature of Line.java.

Learn from him...

So, in the end, distance method wasn’t working because my direction vector wasn’t normalizied, just like @ogerlord said ^^



That solved part of my problems, as now the return of Line.distance is returning a correct value.



Another part was a mistake I made by doing



[java]if (target.distanceSquared(location) < closest.distance(location))[/java]



That didn’t make much sense, so I fixed that either.



As the final part, I needed to calculate signed distance, something I was already doing, so I decided to extend the line class to add this functionality



[java]import com.jme3.math.Line;

import com.jme3.math.Vector3f;



public class MyLine extends Line {



public MyLine() {

}



public MyLine(Vector3f origin, Vector3f direction) {

super(origin, direction);

}



public Vector3f computeNormal(Vector3f direction) {

return direction.cross(Vector3f.UNIT_Y);

}



public float signedDistance(Vector3f point) {

return point.subtract(getOrigin()).dot(computeNormal(getDirection()));

}

}

[/java]



I also used the ideas of @pspeed to get the real collision check by adding the target radius to the collision range check, as it makes no sense to ignore it. Actually, by ignoring it, the solution would be wrong.



So, for the final solution, here’s the algorithm (if anyone is interested)



[java] public Vector3f calculateForce(Vector3f location, Vector3f velocity, float collisionRadius, float speed, float turnSpeed, float tpf, List<Obstacle> obstacles) {



float cautionRange = speed / turnSpeed;

MyLine line = new MyLine(location, velocity.normalize());

Vector3f closest = Vector3f.POSITIVE_INFINITY;



for (Obstacle obs : obstacles) {

Vector3f target = obs.getLocation();



// If the obstacle isn’t ahead of him, just ignore it

if (line.getDirection().dot(target.subtract(location)) <= 0) {

continue;

}



// Check if the target is inside the check radius

if (location.distance(target) <= cautionRange) {

// Check if the target will collide with the source

if (line.distance(target) <= (collisionRadius / 2) + (obs.getRadius() / 2)) {

// Store the closest target

if (target.distance(location) < closest.distance(location))

closest = obs.getLocation();

}

}

}



// If any target was found

if (!closest.equals(Vector3f.POSITIVE_INFINITY)) {



// The steering force will try to steer for the sides away from the target, instead of negating it’s location

// That way, the source just turn the minimum away needed to avoid the collision

Vector3f steeringForce = velocity.normalize().cross(Vector3f.UNIT_Y);



if (line.signedDistance(closest) > 0) // He’s on the left side, just negate the steering force

steeringForce.negateLocal();



return steeringForce;

} else

return Vector3f.ZERO;

}[/java]



Now, the question is: is that code for calculating signed distance correct for a 3D plane? And for steering in a 3D plane?

This is really cool. I think I’m gonna apply this to my river generator. Here’s how it works currently:



Water is divided up into 2^n x 2*n sample points. All points are given average flow values based on the general direction and flow rate of the river. The shader then interpolates between the points to make water transition smoothly between the different flow-values.



Step two will be to iterate over all the points and run your algorithm, using the flow vector for velocity. If there are stuff in the way, rocks or whatever, the flow vector is changed to divert the water away from it.



The only modification would be to check behind the point as well, instead of just skipping that, in order to create “back currents” behind rocks etc.



There are more physically accurate models for fluid flow of course, but this is interesting because it is efficient enough to be done in real time, even on crappy hardware… There are usually not more then 16x16 or maybe 32x32 points in a 512x512 or larger terrain.







Thre’s a thread about it somewhere btw, can’t remember what its called tho. Gonna commit the code when it’s done (but it’s on hold now cause of new forester release).

1 Like

I think there are some mistakes, I changed the distance check to



[java] // Check if the target is inside the check range

if (location.distance(target) <= collisionRadius+cautionRange+obs.getRadius()) {



// Check if the target will collide with the source

if (line.distance(target) < collisionRadius+obs.getRadius()) {





// Store the closest target

if (target.distanceSquared(location) < closest.distance(location))



closest = target;

}

}

}[/java]



Maybe with small vehicles your code works but there are problems with large ones.

@androlo said:
This is really cool. I think I'm gonna apply this to my river generator. Here's how it works currently:

Water is divided up into 2^n x 2*n sample points. All points are given average flow values based on the general direction and flow rate of the river. The shader then interpolates between the points to make water transition smoothly between the different flow-values.

Step two will be to iterate over all the points and run your algorithm, using the flow vector for velocity. If there are stuff in the way, rocks or whatever, the flow vector is changed to divert the water away from it.

The only modification would be to check behind the point as well, instead of just skipping that, in order to create "back currents" behind rocks etc.

There are more physically accurate models for fluid flow of course, but this is interesting because it is efficient enough to be done in real time, even on crappy hardware.. There are usually not more then 16x16 or maybe 32x32 points in a 512x512 or larger terrain.



Thre's a thread about it somewhere btw, can't remember what its called tho. Gonna commit the code when it's done (but it's on hold now cause of new forester release).


Well, your river shader looks great, I saw on it's topic ^^ Someday I'll try to work with more complex things.

@ogerlord said:
I think there are some mistakes, I changed the distance check to

[java] // Check if the target is inside the check range
if (location.distance(target) &lt;= collisionRadius+cautionRange+obs.getRadius()) {

// Check if the target will collide with the source
if (line.distance(target) &lt; collisionRadius+obs.getRadius()) {


// Store the closest target
if (target.distanceSquared(location) &lt; closest.distance(location))

closest = target;
}
}
}[/java]

Maybe with small vehicles your code works but there are problems with large ones.


Well, maybe the cautionRange should be modified, it could look a bit more forward to avoid problems. By adding the source and the target radius you get that, so yeah, that's a nice modification to be done.

The other modification, on the second if, I agree with you either. For big targets, that doesn't work, as big slow moving targets will collide. So, the only way I found out to avoid those problems is to consider all the variables to avoid. Here's the final result:

[java]public Vector3f calculateForce(Vector3f location, Vector3f velocity, float collisionRadius, float speed, float turnSpeed, float tpf, List<Obstacle> obstacles) {

float cautionRange = speed * collisionRadius + 1 / turnSpeed;
MyLine line = new MyLine(location, velocity.normalize());
Vector3f closest = Vector3f.POSITIVE_INFINITY;

for (Obstacle obs : obstacles) {
Vector3f target = obs.getLocation();

// If the obstacle isn't ahead of him, just ignore it
if (line.getDirection().dot(target.subtract(location)) <= 0)
continue;

// Check if the target is inside the check radius
if (location.distance(target) <= (cautionRange + obs.getRadius()))
// Check if the target will collide with the source
if (line.distance(target) <= (collisionRadius + obs.getRadius()))
// Store the closest target
if (target.distance(location) < closest.distance(location))
closest = obs.getLocation();
}

// If any target was found
if (!closest.equals(Vector3f.POSITIVE_INFINITY)) {

// The steering force will try to steer for the sides away from the target, instead of negating it's location
// That way, the source just turn the minimum away needed to avoid the collision
Vector3f steeringForce = velocity.normalize().cross(Vector3f.UNIT_Y);

if (line.signedDistance(closest) > 0) // He's on the left side, just negate the steering force
steeringForce.negateLocal();

return steeringForce;
} else
return Vector3f.ZERO;
}[/java]

For a perfect result, I'm going to put (not now, in future) an avoidance factor, wich will multiply that cautionRange by that avoidanceFactor, so it's more flexible.

Thank you @ogerlord you really helped me out =]

What about changing the Obstacle interface and add the methods

[java] public float distance(Vector3f location);

public float distance(Line line);[/java]

so later someone could add other obstacles? (for example boxes)

Thank you, that was something I hadn’t thought of, although, in the end, I’m going to build a good library from this project, and one of the plans what to allow anything could be used in the library, but that’s for future plans. For the present, I’ll just take notes like this one ^^

Yea as that AI steering class is now, it is really just a prototype. The API should change and the obstacle interface is really just something temporary.

I’m glad this is getting some attention, I think it can grow into something incredibly useful.