Uniform Texture Coordinates

[sibarrick]

Full title too long to fit in the topic title box...

Smoothing an Overlay Grid to Minimize Linear

Distortion in Texture Mapping

so this Xmas hol I've been playing around with the above paper

Pdf here

All is good, and I'll post my results soon, once I've cleaned it up and made some examples.

In the meantime I'm wondering if anyone knows the quickest way to find the closest triangle to a point (in 2D, if that helps) at the moment I have to check the barycentric coordinate of the point relative to every triangle and then use the one where all the weights are <1. Obviously this can be fairly slow and so the whole sop cooks rather slowly for my purposes since I have to iterate through this process quite a few times during the smoothing part of the method.

[Jason]

Wow, that is one wordy paper!

I can't think of a fast solution for you for your problem; I'd probably end up doing the same as you are - however, I'd think that there must be some method in the HDK for doing what you want, surely?

Anyhow, happy holidays and I wish you luck on completing this paper!

Cheers,

Jason

[sibarrick]

I already asked Sesi about this and they couldn't suggest anything that is directly in the hdk. I'm thinking i'll have to use a pointtree structure somehow but that brings its own issues at the moment so I'm just casting around for other suggestions.

I have it working fine for a test sphere but as soon as I pass it any "real" geometry the cook time goes through the roof, like 10 minutes on my poor old laptop, so what I have isn't what you'd call practical yet...

Pelted uv's on a sphere

and after the overlay grid has been used to remove distortions

[edward]

Have you tried GU_RayIntersect anyhow?

[sibarrick]

Ah no! Did you suggest that already? apologies if you did I'd completely forgotten. I'll take a look at, I guess it does some clever internal stuff to optimise things.

[sibarrick]

Rats, GU_RayIntersect is about half the speed of what i have already, back to the drawing board.

I think pointtree is the only way forward...

[sibarrick]

Well having tried various approaches the best I have found is to test every poly but using a fast test

bool
SOP_UVuniform::pointInTriangle(const UT_Vector2 p, const UT_Vector2 a, const UT_Vector2 b, const UT_Vector2 c)
{
  if (p.whichSide(b,a)>0 && p.whichSide(c,b)>0 && p.whichSide(a,c)>0)
	return true;
  else
	return false;
}

Its still a slow sop to cook but its no worse than doing a dops sim I guess and the results are quite good.

UV pelted head

UV's uniformed..

here's the code so far, as usual not much error checking yet, and it echos its status to the console so you can see it is still running....

Compiled version (H8.1.760, windows), plus source

UVuniform.zip

[grasshopper]

In the meantime I'm wondering if anyone knows the quickest way to find the closest triangle to a point (in 2D, if that helps) at the moment I have to check the barycentric coordinate of the point relative to every triangle and then use the one where all the weights are <1. Obviously this can be fairly slow and so the whole sop cooks rather slowly for my purposes since I have to iterate through this process quite a few times during the smoothing part of the method.

Does it have to be the closest? Would "high chance of being the closest (and if it isn't it will still likely be one of the closest)" do? If so, here's a rough algorithm:

1) Sample a small number of random points on the set of triangles to be measured (e.g 40 or so points)

2) Measure the mean distance of these sample points to the reference point

3) Make a bounding sphere centered on the reference point with a radius of the mean distance found in (2).

4) Count the number of points within bounding sphere (should be at least 20)

5) Halve the radius and count points in bounding sphere again

:

6) Keep changing the radius size up or down and counting points within bounding sphere until you home in on the closest 20 or so points.

7) Now just use your previous method to measure the triangles that contain these 20 or so points to find the closest triangle to reference point.

Make sense? Just throwing it out there in case it is useful. It seems like a quicker way to "home in" on the closest (or almost closest) point for large objects.

john.

[edward]

Since it's in 2D and it sounds more like a "containment" problem, why not just build a grid data structure? Set up a 2D array of UT_IntArray's.

For each triangle
	 For each point in the triangle
		 Using the triangle's point position, determine the cell in the grid, add the triangle index to it

So now for each point's triangle you want to find, you can index into the cell, and only test those triangles which intersect that grid cell.

[sibarrick]

Hi guys, thanks for the suggestions i'll check them out. i was actually amazed at how quick the brute force approach was for doing this, but there is plenty of room for improvement.

I think there is a limit to how fast this algorithm can work, even with a really fast triangle search just processing the number of points in the smoothing grid takes a second or so once you have found the triangles, multiple that by the 100-500 iterations you need to get to a nice solution and the time will always be high.

In the paper they talk about using a hierachial/subdivision approach so the detail in the grid is only in the areas where you need it, I think that is really going to be the only way to make any major inroads into the time.

If I get time I'll have another play with it and see if I can improve it. I'm pleased with the fianl output though and that was the main motivation for trying this.

[sibarrick]

Since it's in 2D and it sounds more like a "containment" problem, why not just build a grid data structure? Set up a 2D array of UT_IntArray's.

For each triangle
	 For each point in the triangle
		 Using the triangle's point position, determine the cell in the grid, add the triangle index to it

So now for each point's triangle you want to find, you can index into the cell, and only test those triangles which intersect that grid cell.

How would you determine the grid data dimensions? Persumably if its too small then there will be the possibility of a cell containing no triangle references, and then if a test point was referenced into that empty cell it wouldn't return a triangle....

Is there a formula to determine the size? or is there always the possibilty of having empty cells using this method?

Just thinking out loud...

[edward]

There could be a number of heuristics for determining the cell size. Some combination based upon the bounding box, min/max triangle area, etc. For cells that have no triangles, then it's not just a "containment" problem, then you can start searching with all the cells surrounding the initial cell. If that has no hits, you can search in the next adjacent "ring" of cells, etc.

As for a "hierarchical" approach, the suggested method for using UT_PointTree is probably the easiest right now. Probably less work than rolling your own grid approach even.

[sibarrick]

I've now found a few references to fast search algorithms - good 'ol google scholar

Kirkpatrick, D. G. 1983.

Optimal search in planar subdivisions.

SIAM Journal on Computing 12 , 28

[Daniel]

I've now found a few references to fast search algorithms - good 'ol google scholar

Kirkpatrick, D. G. 1983.

Optimal search in planar subdivisions.

SIAM Journal on Computing 12 , 28

[sibarrick]

Hi Daniel, thanks for the suggestions. I think I'm going to go with rolling my own from the Brown and Faigle paper - its pretty straight forward. Plus I'm interested to see how it works. It should be 100% accurate too.

I might then combine it with either Edwards or John/your point scatter suggestion, and then see what combination returns the best results. This sop needs all the speed it can get....

I can also hopefully squeeze a bit more out of the smoothing routine by doing some cacheing of the calculation as it loops through all the grid points.

Anyway, I'm going to carry on for a bit just to see how much I can improve things.

cheers

[sibarrick]

Ok, here's an update.

I've switched to using GQ_Detail and implimented the fast triangle search from Brown, P. J. C., and Faigle, C. T. 1997.

Has it helped? well its about 1/3 quicker, which isn't bad but I was hoping for more. Its still slow but not quite as slow.... not great ;( still onwards and upwards.

Here's the latest cut of the code plus the usual windows compile.

UVuniform.zip

Next I'm going to try adding in Edward's partitioning idea to see if that helps. I also think there's room for improvement in smoothing function.....

[edward]

You should do a profile to make sure that the bottleneck is still where you think it is.

[sibarrick]

I've done some crude timings using cout.

But how would I go about doing proper profiling in HDK?

[edward]

Nothing special. Hand profiling is probably just as good in your case. UT_Timer found in UT_StopWatch.h is handy. For real profiling (on Windows), we use GlowCode. However, I've never tried it with an HDK operator on a release build.

[sibarrick]

cheers! Edward I'll check out those UT methods.