tldr: help I can’t correctly triangulate a GeoJSON polygon in 3D space to make it spherical and it has been haunting me for weeks. The question at the end of this novel is “Is this a poly2tri issue, a turf issue, a projection issue, a math issue or a me issue. If you have any idea how to fix any of this, or a recommendation of a new way to look at things, or a new library, any pointers to resources or just anything, please let me know because I am losing my mind.”
Hello everyone, I am trying to create procedurally generated planets in THREE.js, but I’ve hit a major hurdle. Here is the gist:
I am subdividing my planet into units called provinces. I generate these provinces using voronoi diagrams, specifically d3-geo-voronoi
. After this, I noisify the borders of each province to add a more natural look. Once I have the points that make up a province’s borders, i make a GeoJSON polygon out of them. In order to generate a spherical polygon in 3D I need certain points, to which the mesh can “attach” in order to create the spherical illusion. I achieve this by iterating through the verticies of an icosahedron and using turf.js’s booleanContains
function I am able to find which vertices are inside the GeoJSON polygon. Let’s call these points “inside points”. After acquiring them, I then use a CDT (constrained delaunay triangulation) algorithm, specifically the poly2tri.js library to triangulate the spherical polygon. One small issue, however, is that most CDT algorithms work only in 2D, which is why I project my GeoJSON polygon with spherical coordinates to a planar polygon using d3’s projections (more on that later). This produces the result you can see here:
generation 1
It works! Well, sort of… Some polygons have these slightly darker green spots on them.
problem 1
This is due to the fact that I have underlayed another icosahedron, transparent with a red color, with a radius 0.01 units smaller than the one of the meshes. If we were to look at these spots from a certain angle they appear almost like a crevasse:
crevasse
This sadly means that the triangulation has faults and after reviewing the mesh’s wireframe we can confirm this.
wireframe
Here is what I tried doing:
1) Projections
My immediate first thought was that the projection algorithm had altered the position of the steiner points, thus invalidating the correctness of the wireframe, however after reviewing the projection, that was not the case:
projection 1.
Let’s talk projections. A projection is a function which maps some spherical coordinates of the globe to planar coordinates. Sadly this isn’t so simple, because it is impossible to produce a projection that keeps the shapes of landmasses the same, keeps the distances between points equal, and keeps the area of said landmasses equal. This means that every projection distorts coordinates in one way or another. After looking through some of d3.js’s projection functions I stopped myself at the azimuthal equidistant. Example bellow:
azimuthal equidistant
I chose this one because of its distortion qualities, mainly distortion at the center is minimal and gets bigger and bigger as the chosen point gets away from the center. The equidistant part means that, at least from my understanding, it keeps the distance between some 2 points real and instead distorts the shape and area of the landmasses. I center the projection on the GeoJSON polygon using turf.js’s center
function.
// lng,lat
const c = center(geoObj).geometry.coordinates as [number,number];
// fit range [-90;90]
c[1]-=90;
console.log("found center: ",c);
let projectionFunction = geoAzimuthalEquidistant().center(c);
Another detail worth noting is the existence of the 180th meridian. It is problematic, because the range of coordinates for longtitude is [-180;180] and some polygons have points which cross the 180th degree mark, making it as if the polygon circles the earth. Example points would be ([-175;0],[175,0]). We know this is a difference of 10 degrees, but projections see them as 350 degrees. I deal with this issue by subtracting each point’s longtitude of the polygon with its first points’ longtitude and correcting the range of the new coordinates if they go over the [-180;180] range. This is my projection code:
function rotateCoords(coord:number) {
if(coord>180) return coord-360;
if(coord<-180) return coord+360;
return coord;
}
function projectNormalised(coords:[number,number],lngDelta:number,projectionFunction:GeoProjection):[number,number]
{
// Normalise coords
coords[1]-=90;;
const normalisedCoords:[number,number]=[rotateCoords(coords[0]-lngDelta),coords[1]];;;;
const res = projectionFunction(normalisedCoords) as [number,number];;
return [res[0]/50,res[1]/50];;
}
function projectRegular(coords:[number,number],projectionFunction:GeoProjection):[number,number] {
const res = projectionFunction(coords) as [number,number];
return [res[0]/50,res[1]/50];;
}
and this is some code inside the function that generates the mesh, it shows how I project the shapes, locate the “inside points” of an icosahedron in a polygon and project them too:
let contour:IdentifiablePoint[] = contourSphericalCoords.map((coords,i) => {
const proj = projectNormalised([coords[0],coords[1]],deltaDegree,projectionFunction);
debugPoints.push(new Vector3(proj[0],0,proj[1]))
return {x:proj[0],y:proj[1],id:i};
});
// Remove last points because the repeat with first and poly2tri.js doesnt accept that
contour.splice(contour.length-1,1);
insidePointIndex = contour[contour.length-1].id+2;
const insidePointsSphericalCoords:GeoJSON.Position[] = [];
// Locate sphere mesh points inside province
let startVertexIndex = 0;
let endVertexIndex = positionAttribute.count;
for ( let vertexIndex = startVertexIndex; vertexIndex < endVertexIndex; vertexIndex ++ ) {
vertex.fromBufferAttribute( positionAttribute, vertexIndex );
spherical.setFromVector3(vertex);
// lat long
const cartesianCoords:[number,number] = [MathUtils.radToDeg(spherical.theta),MathUtils.radToDeg(spherical.phi)];
if(cartesianCoords[1]>provinceLowestLat||cartesianCoords[1]<provinceHighestLat) continue;
const normalizedCoords:[number,number] = [rotateCoords(cartesianCoords[0]-deltaDegree),cartesianCoords[1]-90];
if(booleanContains(geoOffsetObj,point(normalizedCoords))) {
// debugPoints.push(new Vector3().copy(vertex));
const coords = projectRegular(normalizedCoords,projectionFunction);
if(trigPoints.find(x=>x.x==coords[0]&&x.y==coords[1])!=undefined)
continue;
trigPoints.push({x:coords[0],y:coords[1],id:insidePointIndex});
insidePointsSphericalCoords.push(cartesianCoords);
debugPoints.push(new Vector3(coords[0],0,coords[1]))
insidePointIndex++;
}
}
For clarification trigPoints is the array of projected inside points. I do, however think that this is not a projection issue, because projections, such as the:
Azimuthal Equal Area
Azimuthal Equal Area
Mercator
Mercator
Equirectangular
Equirectangular
and more produce the same, if not worse results.
2) Inside point partial triangulation
I tried a more unorthodox approach, where I first triangulate the mesh of the inside points and then triangulate the area between the borders of a province and its inside steiner points. Looks a bit like this:
outside triangulation
outside triangulation wireframe
And then the inside:
inside triangulation
inside triangulation wireframe
But the bad thing about this approach is that it doesn’t always work, like in this case:
bad case
bad case wireframe
In the picture the blue points are the outline points, beyond which there should be no triangulations. As you can see some triangles are not generating. I’ve narrowed it down to 2 issues:
-
the outline points are incorrect sometimes. I’ve tried 2 different libraries for the concave hull of a set of points: turf.js’s
concave
and mapbox’sconcaveman
. This is probably due to the projection distorting the inside steiner points. Still both produce faulty results even if I directly plug in the GeoJSON spherical coordinates without and projections. -
The triangulation produces edges, which, are technically inside the constraints, but are incorrect (The inside points are supposed to be spaced out at equal distances, because that is how the geometry of the icosahedron works – it is made up of many triangles with equal sides, thus the equal distance between points). I am removing all the triangles whose sides are not equal within an epsilon of 0.1 (this means that lengths such as 1 and 1.000001 should be equal). This does in fact remove the stray longer triangles, but as you can see, it sometimes removes correct triangles as well. Somehow, the distance between the points is not equal, maybe my vector math is wrong, at this point I am so lost I have no idea. This is the code:
const innerPolygonContourPointsIndexes:number[] = [];
// const innerRingPolygon = concave(featureCollection(insidePointsSphericalCoords.map(x=>point(x))));
const innerRing = concaveman(trigPoints.map(x=>[x.x,x.y]));
const finalTriangulation:poly2tri.Triangle[] = [];
innerRing.splice(innerRing.length-1,1);
for(let coord of innerRing) {
let index = trigPoints.findIndex(x=>x.x==coord[0]&&x.y==coord[1]);
if(index!=-1) {
innerPolygonContourPointsIndexes.push(index);
}
}
const steinerPointIndexes:number[] = [];
for(let i=0;i<insidePointsSphericalCoords.length;i++) {
if(!innerPolygonContourPointsIndexes.includes(i)) steinerPointIndexes.push(i);
}
for(let index of innerPolygonContourPointsIndexes) {
debugPoints.push(new Vector3().setFromSphericalCoords(radius,MathUtils.degToRad(insidePointsSphericalCoords[index][1]),MathUtils.degToRad(insidePointsSphericalCoords[index][0])));
}
const ringPoints:IdentifiablePoint[] = innerPolygonContourPointsIndexes.map((x,i)=>trigPoints[x]);
const steinerPoints:IdentifiablePoint[] = steinerPointIndexes.map((x,i) => trigPoints[x]);
const epsilon = 0.1;
let rawTriangulation:poly2tri.Triangle[];
// Inside polygon
rawTriangulation = new poly2tri.SweepContext(ringPoints,{cloneArrays:true}).addPoints(steinerPoints).triangulate().getTriangles();
for(let triangle of rawTriangulation) {
console.log("trigid",(triangle.getPoint(0) as IdentifiablePoint).id-trigPoints[0].id);
triangleVectorA.copy(insidePointsVectors[(triangle.getPoint(0) as IdentifiablePoint).id-trigPoints[0].id]);
triangleVectorB.copy(insidePointsVectors[(triangle.getPoint(1) as IdentifiablePoint).id-trigPoints[0].id]);
triangleVectorC.copy(insidePointsVectors[(triangle.getPoint(2) as IdentifiablePoint).id-trigPoints[0].id]);
const AB = vertex.subVectors(triangleVectorA,triangleVectorB).length();
const BC = vertex.subVectors(triangleVectorB,triangleVectorC).length();
const CA = vertex.subVectors(triangleVectorC,triangleVectorA).length();
console.log("lenghts", AB,BC,CA,triangle.isInterior());
if(equalsNumberEpsilon(AB,BC,epsilon)&&equalsNumberEpsilon(BC,CA,epsilon)&&equalsNumberEpsilon(CA,AB,epsilon)) {
finalTriangulation.push(triangle);
}
}
// THIS COMMENTED CODE IS FOR TRIANGULATING THE SHAPE BETWEEN THE PROVINCE BORDERS AND THE INSIDE POINTS
// rawTriangulation = new poly2tri.SweepContext(contour,{cloneArrays:true}).addHole(ringPoints).triangulate().getTriangles();
// finalTriangulation.push(...rawTriangulation.filter(x=>x.isInterior()));
For the sake of clarity and continuity this is the code of the entire function that generates a mesh’s province. Beware it isn’t clean, nor formatted and very very experimental and ugly (rows of semicolons are used for reloading the changes in the renderer on save):
function generateProvinceGeometry(province:ProvinceDTO,planetGeometry:BufferGeometry,radius:number):[Vector3[],BufferGeometry] {
const vertex = new Vector3();
const spherical = new Spherical();
const positionAttribute = planetGeometry.getAttribute( 'position' );;
const contourSphericalCoords:GeoJSON.Position[] = [];
const trigPoints:IdentifiablePoint[] = [];
const insidePointsVectors:Vector3[] = [];
const geometry = new BufferGeometry();
const debugPoints:Vector3[]=[];
const offsetPositions:GeoJSON.Position[] = [];
const trigPointsV:IdentifiablePoint[] = [];
const contourV:IdentifiablePoint[] = [];
let bufferGeometryArrayIndex=0;
let insidePointIndex;
// 0 is the highest latitude, 180 is the lowest latitude
let provinceHighestLat=180, provinceLowestLat=0;
for(let border of province.borders) {
for(let i=0;i<border.borderPoints.length-1;i++) {
const point=border.borderPoints[i];
spherical.setFromVector3(point);
contourSphericalCoords.push([MathUtils.radToDeg(spherical.theta),MathUtils.radToDeg(spherical.phi)]);
if(contourSphericalCoords[contourSphericalCoords.length-1][1]>provinceLowestLat)
provinceLowestLat=contourSphericalCoords[contourSphericalCoords.length-1][1];
if(contourSphericalCoords[contourSphericalCoords.length-1][1]<provinceHighestLat)
provinceHighestLat=contourSphericalCoords[contourSphericalCoords.length-1][1];;;
offsetPositions.push([rotateCoords(MathUtils.radToDeg(spherical.theta)-contourSphericalCoords[0][0]),MathUtils.radToDeg(spherical.phi)-90]);
}
}
contourSphericalCoords.push(contourSphericalCoords[0]);
offsetPositions.push(offsetPositions[0]);
const deltaDegree = contourSphericalCoords[0][0];;;
const geoOffsetObj:GeoJSON.Polygon = {
type: "Polygon",
coordinates: Array.from([offsetPositions])
};
const geoObj:GeoJSON.Polygon = {
type: "Polygon",
coordinates: Array.from([contourSphericalCoords])
};
// rewind polygon if needed (clockwise rules for d3)
if(geoArea(geoObj)>Math.PI) {
rewind(geoObj,{mutate:true,reverse:true});;;;;
rewind(geoOffsetObj,{mutate:true,reverse:true});;;;;
}
// lng,lat
const c = center(geoObj).geometry.coordinates as [number,number];
// fit range [-90;90]
c[1]-=90;
console.log("found center: ",c);;;;
let projectionFunction = geoEquirectangular().center(c);;;;;
// offsetPositions.forEach(x=>pts.push(new Vector3().setFromSphericalCoords(radius,MathUtils.degToRad(x[1]),MathUtils.degToRad(x[0])-centerLatDelta+90)));
let contour:IdentifiablePoint[] = contourSphericalCoords.map((coords,i) => {
const proj = projectNormalised([coords[0],coords[1]],deltaDegree,projectionFunction);
debugPoints.push(new Vector3(proj[0],0,proj[1]))
contourV.push({x:proj[0],y:proj[1],id:i});
return {x:proj[0],y:proj[1],id:i};
});
contourV.splice(contourV.length-1,1);;
contour.splice(contour.length-1,1);
insidePointIndex = contour[contour.length-1].id+2;;
const insidePointsSphericalCoords:GeoJSON.Position[] = [];
// Locate sphere mesh points inside province
let startVertexIndex = 0;
let endVertexIndex = positionAttribute.count;
for ( let vertexIndex = startVertexIndex; vertexIndex < endVertexIndex; vertexIndex ++ ) {
vertex.fromBufferAttribute( positionAttribute, vertexIndex );
spherical.setFromVector3(vertex);
// lat long
const cartesianCoords:[number,number] = [MathUtils.radToDeg(spherical.theta),MathUtils.radToDeg(spherical.phi)];;;;;;;;
if(cartesianCoords[1]>provinceLowestLat||cartesianCoords[1]<provinceHighestLat) continue;
const normalizedCoords:[number,number] = [rotateCoords(cartesianCoords[0]-deltaDegree),cartesianCoords[1]-90];;;
if(booleanContains(geoOffsetObj,point(normalizedCoords))) {
// debugPoints.push(new Vector3().copy(vertex));
const coords = projectRegular(normalizedCoords,projectionFunction);;;
if(trigPoints.find(x=>x.x==coords[0]&&x.y==coords[1])!=undefined)
continue;
trigPoints.push({x:coords[0],y:coords[1],id:insidePointIndex});
insidePointsSphericalCoords.push(cartesianCoords);;;;;;;;
debugPoints.push(new Vector3(coords[0],0,coords[1]))
trigPointsV.push({x:coords[0],y:coords[1],id:insidePointIndex-1});
insidePointIndex++;
insidePointsVectors.push(new Vector3().copy(vertex));
}
}
const finalSphericalCoords:GeoJSON.Position[] = [...contourSphericalCoords,...insidePointsSphericalCoords];
const finalV:IdentifiablePoint[] = [...contourV,...trigPointsV];
let bufferGeometryArray:Float32Array=new Float32Array(0);
const triangleVectorA = new Vector3();
const triangleVectorB = new Vector3();
const triangleVectorC = new Vector3();
try {
const innerPolygonContourPointsIndexes:number[] = [];
// const innerRingPolygon = concave(featureCollection(insidePointsSphericalCoords.map(x=>point(x))));;;
const innerRing = concaveman(trigPoints.map(x=>[x.x,x.y]));;
const finalTriangulation:poly2tri.Triangle[] = [];
// if(innerRingPolygon!=null) {
innerRing.splice(innerRing.length-1,1);
for(let coord of innerRing) {
let index = trigPoints.findIndex(x=>x.x==coord[0]&&x.y==coord[1]);;
if(index!=-1) {
innerPolygonContourPointsIndexes.push(index);;;;
}
}
const steinerPointIndexes:number[] = [];
for(let i=0;i<insidePointsSphericalCoords.length;i++) {
if(!innerPolygonContourPointsIndexes.includes(i)) steinerPointIndexes.push(i);;;;;;;
}
for(let index of innerPolygonContourPointsIndexes) {
debugPoints.push(new Vector3().setFromSphericalCoords(radius,MathUtils.degToRad(insidePointsSphericalCoords[index][1]),MathUtils.degToRad(insidePointsSphericalCoords[index][0])));;;;;;;;
}
// for(let index of innerPolygonContourPointsIndexes) {
// pts.push(new Vector3().setFromSphericalCoords(radius,MathUtils.degToRad(insidePointsSphericalCoords[index][1]),MathUtils.degToRad(insidePointsSphericalCoords[index][0])));;;;;;;;;
// }
const ringPoints:IdentifiablePoint[] = innerPolygonContourPointsIndexes.map((x,i)=>trigPoints[x]);
const steinerPoints:IdentifiablePoint[] = steinerPointIndexes.map((x,i) => trigPoints[x]);
const epsilon = 0.1;
let rawTriangulation:poly2tri.Triangle[];
// Inside polygon
rawTriangulation = new poly2tri.SweepContext(ringPoints,{cloneArrays:true}).addPoints(steinerPoints).triangulate().getTriangles();
// console.log(trigPoints);
// console.log(insidePointsSphericalCoords.length);
// console.log(contourSphericalCoords.length);
// console.log(finalSphericalCoords.length);
for(let triangle of rawTriangulation) {
console.log("trigid",(triangle.getPoint(0) as IdentifiablePoint).id-trigPoints[0].id);
triangleVectorA.copy(insidePointsVectors[(triangle.getPoint(0) as IdentifiablePoint).id-trigPoints[0].id]);
triangleVectorB.copy(insidePointsVectors[(triangle.getPoint(1) as IdentifiablePoint).id-trigPoints[0].id]);
triangleVectorC.copy(insidePointsVectors[(triangle.getPoint(2) as IdentifiablePoint).id-trigPoints[0].id]);
const AB = vertex.subVectors(triangleVectorA,triangleVectorB).length();
const BC = vertex.subVectors(triangleVectorB,triangleVectorC).length();
const CA = vertex.subVectors(triangleVectorC,triangleVectorA).length();
console.log("lenths", AB,BC,CA,triangle.isInterior());
if(equalsNumberEpsilon(AB,BC,epsilon)&&equalsNumberEpsilon(BC,CA,epsilon)&&equalsNumberEpsilon(CA,AB,epsilon)) {
finalTriangulation.push(triangle);
}
}
// THIS COMMENTED CODE IS FOR TRIANGULATING THE SHAPE BETWEEN THE PROVINCE BORDERS AND THE INSIDE POINTS
// rawTriangulation = new poly2tri.SweepContext(contour,{cloneArrays:true}).addHole(ringPoints).triangulate().getTriangles();
// finalTriangulation.push(...rawTriangulation.filter(x=>x.isInterior()));;
// } else {
// const rawTriangulation = new poly2tri.SweepContext(contour,{cloneArrays:true}).addPoints(trigPoints).triangulate().getTriangles();;
// finalTriangulation.push(...rawTriangulation.filter(x=>x.isInterior()));
// }
// const rawTriangulation = new poly2tri.SweepContext(contour).addPoints(trigPoints).triangulate().getTriangles();;;
// finalTriangulation.push(...rawTriangulation.filter(x=>x.isInterior()));;
const trig2 = new poly2tri.SweepContext(contourV).addPoints(trigPointsV).triangulate().getTriangles();;;;;
bufferGeometryArray = new Float32Array(finalTriangulation.length*9+trig2.length*9);;;;;
for(let trig of finalTriangulation) {
let coordsArr = sphericalToCartesianArr(radius,finalSphericalCoords[(trig.getPoint(0) as IdentifiablePoint).id] as [number,number]);;
bufferGeometryArray[bufferGeometryArrayIndex] = coordsArr[0];
bufferGeometryArray[bufferGeometryArrayIndex+1] = coordsArr[1];
bufferGeometryArray[bufferGeometryArrayIndex+2] = coordsArr[2];
coordsArr = sphericalToCartesianArr(radius,finalSphericalCoords[(trig.getPoint(2) as IdentifiablePoint).id] as [number,number]);
bufferGeometryArray[bufferGeometryArrayIndex+3] = coordsArr[0];
bufferGeometryArray[bufferGeometryArrayIndex+4] = coordsArr[1];
bufferGeometryArray[bufferGeometryArrayIndex+5] = coordsArr[2];
coordsArr = sphericalToCartesianArr(radius,finalSphericalCoords[(trig.getPoint(1) as IdentifiablePoint).id] as [number,number]);
bufferGeometryArray[bufferGeometryArrayIndex+6] = coordsArr[0];
bufferGeometryArray[bufferGeometryArrayIndex+7] = coordsArr[1];
bufferGeometryArray[bufferGeometryArrayIndex+8] = coordsArr[2];
bufferGeometryArrayIndex+=9;;
}
for(let trig of trig2) {
let element = finalV[(trig.getPoint(0) as IdentifiablePoint).id];;;;;;;
// console.log((trig.getPoint(0) as IdentifiablePoint).id,element);
bufferGeometryArray[bufferGeometryArrayIndex ] = element.x;
bufferGeometryArray[bufferGeometryArrayIndex+1] = 0;
bufferGeometryArray[bufferGeometryArrayIndex+2] = element.y;
// coordsArr = sphericalToCartesianArr(radius,finalSphericalCoords[(trig.getPoint(2) as IdentifiablePoint).id] as [number,number]);
element = finalV[(trig.getPoint(2) as IdentifiablePoint).id];
bufferGeometryArray[bufferGeometryArrayIndex+3] = element.x;
bufferGeometryArray[bufferGeometryArrayIndex+4] = 0;
bufferGeometryArray[bufferGeometryArrayIndex+5] = element.y;
// coordsArr = sphericalToCartesianArr(radius,finalSphericalCoords[(trig.getPoint(1) as IdentifiablePoint).id] as [number,number]);
element = finalV[(trig.getPoint(1) as IdentifiablePoint).id];
bufferGeometryArray[bufferGeometryArrayIndex+6] = element.x;
bufferGeometryArray[bufferGeometryArrayIndex+7] = 0;
bufferGeometryArray[bufferGeometryArrayIndex+8] = element.y;
bufferGeometryArrayIndex+=9;;
}
} catch(e:any) {
console.log("Problem:",e);
// flag=true;;
if(!e.message.includes("int")) return [debugPoints,geometry];;;;
const arr = e.message.split(' ').splice(3,4).forEach((x:string)=>{
const arr2 = x.split(';');
let n1 = parseFloat(arr2[0].slice(1));
let n2 = parseFloat(arr2[1].slice(0,-1));
console.log(n1,n2,"n");
debugPoints.push(new Vector3(n1,0,n2));
})
console.log(arr);
}
geometry.setAttribute( 'position', new BufferAttribute( bufferGeometryArray, 3 ) );;
return [debugPoints,geometry];
// return geometry;
}
So, this is everything. After all of this exposition here is my question: Is this a poly2tri issue, a turf issue, a projection issue, a math issue or a me issue. If you have any idea how to fix any of this, or a recommendation of a new way to look at things, or a new library, any pointers to resources or just anything, please let me know because I am losing my mind.