Why check edges for intersections?

[IHateLiam]

Hello Andreas, very nice work!

I was reading the "compute_gpc_system()" function in the GPC group class, and following function calls, I arrived to gpc_system's update function.

In gpc_system.update() (besides from updating the actual data structure) you check for "edges intersections" I'm stuck at understanding what you mean for "intersections". It's clear to me what an intersection between line segments is, but I don't get why edges of a triangular mesh should intersecate. In the function "line_segment_intersection" you follow formulas provided in Wikipedia, and I get that. The only intersections I can think of are vertex intersections, but using "np.logical_and(0. + eps < xs, xs < 1. - eps)," you exclude them (it should be <=).

I thought maybe that's to correct errors of the function that calculates distances and angles (following the article algorithm) (if it makes any?), but I'm not sure.

Could you help me understand why this computation is necessary?

Thank you!

[andreasMazur]

Hello. Thanks for showing interest in GeoConv!

I'm stuck at understanding what you mean for "intersections". It's clear to me what an intersection between line segments is, but I don't get why edges of a triangular mesh should intersecate.

GeoConv slightly extends the algorithm of Melvær, Eivind Lyche, and Martin Reimers (2012) to check for edge-intersections in the plane, i.e., 2D-space and not in the 3D-space.

We do so because we observed that if the maximal radius for a local GPC-system exceeds a certain threshold, faces do overlap in the 2D-space. So we check for edge-intersections to prevent overlapping faces.

But why are overlapping faces a problem? If faces overlap, we have problems during the next step of the preprocessing pipeline, namely the computation of barycentric coordinates. In that step we are interested in computing interpolation coefficients for points which we place into the local GPC-systems. When faces overlap, it could happen that the point which we placed into the GPC-system is located within multiple faces. Now it would be unclear which face to choose to compute the interpolation coefficients.

I hope this clarifies your question. If not, just let me know.

Best regards, Andreas

[IHateLiam]

Ok, i think it's clearer now. Please tell me if I got it right:

The problem arises when (part of) the geometry gets projected into the plane. So when two triangles, even if they are distant from each other, get "distorted" to fit on a 2D-plane, it can happen that these two triangles, once projected onto the plane, get one on top of each other, thus the overlapping of faces.

Thank you for your answer

[andreasMazur]

That's correct!

[IHateLiam]

Thank you very much