search

rgcv / CGAL.jl

CGAL meets Julia
MIT License
24 stars 8 forks source link

Example of triangulation #1

Closed juliohm closed 3 years ago

juliohm commented 3 years ago

Hi @rgcv , thank you for putting this package together.

I am new to CGAL. I wonder if you have an example of triangulation in 2D or 3D based on a set of points? I am considering writing pure Julia versions of some CGAL algorithms in Meshes.jl, but meanwhile it would be nice to interface with C++ library.

Thank you,

rgcv commented 3 years ago

Hey there!

TL;DR: No 3D is available, 2D algorithms are (if my memory serves me right) integrally exposed, from Regular to Delaunay Triangulations. I don't have usage examples, but they shouldn't be hard to translate from CGAL's examples, bearing in mind the Julia code isn't as heavily parametric as the C++ library itself. Might get around to it, but don't hold your breath. I suggest giving it a go, could also serve as a usability or ease-of-use proof of concept case study of sorts.

As it stands, unfortunately, I haven't mapped or exposed any 3D triangulation algorithms. I've considered it once before, but it was in passing. It's been a while since I've looked at CGAL too, so the package has become a bit stale. Might get back into it in the future, but it isn't an immediate concern.

Bad news out of the way, there are several (if not all) 2D triangulation algorithms available, including Regular Triangulations, Delaunay Triangulations, and Constrained Triangulations (DISCLAIMER: THESE ARE TERRIBLY UNTESTED, EVEN MORE SO THAN THE REST OF THE CODE). You might want to check https://github.com/rgcv/libcgal-julia and search for triangulation related wrapper code. If you're familiar with https://github.com/JuliaInterop/libcxxwrap-julia, or https://github.com/pybind/pybind11 or Boost.Python, for that matter, the code will look relatively straightforward w.r.t. what types and functions are being mapped.

Despite not having any examples readily available, it shouldn't be too difficult to take a piece of example code from one of CGAL's 2D Triangulation packages and reproduce it (at least I hope so. If it's too difficult, then that only means there's more work to do, which is great in a way, I suppose).

I can't say I'll be able to look into this in too much depth right away, which means I can't really promise you I'll come up with a few examples right away either. Since I can't really give you a schedule or a due date for when I'll add more examples, I do suggest you to try it out (if you want to) by navigating CGAL's documentation as alluded to above.

On a sidenote: arguably, this package would benefit from having more examples based on CGAL's examples such as the one in the README, but never got around to do that. Considered, but it never came into fruition.

Thanks for the appreciation, and best of luck working on Meshes.jl!

juliohm commented 3 years ago

Thank you @rgcv , I think this is good and bad news at the same time. I will try to find out my way into CGAL and other libraries out there before I start trying to code something up myself. Please feel free to join the efforts if you have experience in CG.

I will close the issue meanwhile.

rgcv commented 3 years ago

No problem! Sorry I couldn't be of more immediate help.

Sorry, don't know what's with me, I'm in a bit of a rambling mood.

TL;DR: I know very little to nothing about CG, at least not enough to be a useful help in that department. I wrapped CGAL to hopefully demonstrate how even beast like this library can be repurposed in Julia without reinventing the wheel and aid me in academia. Despite this, there's more than enough room for not only these kinds of wrapper packages, but as well as pure Julia implementations of the same algorithms. Furthermore, testing both approaches should be most interesting, taking into account pros and cons of each approach, seeing which could make more sense or generally be worth more following.

I must confess that I know/recall very little CG, don't really have much knowledge in the field, feeling I wouldn't be much help in that department. This package exists is as both (yet another) proof of concept that leveraging Julia's C-like lib wrapping capabilities potentially cuts virtually immeasurable costs -- be it time or other resources -- implementing and debugging complex algorithms, e.g., aiming at somewhat avoiding your effort with Meshes.jl, and as a foundation for some academic work of mine.

Of course, this is not to say the entire of the JuliaGeometry organization should be ignored. This should be seen more as an alternative of sorts to what the current ecosystem already provides.

Admittedly, when I started doing this, GeometryBasics.jl wasn't around just yet, or at the very least in its infancy. Haven't kept track of things, but it looked promising then and I'm guessing it's pretty good right now.

Another example is VoronoiDelaunay.jl, which I've found can produce, in some cases, wrong results. Granted, I haven't yet reported this (my bad), and I've tested very little, but enough to obtain different results using that package and CGAL.jl. Performance at the time seemed comparable, which is nice to hear too (one way or the other).

Nonetheless, I also suspect that implementing a lot of things in pure Julia is also beneficial since I've been amazed more than once at how fast the language can be in certain scenarios without resorting to native C/C++ code. This is enough suspicion for me to believe that, despite potentially reducing "code duplication" by leveraging already existing code (in a foreign language, no less), there is more than enough room to experiment and re-implement. Despite the latter being relatively dangerous, it might not be that problematic that one should simply not try.

Back to the issue at hand: don't hold your breath, but don't lose hope either. I can see myself getting around to writing more examples, but I don't really have a schedule in mind. I'll reopen this then. Or not, if anyone else reading is willing to give it a hack, don't be shy! I'll gladly review and accept it.

juliohm commented 3 years ago

Thank you @rgcv for the detailed replies. I am starting Meshes.jl both because I need it as a building block in the GeoStats.jl stack, and because it is a good opportunity to dive into CG. The GeometryBasics.jl package has a very limited design, and that is why I had to fork a new project. I will try to contribute to CGAL.jl as I get more experience on specific topics.