Decomposition of 3D model for 3D printing

3D tiskalniki za domačo uporabo imajo omejeno delovno prostornino, zato je treba prevelike 3D modele razrezati na več delov, da jih lahko natisnemo ločeno. Cilj diplomske naloge je razviti programsko rešitev, ki omogoča razrez 3D modela na poljubno majhne dele. Rešitev naj bo preprosta za uporabo ter uporablja ustrezne algoritemske rešitve. 3D model je tipično definiran z množico trikotnikov, ki opisujejo njegovo površino. Razrez 3D modela poteka v več korakih. Najprej je treba razrezati obstoječe trikotnike ter iz njih sestaviti mnogokotnike na rezu. Za podporo pri triangulaciji površine mnogokotnika na robu smo implementirali algoritem za razvrščanje mnogokotnikov v hierarhično drevo ter algoritem za združevanje mnogokotnika z njegovimi luknjami. Samo triangulacijo mnogokotnikov smo implementirali z Ear clipping algoritmom. Programsko rešitev smo razvili v programskem jeziku Python z uporabniškim vmesnikom, ki deluje iz ukazne vrstice. Po prikazu delovanja programske rešitve smo opravili tudi meritev in analizo časovne zahtevnosti posameznih korakov rezanja 3D modela. Ta je pokazala, da je triangulacija mnogokotnikov časovno najbolj zahteven korak v programu, saj čas izvajanja triangulacije z Ear clipping algoritmom narašča eksponentno z ločljivostjo 3D modela. Ne glede na to, se programska rešitev v praksi dobro obnese, če 3D model ni prezahteven.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