Abstract
This paper describes a complete method to detect collision among CSG modeled objects within a computer animation system. Since objects that are modeled with the constructive solid geometry paradigm can have very complex shapes, especially when they consist of curved primitives, collision detection is performed in three stages. Bounding volumes in each node of the CSG tree are used to determine whether a collision is likely to occur between each pair of objects. If overlapping bounds are discovered, spatial subdivision is used to reduce the complexity of the CSG objects for further analysis. In those voxels, which cover parts of both objects, a redundancy test is performed for each primitive to determine whether the objects interpenetrate. Curved primitives are adaptively approximated by circumscribed and inscribed polyhedrons.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Baraff, D., “Analytical Methods for Dynamic Simulation of Non-penetrating Rigid Bodies”, Computer Graphics, Vol. 23, No. 3, pp. 223–232, July 1989.
Baraff, D., “Curved Surfaces and Coherence for Non-penetrating Rigid Body Simulation”, Computer Graphics, Vol. 24, No. 4, pp. 19–28, August 1990.
Baraff, D., “Non-penetrating Rigid Body Simulation”, State ofthe Art Reports of EUROGRAPHICS’93, Eurographics Technical Report Series, 1993.
Beacon, G., Dodsworth, J., Howe, S., Oliver, R., Saia, A., “Boundary Evaluation Using Inner and Outer Sets: The ISOS Method”, IEEE Computer Graphics amp; Applications, Vol. 9, No. 2, pp. 39–51, March 1989.
Cameron, S., “Efficient Intersection Tests for Objects Defined Constructively”, The International Journal of Robotics Research, Vol. 8, No. 1, pp. 3–25, February 1989.
Cameron, S., “Efficient Bounds in Constructive Solid Geometry”, IEEE Computer Graphics amp; Applications, Vol. 11, No. 3, pp. 68–74, May 1991.
Canny, J., “Collision Detection for Moving Polyhedra”, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. PAMI-8, No. 2, pp. 200 - 209, March 1986.
Duff, T., “Interval Arithmetic and Recursive Subdivision for Implicit Functions and Constructive Solid Geometry”, Computer Graphics, Vol. 26, No. 2, pp. 131–138, July 1992.
Elber, G., Shpitalni, M., “Octree creation via C.S.G definition”, The Visual Computer, Vol. 4, No. 2, pp. 53–64, July 1988.
Gröller, E., Coherence in Computer Graphics, PhD thesis, Technical University of Vienna, September 1992.
Hahn, J., “Realistic Animation of Rigid Bodies”, Computer Graphics, Vol. 22, No. 4, pp. 299–308, August 1988.
Lin, M., Canny, J., “Efficient Collision Detection for Animation”, Proceedings of Third Eurographics Workshop on Animation and Simulation, Eurographics Technical Report Series, 1992.
Miller, J., “Analysis of Quadric-Surface-Based Solid Models”, IEEE Computer Graphics amp; Applications, Vol. 8, No. 1, pp. 28–42, January 1988.
Moore, M., Wilhelms, J. “Collision Detection and Response for Computer Animation”, Computer Graphics, Vol. 22, No. 4, pp. 289–298, August 1988.
Pueyo, X., Tost, D., “A Survey of Computer Animation”, Computer Graphics Forum, Vol. 7, No. 4, pp. 281–300, 1988.
Terzopoulos, D., Platt, J., Barr, A., Fleischer, K., “Elastically Deformable Models”, Computer Graphics, Vol. 21, No. 4, pp. 205–214, July 1987.
Thalmann, D., “Dynamic Simulation as a Tool for Three-dimensional Animation”, in: Magnenat-Thalmann, N., Thalmann, D. (Eds.), New Trends in Animation and Simulation, John Wiley amp; Sons, pp. 257–272, 1991.
Tilove, R., “A Null-Object Detection Algorithm for Constructive Solid Geometry”, Communications of the ACM, Vol 27, No. 7, pp. 684–694, 1984.
Zeiller, M., “Collision Detection for Objects Modelled by CSG”, in: Connor, J., Hernandez, S., Murthy, T., Power, H. (Eds.), Visualization and Intelligent Design in Engineering and Architecture, Computational Mechanics Publications and Elsevier Science Publishers, pp. 165–180, 1993.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Purgathofer, W., Zeiller, M. (1995). CSG Based Collision Detection. In: Straßer, W., Wahl, F. (eds) Graphics and Robotics. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-79210-6_4
Download citation
DOI: https://doi.org/10.1007/978-3-642-79210-6_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-58358-5
Online ISBN: 978-3-642-79210-6
eBook Packages: Springer Book Archive