Discussion for 3d port

[nemo9955]

Hello, I am tempted to convert this library to work with 3D points and graphs. I looked over index.js and managed to understand most of the parts. Main difficulties are with the hull aspects hullNext, hullPrev, hullTri, hullHash, etc and a little with _legalize , I imagine these 2 are kind of core functionality so should be much better understanded.

Contents of _hashKey I also do not understand, but as it is a 2 value hash function, i can just use a slower Map and call it a day. This way i can ignore pseudoAngle also. Most 2d functions can be implemented in 3d or have variants in robust-predicates : dist, inCircle (use insphere), circumradius, circumcenter, orient2d (use orient3d).

I think most difficulties will rise from the increasing hull; in 2D, a new point results in a new triangle, but in 3D it could result in ~3 new triangles depending on neighbors.

Will start also to check delaunay-triangulate as it has a 3D delaunay implementation, but feel like delaunator is a better starting point since it is more used and maintained.

My motivation for doing this is mostly for procedurally generating points on a sphere (planet) , but feel that the way I am combining point generation, running d3-geo-voronoi, computing a graph with dijkstra and then drawing with THREE.js I am wasting a lot of time with arrays and conversions. I'm content with the possibility of this topic being too advanced for my skillset and just drop the port.

[Fil]

Ref. https://github.com/Fil/d3-geo-voronoi/issues/36

[Seventh7th-Son]

Here is an example of the delaunay library 3D port that I made for the MoI3d Node Editor. It can be done.

A delaunay surface climbing up and down a point cloud 3d matrix.

[Seventh7th-Son]

This library can make a 3d hull from a point cloud by using the outer most points.

https://github.com/bjnortier/qhull

[redblobgames]

I learned from Fil's page how to use Delaunator on a sphere, and wrote up my notes and then made a planet generator. It's relatively easy if you only want to work on spheres, and I'm guessing a lot more work if you want it to work on arbitrary 3D.

I made an animated gif to show what's going on: you place points on the sphere, "unwrap" it into a plane, run Delaunator, then "wrap" it back onto the sphere. The tricky part is that it leaves a little hole at the end (corresponding to the convex hull) and you have to add one extra polygon to fill that hole.

[Fil]

wow what an amazing animation @redblobgames !

[nemo9955]

@redblobgames I've been admiring your work since like 2014 starting with https://www.redblobgames.com/grids/hexagons/ ! I've looked over your entire site multiple times, especially the procgen planets :D

To be honest, while looking over 1843-planet-generation/sphere-mesh.js I got the idea to adapt delaunator. Was originally expecting the sphere mesh to not use any Delaunay at all, and just "logically" assemble the edges based on the known order and position of the Fibonacci points generation!

@Wayne5202 https://github.com/bjnortier/qhull seems like a perfect lib actually, considering I am interested (at the moment) in a sphere, a convex hull for the whole thing seems apropriate. Will definitely fallback to it this "experiment" does not work!

As a little more context, at the moment I do want to work with a sphere, but I want options in the future to be able to do other shapes and 3D terrain/detail on those shapes for this project , and I want to find a good balance between making implementing something proper and getting stuff to work in a reasonable time so I do not lose motivation.

[nemo9955]

Hello, Managed to convert all the parts I manage to understand but could not comprehend the hull and legal things and result makes no sense .

Few things that caught me by surprise :

1. orient3d needs some extra point for the side of the plane, tried at random 3 variations but none made a difference : a. 0,0,0 so it would point inside the sphere b. 0, 99990, 0 to point in a static spot above the sphere c. x 2, y 2, z * 2 to point outside the sphere

2. hullHash[(key + j) % this._hashSize] in the find a visible edge on the convex hull using edge hash zone a. cannot make sense how/why to increment a hash, b. tried a Map and adding isFinite/isNaN to the -1 checks

3. inCircle in 3d and insphere implemented code was ok, but result still random a. insphere also requires an extra point which i tried to generate towards 0,0,0 ... did not try other direction(s) b. inCircle i hacked using 3D circumcenter, circumradius and dist for a 3 point sphere

Also kept getting 4294967295 as an halfedges , did not debug the source but appeared only in the hbl, halfedges[ar], bl/_legalize series of this._link() and hacked a if (b == 4294967295) b = - 1; in hopes it was a missed treated -1 case.

Will try later today some variations on params and to see maybe on flatter 3D points it works (but doubt it). If anyone can see some mistakes or provide some clarifications will try a bit more on it, but most probably it is just out of my league.

50 Fibonacci points code can be seen live here : https://nemo9955.github.io/make-world/pages/World.html copied the file in my repo so i can easilly test it: https://github.com/nemo9955/make-world/blob/master/src/utils/delaunator_3d.ts i have also the 2d/original here co compare results : https://github.com/nemo9955/make-world/blob/master/src/utils/delaunator_2d.ts

[nemo9955]

Managed to find the perfect solution, and of course it was under my nose.

Searching around, stumbled across this lib : https://github.com/mauriciopoppe/quickhull3d quickhull3d was more recent so that was good, started reading it, accepts array or arrays for points input but not that big an issue.

It is a convex hull algorithm not a delaunay one, but with some extra steps got a "planet" (sphere+noise elevation) to draw without missing the valleys, by running the ConvexHull (THREE.js implementation of that lib) on a sphere, and then adding the noise elevation to each points.

Got 10k points on a perfect sphere to generate in 0.4s .... 10k in 0.7s , 100k in 5s and 500k in 25s. Results are better than d3-geo-voronoi(delaunator) with some hacks implemented in local (https://github.com/Fil/d3-geo-voronoi/issues/36) so it's an improvement.