How About Grid 2 Sphere?

I should work on the peeps animation, or serpentine landmass, and procedural subdivision of a tetra or octahedron would be pretty kewl… but, I want to find the points of a 3D grid which are inside of a sphere and then find those points which are adjacent to points outside of the sphere. These are subsurface points and I can use them to draw the surface with marching cubes, but I want to find this procedurally rather than looking something up. If one or more vertices of a cube lie inside the sphere and other points lie outside then the surface passes through some of the twelve edges of my cube. For each inside corner we interpolate where the surface point lies along the three edges connecting that corner to one of the three adjacent corners. If the surface doesn’t pass through a point along that edge, we need to keep looking. Make or find the twelve edges, look for edges containing a surface point then start connecting surface points in each quad face which have edges contain surface points.

Too complicated! Let’s just consider the subsurface grid points and worry about the interpolated surface later. I want to link a subsurface point to the nearest subsurface point and then connect the endpoints of resulting edge to the subsurface point which is closest the midpoint of the edge. Now that I have a triangle, I build a surface/subsurface by connecting to neighboring subsurface points in a mesh of triangles. I build new triangles off of the edges of existing triangles, then remove the doubly used edges as the edge of a triangle in a surface mesh only belongs to at most two triangles; if an edge belongs to only one triangle that edge is an open edge and is the border of a surface.

We start with something modeled on the Earth, about 6378 km in radius, as a 3D grid thirteen thousand km across… which is waaaay too much to ask of my poor chromebook! Thirteen hundred cells about 10 km across is slightly more reasonable, but still amounts to a couple of billion cubes, so that’ll take nearly forever as well. A hundred thirty gets it down to about two million cells, about half inside and half outside with a subsurface of a few thousand.

The simplest option is to go with thirteen cubed, some twenty-two hundred cells each about a thousand km on a side with hundreds of subsurface points, edges and triangles approximating the surface/subsurface of the world. Once we find the subsurface and create the mesh of triangles we can adjust the position of each subsurface point to be at the surface and make the triangles represent the area. So, make a 3D grid from 0 to 13, times 20 pixels, across wide, high and deep, from 0 to 260, which will fill up the left side of my 520 by 260 canvas. The proper coordinates would be minus 65 pixels XYZ to plus 65 pixels XYZ, so we can add perspective with the depth or Z coordinate. Each point would be P5D: x, y, z and px, py, for perspective or perceived x and y. Each edge would be EJ5: e1, e2, md, t1 and t2 for the first endpoint (actually lowest index endpoint), second endpoint, midpoint, first and second triangle. Each triangle would be TR7: e1, e2, e3, p1, p2, p3 and cn for three edges, three corners and a triangle center.

Now would be a good time to get on with it...