Mesh reduction is well known. You have some algorithm for removing faces and vertices while trying to maintain something close to the original shape. This usually doesn't work well if you push it too hard and try for an extreme low-poly version of the mesh.

Has anyone ever looked at this from the other direction? Suppose you take a mesh and enclose it in a bounding box. That's the ultimate "low poly" version. Then you use a simple cutting object, such as a cube or a tetrahedron or a plane, to cut off part of the bounding box. Pick the cut that will remove the most excess volume. Repeat until some error criterion is reached.

Here's the general idea, in 2D. We take the black design and surround it with a red bounding box. Then we clip off sections of the red area, as shown by the blue outlines. The next cut should be the one that removes the most red without removing any black. Here, two cuts would get us roughly the house shape. Enough cuts would get you the original object, but you stop long before that point.

Somebody must have tried this; it's kind of obvious. But I've never seen it done.

This is called CSG https://de.wikipedia.org/wiki/Constructive_Solid_Geometry mostly available as 'boolean' mesh operations (union, difference, add, sub) in 3D modeling tools. I think CGAL and lib igl have open source implementations. It is known to be very hard to make robust.

An easier way is to use distance fields (or voxels), like seen in the PS4 game Dreams for user generated content.

Unrelated: I would say more likely the 'reverse' of simplification is 'remeshing', which often aims to reconstruct the surface with regular high res triangles or quads (see the Instant Meshes Tool for example: https://github.com/wjakob/instant-meshes)

I don't see how your algorithm would do anything besides calculate the convex hull eventually?

2 minutes ago, Randy Gaul said:

I don't see how your algorithm would do anything besides calculate the convex hull eventually?

You don't let it go for that many iterations. The idea is to make only a few cuts and get a rough approximation to the object.

Oh, now i get it: You want to make a reduced mesh, not the final house...

But i agree using just planes you would end up with convex hull, more accurate at each step but still convex, so not always a usable result for any shape. (Think of a 'L' shape)

So you would need more complex cutoff shapes, and perform CSG. Automatic calculation of those cutoffs would be harder than CSG itself. Really any existing decimation algorithm is surely better than this i think.

Yes. I'd allow cutting objects up to 6 faces, like a cube. For an L-shaped object, you'd cut with a rectangular solid and get close to an L with one cut.

Doing the cuts is a CSG problem, of course. Deciding where to cut is the hard part. The metric is, make the cut that removes the most unwanted material.

Think of this as a way to make impostor objects. Start with a chair model, enclose it in a bounding box. Make one cut with a cube and you're pretty much done. Then texture map onto the impostor.

Never seen this approach used, and I've done some literature searches. It's kind of obvious, and you'd think someone would have tried this.

There is lots of research about surface segmentation. On method uses quadratic fitting to find pieces of surfaces that form a sphere, or a cylinder, plane... or a cube. It would work to find your cuts, but it really is the hardest route towards simplification i can imagine, and mapping surface data like textures also isn't that easy.

I currently work on a form of simplification too, i need to approximate the surface with only quads, and they should be large and equally sized. See picture for result on Stanford bunny.

What are your goals? 

Why do existing methods like error metrics do not fit your needs? (e.g. https://people.eecs.berkeley.edu/~jrs/meshpapers/GarlandHeckbert2.pdf)

I really have learned how to waste time on this, maybe i can help you to avoid that

It's important to understand what you want to accomplish, in order to find (as JoeJ already noted) applicable quality criteria for the algorithm.

This simplification by cutting has major self-imposed handicaps (for instance, it cannot move vertices) so it's hard to see it competing with generic simplified meshes or billboards for LOD purposes and with traditional algorithms to obtain a good approximation of a high-poly mesh automatically. What is the intended niche in which it makes something look good? Are you going to animate the cutting progress, e.g. to show carving of objects from blocks?