getting 3D coordinates of a point on the texture.(u,v)

First, here is the generalized texture pipeline for a single texture:

1) Compute object space location
2) Use projector function to find (u, v)
3) Use corresponder function(s) to find texel
4) Apply value transform function
5) Modify equation of fragment value

To find the corresponding texel color of a vertex, the projector function, maps the 3-element object space vector (x, y, z) into 2-element parameter space vector (u, v). u and v both range from 0 to 1. This way texture coordinates are independent of the object to which they are to be applied and a single texture can be mapped to different objects. In the third stage, the corresponder function maps the parameter space coordinates to the texture image space and the correct texel coordinate is computed and it's color fetched. The last two steps change the fetched color value to brighten/darken the color or even shift it and are not relevant to your problem.

As an example suppose your object space locations are (12.3, 4, 25.4). The projector function then returns (0.41, 0.63), which will be later mapped to the correct texture image space vector, say (84, 193). The color value is fetched and shifted if necessary.

But as it turns out, computing the texture coordinates at each vertex and linearly interpolating the results for each pixel doesn't lead to satisfactory results. The depth of those individual pixels need also to be considered. This is the basics of projective texture mapping. Almost all hardwares, fetched the perspective correct texel.

All that said, you need to do the reverse to get the object space location of a texture space coordinate, but, can you simply find the object space locations of the end points and interpolate the results to get the object space location of the somewhere-in-between texel? You now know that this can't work because of the perspective correction.

Here are two articles for further readings:
http://www.geocities.com/siliconvalley/2151/tmap.html
http://www.flipcode.com/articles/demomaking_issue14.shtml

Hope that helped,
Ashkan

thank you ashkan, you are absolutely right. it cant work because of the perspective correction. but wouldnt the result be somewhat approximately correct? (which would be ok with me) or would it be completely wrong? i mean the point should still be lying between the ones it is interpolated from

now speaking of interpolation. how would i do that?

Quote:

Original post by Ashkan can you simply find the object space locations of the end points and interpolate the results to get the object space location of the somewhere-in-between texel?

what i know so far is:
1. the 3d-coordinates AND the uv-texture coordinates of the vertices around the unkown point.
2. the uv-texture coordinates of the unkown point.

what i am looking for are the 3d-coordinates of the unkown point.


thanks!

Barycentric Coordinates?

-M

thanks, yes baryzentric coordinates might work. unfortunately my math skills are somewhat last-year, so i dont completely understand it.

how exactly can i get the baryzentric coordinates of a point in a triangle?

thanks!

Quote:

but wouldnt the result be somewhat approximately correct? (which would be ok with me) or would it be completely wrong?

It's up to you and your application, how much mapping anomalies you want to tolerate. I didn't find an image to exactly demonstrate the differences. 3D related books such as "Real Time Rendering" and "3D Computer Graphics" both contain discussions and images on that. There is also an article on developer.nvidia.com, which, while is not directly related to perspective correct texture mapping contains an image that describes the effect. Here is a link:

http://developer.nvidia.com/object/Projective_Texture_Mapping.html

The author of the article points out that although images look like illustration of the difference between perspective-correct and non-perspective correct interpolation, the images are actually related to projective texture mapping. But you get the idea.

Quote:

now speaking of interpolation. how would i do that?

The affine texture mapping ( = non-perspective correct texture mapping ), first interpolates the (u, v) texture coordinates along the triangle edges and then interpolates the results across the scanline. Here is an ASCII-art diagram to demonstrate that.

        a         /\        /  \       /    \   e  x-z----x  f      /        \    /          \   /            \  /--------------\   b              c  

Suppose that we want to compute the texture coordinate of point labeled z. First, the texture coordinates are interpolated across the ab edge to estimate the texture coordinate of point e. The same happens for point f. Next the texture coordinates are interpolated across the scanline ef to find the texture coordinate for z. You can find the equations on the web.

I don't know the equations to perspective-correct texture mapping, but here are some articles that might demonstrate that. If you find the perspective-correct texture mapping matrix that transforms the model space coordinates to texture space coordinates, you can multiply your point by its inverse to get that point's location in model (or as you say object) space.

http://easyweb.easynet.co.uk/mrmeanie/tmap/tmap.htm
http://www.gamedev.net/reference/articles/article331.asp


Regards,
Ashkan

[Edited by - Ashkan on November 3, 2006 8:40:06 AM]

Quote:

Original post by ehmdjii how exactly can i get the baryzentric coordinates of a point in a triangle?

A, B, C are the vertices of a particular triangle.
Auv, Buv, Cuv are the UV coordinates at the vertices.
Axyz, Bxyz, Cxyz are the positions of the vertices.
Puv are the UV coordinates of the point.
Pabc are the barycentric coordinates of the point [for that triangle]
Pxyz is the object space position of the point

aa = (Bu-Au) * (Cv-Av) - (Cu-Au) * (Bv-Av)
Pa = ((Bu-Pu) * (Cv-Pv) - (Cu-Pu) * (Bv-Pv)) / aa
Pb = ((Cu-Pu) * (Av-Pv) - (Au-Pu) * (Cv-Pv)) / aa
Pc = ((Au-Pu) * (Bv-Pv) - (Bu-Pu) * (Av-Pv)) / aa

The above are just a bunch of 2D cross products. The 2D cross product happens to give you the area of a triangle. If you look at the Wolfram reference posted above, it notes that the areas of the sub triangles ABP ACP and BCP are proportional to the barycentric coordinates.

The division of each sub triangle by the area of the main triangle is so we can get the useful property of areal coordinates that for any point which is *inside* the triangle, Pa+Pb+Pc=1


Once you have barycentric coordinates, you can use those to convert between texture units and object units by doing: Pxyz = Axyz*Pa + Bxyz*Pb + Cxyz*Pc


So now to come up with an algorithm for you:

For every triangle in the mesh{  // the barycentric coordinates with respect to this triangle  Compute Pa, Pb, Pc   // is the point inside this triangle ?  If (Pa+Pb+Pc == 1)  {    // yes, so use the barycentric coordinates to compute the position    Pxyz = Axyz*Pa + Bxyz*Pb + Cxyz*Pc  }}

Notes:
1. remember to take floating point storage issues into account when testing Pa+Pb+Pc against 1.

2. if you can guarantee that every face of the mesh uses a unique part of the texture map, then you can early-out from the loop for the first triangle that contains the point. For completely arbitrary texturing, multiple polygons may use the same piece of texture map (e.g. mirroring, repeats etc).

3. on a related note if the artist has stretched a single texel of the texture to cover multiple faces and that's the point you're testing, all of those faces will return matches.

4. as with all "arbitrary mesh" problems, if you know anything like the connectivity between triangles, or knowledge of how the mesh has been textured, or have any kind of spatial data structure, you can make the test somewhat better than O(numFaces).