Concern about PointInPolygon() robustness

[alexisnaveros]

I was writing a quick SSE4.2 version of PointInPolygon() and that CrossProduct followed with if(d == 0) return PointInPolygonResult::IsOn worries me.

We could craft a scenario where a contour is definitely inside another, yet the very first vertex (the only one tested) is so darn close to an edge of its parent contour that the floating point math returns an "outside" result. There could be a fourth option in that PointInPolygonResult enum ("indeterminate, please pick another vertex"), or maybe IsOn should be triggered by a range based on the expected numerical accuracy of that double precision math (rather than == 0.0)...

I'll do the math for that indeterminate numerical range.

(Current draft of C SSE 4.2 PointInPolygon() seems twice as fast, I'll share if you want, although AVX should do better)

EDIT: Okay, don't mind me, it's all good. 😆 Numerical precision is fine because errors can't accumulate enough to flip the result... (Although I would rather compare both sides within the cross product, instead of subtracting them and then comparing against zero. The apparent sequence of two roundings triggers alarms for those watching out for floating point accuracy)

[AngusJohnson]

(Current draft of C SSE 4.2 PointInPolygon() seems twice as fast, I'll share if you want, although AVX should do better)

Sure! Thanks. 😁

[alexisnaveros]

(Current draft of C SSE 4.2 PointInPolygon() seems twice as fast, I'll share if you want, although AVX should do better)

Sure! Thanks. grin

Cool, there:
http://www.rayforce.net/clipper2stuff/pointinpolygon.c

A couple notes:

• I'm using arrays of int64_t instead of Point64 structs (raw arrays are more friendly to SIMD/CUDA/etc.).
• Note the comments about CLP_CONFIG_PATHVLIST_EXTRA_ALLOC, memory storage must extend beyond "vertexcount" for guard values / SIMD loops
• All compilers (GCC, clang, Intel, etc.) define macros such as __SSE4_2__ to know the compilation target's instruction sets at compilation-time, except Microsoft compilers. Not sure how it's supposed to be done there (sorry, never really checked, I don't do Windows).

[AngusJohnson]

Hi again Alexis.
First, thanks for the code suggestions, and please keep them coming.

And before I address your comments above, I'll outline my design objectives for Clipper2, and perhaps for later development too (Clipper3). Excellent performance is most definitely very close to the top of my objectives for Clipper2. But I'm prepared to make small compromises there when I believe it'll make the code too complicated, at least for me to maintain. And Clipper2 is already very complicated. However, I can see there's a place for Clipper2 forks where performance isn't compromised; where paths might be separated into separate X and Y arrays (and Z arrays), and where various instruction set optimisations are considered. And it's very likely that someone can do this in a way that doesn't make my existing code too complicated. And yes, the code logic in clipper.engine could greatly benefit from a lot more attention to simplification with better encapsulation (perhaps into mulitple files) and with much better documentation. And that might be Clipper3. OK, ramble over 😜.

'm using arrays of int64_t instead of Point64 structs
...
Note the comments about CLP_CONFIG_PATHVLIST_EXTRA_ALLOC

I almost certainly won't be persuaded to change the current Point64 struct in Clipper2 . And likewise with accommodating extra 'guard' storage in a modified Path64. But these things could certainly be considered for Clipper3 😁. Nevertheless, could the performance benefits justify creating temporary arrays in the PointInPath function itself?

[alexisnaveros]

Oh, it's really not as complicated as I perhaps made it sound like.

Note that your array of Point64 is an array of int64_t going xyxyxy (as long as USINGZ isn't defined), so you can just cast the pointer. It's not very elegant perhaps... (personally, I use structs when the internal format is meant to be flexible, as code shouldn't break because you add a member to a struct). Safeguards using sizeof() and offsetof() can be put in place before calling the optimized code, otherwise the current generic version.

As for the guard storage, we need a little if( vector->capacity() < vector->size() + GUARD ) vector->reserve( vector->size() + GUARD ); and that's done. 😁

---

I fully understand your concerns about Clipper2. It seems perfectly valid to keep the code generic, to avoid complicating the code with optimizations and a bunch of custom paths (one for SSE2, one for SSE4.1. AVX, AVX2, AVX512, ARM Neon, etc.). So high-level optimizations like cache-awareness (linked lists aren't that great) would fit in, and SIMD wouldn't.

As you probably noticed, my intention is to go all-in on optimization with my C rewrite (perhaps that could be what Clipper3 is, about all programming languages can call a C interface). So we could simply keep the crazy low-level optimizations there, that seems reasonable.

A nice high-level optimization that would belong in Clipper2 is that improved scalability when millions/billions of vertices are involved... Do you have some thoughts on the matter? I have a vague plan, but we both know you understand the big picture better than I do. 🤣

[petrasvestartas]

It would be nice if there would a tolerance value for point in polygon check.

[AngusJohnson]

See #620