Perseverance - a history of Manifold

7 minute read.

If I had known it would take this long, would I have started? This is a question I asked myself when looking back at the development of Manifold, and I honestly don't know the answer. Certainly taking on this challenge was born largely of naivety in software engineering, especially when realizing I worked on it for almost eight years before it saw the light of day. 

Why did I take on this project? It started with 3D printing, where I found out that much of the lack of reliability stemmed from models that had non-manifold mesh data. Manifoldness is what allows a mesh to represent a solid, with a clear inside and outside, so without this the computer is left to guess what your intentions are. In many cases there is simply no clear way for an algorithm to proceed when it encounters a non-manifold mesh. 

At first I thought these non-manifold meshes were simply the result of bugs, but while working at Microsoft I got to work with experts from many of the major CAD and manufacturing companies and I learned several key facts. First, the most common 3D format was/is STL, which loses manifoldness information, so just the process of reading and writing a file can break it. I helped craft 3MF to fix this. Second, manifoldness is such a thorny computational geometry problem that the mesh Boolean (how you add or subtract solids from each other) had been considered an open problem for decades in terms of guaranteeing manifold output. Even the top-of-the-line CAD packages that cost $30,000 per seat could not guarantee manifold mesh output.

Imagine if your linear algebra library occasionally gave incorrect results. What if you couldn't trust your processor's floating-point unit? Can you imagine how hobbled development would be? I think this is the situation computational geometry has been in, and I think it explains why so little automation has made it into the design space. We need reliable foundations upon which to build.

I'm originally an aerospace engineer, not a software developer - I was a PM at Microsoft back then in 2013. However I do have a PhD, so I naturally started to review the literature in computational geometry. I found an intriguing dissertation by Julian Smith from 2009 that seemed to have a novel mesh Boolean method that could actually guarantee manifoldness by construction. I became intrigued and decided to see if I could implement it in the only programming language I knew at the time: Matlab. 

This was completely a hobby project, and Microsoft thankfully had a very open moonlighting policy. I worked on it on and off for a couple of years, learning the basics of object-oriented programming (I shudder to think of OOP in Matlab now) and even GPGPU via their parallel toolbox when I realized Smith's algorithm could be parallelized. I got it working, though I realized later my testing was not sufficient to make that claim. 

As I tired of my role at Microsoft, I realized that I was enjoying coding more and more. I pitched my computational geometry ideas to an acquaintance who ran a startup incubator. He said he was interested, but it wasn't clear how long I'd have to go before I got a paycheck - however he had another startup that needed to hire its first engineer for 3D video; would I be interested? I interviewed and was hired, kind of incredibly given my lack of experience. 

That startup was an amazing learning opportunity - I spent the first six months doing lit review and then inventing and patenting a new volumetric video compression codec that leveraged H264. Concurrently I was teaching myself C++, OpenGL, and CUDA, which I did by rewriting my mesh Boolean using these languages. I got a handshake agreement from our founder that I could keep ownership of this code since it wasn't related to our business and it was just a convenient way for me to learn the skills I would need.

I never actually finished rewriting it; the priority was learning the skills so I could start implementing the compression I designed. I continued to poke at it occasionally on my free time, but by then I realized that I had overlooked a serious problem: making a manifold triangulation of a general (possibly degenerate) polygon-with-holes. 

After almost two years when our startup had five engineers, I walked in one day only to be told I was laid off. The reason given was lack of funding and that I would be better off in a research role somewhere anyway. I'll admit that I took it pretty personally, considering I was singled out and there was no warning. When I asked to take my mesh Boolean code with me, they said I could license it from them. I learned then not to trust founders and to always get agreements in writing. 

While I was unemployed I decided to start over on my implementation. They may have stolen my code, but it didn't produce any useful output yet anyway. Also, it was literally the first piece of C++ I ever wrote, and I can only imagine how hideous it would look if I saw it again. I had learned a lot about code structure since then, so it was actually for the best that I had to rewrite it again from scratch. 

When I joined Google I got IARC approval for it, meaning I owned the copyright. I had decided I wanted nothing to do with making it a business, so I put it up on Github under an open-source license, figuring that would be its best chance of gaining adoption someday. However I did not publicize it, so it remained effectively invisible. 

As hard as it was to keep my motivation up to work on it alone each night after my kids went to bed, I was afraid to publicize it. I still had pretty serious imposter syndrome as a software engineer and there are actually a lot of open source mesh Boolean libraries out there. The only thing that made mine special was this manifoldness guarantee, but by now I had good enough testing to realize it wasn't yet working. I was afraid if I put it out there someone might try to rely on it and I would waste their time, since I hadn't yet proven to myself that what I was claiming was actually possible. 

I occasionally lost the motivation battle - there were six-month stretches where I didn't touch it, demoralized by realizing some foundational assumption was wrong and unsure how to proceed. Sometimes I would have an inspiration about a new approach, only to find myself terrified to implement it for fear that it would fail in practice, when it looked so good in my head. And this was no idle concern - it was born out many times. 

I wrote, rewrote, and refactored the code so many times it's hard to keep track. I went from triangles internally to polygons, then back to triangles. I built a decimator to keep the level of degeneracy manageable. The triangulator took the most time - as much as I never had much trouble with Julian Smith's guarantee, I eventually realized how critical this post process was that he glossed over in the paper. Due to the inexact input, it had different requirements than any other triangulator I could find.

Finally I succeeded at making the triangulator handle even highly complex degenerate cases, and also fall back gracefully for geometrically invalid input in such a way that manifoldness of the result was always guaranteed. I had at this point some very challenging test cases, including a fourth-order Menger Sponge that creates an avalanche of degeneracies. When everything passed the tests reliably, I finally decided to release v1.0 and tell people about it.

When I started to engage with the open source community, I quickly wished I'd done so earlier. Pretty soon developers started testing it out and giving constructive feedback. But critically, I found a contributor who started improving the library, particularly its performance and helped it to build on more systems. Having others contributing was so motivating! And it was so valuable because they have expertise I lack. Now we have contributions coming in from a variety of sources and projects have actually taken a dependency on us. 

One truly amazing thing about open source is how quickly things can come together. One person got Manifold building in WASM so it could work in a browser. Another mentioned that Microsoft's VSCode editor, Monaco, was open-source and web-based, and with that we could make our own web app akin to OpenSCAD. The final piece was the open-source 3D viewer I work on in my 80% time, <model-viewer>, and with these building blocks a web app was born in a mere month: ManifoldCAD.org.

It was around this time I discovered that 20-percenting at Google is not, in fact, dead. I registered Manifold as my official 20% project, finally allowing me to spend a workday per week on it. This concept is so brilliant, particularly for my personality. The usual concern is that I'll only be an 80% employee at my job now, but that completely discounts the concept of motivation. In fact I found myself more productive than ever due to the added intellectual stimulation and excitement. My career has been a series of ~3-year stints at different companies in different fields. The fact that I'm happily working in my fifth year at Google is in no small part due to this 20% flexibility. 

This week I reached a huge personal milestone: OpenSCAD merged Manifold in as a dependency. OpenSCAD made me fall in love with CAD, led to my brief internet stardom, and in no small part inspired me to create Manifold. I always wanted to give back to that community and now I finally have, in the form of reliable output that also happens to be orders of magnitude faster.

Where does Manifold go from here? Of course we'll follow our users, as any good project does. I'll continue to write geometric algorithms that fit into this guaranteed-manifold framework. And hopefully it will continue to grow as more developers get interested in the space of 3D design. All I can say is, I'm certainly glad now that I started this project! For all the years it took, it led me to become a software engineer and to learn so much and to meet a community of like-minded people.