Typical consumer level 3D printers have a limited build volume, so 3D models
that are too big need to be divided into several smaller pieces that can be
printed separately. The goal of this thesis is to develop a program for cutting
3D models into several smaller segments. The idea is to find a simple yet
effective solution which is built with suitable algorithmic solutions.
A 3D model is typically defined with a set of triangles that describe its
surface. Cutting a 3D model is performed in several different steps. We begin
by developing a procedure for cutting the existing triangles, and use them
to construct polygons by connecting the edges. To support triangulation of
polygons with holes we implemented an algorithm for sorting polygons into
a hierarchical tree and an algorithm for merging polygons with its holes.
Next we implemented an Ear clipping algorithm for polygon triangulation.
The program was developed in the Python programming language with a
command line interface.
After presenting how our solution works we performed measurements and
an analysis of time complexity for the separate steps. The anaylsis showed
that the polygon triangulation is the most time consuming step in the program,
and that the execution of triangulation using Ear clipping rises exponentialy
wih the resolution of the 3D model. Nevertheless the solution
performs well if the 3D model is of moderate complexity.
|
