J. Cent. South Univ. Technol. (2010) 17: 1021-1027

DOI: 10.1007/s11771-010-0593-2

Method of triangular mesh modeling in numerical control machining simulation

MA Zhi-yan(马志艳), CHEN You-ping(陈幼平), LI Jian-jun(李建军), ZHAO Yao-jing(赵遥劲)

School of Mechanical Science and Engineering, Huazhong University of Science and Technology,Wuhan 430074, China

? Central South University Press and Springer-Verlag Berlin Heidelberg 2010

Abstract: In the process of numerical control machining simulation, the workpiece surface is usually described with the uniform triangular mesh model. To alleviate the contradiction between the simulation speed and accuracy in this model, two improved methods, i.e., the local refinement triangular mesh modeling method and the adaptive triangular mesh modeling method were presented. The simulation results show that when the final shape of the workpiece is known and its mathematic representation is simple, the local refinement triangular mesh modeling method is preferred; when the final shape of the workpiece is unknown and its mathematic description is complicated, the adaptive triangular mesh modeling method is more suitable. The experimental results show that both methods are more targeted and practical and can meet the requirements of real-time and precision in simulation.

Key words: numerical control machining; triangular mesh model; simulation

1 Introduction

The essence of numerical control (NC) milling simulation is the process of subtracting the swept volume formed by the cutter motion from the workpiece. Its base is to build the geometric models of the workpiece and cutter, which involves the surface dispersion techniques. It is the focal and hard problem in high-quality NC machining simulation to improve the simulation precision when simulation speed is satisfied [1-2]. In computer graphics and surface modeling, objects are often described with various types of models, such as solid geometric model [3-4], image model [5-8] and discrete vector model [9-11]. As the solid geometric model accords with the actual machining process, it is possible to compare the final simulation results with the designed products precisely. However, because of the huge intersection computation burden between the solid model and the cutter swept volume, the solid geometric model does not fit the real-time simulation of complex parts. The method based on image modeling is much more rapid and can realize real-time simulation. As all the original data in this method are transformed to the corresponding pixel values, the method cannot make precise measurement of the simulation results. The method of discrete vector modeling, which integrates the advantages of solid and image modeling, may meet the high-quality and real-time simulation requirements when the discrete precision is appropriate. The key problems of the discrete vector modeling are the discrete mode and the intersection algorithm between the discrete vectors and the cutter swept volume. In Refs.[12-15], the method of uniform triangular mesh modeling was described in details. This approach is simple and effective, and the simulation process can be observed from any point of view. But its disadvantages are also obvious. As the number of triangular pieces is huge, it is hard to perform excellent simulation output. GAO [9] presented an optimized discrete vector modeling method, which is an effective improvement based on the method of uniform discrete vector modeling. But it is not suitable for some objects with special shapes. LEE et al [10] and LIU [11] introduced an adaptive level of detail (LOD) algorithm and applied it to NC machining simulation, which improved simulation efficiency effectively. However, for some simple objects, it needed too much computing time.

Uniform triangular mesh modeling has been a very popular technique in recent years. It is very easy to be achieved and has good performance in simulation. However, in order to obtain better display output, the surface needs to be dispersed with a higher precision, which directly leads to much data redundancy, a lot of node operation and the reduction of simulation speed. For example, if the precisions in both vertical and horizontal directions are improved by 10 times, the number of nodes should be increased by 100 times. So, it is necessary to improve the uniform triangular mesh modeling method. Based on the uniform triangular mesh modeling method, in this work, two improved algorithms i.e., local refinement triangular mesh modeling and adaptive triangular mesh modeling, were proposed according to the actual situation.

2 Local refinement triangular mesh modeling

2.1 Algorithm summary

The local refinement triangular mesh modeling is based on the assumption that the target is relatively simple or the mathematical model z=f(x, y) of the target surface is easy to obtain. So, it is very convenient to calculate the height and curvature of the discrete points. In this method, some secondary discrete points are added in the area where the curvature varies greatly to increase the density of mesh. The secondary discrete points are some new points added between two continuous uniform discrete points, which can improve the local discrete precision of the workpiece. The processing of secondary discrete points is similar to that of primary discrete points. There are two ways for adding secondary discrete points in primary discrete areas: triangular piece splitting and equidistant adding. As it is easier to construct and access the data, the way of equidistant adding is more efficient in machining simulation. Fig.1 shows the principle of local refinement triangular mesh modeling by inserting equidistant secondary discrete points. While improving simulation quality, this method increases the amount of data as small as possible. Because all the discrete points on the surface of the rough model are defined before simulation, the amount and distribution of them will not change during simulation. This method is defined as the bottom-to-top triangular mesh modeling.

2.2 Addition of secondary discrete points

The secondary discrete points should be added according to the geometric information of the part surface. Firstly, it should be judged whether secondary discrete points need to be added or not in every rectangle

Fig.1 Local refinement triangular mesh modeling by inserting equidistant secondary discrete points

on the rough surface after uniform dispersion. Because the motion of the cutter only changes the height of the primary discrete points in the silumation, the height difference in the discrete rectangle is an important factor of local refinement. Another important factor is the variation of the curvature among the four corners of the discrete rectangle. Height difference Z and curvature variation ρ in each discrete rectangle can be calculated with the following formulas:

Z=max(Z_A, Z_B, Z_C, Z_D)-min(Z_A, Z_B, Z_C, Z_D)         (1)

      ρ_X=max(ρ_AX, ρ_BX, ρ_CX, ρ_DX)-min(ρ_AX, ρ_BX, ρ_CX, ρ_DX)

ρ_Y=max(ρ_AY, ρ_BY, ρ_CY, ρ_DY)-min(ρ_AY, ρ_BY, ρ_CY, ρ_DY)    (2)

ρ=max(ρ_X, ρ_Y)

According to variations of Z and ρ, the following cases were investigated, as shown in Fig.2.

Case 1 If variations of Z and ρ are both small and that of Z is less than permissible machining error e, it can be considered that the shape of the target part has little change in the primary discrete rectangle. In this situation, it is not necessary to add secondary discrete points in the primary discrete rectangle.

Case 2 If variations of Z and ρ are both relatively large and that of Z is greater than permissible machining

Fig.2 Four kinds of situations of adding second discrete points in primary discrete rectangle (Z is height difference of object pieces corresponding to discrete rectangular ABCD): (a) Case 1; (b) Case 2; (c) Case 3; (d) Case 4

error e, the shape of the target part has a large change in the primary discrete rectangle. So, it is improper to approximate the rectangular surface only by two triangular pieces. In this situation, secondary discrete points in the primary discrete rectangle need to be added. The spacing (l) among them should be l=Z/e. As a result, the number of secondary discrete points added on each side of the primary discrete rectangle should be the smallest positive integer that is not less than L/l-1, where L is the spacing between two adjacent primary discrete points.

Case 3 If the variation of Z is less than error e, and ρ has a large change, height difference Z of the rectangular surface cannot be calculated by Eq.(1). Furthermore, in the range of the primary discrete rectangle, there are some characters whose sizes are less than L. Because L is far less than the diameter of the cutter, it is impossible to process those details in the rough milling period. In this situation, it also does not need to add secondary discrete points in the primary discrete rectangle.

Case 4 If the variation of Z is more than error e, and ρ has a small change, which usually occurs at the step- like position of the surface, secondary discrete points should be added to meet the simulation requirements. However, in this situation, the spacing between them is not determined by the value of Z but 1/4-1/10 of primary discrete precision L.

2.3 Data structure and assessment of rough

When the simulation begins, the accessing process of the discrete points is as follows. Firstly, according to each cutter step, the surrounded rectangle should be calculated in the projection plane. Then, through comparing heights between four corners of each primary discrete rectangle in the surrounded rectangle and the tool tip, it is easy to judge the intersection situation between them. If they do not intersect, heights of the discrete points in the primary discrete rectangle will not be changed. Otherwise, heights of all the primary and secondary (if they exist) discrete points in the primary discrete rectangle will be assigned to those of the tool tip.

In order to save the memory space and accelerate the simulation speed, the data structure of the rough model needs to be simplified properly. Fig.3 shows the indexed sequence and calculation relationship between the discrete points and the corresponding rectangles. In this way, all the x and y coordinates of discrete points can be worked out according to their array subscripts expediently. As the secondary discrete points are involved in the calculation of intersection, display and final error, their data structure is associated with the corresponding primary discrete rectangle to reduce data

Fig.3 Indexed sequence and calculation relationship between discrete points and corresponding rectangles (Figures without brackets are discrete point index numbers, and figures in brackets are discrete rectangle index numbers)

redundancy. From the above, the data structure of the rough can be determined.

2.4 Display of simulation

In the simulation, the cutter swept volume continually cut the surface of the rough. The heights of the discrete points were continually updated so as to gradually approximate the real shape of the part. When using OpenGL for rendering the simulation output, the normal vector of each triangular piece needs to be calculated. However, not all the triangular pieces need to be rerendered after each cutter step. Thus, when the height of one discrete point is changed, the triangular piece that contains the point may be recorded. For example, in Fig.2, if the height of point A is changed, triangular piece ABD is recorded; if the height of point B or D is changed, triangular pieces ABD and CBD are both recorded. When rendering, we only need to calculate the normal vector of those recorded triangular pieces. As a result, it can greatly reduce the smulation computation burden.

3 Adaptive triangular mesh modeling

3.1 Algorithm summary

Generally, a good modeling method should not depend on the part model. Especially when the surface shape of the workpiece is complex or the height of the discrete point is hard to obtain, adopting the method of local refinement triangular mesh modeling is not worthy, even infeasible. In this situation, it is considered that only the G code and tool settings need to be known before simulation. As the local details cannot be dealt with in advance, it is difficult to establish a proper discrete model of the rough. However, the method of adaptive triangular mesh modeling is more preferable. In this method, the rough surface is approximated by discrete triangular pieces with the minimum resolution, which comes from the blocking of the uniform lattice with the maximum resolution. When simulation begins, the heights of the discrete points in the surrounded rectangle are assigned continuously. Meanwhile, the triangular pieces intersected with the swept volume are split until the desired machining precision is satisfied. In this way, the density of triangles can be controlled adatively. Because the number and distribution of discrete points on the model surface are dynamically changed with the cutter motion during simulation, this method is defined as the top-to-bottom triangular mesh modeling.

Besides, due to the large number of small triangular pieces from splitting, the time for display is far more than that for cutting calculation. So, the main bottleneck is the graphics rendering display. Some measures are taken to alleviate this problem. On one hand, triangular pieces are split continuously until the desired machining precision is satisfied in the uneven areas; on the other hand, they are merged continuously to reduce the number of rendering triangular pieces in even areas if the desired machining error allows. This is the main idea of adaptive triangular mesh modeling.

3.2 Discrete resolution of rough surface

Firstly, the surface is dispersed into a uniform lattice with desired spacing l, which is called data grid. This method differs from the former method in that the initial uniform dispersion of it is made by the maximum resolution. Then, the uniform lattice is divided into some square blocks by n² discrete points, and the minimum resolution dispersion of the surface is obtained, which is called display grid. Obviously, the sapcing of the new discrete points after blocking is L=nl. It should be noted that the value of n must be assigned to 2^x. Near the boundary, if the number of discrete points is not large enough to form a square block, some suppositional points should be added to keep the integrity of the dividing. Finally, each square block is seperated into two triangular pieces by its diagonal. All triangular pieces constitute the minimum resolution approximation of the surface.

Dispersing the surface with the maximum resolution is to guarantee the precision of machining simulation, while dividing the lattice into square blocks is to reduce the number of triangular pieces in rendering queue. It can improve the simulation speed on the premise that the output quality can be guaranteed. To ensure the splitting or merging operation of triangular pieces, the value of n should be assigned to 2^x. Fig.4 shows different situations that the values of L are assigned to be 2l, 4l, 6l and 8l. When the value of L is 2l, the original triangular piece can only be split twice. When the value of L is 4l, it can be split four times. When the value of L is 8l, it can be split six times. But when the value of L is 6l, the original triangular piece can only be split twice, as shown in Fig.4(c). In this case, if the splitting is forced to continue, it will result in the apex of the new triangular piece falling out of the discrete points. This is the situation that should be avoided. In simulation, the assignment of the value of L mainly depends on the detail of the target surface. If there are many details, the value of L can be 2l. If the surface is smooth, the value of L can be 8l. If the surface of the target is unknown, the value can be compromised, such as 4l.

3.3 Splitting and merging of triangular pieces

The height error of the discrete triangular piece is defined as the maximum absolute value among the differences between the height values of the data grid in the range of the triangular piece and those of the corresponding approximate surface. After the surface is dispersed into data grid and display grid, a series of root triangular pieces can be obtained. They are all isosceles right-angled triangles in projection plane XOY. The splitting of triangular pieces obeys the following rules.

(1) When the height error of the triangular piece is greater than permissible machining error e, it will be split until the desired machining precision is met.

(2) When one triangular piece needs to be split, it will be divided along the midline of the hypotenuse. As a result, the two new ones are still isosceles right-angled triangles in projection plane XOY.

Fig.4 Setting the minimum resolution with blocking (where l is grid spacing with the maximum resolution, and L is grid spacing with the minimum resolution): (a) L=2l; (b) L=4l; (c) L=6l; (d) L=8l

The first rule specifies the splitting qualification and

the second one explains the way of splitting. Fig.5 shows the splitting process and some special situations. Fig.5(a) shows the original target surface piece ABCD corresponding to the minimum resolution and Fig.5(b) shows the approximate surface represented by two root triangular pieces △ABC and △ADC. Fig.5(c) shows the first splitting process. If height error Δh_E of △ABC is greater than permissible machining error e, the splitting will begin. As a result, triangular pieces △ABC and △ADC are split. The four right-angle sides of the two root triangles become the four hypotenuses of the four split triangles. In this way, the splitting continues until the desired machining precision is met. Fig.5(d) shows the result of splitting for the second time assuming that height error Δh_F of ?CED is greater than  permissible machining error e. Fig.5(e) demonstrates two special situations in splitting. For the first one, the height error is the main reason for the splitting. After each splitting, height errors of the two new triangular pieces should be calculated again to determine whether the splitting needs to continue or not. It is a recursive process. For the second one, the splitting of some triangular pieces may affect the integrity of the approximate surface. For example, if the position of the height error of     △AGE is at point H, which is the midpoint of the right- angle side, triangular piece △AGE should be split twice. Firstly, △AGE is split into △AIG and △EIG. The change of position of point I causes the blank in the  area of △AIE, which demages the integrity of the approximate surface. To avoid this, brother triangular piece △AKE should be split at the same time. Another special case may be like this: the hypotenuse of △EGB is the right-angle side of △CEB. When △EGB needs to be split, triangular piece △CEB should be split first to get the brother triangular piece of △EGB. Then, this pair of triangular pieces is split.

Compared with splitting, the merging of triangular pieces is relatively simple. It mainly occurs between the brother ones. The merging of triangular pieces obeys the following rules.

(1) When the right-angled apexes of a pair of brother triangular pieces fall on the edge of the surface and their height error is less than permissible machining error e, the pair of brother triangular pieces can be merged to restore their parent triangular piece.

(2) When the right-angled apexes of a pair of brother triangular pieces fall out of the edge of the surface and their height error is less than permissible machining error e, and if the brother pair exists, the two pairs of triangular pieces can be merged to restore the two parents at the same time.

The merging of brother triangular pieces is implemented by deleting the side and the apex corresponding to the common right-angle side and the right-angle apex in projection plane XOY. The parent triangular piece from the merging of brother ones is still an isosceles right-angle triangle in projection plane XOY. For example, in Fig.5(e), there are three pairs of brother triangular pieces as the leaf node. They are △AHI and △GHI, △AIK and △EIK, △CFE and △DFE. If height error Δh_H is less than permissible machining  error e, the pair of triangular pieces, △AHI and △GHI, can be merged to restore their parent triangular piece  △AIG. In fact, with the reverse process of splitting, the merging of triangular pieces also brings about the problem of surface integrity. For example, in Fig.5(e), if height error Δh_I is less than permissible machining  error e and when the pair of triangular pieces, △AIK and △EIK, are merged, blank area △AIE appears. In the same way, this problem can be solved by merging the brother pair of triangular pieces △AIG and △EIG, simultaneously.

3.4 Display refreshing

The continual display refreshing in the simulation mainly depends on the display list defined in the program. For each cutter step, only the triangular pieces whose

Fig.5 Process of triangular pieces splitting and some special situations: (a) Original target surface piece corresponding to the minimum resolution; (b) Approximate surface represented by two root triangular pieces; (c) The first splitting process; (d) The second splitting process; (e) Some special situations in splitting

apexes fall into the surrounded rectangle of cutter motion are added to the display list. If a triangular piece is split, it will be replaced by the two new brother ones in the list. If two brother triangular pieces are merged, they will be replaced by the parent one in the list. If a triangular piece has no operation of splitting or merging, it will be still reserved. At each step, only the triangular pieces in the list need to be rendered. In this way, the simulation speed can be improved obviously.

4 Results and discussion

To verify the two methods of triangular mesh modeling, two groups of milling simulation experiments were conducted. The milling simulation was implemented in VC++ 6.0 with OpenGL on a Genuine Intel 2140 processor with 1 G of main memory. The rendering outputs of experiments are shown in Fig.6. Both the methods were compared with the method of uniform triangular mesh modeling.

Figs.6(a)-(c) show the simulation output comparison between the uniform triangular mesh modeling and the local refinement triangular mesh modeling. The target is a simple geometric part. In this experiment, the size of rough surface is 8×8 and the maximum resolution of it is 120×120. So, spacing l between the secondary discrete points is determined. The machining simulation parameters are chosen as follows: the spacing between two adjacent primary discrete points L=4l, the radius of ball-end cutter is 0.2 cm, permissible machining error e is assigned to be 0.01 cm, and the simplified milling code has 3 305 instructions of linear cutter step. When the simulation runs with the uniform triangular mesh modeling, there will be 28 800 triangular pieces to approximate the target surface and the output speed is 9.72 f/s. While it runs with the local refinement triangular mesh modeling, there will be only 6 240 triangular pieces and the speed is 24 f/s.

Figs.6(d)-(f) show the simulation output comparison between the uniform triangular mesh modeling and the adaptive triangular mesh modeling. The target is a complex geometric part. In this experiment, the size of rough surface is 10×8. The resolution of data grid is 150×120 and that of display grid is 38×30. So, each root triangular piece can be split 4 times. The machining simulation parameters are determined as follows: the spacing between two adjacent primary discrete points L=4l, the radius of ball-end cutter is 0.5 cm, permissible machining error e is assigned to be 0.02 cm, and the simplified milling code has 4 556 instructions of linear cutter step. When the simulation runs with the uniform triangular mesh modeling, there will be 36 000 triangular pieces to approximate the target surface and the output speed is 6.6 f/s. When it runs with

Fig.6 Machining simulation results: (a) Rendering simulation output of local refinement triangular mesh modeling; (b) Wire-frame output of uniform triangular mesh modeling; (c) Wire-frame output of local refinement triangular mesh modeling; (d) Rendering simulation output of adaptive triangular mesh modeling; (e) Wire-frame output of uniform triangular mesh modeling; (f) Wire-frame output of adaptive triangular mesh modeling

the adaptive triangular mesh modeling, there will be only 8 264 triangular pieces and the speed is 17.3 f/s. The simplification effectiveness of the both new modeling methods is directly related to the surface shape of the target.

As proved in the experiment, the two modified algorithms can greatly improve the simulation efficiency on the premise of ensuring the machining precision. Meanwhile, it is convenient to take some geometric transformations such as rotation, translation and zoom, thus meeting the requirements of real-time and precision satisfactorily in the NC machining simulation.

5 Conclusions

(1) When conditions of the simulation are the same, such as the same workpiece model, permissible machining error, cutter and machining code, the speed of frame output will depend on the computation burden of each cutter step and the number of the triangular pieces that need to be rendered in each frame. The frame speed of uniform triangular mesh modeling is the lowest as the number of discrete triangular pieces is the most.

(2) When the target surface is simple, the method of local refinement triangular mesh modeling will be more efficient than that of adaptive triangular mesh modeling.

(3) Compared with the other two modeling  methods, the principle of the uniform triangular mesh modeling is very simple. The simulation is the easiest to realize. But under the condition of the same machining precision, the number of the triangular pieces of the approximate milling surface is the largest, which directly results in the lowest output speed.

(4) Because it does not involve in the operation of splitting and merging in the simulation, the local refinement triangular mesh modeling has the fastest output speed. But the application of this method is restricted. It is not suitable for the cases with complex targets.

(5) The approximate efficiency of the adaptive triangular mesh modeling is the highest. This results in the least number of triangular pieces. As it does not need to know the shape of target surface, this method has the most extensive applications. The image quality can be guranteed and the workpiece model can be moved, rotated and zoomed during the simulation. When the inspections of machining error, overcut, undercut and

interference are performed, the maximum resolution model in memory will be used to ensure the measurement accuracy and reliability.

References

[1] GIACONIA P. Trends in NC simulation [J]. Tooling and Production, 1996, 6: 31-42.

[2] LUTTERVELT C A V, CHILDS T H C, JAWAHIR I S. Present situation and future trends in modeling of machining operations [J]. CIRP Annals, 1998, 47(2): 587-626.

[3] SPENCE A D, ABRARI F, ELBESTAWIT M A. Integrated solid modeler based solutions for machining [J]. Computer-Aided Design, 2000, 32(8): 553-568.

[4] ZHOU Ji, ZHOU Yan-hong. Technology of NC machining [M]. Beijing: National Defense Industry Press, 2002: 29-50. (in Chinese)

[5] ZHAO Ji-zheng, WEI Sheng-min, YANG Pen-ji. Simulation of NC machining based on improved image space method [J]. China Mechanical Engineering, 1998, 9(5): 28-31. (in Chinese)

[6] MAENG S R, BAEK N, SHIN S Y. A fast NC method for linearly moving tools [J]. Computer-Aided Design, 2003, 35(11): 995-1009.

[7] CHOI B K, CHUNG Y C, PARK J S. Application and extension of Z-map model [C]// Proceeding of the 3rd Pacific Conference on Computer Graphics and Applications, Pacific Graphics 95’. Seoul: World Scientific, 1995: 363-382.

[8] SABINE S. Simulation of NC machining based on the Dexel model: A critical analysis [J]. International Journal of Advanced Manufacturing Technology, 1995, 10: 149-157.

[9] GAO Ming. Research and implementation of optimized discrete vector model of NC machining simulation [D]. Beijing: Beijing University of Aeronautics and Astronautics, 2002: 10-53. (in Chinese)

[10] LEE S H, LEE K S. Local mesh decimation algorithm for view-independent three-axis NC milling simulation [J]. International Journal of Advanced Manufacturing Technology, 2002, 19: 579-586.

[11] LIU Shi-qing. Research and application of level-of-detail technology of mesh models [D]. Wuhan: Huazhong University of Science and Technology, 2006: 34-61. (in Chinese)

[12] LUO Kun. Using triangular faceted model for NC machining verification [J]. Journal of Computer Aided Design and Computer Graphics, 2001, 13(11): 1024-1028. (in Chinese)

[13] HSU P L, YANG W T. Real-time 3D simulation of 3-axis milling using isometric projection [J]. Computer-Aided Design, 1993, 25(4): 215-224.

[14] ZHAO Ji-zheng, WEI Sheng-min, YANG Pen-ji. On improving simulation and verification of numerical control machining [J]. Journal of Northwestern Polytechnic University, 1998, 16(4): 575-579. (in Chinese)

[15] ZHAO Ji-zheng, WEI Sheng-min, YANG Pen-ji. Verification technique for numerical control machining method [J]. Manufacturing Automation, 1998, 20(2): 54-60. (in Chinese)

(Edited by CHEN Wei-ping)

Foundation item: Project(60772089) supported by the National Natural Science Foundation of China; Project(20080440939) supported by the China Postdoctoral Science Foundation

Received date: 2009-11-20; Accepted date: 2010-04-28

Corresponding author: MA Zhi-yan, PhD; Tel: +86-27-87543555; E-mail: marn2000@sohu.com