Data processing: structural design – modeling – simulation – and em – Simulating nonelectrical device or system – Mechanical
Patent
1998-04-17
2000-08-08
Teska, Kevin J.
Data processing: structural design, modeling, simulation, and em
Simulating nonelectrical device or system
Mechanical
703 2, 703 6, 703 8, 701301, 345419, 345441, 345473, G06G 748
Patent
active
060995734
ABSTRACT:
A method and apparatus for modeling interactions between bodies. The method comprises representing two bodies undergoing translations and rotations by two hierarchical swept volume representations. Interactions such as nearest approach and collision can be modeled based on the swept body representations. The present invention can serve as a practical tool in motion planning, CAD systems, simulation systems, safety analysis, and applications that require modeling time-based interactions. A body can be represented in the present invention by a union of convex polygons and convex polyhedra. As used generally herein, polyhedron includes polygon, and polyhedra includes polygons. The body undergoing translation can be represented by a swept body representation, where the swept body representation comprises a hierarchical bounding volume representation whose leaves each contain a representation of the region swept by a section of the body during the translation, and where the union of the regions is a superset of the region swept by the surface of the body during translation. Interactions between two bodies thus represented can be modeled by modeling interactions between the convex hulls of the finite sets of discrete points in the swept body representations.
REFERENCES:
patent: 4890242 (1989-12-01), Sinha et al.
patent: 4944034 (1990-07-01), Ohsawa
patent: 5014230 (1991-05-01), Sinha et al.
patent: 5047916 (1991-09-01), Kondo
patent: 5056031 (1991-10-01), Nakano et al.
patent: 5056045 (1991-10-01), Ohsawa
patent: 5307282 (1994-04-01), Conradson et al.
patent: 5347459 (1994-09-01), Greenspan et al.
patent: 5515489 (1996-05-01), Yaeger
patent: 5572634 (1996-11-01), Duluk, Jr.
patent: 5625575 (1997-04-01), Goyal et al.
patent: 5808625 (1998-09-01), Picott et al.
patent: 5929864 (1999-07-01), Picott et al.
Xavier, "Fast Swept-Volume Distance for Robust Collision", 1997 IEEE International Conference on Robotics and Automation, pp. 1162-1169, Apr. 1997.
Stephen Cameron, Dealing With Geometric Complexity In Motion Planning, IEEE ICRA 1996 Workshop on Practical Motion Planning in Robotics, Minneapolis, MN, 1996.
Henry Fuchs, University of North Carolina at Chapel Hill; Zvi M. Kedem and Bruce F. Naylor, The University of Texas at Dallas, On Visible Surface Generation by a Priori Tree Structures, 1980 ACM 0-89791-021-4/80/0700-0124.
Chris L. Jackins and Steven L. Tanimoto, Oct-Trees and Their Use in Representing Three-Dimensional Objects, Computer Graphics and Image Processing, 14, 249-270 (1980).
Donald Meagher, Geometric Modeling Using Octree Encoding, Computer Graphics and Image Processing, 19, 129-147 (1982).
Bernard Faverjon, Hierarchical Object Models for Efficient Anti-Collision Algorithms, CH2750-8/89/0000 1989 IEEE.
Sean Quinlan, Efficient Distance Computation Between Non-Convex Objects, 1050-4729/94 1994 IEEE.
Yuichi Sato, Mitsunori Hirata, Tsugito Maruyama, Yuichi Arita, Efficient Collission Detection Using Fast Distance-Calculation Algorithms for Convex and Non-Convex Objects, Proceedings of the 1996 IEEE International conference on Robotics and Automation, Minneapolis, Minnesota--Apr. 1996.
S. Gottschalk, M. C. Lin, D. Manocha, OBBTree: A Hierarchical Structure for Rapid Interference Detection, Computer Graphics Proceedings, Annual Conference Series, 1996.
John Canny, Collision Detection for Moving Polyhedra, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. PAMI-8, No. 2, Mar. 1986.
Stephen Cameron, Collision Detection by Four-Dimensional Intersection Testing, IEEE Transaction on Robotics and Automation, vol. 6, No. 3, Jun. 1990.
Stephen Cameron, A Comparison of Two Fast Algorithms for Computing the Distance Between Convex Polyhedra, Submitted to IEEE TR&A as a Communications Paper, Jul. 1996.
Elmer G. Gilbert, Daniel W. Johnson and S. Sathiya Keerthi, A Fast Procedure for Computing the Distance Between Complex Objects in Three-Dimensional Space, IEEE Journal of Robotics and Automation, vol. 4, No. 2, Apr. 1988.
Patrick G. Xavier, A Generic Algorithm for Constructing Hierarchical Representations of Geometric Objects, 1996 IEEE International Conference on Robotics and Automation.
Broda Samuel
Grafe V. Gerald
Sandia Corporation
Teska Kevin J.
LandOfFree
Method and apparatus for modeling interactions does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for modeling interactions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for modeling interactions will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1145926