# Triangulate a polygon into a uniform grid?

This topic is 3020 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hello there,
I was wondering if there are algorithms that can triangulate an arbitrary polygon into a uniform grid. I am probably not using the correct terms so here is an image describing what I have in mind:

Given a set of points defining a polygon I need to compute that kind of triangulation. For simplicity it should just handle convex polygons. The algorithms should allow users to define the number of width and height segments. Basically where there aren't oblique edges, there should just be triangles arranged into a grid.

I need to have that kind of triangulation to allow WPF-esque use of gradients into widgets. I already have it in place for simple shapes such as a rectangle. To draw their background with a linear vertical gradient I am structuring their vertices so to have different height segments in place of their gradient offsets.

However in the future I'd want to be able to draw gradient backgrounds for other polygonal shapes and I will need that kind of algorithm.

If someone could point me in the right direction I would appreciate it. What is the correct term for what I am looking for anyway?

--
My development blog.

##### Share on other sites
You shouldn't need a fine tesselation of your polygon in order to get a linear gradient. All you need to do is compute the correct vertex colors, and, since barycentric interpolation is a linear operation, you'll get the correct linear gradient over the entire polygon. For convex polygons, a simple triangle fan should suffice.

In more detail, your gradient is a function g that takes a 2d point p and returns a scalar g(p) = <w, p> + k, where w is a 2-vector, k is a scalar, and <.,.> denotes the inner (dot) product. Or, if you have two colors A and B, represented as 3-vectors, then the gradient color, represented as another 3-vector, is c(p) = (1 - g(p))A + g(p)B. In both cases -- scalar (grayscale) or vector (color) -- you just need to evaluate your function (g(p) or c(p), respectively) at the vertices.

If you want nonlinear gradients, then I understand. Of course, even here, I'm not sure why you wouldn't prefer to just build some 1d textures. Again, all you'd have to do is set the correct texcoords for your vertices, in the same way as above, and barycentric interpolation would handle the rest.

If for some reason either of the above is not enough and you still need a grid for some reason, I would also be tempted to just use a stencil buffer trick: Draw the polygon to the stencil buffer using a simple fan; then draw a uniform grid the size of its AABB using a stencil test. Finally clear the stencil buffer and you're back where you started, but with a clipped grid drawn.

And if NONE of the above are good enough and you REALLY need a tessellation like you described, then even this isn't terribly difficult. Each grid square is convex; your shape is convex; hence the intersection of any grid square with your shape is convex. So if you clip each grid square individually against your polygon, you can easily tessellate the results (e.g. as triangle fans), and the union will be what you want. So the only subproblem you really need to figure out how to solve is convex polygon clipping, which I think you'll find is well-documented on the web.

##### Share on other sites
Thanks very much for your reply. Indeed, polygon clipping seems to be what I was looking for.

I really need that kind of tesselation. That image makes it look like unnecessarily complex but in order to have nonlinear gradients I need to draw shapes with several width and height segments. Linear vertical gradients need just one width segment but several height ones for example, with different offsets to account for the various gradient stops.

I am developing a SlimDX GUI system based on DirectX11. Widgets are to be drawn at different sizes therefore textures are not an ideal solution. Vertex coloring seemed to me the best solution. I thought about "shading" widgets via pixel shader but as I'm drawing the whole interface into a single vertexbuffer it would become somewhat complex discriminating between the individual widgets once in the pixel shader.

The system is working for simple shapes but should I wish to draw more complex shapes that kind of tessellation would be needed. Drawing a simple rectangle with rounded corners is not something so trivial with a vertex-based approach, for example. Especially if I need the shape to have non linear gradients.

It probably is just a personal whim but I wanted my GUI system to have fancy WPF-like gradients :D Since the game I'm hoping to develop sooner or later is heavily GUI based (a Master of Orion - like game) I needed to invest some time in this process.

--
My development blog.

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 11
• 11
• 15
• 11
• 11
• ### Forum Statistics

• Total Topics
634149
• Total Posts
3015834
×