How to check whether a polyhedron is inside the polyhedron

Technical report

Introduction

Generally, point-in-Polygon, Point-in-Polyhedron, and Polyhedra-in-Polyhedron tests in many applications are utilized not only for the detection or point localization but to increase the speed of the algorithm. In this technical report, we are trying to fully learn the knowledge of Polyhedra-in-Polyhedron by implementing the program in C and in Cuda. Through combining the knowledge of computational geometric, we could have a better understanding of point, segment, polygon, and polyhedron. [1] We also transferred the two-dimension ray crossing method in the three-dimension which is an effective tool in our implementation.

In this report, we will first introduce the datasets in section 2. The related knowledge before developing our program will be shown in section 3. The algorithm we implement will be discussed in section 4.

Datasets

In our project, we use different OFF File Format files as datasets. Containing the information of the composing polygons of a geometric object, OFF (Object File Format) is a geometry definition file format. [16] The ability to store two-dimensions and three-dimensions objects and simple extensions let it become an effective tool in representing higher-dimensional objects. With the widespread use of object file format, the simple standard has been developed by geometry visualization software, other software.

In our project, we used three-dimension types of the composition of Object File Format which contains, (1) The number of vertices, number of faces, and number of edges. (2) List of vertices:X, Y, and Z coordinates. (3) List of faces: number of vertices, followed by the indexes of the composing vertices, in order (indexed from zero). [16]

In Fig. 1, we plot one of the datasets through Meshlab which contains 140 vertices with 276 facets. [13]

Related Approach

A. Segment-Segment Interaction

Before implementing the Polyhedra-in-Polyhedron program, it’s a must to build the concept of interaction between segment and segment. With two segment lines on a planet L, we could find the interaction by solving slope-intercept equations for two segments at the same time. In the research [1], they applied a more effective parametric approach to do interaction computation more effectively.

B. Segment-Triangle Interaction

After handling the interaction of segment and segment, we are moving to a more difficult part, computation of the point in the triangle in three dimensions. The first step is to find the interaction of the segment in the plane. From the [1], we could know that all points on the planet share the same equation with all points on the line which could be written as follows:

Using vector to represent the formula above:

We would further use this concept to develop the formula in the following implementation.

C. Segment-Triangle Classification

From sections A and B, we have the knowledge of point of interaction between the segment and the planet contain triangle. However, we don’t understand how to classify the relationship between point and triangle. Therefore, we will introduce the method we are going to implement and several situations to classify the relationship of segment, point, and triangle.

Without using another complex method, we applied the straightforwardly Projection to the Two Dimensions Method. Reducing the original three dimensions question into two dimensions, we could solve the classification easily. We concluded four situations [1] may occur after a project to two-dimension: (1) Point coincides with a vertex of Triangle. (2) Point is in the relative interior of one edge of the Triangle. (3) Point is in the relative interior of one Face of Triangle. (4) Point is no interaction with the Triangle.

D. Ray Crossings

The idea of ray crossings is easy. Extending a line from the point to a certain direction and count the number of interactions with the plane. The concept of Ray Crossings in three dimensions is the same as the two-dimension version. [1][2][7] Through calculating how many times the line crosses the boundary, we could know whether the point is inside or outside the planet.

As the ray may degenerate [1], we build the mechanism which will create a random ray to check for the degeneracy. Once we found the ray has degenerated, this ray will be discarded and replaced by another random one. To generate the random ray, we need to utilize the idea of the Bounding Box. By estimating the bounding box in advance, we could ensure the endpoint of the Point is outside the planet. We could get the bounding box by computed the maximum and minimum of the vertices of the Point.

Point In Polyhedron

In this section, we will introduce the process of checking the point is inside or outside the polyhedron. With the combination of knowledge in section, the algorithm in Fig 2 will be easy to understand.

First, variable Q and R represent Point and Polyhedron separately inline 1–2. After computing the bounding radius, we will loop forever until all the faces have been checked. We will generate a random ray in the beginning of the loop. Inline 8–14, we will check each Point Q with triangle T in polyhedron P. If the degeneracy of interaction is found, we will back to LOOP and generate another one. On the other hand, if we didn’t find the degeneracy, then the variable crossing will be increased. The last step inline 15–18 will check the Point Q is inside or outside the Polyhedron P though the number of variable crossings.

Polyhedron In Polyhedron

In section 3, we have fully introduced how we implement the algorithm of finding the point in a polyhedron. We would further our discussion on how to check whether a polyhedron is inside a polyhedron or not.

In Fig. 3, we changed our input to two polyhedrons P1 and P2. From inline 3–10, we implement algorithm 1 in section 3 again to ensure each point Q in P2 is inside the polyhedron P1. Once any point isn’t contained in P1, we will return false and exit the program. After examining every point Q in P2 is inside P1, we will apply segment detection to know in P1 is totally inside the P2, or not.

First, two points A and B in P2 will be chosen inline 11. The same idea of Segment-Triangle Interaction and Segment-Triangle Classification in section 2 will be utilized here. Finally, after scanning all the relationships of two points A, B in polyhedron P2, and polyhedron P1, we could know if the P2 is truly inside P1 or not.

Fig. 4 gives us a clear example of algorithm 2. For detecting one polyhedron whether, inside another one, we not only need to examine each point but every segment of the inner polyhedron.

GPU and Cuda

In order to improve the performance of this project, we try to transfer the CPU-based program in C to the GPU-based program in CUDA. Developed by Nvidia for general computing on its own Graphics Processing Units (GPUs), CUDA could be seen as a parallel computing platform and programming model. Through controlling the power of GPUs for the parallelizable part of the computation, CUDA allows developers to accelerate compute-intensive applications.

As we know, CUDA is not the only one. Like OpenCL could be counted as proposed APIs for GPUs [13] and there are competitive GPUs from other companies, like AMD. [14] However, including deep learning and other fastest computers in the world, the combination of CUDA and Nvidia GPUs still dominates several application areas.

CPU is designed to handle a wide range of tasks quickly, but are limited in the concurrency of tasks that can be running which cause the primary difference between CPU and GPU architecture. GPUs are frequently used for non-graphical tasks such as machine learning and large computation tasks because of its high performance on handing multiple datasets by executing parallel computing operations. Designed with thousands of processor cores running simultaneously, GPUs equipped the developers the ability to finish massive parallelism where each core is focused on making efficient calculations.

Conclusion

In this project, I learned many new skills from different domains. After spending lots of time studying [1] and discussing with senior, I build a solid foundation from points, segments, polygons, and, polyhedron. For the space aspects, I have seen different datasets from two-dimensional and three-dimensional which enabled me to better image the tasks I would like to solve. Equipped with that basic knowledge, I started to understand how to detect if the point is inside the polyhedron.

We found an effective algorithm in the [1] and tried to apply it in our version. Fortunately, it works well as our imagination. The next step is to check it the polyhedron is inside another polyhedron. In the very beginning, I thought that it could be a very simple question. I could check all the points of one polyhedron. However, after the senior mentioned some situations, I found I’m totally wrong.

Even if all points are inside one of the polyhedra, some parts of the inner polyhedron could be outside the outer one. To have this problem, we apply the segments to check for each point for the inner polyhedron with the outer polyhedron. To make sure, the whole polyhedron willfully inside the polyhedron.

In the last step, we transfer our C program into the CUDA program. Because GPUs are good at handling parallel computing, the time spending of our program could be reduced largely. Finally, we finished this project and build an effective tool to detect if the polyhedron is inside another polyhedron or not.

Future Work

We applied the basic but classic idea in our research. I thought we could try to apply a new algorithm or approach in detecting a point is inside or outside the polyhedron. Besides, here still have slight bugs in my CUDA program when facing degenerate rays. Even it didn’t cause mistakes in most datasets, I would solve this problem in the future.

Reference

1. O’rourke, Joseph. Computational geometry in C. Cambridge university press, 1998.
2. Kainz, Bernhard, et al. “Ray casting of multiple volumetric datasets with polyhedral boundaries on manycore GPUs.” ACM Transactions on Graphics (TOG) 28.5 (2009): 1–9.
3. Cui, Shulin, et al. “Point-in-polyhedra test with direct handling of degeneracies.” Geo-spatial Information Science 14.2 (2011): 91–97.
4. Li, Jing, and Wencheng Wang. “Fast and robust GPU-based point-in-polyhedron determination.” Computer-Aided Design 87 (2017): 20–28.
5. Kazar, Baris M., Siva Ravada, and Ravi Kothuri. “Point in polyhedron.” U.S. Patent №8,248,409. 21 Aug. 2012.
6. Chen, Min and T. Townsend. “Efficient and Consistent Algorithms for Determining the Containment of Points in Polygons and Polyhedra.”, 1987.
7. Horvat, Denis, and B. Zalik. “Ray-casting point-in-polyhedron test.” Proceedings of the CESCG 2012: The 16th Central European Seminar on Computer Graphics. 2012.
8. kala, Vaclav. “Point-in-convex polygon and point-in-convex polyhedron algorithms with O (1) complexity using space subdivision.” AIP Conference Proceedings. Vol. 1738. №1. AIP Publishing LLC, 2016.
9. Rui-Juan Jing and Marc Moreno Maza. 2019. Computing the integer points of a polyhedron. ACM Commun. Comput. Algebra 52, 4 (December 2018), 126–129.
10. Leonid Khachiyan, Endre Boros, Konrad Borys, Khaled Elbassioni, and Vladimir Gurvich. 2006. Generating all vertices of a polyhedron is hard. In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm (SODA ’06). Society for Industrial and Applied Mathematics, USA, 758–765.
11. Nivida, C. U. D. A. “Programming guide.” (2010).
12. Guide, Design. “Cuda c programming guide.” NVIDIA, July (2013).
13. Cignoni, Paolo, et al. “Meshlab: an open-source mesh processing tool.” Eurographics Italian chapter conference. Vol. 2008. 2008.
14. Munshi, Aaftab, et al. OpenCL programming guide. Pearson Education, 2011.
15. Introduction of AMD Graphics Processing Units (GPUs) from Wikipedia https://en.wikipedia.org/wiki/List_of_AMD_graphics_processing_units
16. Definition of the Object File Format (OFF) from Wikipedia https://en.wikipedia.org/wiki/OFF_(file_format)
17. BUBER, Ebubekir, and D. I. R. I. Banu. “Performance Analysis and CPU vs GPU Comparison for Deep Learning.” 2018 6th International Conference on Control Engineering & Information Technology (CEIT). IEEE, 2018.

Content sharing and implementation.

Author: Hsien-Yi Liu
Department of Computer Science@Stony Brook University
NY, United States
hsliu@cs.stonybrook.edu

Mainly implementing the idea in O’rourke, Joseph. Computational geometry in C.