search

artem-ogre / CDT

Constrained Delaunay Triangulation (C++)
https://artem-ogre.github.io/CDT/
Mozilla Public License 2.0
1.07k stars 133 forks source link

Steiner Point insertion #7

Open ihmc3jn09hk opened 4 years ago

ihmc3jn09hk commented 4 years ago

Hi, I am looking for alternative and more modern delaunay triangulation library instead of Triangle. It is awesome and extremely fast. I have been using it for a while but it's kind of old now and the memory management is still 32bit. I found this CDT project and everything looks promising. Yet I could not find any parameter/function that allows insertion of Steiner Points/Quality control during triangulation. Could you guide me out?

artem-ogre commented 4 years ago

Hi,

Thanks for the question.

Triangulation refinement is not implemented in CDT. I have it on my TODO with the highest priority (after performance improvements). It is nice to know that this feature is demanded :)

Any help is welcome and appreciated: pull requests, algorithm implementation suggestions or any other additional information.

There are couple of 64bit patches for Triangle floating around on github. I can check where I’ve seen one if you are interested. One major Triangle shortcoming for me is that it does not use a proper permissive software license. And Mr. Shewchuk is impossible to reach (I tried really hard for months).

Did you have a chance to do any perf comparisons with Triangle? It would be really interesting to know how it compares.

artem-ogre commented 4 years ago

I'm closing this issue for now. Please let me know if you have any further questions.

starseeker commented 3 years ago

Does poly2tri's implementation have anything useful in this regard? They do support Steiner points, although as far as I know they don't use robust predicates... https://github.com/jhasse/poly2tri

starseeker commented 3 years ago

In a similar mode, does CDT support specifying hole polygons? I end up needing both holes and Steiner points in the application in which I use poly2tri (triangulation of trimmed NURBS surfaces).

artem-ogre commented 3 years ago

Thanks for the interest @starseeker!

Inserting Steiner points is a rather straight forward algorithm. We don't need it for our needs right now and unfortunately there is not enough free time to just implement it. Hence a 'help wanted' label on this issue :)

Removing holes is supported and done automatically with one condition: hole polygons and boundary polygon edges need to be constraint edges. See eraseOuterTrianglesAndHoles. It is much easier to use and works for all the use cases we had so far.

Islam0mar commented 1 year ago

WIP https://github.com/artem-ogre/CDT/pull/133.

HahSZ commented 10 months ago

hello！Thank you very much for CDT, it helps me a lot, I would like to ask if Triangulation refinement is currently implemented. Is it possible to densify the points and triangles based on triangle sides or angles? Also, I'm not very clear about the removal of holes, and I can't figure out how to distinguish between holes and constraint edges in the program when using visualizer because all the edges is given in the text without difference.

artem-ogre commented 10 months ago

Hi, @HahSZ. Ruppert refinement algorithm is currently WIP: there are branches and an open PR #133 . It is almost usable but not production ready.

I have very little time for working on CDT so unfortunately it is hard to tell when it will be ready.

Regarding auto removal of holes, I didn’t understand what exactly do you need help with. If it is still unclear for you or you need help feel free to open a new discussion or issue with a more detailed description.