WIP
Sphere is one of the most elemental 3D geometrical shapes that's defined as a set of all points that share the same distance r from given center point c. Every sphere is therefore uniquely defined by the point c and the distance r, which we call radius (that's half of diameter). Sphere is the equivalent of a circle, just in three dimensions, and the concept can be further generalized to higher dimensions (with the definition remaining the same) -- these "higher dimensional spheres" are named hyperspheres. Cutting a sphere with a plane going through the sphere's center point creates two equally sized hemispheres. It goes without saying that sphere is an object of immense importance: it's simple but hides profound concepts. In mathematics, physics and programming we know spheres for their special, many times optimal and/or very convenient properties such as having minimal surface to volume ratio, which then manifests in nature for example by animals curling to approximately spherical shapes when they want to stay warm. Spheres are beautiful and culturally they're a symbol of perfection; stars, planets, water droplets and bubbles take on the shape of a sphere, bounding spheres are used to accelerate computer programs such as physics engines, signals broadcast in empty space travel as an expanding sphere, sports make use of sphere-shaped balls, and we could probably spend the rest of eternity recounting more and more examples demonstrating this shape's significance.
Some data/facts/formulas/etc. related to spheres are the following:
A = 4 * pi * r^2.V = 4/3 * pi * r^3.sqrt(2 * h * r + h^2) and (using the formula for small
circle area below we can compute that) he sees total area of
(2 * pi * h) / (h + r). If we take the height above surface
to be expressed as a fraction x of the sphere's radius,
then the portion of total visible surface is
(1 - 1 / (1 + x)) / 2. Plotting this we see this converges
to 1/2, meaning you can only ever see less than half of any
sphere's surface at once (not counting tricks with mirrors and
cameras of course).l = 2 * pi * r.A2 = pi * (r2)^2. Now if r3 is the distance
measured ON the big sphere's surface (i.e. going to be a little longer
than r2), then it's:
A2 = 2 * pi * r^2 * (1 - cos(r3/r)). { Thanks math exchange
:D ~drummyfish } If we known height h of the spherical cap,
then the area is A2 = 2 * pi * r * h and the volume inside
the cap is V2 = pi * h^2 / 3 * (3 * r - h). From this it
also follows that equally spaced parallel slices of a sphere
create "spherical bands" of the same area (because
(2 * pi * r * 2 * h) - (2 * pi * r * h) = (2 * pi * r * h)).cos(c/r) = cos(a/r) * cos(b/r).1/r^2.p - c, normalize it and flip
it. Any two spheres that touch by one point ALWAYS have their normals at
the point of contact exactly aligned, just with opposite direction --
this is also very convenient e.g. in physics engines.Locating individual points on a sphere's surface is complicated by the fact that the surface is curved (duh). Smaller parts of the surface are locally pretty close to a flat plain (see also Flat Earth), so in some cases the curvature can be safely neglected and we may happily continue using normal Cartesian coordinates. Nonetheless in many other situations we can't afford such luxury and will have to resort to something more complex and precise. Global navigation probably comes to mind as the first real world example but as programmers we may also imagine things like texturing or cellular automata. The question of choosing appropriate coordinates for a spherical surface is also related to map projections and tesselation.
The natural and likely most frequent choice is the latitude/longitude approach used for navigation on Earth (see also Euler angles, this is the same but without roll). Here we use two coordinates: latitude to say the "vertical" position between north and south pole and longitude for "horizontal" distance from some conventionally chosen meridian. The principle is pretty straightforward, simple and on small scales approximates the Cartesian coordinates, which is awesome. But the system isn't without shortcomings, namely for example that longitude is meaningless on the poles (the problem known as Gimbal lock in Euler angles), i.e. it's redundant, the poles have infinitely many representations etcetc. In programming a disadvantage is non-uniform sampling -- that is if the coordinates are limited to finitely many values (integers, fixed point, floating point, ...), loads of points will be densely concentrated around the poles while the resolution around the equator will be sparser. Imagine you'd want to divide land on Earth with let's say a 256x256 grid mapped onto it by this scheme (y is latitude, x is longitude) -- it's going to be quite ugly, some cells will be small, others big and many will have awkward "tall but narrow" spaghetti shapes, PLUS dealing with the poles will be a pain. The system is also topologically non-spherical (well, prolly depends on how we treat the poles or something I dunno), we just forcefully project and display something non-spherical on a sphere, so this has no value for cellular automata experiments for example.
Hence the desire for better alternatives. Apparently there exist some already, based on space filling curves and similar stuff. But let's try to come up with something on our own.
A relatively cool idea is projecting cube onto a sphere, something used for instance with cubemaps in computer graphics. Coordinates on the surface of a cube are easy: you say which side the point is at (number 0 to 5) and then you give the point's position within that side with normal Cartesian coordinates. Now you can 1 to 1 pair every point of a spherical surface with every point of a cube's surface: simply put a small cube inside a sphere, align their centers, and then for any point p_c on the cube you get a unique point on the sphere p_s by casting a straight ray from the sphere's center through p_c, hitting a point on the sphere, which is p_s. Vice versa works the same. So you essentially divide the sphere's surface to 6 "squares" and continue with Cartesian coordinates in each. Sampling density (and thus also shapes of mapped grid cells) is good, although not perfect. A slight disadvantage may be a little more difficult (slow) math and potential branches in code (due to 6 individual sides). This approach is well usable for cellular automata already, however with one caveat: pinch points. Pinch points correspond to the vertices of the cube, i.e. there are 8 of them, and their problem is that there will be only 3 cells around every pinch point while every other point will have 4 points around (as is the case with planar cellular automata as well). This is troublesome because it messes with rules of cellular automata but not just that, it also fucks up some assumption such as that going "up, left, down and right" gets you to the where you started. Maybe it doesn't seems too bad but the problem's a real bitch.
Now let's keep following the same line of thought with projecting regular tetrahedron (3-simplex) onto a sphere. We lose the convenient Cartesian grid but obtain something nice in return. Say we want to locate point p on the sphere with certain accuracy. Initially we start with the sphere split in 4 "triangular" parts (the projected tetrahedron faces), so we can start by saying which of these 4 regions p lies in -- this requires 2 bits (able to express 4 value). To give the position more precisely, we can now subdivide our triangular region into 4 new triangles by splitting each side in two and connecting them. Again we require 2 bits to reveal which of the new triangles p occupies. And we can repeat this process as many times we like to get arbitrarily close to p. The cool thing is that our coordinates are now elegantly a single string of (pairs of) bits and they get more precise the longer the string is -- we can even cut off some bits from the end to get shorter coordinates for the price of lowering our resolution. Note however that the triangles won't generally be of the same size and area (consider for example that on a spherical surface it no longer holds that subdividing an equilateral triangle by splitting its sides in halves gives us 4 new equilateral triangles of same area). Octahedron can alternatively be considered as the starting shape: it's less elegant (the first choice requires 3 bits, not 2, since there are 8 faces) but possibly aligns better with other coordinate systems, for example there is exact north and south pole, equator and 4 equally spaced meridians. However should you decide for this you might as well go with the "cubemap" approach and treat each of its sides with subdivisions too (you can split a square face into four new squares, that's 2 bits again), then you'll get back the nice square grid. In 3D computer graphics we often use icospheres which start with icosahedron (20 triangular faces) and then keep subdividing the triangles as per above with the reason being that this results in very nice triangles that are "almost" equilateral and have similar areas. Bad news is that any of these systems still retains pinch points (although tetrahedron will only have 4) -- only Platonic solids have no pinch points.
This projection of shapes still leaves many ideas to be explored, for example: take a square grid, then kinda "reshape" it to a circular shape and project it top-down onto the sphere, which will cover the upper hemisphere, and do the same with another grid for the lower hemisphere (and connect the grids together by their touching sides). This will have some badly shaped cells and 4 pinch points, but can be usable and will be simple (it's basically the normal torus "wrap-around" grid). And so forth, feel free to think up more stuff like this. See also Platonic solids.
Now here is a sketch of the space filling curve idea. Quick recap/definition of a space filling curve for our purposes: it's an infinitely long fractal path in flat 2D plane that starts at origin (point [0,0]) and visits EVERY point in the unit square (from [0,0] to [1,1]) EXACTLY ONCE without ever stepping outside the square. Position on the curve is given by parameter t which is a single real number from 0 to 1. There exist various such curves, e.g. Hilbert curve and Peano curve -- let's go with Hilbert whose end lies in point [1,0] (or [0,1] if we transpose it). Now we can start with the "cubemap" trick: we project a cube onto our sphere and then simply fill each of the cube's sides (a unit square) with Hilbert curve so that each side's curve end connects to the next side curve's beginning. Remember that each cube's surface point corresponds 1:1 to the all of the sphere's surface points, we just have to do some projections. So now we can identify any surface point with a SINGLE real parameter that goes from 0 to 6 (there are 6 cube sides, each with a parameter going from 0 to 1). This may need some refinement due to edges for example (edge points may be touched by two side's curves), but it's a start. In fact it appears to be best to think in terms of subdivisions again: level 0 says the specific cube side (0 to 5), level 1 says the subsquare of the side, level 2 says the subsquare of the level 1 subsquare etc. -- this way we can treat the coordinates as a string of digits whose resolution increases with the string length. { I think this is actually one of the existing coordinate systems, think I saw it on Wikipedia. Hope it's not patented or something. ~drummyfish } Perhaps it could also be considered to start with just planes instead of a cube or with tetrahedron (see above) and then use a triangle filling curve.
.-------top------.
; 11==12 21==22 ;
; || || || || ;
; 10 13==20 23 ;
; || || ;
; 03==02 31==30 ;
; || || ;
; 00==01 32==33 ;
'-------------||-'
||
.------front--||-. .------right-----.
: 51==50==43 40 : : 91==92 A1==A2 :
: || || || : : || || || || :
: 52==53 42==41 : : 90 93==A0 A3 :
: || : : || || :
: 61==60 71==72 : : 83==82 B1==B0 :
: || || || : : || || :
: 62==63==70 73======80==81 B2==B3 :
'----------------' '-------------||-'
||
.-----bottom--||-. .------back------.
: D1==D0==C3 C0 : : H1==H2 I1==I2 :
: || || || : : || || || || :
: D2==D3 C2==C1 : : H0 H3==I0 I3 :
: || : : || || :
: E1==E0 F1==F2 : : G3==G2 J1==J0 :
: || || || : : || || :
: E2==E3==F0 F3======G0==G1 J2==J3 :
'----------------' '-------------||-'
||
.-----right---||-.
: L1==L0==K3 K0 :
: || || || :
: L2==L3 K2==K1 :
: || :
: M1==M0 N1==N2 :
: || || || :
: M2==M3==N0 N3 :
'----------------'Continuous path over cube's surface (that can be projected onto a sphere) with Hilbert's space filling curve. It's even a closed loop.
Another idea is to consider a spiral starting at the north pole, then going down and around until it hits the south pole. This in itself isn't a space filling curve, so we can't increase accuracy, but if we know desired accuracy beforehand, we can accordingly choose the system's parameters (probably two: the total number of points along the spiral and the number of turns the spiral makes around the globe). With this we'll be able to specify position with one parameter like with space filling curves and won't be dealing with the "Gimbal lock" headaches.
Deserving a few words is also the following imperfect but interesting idea. Imagine we cut off the north and south pole caps of the sphere and thereby limit ourselves to only "non-polar" regions of the sphere (with Earth we oftentimes ignore polar regions too). We are now left with something like a "fat cylinder" or a tyre. We can project a cylinder onto this, and cylinder's surface can nicely be covered with a Cartesian grid whose left side is connected to its right side so that one can keep going around indefinitely. However we can also allow going "over the border" up and down. If we connected top to bottom the same way to the left/right sides, we'd get a torus (doughnut) topology, and that's not quite a sphere (going over north pole you'd suddenly appear at the south pole). What we can do is connect both top and bottom side of the grid EACH TO ITSELF, in a "special way". Imagine you cross the northern border -- then you'll appear on the cell that's half the grid width to the right (or left, it doesn't matter) and turned upside down. The same would happen on the southern border. Visually you can imagine it simply as "skipping" the polar cap to the cell that's straight forward in front of you. Sure, this still sucks in many ways (no poles, sampling density still bad, ...) but it's a relatively simple way to get "something like a sphere".
TODO: moar, maybe "quaternions without roll"?
Powered by nothing. All content available under CC0 1.0 (public domain). Send comments and corrections to drummyfish at disroot dot org.