کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4952601 1442477 2017 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Fast and robust GPU-based point-in-polyhedron determination
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر گرافیک کامپیوتری و طراحی به کمک کامپیوتر
پیش نمایش صفحه اول مقاله
Fast and robust GPU-based point-in-polyhedron determination
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computer-Aided Design - Volume 87, June 2017, Pages 20-28
نویسندگان
, ,