3D Delaunay

[SimonDanisch]

Hi,
would it be sensible to just wrap this piece of code and port it to julia when there is time?
http://www.codeproject.com/Articles/587629/A-Delaunay-triangulation-function-in-C
Like this we could already have 3D Delaunay available in Julia, which could be used in PetrKryslUCSD/JFinEALE.jl#3 for example.
Also, do you have any plans to merge your efforts into one big 3D geometry package, including mesh algorithms, triangle intersections, your geometric predicates etc? Meshes.jl also has some algorithms, and I'm trying to add some to it as well. ( JuliaGeometry/OldMeshes.jl#32 )
It doesn't necessarily need to be merged, but it would be nice if all the packages use the same design principles and the same vector library. I'm in the middle of implementing fixedsizearrays, which hopefully can be the basis for any 3D vector class. ( FixedSizeArrays.jl )
If we have a nice solid basis, it would also be a lot simpler, to write the appropriate visualization code.
Also, if we take care and allow for Float32 types and don't use complex data structures, we might be able to get OpenCL acceleration for the geometry algorithms for free, which would be incredibly cool.
(Given, that JuliaGPU/OpenCL.jl#29 ever succeeds).

Best,
Simon

[PetrKryslUCSD]

Simon,

Adding Delaunay triangulation capabilities to Julia is certainly worthwhile. It needs to be realized however that unconstrained triangulation is of limited usefulness. Also, compared to CONSTRAINED triangulation, unconstrained triangulation is easy. The real difficulty comes with triangulating domains with boundaries.

I believe it would be quite worthwhile to wrap one of the public-domain meshers in a Julia package, for instance tetgen. (This could be in addition to unconstrained (Delaunay) triangulation capability.) Then having the mesh represented in some standard format (for instance as proposed in Meshes.jl) would be quite useful.

Petr

[SimonDanisch]

I see, thanks for the clarification.
Sounds like a bigger project though.
CGAL seems to be interesting as well!

[skariel]

Wrapping Tetgen should be easy, it seems to me this is the way to go.

Nevertheless a pure Julia implementation has some value: VoronoiDelaunay.jl is faster than current alternatives, it will support distributed execution, and it is MIT licensed.

This library started without a need for constraining Delaunay meshes as I want to write a moving-mesh hydrodynamical simulation (see images below) that constrains only the Voronoy tessellation. This simulation method was developped for computational cosmology (which I practice daily as a post-doc) but it should be very useful in an engineering context.

I suggest we create a "Computational Geometry with Julia" organization in Github much like the Julia Webstack, Julia Optimization, or Julia Astro and develop all relevant projects there

Regarding the timeframe to develop the 3D in Julia -- It goes really slow as I work, try to develop a startup and have kids :) So I would say tentatively by end of year. I have a plan to automate code generation for flips. This is one of the advantages of Julia, for 2D I manually wrote 9 flip functions but for 3D it will require 64, all highly error prone. Other libraries write less code by using tables etc but sacrifice speed.

Any thoughts?

[SimonDanisch]

VoronoiDelaunay.jl is faster than current alternatives, it will support distributed execution

That's exciting and really proves the point, that a high-level language helps to make code fast, even though that it's in theory just barely on eye level with C-performance.

Any thought?

I'm really inexperienced with geometric algorithms, but if I understand the problem correctly, a recursive staged function could help.
You could have a flip type with the parameters encoding what flip you want to perform, and then emit optimized code for that in the staged function. This can be really fast and concise, if there are no conceptual problems.

immutable Flip{F} end

const lookuptable = [...]
stagedfunction flip!{F}(tess, f::Flip{F})
    # probably via the mentioned lookup table?! 
    newflip = Flip{lookuptable[F]}()
    return quote 
        #... flipping code
        flip!(tess, $newflip) #recursive call
    end
end

I hope this helps, even though that I don't really know how the triangulation algorithm works ;)

[SimonDanisch]

I suggest we create a "Computational Geometry with Julia" organization in Github much like the Julia Webstack, Julia Optimization, or Julia Astro and develop all relevant projects there

I guess the field of Computational Geometry would definitely qualify for it's own group!
However, it would be nice to carefully design it together with the visualization libraries, to enforce interoperability. So maybe, JuliaGraphics could be the umbrella group!?
For me that would make some sense, as geometry algorithms are tightly coupled to visualizations.
But, if you follow this argument, anything handling data can be seen as tightly coupled to visualization, as most data is hard to understand without a proper visualization.
What are your thoughts?

[SimonDanisch]

To get things started I created JuliaGeometry and an empty Package for the TetGen wrapper:
https://github.com/JuliaGeometry/TetGen.jl

[PetrKryslUCSD]

Ariel,

Congratulations on the impressive results from the mixing simulation! That
is quite something...

About the simulation though: it appears that your code must actually handle
boundaries: internal ones, the surface of the paddle. Do you do this by
distributing strategically points on the surface?

P

On Sun, Feb 8, 2015 at 11:50 PM, Ariel Keselman [email protected]
wrote:

Wrapping Tetgen should be easy, it seems to me this is the way to go.

Nevertheless a pure Julia implementation has some value:
VoronoiDelaunay.jl is faster than current alternatives, it will support
distributed execution, and it is MIT licensed.

This library started without a need for constraining Delaunay meshes as I
want to write a moving-mesh hydrodynamical simulation (see images below)
that constrains only the Voronoy one. This simulation method was developped
for computational cosmology (which I practice daily as a post-doc) but it
should be very useful in an engineering context.

I suggest we create a "Computational Geometry with Julia" organization in
Github much like the Julia Webstack http://juliawebstack.org/, Julia
Optimization http://www.juliaopt.org/, or Julia Astro
http://juliaastro.github.io/ and develop all relevant projects there

Regarding the timeframe to develop the 3D in Julia -- It goes really slow
as I work, try to develop a startup and have kids :) So I would say
tentatively by end of year. I have a plan to automate code generation for
flips. This is one of the advantages of Julia, for 2D I manually wrote 9
flip functions but for 3D it will require 64, all highly error prone. Other
libraries write less code by using tables etc but sacrifice speed.

Any thoughts?

[image: screenshot from 2015-02-09 09 42 17]
https://cloud.githubusercontent.com/assets/2347816/6102484/03abd662-b040-11e4-8d55-7e6cabda41e1.png

[image: screenshot from 2015-02-09 09 42 35]
https://cloud.githubusercontent.com/assets/2347816/6102486/08061470-b040-11e4-85ee-600e38c164a5.png

—
Reply to this email directly or view it on GitHub
#8 (comment)
.

Petr Krysl
Professor
University of California, San Diego
Skype: Petr.Krysl.UCSD.EDU, Office: 858-822-4787
http://hogwarts.ucsd.edu/~pkrysl/

[skariel]

Petr you should congratulate Volker Springel not me! These images are taken from his paper describing the method in details see section 8.9 on page 52 The paper is also linked from this package readme file) See also movies here: http://www.mpa-garching.mpg.de/~volker/arepo/ and some application in cosmology here: http://www.cfa.harvard.edu/itc/research/movingmeshcosmology/ and here: http://www.illustris-project.org/

I would like to bring this method to the industry. Boundaries are built by having two set of points that move together as a rigid body. One set is of "red" points inside the material as you can see above and the other set of "blue" points outside the material. Building complex and moving models like this seems much easier than using non-voronoi meshes. Note that no point is actually on the surface, the surface is built by Voronoi edges while Voronoi generators are inside the cells.

[afasc]

I am currently looking for a way to perform 3D Delaunay and Voronoi tessellations of a given pointset. Has this progressed any further?

[fverdugo]

Hi! In our lab, we have implemented a simple Julia wrapper to Qhull in order to compute Delaunay triangulations in arbitrary dimensions.

https://github.com/gridap/MiniQhull.jl

We interface with Qhull via ccall (instead of PyCall), so you don't need to install scipy in your system, just Qhull itself and a C compiler. Moreover, we are using the re-entrant version of Qhull. Thus, our wrapper should be thread-safe (even though we have not confirmed it).

Hope you find the project useful. Contributions and enhancements are welcome!