logo

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

More info
  • ReceivedJan 3, 2018
  • AcceptedJun 28, 2018
  • PublishedApr 10, 2019

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 (PB(2), aA(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<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. 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<Cpoint>

    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<Cpolygon>

    polyList

    The boundary polygons of this block with normal vector pointed to inner block, i.e. A(2) in Table2 (Figure 4(c))

    List<Cangle>

    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<Cdihedral>

    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, int(A)={xA and xA}

    A(0)

    The vertex of A, e.g. A(0)={a1, a2, ...ak}

    A(1)

    The boundary edge of A, e.g. A(1)=a1a2a2a3∪...∪ap--1apapa1

    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, 0<r<u+1 and eu+1=e1

    S

    A plane

    V

    A space

    ni

    ni=(xi, yi, zi) is a vector from (0,0,0) to (xi, yi, zi). It often refers to an inner normal vector, which is normalto a boundary polygon or plane and points to the inside of the 3D block

    mj

    mj=(xj, yj, zj) is a vector. It often refers to an inner normal vector which is normal to a boundary edge andpoints to the inside of the 2D polygon

    er

    er is a vector parallel to the r edge of block A

    hs

    Hs is a vector parallel to the s edge of block B

    ||

    Parallel, e.g. ni||nj means ni=tnj, t is a real number

    Parallel and in the same direction, e.g. ni↑↑nj means ni=tnj, t>0

    Normal, e.g. ⊥ni is a plane passing (0,0,0), ni is the normal vector of the plane

    At the same side, ninj 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=ba

    Edge (Figure 6(a))

    L(ab)

    ab=a+0t1t(ba)

    Plane passing point O

    nr

    nr={xnr=0}

    Plane passing a0

    S

    S=a0+(nr)

    Half space passing point O

    nr

    nr={xnr=0}

    Convex polygon

    (Figure 6(b))

    P

    P=SA,  S=nr

    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+B=aAbB(a+b)

    A block

    bB(b)

    A point

    a±b

    a±b=(xi±xj,  yi±yj,  zi±zj)

    A point

    A±b

    Figure 2(a)

    A±b=aA(a±b)

    A block

    P±a0

    Figure 2(b)

    P(a1, a2, ..., ak)±a0=P(a1±a0, a2±a0, ..., ak±a0)

    A polygon

    ab±cd

    Figure 9

    ab±cd=P(a±c, b±c, b±d, a±d)

    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.

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

京ICP备17057255号       京公网安备11010102003388号