Logo sketches: Shard

My logo already uses forced perspective to create an illusion, so why not really force it a little harder? Shard splits polygons at random vertices and carefully hurls them in front of a camera where they appear like the original. That is... until you put a spin on them!

Randomizing the z dimension without changing the image is pretty simple at its core. In the orthographic case, the projection just grabs a ray from a point in the scene, through the screen, to the "focal point" of the camera, and draws it where it hit the screen. Then, any points along that ray will map to the same screen point, so moving a geometry's vertices along these rays won't change the image. Note that the vertices can be moved independently and it's totally still okay:

Right now, the viewer sits 100x farther from the object than the object is wide, with the screen sandwiched in between. This is a fairly silly setup, and suggests that I should really instead use an isometric projection which is the limit of the orthographic projection when the viewer vanishes to infinity away from the screen.

The orthographic projection was a hangover from the initial setup to keep the setup general and tune to find what was visually appealing. I found myself nudging towards isometric because the best visual effects came when the range in z was comparable to the width of the screen, so the angle of the frustrum needed to shrink so the subject could maintain its distance from the screen without getting too small. Trying a distribution that pushed far into the negative z axis looks off-balance (↓).

↑ Notice also the parallax that's hallmark of orthographic, which looks pretty mediocre, so all the more power to isometric.

Despite the simplicity of its premise, there were some interesting considerations along the way. I have my favorites, which I'll discuss here:

How can we generalize to sharding graphs instead of polygons? For example, this very convenient geometry I'll scoop up here has many non-overlapping polygon/polyline decompositions:

Note in the above: the shapes highlighted in red can't be formed by decompositions of the shapes in the other. Therefore, when we make up a geometry like that with polygons and polylines — whatever can be with a Pen tool — we have to be opinionated.
Is a 3D engine overkill?

Graph partitioning

Great, we want to break our graphs at the joints, reassemble the tattered limbs and puppet them around! Hold on... our macabre aspirations our dependent on our ability to actually reassemble our graph's corpse. 2D Canvas primitives can only draw open and closed paths, which critically are graphs of max degree 2. We're in the territory of a constrained graph partitioning problem, which if we weren't careful could suddenly get very NP-hard. Canonically, we might demand that our polygons be of similar size for example. However, the crucial difference is optimization: for this purpose we actually want to be as unopinionated as possible so long as the resulting partition is drawable with polylines. We can actually be greedy!

Let's specify a bit more. Worth noting that this is not a graph partition as it's often defined in terms of vertices, because two daughter paths will both receive the vertices that their edges share.

The difference however is just a bit of extra housekeeping on cut edges, since the whole point is to keep them in the projection!

Suppose we go a vertex and try to pair incident edges at random and terminate others. Let $n$ be the degree of this vertex of ours. We can produce every unique possibility locally pretty easily:
1. We can choose a random number of pairs $p$ uniformly from 0 to $\lfloor n/2 \rfloor$
2. We then shuffle the edge list and pair the first $p$ edges with the next $p$
3. The remaining $n-2p$ edges mark the end (or start, if you're an optimist!) of their respective paths at our vertex.
Note that since we don't delete or reroute the edges, the decisions at every vertex are totally independent! So long as we maintain the adjacencies we're creating in the daughters paths, we can iterate through the vertices exactly once and finish this in $\mathcal{O}(VE)$. Not shabby.

There is a caveat, since different numbers of pairs we choose have differing amounts of redundancy. Reveal the aside to see the derivation of an approximate proper weighting.

We can split the redundancy into two terms relating to the edge pairs and the leftover singles:

$p$ random but numbered pairs of shuffled edges have $2^p(p!)$ identical configurations: $2^p$ because each pair is symmetric; $p!$ because once paired, the pairs can be shuffled without any effect.
$n-p$ random singles are already totally defined once they've been identified, so their $(n-p)!$ shuffles are identical configurations.

Overall, of $n!$ unique shuffles of numered edges, there are $C = \frac{n!}{2^p(p!)(n-2p)!}$ unique configurations. Using Stirling's approximation $\ln n!\approx n\ln n - n$, we can see how the size changes for constant large $n$ and changing $p$:

$$ \ln C\approx (n\ln n - n) - p\ln2 - (p\ln p - p) - ((n-2p)\ln(n-2p) - (n-2p)) $$

Starting with $2p < n$, note that $C$ rises exponentially with p:

$$ \ln C\approx n\ln n + p(1 - \ln 2p) - (n-2p)\ln(n-2p)\\ = n(\ln\left(\frac{n}{n-2p}\right) + p(1 + \ln\left(\frac{n-2p}{2p}\right))\\ \frac{\partial \ln C}{\partial p} \approx 2\ln(\frac{n}{2p}-1)+\frac{7n}{2(n-2p)}+2 > 0 $$

With a special case of all edges being paired, which is a much more straightforward $\frac{(2p)!}{2(p!)} \approx \exp(n-p)\frac{n-1}{2(p-1)}$:

The unnormalized weight of each number of pairs $p$:

$$ W_p \approx \begin{cases} \exp\left[n\ln\left(\frac{n}{n-2p}\right) + p\left(1 + \ln\left(\frac{n-2p}{2p}\right)\right)\right] & 0 \le p < \lfloor\frac{n}{2}\rfloor\\ \exp(n-p)\frac{n-1}{2(p-1)} & p = \lfloor\frac{n}{2}\rfloor \end{cases} $$

Cooking up a camera


V1, with THREE.js and default pixel density	V2, with DIY camera in 2D canvas and built-in pixel density

Since this project is just drawing lines, it seemed a bit silly to invoke a full 3D graphics pipeline really just to do the math of the camera projection. On the left in the above figure is the first attempt using THREE.js that ran my site for a while. Three.JS minified still weighs 430KB, and added with the curiosity about performance of an opinionated rendering engine, I implemented my own which runs currently on the site.

The camera sits at a fixed position offset along the z axis facing the origin.
The camera uses a raytracer on only vertices to project the endpoints of edges onto the screen.
Moving the mouse updates a global target rotation. A global rotation state tracks the target with a P controller and rotates all the objects in the world around the origin. (See figure below)

GitHub: acrylic-origami/shard