[don't merge] Initial implementation of Constrained Delaunay Refinement (fixes #6)

[kintel]

Hi,

This is my initial implementation of Constrained Delaunay Triangulation. This is implemented as an optional post-process to the normal triangulation.

To use, pass TESS_CONSTRAINED_DELAUNAY_TRIANGLES as elementType to tessTesselate(). e.g.:

    tessTesselate(tess, TESS_WINDING_ODD, TESS_CONSTRAINED_DELAUNAY_TRIANGLES, 3, 3, normalvec);

Before merging, this code needs review, cleanup and testing, but it does pass all tests for the OpenSCAD project. Please give it a spin and tell me what you think. Improvements are also welcome :)

[memononen]

Awesome stuff! Few nitpicks, mostly about the memory allocations. It makes a huge difference in speed, so we should get that fixed.

I'm not sure if the element type is the right place to put the constrained flag. Maybe we could add one more parameter triangulationType, which chooses if we use TESS_MONOTONE or TESS_CONSTRAINED_DELAUNEY? That way the polygon output could also benefit from it. The benefit for doing it like you did, is that the API does not change. What do you think?

[kintel]

Thanks for the thorough comments. I'll go through them and fix the code.

About how to enable this: Note that delaunay refinement is a pure post-process after triangulating using monotone region. It's run globally on the entire result mesh. I see that polygon output works by merging triangles into larger polygons. I'm uncertain how well that algorithm will work on a post-processed triangulation, but if you think it could benefit from this, we could simply enable this by renaming TESS_CONSTRAINED_DELAUNAY_TRIANGLES to TESS_CONSTRAINED_DELAUNAY_POLYGONS.

[memononen]

The polygon merger just tries to merge two neighbours if they form a convex polygon. There's no guarantees, it just does its' best. It will work with any kind of triangles.

I think your proposal is nice and simple simple. The flag should also work with connect polygons. The only difference is that the connected one returns also indices to neighbour polygons as result. I wonder if there is such thing as constrained delauney polygon :) I'm still slightly in favor of adding another parameter.

[kintel]

OK, I agree that since delaunay is about triangles, it should be independent from other parameters. tessTesselate() is such a monster function. It think would be better if parameters were passed using separate functions, but we might not want to go down that road either..

[memononen]

I agree, separate setter functions or a struct might be good idea. Functions might be more in line with the rest of the API.

[kintel]

Breaking API is never good : / I don't know how many people use this library, but that would make it annoying to upgrade..

[kintel]

I think I cleaned up most/all your comments. The coding style isn't very uniform; I matched new code with the style of surrounding code rather than making a guess at a global style : /

API decision is pending, but any functional testing can be done on this code. I wish there was a test framework ;)

[memononen]

Thanks for the fixes. I'll looke them more in detail when I get back home.

Few random thoughts on the API:

• add tessTesselateDelauney() (a bit meh)
• add just tessTriangulation(int type) which sets state
• rename tessTessellate() as tessTessellateDeprecated() and change the API (setters + tessTessellate() w/o additional params)

The first two would not change the current API (I agree it's good idea).

The original code mentions some test cases. I'd love to have those in somewhere too.

[kintel]

I've been testing a bit and it looks stable. Any further thoughts about API?

Btw., Is there any interest in the test program I added in https://github.com/openscad/libtess2/tree/test? More work is needed to make it a test framework though. I did some digging for the original tests, but it looks like that was an internal SGI system which wasn't released together with the OpenGL reference implementation.

[memononen]

Finally merged this PR. I'm sorry it took so long. A house construction project was finished and a baby was born in between, life got hectic.

I chose to change the API to option based. The reason was that the polygon output can greatly benefit from the CDT too, and that single enum started to cluttered with all the combinations.