This will probably be a quick one, I am trying to find the best way of programming 'edge padding' to the UV islands on texture maps:

http://wiki.polycount.com/wiki/Edge_padding

I first started using a naive algorithm that searches outwards from each transparent pixel to find the nearest uv island (valid) pixel. This works but is very slow.

[attachment=34483:facemapREF.png]

Up till now I've been using a cellular automaton to 'grow' the edges of the uv islands. This works, but produces 45 degree angle or 90 degree angle growth only (because of the neighbourhood of the CA being 8 cells). It's also not super fast.

Instead of just padding, say 8 or 16 pixels, I'd like to be able to pad reasonably quickly all the empty space if possible, for large tex sizes (4096x4096), so I'm having another look at it.

I'm getting the impression most other developers are using 'dilation', which seems to be a fancy word for the cellular automaton approach. However I'm wondering if anyone has got a good optimized version of the search approach?

My first thoughts were that when checking neighbouring transparent pixels A and B, the closest possible one to B must be within 1 pixel distance of the closest to A. Considerably narrowing the search. I've done this and it is faster, but not blindingly fast.

Then I'm wondering whether it is possible to take some kind of 'mipmapping' type approach .. find the closest neighbour on a low res version, then progressively scale up to the full res version, only checking the pixels necessary.

Finally I was wondering about some kind of 'progressive field' approach as I move through the x pixels, just processing the incoming y line, rather than the whole 'kernel'.

Any thoughts anyone? :mellow: (should I be happy with the dilation approach for example?)

All the ideas that you mention involve pixels. For a completely different idea -- UV islands are sets of 2D triangles. There's lots of spatial partitioning algorithms that are designed to quickly solve "what is close to this thing" type queries.
For any point, you could query the closest 2D triangle to it, excluding any within your own island, then get the distance to it, and then quantize that to a pixel-distance.


As for the mip-map based approach you mention, UV gutters are designed to solve bleeding issues with mipmapping, so that would work too. You're basically using a quad-tree of pixels.

Could you use premultiplied alpha and through that avoid the need for the padding?

Look for the 2 posts about it in the timeline there:

http://eelpi.gotdns.org/blog.wiki.html

Substance Painter uses dilation and my exports on a 4096 image set (rough, diffuse, metal, normal) is 20 seconds or so. So judge by your speed results if they are similar and if they are reasonable.

This is a very good article to read. It talks about fast and efficient dilation algorithms. Includes pseudo code too: http://blog.ostermiller.org/dilate-and-erode

All the ideas that you mention involve pixels. For a completely different idea -- UV islands are sets of 2D triangles. There's lots of spatial partitioning algorithms that are designed to quickly solve "what is close to this thing" type queries.
For any point, you could query the closest 2D triangle to it, excluding any within your own island, then get the distance to it, and then quantize that to a pixel-distance.

This might be a good avenue, especially as the number of tris does not increase with the resolution of the texture .. whereas the number of pixels to 'check against' goes up with the number of pixels to test and the number of pixels to test against (squared).

Could you use premultiplied alpha and through that avoid the need for the padding?

Look for the 2 posts about it in the timeline there:

http://eelpi.gotdns.org/blog.wiki.html

Not sure yet, I suspect not, but I will read .. remember Tom Forsyth's name from gdalgorithms etc way back. :)

Substance Painter uses dilation and my exports on a 4096 image set (rough, diffuse, metal, normal) is 20 seconds or so. So judge by your speed results if they are similar and if they are reasonable.

Ah this is good info, so substance painter isn't immediate either. I only really need to do this calculation (for 3D paint) strictly speaking as a one off on import, whereas I've been doing it every time on loading projects (to avoid unnecessarily bloating the save files), so an option is to save this info in the save files. It may well compress down quite small.

This is a very good article to read. It talks about fast and efficient dilation algorithms. Includes pseudo code too: http://blog.ostermiller.org/dilate-and-erode

A good article, however nothing new to me in this particular case (they missed only processing the 'active' pixels, which can be a big win in some cases, like this one I suspect).

If you're doing dilation on the CPU, it's also going to be way slower than a GPU implementation. I've shipped games where we've (re)dilated dynamic sprite atlases every frame on the GPU :wink:

If you're doing dilation on the CPU, it's also going to be way slower than a GPU implementation. I've shipped games where we've (re)dilated dynamic sprite atlases every frame on the GPU :wink:

Cool! :D Yeah I will have to eventually learn to do more stuff on the GPU lol!

Could you use premultiplied alpha and through that avoid the need for the padding?

Look for the 2 posts about it in the timeline there:

http://eelpi.gotdns.org/blog.wiki.html

Read through it now, I have had to revisit the straight vs premultiplied thing a few times .. here I think I do need to use straight alpha as 3D Paint is producing texture maps for use by users, who may need to use straight alpha. But it has reminded me I should double check it exports composite alpha masks as they might be useful! :o

[attachment=34512:facemap.png]

Done a little exploratory work on optimizing the 'search' algorithm (rather than dilate). It does produce nicer results because the lines aren't limited to 90 and 45 degrees. Whether that improvement would be seen through the filtering etc versus dilate I don't know .. but I'm tempted to keep it as an option given the offline nature of the tool.

When I was growing the search as a rectangle around the test pixel, the optimization that I only needed to start checking the next x pixel search at a distance 1 pixel less, was hampered because the new nearest pixel could in some circumstances have been on the corner of the rectangle, at a rectangle distance of 0.707 x the previous. Thus I had to start each search through a number of smaller rectanges 'just in case'. :o

To help with this, I precalculated a kernel of distances and offsets around a centre point, then quicksorted the points by distance, and made a note of where each whole number distance started in the array.

	dist 0    	(0, 0)
End run 0    , length 1
	dist 1    	(-1, 0)
	dist 1    	(0, -1)
	dist 1    	(0, 1)
	dist 1    	(1, 0)
	dist 2    	(-1, -1)
	dist 2    	(-1, 1)
	dist 2    	(1, -1)
	dist 2    	(1, 1)
End run 1    , length 8
	dist 4    	(-2, 0)
	dist 4    	(0, -2)
	dist 4    	(0, 2)
	dist 4    	(2, 0)
	dist 5    	(-2, -1)
	dist 5    	(-2, 1)
	dist 5    	(-1, -2)
	dist 5    	(-1, 2)
	dist 5    	(1, -2)
	dist 5    	(1, 2)
	dist 5    	(2, -1)
	dist 5    	(2, 1)
	dist 8    	(-2, -2)
	dist 8    	(-2, 2)
	dist 8    	(2, -2)
	dist 8    	(2, 2)
End run 2    , length 16
	dist 9    	(-3, 0)
	dist 9    	(0, -3)
	dist 9    	(0, 3)
	dist 9    	(3, 0)
	dist 10   	(-3, -1)
	dist 10   	(-3, 1)
	dist 10   	(-1, -3)

Then when processing each pixel, knowing the distance I wanted to start from, I jumped to the first point at that distance in the array, and tested each further point in turn until I found the winner, giving its distance and coordinates. :lol:

One gotcha is that if you just sort by distance in the quicksort, you get pixel 'juddering' in the lines that result. I solved this by also sorting by x and y coordinate if the distance was equal (on a diagonal for instance). :cool:

Next I'll do some optimization to prevent boundary checking unless necessary, and perhaps use a 'bit image' to detect the nearest hit instead of the present 32 bit uint, to save so much jumping around for the cache.

Fingers crossed it might run quite fast, it's just a tad slower than substance painter at the moment (and that is using dilate). I could also e.g. run the accurate version for the first 16 pixels, then just use a cheap dilate after that.