# An Accelerated Slicing Algorithm for Frep Models
## 1 Introduction
All objects in the FRep are defined by a real valued continuous function  
\[f(x_{1},x_{2},\ldots,x_{n}) \tag{1}\]  
where \(x_{1},x_{2},\ldots,x_{n}\) are coordinates in n-dimensional space. By design, these functions are positive at the internal points of the modelled 3D object, zero at its boundary points and negative at the external points. Both BRep and FRep models should be sliced prior to their use in additive manufacturing. The BRep approach utilizes STL files as the intermediate layer between a CAD model and the slicing software. The FRep approach offers an advantage by directly slicing the 3D models with no STL conversion or other unnecessary meshing. This process takes a significant amount of computational time for models featuring complex geometry. The complex geometry of FRep models is discussed in this paper as a microstructure built via the replication of unit cells. The defining function of such FRep models can be described by the following statement:  
\[f(x_{1},x_{2},\ldots,x_{n},g(x_{1},x_{2},\ldots,x_{n})) \tag{2}\]  
In this equation, \(g(x_{1},x_{2},\ldots,x_{n})\) defines a feature of the initial model that can be represented by:  
\[g(x_{1},x_{2},\ldots,x_{n})=\gamma[u(x_{1},x_{2},\ldots,x_{n})]. \tag{3}\]  
where \(u(x_{1},x_{2},\ldots,x_{n})\) defines a basis object, which is replicated over the modelling domain and is generally transformed by the operation \(\gamma\). Further, we will call \(u(x_{1},x_{2},\ldots,x_{n})\) a unit cell function or just a unit cell. For the operator \(\gamma\) a function \(\Gamma\) with the following properties should exist. The function \(\Gamma\) defines a sequence \(B_{i}=(X_{1},X_{2},\ldots,X_{n})_{i},i=\overline{1,m}\) of bounding boxes for all replicated and transformed \(u(x_{1},x_{2},\ldots,x_{n})\) inside the considered domain. \(X_{1},X_{2},\ldots,X_{n}\) are intervals along coordinate axes, which define the bounding boxes. The bounding boxes must not overlap, hence: \(B_{i}\bigcap B_{j}=\varnothing\) for any \(i,j=\overline{1,m},i\
eq j\). The consideration of unit cells with an L-shape is beyond the scope of this paper. In this paper we propose an accelerated slicing algorithm for the such FRep models satisfying Equation (2). The algorithm applies a new compound adaptive criterion and a new acceleration criterion. The criteria are based on binary search trees (B-trees) such as K-dimensional (K-d) trees and R-trees. The resultant structures, called spatial indexes, allow for the significant acceleration of the slicing process. The details of the slicing algorithm will be described below. Examples of its usage are provided for two special cases (Case study 1 and Case study 2). The performance of the accelerated slicing algorithm was tested. The contributions of this work are the following:  
1. A novel compound adaptive criterion for contour construction during the slicing of FRep models satisfying Equation (2) is presented. It localizes an FRep surface in 3D space, thereby reducing the number of processed cells during the implementation of the contouring method. 2. A novel acceleration criterion for contour construction during the slicing of FRep models satisfying Equation (2) is presented. It allows the replacement of the loop operation by the spatial search operation and reduces the number of iterations needed during the computation of the defining function of the FRep model. 3. An accelerated slicing algorithm for FRep models satisfying Equation (2) is presented. It is used for obtaining 2D contours in each sliced layer of FRep models with complex geometries based on the repetition of a unit cell satisfying Equation (2). The algorithm is built into the CAM system for FRep models and reduces the time needed for slicing by applying the novel compound adaptive criterion and the novel acceleration criterion.