Fast point-face classifier (?)

[Quaoar]

Here's another issue I came across, and I do not have any solution so far. What I'm doing is sampling CAD faces in their UV spaces with uniform grids. Something like that:



And with the grid overlay:



The red color means that the corresponding point falls inside the parametric domain of a face. The white color means that the corresponding point is outside. For that test, I use the good old IntTools_FClass2d and it appears to be not that good (just old). The problem is the performance and now I'm looking for a better way of point-face classification.

Has anyone ever implemented fast PMC for 2D contours?

 

[Quaoar]

The description of the point-in-polygon test (together with a bibliography) could be found in the book by [Christer Ericson. 2004. Real-Time Collision Detection. CRC Press, Inc., USA.], sec. 5.4. p. 201.

Another test that works for concave polygons is based on shooting a ray from the point along some direction (commonly the positive x axis) and counting the number of times it crosses the polygon boundary. If the ray crosses the boundary once, the point must be inside the polygon. If it crosses twice, the point must be outside, with the ray first entering and then exiting the polygon. In general, the point will be inside the polygon for an odd number of crossings and outside for an even number of crossings. This test, commonly referred to as the crossings test, is illustrated in Figure 5.29.

Some care must be exercised to properly handle cases where the ray passes through a polygon vertex or coincides with an edge of the polygon. If not dealt with correctly, multiple crossings could be detected in these cases, giving an incorrect crossings count. In practice, this problem can be dealt with effectively by arranging the tests performed so as to treat vertices on the ray as lying infinitesimally above the ray. Several variations on the crossings test are presented in [Haines94].

Here is the link to the homepage of Eric Haines mentioned in the book: http://erich.realtimerendering.com/ptinpoly/

I'll give it a try and come back here.

 

[A-U]

Please do share your findings. This looks potentially interesting too:

De Miras, J. Ruiz, and Francisco R. Feito. "Inclusion test for curved-edge polygons." Computers & Graphics 21.6 (1997): 815-824.

 

[Quaoar]

The following paper is related to the RGK kernel (the never-released one):

Gatilov, S. Y. (2013). Efficient angle summation algorithm for point inclusion test and its robustness. Reliable Computing, 19, 1–25.

It's interesting as it explains in great detail the winding angle summation method which is "known to be the worst one" because of the use of inverse trigonometric functions. S. Gatilov also uses BVH for fast filtering of candidate segments.

 

[Quaoar]

As I needed to overlay a Cartesian grid onto the face's UV domain without much care on the inner contours, I simplified the ultimate logic quite a bit.

Here is the sampling result in the UV domain with the OpenCascade's classifier.



The grid was really fine:



It took 8 sec with the OpenCascade classifier. Then I switched to the PMC code by Haines, but I also simplified the "business logic" part so that to ignore all the inner contours. Therefore, this test is not exactly fair. Here's what I ended up with:



For my needs, this overlay is also fine as I do not really need to take into account inner features. However, it should be trivial to take them into account as it's essentially the same ray casting method. A closer look:



This Haines' mode worked in 1.7 sec, which is quite an improvement, and it eliminates the hotspot I initially observed. The code is here: https://gitlab.com/ssv/AnalysisSitus/-/blob/master/src/asiAlgo/auxiliary/asiAlgo_SampleFace.cpp

I use the original code by Haines without any modifications. To run it, I converted the outer TopoDS_Wire to the fixed-length array (to avoid dynamic memory allocations) after discretizing the corresponding pcurves of all the edges. The function I used is the CrossingsTest(), and I did not try any other methods he has in his source file. The thing is that for me it's already good enough, and now I have another hotspot in the point-mesh projection logic which is a different subject.

 

[Quaoar]

One little update: Haines algorithm does not provide ON type of classification (only IN and OUT). In that sense, it does not serve well some typical CAD scenarios of use. A point lying ON a polygon will be attributed as IN or OUT, whichever round-off condition is realized.