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...