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.
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)
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.
Supporting Information
The supporting information is available online at
[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
Figure 2
The operation of
Figure 3
(Color online) An example of
Figure 4
(Color online) The definition of a 3D block
Figure 5
The definition of a 3D solid angle
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
Figure 12
Flow chart for solving the contact covers of the edge-edge contacts, i.e. for
Figure 7
(Color online) Angle to face contact (
Figure 9
An edge
Figure 8
(Color online) Edge to edge contact. (a) Edge
Figure 13
The flow chart for searching the contact covers.
Figure 14
Numbering system of two identical blocks
Figure 15
(Color online) An example for searching the boundary polygon of the entrance block, i.e. the contact cover (for case of
Figure 16
(Color online) Top view of the solved boundary polygons (or contact covers) on ∂
Figure 17
(Color online) Top view of a closed
Figure 18
(Color online) Numbering system of cubic
Figure 19
(Color online) Finite contact covers on the front face of the entrance block of two cubic (
Figure 20
(Color online) Overlapped contact covers on ∂
Figure 21
The flow chart for solving 3D entrance block
Figure 22
(Color online)
Figure 23
(Color online)
Figure 24
(Color online) Application of contact searching algorithm in a rock fall analysis. (a) Initial state; (b) 1000 step; (c) 2000 step.
Class name | Geometry | Data type | Variables | Meaning |
Cpoint | Point or vector, e.g. | Integer | ID | Vertex No. |
Double | Coordinate values | |||
Cpine | Oriented edge, e.g. | Integer | ID | Edge No. |
Cpoint | p0, p1 | Start and end | ||
Cpoint | vector | Direction of line | ||
Cpolygon | Oriented polygon, e.g. | Integer | ID | Polygon No. |
List<Cpoint> | 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. | ||
Cdihedral | Solid dihedral angel, e.g. | Integer | ID | The dihedral angle No. |
Bool | isConcave | Indicator of concave dihedral angel | ||
Cline | edge | The edge of dihedral angle. Its direction is | ||
Cpoint | n0, n1 | The inner normal vectors of the two boundary face, i.e. | ||
Cpoint | v0, v1 | The vector that is perpendicular to the edge vector and inner the boundary face, i.e. | ||
Cangle | 3D solid angle, e.g. | 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<Cpoint> | vectorlist | The boundary vectors ordered in right hand rule, i.e. | ||
List< Cpoint > | nodelist | The node related to this angle and ordered in right hand rule | ||
Cblock | 3D block, e.g. | 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<Cpolygon> | polyList | The boundary polygons of this block with normal vector pointed to inner block, i.e. | ||
List<Cangle> | angleList | The solid angles at the vertexes of this block that corresponds to the vertexes belonging to | ||
List<Cdihedral> | diheList | The dihedral angles containing the block edges that correspond to the edges belonging to |
Symbol | Physical meaning |
The entrance block with a definition of | |
1D, 2D, 3D geometry object, e.g. point, edge, polygon, block, etc. | |
The boundaries of | |
int( | The inner points of |
The vertex of | |
The boundary edge of | |
The boundary polygon of | |
Real number | |
Natural number | |
Point | |
Point | |
Point | |
An edge from | |
A polygon with ordered vertexes | |
A dihedral angle with the two outer boundary surfaces of | |
A 3D block with outer boundary surfaces of | |
A 3D block containing inner dihedral angles of | |
| A solid angle with boundary edges |
A plane | |
A space | |
|| | Parallel, e.g. |
Parallel and in the same direction, e.g. | |
Normal, e.g. ⊥ | |
At the same side, |
Geometric object | Symbol | Point set expression |
Point | ||
Vector ( | ||
Edge ( | ||
Plane passing point | ||
Plane passing | ||
Half space passing point | ||
Convex polygon ( | ||
Half space with boundary passing | ||
Convex block ( | | |
Concave polygon ( | | |
Concave block ( | |
Operation | Figure | Rule | Result |
A block | |||
A point | |||
A point | |||
A block | |||
A polygon | |||
A parallelogram |
isBp ( | |||
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 |
| | Sketch | ||
1 | False (Parallel condition) | |||
-- | ||||
-- | ||||
-- | ||||
-- | ||||
3 | False | |||
>0 | ||||
0 | ||||
0 | ||||
>0 | ||||
6 | True | |||
>0 | ||||
>0 | ||||
<0 | ||||
<0 | ||||
Sketch | ||
1 | 5 | |
2 | 6 | |
3 | 4 | |
4 | 3 | |
5 | 1 | |
6 | 2 |
| | ||||||||
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 |
Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有
京ICP备17057255号 京公网安备11010102003388号