| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 1914.1 | | AUSSIE::GARSON | achtentachtig kacheltjes | Wed Nov 30 1994 03:34 | 27 |
| re .0
Theoretically speaking you can determine whether a line intersects a
plane by determining whether the line is perpendicular to the normal of
the plane. If a and b are two vectors in the plane and c is the line
then this is equivalent to evaluating (a * b) � c where * is here used
to represent the vector cross product and � represents the dot product.
This ignores issues such as
* the plane may be finite
* the ray is semi-infinite
In practice this would be a waste of time (I think). It would be better
just to go ahead and try to find the point of intersection. If there is
none then this will come out of the algebra anyway. Finding the
intersection is just basic algebra if you have the equation of the
plane, say Ax+By+Cz = D, and the equation of the line, x, y and z as
linear functions of a parameter t. It is only necessary to solve for t
and substitute back in the equation for the line. The sign of t will
tell you whether the ray (as opposed to the line) will intersect.
Presumably you would have to do that for each triangle. I'm not sure
how you tell whether the point of intersection is inside the triangle.
I'm sure there are good algorithms around for this that are optimised
somewhat over the simplistic approach outlined above.
|
| 1914.2 | | AZUR::DESOZA | Jean-Pierre Sophia-Antipolis, DTN 828-5559 | Wed Nov 30 1994 08:20 | 20 |
| In this case, the plane is typically finite, it's a facet. and there may be
tousands of them.
I think that there is first a 3D-clipping step. Its purpose is to eliminate
unnecessary computations: Only facets in the 1/2 space containing the ray
are candidates to intersection. Imagine the ray starting from your eye.
You don't need to consider any facet behind your head.
Consider a pyramid or a cone starting from the origin of the ray with an
aperture to be determined, and sort the facets that lie inside or outside the
pyramid or cone.
Then process the subset of facets that lie inside the pyramid or cone.
If this is not what is interesting you, then the details on an intersection
algorithm are surely in some book on projective or computational geometry.
For example I remember that for intersecting straight lines the most efficient
algorithm was based on a parametric representation of the lines rather another
one because it saved just one multiplication or division.
|
| 1914.3 | Back to basics | AZUR::DESOZA | Jean-Pierre Sophia-Antipolis, DTN 828-5559 | Wed Dec 07 1994 12:18 | 27 |
| I've reviewed my computer graphics books :-)
A plane can be represented by its distance d to origin O and by a normal
vector N. (Imagine the plane tangent to a sphere centered on the origin)
The points of the plane when projected on an axis normal to the plane are also
at a distance d off the origin: The projection is obtained by a dot product
with the vector N: (u.v = Xu * Xv + Yu * Yv + Zu * Zv in 3D space)
If P belongs to the plane:
OP.N - d = 0 (OP is the vector from the origin to the point P.)
A straight line is defined by a point R and a vector V.
M belongs to the straight line iff there is such a lambda as
RM = lambda x V
The point I of intersection of the straight line and the plane veryfies both
relationships.
RI = lambda x V
and
OI.N - d = 0
as OI = OR + RI
we get OR.N + RI.N - d = 0 (distributivity of dot product)
i.e. OR.N + (lambda x V).N - d = 0
Hence: lambda = (d - OR.N)/V.N
|