SCIENCE CHINA Technological Sciences, Volume 62 , Issue 8 : 1438-1454(2019) https://doi.org/10.1007/s11431-018-9318-2

## A compact 3D block cutting and contact searching algorithm

• AcceptedJun 28, 2018
• PublishedApr 10, 2019
Share
Rating

### Abstract

The geometry relation and the contact point-pairs detection between two three dimensional (3D) objects with arbitrary shapes are essential problems involved in discontinuous computation and computational geometry. This paper reported a geometry relation judgment and contact searching algorithm based on Contact Theory. A contact cover search algorithm is proposed to find all the possible contact cover between two blocks. Two blocks can come to contact only on these covers. Each contact cover can define a possible contact point-pair between two blocks. Data structure and flow chart are provided, as well as some examples in details. Contact problems involving concave blocks or parallel planes are considered to be very difficult in past and are solved by this algorithm. The proposed algorithm is compacted and applicable to the discontinuous computation, such as robotic control, rock mass stability, dam stability etc. A 3D cutting and block searching algorithm is also proposed in this study and used to search the outer boundary of the 3D entrance block when 3D concave blocks are encountered. The 3D cutting and block searching algorithm can be also used to form the block system for jointed rock.

### Funded by

the National Natural Science Foundation of China(Grant,Nos.,51479001,41471052)

and the China Institute of Water Resources and Hydropower Research Research & Development Support Program(Grant,Nos.,GE0145B462017,GE0145B692017)

### Acknowledgment

This work was supported by the National Natural Science Foundation of China (Grant Nos. 51479001, 41471052), and the China Institute of Water Resources and Hydropower Research Research & Development Support Program (Grant Nos. GE0145B462017, GE0145B692017). Many thanks are given to Dr. Shi GenHua for his guidance and encourage in this research.

### Supplement

Supporting Information

The supporting information is available online at tech.scichina.com and link.springer.com. The supporting materials are published as submitted, without typesetting or editing. The responsibility for scientific accuracy and content remains entirely with the authors.

### References

[1] Shi G H. Contact theory. Sci China Technol Sci, 2015, 58: 1450-1496 CrossRef Google Scholar

[2] Zhong Z H, Nilsson L. A contact searching algorithm for general contact problems. Comput Struct, 1989, 33: 197–209. Google Scholar

[3] Benson D J, Hallquist J O. A single surface contact algorithm for the post-buckling analysis of shell structures. Comput Methods Appl Mech Eng, 1990, 78: 141-163 CrossRef ADS Google Scholar

[4] Belytschko T, Neal M O. Contact-impact by the pinball algorithm with penalty and Lagrangian methods. Int J Numer Meth Engng, 1991, 31: 547-572 CrossRef ADS Google Scholar

[5] Bonnet J, Peraire J. An alternating digital tree (ADT) algorithm for 3D geometric searching and intersection problem. Int J Numer Methods Eng, 1991, 31: 1–17. Google Scholar

[6] Williams J R, O’Connor R. A linear complexity intersection algorithm for discrete element simulation of arbitrary geometries. Eng Computations, 1995, 12: 185-201 CrossRef Google Scholar

[7] Perkins E, Williams J R. A fast contact detection algorithm insensitive to object sizes. Eng Computations, 2001, 18: 48-62 CrossRef Google Scholar

[8] Munjiza A, Andrews K R F. NBS contact detection algorithm for bodies of similar size. Int J Numer Meth Engng, 1998, 43: 131-149 CrossRef Google Scholar

[9] Diekmann R, Hungershofer J, Lux M. Efficient contact search for finite element analysis. In: Proceedings of the European Congress on Computational Methods in Applied Sciences and Engineering. Barcelona, 2000. Google Scholar

[10] Wu W, Zhu H, Zhuang X, et al. A Multi-shell cover algorithm for contact detection in the three dimensional discontinuous deformation analysis. Theor Appl Fract Mech, 2014, 72: 136-149 CrossRef Google Scholar

[11] Cundall P A. Formulation of a three-dimensional distinct element model-Part I: A scheme to detect and represent contacts in a system composed of many polyhedral blocks. Int J Rock Mecha Mining Sci Geomech, 1988, 25: 107–116. Google Scholar

[12] Jelenic G, Crisfield M A. Non-linear master-slave relationships for joints in 3D beams with large rotations. Comp Meth Appl Mech Eng, 1996, 135: 211–228. Google Scholar

[13] Li S, Zhao M, Wang Y, et al. A new numerical method for dem-block and particle model. Int J Rock Mech Min Sci, 2004, 41: 436 CrossRef Google Scholar

[14] Chen W S, Zheng H, Cheng Y M, et al. Detection of 3D rock block contacts by penetration edges. Chin J Rock Mech Eng, 2004, 23: 565–571. Google Scholar

[15] Nezami E G, Hashash Y M A, Zhao D, et al. Shortest link method for contact detection in discrete element method. Int J Numer Anal Meth Geomech, 2006, 30: 783-801 CrossRef ADS Google Scholar

[16] Wu J H. New edge-to-edge contact calculating algorithm in three-dimensional discrete numerical analysis. Adv Eng Software, 2008, 39: 15-24 CrossRef Google Scholar

[17] Keneti A R, Jafari A, Wu J H. A new algorithm to identify contact patterns between convex blocks for three-dimensional discontinuous deformation analysis. Comput Geotechnics, 2008, 35: 746-759 CrossRef Google Scholar

[18] He L. Three Dimensional Numerical Manifold Method and Rock Engineering Applications. Dissertation for Dcotoral Degree. Singapore: Nanyang Technological University, 2010. Google Scholar

[19] Ahn T Y, Song J J. New contact-definition algorithm using inscribed spheres for 3D discontinuous deformation analysis. Int J Comput Methods, 2011, 08: 171-191 CrossRef Google Scholar

[20] An X, Ma G, Cai Y, et al. A new way to treat material discontinuities in the numerical manifold method. Comput Methods Appl Mech Eng, 2011, 200: 3296-3308 CrossRef ADS Google Scholar

[21] Konyukhov A, Schweizerhof K. Geometrically exact theory for contact interactions of 1D manifolds. Algorithmic implementation with various finite element models. Comput Methods Appl Mech Eng, 2012, 205-208: 130-138 CrossRef ADS Google Scholar

[22] Mousakhani M, Jafari A. A new model of edge-to-edge contact for three dimensional discontinuous deformation analysis. GeoMech GeoEng, 2016, 11: 135-148 CrossRef Google Scholar

[23] Nejati M, Paluszny A, Zimmerman R W. A finite element framework for modeling internal frictional contact in three-dimensional fractured media using unstructured tetrahedral meshes. Comput Methods Appl Mech Eng, 2016, 306: 123-150 CrossRef ADS Google Scholar

[24] Jiang Q, Chen Y, Zhou C, et al. Kinetic energy dissipation and convergence criterion of discontinuous deformations analysis (DDA) for geotechnical engineering. Rock Mech Rock Eng, 2013, 46: 1443-1460 CrossRef ADS Google Scholar

[25] Jiao Y Y, Zhang H Q, Tang H M, et al. Simulating the process of reservoir-impoundment-induced landslide using the extended DDA method. EngGeol, 2014, 182: 37-48 CrossRef Google Scholar

[26] Fan H, He S. An angle-based method dealing with vertex-vertex contact in the two-dimensional discontinuous deformation analysis (DDA). Rock Mech Rock Eng, 2015, 48: 2031-2043 CrossRef ADS Google Scholar

[27] Zheng H, Zhang P, Du X. Dual form of discontinuous deformation analysis. Comput Methods Appl Mech Eng, 2016, 305: 196-216 CrossRef ADS Google Scholar

[28] Sun Y, Feng X, Xiao J, et al. Discontinuous deformation analysis coupling with discontinuous galerkin finite element methods for contact simulations. Math Problems Eng, 2016, 2016: 1-25 CrossRef Google Scholar

[29] Wang T, Zhou W, Chen J, et al. Simulation of hydraulic fracturing using particle flow method and application in a coal mine. Int J CoalGeol, 2014, 121: 1-13 CrossRef Google Scholar

[30] Guo Y, Curtis J S. Discrete element method simulations for complex granular flows. Ann Rev Fluid Mech, 2015, 47: 21–46. Google Scholar

[31] Feng Y T, Han K, Owen D R J. A generic contact detection framework for cylindrical particles in discrete element modelling. Comput Methods Appl Mech Eng, 2017, 315: 632-651 CrossRef ADS Google Scholar

[32] Shi G H. Manifold method. In: Proceedings of the First International Forum on Discontinuous Deformation Analysis (DDA) and Simulations of Discontinuous Media. Bekerley, 1996. 52–204. Google Scholar

[33] Ma G, An X, He L. The numerical manifold method: A review. Int J Comput Methods, 2010, 07: 1-32 CrossRef Google Scholar

[34] Zheng H, Liu F, Du X. Complementarity problem arising from static growth of multiple cracks and MLS-based numerical manifold method. Comput Methods Appl Mech Eng, 2016, 295: 150-171 CrossRef ADS Google Scholar

[35] Fan H, Zhao J, Zheng H. A high-order three-dimensional numerical manifold method enriched with derivative degrees of freedom. Eng Anal Bound Elem, 2017, 83: 229-241 CrossRef Google Scholar

[36] Minkowski H. Volumen and oberflache. Mathematische Annalen, 1903, 57: 447–495. Google Scholar

[37] Zheng H, Li X. Mixed linear complementarity formulation of discontinuous deformation analysis. Int J Rock Mech Min Sci, 2015, 75: 23-32 CrossRef Google Scholar

• Figure 1

(Color online) Simplification of the geometric relation between a triangle block A and a triangle block B. (a) Relation between block A and block B; (b) relation between E(A,B) and a0; (c) relation between ∂E(A, B) and a0; (d) the distance between two blocks and contact point pairs.

• Figure 2

The operation of A+b, where b is a point. (a) A is a point; (b) A is a polygon; (c) A is a block.

• Figure 3

(Color online) An example of E(A, B) where A is a disk and B is a square.

• Figure 4

(Color online) The definition of a 3D block A. (a) The vertexes, A(0); (b) the edges, A(1); (c) the boundary polygons, A(2).

• Figure 5

The definition of a 3D solid angle $∡$e1e2e3. (a) Solid angle with vertex of a; (b) boundary face P1; (c) boundary face P2; (d) boundary face P3.

• Figure 6

(Color online) Geometric objects and their expressions of point set. (a) Edge; (b) polygon; (c) tetrahedron; (d) concave polygon and its sub convex polygons; (e) concave block and its sub convex blocks.

• Figure 10

Flow chart of searching the contact covers (subroutine Covers_solve).

• Figure 11

Flow chart for solving the contact convers of the angle to face contacts, i.e. for C(0,2).

• Figure 12

Flow chart for solving the contact covers of the edge-edge contacts, i.e. for C(1,1).

• Figure 7

(Color online) Angle to face contact (P$⊂$B(2), a$⊂$A(0), a0=a).

• Figure 9

An edge ab sum another edge cd. (a) ab is not parallel to cd (b) ab || cd.

• Figure 8

(Color online) Edge to edge contact. (a) Edge er of dihedral angel A contacts with edge hs of dihedral angel B; (b) dihedral angles A and B.

• Figure 13

The flow chart for searching the contact covers.

• Figure 14

Numbering system of two identical blocks A and B. (a) Angle numbering system; (b) dihedral numbering system; (c) polygon numbering system.

• Figure 15

(Color online) An example for searching the boundary polygon of the entrance block, i.e. the contact cover (for case of i = 1). (a) The solid 3D angle of block A; (b) one of the boundary polygon of block B, Pj with j = 2; (c) a case against eq. (8) (Pj, j=3); (d) a case satisfying eq. (8) (Pj, j=4).

• Figure 16

(Color online) Top view of the solved boundary polygons (or contact covers) on ∂E(A, B). (a) Four covers from C(0,2); (b) four covers from C(2,0).

• Figure 17

(Color online) Top view of a closed E(A, B), which contains 4 covers from C(0,2), 4 covers from C(2,0) and 6 covers from C(1,1).

• Figure 18

(Color online) Numbering system of cubic A, B.

• Figure 19

(Color online) Finite contact covers on the front face of the entrance block of two cubic (A=B).

• Figure 20

(Color online) Overlapped contact covers on ∂E(A, B) of two regular octahedrons.

• Figure 21

The flow chart for solving 3D entrance block E(A, B).

• Figure 22

(Color online) E(A, B) between a 2D concave block and a 2D convex block.

• Figure 23

(Color online) E(A, B) between two 3D blocks.

• Figure 24

(Color online) Application of contact searching algorithm in a rock fall analysis. (a) Initial state; (b) 1000 step; (c) 2000 step.

• Table 1   Data structure for the representation of geometry objects (language: C#)
 Class name Geometry Data type Variables Meaning Cpoint Point or vector, e.g. a, ei, nk Integer ID Vertex No. Double x, y, z Coordinate values Cpine Oriented edge, e.g. ab Integer ID Edge No. Cpoint p0, p1 Start and end Cpoint vector Direction of line Cpolygon Oriented polygon, e.g.Figures 4(c) and 6(b) Integer ID Polygon No. List plist Vertexes ordered in anti-clockwise direction Cpoint inner An inner point, which is often used as the reference point of this polygon Cpoint vector The inner normal vector of the polygon, i.e. n Cdihedral Solid dihedral angel, e.g.Figure 8(b) Integer ID The dihedral angle No. Bool isConcave Indicator of concave dihedral angel Cline edge The edge of dihedral angle. Its direction is er Cpoint n0, n1 The inner normal vectors of the two boundary face, i.e. n11 n12 Cpoint v0, v1 The vector that is perpendicular to the edge vector and inner the boundary face, i.e. e1 e2 Cangle 3D solid angle, e.g. Figure 7 Integer ID The solid angle No. Cpoint vertex The vertex of the angle, which is often used as the reference point of this angle Bool isConcave Indicator of concave angle List vectorlist The boundary vectors ordered in right hand rule, i.e. ei List< Cpoint > nodelist The node related to this angle and ordered in right hand rule Cblock 3D block, e.g. Figure 6(c) and (e) Integer ID The block No. Cpoint a0 An inner point, which is often used as the reference point of this angle Bool isConcave Indicator of concave block List polyList The boundary polygons of this block with normal vector pointed to inner block, i.e. A(2) in Table2 (Figure 4(c)) List angleList The solid angles at the vertexes of this block that corresponds to the vertexes belonging to A(0) in Table2 (Figure 4(a)) List diheList The dihedral angles containing the block edges that correspond to the edges belonging to A(1) in Table2 (Figure 4(b))
• Table 2   Symbols used in this paper (after ref. )
 Symbol Physical meaning E(A, B) The entrance block with a definition of E(A, B)={a0+x|(A+x)∩B≠Ø} A, B 1D, 2D, 3D geometry object, e.g. point, edge, polygon, block, etc. $∂A,∂B$ The boundaries of A,B int(A) The inner points of A, A(0) The vertex of A, e.g. A(1) The boundary edge of A, e.g. A(1)=a1a2∪a2a3∪...∪ap--1ap∪apa1 A(2) The boundary polygon of A x, y, z, t Real number i, j, k, r, s, u, v, w Natural number x Point x={x, y, z} a Point a={xi, yi, zi} b Point b={xj, yj, zj} L(ab), or ab An edge from a to b P(a1a2...akak+1) A polygon with ordered vertexes a1a2...akak+1 with ak+1=a1 D(P1, P2) A dihedral angle with the two outer boundary surfaces of P1and P2 B(P1, P2, ..., Pk) A 3D block with outer boundary surfaces of P1, P2, ..., Pk B(D1, D2, ..., Dk) A 3D block containing inner dihedral angles of D1, D2, ..., Dk $∡$e1e2...eueu+1 A solid angle with boundary edges er, 00 $⊥$ Normal, e.g. ⊥ni is a plane passing (0,0,0), ni is the normal vector of the plane $↑$ At the same side, ni↑nj means ninj≥0
• Table 3   The representation of 3D geometric objects in form of point sets
 Geometric object Symbol Point set expression Point a a Vector (Figure 6(a)) $e1$ $e1=b−a$ Edge (Figure 6(a)) $L(ab)$ $ab=a+∪0≤t≤1t(b−a)$ Plane passing point O $⊥nr$ $⊥nr={x⋅nr=0}$ Plane passing a0 S $S=a0+(⊥nr)$ Half space passing point O $↑nr$ $⊥nr={x⋅nr=0}$ Convex polygon(Figure 6(b)) P $A=∩k=1,2...f(mk+ak)$ Half space with boundary passing a0 V $V=a0+↑nr$ Convex block (Figure 6(c)) A or B $A=∩k=1,2...f(nk+ak)$, where $k∈{1,⋯,u}$; nk is the inner normal vector of boundary polygon Pk, which is pointing to the inner of block A; ak is a point on the boundary polygon Pk Concave polygon (Figure 6(d)) P $P=∪1C1$, where Ci is the i sub convex polygon, $i∈{1,⋯,u}$, and u is the number of thesub convex polygon Concave block (Figure 6(e)) A or B $A=∪1C1$, where Ci is the i sub convex block, $i∈{1,⋯,u}$, and u is the number of thesub convex block
• Table 4   The sum or inverse operation between two simple point sets
 Operation Figure Rule Result $+$ A block $−$ $∪b∈B(−b)$ A point a±b A point A±b Figure 2(a) $A±b=∪a∈A(a±b)$ A block P±a0 Figure 2(b) A polygon ab±cd Figure 9 A parallelogram
• Table 5   The searching process for (0,2) in case of = 1
 j j Fg (eq. (14)) isBp (eq.(15)) 1 1 =0 False 2 =0 3 >0 2 1 >0 False 2 <0 3 <0 3 1 <0 True 2 <0 3 <0 4 1 <0 False 2 >0 3 <0
• Table 6   The searching process for (1,1) when =1 ((b))
 j $Fg$ (eq. (18)) $isBP$ (eq. (18)) Sketch 1 False(Parallel condition) i1 -- i2 -- j1 -- j2 -- 3 False i1 >0 i2 0 j1 0 j2 >0 6 True i1 >0 i2 >0 j1 <0 j2 <0
• Table 7   The result for solving the boundary polygons of edge-edge contacts, i.e. (1,1)
 i j Sketch 1 5 2 6 3 4 4 3 5 1 6 2
• Table 8   The contact covers on the front face of (, ) (referring to and )
 C(0,2) C(2,0) C(1,1) i j j i k1 k2 k1 k2 3 3 5 1 7 2 6 5 4 3 5 2 8 2 12 5 7 3 5 5 6 3 7 9 8 3 5 6 12 3 8 9

i is the angle ID; j is the polygon ID, k1 is the first dihedral ID; k2 is the second dihedral ID.

Citations

• #### 0

Altmetric

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有