On Wed, 14 Jul 1999 17:59:10 GMT, pet### [at] usanet (Peter Popov)
wrote:

>On Tue, 13 Jul 1999 16:41:34 GMT, nos### [at] despamcom (Jerry Anning)
>wrote:
>
>>Here is another intuitive stab at the problem stated this way.
>>For each (possibly relevant) triangle of the mesh:
>>  If the normals of the three corners all point east of the target
>>point (or all point west ..., north..., above..., etc.) then that
>>triangle is irrelevant.
>
>I don't quite get that. The target is a point in space and thus the
>chance of any of the normals to point directly at it is
>infinitesimally small. Some hidden line removal algorithm will be
>useful, if that's what you meant, like ignoring all triangles whose
>normals point at the semi-space (about the plane of the triangle) not
>containing the target point.

By "possibly relevant" I mean every triangle some hidden line algo
would show from a camera at the target point.  By the normals part, I
mean: make a triangular prism by extending the normals of the triangle
out further than the distance to the target point.  If the target
point isn't in or on that prism, that triangle is also irrelevant.

>>  For each remaining relevant triangle, there will be several cases:
>>    If all three vertices have normals pointing at the target, the
>>whole triangle will, so you will have to integrate over the triangle.
>>    If two vertices do, integrate over the line between them.
>>    If only one vertex does, use it.
>
>As above, I don't quite understand what you mean by pointing at the
>target.

If that normal, extended enough, would intersect the target point.  As
you say, it is unlikely.  For bulletproofing, the case must be
considered
. 
>>    If no vertices have normals pointing at the target, and at least
>>two vertices have normals pointing into different "hemispheres" around
>
>What hemispheres do you have in mind?

In other words, the case remaining.  The target point is strictly
inside the triangular prism I mentioned above.

>>the target as determined above, then by continuity, there will be a
>>point in or on the triangle that has a normal pointing at the target.
>>In this case, proceed as follows:
>>      For each vertex of the triangle, compute a vector pointing at
>>the target from that point.
>>      Find the angle between that vector and the given normal at the
>>vertex (in radians).
>>      If it is greater than pi, subtract pi.
>>     Divide the result by pi.  You should have a number between zero
>>and one.
>>      Add the three numbers you just calculated together and divide
>>each one by the sum.  The three numbers will now sum to one, so you
>>have barycentric coordinates for a point on the triangle.
>
>What are barycentric coordinates?

given a (convex) n-gon (it doesn't have to be regular), a set of n
numbers that sums to one is a set of barycentric coordinates for that
n-gon.  By multiplying the elements of the  (Cartesian) coordinates of
each vertex of that n-gon by the barycentric coordinate corresponding
to that vertex and adding the n sets of modified coordinates that
result, you get Cartesian coordinates of a point in or on that n-gon.
This is useful for many purposes.  Some POV-related things I have done
with these coordinates are: picking a random point inside a polygon
(to pace an object there) and producing an image of the sinc function
(the "splash with ripples" thing, (sin(x)/x)) with the border
constrained to lie inside a pentagon - without having to use messy csg
or clipping.  Incidentally, if my memory serves (it often doesn't),
this should also work for a convex n-hedron (as, for example, a
triangle mesh with no "dents").

>>      Take the coordinates of each vertex (the point itself, not the
>>normal)  and multiply each component by the barycentric coordinate
>>calculated for that vertex.
>>      Add the transformed coordinates for each of the vertices
>>together componentwise.
>>      The result should be the coordinates of the appropriate point in
>>or on that triangle.
>
>I hope so :)
>
>>I don't have a formal proof that this will work, but give it a shot.
>
>if you would please explain the above items which are quite ambiguous
>to my not-so-mathematical and totally coffeeless mind, I'd give it a
>shot as you say. Thanks for your help.

If (with coffee) this still doesn't make sense, write me direct and
I'll send some doc on barycentric coordinates and try to put together
a demo.


Jerry Anning
clem "at" dhol "dot" com

Post a reply to this message