CN111186139B - Multi-level parallel slicing method for 3D printing model - Google Patents

Abstract

The invention relates to a multi-level parallel slicing method for a 3D printing model. The method accelerates the slicing of a three-dimensional model by means of multi-level parallel processing, and specifically includes four levels of slicing parallelization, which are computing node level and multi-GPU level respectively. , thread block level and thread level. In each level of parallelization, according to the address space distribution, memory access method and data structure characteristics of the current level, the corresponding task division and data interaction scheme is designed to balance the load of each parallel execution unit and reduce the data traffic. In the thread-level parallelization, the atomic addition of the array index is adopted to solve the data race problem during parallel insertion. The invention can effectively reduce the time-consuming of three-dimensional model slice processing without reducing the original slice precision. At the same time, through the parallel reading of the corresponding sub-model files by each computing node, the hard disk I/O time can be reduced; each computing node only needs to process the sub-model data, which reduces the memory usage.

Description

A Multi-level Parallel Slicing Method for 3D Printing Models

technical field

The invention belongs to the technical field of 3D printing, and in particular relates to a multi-level parallel slicing method of a 3D printing model.

Background technique

3D printing refers to the process of digital modeling and layering of three-dimensional entities, and then layer-by-layer additive manufacturing of objects through certain materials and related supporting technologies. The layered slicing process communicates the 3D model representation of the item stored in the computer and the final processed product. Only when the 3D digital model is pre-processed and layered into a series of 2D plane data can the 3D printing equipment recognize and execute the actual item. print.

STL is a data format that can collaborate between CAD and printing equipment. It is the de facto file format standard in the field of 3D printing. It uses a large number of triangle patches to approximate the original CAD model. The STL file records each triangle Vertex information and unit normal vector for the patch. With the continuous improvement of industrial demand, the representation of the 3D model of the item to be printed is becoming more and more complex, and the requirements for the accuracy of the finished product are getting higher and higher. These factors have greatly increased the time-consuming process of slicing the 3D model. It has gradually become a bottleneck restricting the improvement of the overall production efficiency of 3D printing.

The document "Hierarchical Adjacency Sorting Fast Slicing Algorithm for STL Model, Journal of Computer Aided Design and Graphics, 2011, Vol23(4), p600-606" discloses a hierarchical adjacency sorting fast slicing algorithm for STL model. This method firstly obtains the maximum and minimum coordinate values of each triangular facet in the model projected in the slicing direction, and then combines the coordinate values of each tangent plane to determine the tangent plane that intersects each triangular facet, and obtains the triangular facet. The coordinates of the intersection with the tangent plane. In addition, for each slice layer, a linked list of intersection points is constructed according to the adjacency relationship between the triangular facets, and the intersection points are stored. Compared with the traditional slicing method based on topology information extraction and rectangular grouping, the method described in the literature has achieved a performance improvement. The method described in the literature is still a serial algorithm in essence, and the parallel processing potential of the slicing problem itself has not been analyzed and utilized. Slicing processing efficiency.

SUMMARY OF THE INVENTION

technical problem to be solved

In order to reduce the time-consuming of the three-dimensional model slicing process and improve the slicing efficiency, the present invention proposes a multi-level parallel slicing method for processing 3D printing models. The four-level parallelization slicing scheme is designed, taking advantage of the parallelization potential of the slicing problem itself, and relying on the parallel processing of each execution unit to achieve the effect of reducing the time-consuming of 3D model slicing processing without reducing the original slicing accuracy.

Technical solutions

A multi-level parallel slicing method for 3D printing models, characterized in that the steps are as follows:

Step 1: Execute the parallelization of computing node-level slices. In the cluster, use the patch as the basic unit to divide tasks among the computing nodes, and divide the original model file according to the division result to obtain multiple sub-model files;

Step 2: Perform multi-GPU-level slice parallelization. In each computing node, use the patch as the basic unit to divide tasks among multiple GPUs, and read the corresponding sub-model files into the memory in stages according to the division results and construct the patch and vertex arrays, import the patches and vertex arrays required for slicing from the compute node main memory into GPU memory;

Step 3: Execute thread block-level slicing parallelization, and divide the patch array imported into GPU memory into multiple sub-patch arrays between thread blocks;

Step 4: Execute thread-level slice parallelization, divide the sub-patch array belonging to a thread block among threads, the threads process the assigned patches in turn, and obtain all the slices that intersect with each patch. plane, and calculate the tangent segment, the thread inserts the tangent segment into the tangent segment array of the corresponding layer mutually exclusive;

Step 5: Export the tangent segment array from each GPU memory to the main memory, merge the calculation results of each GPU on the CPU side, and generate a sub-tangent segment array corresponding to the current computing node at each layer;

Step 6: Divide tasks by layer among computing nodes, collect and merge sub-tangent segment arrays by layer according to the division result, and obtain a corresponding tangent segment array in each layer obtained by allocation;

Step 7: Each computing node sequentially processes the tangent segment arrays of each layer existing in the current node, and performs the tangent segment connection in parallel to generate the contour lines of the slices in the layer.

In the step 1, the task division between computing nodes refers to using the patch as the basic unit, dividing the original model file in a continuous and even way, and assigning the remainder after the dividing to the last computing node; dividing according to the division result. After the original model file, several sub-model files are formed, one for each computing node.

The task division among multiple GPUs in the step 2 means that the sub-model files are divided into the sub-model files in a way of continuous equal division with the patch as the basic unit, and the remainder after equal division is allocated to the last GPU.

The reading of the sub-model file and constructing the array in the step 2 means that the computing node reads the assigned sub-model file several times according to the task division result, and the number of reading times is equal to the number of GPUs included in the computing node. After reading, the main memory of the computing node contains the same number of model data, and each group contains a patch array and a vertex array.

In the step 3, the patches are divided among the thread blocks. First, the patches are allocated in a continuous and equal manner, and the remainder after the equal division is allocated to each thread block one at a time, so that the task amount is distributed evenly and each thread block is distributed. Thread blocks are divided into consecutive patches.

In the step 4, the sub-patch array is divided among threads, one at a time is used to allocate among each thread in turn, so as to balance the distribution of tasks, and to make the memory units read by adjacent threads continuous, which promotes the Coalescing reads of GPU memory to improve memory access bandwidth.

In the step 4, the tangent segments are inserted into the array mutually exclusive, which means that when the threads participating in parallel process their respective triangular patches, the calculated tangent segments have a probability of belonging to the same layer, and the data needs to be inserted into the same array in a mutually exclusive manner. . The mutually exclusive insertion method is to set an array index to point to the next free position to be inserted in the array, specify that when inserting data, perform an atomic addition operation on the array index, and obtain the current value of the array index as the insertion position.

In the step 5, the calculation results of each GPU are merged, and the tangent segment data is merged by layers on the CPU side, that is, the tangent segments belonging to the same layer are merged into the same array.

In the step 6, collecting and merging tangent segment data between computing nodes specifically includes the following steps:

1) Take the layer as the basic unit, distribute the merge task among the computing nodes in a continuous and evenly divided manner, and distribute the remainder after the equal division to the last computing node;

2) The computing node performs data merging on the assigned layer, collects the tangent segment data located on the same layer in all computing nodes, and merges them into an array; after the tangent segment data is merged, each computing node discards the data that does not belong to the current computing node. Layer data, freeing up memory space.

beneficial effect

The present invention proposes a multi-level parallel slicing method for 3D printing models. The method accelerates 3D model slicing by means of multi-level parallel processing, and specifically includes four levels of slicing parallelization, which are computing node level, multi-GPU level, thread block level, and thread level. In each level of parallelization, according to the address space distribution, memory access method and data structure characteristics of the current level, the corresponding task division and data interaction scheme is designed to balance the load of each parallel execution unit and reduce the data traffic. In the thread-level parallelization, the atomic addition of the array index is adopted to solve the data race problem during parallel insertion. The invention can effectively reduce the time-consuming of three-dimensional model slice processing without reducing the original slice precision. At the same time, through parallel reading of the corresponding sub-model files by each computing node, the hard disk I/O time can be reduced; each computing node only needs to process the sub-model data, which reduces the memory usage.

Description of drawings

Fig. 1 is the flow chart of each level of the four-level parallelization slicing method proposed by the present invention;

2 is a structural diagram of each level of execution unit of the four-level parallelized slice of the 3D printing model proposed by the present invention;

3 is a schematic diagram of the division of parallelization tasks at the computing node level in the present invention;

Fig. 4 is the multi-GPU level parallelization task division schematic diagram in the present invention;

Fig. 5 is the schematic diagram of thread block level parallelization task division in the present invention;

6 is a schematic diagram of thread-level parallelization task division in the present invention;

7 is a schematic diagram of inserting data into the tangent segment array of the same layer mutually exclusive by two threads in an embodiment;

FIG. 8 is a comparison diagram of slicing time consumption between the original scheme and the current scheme.

Detailed ways

The present invention will now be further described in conjunction with the embodiments and accompanying drawings:

1-2, the present invention improves the slice processing speed of the three-dimensional model through a multi-level parallel method, which specifically includes four levels of parallelization. From a top-down perspective, they are compute node level, multi-GPU level, thread block level, and thread level.

Step 1: Execute the parallelization of computing node-level slices. In the cluster, use the patch as the basic unit to divide tasks among computing nodes, and divide the original model file according to the division result. Perform step 2. After completion, collect and merge tangents between computing nodes. segment data.

The division of tasks among the computing nodes means that the original model file is divided in a continuous and equal manner by taking the patch as the basic unit, and the remainder after the equal division is allocated to the last computing node. After dividing the original model file according to the division result, several sub-model files are formed, one for each computing node.

Referring to Figure 3, an STL model file contains the total number of patches N, the number of computing nodes in the cluster is n1, the number of patches allocated to each computing node is unify_count1, and the number of patches allocated to the last process is last_count1, then :

表示向下取整，％指求余数。按照上述计算出的面片数将原始STL模型文件分割为n1个子模型文件。in,

Indicates rounding down, and % refers to the remainder. Divide the original STL model file into n1 sub-model files according to the number of patches calculated above.

The benefits of splitting the original model file are:

1) Reduce the amount of data that each computing node reads from the hard disk into the memory, thereby reducing the I/O time;

2) Reduce the memory usage of each computing node, so that larger models can be sliced when the total memory of the computing node is fixed;

3) Each computing node performs slice computation in parallel, which brings about an effective reduction in computation time.

The collecting and merging tangent segment data between computing nodes specifically includes the following steps:

1) Taking the layer as the basic unit, the merging task is distributed among the computing nodes in a continuous and evenly divided manner, and the remainder after the equal division is distributed to the last computing node.

The number of layers that each computing node is equally divided into is unify_layer_count, and the remainder of the average distribution is allocated to the last computing node, and the number of layers obtained is last_layer_count, then:

2) The computing node performs data merging on the assigned layer, collects the tangent segment data located in the same layer in all computing nodes, and merges them into an array uniformly. In one embodiment, the MPI_Gather( ) interface of MPI is used to perform the merging operation on the tangent segment data, and this interface is called once for merging the data of one layer. After the tangent segment data is merged, each computing node discards the data of the layer that does not belong to the current computing node and releases the memory space.

Step 2: Execute multi-GPU-level slice parallelization. In the computing node, use the patch as the basic unit to divide tasks among multiple GPUs, read the sub-model files into the memory in stages according to the division results, and construct the patch and vertex arrays , import the data required for slicing from the main memory of the computing node into the GPU memory, and perform step 3. After completion, export the tangent segment data from each GPU memory to the main memory, and merge the calculation results of each GPU on the CPU side.

The division of tasks among multiple GPUs refers to using a patch as a basic unit to divide the sub-model files in a way of continuous equal division, and the remainder after equal division is allocated to the last GPU.

Referring to Figure 4, the number of GPUs in each computing node is n2, the number of patches included in the sub-model file allocated by the current computing node is count1, the number of patches each GPU is equally divided into is unify_count2, and the last GPU is assigned The number of patches is last_count2, then:

The step 2 of reading the sub-model file and constructing the array means that the computing node reads the assigned sub-model file several times according to the task division result, and the number of reading times is equal to the number of GPUs included in the computing node. After reading, the main memory of the computing node contains the same number of model data, and each group contains a patch array and a vertex array.

Among them, after the reading is completed, the main memory of the computing node contains n2 groups of data, and each group of data includes a face array Face[] and a vertex array Vertex[]. In the patch array, an element records the index of the three vertices contained in a patch, and the index refers to the subscript of the vertex in the Vertex[] array. In the vertex array, an element records the x, y, z coordinates of the vertex in the three-dimensional coordinate system.

Further, the merging of the calculation results of each GPU is to merge the tangent segment data by layers at the CPU end, that is, merging the tangent segments belonging to the same layer into the same array.

In one embodiment, OpenMP is used to implement control over multiple GPUs in a computing node, wherein the number of OpenMP threads created is equal to the number of GPUs in the computing node, and one OpenMP thread takes over one GPU computing card.

Step 3: Execute thread block-level slice parallelization, divide the patch array imported into the GPU memory among thread blocks, and execute step 4.

The division of the dough among thread blocks is to firstly allocate the dough in a continuous and equal manner, and allocate the remainder after the equal division to each thread block one at a time, so that the task amount is distributed evenly and each thread block is distributed. Divide into consecutive slices.

Referring to Figure 5, the number of thread blocks is n3, the number of faces in the Face[] array in the GPU memory is count2, the remainder after equal division is remain_count, the number of faces allocated to each thread block is face_count, and each thread block has Consecutive and unique number id, then:

In one embodiment, the thread blocks are organized as one-dimensional, and the number of thread blocks is reasonably set according to the number of stream multiprocessors included in the GPU.

Step 4: Execute thread-level slice parallelization, divide the sub-patch array belonging to a thread block among threads, and the threads process the assigned patches in turn, and obtain all the slices that intersect with each patch. plane, and calculate the tangent segment, the thread inserts the tangent segment into the tangent segment array of the corresponding layer mutually exclusive.

Referring to FIG. 6, the number of threads is n4, and the sub-patch array is divided among threads in a way of assigning one at a time among each thread, so as to balance the distribution of tasks and enable adjacent threads to read Memory cells are contiguous, enabling coalesced reads to GPU memory to increase memory access bandwidth.

Inserting the tangent segments into the array mutually exclusive means that when the parallel threads process their respective triangular patches, the calculated tangent segments have a probability of belonging to the same layer, and data needs to be inserted into the same array in a mutually exclusive manner. The mutually exclusive insertion method is to set an array index to point to the next free position to be inserted in the array, specify that when inserting data, perform an atomic addition operation on the array index, and obtain the current value of the array index as the insertion position.

In one embodiment, the threads are organized into one dimension, the number of threads included in a thread block is usually an integer multiple of 32, and the number of threads is reasonably selected according to the number of hardware resources such as registers on the GPU.

Referring to Figure 7, in one embodiment, an index e is used to record the current position to be inserted in the arr array, and the thread x and thread y calculate the tangent segments s1 and s2 of the same tangent plane and the respective triangular facets respectively, and want to simultaneously send the arr Array insertion, thread x executes AtomAdd(e), Insert(s1), thread y executes AtomAdd(e), Insert(s2), which realizes the correct insertion of mutual exclusion to the same array.

Step 5: According to the assigned layer, each computing node executes the tangent segment connection in parallel to generate the slice outline in the layer.

The layer allocated to each computing node refers to the layer allocated when collecting and merging tangent segment data between computing nodes in step 1. During the data collection and merging, the tangent segment data is evenly divided by layers to each computing node in the cluster. After the division, the data of each layer is independent of each other, and each computing node can perform the tangent segment connection in parallel to generate the contour line of the slice in the layer, and complete the slice processing of the model.

Referring to Figure 8, compare the slicing time consumption of the original scheme and the current scheme, where the original scheme refers to the serial slicing scheme, the current scheme refers to the multi-level parallel slicing scheme, and the hardware device used for the test is a GPU cluster. It includes two computing nodes. The CPU model on the computing node is Intel(R) Xeon(R) Gold 6132CPU@2.60GHz, and each computing node has three GPU computing cards, the model is Tesla V100-PCIE-32GB. The test results show that the multi-level parallel slicing scheme can effectively reduce the time-consuming of slicing, and the larger the model scale, the more obvious the acceleration effect.

Claims (8)

1. A multi-level parallel slicing method of a 3D printing model is characterized by comprising the following steps:

step 1: executing parallelization of computing node level slices, performing task division among computing nodes by taking a patch as a basic unit in a cluster, and dividing an original model file according to a division result to obtain a plurality of sub-model files;

the task division is carried out among the computing nodes: dividing an original model file in a continuous equipartition mode by taking a patch as a basic unit, and distributing the equipartition remainder to the last computing node; dividing the original model file according to the division result to form a plurality of sub-model files, and allocating one computing node;

and after the original model file is divided according to the division result, a plurality of sub-model files are formed: the total number of patches N contained in an STL model file, the number of compute nodes in the cluster is N1, the number of patches that each compute node distributes to is uniform _ count1, and the number of patches that the last process distributes to is last _ count1, then:

wherein,

indicating rounding down,% indicates remainder; dividing the original STL model file into n1 sub model files according to the calculated number of the slices;

step 2: executing multi-GPU-level slice parallelization, performing task division among a plurality of GPUs by taking a patch as a basic unit in each computing node, reading corresponding sub-model files into a memory in a grading manner according to a division result, constructing patches and vertex arrays, and importing the patches and the vertex arrays required by the slices into the GPU memory from a computing node main memory;

and step 3: executing thread block level slice parallelization, and dividing a patch array led into a GPU memory into a plurality of sub-patch arrays among thread blocks;

and 4, step 4: executing thread-level slice parallelization, dividing sub-patch arrays belonging to a thread block among threads, sequentially processing the allocated patches by the threads, solving all tangent planes intersected with each patch, calculating tangent segments, and mutually exclusively inserting the tangent segments into the tangent segment arrays of the corresponding layers by the threads;

and 5: exporting the tangent line segment array from each GPU memory to a main memory, merging the calculation results of each GPU at a CPU end, and generating a sub-tangent line segment array corresponding to the current calculation node at each layer;

step 6: task division is carried out among the computing nodes according to layers, sub-tangent segment arrays are collected and merged according to the division results according to the layers, and a corresponding tangent segment array is obtained in each layer obtained through distribution;

and 7: and each computing node sequentially processes the tangent line array of each layer existing in the current node and parallelly executes the tangent line connection to generate the intra-layer tangent contour line.

2. The method according to claim 1, wherein in step 2, a task division is performed among the GPUs, a sub-model file is divided in a continuous and equal division manner by using a patch as a basic unit, and the remainder after the equal division is allocated to the last GPU.

3. The method for multilevel parallel slicing of 3D printing model according to claim 1, wherein the reading in and constructing the array of the sub-model file in the step 2 means that the sub-model file allocated is read by the computing node for a plurality of times according to the task division result, and the number of reading times is equal to the number of GPUs included in the computing node; after reading, the main memory of the computing node contains the model data with the same group number, and each group contains a patch array and a vertex array.

4. The method of claim 1, wherein in step 3, the patches are divided among the thread blocks, and the patches are allocated in a continuous averaging manner, and the remainder after averaging is sequentially allocated to the thread blocks one at a time, so that the task allocation is balanced and each thread block is divided into consecutive patches.

5. The method as claimed in claim 1, wherein the step 4 is performed by dividing the sub-patch array among the threads, and sequentially allocating the sub-patch arrays among the threads one at a time to balance the task allocation and to make the memory units read by the adjacent threads continuous, so as to facilitate the merged reading of the GPU memory and improve the memory access bandwidth.

6. The method for multi-level parallel slicing of 3D printing model according to claim 1, wherein the mutually exclusive insertion of the tangent segments into the array in step 4 means that the calculated probability of the tangent segments belonging to the same layer when the threads participating in the parallel processing the respective triangular patches is the same, and the mutually exclusive insertion of data into the same array is required; the exclusive insertion mode is that an array index is set to point to the next idle position to be inserted in the array, the atomic addition operation needs to be executed on the array index when data is specified to be inserted, and the current value of the array index is obtained as the insertion position.

7. The method as claimed in claim 1, wherein the step 5 of combining the GPU results is to combine the slice data in layers at the CPU, that is, combine the slices belonging to the same layer into the same array.

8. The method for multi-level parallel slicing of 3D printing model according to claim 1, wherein the step 6 of collecting merged tangent segment data among the computing nodes comprises the following steps:

1) taking a layer as a basic unit, distributing merging tasks among the computing nodes in a continuous and uniform dividing mode, and distributing the equalized remainder to the last computing node;

2) the computing nodes perform data merging on the distributed layers, collect tangent segment data located on the same layer in all the computing nodes, and merge the tangent segment data into an array in a unified manner; after the combination of the data of the tangent line segments is completed, each computing node discards the data of the layer which does not belong to the current computing node, and the memory space is released.

Images