A way to fill a polygon with the lowest possible number of rectangles

Duugu · 08-25-14, 09:13 PM

Well, I know this forum is not about graphics programming ... and the topic is not even wow-specific (at least not right now *g*).
But, I've searched for hours now and I can't figure out how to do it. So, I'm just hoping that there's someone out here, who knows a way or at least has an idea where to search for it.

I am looking for a fast way to fill a polygon (non-convex, no intersections) with the lowest possible number of rectangles.

Any idea anyone?

semlar · 08-25-14, 09:57 PM

Do you mean triangles? Rectangles can't fill arbitrary polygons.

Duugu · 08-25-14, 10:03 PM

No. I mean rectangles. Of variable sizes of course. (smallest ones of 1x1 units)

I would like to fill a polygon ingame. So I can't use triangles.

semlar · 08-25-14, 10:49 PM

Originally Posted by Duugu

I would like to fill a polygon ingame. So I can't use triangles.

Of course you can, just make a half transparent texture and skew it..

Duugu · 08-25-14, 11:00 PM

Ehm. So, you use Settexcoords to rotate/modify the triangle texture to the required shape?
I don't get it. Maybe I'm a bit slow today.

semlar · 08-25-14, 11:39 PM

The only addon examples for this that I can think of off the top of my head are AVR, which used triangles to draw shapes, and QuestHelper, which used triangles to fill quest blobs on the map.

I think they started with a right triangle with 1 pixel of transparency along the edges and used SetTexCoord to skew it into the desired format.

I don't have a polygon triangulation formula for you to start with since it wasn't necessary for what I was doing, but you should be able to get an idea from looking at those addons.