Image-assisted Collision Detection for Calculation of Assembly Interference Matrix

doi:10.21203/rs.3.rs-2107927/v1

Download PDF

Research Article

Image-assisted Collision Detection for Calculation of Assembly Interference Matrix

https://doi.org/10.21203/rs.3.rs-2107927/v1

This work is licensed under a CC BY 4.0 License

Journal Publication

published 10 Apr, 2023

Read the published version in The International Journal of Advanced Manufacturing Technology →

You are reading this latest preprint version

Assembly interference matrix is one of foundation information model for assembly process planning like assembly sequence planning and assembly path planning, which supports the digital assembly simulation, intelligent assembly, digital twins based assembly etc. Assemble interference matrix represents each two parts are collision or not when they moving along specific directions. Traditional assembly interference matrix construction adopts geometric collision detections on approximate swept volume of part which composed by moving part step by step. This manner not only leads to heavy computational loading since small moving step but also easy to misjudging contact as collide as well as missing collide due to discrete spatial moving of part. To overcome the drawbacks, this work equivalent the collision detection of parts during assembly interference matrix establishing as visibility judgement, and develop an image-assisted calculation method to process the collision between part’s swept volume as occlusion of images via computer graphic rendering. This method is implemented on OpenGL to ensure its generality, and the implicit calculating is finished in computer graphic rendering process by arranging proper rendering conditions with adopting depth testing and stencil testing. Furthermore, the erosion operation of image process is employed to distinguish whether contact or collide. At last, an examples for gear box assembly validates the effectiveness of this method.

Assembly

interference matrix

collision detection

contact

image space

OpenGL

As the last step of product manufacture, assembly process has significant effect on the performance and quality of product [1]. Assembly sequence planning is the basis to implement assembly activity. According to the assembly sequence of parts and components, specifying reasonable inspection, process operations, assembly fix and material are the foundation to obtain high efficiency for assembly and guarantee the assembly quality [2, 3]. As a powerful digital technology, virtual assembly is capable to validate the accessibility and evaluate the performance of assembly process in early assembly process design stage, e.g. ensuring the feasible assembly sequence by simulating the assembly process with collision detection, which contributes to avoid assembly interference due to mistake assembly process and shorten the period of assembly process design [4].

Interference matrix is an important information model for assembly sequence planning that working via relationship matrix. It represents the relative spatial position between parts which is the important basis to judge the feasibility for part assembly [5]. Normally, interference matrix indicates it is interference or not of each part moving out the whole assembly room along the positive / negative directions of three coordinate frame axes with the other parts. For interference matrix A_D in direction D, it is element A_D[i,j] stores the interference result of moving part i along direction D with part j, which including three cases, i.e. interference-free, contact, and hard-collision [6].

Identifying the interference elements values, normally, is adopting the classic triangle-based rigid objet collision detection method. The object part is moving step by step with specific step length, and the collision detection is performed for each position between object part and the opposite part to report is there any interference occurred. However, it is low efficient, particular for plenty of parts with complex geometry since the collision detections lead to heavy computation, huge-memory requirement, and spend long time. Besides, it is significant to accurately distinguish interference and contact for interference matrix establishing since contacts are common exist in mechanical part assembly like shaft-hole, panel align panel etc. Therefore, it enhances the compute difficult for collision detection algorithms and heavier compute load.

Actually, the establishment of interference matrix establishment is met that only checking it is interference or not for object part taking linear motion with opposite part. Therefore, it is hopeful to improve the computation efficiency by dimension-reduction in viewpoint of image-space where represents the swept volume of object part by the projection area of view volume for object part along moving direction. Besides, with the performance boosting of Graphic Processing Uniting (GPU), image-based collision detection methods gain excellent performance by utilizing the powerful parallel computation capability of GPU to seed up task calculation [7]. As the two of most classic ones, RECODE [8] and CULLIDE [9] employ the depth buffer, stencil buffer, occlusion query etc. in image space to perform collision detection computation. In this basis, according to the dimension reduction ideology, Zhou et al [10] proposed a fast collision detection method based on the Z-buffer, which good at the real-time collision report for first person roams in virtual scene by providing the spatial coordinate value of specific pixel to perform collision detection. To deal with the collision detection during kinematic simulation of mechanical system, Sun et al [11] developed a dual view and semi-transparent color overlap collision detection algorithm, which transforming the problem as panel pixel judgement by projection based dimension reduction, resulting to meet the real time requirement during virtual assembly simulation. With respect to the characteristic of stream computation for GPU, Liu et al [12] represented a collision detection that combine both model space and image space for the purpose that employing the parallel computation speed up of GPU without lose the real-time and accuracy of algorithm. Kim et al [13] developed the hybrid parallel continuous collision detection (HPCCD) to obtain significant improvement in efficiency by utilizing the computation capability of both GPU and many-CPU. These methods have indicated that image-based collision detection show extraordinary efficiency improvement by reducing the dimension of mathematical model for collision detection task. However, establishing the interference matrix for complex mechanical system by directly adopting the image-based collision detection algorithms still subject to heavy compute task and result to low efficiency.

To overcome this drawback, a geometry space and image space combined collision detection algorithm is developed with respect to the special requirement of collision detection for interference matrix element establishment. It identifies the obvious interference-free element by spatial boundary box based on conservatism in rough stage, and performs precise interference checking by a delicate algorithm with adopting Z-buffer and stencil buffer through OpenGL. Finally, it not only reaches a high compute efficiency but also capable to report interference and contact cases for assembly interference matrix establishment. The rest of part is arranged as follows: section 2 represent the rough stage of interference matrix calculation by boundary box; The complete image-based collision detection algorithm performed by OpenGL including both calculation principle and concrete algorithms are described in section 3; In section 4, examples are studied and discussed and concluded at last.

Identifying it is interference or not for each part along six directions with other parts is basic operation to establish the interference matrix. The non-overlap between parts of assembly indicates that most of parts are non-interference to each other in their separation directions. Therefore, taking a simply but robust method to identify these non-interference elements at first is significant to improve the computational efficiency of interference matrix, since the details interference checking only performs to the rest elements [14, 15].

As an easy to obtained geometric structure, axial alignment boundary box (AABB) expresses the coordinate ranges of all the geometric elements of part in specific coordinate frame UVW. As shown in Fig. 1, it facilities the identification of non-interference for moving part i relative to part j along direction D∈{+U, -U, +V, -V, +W, -W} as below:

(i) if condition D_i_,min > D_j_,max is satisfied, interference-free in +D and the rest directions except -D are met since it indicates that part i is completely on the +D side of part j;

(ii) similar, condition D_i_,max < D_j_,min reports interference-free in -D and the rest directions except +D due to part i completely locates in the –D side of part j;

In this basis, delicate collision detections are evoked for the rest elements which have possibility of non-interference. Meanwhile, with considering the relative moving between parts, only the right-up element of interference matrix are calculated. The complete calculation schema is arranged as in Fi. 2.

With considering the special collision detection requirement of interference matrix, the image-assisted interference checking method is detailed in principle and implement procedure as well as contact distinguishing.

3.1 Principle of image-assisted collision detection

The element M_D,_i,_j of interference matrix indicates the swept volume of part i along direction D is interference or not to part j. In viewpoint of computer graphics rendering, this kinds of swept volume can be expressed as the occlusion room with the help of z-buffer when taking the view as direction D and the depth-test strategy as greater than through [15]. As demonstrate in Fig. 3, the spatial line segments of part corresponding pixels that from z_far(1.0) to their minimum value consist of the part swept volume once taking orthogonal projection mode. Obviously, the rendering of part i instead of the traditional discrete part swept volume by a serial of part solid along moving path.

In this basis, when the depth-test strategy is re-set as smaller than pass for part j rendering, as shown in Fig. 4, (i) there is no pixel passing the depth-test if all the pixels of part j completely on the –D side of their corresponding pixels of part i, and (ii) only the pixels that corresponding to overlap areas of interference room between part j and the swept volume of part i is passed the depth-test. Consequently, the interference or not of element M_D,_i,_j can be reported by existing rendered pixels of part j or not respectively.

All these calculations are performed implicitly comply with the graphic rendering process by discrete pixels. Essentially, this kind of discretization on geometry objects produced by rasterization, not only provides the capability to process complex geometry but also ensures the generality and robustness and practicality for this calculation principle.

3.2 Detail calculation model based on OpenGL

The detail computation is performed by OpenGL with considering its excellent characteristics like cross-platform, industrial graphics programming interface. It is arranged in three stage i.e., preparation of rendering, implicit calculation by graphic rendering, and identification of contact condition. Besides, optimization operations like face culling, stencil buffer, and occlusion testing are involved to speed up the computational efficiency.

3.2.1 Preparation of rendering

Preparing rendering environment properly according to the interference calculation model is the foundation for OpenGL based calculation. It includes two sides, i.e., view direction setting, and view volume setting. As show in Fig. x, the view direction is consistent with moving direction D of part i, and the view volume is specified as the overlap room of AABBs of part i and part j to get rid of the non-intersection areas for reducing computational loads. The detail functions can be given as:

gluLookAt(C_1×3, F_1×3, T_1×3)

glOrtho(left, right, bottom, up, near, far);

Where, C is the center of view volume; F is a point in front of view volume along D; T is a point above view volume from C;

3.2.2 Procedure of OpenGL-assist implicit calculation

The calculation principle has indicated that the key of rendering calculation is to judge whether the rendered pixels of part j pass the depth test. With respect the functions of OpenGL, stencil test and occlusion query are involved to help accelerate this judgement. As shown in Fig. 6, the implicit calculation is arranged in 6 steps via OpenGL functions according to the calculation principle. The detail process is represented as follows:

Step I: Initializing z-buff and stencil buffer as 1.0 and 0 respectively.

Step II: Setting the judgement conditions of depth test and stencil test for part i rendering. (i) Depth test: less than passing; (ii) Stencil test: ensuring all pixels take participate stencil test, and assign 1 to stencil value if the pixel passing depth test.

Step III: Rendering the part i. Herein, the back faces of part i are culled since the maximum value of pixels are determined by the front faces. After rending, the stencil values of part i correspond pixels are set as 1, and the rest ones remain 0.

Step IV: Resetting the judgement conditions of depth test and stencil test, and preparing occlusion test for part j rendering. (i) Depth test: greater than passing; (ii) Stencil test: only the pixels that stencil value equal to 1 engage stencil test, and further, the stencil vale is increasing 1 of the pixel passed depth test.

Step V: Rendering the part j. Similarly, the front faces are expelled because of only the back faces generate the minimum depth value. In this process, only the pixels of part j that overlap part i passes the stencil test since these pixels’ stencil value equal to 1. Further, the occlusion query is monitoring the pixels that pass the depth test.

Step VI: Get result. It is interference-free if no pixels go pass the depth test. Otherwise, the stencil buffer is extracted for further distinguishing that it is collision or contact between part j and the swept volume of part i.

3.2.3 Identification of contact condition

In practical assembly, the adjacent parts with positioning relationships like shaft-hole, plane-fitting etc., might be mistaken as interference by collision detection due to its geometric represent precision [16]. Essentially, the key to avoid this kinds of mistake is how to correctly distinguish two parts is contact.

If two parts are contact, only their contact boundary geometries might be go through the depth test and stencil test. Accordingly, one can regard the two parts are contact if the pixels that stencil value no less than 2 are distributed as lines or curves. The classic image corrosion operation [x] is adopted to process the image composed stencil buffer after binary segmentation with threshold 2. As a result, it is interference-free if all the pixels are eliminated after one times of image corrosion operation, otherwise collision is reported.

In order to proof the effectiveness of this method, an example to distinguishing interference and contact for shaft-hole is test at first, and a complete calculation for gear-worm box is performed. Through programming developed algorithm by VS2017 C + + and OpenGL (v.x.x.x), all the computations are running on a laptop with Win10, CPU intel core-i7×12, GPU NAVIDIA GeForce GTX 1050Ti. Besides, all the part models are stored in STL format for rendering, and the viewport size is given as 800×800.

4.1 Example of shaft-hole assembly

As a common assembly form, the shaft-hole exists contact is practical assembly. a shat and a bearing assembly that shown in Fig. 7(a) is taken for interference checking along their axial direction as demonstrated in Fig. 7(b). According to the calculation procedure developed in this work, the stencil buffer results of step-I, step-II/III, and step-IV/V are rendered as image composed by pixels in Figs. 7 (c), where blue, green and red color indicated the pixel’s stencil value is 0, 1, and no less than 1, respectively. Clearly, the red circle produced after step IV/V in Fig. 7(c) indicates the shaft and bearing is taking a potential interference as cylindrical surface, while no residual pixel after erosion operation for output stencil buffer reports the shaft and hosle are interference-free. This example shown that this method is capable to identify contact conditions in interference conditions.

4.2 Example of worm gear box

The developed interference matrix calculation method based on OpenGL is performed on a gear-worm box to proof its effectiveness. As shown in Fig. 8, this assembly includes 16 parts, of which the sequence numbers are listed in the exploded diagram, most of them taking the shaft-hold assembly relationship. The right-up elements of interference matrices for 6 directions are listed in Fig. 9, where “0” indicates interference-free, “1” indicates contact, and “2” indicates collision. Herein, the element of (i,j) is just the element of (j,i) in opposite direction.

The statistic time-cost of image-assisted calculation is investigated by implement this task 10 times. For single calculation, the image-assisted algorithm is called 720 time, and reporting 492 times interference-free and 228 times collision, of which the average accumulate time costs are 14287.85 and 9005.168 milliseconds respectively, and the average single calculation times are 28.837 and 39.496 milliseconds respectively.

4.3 Discussion

Although this method can effectively to identify collisions, it still has two drawbacks subject to computational principle. One is invalid to distinguish the contact for bolt-connect since the overlap area of threads not is a curve shape. The other one is might identify the contact as interference-free, which due to the contact area might be divided into non-overlap pixels during the rasterization of OpenGL. For instance, the actually contact of 5–13 (bearing on output shaft) is judged to interference-free as show in Fig. 9. Normally, this kind of misjudge will not disturb the correct working of interference matrix in practical application.

This work developed an image-based interference collision detection algorithm for interference matrix establishment that utilized for assembly process planning. The main contributions are concluded as follow.

Firstly, a mathematic model of collision detection based on visibility principle is developed for interference matrix element establishing. Compare with the traditional geometric collision detection method that fixing one object and moving the other object with small steps, the visibility of image-assisted method ensures the completeness of the swept volume of moving object and finishes collision detection by once compute.
Secondly, the complete procedure and parameters specification model of image-assisted method is performed by OpenGL to ensure its generality and portability. Several skills are adopted to improve the compute efficiency, i.e., the spatial relative position calculation is finished by depth testing and stencil test with orthogonal projection, unnecessary geometries is culled to reduce rendering loading, and occlusion query function is involved to judge interference-free by avoid slowly stencil buffer data translation.
Unlike traditional geometric collision detection can only identify two parts are interference, the image-assisted method can further distinguish the two assemble parts are surface contact or entity collision. It is simple to finish by transforming stencil buffer as an image and performing erosion process with specific threshold.
The shaft-bearing assembly example proofs the developed method can identify whether contact and collision for interference case, while the assembly interference matrix establishment for gear box demonstrates the effectiveness of this method. However, this method still exists the drawback that might misjudging some contacts as interference-free.

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

Funding This work was supported by the Natural Scientific Foundation of China [Grant No. 52075427], and State Key Laboratory of Smart Manufacturing for Special Vehicles and Transmission System [Grant No. GZ2022KF013].

Authors’ contribution Kang Jia proposed the research idea and formulated the content. Hao Liu proposed the technical schema on OpenGL. Junkang Guo was responsible for the numerical case study. Tao Ma and Lei Zhang were involved in the discussion and significantly contributed to making the final draft of the article. Jun Hong designed the numerical case study. All the authors read and approved the final manuscript.

Data availability The authors confirm that the data supporting the findings of this study are available within article.

Compliance with ethical standards

Competing interests The authors declare that they have no competing interests.

Ethical approval Not applicable.

Consent to participate Not applicable.

Consent to publish Not applicable.

Liu J, Sun Q, Cheng H, et al. The state-of-the-art, connotation and development trends of the products assembly technoogy [J]. Journal of Mechanical Engineering, 2018, 54(11): 1-27.
Yu J P , Wang C E , Zhang W L . Automatic acquiring method for assembly relation matrix of complex product[J]. JComputer Integrated Manufacturing Systems, 2010, 16(2):249-255+270.
Shahi V J , Masoumi A , Franciosa P , et al. A quality-driven assembly sequence planning and line configuration selection for non-ideal compliant structures assemblies[J]. International Journal of Advanced Manufacturing Technology, 2020:1-16.
Peng G, Hou,X, Wu C, et al. Fast collision detection approach to facilitate interactive modular fixture assembly design in a virtual environment [J]. Int J Adv Manuf Technol, 2010, 46: 315–328.
Alfadhlani, T. M. A. Ari Samdhi, Anas Marus, Isa Setiasyah Toha. Automtic collision detection for assembly sequence planning using a three-dimensional solid model [J]. Journal of Advanced Manufacturing Systems, 2011, 10(2): 277-291.
Zhang W , Ma M , Li H , et al. Generating interference matrices for automatic assembly sequence planning[J]. The International Journal of Advanced Manufacturing Technology, 2017, 90(1):1187-1201.
Schns F , Hartmann D , Obst B , et al. GPU accelerated voxel-based machining simulation[J]. 2021, 115: 275-289.
Baciu G , Wong W , Sun H Q . RECODE: an image-based collision detection algorithm[C]. Conference on Computer Graphics & Applications. IEEE, 2015.
Govindaraju N K, Redon S, Lin M C, et al. CULLIDE: interactive collision detection between complex models in large environments using graphics hardware[C]. International Conference on Computer Graphics and Interactive Techniques. ACM, 2005.
Zhou Y, Xu Q, Xiao Y. Research on collision detection algorithm based on z-buffer [J]. Computer Engineering, 2007, 33(12): 214:216.
Sun C, Li P, Xiong W, Wang H. Collison detection algorithm based on double view and semi-transparent color overlap [J]. Computer Integrated Manufacturing Systems, 2019, 25(2): 350-357.
Liu X,Wang D, Chen D, et al. Fast algorithm for collison detection in complicated scene and GPU acceleration [J]. Computer Enigneering and Design, 2012, 33(5): 1847-1851.
KIM D, HEO J-P, HUH J, et al. HPCCD: Hybrid Parallel Continuous Collision Detection using CPUs and GPUs [J]. Computer Graphics Forum, 2009, 28(7): 1791-800.
Yu H, Ma Y, Zhang T, Chen G. Fast collision detection algorithm based on image space [J]. Journal of Computer Applications, 2013, 33(2): 530-533.
ABECASSIS F, LAVERNHE S, TOURNIER C, et al. Performance evaluation of CUDA programming for 5-axis machining multi-scale simulation [J]. Computers in Industry, 2015, 71: 1-9.
Zheng W, Ma M, Li H. Method for assembly interference detection based on MRT [j]. Computer Integrated Manufacturing Systems, 2017, 26(6): 1253-1262.

Download PDF

Journal Publication

published 10 Apr, 2023

Read the published version in The International Journal of Advanced Manufacturing Technology →

Editorial decision: Minor Revisions Needed
31 Dec, 2022
Reviewers agreed at journal
03 Oct, 2022
Reviewers invited by journal
30 Sep, 2022
Editor assigned by journal
28 Sep, 2022
First submitted to journal
27 Sep, 2022

You are reading this latest preprint version

Image-assisted Collision Detection for Calculation of Assembly Interference Matrix

Status:

Journal Publication

Version 1

Abstract

Figures

1 Introduction

2 Rough Stage For Interference Matrix Establishment

3 Image-assisted Collision Detection For Interference Matrix Element Identification

3.1 Principle of image-assisted collision detection

3.2 Detail calculation model based on OpenGL

3.2.1 Preparation of rendering

3.2.2 Procedure of OpenGL-assist implicit calculation

3.2.3 Identification of contact condition

4 Case Study And Discussion

4.1 Example of shaft-hole assembly

4.2 Example of worm gear box

4.3 Discussion

5 Conclusions

Declarations

References

Status:

Journal Publication

Version 1