# An Accelerated Slicing Algorithm for Frep Models
## 3 An Accelerated Slicing Algorithm  
The slicing process is an essential part of additive manufacturing as well as the direct manufacturing method. The method of direct manufacturing [38] for 3D printing was developed for BRep CAD systems. Moreover, the direct manufacturing algorithm was implemented for row 3D scan data [39]. This method for AM was implemented for FRep in the FRepCAM software [19]. The slicing process obtains 2D contours of the model on each level along the Z-axis (Figure 1). A construction of the 2D contours of a FRep model is localization of the areas where \(f(x,y,z)=0\). The typical slicing algorithm for the FRep models consists of the quadtree construction and the marching squares (MS) algorithm [40] with the adaptive criteria. The MS algorithm is used to construct the contour topology, quadtrees and adaptive criteria are used to speed up calculations. The quadtree is built from the root node, which is the bounding box of the implicit curve. Then, it is divided into four equal regions, which form the child nodes. Every child node can be recursively divided further. The process of contour extraction using the quadtree for one Z-layer is shown in Figure (Figure 2a). The contouring process requires to calculate the value of the defining function of FRep model at very large number of points. An adaptive subdivision is used for decreasing the number of calculations of the defining function by localize the areas (cells of quadtree) which contains implicit curve. Adaptive subdivision can employ an interval [41; 42] or affine arithmetic [17] as common adaptive criteria [16], which allows you to evaluate the upper and lower bounds of the range of values of the defining function for each cell of the quadtree and decide whether to split the cell or not. In interval arithmetic, every quantity is represented by an interval of real numbers. An interval \([a,b]\) is a set of \(x\in\mathbb{R}\) such that \(a\leq x\leq b\). During functions processing in interval arithmetic, each quantity is replaced by its interval extension, and all computations are executed on intervals. If the upper and lower bounds of the interval are on opposite sides of zero, this means that the processed quadtree cell contains contours of the curve and should be divided. In most cases, slicing FRep models constructed using the loop operation is often a computationally complex task. There are two main problems with 2D contour extraction from FRep models equipped with the loop operation. The first problem is that common adaptive criteria (interval, affine or revised affine arithmetic) do not work properly with such models due to interval overestimations. The intervals of values of the defining function becomes wide, and the algorithm divides all the cells of the quadtree without adaptivity. The second problem is the slow performance of the loop operation. Figure 1: Slicing of the FRep model allows obtaining 2D contours within each layer along the Z-axis. Figure 2: The contour extraction process for one layer of the FRep model: (**a**) building a quadtree, (**b**) contouring of one layer using the quadtree. The proposed solution to both problems is to use an acceleration method based on the spatial indexes. We present the accelerated slicing algorithm, which uses this technique. The accelerated slicing algorithm for FRep models satisfying Equation (2) contains the following steps:  
1. Cutting the 3D model into layers with a certain step. 2. Contouring each layer. 3. Post-processing the obtained contours with support and hatching building. 4. Generating the operating program for a certain 3D printer. An acceleration of the proposed slicing algorithm is reached by applying the specific contouring algorithm, which consists of the following steps:  
1. Constructing the 2D bounding boxes \(B_{i}=(X_{1},X_{2},\ldots,X_{n})_{i},i=\overline{1,m}\) for all the unit cells \(u(x_{1},x_{2},\ldots,x_{n})\) of the FRep model (Figure 3a red rectangles). 2.