From UV to point on Mesh = impossible?

[tussockyracer]

I have racked my brain at this little conumdrum and honestly cant find a working solution. I want some way of given the UV coords to obtain the corresponding position(s) on the surface of a mesh. This can be done easily with the pointOnSurfafceInfo node but that only works with nurbs. pointOnMeshInfo node altho working with polys doesnt have the required functionality, as it can only provide positional data based upon a parameterized face from the face index.

Any ideas ??

[jeffd]

I have some thoughts on how this might be pulled off, but I keep getting hung up how to determine a corresponding face for the arbitrary UV position. Is that where you are getting stuck as well?

--JeffD

[nonquad]

Well it is a more complicated problem on a mesh.

On a polygon mesh, any given UV coordinate may potentially correspond to more than one worldspace coordinate (overlapping UV's) or it may not be mapped at all.

So a fully functional 'pointonmeshinfo' node would have to return not just one result, but a list, which might be empty. It's just not as straightforward.

You can simplify it some by assuming no overlaps, and returning just the first result, if any. I guess that's the perspective we should take.

Here is what you are probably going to have to do:
Break the object into triangles.
Check every triangle in the object to see if its UV space contains the point in question. I don't remember the math for this offhand but you can find it on yahoo.
Take the first 'true' result as your target polygon (or repeat for every true result, depending on how robust you want your script to be)
Record the distance from the target point to each corner of the triangle.
Take a weighted average of the triangle's points in worldspace, using the distances from the last step for the weights.

That should give you your output point.

[tussockyracer]

JeffD that is indeed where I am stuck.

Nonquad, thanks for the input - altho your method does seem overly complex for what should be a simple and straightforward problem.

[jeffd]

I think that is just it, though. It is not straight-forward problem. UV space has no real correlation to object or world space. Your only connection to object/world space is through a vertex so to choose and arbitrary point means you would have to go find a vert to ride into object/world space.

I think this algorithm might be flawed (and definitely breaks with overlapping UVs - though you could probably get it to work if you did it per shell) but here is a thought.

• Find the closest UV point. And get its vertex.
• Get all faces associated with the vert and their UVs
• After that go through the steps Nonquad mentions

At least you wuld have a much small list of polys to test. Also, if the mesh is not triangulated this would cause incorrect results where UVs might be stretched.

Impossible? Probably not. Simple? Definitely not.

--JeffD

[empleh]

This might give you some ideas.

http://www.acm.org/pubs/tog/editors/erich/ptinpoly/

Good luck,
ww

[nonquad]

• Find the closest UV point. And get its vertex.
• Get all faces associated with the vert and their UVs
• After that go through the steps Nonquad mentions

Unfortunately that could fail.

For example: take two polygons, both square.
One is mapped over the entire UV domain, with a point on each corner.
The other is mapped as a small square close to the center, but not covering it.

Now use your system to try and solve for the center point.

The closest point to the center is a point on the small polygon. However the small polygon does not contain the center, so the algorithm concludes that there is no match, when in fact the center is contained by the larger quad.

In this example there were overlapping faces, but the process can also fail without that condition.

Suffice to say, there's just no way out of it. The code has to check every polygon. Doing a preliminary check with polygon bounding boxes would shave a little time off it, but one way or another you still have to check every poly.

[joojaa]

Actualy what you are asking is exactly how texturemapping works except in reverse (its technicaly a linera interpretation so it can be perfectly reversed).

Except for the problems relating uv overlap in plygons wich means you actualy can get many hits (this is a bit problematic on the algorthim end sice you would need to sample all plygons separately).

Actualy aw has such codes in place namely the artisan tools and painting so it is possible except it causes problems on overlap (hence soem of maya tools require no overlap whatsoever). So this kind of querry is available inside the package, but it wont work in overap cases and it only works in 0 1 space.

PS if you couldnt do this querry easily then how on earth do you suppose maya can draw textures on objects?

[jeffd]

Um.... magic?

Nonquad you are right. I suspected my technique was flawed and after thinking about it some more and sketching some cases, indeed it is.

Good points also, Joojaa. I am not familiar at all with the API end of things, so maybe the "easy" way can be found in there.

--JeffD

[nonquad]

PS if you couldnt do this querry easily then how on earth do you suppose maya can draw textures on objects?

When maya renders, it's operating in a forward direction. It already knows what polygon it's drawing etc. This question is trying to solve in the opposite direction.

It's not really fair to compare the two, although the solution as I described it is (IMO) still fairly simple.

Also, as a side note I was thinking about this...
And I was thinking about ways to speed it up if (for example) you wanted to code a plugin to do it in real time.

I came up with two ideas; both are designed to work in a condition of no overlap allowed, and both work by trying to find the 'right' polygon fast to short-circuit the search. Both ideas involve doing some prep work up front, but should speed up the process afterwards.

First idea is: pre-sort your polygon list based on UV map area. Largest polygons to the front of the queue, smaller to the back. This ensures that when you go to solve for any given UV, the polygons most statistically likely to contain it will get checked first.

Second idea is to set up a 2d array of polygon indices to represent the UV domain. Solve for each 'pixel' in the array ahead of time and store the counterpart polygon index in the array.

The array approach wouldn't be an end-all solution; it could still fail, but it could be coded to fail gracefully, and would still save a huge amount of calculation the vast majority of the time.

Say for example you need to look up (.101,.101). Now say the nearest array element is for (.1,.1). (.1,.1) and is right near the edge of polygon A, while (.101,.101) is unfortunately just over the edge and on polygon B. This would happen only a tiny fraction of the time, but it would need to be accounted for.

So you check the array, get poly A, check it and find that it doesn't contain your point. Not that big of a deal. You check the adjacent elements in the array and check their polys. 99% of the time that should produce a poly that contains your point.

If that still doesn't give you your poly, then it means your point is either not mapped or contained by a polygon so small that it slipped between array pixels. So at that stage you just have to do the full search as usual. No big deal.

The remaining 99.99% of the time, the array method would cut the search down to a single iteration; so overall it would be a very effective plan to implement if you needed to solve constantly in real time.

There are only really two downsides; one is the space required to hold the array, which could vary depending on how much accuracy you want. A high res array would produce solutions more often, while lower res would fail more often and require a full search.

The other is that the array is not dynamic, and wouldn't offer any help if your UV map was dynamically animating or if your topology changed over time. But this situation is pretty rare and probably not really a factor.

[joojaa]

Noquad ok your right, its a bit more complex but not much. Only overlaps cause problems nothing else realy.

Actualy i remeber a tactique from the 2d coding classes that could be quite helpfull (this is how vector iluustration apps know wehn they are in or out or atleast older ones newer work on closest point and clockwise or counterclokwise motion). Imagine the problem as a buch of polygons. Now shoot a ray out of the point (any direction) and if you hit the poly a odd amount of times then you are inside otherwise you are outside (one notable exception is that if you happen to hit the line itself).

Now you could speed this up by shooting at the closest empty edge by missing as much as possible. You could do some pre intersection calculations before trying to solve what is what. and treat the data as plain lines for the time being and try to figure them out later with some nifty memory tricks. Now you wouldnt need to sample verything just build it in some nice quad tree or something.

[empleh]

Time for me to add my $.02.

The mesh needs to be triangulated to avoid nonplanar faces and ease the code for the line intersection test. Triangles are simple and fast.

Here's some code from my raytracer that does a point in polygon test.

/*****************/

float mypoint[2]; // the position you wish to test
int asdf=0; //a counter for edge intersections
int a;
int b;

float u[4]; //the three u and v values from the verts in the triangle
float v[4]; //I assume that v is vertical like y would be

u[0]=vert[0].u-mypoint[0];
v[0]=vert[0].v-mypoint[1];

u[1]=vert[1].u-mypoint[0];
v[1]=vert[1].v-mypoint[1];

u[2]=vert[2].u-mypoint[0];
v[2]=vert[2].v-mypoint[1];

u[3]=vert[0].u-mypoint[0]; // I reuse the first position to make the next for loop easier
v[3]=vert[0].v-mypoint[1];

// now all of the uv positions have been translated so that the point you are testing is (0,0)
// If an edge crosses the x axis in the positive direction, you have an edge intercept

for(i=0;i<3;i++){
a=-1;
b=1;

if(v[j] >=0.0)a=1;
if(v[j+1] <0.0)b=-1;

if(a!={ // this means that one v is negative
// and one is positive so the line
// crosses the x axis somewhere and an
// intersection is possible

  if(u[j]>=0.0&&u[j+1]>0.0)edge\_int++;   // the edge crosses along the
				     // positive x axis, there is
				     // an intersection

  else if(u[j]>=0.0&&u[j+1]<0.0||u[j]<=0.0&&u[j+1]>0.0){  // an intersection
						      // is possible
     if(u[j]-(v[j]*(u[j+1]-u[j])/(v[j+1]-v[j]))>0.0){
        edge\_int++;		// an intersection occured
     }
  }//end if

}//end if

}//end for

// now if edge_int = 1 the the point lies inside of the triangle
/*****************/

I don't know if this helps or not. It looks like the direction the thread was going to take and I wanted to look at the old code any way. You just need to loop through each face on the poly and test untill you get a hit.

And a little advice. If you guys use variables like [j] or [k] make sure they don't mean something likeitalics lol.

ww

[tussockyracer]

Heheh i think i need to rethink a solution to my original idea. I wanted to transform the 2D motion of a cloud of 100 or so particles and map them onto a 3D surface, by using the well mapped uv-set. I guess I will have to think of another way.

[joojaa]

wouldnt it be smarter to build a quadtree with all the lines in it and then shoot aray thisway you could optimize it terribly much since:

You could device it so that you could use rotation to determine what lines are aplicable for test thisway you would only need to test fully only some half of the lines on the way in front of the ray so you would get only half the data of a minuscule amount of data instead if testing everything.

Or indeed even better do it on poly level but this would use more memory (altough its seldom aproblem per se), and sort the tringles so they have a rotation direction defined thisway you would immideately get all the polygons you are inside of with one ray that hits only a pert of the structure

But i realize this is a api solution, since mel or expressions to be presice would not be the best possible way to do this.

[empleh]

Hi Joojaa,
I think you are talking to me. If not, I sure do look stupid.

If the lookup was going to be done multiple times on a mesh then then I guess any optimization that you could get would be better than checking every face.

I don't understand how rotation could help determine applicable lines unless the slope of the line was 0.

---

Hi rebo,
That sounds like a neat way to animate particles across a surface. One thing that sticks out to me, though, is that the area of each uv doesn't match the area in world space of the face. This makes me think that a point with a constant velocity across a texture would change velocity instantaneously as it crossed from one face to the next. This might not be noticable or it might be used for an advantage. I could be completely off the mark also.

Anyway, it's just something to think about. Good luck with your endevor.

ww

[joojaa]

Absolutely not true, it all dopends on the memory algorithm you use, we did this kind of soerting all the time, let me illustrate ths. You just cant do this very effectively in mel but its doable all the same.

You need a memory structure thet works like the raytracers do so that they dont need to test all the intersections jus the buch that is more pormissing (it works quite like this).

The picture isnt prefect and you vill expect much more polys sorted in some form of a quadtree to avoid having to test unnesesery data.

now if the meory tree is carefully planned you can stipulate that the light green triangle needs not be tested since the points are outside of the boundary alltogeter (it doesent need to test this the tree makes sure it never will). Now the ray intersects with the yellow triangle once and the dargreen polygon 3 times wich are odd figures so its inside. the red is intersected two times, an even number wich, means you are outside. There was a demonstration on the not on ow to build the tree (do you know how an octree and quadee works?) so that this can be done very effectively.

Also note its easier to shoot the ray either verticaly or horisontaly, because the calcs get easier. the tree porobably works on some kind of bounding wich means the light green triangle in this case would probably be sampled if weshot the ray that way but ot if we shot it verticaly (very easy to know wehter the bound is in front of you). also again let me be clear you dont iterate the bouds since the tree is self aware and will not make you iterate them. Its not the best solution for 10 or 20 polys but sure kicks ass wen there are many.

[nonquad]

Sounds cool.

Tell us about octrees and quadtrees please!

[nonquad]

ok so I did some searching on yahoo... and I think I'm beggining to understand quad/octrees.

Here are some references for anyone interested.

http://www.cs.wustl.edu/~suri/cs506/projects/quad.html
http://hpcc.engin.umich.edu/CFD/users/char...tml/node29.html

It's pretty clear how the trees are constructed. I'm not quite as clear about how they are used in practice, but I think I get the idea. If you have a large set of points and need to find the indices of points within a bounding volume, you can look them up by finding the cells/leaves within that volume. Right?

Sounds awesome, and I hope to learn more about this stuff. However in the meantime I'm still a little confused about how this would apply to our problem, since we're searching for polygons and not points.

An quadtree operates by branching/subdividing space until each top-level cell contains only one point or none... but with polygons, no matter how much you subdivide there will always be two polygons within the same cell, along a diagonal edge -- and possibly many more.

For example if you planar mapped the top of a standard cylinder primitive; the center point will have any number of polygons touching it, depending on the resolution of the cylinder. So how will the quadtree decide when to 'give up' and accept multiple polys in the same cell? I guess you will need to set an arbitrary limit to the number of levels in the tree?

[joojaa]

There are many ways to utilize theese algorithms but yeah youd probably want 4 trees instead? or something else im not realy an algorithm designer, so what you need is to talk to a good programmer. I just did the basics about theese things in the university enough to know that there are way much more effective solutions than would be apparent at first.

but actualy i think points could be the basis for the question here even tough we are talking of polys. Im not entirely clear myself how raytracing engenes do the intersection bounding but ill ask from soeone with experience if i remeber.

[empleh]

If for each face you keep a list of other faces that share an edge then you could reduce the number of tests that have to be done. I think this would scale very very well. Even if you had millions of faces you wouldn't have to test but a few faces once an initial location was found. Something like a seed fill agorithm could quickly search the current face and the surrounding faces untill the new location of the uv position is found.

Does this make sense?

ww