The Shape of Things to Come

4 minute read. My Manifold library operates on triangle meshes because they are a lowest common denominator representation of a solid that all others, from NURBS to SDFs, can be converted into. However, it can take a huge number of flat facets to adequately approximate the smooth curves of these other representations, particularly in manufacturing where graphics cheats like Phong shading are not available. Therefore, it would be convenient to be able to smoothly interpolate a triangle mesh so that fewer triangles could adequately approximate the desired curved surface. I have devised such a method which I will describe here, but first, a little background. When I was working on the 3MF spec (3D manufacturing format), we were trying to avoid the pitfalls of AMF (additive manufacturing format), one of which was curved triangles. The idea was that faceted meshes could be refined to a smooth shape by interpolating each triangle's corner vertices and normal vectors; the problem w...

7 minute read. I recently published my Manifold library , which does operations on solids, specifically those represented by triangle meshes. But there are many ways to represent a solid object in a computer, so why did I choose this one? I thought it might be useful to give an overview of some of the popular data structures and what they are well- and poorly-suited to. Of course this is also my opinion and I have limited experience with many of these, so please comment if you know something I don't.  Categorization is always a bit tricky and arbitrary, but I feel like the highest-level split is between boundary representations (B-Reps) and signed distance functions (SDFs). I'll sub-categorize below each of these. Signed Distance Functions (SDFs) Though less common, the SDF is in some ways the simpler idea. It explicitly represents a solid: in its simplest form it is a function that takes any point in 3D space and returns if that point is inside or outside of the solid. To make...

4 minute read. The primary purpose of my Manifold library is topologically-robust results, as I've already discussed . My secondary purpose is to make it fast by leveraging the power of parallel processing. There is still significant work that can be done to improve performance, but I'm proud enough of its current state to show some benchmark comparisons.  How to benchmark? It would be nice to show some kind of big-O trend, but different shapes have wildly different results: if we take n to be the number of triangles in each input shape, the number of intersections could be anywhere from zero to n 2 , which will directly affect the processing time. The Menger sponge is an example that scales close to  n 2 , but that is not common. If you think of the progression of  n  as a refinement function, subdividing the triangles into smaller ones, then you would generally expect to have O( n 1/2 ) intersections since the surface is 2-dimensional while the intersection cu...

3 minute read. Manifold is my computational geometry library - the beginnings of a CAD kernel of sorts. Its purpose is fast, reliable, topologically-sound operations on manifold triangle meshes. Reliability is really the key: I started this library because I was amazed at how unreliable the geometry kernels I had experienced (even high-end CAD) were in generating manifold - basically solid - output. The lack of reliability stems from the fact that Euclidean geometry is based on real numbers, but computers work in finite precision with rounding errors. This means it is entirely possible for a computer to find two points to be on the same side of a line, but their midpoint to be on the opposite side: Euclidean geometry does not hold.  For this reason, many computational geometry libraries are proven correct for "general position" input, which means geometry where nothing is within rounding error of coincident, co-linear, or co-planar. This might be okay if the geometry were...

The cabin I was born in. I grew up in the sticks, on a tiny island in the Puget Sound. My parents moved there in the '70s as back-to-the-land hippies and built the log cabin my mom still lives in (I wrote about my late father here ). I had it easy with power and running water by the time I was born; my siblings had ten years without. But there are some funny things about the country, as illustrated all too well by an article entirely too close to home: The True Story of the Antifa Invasion of Forks, Washington . It's a long read, but I highly recommend it; while I don't know any of the people referenced, I feel like I could have. It's a good portrait of a world far outside the urban bubble.  Now, my town was actually closer to Port Townsend, a tourist metropolis of about 8,000 people that served as my bright, shining lights. Port Townsend probably has more artists per capita than anywhere in the state and has attracted hippies like my parents for decades, so it's qu...

As a software engineer working on graphics I’ve drifted a pretty long way from my original specialty, aerospace controls. I’m glad I got my PhD in controls though, because it taught me a unique way to approach problem solving, one which I tend to apply well beyond the traditional realm of controls. Controls is a very math-heavy discipline, focused on proofs and guarantees of safety because in many situations lives depend on the reliability of the system: autopilots come to mind, but there are countless examples in many fields. At its core is uncertainty and the management thereof. The first thing we’re taught when modeling systems is that our models are inevitably wrong, and not by a little: nothing is linear, nothing is rigid, nothing is independent of the world around it. These assumptions make our math tractable, but they are not realistic. And yet, all is not lost: we take our terrible models and our unreliable sensors and we bound their uncertainty. No matter how poor the input is...

My boss and I had a career conversation where he asked about what motivates me. I realized it’s not really money, as I’m already so far beyond the financial position I grew up in. I eventually had to admit, to myself mostly, that I’m actually motivated by fame, or more generally by being respected in my field. The funny thing is that I am almost certainly well past my high-water mark as far as fame is concerned.  I achieved my modest internet stardom through an unexpected avenue: 3D printing design. I discovered 3D printing through my first job which sent me to a UAV conference (back before everyone called them drones) and I saw a printed radio controlled samara (one wing helicopter) that some college students had designed. They crashed and broke it, then went over to the Stratasys booth with a thumb drive and had them print a replacement. They were back flying the next day. My coworker mentioned that a new company called Makerbot was selling a kit to build your own 3D printer for...