Páginas

segunda-feira, 19 de maio de 2014

Why would we like dot product? Part 3

Finally, this is the third part of things you can do with dot product. I had some difficulty in deciding what to post here. Most tricks would either be slight variations of what has been said in part two, or dot product would be only a helping tool in a complex set of calculations (take Separating Axis Tests, for example). As a result, I have a feeling that this post will be the last post about dot product alone.


Closest point of a line segment to another point


Sometimes, you will find a problem that can be solved (or reduced) by knowing the point of a line segment that is closest to another point. With this information, you can build up usable data as distance and direction between the points. Suppose, for example, a 2d top view game. As long as obstacles can be modeled as line segments, you can calculate the distance from an object (i.e the player) from the obstacle. If the object is too close, you move it a little so the object and the obstacle do not overlap.

There are numerous way of calculating the closest point of a point to a line segment, and one of them is with dot products. I will post here code for 3d checking, as converting it to 2d, if needed, is really simple. What we will need to find the closest point is:

 - Vector3 testPoint: the point that we will check the segment against.
 - Vector3 segmentStart: starting position of the line segment. This is one of the segment extremity points.
 - Vector3 segmentEnd: ending position of the line segment. This is the other segment extremity point.


Since the calculation is simple, the requisites are also simple - however the magic behind them can be rather tricky to understand. When you calculate a dot product between two normalized vectors, the resulting value is the cosine between them. If the vectors aren't normalized, you don't have the cosine, but you can still get some useful information about their relationship:

 - Product is a positive value, so the angle between the vectors is less than 90 degrees.
 - Product is zero, so the angle between the vectors is exactly 90 degrees (aka never in computer calculations).
 - Product is a negative number, so the angle between the vectors is more than 90 degrees (not bigger than 180 degrees).


So, what we do is calculate the dot product between the line segment against two vectors created with the test point and each of the line segment extremities. If, when calculating, the dot product is zero or negative, then we know that the segment extremity currently being used in the calculations is also the closest point to the testing one. If both dot products are positive, then the closest point is somewhere between the the two points that defines the segment.


We first calculate our line segment as a vector, to do the calculations:

Vector3 segment = segmentEnd - segmentStart;


Next, we create new vectors with the testing point and the segment extremities, in order to check if any of them is also the closest point:

Vector3 pointToSegmentStart = testPoint - segmentStart;
float dotPointToStart = Vector3.Dot(pointToSegmentStart, segment);
if(dotPointToStart <= 0) return(segmentStart);

Vector3 pointToSegmentEnd = segmentEnd - testPoint;
float dotPointToEnd = Vector3.Dot(pointToSegmentEnd, segment);
if(dotPointToEnd <= 0) return(segmentEnd);


Notice that none of the vectors are normalized. This is important when the closest point actually is between the two segment extremities. Now curse the math. You can actually use the dot products (that came from non normalized vectors) to calculate the closest point, by means of a interpolation.

Vector3 resultingPoint = Vector3.zero;

resultingPoint.x = segmentStart.x + ((segment.x * dotPointToStart) /
    (dotPointToStart + dotPointToEnd));
resultingPoint.y = segmentStart.y + ((segment.y * dotPointToStart) /
    (dotPointToStart + dotPointToEnd));
resultingPoint.z = segmentStart.z + ((segment.z * dotPointToStart) /
    (dotPointToStart + dotPointToEnd));

return(resultingPoint);


The interpolation will return the point of the line segment that is closest to our testing point. The full code follows:


static public Vector3 ClosestPointToSegment(
    Vector3 testPoint, Vector3 segmentStart, Vector3 segmentEnd
) {
    Vector3 segment = segmentEnd - segmentStart;
    
    Vector3 pointToSegmentStart = testPoint - segmentStart;
    float dotPointToStart = Vector3.Dot(pointToSegmentStart, segment);
    if(dotPointToStart <= 0) return(segmentStart);
    
    Vector3 pointToSegmentEnd = segmentEnd - testPoint;
    float dotPointToEnd = Vector3.Dot(pointToSegmentEnd, segment);
    if(dotPointToEnd <= 0) return(segmentEnd);
    
    Vector3 resultingPoint = Vector3.zero;
    resultingPoint.x = segmentStart.x + ((segment.x * dotPointToStart) /
        (dotPointToStart + dotPointToEnd));
    resultingPoint.y = segmentStart.y + ((segment.y * dotPointToStart) /
        (dotPointToStart + dotPointToEnd));
    resultingPoint.z = segmentStart.z + ((segment.z * dotPointToStart) /
        (dotPointToStart + dotPointToEnd));
    return(resultingPoint);
}



Efficiency wise, this way of calculating distance can be pretty fast on gpus, since they are magical with dot products. However, if you are truly worried with performance and/or precision, testing and profiling is strongly advised.

Nenhum comentário:

Postar um comentário