I am looking for the fastest way to find the Texture Coordinate (UV) at any point inside an arbitrary triangle, given the XYZUV values at each vertex.
IE I seek information regarding triangular interpolation methods (pseudocode would be nice).

Can anyone point me towards information on trilinear or barycentric solutions? (preferably ones that address numerical instability)..

Can anyone point me towards other potentially useful algorithms?
Posted on 2006-01-20 02:53:21 by Homer
Why not just using D3DXIntersectTri? It returns barycentric coordinates. You can easily convert them to UV.
Posted on 2006-01-20 07:00:49 by ti_mo_n
Your suggestion is valid, however I'm not convinced that this is the fastest possible solution...
I'm pretty sure that even if I implemented the very same algorithm that I could optimize it to execute faster.
Posted on 2006-01-20 22:21:36 by Homer
What's the context you need this for, a pixel shader or something on the software processing end?

The Dx API's are well optimized, the dll's use the best code for your system. (IE if you have SSE3 it uses SSE3 optimized). It does this through a sort of jmp table it creates.

But depending on the amount your calling the function, making it inline and avoiding the call,ret instructions would save a little. Also the Dx functions have an extra jmp in them (to get to the optimized code stub) which is another few processor ticks every call.

Is this the type of function prototype you mean
GetTexCoords(VECTORXYZUV v1,v2,v3, D3DXVECTOR3 point, FLOAT *TU, FLOAT *TV)
Could you then do something with the weighed averages of the component distances each vertex is from the point? It's a shame this kind of math isn't better documented (or at least easier to find).

I'm just shooting from the hip but
Could transform the triangle and point to a 2d coordinate system or screen coords (since the 3 verts can lie on some plane). It would make deriving the texcoords easier if the triangle was in screen coords, because then the triangles that you don't see would not need to be calculated (like if you were looking at it from the side it would be just a line or invisible on the screen).

http://www.cs.unc.edu/~andrewz/comp236/hw6/
http://www.cse.ohio-state.edu/~rayt/cis782-lab1/

Hope those help a little.
Posted on 2006-01-21 00:14:11 by r22
You're right, I should qualify my statement.
I'm not interested in viewpoint-dependant (raytracing) solutions.
I want to calculate UV values for known XYZ points apon the plane of a Triangle, for use in a BSPTree generator. IE, I want to calculate subtriangles created when some Plane cuts through some Triangle, and in particular, I want to calculate the UV values for the new vertices formed at the intersections between the plane and the triangle.

The D3DXIntersectTri function internally calculates the Plane of the triangle being intersected, and what kinda sucks, it does NOT return the point of intersection on the Plane.

In my case, I already have calculated the Plane of each Face, and I can cheaply find the intersection point XYZ on the Plane, via my own DistanceRayPlane function.

This makes D3DXIntersectTri seem quite naive and slow, given that it must calculate the Plane every time it is called.

Axial solutions to this problem are inherently flawed, especially where the face is on 45 degrees to the working axis.

What I really want then is a way to calculate the Barycentric RST or UV values, I know these can be obtained from the plane equation and the intersection point. Once I have those I can easily determine the texture UV at the intersection point.

Posted on 2006-01-21 00:41:29 by Homer
I understand that you can't use it, but I'd like to correct 1 thing:
The D3DXIntersectTri function (...) does NOT return the point of intersection on the Plane.

It does - indirectly. pDist is a pointer that will receive the distance from ray's origin.

Nevertheless, good luck with your goal.
Posted on 2006-01-21 02:42:14 by ti_mo_n
Yeah thanks, I think I found the most efficient solution for my particular problem, and I have to say you got me thinking when you mentioned the fDistance.
I modified my own IntersectionRayPlane function, it now returns A) the intersection point on the plane, and B) the distance to the intersection along the Ray AS A RATIO OF THE RAY LENGTH. In other words, I should rename this function to IntersectionLinePlane.

Since my intersection points are always on the Triangle Edges (and not somewhere within the triangle), I can simply interpolate the UV along each intersecting edge, and the Ratio value I've obtained is exactly what I need to perform this 2D interpolation of the UV values of the vertices at each end of the intersecting edges.

I don't know why, but I always overcomplicate simple problems, yet seem to have a knack for finding elegant and simple solutions to complex problems.

Posted on 2006-01-21 05:10:11 by Homer