# Controlling delaunay triangulation

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

## Recommended Posts

Hi there!
I'm working on a WPF-esque markup style syntax to render my UI. So I can specify how say a button might be rendered in-game. The problem that I'm facing is with radial gradient. I can specify parameters such as the center of the gradient and the radius in the X and Y axes along with the colors to use to create the gradient. If you specify a radius bigger thant 0.5 in either direction the gradient has to be clipped by the button's extents.

So I render the rectangle defining the control boundaries first and a clipped ellipse afterwards. In most circumstances I can end up with the following situation:
[attachment=5466:ellipse.jpg]

As long as the vertices in the red area are not clipped I can retain the level of detail of the original number of points specified in my definition of the ellipse polygon. Where the ellipse is clipped I only end up with the two points of the intersection. After I apply a delaunay triangulation, the blue area will be triangulated as a big triangle, whereas the red areas as I said will retain the original number of "slices" my ellipse is made of. This can result in ugly gradients where that triangle is really noticeable. This can be mitigated if the ellipse has multiple gradient stops (thereby making it have various "rings" of triangles) but still it's not pretty.

So my question is, what modifications would I need to do in order to add more vertices in that area? The algorithm I'm using removes collinear points...

Since i know the nature of the problem I think I could edit it semi-manually after the triangulation has been completed or I could even triangulate it myself, but I want to know if there's a more elegant solution.

##### Share on other sites
As long as the vertices in the red area are not clipped I can retain the level of detail of the original number of points specified in my definition of the ellipse polygon. Where the ellipse is clipped I only end up with the two points of the intersection. After I apply a delaunay triangulation, the blue area will be triangulated as a big triangle, whereas the red areas as I said will retain the original number of "slices" my ellipse is made of. This can result in ugly gradients where that triangle is really noticeable. This can be mitigated if the ellipse has multiple gradient stops (thereby making it have various "rings" of triangles) but still it's not pretty.

You subdivide your shape according to gradient stops? You could just render the entire gradient in a 1d texture, then "warp" it into a radial gradient in the pixel shader (with the center/radius of the gradient passed as uniform variables).

This way your triangulation and clipping would be completely independent from the gradient (and therefore much simpler).

##### Share on other sites

You subdivide your shape according to gradient stops? You could just render the entire gradient in a 1d texture, then "warp" it into a radial gradient in the pixel shader (with the center/radius of the gradient passed as uniform variables).

This way your triangulation and clipping would be completely independent from the gradient (and therefore much simpler).

Yes that could be one other way of doing this. The reason that I'm using this system is that in this way I can assemble the whole interface in just one mesh and draw it in one go. If I used textures I'd have to stop and send multiple draw calls for as many widget I'd be using. So I was hoping that Math could do most of the work in my place But anyway it is working reasonably well, but I'd like to eliminate these fringe cases..

##### Share on other sites
If it's a simple gradient replace the 1D texture with a function in the shader. You can pass in the coefficients for it to the shader.

I'm doing something like that to draw pixel-perfect circles. They're actually just quads, and I do some math in the pixel shader and I get out circles.

##### Share on other sites
Personally, I like the pixel shader approach. However, if you're set on meshes and barycentric interpolation...

Why Delaunay? I think that's giving you weird triangulations. Why not just generate a triangle fan with a vertex at the center, and then clip the triangles individually against the box halfspaces? The only special case to watch out for will be the triangles at the corners that intersect two halfspaces, as these will be turned into quads. There are two choices for splitting these; in keeping with the radial theme, I'd suggest you split them along the diagonal that is on a radius (so that you keep a pure triangle fan).

Would that work?

If not, it'd help to see wireframes of the triangulations you are using, and screenshots of some of the artifacts.

##### Share on other sites
Yours are clever solutions, but since I'm rendering the whole interface mesh in one single batch how would I know the vertex index I'd be using in the pixel shader? Is there some way to get to know which vertex index I'm currently using?

If so I could, in theory, pass an array describing where a widget "starts" and where it "ends" so that the shading could work properly. Otherwise I'd have to render each control individually and it seems a waste for a handful of vertices.On the plus side, the pixel shader feature would allow me to include the WPF's "GradientOrigin" feature, which is the focal point of the gradient (and thus different from the gradient center) which is not easily attainable using my approach as it would require the shape to be triangulated by using a very specific point.

Anyway here's an in-game (well, in-GUI editor) of the artifacts. This is the gradient used:

 <RadialGradient GradientType="Radial" Center="0.5,0.65" RadiusX="0.75" RadiusY="0.6"> <Gradient> <GradientStop Color="#FFFF0000" Offset="0"/> <GradientStop Color="#FFFFFF00" Offset="0.25"/> <GradientStop Color="#FF00FF00" Offset="0.5"/> <GradientStop Color="#FF0000FF" Offset="0.75"/> <GradientStop Color="#FF000000" Offset="1"/> </Gradient> </RadialGradient> 

[attachment=5502:Capture.JPG]

As you can see, the first gradient stop (from red to purple) causes an ugly artifact where the triangulation generates those two big red triangles. Same goes for the penultimate gradient stop (green to blue): again, there are two big triangles in the left and right side which cause the gradient to abruptly stop.

Keep in mind that this was all generated automatically: I identify which polygons to clip against the widget boundaries and then triangulate the resulting points. I can mitigate the effect If I triangulate myself the "inner" ellipse, in those cases where part of the gradient doesn't need to be clipped. But the problem resurfaces in the automatic triangulation of the clipped ellipse.

##### Share on other sites
Looking at those pictures really makes me think a triangle fan with a central vertex will look better. The reason is that all the edges will line up with the gradient of your function, and your ideal elliptical level sets will be approximated by nice concentric polygonal level sets, all the same. With this approach, you'd never get e.g. the square level sets you see in your picture.

It's actually a little more complicated than I'd realized; you'll end up generating a couple extra radial segments to deal with the clipping. See attached image.

You'd get better gradient quality from a pixel shader, but, for the linear-interpolated approach, I think that either this more careful triangulation, or just a brute-force increase to your mesh resolution, is required.

1. 1
2. 2
3. 3
Rutin
16
4. 4
5. 5
A4L
12

• 11
• 26
• 10
• 11
• 9
• ### Forum Statistics

• Total Topics
633723
• Total Posts
3013541
×