Rockthesmurf said:
The circle/triangle fan type approach is interesting, it's similar to what I hinted to at the end about just finding the largest rectangle that I can fit in the middle of the sprite, although, more circular type primitive would probably work better just about all the time. I need a solution that works for more than just convex sprites, but the algorithm could be adapted to work in this situation. I think some sprites will naturally work better with this approach than others, the example given would work pretty well, a 'tree' on the other hand, that has a long thin trunk, branches coming off, etc. wouldn't work as well, but there's no reason not to implement a bunch of different techniques, then just let the code cycle through them and work out which is best and use that, on a sprite by sprite basis.
Thanks for your help, if anyone else has any other ideas then please join in!
Steve
Hm, maybe I should give it a shot; trying to find some algorithm.
The biggest issue that I can think of at the moment with the "circle approach" above, is that there will be unideal primitives that can be difficult to map textures to correctly (and you'll get aliasing issues at the edges of primitives).
So, here's how I would do it; my method uses a binary fractal algorithm kind of thing.
First, let's pick this as our sprite (the blue circle is transparent in case you can't tell):
Now, the algorithm will be a recursive one, and in my example, I assume that a sprite has a size of a power of two, but this is not required and the algorithm can easily be readjusted.
First, we need an image slicer that produces a slice fractal for us.
It will take the image and slice it into 4 slices. A slice can be one of 4 types: Fully transparent, semi-transparent, opaque, or mixed. The slices slices the input slice into 4 parts by dividing it by 2 horizontally and vertically, and then determining which of the types above the slice belongs to. Then, if one slice is of type "mixed", it will call the algorithm function again recursively with that slice.
The slicer will as its output generate a tree of slices; the slices will end up being as small as 1 pixel some times
Pseudocode:
Code:
function partition(Slice slice)
slices[] = slice.sliceUp
result = for each s in slices
type = s.type
if type == mixed
yield partition(s)
else
yield Leaf(slice)
return Node(result)
The next step of the algorithm is a slice pattern recognizer. This is what will yield the actual mesh data. The idea is that we want to take the slice tree and flatten it recursively. This will be done by using pattern recognition methods similar to the methods used by
hqnx pixel art scaling algorithms. Basically, you have a function take a tree that yields some kind of shape information.
Pseudocode:
Code:
function patternize(Node node)
if node.pattern == {#, #
#, #}
return Filled(#)
if node.pattern == {#, %,
%, %}
return Slope45Dgr(#, %)
else if node.pattern == {#, #,
%, %}
return Horiz(#, %)
else if node.pattern == {Filled(#), Filled(#),
Slope45Dgr(#, %), Horiz(#, %)}
return Rounded(#, %)
//.... etc ....
The % and # in this case are symbols for respective recursive calls to the patternize function; I just wanted to save space.
Of course, the code above uses abstract class-like constructs for everything, but in reality you probably would use some kind of vector structure.
Finally, you just generate mesh information from the shape meta data.
I ran this algorithm by hand (in GIMP), and ended up with this:
...so, if you have a good pattern recognition algorithm, you can get close-to-ideal results by using an algorithm like this.