• Advertisement
Sign in to follow this  

Need help with math with vectors and spheres

This topic is 2996 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi there good people, I have the following problem (which isn't homework, it has a very practical use in my computer graphics experiment). We have a point p with a normal vector n, in space. We also have a sphere with center c and radius r. Problem: what is the smallest angle phi between n and a line to any point inside the sphere? Or: what is the largest dot product we can get for n and any normalized vector to a point in the sphere? I found a solution for this problem as follows. I assumed that p would be the origin to simplify things. Then I observed that a point in/on the sphere maximizing the dot must 1. lay on the surface of the sphere and 2. a line from p to such a point must be tangent to the sphere. This provided me 2 equations, and all lines from p to points satisfying these equations would result in a cone. Then I went to 2D, on the plane created by n and c. The point maximizing the dot has to live on this plane, and by taking a 2D slice through that cone we know we have 2 unique solutions. Anyway, that is my approach, and I verified it numerically, but: - I have to calculate three sqrts (one for normalizing, one for solving a quadratic formula due to the sphere/sphere, and another one for normalizing). sqrts aren't extremely fast. - My solution (I can LaTeX it on request) is ugly. I have the feeling that a more elegant solution should exist. I can expand my explanation on request (my story is already too long I think), and anyone that can provide a solution that can be computed faster (on x86) or that can provide another approach will receive eternal fame by being thanked in the foreword of my thesis. Thanks :)

Share this post


Link to post
Share on other sites
Advertisement
I've not given this a huge amount fo thought so it might be stupid but here goes (just some ideas).

You make another circle, center p with radius of size p->c. Those two circles will then intersect at exactly 2 points (I think, maybe there's a situation I've not thought of). Once you have those 2 points compute the dot products (prior to normalizing). Pick the largest, normalize the vector and get the correct dot product.

I'm not sure how complex it would be to solve the circles intersecting though so might be a worse solution than you have at the moment.

I did a quick search and found this:

Intersection of two circles

didn't seem to involve any square roots (ok it needs magnitude) so you might get it down to two square roots (normalizing that closest vector).




After re-reading your post IT hink you might be doing the same thing anyway :/ I'll leave the post just in case thats not the case.

[Edited by - Nanoha on December 8, 2009 4:17:47 AM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Nanoha
You make another circle, center p with radius of size p->c. Those two circles will then intersect at exactly 2 points (I think, maybe there's a situation I've not thought of). Once you have those 2 points compute the dot products (prior to normalizing). Pick the largest, normalize the vector and get the correct dot product.


If the normal vector points between the two intersection points then the maximum dot product will be 1, which you won't get at the two points.

Share this post


Link to post
Share on other sites
I'll consider the circle intersection idea, thanks!
Morbius, in my approach I have several cases to handle in a different way too: sphere could be right in front of the normal, p could be in the sphere's volume.

Share this post


Link to post
Share on other sites
Instead computing the intersection of two circles, you can intersect the circle with the polar curve for point P, which happens to be a straight line.

As an example, if your circle is

x^2 + y^2 - 1 = 0

and your point is (P_x, P_y), the polar curve is

P_x*x + P_y*y - 1 = 0

The intersection of that with the circle should be faster to compute than the intersection of two circles.

Share this post


Link to post
Share on other sites
Thanks for that too, never heard of polar curves before. If I find use for it, I'll let you know. Will investigate it later. Thanks!

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement