Drawing countries on top of a 3D sphere from set of boundaries

Programming Questions

radiodario

Drawing countries on top of a 3D sphere from set of boundaries

in Programming Questions • 2 years ago

Hello all,

I'm trying to draw countries on top of a 3D sphere. I've created the following classes (in bold): For each Country, I have a list of Landmasses. Each Landmass has a set of Coordinates (lat long) which define the landmasses border. So in 2D this is all fine, i map the coordinates to x,y points on my sketch based on some projection and i've got the result i want. However, the same approach doesn't work as well in 3D.

I have successfully converted the lat,long coordinates onto x, y, z using the following formulae

x = radius * (float) Math.sin(latRad) * (float) Math.cos(lngRad);
y = radius * (float) Math.sin(latRad) * (float) Math.sin(lngRad);
z = radius * (float) Math.cos(latRad);

my draw() function for a landmass looks like:

public void draw(PApplet p) {
p.strokeWeight(1);
p.stroke(107,177,209,255);
p.beginShape();
for (int i = 0; i < this.borders.length; i++) {
Coordinate c = this.borders[i];
p.vertex(c.x, c.y, c.z);
}
p.endShape(p.CLOSE);
}

However, this method, while really intuitive, doesn't produce convex shapes. If i place these shapes on top of a sphere, small landmasses are drawn just fine. However, the surfaces of larger countries such as Russia or Canada are drawn with ridges and they cross the sphere they're drawn upon:

What i'd like to have is a method that given a set of boundary points, it would compute a mesh that follows the convex shape of a sphere. I've had a look at toxi's amazing toxic libs, but i haven't been able to use them successfully. Is this a 3D convex hull problem?

Cheers

Replies(10)

toxmeister

Re: Drawing countries on top of a 3D sphere from set of boundaries

2 years ago

IMHO not a convex hull problem, but a geometry & depth sorting issue. Your landmass borders form polygons, but when they're rendered in 3D they will be first tesselated into smaller triangles. That means points on opposite sides of the perimeter polygon will now be forced on a (number of) planes, one for each triangle, all of which will intersect the sphere mesh. The longer the distance between those opposite points, the more the plane will intersect the sphere and you get those holes because the sphere surface is actually closer to the camera. Apart from reducing the radius to say 95-98% for rendering the sphere, to solve this problem purely geometrically (without using texture mapping the regions), you should add additional points within the regions and then tesselate each region individually using a Delaunay triangulation in 2D and finally map each vertex of the resulting 2D triangles onto the sphere. You can use toxiclibs for all these tasks, see these threads below:

http://forum.processing.org/topic/toxiclib-voronoi-example-sketch#25080000000792036

http://forum.processing.org/topic/gps-to-spherical-coordinates-with-vec3d-toxilibs#25080000000756005

In general, the point of using the Delaunay is to get additional triangles within the centre of each country polygon and thereby reducing the average size of the triangles and hence reduce the intersection with the sphere. But you'll first have to add points within each polygon. You can do that (for example) by first computing the bounds of each poly and then add random points which lie within the bounding rect as well as the polygon itself. This should work with all convex/concave polygons (without any holes in them):

Here's a modified version of that Delaunay sketch from the other thread mentioned above, showing how to tesselate a polygon with additional inlier points:

import toxi.geom.*;
import toxi.geom.mesh2d.*;
import toxi.processing.*;
// radius of the root delaunay triangle which encompasses (MUST) all other points
float DELAUNAY_SIZE = 10000;
ToxiclibsSupport gfx;
Polygon2D poly;
List<Triangle2D> tesselated;
void setup() {
size(600, 600);
smooth();
gfx = new ToxiclibsSupport(this);
// create a regular polygon by sampling a circle
poly=new Circle(200).toPolygon2D(16);
// optionally make concave:
// poly.vertices.get(0).scaleSelf(0.1);
// center in window
poly.center(new Vec2D(width/2,height/2));
// now tesselate it with 10 additional points inside (also try with 0 extras to compare!)
tesselated=tesselatePolygon(poly, 10);
}
void draw() {
background(255);
noFill();
// draw original poly
stroke(255,0,0);
gfx.polygon2D(poly);
// then tesselated version to compare
stroke(0, 0, 255);
beginShape(TRIANGLES);
for (Triangle2D t : tesselated) {
gfx.triangle(t);
}
endShape();
}
// tesselates polygon with additional/optional inliers
List<Triangle2D> tesselatePolygon(Polygon2D poly, int num) {
List<Triangle2D> result=new ArrayList<Triangle2D>();
// a Voronoi diagram relies on a Delaunay triangulation behind the scenes
Voronoi voronoi = new Voronoi(DELAUNAY_SIZE);
// add perimeter points
for (Vec2D v : poly.vertices) {
voronoi.addPoint(v);
}
// add random inliers
for (Vec2D v : createRandomInsidePoints(poly,num)) {
voronoi.addPoint(v);
}
// get filtered delaunay triangles:
// ignore any triangles which share a vertex with the initial root triangle
// or whose centroid is outside the polygon
for (Triangle2D t : voronoi.getTriangles()) {
if (abs(t.a.x)!=DELAUNAY_SIZE && abs(t.a.y)!=DELAUNAY_SIZE) {
if (poly.containsPoint(t.computeCentroid())) {
result.add(t);
}
}
}
return result;
}
// compute bounding rect of a polygon
// (will be unnecessary from toxiclibs-0021 onwards)
Rect computeBounds(Polygon2D poly) {
Vec2D min=Vec2D.MAX_VALUE.copy();
Vec2D max=Vec2D.MIN_VALUE.copy();
for (Vec2D v : poly.vertices) {
min.minSelf(v);
max.maxSelf(v);
}
return new Rect(min, max);
}
// create list of random points within polygon
List<Vec2D> createRandomInsidePoints(Polygon2D poly, int num) {
List<Vec2D> points=new ArrayList<Vec2D>(num);
Rect bounds=computeBounds(poly);
for (int i=0; i<num; i++) {
Vec2D p=null;
while (p==null || !poly.containsPoint (p)) {
p=new Vec2D(random(bounds.getLeft(), bounds.getRight()), random(bounds.getTop(), bounds.getBottom()));
}
points.add(p);
}
return points;
}

The only thing missing is to translate this final list of 2D triangles into a 3D mesh whose vertices have been mapped onto a sphere. In pseudo code this could be similar to:

TriangleMesh countryMesh=new TriangleMesh();
// assumes 2D coordinates are in x=lon, y=lat
for(Triangle2D t : tesselated) {
// 2D lat/lon => spherical => cartesian conversion
Vec3D a=new Vec3D(earthRadius, radians(t.a.x), radians(t.a.y)).toCartesian();
Vec3D b=new Vec3D(earthRadius, radians(t.b.x), radians(t.b.y)).toCartesian();
Vec3D c=new Vec3D(earthRadius, radians(t.c.x), radians(t.c.y)).toCartesian();
countryMesh.addFace(a,b,c);
}

http://postspectacular.com | http://toxiclibs.org

radiodario

Re: Re: Drawing countries on top of a 3D sphere from set of boundaries

2 years ago

Hey toxi, thanks for answering! those two examples cover pretty much what i'm looking for so i'll be implementing the changes and i'll post a pic of the results.

cheers

toxmeister

Re: Drawing countries on top of a 3D sphere from set of boundaries

2 years ago

Cool, since this a problem I myself am very interested in, I've tested & implemented my assumptions from above (see result images below). This code adds new points on a grid within the polygon and also does the 3D mesh construction:

/**
* This example demonstrates how to map a 2D polygon onto a the surface of a sphere
* using purely geometry (no texture mapping). The process involves tesselating the polygon
* using Delaunay triangulation, for which additional points within the polygon are added.
* The resulting 2D triangles are then transferred onto the sphere and connected into a
* 3D mesh. The demo also has some key controls to adjust rendering modes and resolution to
* observe the effect of the additional inside points.
*
* Usage:
*
* 0-9: adjust sample grid resolution
* r: randomize position of polygon on sphere
* m: toggle between mesh display (3D) and flat 2D rendering
*/
/*
* Copyright (c) 2011 Karsten Schmidt
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* http://creativecommons.org/licenses/LGPL/2.1/
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this library; if not, write to the Free Software
* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
*/
import toxi.geom.*;
import toxi.geom.mesh2d.*;
import toxi.geom.mesh.*;
import toxi.processing.*;
import processing.opengl.*;
// radius of the root delaunay triangle which encompasses (MUST) all other points
float DELAUNAY_SIZE = 10000;
// sphere radius
float EARTH_RADIUS=300;
ToxiclibsSupport gfx;
// Perimeter polygon
Polygon2D poly;
// list of 2D triangles (intermediate result of Delaunay triangulation)
List<Triangle2D> tesselated;
// 3D mesh
TriangleMesh mesh;
// grid resolution for adding inliers
int res=1;
void setup() {
size(1024, 768, OPENGL);
smooth();
gfx = new ToxiclibsSupport(this);
// create a regular polygon by sampling a circle
poly=new Circle(30).toPolygon2D(20);
tesselated=tesselatePolygon(poly, res);
}
void draw() {
background(255);
// switch between 2D/3D modes
if (mesh==null) {
translate(width/2, height/2);
noFill();
// draw original poly
stroke(255, 0, 0);
gfx.polygon2D(poly);
// then tesselated version to compare
stroke(0, 0, 255);
beginShape(TRIANGLES);
for (Triangle2D t : tesselated) {
gfx.triangle(t);
}
endShape();
}
else {
lights();
translate(width/2, height/2, 0);
rotateX(mouseY*0.01);
rotateY(mouseX*0.01);
fill(255);
noStroke();
sphere(EARTH_RADIUS*0.99);
fill(255,0,64);
stroke(0);
gfx.mesh(mesh, true, 20);
}
}
void keyPressed() {
if (key>='0' && key<='9') {
res=(key-'0')*2;
// resample polygon with new resolution
tesselated=tesselatePolygon(poly, res);
if (mesh!=null) {
mesh=buildSurfaceMesh(tesselated, EARTH_RADIUS);
}
}
if (key=='r') {
// randomize position of polygon (coords are in lon/lat space)
poly=new Circle(new Vec2D(random(-180, 180), random(-30, 30)), 30).toPolygon2D(30);
tesselated=tesselatePolygon(poly, res);
// update mesh, if needed...
if (mesh!=null) {
mesh=buildSurfaceMesh(tesselated, EARTH_RADIUS);
}
}
if (key=='m') {
// toggle between 2d/3d
if (mesh==null) {
mesh=buildSurfaceMesh(tesselated, EARTH_RADIUS);
}
else {
mesh=null;
}
}
}
// tesselates polygon with additional/optional inliers
List<Triangle2D> tesselatePolygon(Polygon2D poly, int num) {
List<Triangle2D> result=new ArrayList<Triangle2D>();
// a Voronoi diagram relies on a Delaunay triangulation behind the scenes
Voronoi voronoi = new Voronoi(DELAUNAY_SIZE);
// add perimeter points
for (Vec2D v : poly.vertices) {
voronoi.addPoint(v);
}
// add random inliers
for (Vec2D v : createInsidePoints(poly,num)) {
voronoi.addPoint(v);
}
// get filtered delaunay triangles:
// ignore any triangles which share a vertex with the initial root triangle
// or whose centroid is outside the polygon
for (Triangle2D t : voronoi.getTriangles()) {
if (abs(t.a.x)!=DELAUNAY_SIZE && abs(t.a.y)!=DELAUNAY_SIZE) {
if (poly.containsPoint(t.computeCentroid())) {
result.add(t);
}
}
}
return result;
}
// compute bounding rect of a polygon
// (will be unnecessary from toxiclibs-0021 onwards)
Rect computeBounds(Polygon2D poly) {
Vec2D min=Vec2D.MAX_VALUE.copy();
Vec2D max=Vec2D.MIN_VALUE.copy();
for (Vec2D v : poly.vertices) {
min.minSelf(v);
max.maxSelf(v);
}
return new Rect(min, max);
}
// create list of grid points within polygon
List<Vec2D> createInsidePoints(Polygon2D poly, int num) {
List<Vec2D> points=new ArrayList<Vec2D>(num);
Rect bounds=computeBounds(poly);
for (int y=0; y<num; y++) {
float yy=map(y, 0, num, bounds.getTop(), bounds.getBottom());
for (int x=0; x<num; x++) {
Vec2D p=new Vec2D(map(x, 0, num, bounds.getLeft(), bounds.getRight()), yy);
if (poly.containsPoint(p)) {
points.add(p);
}
}
}
return points;
}
// converts a list of 2D triangles into a 3D mesh on a sphere
TriangleMesh buildSurfaceMesh(List<Triangle2D> tris, float radius) {
TriangleMesh mesh=new TriangleMesh();
for (Triangle2D t : tris) {
// ensure all triangles have same orientation
if (!t.isClockwise()) {
t.flipVertexOrder();
}
// lat/lon => spherical => cartesian mapping
Vec3D a = new Vec3D(radius, radians(t.a.x), radians(t.a.y)).toCartesian();
Vec3D b = new Vec3D(radius, radians(t.b.x), radians(t.b.y)).toCartesian();
Vec3D c = new Vec3D(radius, radians(t.c.x), radians(t.c.y)).toCartesian();
// add 3D triangle to mesh
mesh.addFace(a, b, c);
}
// needed for smooth shading
mesh.computeVertexNormals();
return mesh;
}

Some result images: This first one is what you've been getting so far (in a very drastic way). No extra points within the poly were added...

Sampled with a 6x6 subgrid:

Sampled with a 18x18 subgrid:

http://postspectacular.com | http://toxiclibs.org

radiodario

Re: Re: Drawing countries on top of a 3D sphere from set of boundaries

2 years ago

Cheers man!

radiodario

Re: Re: Drawing countries on top of a 3D sphere from set of boundaries

2 years ago

So I used your code and this is the result:

No more patchy russia ;)

hats off toxi.

radiodario

Re: Re: Drawing countries on top of a 3D sphere from set of boundaries

2 years ago

Here's another shot that reveals the tesselation. One thing I notice is that the smaller the area of the country, the more dense the triangulation. I now have to choose the rez based on the area of the country. But i'm already well chuffed with how good it looks.

davbol

Re: Drawing countries on top of a 3D sphere from set of boundaries

2 years ago

another method that might require less sub-sampling is to do all your clipping work in planar projected space, then project everything back onto the sphere, that way you can use exactly the sphere's vertices as subsamples within your polys, essentially just "extruding" the sphere's own triangles...

"unroll" the sphere coordinates into a plane as a cylindrical projection (aka equirectangular, equidistant cylindrical, etc). draw your countries. select all sphere triangles that intersect your country polygon and clip them to the poly boundary. that set of triangles (and irregular clipped triangle shapes, which you can let the renderer triangulate when drawn) is now your "country" and will "bulge" at exactly the same places the sphere does (tho within any single sphere triangle they'll remain planar, just as the triangle itself does).

(most of that project/unproject work you won't have to actually DO, you just have to think it conceptually)

when drawing the country tris in 3d versus the sphere, you may just want to add a tiny bit of extra radius for elevation - fe, simply treat them as vectors and scale magnitude by 1.001 or as needed to clear up zbuffer issues

hth

toxmeister

Re: Drawing countries on top of a 3D sphere from set of boundaries

2 years ago

Hey, sorry for delay...

That's looking fabulous, mister! Meanwhile I've extended this process and wrapped it into 2 different implementations for the next release. One as is,the other is based on a global grid size and not the size of the polygon. The latter would be more beneficial for your purposes and you can see the source for both here:

http://hg.postspectacular.com/toxiclibs/changeset/7ad7880cb291

Usage example here:

http://hg.postspectacular.com/toxiclibs/src/tip/examples/core/geometry/PolyGridTesselate/PolyGridTesselate.pde

You should be able to just copy & paste these classes into your sketch for now (until 0021 is out)

Keep us posted please! Best, K.

http://postspectacular.com | http://toxiclibs.org

czwaal

Re: Drawing countries on top of a 3D sphere from set of boundaries

2 years ago

This is completely off-topic; but how did you get those coordinates?

radiodario

Re: Re: Drawing countries on top of a 3D sphere from set of boundaries

2 years ago

well you can find these pretty much everywhere, but you can use the countries.js file freely available at the protovis site, which they use on all their map examples

http://vis.stanford.edu/protovis/ex/countries.js

you probably will have to format it to your liking (to csv?) or use some sort of json reading library to read the coordinates. you can see that for each country there is a list of shapes (i.e. landmasses) so you might want to organise your classes that way

peace.

Top Reply