Fast and robust GPU-based point-in-polyhedron determination. (June 2017)

• Record Type: Journal Article
• Authors: Li, Jing; Wang, Wencheng
• Is Part Of: Computer aided design. Volume 87(2017)
• Page Start: 20
• Page End: 28
• Publication Date: 2017-06
• Subjects: Point-in-polyhedron test -- GPU -- 3D uniform grids -- Ray-crossing; Computer-aided design -- Periodicals; Engineering design -- Data processing -- Periodicals; Computer graphics -- Periodicals; Conception technique -- Informatique -- Périodiques; Infographie -- Périodiques; Computer graphics; Engineering design -- Data processing; Periodicals; Electronic journals; 620.00420285
• DOI: 10.1016/j.cad.2017.02.001
• Languages: English
• ISSNs: 0010-4485

Abstract

Abstract: This paper presents a fast and robust GPU-based point-in-polyhedron determination method. The method partitions the bounding box of the polyhedron into a grid with O ( N ) cells, where N is the number of polyhedron faces, and predetermines the inclusion property of the grid cells' center points. Then, a line segment is generated from the query point to the center point of its related grid cell to determine the inclusion property of the query point by counting the faces intersected by the line segment. Such a localization treatment is further exploited to optimize the visiting pattern in using GPUs, by which a high increase in the testing speed is achieved. We also provide a unified solution to all singular cases, especially those caused by localization, to guarantee the efficiency and robustness for point-in-polyhedron tests. The results show that our proposed method can be faster than both state-of-the-art serial and parallel methods by several orders of magnitude, with only a slight increase in storage requirement. Highlights: We propose a novel fast and robust point-in-polyhedron test method. The method is robust with singularities well handled. The method can be easily implemented efficiently on GPUs. Results show the method can be several magnitudes faster than existing techniques.