Some notes about how to generate geometry for 3d scenes dynamically, rather than designing models in 3d programs and importing them.
For example, if you wanted to have 3d terrain you probably wouldn't model completely it in a 3d program and import it as a mesh object. Maybe instead you would randomly generate it, or perhaps generate a height map and generate the terrain using that, or some other technique.
For generating meshes the popular approach is CSG or Constructive Solid Geometry, where you use geometric primitives and perform boolean operations on them. For example a tube would either be a smaller diameter cylinder subtracted from a larger diameter one, or an liner extrusion of a 2d ring.
But what if we treat a triangle as a basic unit of a mesh, and perform mathematical transformations on it to build shapes up.
Or perhaps another way: imagine defining some mathematical plane defined by a function. Then "sampling" from that plane based on a 2d grid that defines a pattern of triangles. Imagine a mathematical plane that looks like a egg shaped tent, defined by the function: z = 200 - (x^2 + y^2). We could generate an x,y 2d grid of points defining a pattern of triangles, and then project the points that down onto the plane to find the Z height. This would give us a triangular mesh in that shape.
However as the slope of the plane we are projecting onto increases, the triangle size gets "skewed" because small differences in X or Y dimensions result in a large Z difference. So what if we distorted the 2d grid so it had a higher density of trianges if that portion of the grid were above an area of large slope in the 3d plane. That "density" would approach infinitely small triangle points as we approached infinite slope. Or the 3d plane approaches limits around the edges as the slope approaches goes toward totally vertical.
Consider another example: a sphere. Imagine we had a 3d mathematical representation of a sphere. We then generated a uniform 2d grid of triangulation points and "descended" this plane down on top of the sphere, like we were draping a cloth over the top of the sphere. Looking down from the top, right at the edges of the sphere (which from this view we see as a circle), we have a problem: some of our triangulation points "miss" the sphere and do not intersect with it. Like the example above, if we increase the density of triangulation points as we approach the edge of this circle looking down, the density increases to infinity right on the circle edge. So what would our triangles look like there? Like a mess.
Another approach is to compute triangles in an "iterative" way. This would mean we might pick a point on the sphere and generate a triangle centered there. We then take each side of that triangle and generate more triangles around it. However, each of those triangles must be at an angle to the original, so they wrap onto the surface of the sphere. Specifically, each triangle would be oriented to the 3d tangent of the surface of the sphere, at a distance of radius from the center of the sphere. But we have a problem where we must compute the exact position of the center of each triangle, and the exactl size of each triangle, such that the three points of each triangle match exactly neighbouring triangle points, otherwise we end up with weird floating point offset gaps in our mesh.
What we really want to do is compute the points of the triangles, not their center. That way our triangles are made up of joining the points together, ensuring no gaps between trangles edges. If all computed triangle points are always at exatly radius distance from the center, then our triangulated sphere is always smaller in volume to our methematical sphere. Approaching equal volume as the number of triangles approaches infinity.
Now imagine a globe of the earth with lines of longitude going from pole to pole. We could triangulate this easily by generating lines of latitude at regular intervals around the sphere, and then each "square" is simply triangulated as a quad. At the poles we would need a special case to generate a triangle "fan" rather than a ring of quads. This is how many spheres in CAD programs are generated.
Wikipedia as usual, probably has a good description of the problem - but it's unintelligble to me. The torus image there has some strange "artifacts" that to me indicate the problem is not "simple". For example, some parts of the torus have a regular repetition of triangles. But other areas seem to descend into a chaotic arrangement of triangles.
In that example above of draping a cloth over a sphere: If you were to do that with a real cloth over a real sphere, at the edges of the sphere the cloth would gether folds. And these folds would perhaps be "chaotic" in that their location and size would not be uniform. Would that chaos be simply due to tiny differences in the weave strength of the cloth? If you could somehow manuafacture a cloth with a totally uniform weave strength (or elasiticy), would the folds in the cloth be uniform around the edges of the sphere?
Here is another messed up idea: what if you generated a bunch of random points on the surface of a sphere, and then applied a virtual replusive force between all of them, so they all tried to get as far away from each other as possible, while being confined to the surface?
If I look at an icosahedron, oriented a certain way it looks like two triangle fans made of five triangles each, one above and one below, connected via a ring made of triangles around the circumfrence. However, you can also look at it as a collection of equilateral triangle pairs, where each pair has the same angle between the connected edges. If each angle is equal to all others, there must be a discrete angles (an infinite amount of them) that can generate a sphere-like shape. Each descrete angle will correspond to the number of triangles in the shape. There should be a formula that relates the number of triangles in the shape to each discrete angle in that set. Actually, the set of angles is not infinite: the angles must be less than the angle that makes up a tetrahedron, and can also not reach zero.
Oh, but here is something really fucked up: as that angle reduces it gets closer to zero. And a zero angle would be a sphere of an infinite radius. Yet "size" is meaningless because none of the variables are dimensions (nr. triangles or angles). I suppose nr. of triangles is kindof like size, in that you would need an infinite number of triangles to make a sphere where the angle between them is zero.
A triangle has three edges. Each time we generate a triangle we have to decide to create either zero, one, or two additional triangles. Imagine we are generating a flat triangle strip. We first create our starting triangle, we then generate a new triangle from the left edge of that one, and we then generate a new triangle from the right edge of that one. Then another from the left edge of that one, and so on. So the edge that we generate a triangle from alternates.
Considering Platonic solids of the type made exclusively of equilateral triangles we have:
Each once is can be created using a "net". This is a flat 2d representation of the shape that can be "folded" up into the 3d shape. The first thing to establish is: Can we come up with a "procedure" (repeatable process) that can generate a net for every possible convex solid that can be made of equilateral triangles?
Ok, here is an interesting thing:
In geometry, a deltahedron (plural deltahedra) is a polyhedron whose faces
are all equilateral triangles. The name is taken from the Greek upper case
delta (Δ), which has the shape of an equilateral triangle. There are
infinitely many deltahedra, all having an even number of faces by the
handshaking lemma. Of these only eight are convex, having 4, 6, 8, 10, 12,
14, 16 and 20 faces.
Wow, so "Of these only eight are convex, having 4, 6, 8, 10, 12, 14, 16 and 20 faces". Of an infinite number of them... So basically: no. As soon as we go beyond 20 faces it is not possible to generate a convex solid made exclusively of equilateral triangles!
But wait, this is a bit weird: I can't find any convex polyhedron made up of 6 equilateral triangles! Ahh, there is one called a "triangular bipyramid" but three edges do not have the same dihedral angle as the others.
Ok, so my new question is this:
How many convex solids (convex polyhedra) can be made exclusively of
equilateral triangles, where all dihedral angles are identical?
Why ask this question? Because presumably all these can be made with the simplist of algorithms. "Convex deltahedrons with congruent dihedral angles". So how many convex deltahedrons with congruent dihedral angles are there? Answer: a whopping three! The tetrahedron, octahedron and isosahedron!
From the table of polyhedron dihedral angles:
Polyhedra Sides Degrees Computation
---------------------------------------------------
Tetrahedron 4 70.529° arccos(1/3)
Octahedron 8 109.471° arccos(-1/3)
Isosahedron 20 138.190° arccos (-(√5/3))
I also learned that "congruent dihedral angles" is called isotoxal:
In geometry, a polytope (for example, a polygon or a polyhedron) or a
tiling is isotoxal (from Greek τόξον 'arc') or edge-transitive if its
symmetries act transitively on its edges. Informally, this means that there
is only one type of edge to the object: given two edges, there is a
translation, rotation, and/or reflection that will move one edge to the
other, while leaving the region occupied by the object unchanged.
Update our description to "Convex isotoxal deltahedrons"! So to conclude: if we make an algorithm that performs the same "folding angle" on every edge (isotoxal), and every triangle is equilateral, we can make a grand total of three convex shapes.
Polyhedra Possible nets
-----------------------------
Tetrahedron 2
Octahedron 11
Isosahedron 43380
If we pick one of two the possible tetrahedron nets, can we pick one of the 11 possible octahedron nets that "algorithmically" seems to follow from that, and then pick one of the 43380 possible isosahedron nets that algorithmically follows from that? I am not sure this is really possible, and with only three possible polyhedra it's not really enough to go by. We could allow non-convex polyhedra in, as long as they are isotoxal?
One of the two possible nets for a tetrahedron is a triangle strip, as described in the top of this section: make a triangle, pick the left edge and make a new triangle there, pick the right edge of that and make a new triangle there, pick the left edge of that triangle and make a new one there: four triangles in total making a strip. Then fold each edge "up" by about 70.53 degrees and we have a tetrahedron!
One possible way of thinking about net generation is that the process of creating triangles should follow a single "path" - that is that each triangle is generated from the edge of the previous triangle, with no "backtracking" to a previous triangle (perhaps, although with recursion this backtracking might be possible/better). For example, of the 11 possible octahedron nets, only 3 can be generated without branching or backtracking.
Taking just those three shapes into account, what would a little machine need to do in order to manufacture those? This machine manufactures vertexes. It is "executed" once for each triangle. Let's start with the tetrahedron:
It is executed four times. Apart from the first triangle, each pass needs to generate only one vertex - the "apex" of that triangle being generated. This is because the two vertexes making up the base were generated in the previous triangle. However on the first pass the first two vertexes making up the base need to be generated. Ther machine has a "memory" of two vertexes - these are the base line vertexes of the triangle being generated. After generating the third vertex this memory is updated. If we have a strip where the vertex numbers increment from left to right then right to left at each step along the strip:
vertex nr. prev indexes new vertex nr. memory put new one in
1,2,3 [0,1] 3 [1,2] n/a
3,4,2 [0,2] 4 [3,2] 0
3,4,5 [0,1] 5 [3,4] 1
5,6,4 [0,2] 6 [5,4] 0
It might be easier to just have a three vertex memory: