jouley 805 Report post Posted November 20, 2007 I'm having a bit of trouble finding the shortest distance from a 3D point to the surface of an infinite cone defined by an apex, interior semi-angle, and opening axis. I have what I believe to be the solution for a double cone (one opening from either side of the apex), but can't quite wrap my head around how to restrict it to a single cone. Here's pseudocode for what I have thus far: double Angle; // radians double Apex[3]; double Axis[3]; double Point[3]; // send to origin Point[0] -= Apex[0]; Point[1] -= Apex[1]; Point[2] -= Apex[2]; Apex[0] = 0.0; Apex[1] = 0.0; Apex[2] = 0.0; // get another point on the axis of the cone double Point2[3] = { Apex[0] + Axis[0], Apex[1] + Axis[1], Apex[2] + Axis[2] }; // get the vector from the second point to the given point double V[3] = { Point[0] - Point2[0], Point[1] - Point2[1], Point[2] - Point2[2] }; // find the distance from the cone's axis to the point double Crossed[3] = CrossProduct(Axis, V); double CrossedMagnitude = Magnitude(Crossed); double AxisMagnitude = Magnitude(Axis); double d = CrossedMagnitude / AxisMagnitude; // find orthogonal distance of point down axis via pythagoras double V2[3] = { Apex[0] - Point[0], Apex[1] - Point[1], Apex[2] - Point[2] }; double p = sqrt((V2[0] * V2[0] + V2[1] * V2[1] + V2[2] * V2[2]) - (d * d)); // we've reduced the problem to 2D trig Distance = d * cos(Angle) - p * sin(Angle); I feel confident that it works, because when I test it with a point cloud generated from a cone model, every point returns 0 +- 0.001. When I test with a point one unit above and below the apex, though, it gives me the same result, when one unit above the apex should give 1. This last fact led me to the conclusion that it's only working for double cones. What am I missing? -jouley 0 Share this post Link to post Share on other sites
jyk 2094 Report post Posted November 20, 2007 I didn't check your existing code for correctness (since you stated it seems to be working ok), but as for the double-cone problem, if the point lies behind the plane formed by the apex and the cone axis, then the closest point is the apex.Does that help at all? 0 Share this post Link to post Share on other sites
jouley 805 Report post Posted November 20, 2007 Quote:Original post by jykI didn't check your existing code for correctness (since you stated it seems to be working ok), but as for the double-cone problem, if the point lies behind the plane formed by the apex and the cone axis, then the closest point is the apex.Does that help at all?I thought about this, but couldn't convince myself that it was true. For very very short and fat cone, a point out towards the base of the cone but still above the plane formed by the apex/axis would have a closest point somewhere on the cone closer to the edge, wouldn't it? I'll see if I can whip up some mspaint to illustrate... 0 Share this post Link to post Share on other sites
jyk 2094 Report post Posted November 20, 2007 Quote:Original post by jouleyQuote:Original post by jykI didn't check your existing code for correctness (since you stated it seems to be working ok), but as for the double-cone problem, if the point lies behind the plane formed by the apex and the cone axis, then the closest point is the apex.Does that help at all?I thought about this, but couldn't convince myself that it was true. For very very short and fat cone, a point out towards the base of the cone but still above the plane formed by the apex/axis would have a closest point somewhere on the cone closer to the edge, wouldn't it? I'll see if I can whip up some mspaint to illustrate...Yeah, you're right - I wasn't thinking clearly :) 0 Share this post Link to post Share on other sites
jouley 805 Report post Posted November 20, 2007 Well, if it helps anyone to visualize:(It can be simplified by a triangle and a point on a plane parallel to the axis.) 0 Share this post Link to post Share on other sites
ckin2001 122 Report post Posted November 20, 2007 This paper shows how to discount the fact that the point is part of the double cone - http://www.geometrictools.com/Documentation/IntersectionLineCone.pdf 0 Share this post Link to post Share on other sites
jouley 805 Report post Posted November 20, 2007 Quote:Original post by ckin2001This paper shows how to discount the fact that the point is part of the double cone - http://www.geometrictools.com/Documentation/IntersectionLineCone.pdfHmm... It does deal with the double cone, but it also makes the assumption that the angle of the cone is acute. It then rids itself of the second cone with a simple dot product to check for being on the same side of the plane defined by the apex and the axis, as jyk mentioned above. This works for acute angles, but, unless I've missed something (if I have, please explain!), it's the obtuse ones I'm worried about. 0 Share this post Link to post Share on other sites
Zipster 2377 Report post Posted November 21, 2007 The closest distance can be found by doing:c = (bSingleCone) ? acos(((Point-Apex).Axis)\(|Point-Apex|*|Axis|)) : acos(abs(((Point-Apex).Axis))\(|Point-Apex|*|Axis|)); // from dot product definitionif(abs(c - a) >= Pi/2) return |Point-Apex|;else return |Point-Apex| * sin(abs(c - a));Now some explanation. The angle 'c' is the angle between the Axis vector and the (Point-Apex) vector. But what's really important here whether or not the angle between 'c' and 'a' is obtuse, not just 'c' or 'a'. In the single-cone case, if this angle is obtuse, then the Apex is the closest point. Otherwise, the closest point is somewhere on the cone and we use some simple trigonometry. Note that abs(c - a) handles the case where the point is inside the cone. In the double-cone case, obtuse angles aren't an issue since you're always going to form an acute angle with either +Axis or -Axis. This is where the absolute value inside the acos() comes from, it reflects the symmetry of the problem and the fact that you always have an acute angle. 0 Share this post Link to post Share on other sites
jouley 805 Report post Posted November 21, 2007 Well, that certainly is a whole lot more simple! I see the trick, too, I think, about the important angle being that between the Axis and the Apex-Point. I also understand the abs(c-a) makes the result always positive, so removing the abs( ) will give a negative result for points inside the cone, which is the behavior I'm after.Works like a charm, thanks! 0 Share this post Link to post Share on other sites