# Triangulation problem

Hello,
I’m working on a CAD project and I want to implement foundation drawing. It’s very simple. I store coordinates of mouse clicks when foundation drawing is enabled then I transfer this coordinates so OpenGL can work with them and then I do triangulation with them. After that I just send this data to gpu memory and draw them. But I have some problems with triangluation. I’m using delaunator library and when I draw something like this:

It will add extra triangle like this:

Do you have any experience with this library or should I consider change to some other library ? If so what’s the best library for stuff like this ?

I’m assuming that implements Delaunay triangulation, which isn’t what you want (Delaunay triangulation generates triangles from an arbitrary set of points with no regard to connectivity).

The GLU tessellator (gluNewTess etc) can tessellate non-convex polygons. The interface is designed for legacy OpenGL (`glBegin`/`glEnd`) but it’s possible to use it in conjunction with vertex arrays.

1 Like

I will definitely take a look at that. Thx.

@DajcoK,
@GClements is right, but that approach is likely to … exhaust you.
I’ve worked with the problem of covering arbitrary polygons with color, with a plain geometric approach. That took an embarassing long time. Unfortunately I’m not ready to publish the result … somewhat because the glory of the result is it’s ‘realtime’ dynamic capacity to consume points as they come when you click 'em in - the implementation is messy.

I’ll pop you a minor solution/approach that can solve ‘simple’ polygons with some non-complex concave points (a fluffy def):
I use a function that can return the indices of the concave points. I’ll use it repeatedly on the returned result (the concaves returned compose their own polygon). If this iteration ends with a return of zero concaves … then you can use those concave polygons to clip the polygon into minor entities that are convex and drawable.
I use fans as final drawables, not triangles. A fan can draw a polygon with one concave point if you rotate the fan-points to make the concave point as the first point.
Translated to the specific problem you present (as I understand you), you could just rotate your points and woila, problem solved.
The approach described fails if the iteration ends with returning any remaining concave … this is the complexity barriere that forces you to use heavier approaches.
You will probably have an advantage if you work in index-space and arrange some ‘range’ implementation (a range being two indices representing a clip that splits the polygon in two). That way you can consider every index-pair that a returned polygon can be split into as ‘clips’. If range(2->4) then the clip will use index 2,3,4 and index 3 will be gone in the remaining polygon. … this is math and why it quickly becomes cumbersome…If you glare at it for long enough, you’ll glean the ranges as a tree-structure, with zero->last_index as the root. That’s usefull to know if you pull out the big guns.

1 Like

This topic was automatically closed 183 days after the last reply. New replies are no longer allowed.