Abstract
Two-dimensional line segment–triangle intersection test is a part of some 3D triangle–triangle intersection test algorithms. It is the kind of algorithms dealing with intersection of one triangle and line segment obtained as the intersection of the other triangle with the plane which the first triangle lies on. There appeared a number of algorithms each proclaiming its efficiency against to its predecessors with respect to the number of operations. In the paper, we seek out the minimal set of operations. Applying divide and conquer paradigm, we split the operations needed into (a) fixed part consisting of core arithmetic operations and (b) variable part dealing with logical reasoning. As we come to the set of core arithmetic operations that cannot be further minified we realize previous algorithms come to the same set in spite of their different strategies. Further improvement we sought in the area of modern processor architectures. We exploit modern CPU’s parallel processing capabilities like Single instruction, multiple data vectorization, parallel—out-of-order execution and branch prediction and enlighten their strengths and weaknesses for usage in this type of algorithms.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Gottschalk, S., Lin, M.: Collision detection between geometric models: a survey. In: Proceedings of IMA Conference on Mathematics of Surfaces 1998, pp. 3–15 (1998)
Botsch, M., Pauly, M., Kobbelt, L., Alliez, P., Lévy, B., Bischoff, S., Rössl, C.: Geometric Modeling Based on Polygonal Meshes, Eurographics 2008—Tutorials. http://lgg.epfl.ch/publications/2008/botsch_2008_GMPeg.pdf. Accessed Dec 2017
Möller, T.: A fast triangle–triangle intersection test. J. Graph. Tools 2(2), 25–30 (1997)
Held, M.: ERIT—a collection of efficient and reliable intersection tests. J. Graph. Tools 2(4), 25–44 (1997)
Devillers, O., Guigu, P.: Faster triangle–triangle intersection tests. Technical report 4488, INRIA (2002)
Tropp, O., Tal, A., Shimshoni, I.: A fast triangle to triangle intersection test for collision detection. Comput. Animat. Virtual Worlds 17(50), 527–535 (2006)
Ling-yu, Wei: A faster triangle-to-triangle intersection test algorithm. Comput. Animat. Virtual Worlds 25(5–6), 553–559 (2014)
Tang, K.T.: Mathematical Methods for Engineers and Scientists—Complex Analysis. Determinants and Matrices. Springer, Berlin (2007)
Shen, J.P., Lipasti, M.H.: Modern Processor Design. Fundamentals of Superscalar Processors. Waveland Press, Long Grove (2005)
Fog, A.: Optimizing software in C++: an optimization guide for Windows, Linux and Mac platforms. Technical University of Denmark. http://www.agner.org/optimize/optimizing_cpp.pdf. Accessed Dec 2017
Intel 64 and IA-32 Architectures Optimization Reference Manual, Intel Corporation, Order Number: 248966-033 (2016)
Klosowski, J.T., Held, M., Mitchell, J.S.B., Sowizral, H., Zikan, K.: Efficient collision detection using bounding volume hierarchies of k-DOPs. IEEE Trans. Vis. Comput. Graph. 4(1), 21–36 (1998)
Acknowledgements
I express my gratitude to professor Joseph Mitchell from State University of New York at Stony Brook, for handing out the code of QuickCD algorithms to me.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
Author Simo Jokanovic declares that he has no conflict of interest.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Jokanovic, S. Two-dimensional line segment–triangle intersection test: revision and enhancement. Vis Comput 35, 1347–1359 (2019). https://doi.org/10.1007/s00371-018-01614-1
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00371-018-01614-1