# An Accelerated Slicing Algorithm for Frep Models
## 2 Materials and Methods
### Microstructure Modelling  
The FRep-based approach offers a broad set of tools for 3D modelling complex shapes. In [8], trigonometric functions and R-functions were used for modelling infinite lattices. Trigonometric functions or triply periodic minimal surfaces (TPMSs) [9] can be used together with space mapping or metamorphosis operations [4] to increase the complexity of non-uniform lattices. The use of the bounded blending operation [10] in FRep allows the controlling of material addition and subtraction within certain regions of a 3D model with the help of a single operation. For example, this helps to increase the rigidity of certain sections in a 3D model [11]. A commonly used tool for microstructure construction in FRep is unit cell repetition. This approach allows for the construction of a basic 3D unit cell using a skeleton-based modelling technique combined with the distance field tool [12] and the replication of the cell throughout the modelling domain with the space mapping and looping tools. The repetition of the unit cell with the space mapping tool is a computationally inexpensive operation, but it is subject to certain limitations. For example, it is difficult to control the boundary shape of the target 3D model. Additionally, there are requirements for the symmetry of the unit cell. Such restrictions were studied for non-symmetric cell repetition with the sawtooth wave function [13] and for symmetric cell repetition using the triangle wave function [14] in [15]. The replication of the unit cell via the loop operation is free of the limitations associated with the space mapping operation. The proposed algorithm is convenient for objects that cannot be modelled by the space mapping as shown in [15]. Loop operation is used in traditional BRep-based and FRep-based CAD systems. Users usually call this operation copying modelled objects and creating arrays. Loop operations are represented by \"for\" and \"while\" loops operators in modelling systems based on scripts. This operation is equally suitable for modelling complex 3D structures and free-form shapes. However, this method is computationally expensive, due to the need to process every unit cell individually within the volume. Several adaptive criteria can be applied to reduce the computational burden in FRep, that is, interval arithmetic [16], affine arithmetic [17], extended revised affine arithmetic [18] criteria, but these adaptive criteria demonstrate low efficiency in accelerating loop operations [19]. Traditionally, the polygonization and slicing of FRep models employs adaptive space subdivision algorithms featuring octree or quadtree data structures [20]. However, the application of these algorithms to FRep models that can be represented by Equation (2) may take much time because the loop operation is internally applied for model construction. Acceleration of these processes for FRep models can be achieved via computation of only a part of the defining function evaluation around the point of interest in the space. This replacement may lead to losing the function continuity, but it does not influence the constructions of sliced 2D contours during the slicing process. Such selective computation of the FRep model at the point of interest requires defining 3D model parts, which significantly influence its resulting shape. To control the process of 3D model decomposition, B-trees can be employed. B-trees assign a spatial index to each part of the 3D model. The indexes can be adapted to the scene geometry. It allowing the proper arrangement of 3D model elements and enabling fast access to, insertion of or removal of particular elements to/from the B-tree. Spatial indexes such as K-d trees, R-trees or bounding volume hierarchies are broadly used in 3D graphics, in particular, in ray-tracing algorithms [21]. In [22], a K-d tree is used as an acceleration structure of the ray-tracing algorithm on a GPU. In [23], a K-d tree is used for surface reconstruction from a point cloud.