A linear complexity intersection algorithm for discrete element simulation of arbitrary geometries

Engineering Computations - Tập 12 Số 2 - Trang 185-201 - 1995
John Williams1, R. O’Connor1
1(Intelligent Engineering Systems Laboratory (IESL), Department of Civil and Environmental Engineering, Massachusetts Institute of Technology, Cambridge, MA 02139, USA)

Tóm tắt

We present an algorithm for contact resolution that is valid for a wide variety of polygonal two dimensional shapes and is of linear computational complexity. The algorithm is designed for use in discrete element analysis of granular and multibody systems exhibiting discontinuous behaviour. Contact detection usually consists of a spatial sorting phase and a contact resolution phase. The spatial sorting phase seeks to avoid an all‐to‐all body comparison by culling the number of objects which are potential contactors of a given object. The contact resolution phase resolves the details of the contact between two given objects. The algorithm presented here (called DFR) addresses the contact resolution phase and is applicable to convex geometries and to a restricted set of concave geometries. Examination of the algorithm establishes an upper bound linear computational complexity, of order O(N), with respect to the number of points (N) used to define the object boundary. The DFR algorithm is combined with a modified heapsort algorithm for spatial sorting of M bodies which has complexity O(M log M) and is applied to a baseline granular simulation problem to test its efficiency.

Từ khóa


Tài liệu tham khảo

Burington R., 1965, Handbook of Mathematical Tables and Formulas, 4

Craig J. J., 1986, Introduction to Robotics: Mechanics and Control

10.1680/geot.1979.29.1.47

Dworkin, P. Efficient Collision Detection for Real-Time Simulated Environments, Master of Science Thesis,Media Lab, Massachusetts Institute of Technology (1994)

Mustoe G. G. W., 1985, Proc. ART1C '85 San Francisco

Williams J. R., 1987, Proc. of NUMETA 1987

Greengard L. F., 1987, ACM Distinguished Dissertation

10.1145/378456.378530

10.1016/0032-5910(93)02748-Y

Shi, 1993, Gen hua. Block System Modeling by Discontinuous Deformation Analysis

Kernighan B. W., 1988, The C Programming Language, 2

Knuth D. E., 1973, The Art of Computer Programming

Kreyszig E., 1983, Advanced Engineering Mathematics, 5

10.1145/378456.378528

Plauger P. J., 1992, The Standard C Library, 1

10.1145/37402.37406

Rogers D., 1985, Procedural Elements for Computer Graphics

Sedgewick R., 1990, Algorithms in C

Swegle, J. W. Search algorithm. Technical Report, Sandia National Laboratories, Solid and Structural Mechanics Dept., Albuquerque, NewMexico 87185 (1993), External Distribution Memo.

Press W. H., 1988, Numerical Recipes in C, 1

10.1002/nag.1610170902

10.1108/eb023858

Williams J. R., 1989, Proc. ASCE Structures

Thông tin
Thông tin xuất bản

Engineering Computations

Tập 12 Số 2

185-201

Thông tin tác giả