thallada.github.io/_posts/2020-02-01-generating-icosahedrons-and-hexspheres-in-rust.md

759 lines
27 KiB
Markdown
Raw Permalink Normal View History

---
title: "Generating icosahedrons and hexspheres in Rust"
layout: post
2020-02-02 02:08:58 +00:00
image: /img/blog/hexsphere_colored_7.png
---
I've been trying to learn [Rust](https://www.rust-lang.org/) lately, the hot new
systems programming language. One of the projects I wanted to tackle with the
speed of Rust was generating 3D polyhedron shapes. Specifically, I wanted to
implement something like the [Three.js
`IcosahedronGeometry`](https://threejs.org/docs/#api/en/geometries/IcosahedronGeometry)
in Rust. If you try to generate
[icosahedron](https://en.wikipedia.org/wiki/Icosahedron)s in Three.js over any
detail level over 5 the whole browser will slow to a crawl. I think we can do
better in Rust!
Furthermore, I wanted to generate a hexsphere: a sphere composed of hexagon
faces and 12 pentagon faces, otherwise known as a truncated icosahedron or the
[Goldberg polyhedron](https://en.wikipedia.org/wiki/Goldberg_polyhedron). The
shape would be ideal for a game since (almost) every tile would have the same
area and six sides to defend or attack from. There's a few [Javascript projects
for generating hexspheres](https://www.robscanlon.com/hexasphere/). Most of them
generate the shape by starting with a subdivided icosahedron and then truncating
the sides into hexagons. Though, there [exist other methods for generating the
hexsphere
shape](https://stackoverflow.com/questions/46777626/mathematically-producing-sphere-shaped-hexagonal-grid).
**Play around with all of these shapes in your browser at:
[https://www.hallada.net/planet/](https://www.hallada.net/planet/).**
So, how would we go about generating a hexsphere from scratch?
<!--excerpt-->
### The Icosahedron Seed
To start our sculpture, we need our ball of clay. The most basic shape that we
start with can be defined by its 20 triangle faces and 12 vertices: the regular
icosahedron. If you've ever played Dungeons and Dragons, this is the 20-sided
die.
To define this basic shape in Rust, we first need to define a few structs. The
most basic unit we need is a 3D vector which describes a single point in 3D
space with a X, Y, and Z float values. I could have defined this myself, but to
avoid having to implement a bunch of vector operations (like add, subtract,
multiply, etc.) I chose to import
[`Vector3`](https://docs.rs/cgmath/0.17.0/cgmath/struct.Vector3.html) from the
[cgmath crate](https://crates.io/crates/cgmath).
The next struct we need is `Triangle`. This will define a face between three
vertices:
```rust
#[derive(Debug)]
pub struct Triangle {
pub a: usize,
pub b: usize,
pub c: usize,
}
impl Triangle {
fn new(a: usize, b: usize, c: usize) -> Triangle {
Triangle { a, b, c }
}
}
```
We use `usize` for the three points of the triangle because they are indices
into a [`Vec`](https://doc.rust-lang.org/std/vec/struct.Vec.html) of `Vector3`s.
To keep these all together, I'll define a `Polyhedron` struct:
```rust
#[derive(Debug)]
pub struct Polyhedron {
pub positions: Vec<Vector3>,
pub cells: Vec<Triangle>,
}
```
With this, we can define the regular icosahedron:
```rust
impl Polyhedron {
pub fn regular_isocahedron() -> Polyhedron {
let t = (1.0 + (5.0 as f32).sqrt()) / 2.0;
Polyhedron {
positions: vec![
Vector3::new(-1.0, t, 0.0),
Vector3::new(1.0, t, 0.0),
Vector3::new(-1.0, -t, 0.0),
Vector3::new(1.0, -t, 0.0),
Vector3::new(0.0, -1.0, t),
Vector3::new(0.0, 1.0, t),
Vector3::new(0.0, -1.0, -t),
Vector3::new(0.0, 1.0, -t),
Vector3::new(t, 0.0, -1.0),
Vector3::new(t, 0.0, 1.0),
Vector3::new(-t, 0.0, -1.0),
Vector3::new(-t, 0.0, 1.0),
],
cells: vec![
Triangle::new(0, 11, 5),
Triangle::new(0, 5, 1),
Triangle::new(0, 1, 7),
Triangle::new(0, 7, 10),
Triangle::new(0, 10, 11),
Triangle::new(1, 5, 9),
Triangle::new(5, 11, 4),
Triangle::new(11, 10, 2),
Triangle::new(10, 7, 6),
Triangle::new(7, 1, 8),
Triangle::new(3, 9, 4),
Triangle::new(3, 4, 2),
Triangle::new(3, 2, 6),
Triangle::new(3, 6, 8),
Triangle::new(3, 8, 9),
Triangle::new(4, 9, 5),
Triangle::new(2, 4, 11),
Triangle::new(6, 2, 10),
Triangle::new(8, 6, 7),
Triangle::new(9, 8, 1),
],
}
}
}
```
### JSON Serialization
To prove this works, we need to be able to output our shape to some format that
will be able to be rendered. Coming from a JS background, I'm only familiar with
rendering shapes with WebGL. So, I need to be able to serialize the shape to
JSON so I can load it in JS.
There's an amazing library in Rust called
[serde](https://crates.io/crates/serde) that will make this very
straightforward. We just need to import it and `impl Serialize` for all of our
structs.
The JSON structure we want will look like this. This is what Three.js expects
when initializing
[`BufferGeometry`](https://threejs.org/docs/#api/en/core/BufferGeometry).
```json
{
"positions": [
[
-0.8506508,
0,
0.5257311
],
...
],
"cells": [
[
0,
1,
2,
],
...
],
}
```
For the `"cells"` array, we'll need to serialize `Triangle` into an array of 3
integer arrays:
```rust
impl Serialize for Triangle {
fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
where
S: Serializer,
{
let vec_indices = vec![self.a, self.b, self.c];
let mut seq = serializer.serialize_seq(Some(vec_indices.len()))?;
for index in vec_indices {
seq.serialize_element(&index)?;
}
seq.end()
}
}
```
I had some trouble serializing the `cgmath::Vector3` to an array, so I made my
own type that wrapped `Vector3` that could be serialized to an array of 3
floats.
```rust
#[derive(Debug)]
pub struct ArraySerializedVector(pub Vector3<f32>);
impl Serialize for ArraySerializedVector {
fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
where
S: Serializer,
{
let values = vec![self.0.x, self.0.y, self.0.z];
let mut seq = serializer.serialize_seq(Some(values.len()))?;
for value in values {
seq.serialize_element(&value)?;
}
seq.end()
}
}
```
And now `Polyhedron` needs to use this new type and implement `Serialize` for
the whole shape to get serialized:
```rust
#[derive(Serialize, Debug)]
pub struct Polyhedron {
pub positions: Vec<ArraySerializedVector>,
pub cells: Vec<Triangle>,
}
```
The actual serialization is done with:
```rust
fn write_to_json_file(polyhedron: Polyhedron, path: &Path) {
let mut json_file = File::create(path).expect("Can't create file");
let json = serde_json::to_string(&polyhedron).expect("Problem serializing");
json_file
.write_all(json.as_bytes())
.expect("Can't write to file");
}
```
On the JS side, the `.json` file can be read and simply fed into either Three.js
or [regl](https://github.com/regl-project/reg) to be rendered in WebGL ([more on
that later](#rendering-in-webgl-with-regl)).
![Regular Icosahedron](/img/blog/icosahedron_colored_1.png)
## Subdivided Icosahedron
Now, we need to take our regular icosahedron and subdivide its faces N number of
times to generate an icosahedron with a detail level of N.
I pretty much copied must of [the subdividing code from
Three.js](https://github.com/mrdoob/three.js/blob/34dc2478c684066257e4e39351731a93c6107ef5/src/geometries/PolyhedronGeometry.js#L90)
directly into Rust.
I won't bore you with the details here, you can find the function
[here](https://github.com/thallada/icosahedron/blob/9643757df245e29f5ecfbb25f9a2c06b3a4e1217/src/lib.rs#L160-L205).
![Subdivided Icosahedron](/img/blog/icosahedron_colored_3.png)
### Truncated Icosahedron
Now we get to the meat of this project. Transforming an icosahedron into a
hexsphere by
[truncating](https://en.wikipedia.org/wiki/Truncation_%28geometry%29) the points
of the icosahedron into hexagon and pentagon faces.
You can imagine this operation as literally cutting off the points of the
subdivided icosahedron at exactly the midpoint between the point and it's six or
five neighboring points.
![Image of biggest dodecahedron inside
icosahedron](/img/blog/dodecahedron_in_icosahedron.png)
([image source](http://www.oz.nthu.edu.tw/~u9662122/DualityProperty.html))
In this image you can see the regular icosahedron (0 subdivisions) in wireframe
with a yellow shape underneath which is the result of all 12 points truncated to
12 pentagon faces, in other words: the [regular
dodecahedron](https://en.wikipedia.org/wiki/Dodecahedron).
You can see that the points of the new pentagon faces will be the exact center
of the original triangular faces. It should now make sense why truncating a
shape with 20 faces of 3 edges each results in a shape with 12 faces of 5 edges
each. Each pair multiplied still equals 60.
#### Algorithm
There are many different algorithms you could use to generate the truncated
shape, but this is roughly what I came up with:
1. Store a map of every icosahedron vertex to faces composed from that vertex
(`vert_to_faces`).
2. Calculate and cache the [centroid](https://en.wikipedia.org/wiki/Centroid) of
every triangle in the icosahedron (`triangle_centroids`).
3. For every vertex in the original icosahedron:
4. Find the center point between all of centroids of all of the faces for that
vertex (`center_point`). This is essentially the original icosahedron point
but lowered towards the center of the polygon since it will eventually be the
center of a new flat hexagon face.
![hexagon center point in red with original icosahedron faces fanning
out](/img/blog/hexagon_fan.png)
5. For every triangle face composed from the original vertex:
![hexagon fan with selected triangle face in
blue](/img/blog/hexagon_fan_triangle_selected.png)
6. Sort the vertices of the triangle face so there is a vertex `A` in the center
of the fan like in the image, and two other vertices `B` and `C` at the edges
of the hexagon.
7. Find the centroid of the selected face. This will be one of the five or six
points of the new pentagon or hexagon (in brown in diagram below:
`triangleCentroid`).
8. Find the mid point between `AB` and `AC` (points `midAB` and `midAC` in
diagram).
9. With these mid points and the face centroid, we now have two new triangles
(in orange below) that form one-fifth or one-sixth of the final pentagon or
hexagon face. Add the points of the triangle to the `positions` array. Add
the two new triangles composed from those vertices as indexes into the
`positions` array to the `cells` array. We need to compose the pentagon or
hexagon out of triangles because in graphics everything is a triangle, and
this is the simplest way to tile either shape with triangles:
![hexagon fan ](/img/blog/hexagon_fan_construct.png)
10. Go to step 5 until all faces of the icosahedron vertex have been visited.
Save indices to all new triangles in the `cells` array, which now form a
complete pentagon or hexagon face, to the `faces` array.
![hexagons tiling on icosahedron faces](/img/blog/hexagon_tiling.png)
11. Go to step 3 until all vertices in the icosahedron have been visited. The
truncated icosahedron is now complete.
![colored hexsphere of detail level 3](/img/blog/hexsphere_colored_3.png)
#### Code
The `truncate` function calls out to a bunch of other functions, so [here's a
link to the function within the context of the whole
file](https://github.com/thallada/icosahedron/blob/9643757df245e29f5ecfbb25f9a2c06b3a4e1217/src/lib.rs#L227).
### Calculating Normals
It took me a surprisingly long time to figure out how to compute
[normals](https://en.wikipedia.org/wiki/Normal_(geometry)) for the truncated
icosahedron. I tried just using an out-of-the-box solution like
[angle-normals](https://github.com/mikolalysenko/angle-normals/blob/master/angle-normals.js)
which could supposedly calculate the normal vectors for you, but they came out
all wrong.
![hexsphere with bad normals](/img/blog/bad_hexsphere_normals.png)
So, I tried doing it myself. Most tutorials on computing normal vectors for a
mesh assume that it is tiled in a particular way. But, my algorithm spins around
icosahedron points in all different directions, and so the triangle points are
not uniformly in clockwise or counter-clockwise order.
I could have sorted these points into the correct order, but I found it easier
to instead just detect when the normal was pointing the wrong way and just
invert it.
```rust
pub fn compute_triangle_normals(&mut self) {
let origin = Vector3::new(0.0, 0.0, 0.0);
for i in 0..self.cells.len() {
let vertex_a = &self.positions[self.cells[i].a].0;
let vertex_b = &self.positions[self.cells[i].b].0;
let vertex_c = &self.positions[self.cells[i].c].0;
let e1 = vertex_a - vertex_b;
let e2 = vertex_c - vertex_b;
let mut no = e1.cross(e2);
// detect and correct inverted normal
let dist = vertex_b - origin;
if no.dot(dist) < 0.0 {
no *= -1.0;
}
let normal_a = self.normals[self.cells[i].a].0 + no;
let normal_b = self.normals[self.cells[i].b].0 + no;
let normal_c = self.normals[self.cells[i].c].0 + no;
self.normals[self.cells[i].a] = ArraySerializedVector(normal_a);
self.normals[self.cells[i].b] = ArraySerializedVector(normal_b);
self.normals[self.cells[i].c] = ArraySerializedVector(normal_c);
}
for normal in self.normals.iter_mut() {
*normal = ArraySerializedVector(normal.0.normalize());
}
}
```
### Assigning Random Face Colors
Finally, all that's left to generate is the face colors. The only way I could
figure out how to individually color a shape's faces in WebGL was to pass a
color per vertex. The issue with this is that each vertex of the generated
shapes could be shared between many different faces.
How can we solve this? At the cost of memory, we can just duplicate a vertex
every time it's used by a different triangle. That way no vertex is shared.
This can be done after a shape has been generated with shared vertices.
```rust
pub fn unique_vertices(&mut self, other: Polyhedron) {
for triangle in other.cells {
let vertex_a = other.positions[triangle.a].0;
let vertex_b = other.positions[triangle.b].0;
let vertex_c = other.positions[triangle.c].0;
let normal_a = other.normals[triangle.a].0;
let normal_b = other.normals[triangle.b].0;
let normal_c = other.normals[triangle.c].0;
self.positions.push(ArraySerializedVector(vertex_a));
self.positions.push(ArraySerializedVector(vertex_b));
self.positions.push(ArraySerializedVector(vertex_c));
self.normals.push(ArraySerializedVector(normal_a));
self.normals.push(ArraySerializedVector(normal_b));
self.normals.push(ArraySerializedVector(normal_c));
self.colors
.push(ArraySerializedVector(Vector3::new(1.0, 1.0, 1.0)));
self.colors
.push(ArraySerializedVector(Vector3::new(1.0, 1.0, 1.0)));
self.colors
.push(ArraySerializedVector(Vector3::new(1.0, 1.0, 1.0)));
let added_index = self.positions.len() - 1;
self.cells
.push(Triangle::new(added_index - 2, added_index - 1, added_index));
}
self.faces = other.faces;
}
```
With unique vertices, we can now generate a random color per face with the [rand
crate](https://crates.io/crates/rand).
```rust
pub fn assign_random_face_colors(&mut self) {
let mut rng = rand::thread_rng();
for i in 0..self.faces.len() {
let face_color = Vector3::new(rng.gen(), rng.gen(), rng.gen());
for c in 0..self.faces[i].len() {
let face_cell = &self.cells[self.faces[i][c]];
self.colors[face_cell.a] = ArraySerializedVector(face_color);
self.colors[face_cell.b] = ArraySerializedVector(face_color);
self.colors[face_cell.c] = ArraySerializedVector(face_color);
}
}
}
```
### Binary Serialization
Now that we have to duplicate vertices for individual face colors, the size of
our JSON outputs are getting quite big:
| File | Size |
|---|---|
| icosahedron_r1_d6.json | 28 MB |
| icosahedron_r1_d7.json | 113 MB |
| hexsphere_r1_d5.json | 42 MB |
| hexsphere_r1_d6.json | 169 MB |
Since all of our data is just floating point numbers, we could reduce the size
of the output considerably by using a binary format instead.
I used the [byteorder](https://docs.rs/byteorder/1.3.2/byteorder/) crate to
write out all of the `Vec`s in my `Polyhedron` struct to a binary file in
little-endian order.
The binary format is laid out as:
1. 1 32 bit unsigned integer specifying the number of vertices (`V`)
2. 1 32 bit unsigned integer specifying the number of triangles (`T`)
3. `V` * 3 number of 32 bit floats for every vertex's x, y, and z coordinate
4. `V` * 3 number of 32 bit floats for the normals of every vertex
5. `V` * 3 number of 32 bit floats for the color of every vertex
6. `T` * 3 number of 32 bit unsigned integers for the 3 indices into the vertex
array that make every triangle
The `write_to_binary_file` function which does all that is
[here](https://github.com/thallada/icosahedron/blob/9643757df245e29f5ecfbb25f9a2c06b3a4e1217/src/bin.rs#L13).
That's a lot better:
| File | Size |
|---|---|
| icosahedron_r1_d6.bin | 9.8 MB |
| icosahedron_r1_d7.bin | 11 MB |
| hexsphere_r1_d5.bin | 14 MB |
| hexsphere_r1_d6.bin | 58 MB |
On the JavaScript side, the binary files can be read into `Float32Array`s like
this:
```javascript
fetch(binaryFile)
.then(response => response.arrayBuffer())
.then(buffer => {
let reader = new DataView(buffer);
let numVertices = reader.getUint32(0, true);
let numCells = reader.getUint32(4, true);
let shape = {
positions: new Float32Array(buffer, 8, numVertices * 3),
normals: new Float32Array(buffer, numVertices * 12 + 8, numVertices * 3),
colors: new Float32Array(buffer, numVertices * 24 + 8, numVertices * 3),
cells: new Uint32Array(buffer, numVertices * 36 + 8, numCells * 3),
})
```
### Rendering in WebGL with Regl
I was initially rendering the shapes with Three.js but switched to
[regl](https://github.com/regl-project/regl) because it seemed like a more
direct abstraction over WebGL. It makes setting up a WebGL renderer incredibly
easy compared to all of the dozens cryptic function calls you'd have to
otherwise use.
This is pretty much all of the rendering code using regl in my [3D hexsphere and
icosahedron viewer project](https://github.com/thallada/planet).
```javascript
const drawShape = hexsphere => regl({
vert: `
precision mediump float;
uniform mat4 projection, view;
attribute vec3 position, normal, color;
varying vec3 fragNormal, fragPosition, fragColor;
void main() {
fragNormal = normal;
fragPosition = position;
fragColor = color;
gl_Position = projection * view * vec4(position, 1.0);
}`,
frag: `
precision mediump float;
struct Light {
vec3 color;
vec3 position;
};
uniform Light lights[1];
varying vec3 fragNormal, fragPosition, fragColor;
void main() {
vec3 normal = normalize(fragNormal);
vec3 light = vec3(0.1, 0.1, 0.1);
for (int i = 0; i < 1; i++) {
vec3 lightDir = normalize(lights[i].position - fragPosition);
float diffuse = max(0.0, dot(lightDir, normal));
light += diffuse * lights[i].color;
}
gl_FragColor = vec4(fragColor * light, 1.0);
}`,
attributes: {
position: hexsphere.positions,
normal: hexsphere.normals,
color: hexsphere.colors,
},
elements: hexsphere.cells,
uniforms: {
"lights[0].color": [1, 1, 1],
"lights[0].position": ({ tick }) => {
const t = 0.008 * tick
return [
1000 * Math.cos(t),
1000 * Math.sin(t),
1000 * Math.sin(t)
]
},
},
})
```
I also imported [regl-camera](https://github.com/regl-project/regl-camera) which
handled all of the complex viewport code for me.
It was fairly easy to get a simple renderer working quickly in regl, but I
couldn't find many examples of more complex projects using regl. Unfortunately,
the project looks a bit unmaintained these days as well. If I'm going to
continue with rendering in WebGL, I think I will try out
[Babylon.js](https://www.babylonjs.com/) instead.
### Running in WebAssembly
Since rust can be compiled down to wasm and then run in the browser, I briefly
tried getting the project to run completely in the browser.
The [wasm-pack](https://github.com/rustwasm/wasm-pack) tool made it pretty easy
to get started. My main struggle was figuring out an efficient way to get the
megabytes of generated shape data into the JavaScript context so it could be
rendered in WebGL.
The best I could come up with was to export all of my structs into flat
`Vec<f32>`s and then create `Float32Array`s from the JS side that are views into
wasm's memory.
To export:
```rust
pub fn fill_exports(&mut self) {
for position in &self.positions {
self.export_positions.push(position.0.x);
self.export_positions.push(position.0.y);
self.export_positions.push(position.0.z);
}
for normal in &self.normals {
self.export_normals.push(normal.0.x);
self.export_normals.push(normal.0.y);
self.export_normals.push(normal.0.z);
}
for color in &self.colors {
self.export_colors.push(color.0.x);
self.export_colors.push(color.0.y);
self.export_colors.push(color.0.z);
}
for cell in &self.cells {
self.export_cells.push(cell.a as u32);
self.export_cells.push(cell.b as u32);
self.export_cells.push(cell.c as u32);
}
}
```
And then the wasm `lib.rs`:
```rust
use byteorder::{LittleEndian, WriteBytesExt};
use js_sys::{Array, Float32Array, Uint32Array};
use wasm_bindgen::prelude::*;
use web_sys::console;
mod icosahedron;
#[cfg(feature = "wee_alloc")]
#[global_allocator]
static ALLOC: wee_alloc::WeeAlloc = wee_alloc::WeeAlloc::INIT;
#[wasm_bindgen(start)]
pub fn main_js() -> Result<(), JsValue> {
#[cfg(debug_assertions)]
console_error_panic_hook::set_once();
Ok(())
}
#[wasm_bindgen]
pub struct Hexsphere {
positions: Float32Array,
normals: Float32Array,
colors: Float32Array,
cells: Uint32Array,
}
#[wasm_bindgen]
pub fn shape_data() -> Result<Array, JsValue> {
let radius = 1.0;
let detail = 7;
let mut hexsphere = icosahedron::Polyhedron::new_truncated_isocahedron(radius, detail);
hexsphere.compute_triangle_normals();
let mut unique_hexsphere = icosahedron::Polyhedron::new();
unique_hexsphere.unique_vertices(hexsphere);
unique_hexsphere.assign_random_face_colors();
unique_hexsphere.fill_exports();
let positions = unsafe { Float32Array::view(&unique_hexsphere.export_positions) };
let normals = unsafe { Float32Array::view(&unique_hexsphere.export_normals) };
let colors = unsafe { Float32Array::view(&unique_hexsphere.export_colors) };
let cells = unsafe { Uint32Array::view(&unique_hexsphere.export_cells) };
Ok(Array::of4(&positions, &normals, &colors, &cells))
}
```
With wasm-pack, I could import the wasm package, run the `shape_data()`
function, and then read the contents as any other normal JS array.
```javascript
let rust = import("../pkg/index.js")
rust.then(module => {
const shapeData = module.shape_data()
const shape = {
positions: shapeData[0],
normals: shapeData[1],
colors: shapeData[2],
cells: shapeData[3],
}
...
})
```
I could side-step the issue of transferring data from Rust to JavaScript
entirely by programming literally everything in WebAssembly. But the bindings
from rust wasm to the WebGL API are still way too complicated compared to just
using regl. Plus, I'd have to implement my own camera from scratch.
### The Stats
So how much faster is Rust than JavaScript in generating icosahedrons and
hexspheres?
Here's how long it took with generating shapes in JS with Three.js in Firefox
2020-02-02 00:07:28 +00:00
versus in native Rust with a i5-2500K 3.3 GHz CPU.
| Shape | JS generate time | Rust generate time |
|---|---|---|
| Icosahedron detail 6 | 768 ms | 28.23 ms |
| Icosahedron detail 7 | 4.25 s | 128.81 ms |
| Hexsphere detail 6 | 11.37 s | 403.10 ms |
| Hexsphere detail 7 | 25.49 s | 1.85 s |
So much faster!
### Todo
* Add a process that alters the shape post-generation. Part of the reason why I
decided to fan the hexagon faces with so many triangles is that it also allows
me to control the height of the faces better. This could eventually allow me
to create mountain ranges and river valleys on a hexsphere planet. Stretching
and pulling the edges of the polygon faces in random directions could add
variation and make for a more organic looking hexsphere.
* Conversely, it would be nice to be able to run a process post-generation that
could reduce the number of triangles by tiling the hexagons more efficiently
when face elevation isn't needed.
* Add parameters to the generation that allows generating sections of the
hexsphere / icosahedron. This will be essential for rendering very detailed
polyhedrons since at a certain detail level it becomes impossible to render
the entire shape at once.
In WebGL, figure out what part of the shape is in the current viewport and
pass these parameters to the generation.
* Render the shapes in a native Rust graphics library instead of WebGL. I'm
curious how much slower WebGL is making things.
* Parallelize the generation. Right now the generation is very CPU bound and
each subdivide/truncate iteration is mostly independent from each other, so I
think I could get some decent speed-up by allowing the process to run on
multiple cores. Perhaps the [rayon](https://github.com/rayon-rs/rayon) crate
could make this pretty straightforward.
* Find some way to avoid unique vertices. The size of the shape is *much* bigger
because of this. There might be a way to keep shared vertices while also
having a separate color per face by using texture mapping.
* In the renderer, implement face selection (point and click face and show an
outline around selected face).
* In the renderer, implement fly-to-face zooming: given a face, fly the camera
around the sphere in an orbit and then zoom in on the face.