Delaunay Triangulation

[nlsn]

Presentation

I'd like to announce a repository I'm working on and invite people to contribute.

It is about Delaunay Triangulation and Refinement. My goal is to implement a 3D tetrahedralization and refinement, targeting WebAssembly in the future. Up until now, the repository is about to be published to CratesIO and a proper API is missing.

I do expect to find hard problems and to succeed solving them. If you are interested in this implementation and wanna join, I hopefully expect we may have a nice development experience together.

The link to the repository is https://github.com/nelsonatgithub/nlsn-delaunay-refine

Delaunay Triangulation

Delaunay triangulation is a special triangulation, where the circumcircle of any triangle in the triangulation does not contain any vertex in its interior. L’idée was proposed in 1934 by Boris Delaunay in his paper Sur la Sphère Vide [B. Delaunay, Sur la sphère vide. A la mémoire de Georges Voronoi, Bulletin de l’Académie des Sciences de l’URSS. Classe des sciences mathématiques et naturelles, 1934, no. 6, 793–800.]. The triangulation’s emptiness property maximizes the smallest interior angle of the triangles in the triangulation and has important applications to several areas, including mesh generation.

How to Contribute

The first thing to do is to clone the repository, with a cargo environment. Fork it if you want. Run the tests. Then read the code.

Open an issue with suggestions, code reviews, refactoring.

As the repository is at initial state of development, the code is mostly under naive implementation. I'd ask as many suggestions and opinions as possible. I hopefully expect this to be a great experience to everyone.

About me

Nice to meet you. My name is Nelson. I'm a developer and engineer. I've got experience in C, Javascript, Java and Python. Professionally, I did web development under Node, React, and AWS services and Android app development. I'm a Linux user and a Shell scripter by hobby.

I'm just new in this forum. I've been learning Rust for about 1 year. And a few months ago, I've decided to put this knowledge into practice and create an open source library. Now I've got an interesting implementation of an algorithm of my choice to share.

[Michael-F-Bryan]

At $JOB my current task requires updating code that works with Triangle.NET (the C# library we're using for 2D triangulation) to make it avoid certain areas, so this announcement is quite relevant to me.

Have you put much thought towards constrained delaunay? I've found the concept of "holes" pops up fairly often in the real world (e.g. I'm using triangulation to generate a navmesh for path finding and want to make sure it won't accidentally cut a part in half).

I know the project is still in its infancy, but do you think it's theoretically possible to be generic over 2D and 3D? Does the algorithm change much between triangles and tetrahedrons?

Did you have any applications in mind when making this library? I've often found it helps to have a real, tangible application that needs to use your library because you start thinking like an end user, making you think about ergonomic how to provide an ergonomic API with good documentation and examples.

[nlsn]

Thanks for reply!

Triangle.NET is a port to triangle library written by Jonathan R. Shewchuk, which is, by the way, one author of [Delaunay Mesh Generation. 2013, Taylor & Francis Group, LLC]. He is an authority in the subject of Delaunay Triangulation, making good publications with very well organized knowledge.

I tried to port triangle to wasm through Emscripten in this repository [https://bitbucket.org/nelsonkenzotamashiro/delaunay_shewchuk]. I must confess I'm trying to port a 3d tetrahedralization it's been some time. hehe

I've actually quit the emscripten project because of C interface requirement, which is really expensive. In this point, I do prefer Rust, due to scalability, maintainability and portability. Also the open source triangle lib from sir Schewchuk has no support to tetrahedralization.

@Michael-F-Bryan

I know the project is still in its infancy, but do you think it's theoretically possible to be generic over 2D and 3D? Does the algorithm change much between triangles and tetrahedrons?

The book presents an approach through Bowyer Watson incremental insertion algorithm and conflict maps.

The conflict map will relate existing triangles inside a delaunay triangulation to vertices to be inserted, which would break the delaunay property. If the vertex is contained by the circumcircle of a triangle, the triangle it is said to encroach the vertex and it breaks the delaunay property.

The incremental insertion allows to insert a vertex inside an existing triangulation, making the proper modifications to create new triangles and deleting existing ones and still keeping the delaunay property. It inserts the conflicting vertices and digs adjacent triangles for more encroachments.

In 3D case, the algorithm will dig adjacent tetrahedrons instead of triangles. And since verifying circumcircle (actually, a circumball) containment in 3D is a matter of calculating the determinant of a matrix with an additional degree, the maths would not be the main problem.

Problems like sliver exudation are known. But as soon as I know there are solutions, I see it as a matter of guaranteeing a proper implementation to these existing solutions. It is a great challenge.

I must confess I still need to study a bit more about the 3D case, in order to give a precise answer though.

When you say "generic", you mean calling the API to 3D in the same way we call the 2D API or extending the trait interfaces. Right?

In the current state, I agree that there are still many "triangle" words inside the "triangulation". It can't persist in 3D, if generalizing the interface is the objective. A higher level of abstraction is necessary.

Up until now the focus was the MVP of triangulation. So currently the code is simple.

Actually, I'm quite favorable to just copy, paste and rename triangles to tetrahedrons whenever it is necessary, in order to repeat the extensible behavioral patterns of the algorithms. I don't think I would extend the algorithm to a 4th dimension. Too much of generalizations seems to be an over engineering.

@Michael-F-Bryan

Have you put much thought towards constrained delaunay?

Currently, the code expects a well behaved user. But I'm working on how to provide the validation methods to avoid cutting the mesh in half. I think I'll just force a panic if it happens. There is still no line intercepting methods to this purpose.

@Michael-F-Bryan

Did you have any applications in mind when making this library?

I had in mind displaying the mesh in canvas through WebGLContext. I've got some experiments in this repository [https://github.com/nelsonatgithub/nsln-react-webgl]

By the way, you have a repository that also uses canvas to draw meshes, don't you?