unity-delaunay
unity-quickhull
| unity-delaunay | unity-quickhull | |
|---|---|---|
| 6 | 1 | |
| 768 | 168 | |
| - | - | |
| 2.3 | 10.0 | |
| 9 months ago | almost 4 years ago | |
| C# | C# | |
| MIT License | MIT License |
Stars - the number of stars that a project has on GitHub. Growth - month over month growth in stars.
Activity is a relative number indicating how actively a project is being developed. Recent commits have higher weight than older ones.
For example, an activity of 9.0 indicates that a project is amongst the top 10% of the most actively developed projects that we are tracking.
unity-delaunay
-
Voronoi Diagram and Delaunay Triangulation in O(nlog(n)) (2020)
I wrote a moderately popular Delaunay/Voronoi library for Unity a few years back [1] with a neat little demo video [2]. I implemented the incremental Bowyer-Watson algorithm for generating the triangulations, and then took the dual to generate the Voronoi tesselation (I also added a "clipper" that clips the voronoi diagram to a convex outline, which was fun, I haven't seen that anywhere else before and had to figure out how to do it myself).
Bowyer-Watson (which is described in this article) seems very simple to implement when you start: just start with a "big triangle" and then add points iteratively to it, and perform the flips you need to do. To do it performant, you have to build up a tree structure as you go, but it's not very tricky.
However: almost every description and implementation of Bowyer-Watson I could find was wrong. There's an incredibly subtle and hard to deal with issue with the algorithm, which is the initial "big triangle". Most people who implement it (and indeed I did the same initally) just make the triangle big enough to contain all the points, but that's enough: it needs to be big enough to contain all the points in all the circumcircles of the triangles. These circumcircles can get ENORMOUS: in the limit of three points on a line, it's an infinite half-plane. Even if they aren't literally collinear, just close, the triangle becomes way to huge to deal with.
The answer is that you have to put the points "at infinity", which is a very weird concept. Basically, you have to have special rules for these points when doing comparisons, it's really tricky and very hard to get right.
If I were doing this again, I wouldn't use Bowyer-Watson, this subtlety is too tricky and hard to get right. Fortune's sweep-line is more complex on the surface, but that's the one I would go with. Or the 3D convex hull technique (which I also wrote a library for, by the way [3]).
[1]: https://github.com/OskarSigvardsson/unity-delaunay
[2]: https://www.youtube.com/watch?v=f3T5jtsokz8
[3]: https://github.com/OskarSigvardsson/unity-quickhull
-
Using Voronoi polygons for simplified continent generation
Fortunately for me, the internet came in clutch with the Oskar Sigvardsson Delaunay Unity Library with the vast majority of the work done for me!
- How to find the minimum enclosing circle of a set of points. Made this to build my "super triangle" to start off my delaunay triangulation, but it can also be used to dynamically figure out where to center your camera and with how much zoom to keep everything you want in view.
-
How to calculate the circumcenter of a triangle. Working my way up to Delaunay Triangulation, this is how I'm finding my triangle's circumcenters.
Here's a link for the destruction use i mentioned: https://github.com/OskarSigvardsson/unity-delaunay
- In my hubris, I endeavor to make a procedural planet out of tiles
- Is there a good blender or unity tutorial for how to break your models to be used in explosions?
unity-quickhull
-
Voronoi Diagram and Delaunay Triangulation in O(nlog(n)) (2020)
I wrote a moderately popular Delaunay/Voronoi library for Unity a few years back [1] with a neat little demo video [2]. I implemented the incremental Bowyer-Watson algorithm for generating the triangulations, and then took the dual to generate the Voronoi tesselation (I also added a "clipper" that clips the voronoi diagram to a convex outline, which was fun, I haven't seen that anywhere else before and had to figure out how to do it myself).
Bowyer-Watson (which is described in this article) seems very simple to implement when you start: just start with a "big triangle" and then add points iteratively to it, and perform the flips you need to do. To do it performant, you have to build up a tree structure as you go, but it's not very tricky.
However: almost every description and implementation of Bowyer-Watson I could find was wrong. There's an incredibly subtle and hard to deal with issue with the algorithm, which is the initial "big triangle". Most people who implement it (and indeed I did the same initally) just make the triangle big enough to contain all the points, but that's enough: it needs to be big enough to contain all the points in all the circumcircles of the triangles. These circumcircles can get ENORMOUS: in the limit of three points on a line, it's an infinite half-plane. Even if they aren't literally collinear, just close, the triangle becomes way to huge to deal with.
The answer is that you have to put the points "at infinity", which is a very weird concept. Basically, you have to have special rules for these points when doing comparisons, it's really tricky and very hard to get right.
If I were doing this again, I wouldn't use Bowyer-Watson, this subtlety is too tricky and hard to get right. Fortune's sweep-line is more complex on the surface, but that's the one I would go with. Or the 3D convex hull technique (which I also wrote a library for, by the way [3]).
[1]: https://github.com/OskarSigvardsson/unity-delaunay
[2]: https://www.youtube.com/watch?v=f3T5jtsokz8
[3]: https://github.com/OskarSigvardsson/unity-quickhull
What are some alternatives?
delaunator-sharp - Fast Delaunay triangulation of 2D points implemented in C#.
geogram - a programming library with geometric algorithms
delaunator - An incredibly fast JavaScript library for Delaunay triangulation of 2D points