[ANN] Meshes.jl - Computational Geometry in Julia

[juliohm]

Meshes.jl provides efficient implementations of concepts from computational geometry and finite element analysis. It promotes rigorous mathematical definitions of spatial discretizations (a.k.a. meshes) that are adequate for describing general manifolds embedded in Rⁿ, including surfaces described with spherical coordinates, and geometries described with multiple coordinate reference systems. Our ambitious goal is to provide all the features of the CGAL project in pure Julia.

Unlike other existing efforts in the Julia ecosystem, this project is being carefully designed to facilitate the use of meshes across different scientific domains. We follow a strict set of good software engineering practices, and are quite pedantic in our test suite to make sure that all our implementations are free of bugs in both single and double floating point precision. Additionally, we guarantee type stability.

The design of this project was motivated by various issues encountered with past attempts to represent geometry, which have been originally designed for visualization purposes (e.g. GeometryTypes.jl, GeometryBasics.jl) or specifically for finite element analysis (e.g. JuAFEM.jl, MeshCore.jl). We hope to provide a smoother experience with mesh representations that are adequate for finite finite element analysis, advanced geospatial modeling and visualization, not just one domain.

Documentation

The project is being actively developed, and we didn’t have time to document it properly yet. The documentation in the master branch illustrates some of the current functionality: https://juliageometry.github.io/Meshes.jl/dev

Roadmap

I am finishing a pure Julia implementation of the FIST algorithm for triangulation of polygonal areas with holes, which are quite common in GIS applications. This is the same algorithm behind the widely used Mapbox’s earcut.hpp library. After this is done, I will start implementing other tesselation and meshing algorithms of 2D manifolds embedded in 3D. Please open an issue if you would like to see a specific algorithm implemented.

We support basic plotting features via Plots.jl recipes, but the plan is to migrate these recipes to Makie.jl when its recipe system becomes available. Help is appreciated, especially if you are familiar with the AbstractPlotting.jl internals. In the long-run, it would be ideal to see more synergy between the Makie.jl stack and Meshes.jl (cc: @sdanisch @jkrumbiegel).

Acknowledgements

I would like to thank all contributors of GeometryBasics.jl for some of the key ideas. Your names are in the copyright notice:

https://juliageometry.github.io/Meshes.jl/dev/about/license.html

Thanks to @serenity4 for very interesting design discussions, proposals and PRs, and for other folks who are also interested in this effort (cc: @ElOceanografo @goretkin @briochemc).

Thanks to @cormullion for helping with another awesome project logo made with Luxor.jl

[briochemc]

Not sure, but I think this overlaps with @gaelforget’s interests/packages! (Thinking about MeshArrays.jl in particular.)

[juliohm]

Update

FIST triangulation of polygonal areas is now available. It takes an arbitrary polygonal area as input and outputs a mesh of triangles.

Consider for example this polygonal area as input:

We can discretize it with FIST and get the following mesh:

This is useful for plotting polygonal areas with holes common in GIS applications (e.g. geographic maps). I am stress-testing the implementation with various polygonal areas, and trying to find the time to handle degenerate polygons with self-overlapping edges.

For examples of usage, please check the test suite in the master branch: https://github.com/JuliaGeometry/Meshes.jl/blob/cd8f8cce1a938c7576429138bfa7c9b83814f755/test/discretization.jl#L32-L36

[juliohm]

Meshes.jl v0.10 is out with tons of new features. We now have various partition, neighbor search, sampling, intersection methods for various geometries and meshes.

GeoStats.jl v0.22 is now completely refactored to use meshes, and all previous tests have passed. This is another indication that we are moving in the right direction.

The next steps include implementing a proper data structure for unstructured meshes to navigate the different faces efficiently, and drafting Makie.jl recipes in a separate playground package. In case anyone wants to help with the visualization effort, please get in touch.

Best,

[juliohm]

Hi everyone, I’d like to share a final update on Discourse regarding the Meshes.jl effort. Future updates will be shared on our Zulip channel, which is where we are spending most of our time discussing computational geometry and related topics.

In this latest release, we have various new features including Douglas-Peucker simplification of polygonal chains and areas, a new triangulation algorithm for polygonal areas by Dehn 1899, a new half-edge data structure with efficient topological relations (boundary, coboundary, adjacency), and I have just finished a first subdivision algorithm by Catmull-Clark to refine and smooth meshes, which is what I am gonna illustrate here.

Suppose you are given a mesh of Beethoven:

This mesh is stored in a PLY file, so we will load it with the PlyIO.jl package:

using Meshes
using PlyIO

function readply(fname)
  ply = load_ply(fname)
  x = ply["vertex"]["x"]
  y = ply["vertex"]["y"]
  z = ply["vertex"]["z"]
  points = Point.(x, y, z)
  inds = ply["face"]["vertex_indices"]
  connec = [connect(Tuple(ind.+1)) for ind in inds]
  SimpleMesh(points, connec)
end

mesh = readply("bethoven.ply")

We can perform the refinement with:

refined = refine(mesh, CatmullClark())

And it looks like this:

The refinement is taking 60ms approximately in this mesh with 5000 elements, but I think we can make it even faster with more optimizations in the half-edge structure.

We can repeat the refinement multiple times and there is a theorem that says that this process converges to a smooth and nice spline surface. Here is a zoom in the statue after 3 refinement steps:

Notice how the surface is much nicer visually compared to the original control mesh. I learned that this method is the same method used by Pixar in the movie Geri’s Game to render Geri’s hands and head.

You can watch it here:

Geri's Game

We are still polishing the minor details, but if you would like to give it a try, feel free to checkout the master branch. A new release should come out by the end of the month with more planned features.

[sijo]

That looks great! Please keep sharing important updates here if it’s not too much work, for those of us not on Zulip!

[timmm]

This is great. Looking forward to how this develops.

At the moment I get Julia to build CGAL and call this through Julia in quite a messy way:

GitHub - Timmmdavis/BuildCGAL: Builds CGAL and scripts for meshing

As such I would love to see Julia versions of polygon mesh processing and advancing front.

Are you going to keep the algorithm names and function inputs the same in the Julia implementation? The CGAL documentation is really well written.

Cheers,
Tim

[juliohm]

Hi @timmm there is also GitHub - rgcv/CGAL.jl: CGAL meets Julia if you are interested in interfacing with CGAL directly. Regarding the names, we are trying to pick the most mathematically correct names whenever possible.

Cheers,

[empet]

Are there packages that read obj, stl and off files, too? A lot of meshes are available in these formats, too

[juliohm]

@empet you can open any mesh file in meshlab and convert it to PLY to read with PlyIO.jl for example. The meshlab software can also fix issues with the mesh such as dealing with non-manifold faces, remove repeated vertices, etc.

If you prefer the command line, there is also Python’s meshio: meshio · PyPI

[empet]

Thanks, I know about meshio, because three years ago, incidentally, I plotted Beethoven, too, and read the ply file with meshio: https://chart-studio.plotly.com/~empet/14749/mesh3d-with-intensities-and-flatshading/#/. Seeing PlyIO.jl, I thought there is a Julia package that eventually can read particular mesh files.

[juliohm]

There is MeshIO.jl but it is currently tied to GeometryBasics.jl.

I like the approach taken by PlyIO.jl, because it is based on simple Julia dictionaries and arrays. Everyone can manipulate the data easily that way. Writing a OffIO.jl with the same design shouldn’t be difficult.

[paulmelis]

@juliohm

Hi everyone, I’d like to share a final update on Discourse regarding the Meshes.jl effort. Future updates will be shared on our Zulip channel, which is where we are spending most of our time discussing computational geometry and related topics.

In echoing another reply above, that’s too bad. I guess I’ll subscribe to the github page then instead, as I really don’t want to have to follow yet another platform (apart from this Discourse, Discord, Teams, our internal Element chat, etc). I’m not familiar with Zulip, but it seems like a Slack clone, so does it really facilitate discussions as well as Discourse?

@juliohm

In this latest release, we have various new features including Douglas-Peucker simplification of polygonal chains and areas, a new triangulation algorithm for polygonal areas by Dehn 1899, a new half-edge data structure with efficient topological relations (boundary, coboundary, adjacency), and I have just finished a first subdivision algorithm by Catmull-Clark to refine and smooth meshes, which is what I am gonna illustrate here.

Nice!

@juliohm

This mesh is stored in a PLY file, so we will load it with the PlyIO.jl package:

How does PlyIO.jl relate to MeshIO.jl, which also supports PLY? From recent tests with MeshIO it seemed it did not fully work with binary PLY files, is PlyIO more mature in this respect? And could these packages somehow be merged?

Edit: just noticed you answered this above

@juliohm

Notice how the surface is much nicer visually compared to the original control mesh. I learned that this method is the same method used by Pixar in the movie Geri’s Game to render Geri’s hands and head.

You would also need to implement their extensions for semi-sharp creases (easy) and scalar fields (still covered by a patent I believe) to be able to make a clone of Geri

@juliohm

Our ambitious goal is to provide all the features of the CGAL project in pure Julia.

A question somewhat related to this quote from your original announcement, which by the way would make me really happy if you manage that goal. I recently was looking for an implementation of a mesh morphing algorithm, something like Alexa’s early work. I know there’s been a lot of progress in the field since then, but I only needed something simple and it seemed like a fairly straightforward algorithm to implement and therefore might have a higher chance of already being coded by someone. However, I could not find much available open-source code, nor of other morphing algorithms. In general, it seems not much of the research on geometry processing ends up in packages like CGAL, or is provided (even in research code form) as open-source. As you’re working in this field would you have insights as to why that is? I can guess, but I don’t really know the true reasons, for example:

• The research is more aimed at theoretical results than on providing practical tools, partly due to the formal nature of this type of research
• Creating robust geometry processing code is hard and there’s direct commercial value for many research outcomes in industry and creative 3D, so the implementation effort is concentrated at companies supporting these markets and less from “hobbyists”
• Research in this field seems often to be done in matlab and so might be perceived to be less directly useful to others than implementations in, say, C++
• It just isn’t part of the culture of the field to share code

Edit: nice counter-example today on twitter: https://www.quadmesh.cloud/. Results look amazing and…

Demo and Code
An implementation will be soon available…

[heliosdrm]

Thanks for this great package!

I’m a bit puzzled about the relationship betwee Meshes.jl, MeshIO.jl and GeometryBasics.jl. The README of MeshIO says that " Functions for mesh manipulation can be found in Meshes", and the Mesh type imported from Meshes is parametrized in a way that looks much like the Mesh type from GeometryBasics.

However, it seems that I cannot directly use the functions of Meshes.jl on objects loaded with FileIO + MeshIO, and I cannot save a SimpleMesh with MeshIO. Is that right? How could I save a SimpleMesh as an OBJ file?

[Raf]

It’s a fork of GeometryBasics.jl: https://github.com/JuliaGeometry/GeometryBasics.jl/pull/101

The commit history was deleted so you can’t see the previous (e.g. Simon Danischs) commits, otherwise it would be clearer what happened.

[juliohm]

@paulmelis I think the computational geometry community is happy with open source in general. I think most libraries are written in low-level languages though, and end up lost in the researcher’s personal websites.

[juliohm]

@heliosdrm many packages in JuliaGeometry need to be updated. MeshIO.jl was written before the existence of Meshes.jl and could be generalized or refactored to support Meshes.jl meshes.

I was talking to Simon, and the plan is to first concentrate energy on writing Makie recipes for Meshes.jl types in a separate repository so that people can easily visualize SimpleMesh and other types from the project. I’ve registered a new package yesterday where I plan to work on these recipes given that the recipe system is back online: https://github.com/JuliaGeometry/MeshViz.jl/blob/master/src/MeshViz.jl

Only after that I will be able to work on IO packages. So if you would like to see more IO support right away in MeshIO.jl, please help with PRs.

[heliosdrm]

I don’t know all the details of the specifications of mesh file types (e.g. OBJ, which is the one I’m using), or the internals of MeshIO. So, to work around the current limitation I have been looking into the structures GeometryBasics.Mesh and Meshes.Mesh objects, and made a couple of functions to transform one into another. (I wanted to load a mesh from an OBJ file, refine it as in your example, and then save the result.)

This has solved my problem, but I guess this is not something worthwile of a PR in any of those two packages, since I understand that none of those two packages are meant to depend on the other.

[juliohm]

Thanks for sharing @heliosdrm. If we could write small packages for specific file formats such as OBJ and OFF similar to PlyIO.jl, then these packages would give the user full flexibility to manipulate the contents of the file. At the end MeshIO.jl could just depend on these packages to do the basic read with a single load command.

[Klaas_Pauly]

@heliosdrm

I cannot save a SimpleMesh with MeshIO. Is that right? How could I save a SimpleMesh as an OBJ file?

I’m also currently figuring that out, trying to save to PLY file. PlyIO is currently also undocumented. I’ll keep you posted on progress with my function and/or documentation.