1
$\begingroup$

Windows 10 ships with "3D Builder", a Universal App that contains utility functions to prepare STL, OBJ, 3DS, and other files that represent geometries for 3D printing.

The utility looks like this: 3D Builder

In particular, they have triangle mesh functions there that:

  • "Detect" when a mesh is not suitable for 3D printing;
  • "Repair" so that the mesh isn't right it prepares it, by removing internal faces, closing "holes" in the outer surface, etc.;
  • "Simplify" by removing redundant triangles, such as those found to be adjacent and co-planar; and
  • "Plane Cut", slicing a mesh through an arbitrarily positioned plane and filling in a surface on that plane to re-enclose the geometry, sometimes followed by a "Detect" and "Repair".

Every copy of Windows 8.1 and 10 has this utility at no additional cost. That says to me that the functions are well-known and as far as I've been able to test, reliable for virtually all inputs to the 3D printing use case. I used some of the messiest STL files I could find to prove this thing.

Which algorithms did they use for those functions? Where are they found for a .NET/WPF/UWP environment?

More to the point, did they expose the functions in an API I can use for a slightly dissimilar use case?

In the builder the functions look like this:

Simplify (the tractor top and sides have fewer facets):

Simplify Output

Slice, UI before processing:

Slice, UI before processing

Slice, after processing and then one "Simplify" pass:

Slice, after processing

$\endgroup$
  • $\begingroup$ This is (too) many questions rolled into one. Should it possibly be split up? $\endgroup$ – joojaa Mar 24 '16 at 5:33
  • $\begingroup$ They are all algorithms which apply to the same topic in computational geometry, specifically, computation concerning non-convex enclosed polyhedrons. (Thank you, @nathan-reed, for adding that tag.) $\endgroup$ – Rob Perkins Mar 25 '16 at 1:28
1
$\begingroup$

Well obviously nobody except the makers of this program can answer the exact algorithms used. I have done a quick explanation on each. Each separate task really deserves its own question and answer.

Just iterate each polygon, for each vertex check if all of them are above the cut line eliminate the face. To make this check easy you can transom each vertex to the plane orientation. If not all vertices are above the cut line then the triangle is split along one of the edge that has a eliminated vertex. Then use the internal face closing algorithm. Heres some math.

Face closing algorithm works by finding open edges and then tessellating the new polygon closed. Please note: That this produces somewhat erratic results if the open holes are not planar. See polygon triangulation

Simplifying planar regions is basically the same face closing algorithm except they you first build up polygons out of regions. Also decimation might come to play. There is a lot of lore, and different algorithms for simplification and going trough all of it its way too bread for a post like this.

Self intersection is a sorting problem. Quite a bit of lore on this exists too. The one that i mostly do is putting the polygons one by one into a BSP self organizing tree and checking against polygons against items in that tree to reduce the check complexity to n log n.

Internal cavities can be detected by splitting each mesh into shells and then for each shell check if the other shell is contained within each other. See this post

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.