PDA

View Full Version : Vector & plane math question



Wulf
08-11-2001, 01:41 PM
1. How can the angle of seperation between 2 vectors be found?

2. Given a, b, c & d for a plane, how can I determine if a point on the plane lies within a polygon on the plane?

Decimal Dave
08-11-2001, 06:01 PM
You'll have to test this to be sure, but I think the angle between two vectors looks something like this:

angle = acos( dotProduct(v1,v2) / (magnitude(v1)*magnitude(v2)) )

It has a trig function and a couple of sqrts, but this is still the fastest method I know of. If you just need results proportional to the cosine of the angle (as is commonly used for lighting), just a dot product of normalized vectors is enough, eliminating trig for a small speed gain.

[This message has been edited by Decimal Dave (edited 08-11-2001).]

DFrey
08-11-2001, 09:16 PM
For the second part of the question, you first plug the test point into the plane equation and see if it holds true. If not, then the point is not in the plane, so can not be in the triangle. Next you can reduce the system to 2D by using a choosing a basis in the plane. Let the triangle be described by an oriented piecewise winding. For each piece of the triangle, see if the point lies to the left, right, or on the line. Assuming the winding is ccw, if the test point is found to be on the right of any side, then it must be outside the polygon and you can stop testing. So if get past those three tests without the testpoint being on the right, then it is either on or in the polygon.

That's just one way. There is another way which uses a sum of triangle areas. Basically, if the triangle is ABC, and the testpoint is D, then if the area of ABC equals the sum of the areas of ABD, CAD, and BCD, then the point must be in the polygon, assuming it is in the plane.

There are many other methods as well.

Of course with any of these methods, you must take floating point errors into consideration.

Go here: http://www.gamasutra.com/features/20000210/lander_01.htm for some of the various ways to do this.

Wulf
08-12-2001, 05:46 AM
That formula is accurate Dave. Thanks for your help.