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

<p>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. <a href="http://geomalgorithms.com/a06-_intersect-2.html" rel="nofollow noreferrer">Heres some math</a>.</p>

<p>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 <a href="https://en.wikipedia.org/wiki/Polygon_triangulation" rel="nofollow noreferrer">polygon triangulation</a></p>

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

<p>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 <em>n</em> log <em>n</em>. </p>

<p>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 <a href="https://computergraphics.stackexchange.com/questions/2208/model-separation-several-models-reside-in-a-single-stl-file/2209#2209">this post</a></p>

CC BY-SA 3.0
2016-03-28T09:55:53.623Z
2016-03-28T09:55:53.623Z
2017-04-13T13:00:43.660Z
joojaa
<p>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.</p>

<p>The utility looks like this:
<a href="https://i.sstatic.net/N3VXd.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/N3VXd.png" alt="3D Builder"></a></p>

<p>In particular, they have triangle mesh functions there that:</p>

<ul>
<li>"Detect" when a mesh is not suitable for 3D printing;</li>
<li>"Repair" so that the mesh isn't right it prepares it, by removing internal faces, closing "holes" in the outer surface, etc.;</li>
<li>"Simplify" by removing redundant triangles, such as those found to be adjacent and co-planar; and</li>
<li>"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".</li>
</ul>

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

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

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

<p>In the builder the functions look like this:</p>

<p>Simplify (the tractor top and sides have fewer facets):</p>

<p><a href="https://i.sstatic.net/qAAr2.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/qAAr2.png" alt="Simplify Output"></a></p>

<p>Slice, UI before processing:</p>

<p><a href="https://i.sstatic.net/GYHQV.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/GYHQV.png" alt="Slice, UI before processing"></a></p>

<p>Slice, after processing and then one "Simplify" pass:</p>

<p><a href="https://i.sstatic.net/PDt95.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/PDt95.png" alt="Slice, after processing"></a></p>

CC BY-SA 3.0
2016-03-24T05:33:11.800Z
This is (too) many questions rolled into one. Should it possibly be split up?
joojaa
CC BY-SA 3.0
2016-03-25T01:28:16.253Z
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.)
Rob Perkins
CC BY-SA 4.0
2019-08-19T13:58:44.780Z
You might be interested in this book: http://www.pmp-book.org/
Ryan
<algorithm><3d><mesh><computational-geometry>
Which 3D algorithms does Windows 10's "3D Builder" application use?
Rob Perkins
# Which 3D algorithms does Windows 10's "3D Builder" application use?

(Asked by: username_0 on 2016-03-24)

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](https://i.sstatic.net/N3VXd.png)](https://i.sstatic.net/N3VXd.png)

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](https://i.sstatic.net/qAAr2.png)](https://i.sstatic.net/qAAr2.png)

Slice, UI before processing:

[![Slice, UI before processing](https://i.sstatic.net/GYHQV.png)](https://i.sstatic.net/GYHQV.png)

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

[![Slice, after processing](https://i.sstatic.net/PDt95.png)](https://i.sstatic.net/PDt95.png)

**Tags:** algorithm, 3d, mesh, computational-geometry

> **Comments:**
> **username_1**: This is (too) many questions rolled into one. Should it possibly be split up?  
> **username_0**: 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.)  
> **username_2**: You might be interested in this book: http://www.pmp-book.org/  

---

## 1 answers

### Answer by username_1 on 2016-03-28. Score: 1 | Accepted answer

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](http://geomalgorithms.com/a06-_intersect-2.html).

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](https://en.wikipedia.org/wiki/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](https://computergraphics.stackexchange.com/questions/2208/model-separation-several-models-reside-in-a-single-stl-file/2209#2209)


---

