Thank you for sharing your approach to handling the connectivity issue. Your method resonates with certain concepts from computational geometry, specifically the idea of mesh arrangements.
This approach is actually quite similar to the strategies we employed in computational geometry, a field where handling such geometric information is routine. Incorporating this kind of mesh arrangement in our codes would undoubtedly be beneficial. In fact, mesh arrangement does more than just solve the connectivity problem you mentioned. It can also determine if an arbitrary point is located inside a given polygon, a topic that I plan to delve into in my upcoming research.
One primary concern here is the direction of the edges. According to the UGRID convention, the edge should be counter-clockwise directed. This raises a challenge: for instance, edge "3" runs from vertex 1 --> 0 in face 'b' but from vertex 0 --> 1 in face 'a'. This discrepancy calls for the introduction of a concept known as the "half-edge". As you can infer, each half-edge relates to its adjacent face, providing a solution to the edge directionality issue. This is precisely how mesh arrangements address such problems.
For a deeper dive into these concepts, I recommend looking into the following papers:
The mesh arrangement concept captures this precisely:
During the input construction, the mesh arrangement notes that the descending yellow half-edge (3) is linked to face 'b', whereas the ascending half-edge (3) corresponds to face 'a'.
So, when inquiring about the faces adjacent to edge (3), the mesh arrangement can promptly indicate faces 'a' and 'b' as the answer. It can also answer the problem "Which edge is adjacent to face a"
While it's entirely feasible to identify faces adjacent to an edge without emphasizing edge direction, it's essential to recognize the inherent subtleties. These nuances might become significant in advanced use cases or as our project progresses.
I advocate for the mesh arrangement for several reasons:
For creating a fast and reliable algorithm on a spherical surface, the mesh arrangement is nearly indispensable. Not only does it offer solutions to your adjacency concerns, but it also robustly addresses whether a specific point lies within a given polygon. Furthermore, it can shed light on other topological issues, such as identifying mesh "holes" and their locations. As previously mentioned, this direction aligns with my upcoming research focus.
The solution presented in #510 just aims to accelerate our present trajectory, enabling the integral function's swift availability. However, I anticipate utilizing the mesh arrangement to refine the algorithm down the line.
Incorporating mesh arrangement into our workflow will preempt the need to keep re-building the wheel repeatedly. It also helps us steer clear of extensive code refactoring in the future.
But I also understand your concern about bringing out a working solution as soon as possible. And I am just sharing my thoughts about the mesh arrangement here. I am always open to any suitable solutions or suggestions related to our project
philipc2
commented
1 month ago
Discussion initialized in https://github.com/UXARRAY/uxarray/issues/512#issuecomment-1765325749
Thank you for sharing your approach to handling the connectivity issue. Your method resonates with certain concepts from computational geometry, specifically the idea of mesh arrangements.
This approach is actually quite similar to the strategies we employed in computational geometry, a field where handling such geometric information is routine. Incorporating this kind of mesh arrangement in our codes would undoubtedly be beneficial. In fact, mesh arrangement does more than just solve the connectivity problem you mentioned. It can also determine if an arbitrary point is located inside a given polygon, a topic that I plan to delve into in my upcoming research.
One primary concern here is the direction of the edges. According to the UGRID convention, the edge should be counter-clockwise directed. This raises a challenge: for instance, edge "3" runs from vertex 1 --> 0 in face 'b' but from vertex 0 --> 1 in face 'a'. This discrepancy calls for the introduction of a concept known as the "half-edge". As you can infer, each half-edge relates to its adjacent face, providing a solution to the edge directionality issue. This is precisely how mesh arrangements address such problems.
For a deeper dive into these concepts, I recommend looking into the following papers:
Eric Berberich, Efi Fogel, Dan Halperin, Michael Kerber, and Ophir Setter. Arrangements on parametric surfaces II: Concretizations and applications. Mathematics in Computer Science, 4:67–91, 2010. Eric Berberich, Efi Fogel, Dan Halperin, Kurt Mehlhorn, and Ron Wein. Arrangements on parametric surfaces I: General framework and infrastructure. Mathematics in Computer Science, 4:45–66, 2010. Let me know if you need more clarification or if you have any other thoughts on this. Looking forward to working closely on this!
The mesh arrangement concept captures this precisely:
During the input construction, the mesh arrangement notes that the descending yellow half-edge (3) is linked to face 'b', whereas the ascending half-edge (3) corresponds to face 'a'.
So, when inquiring about the faces adjacent to edge (3), the mesh arrangement can promptly indicate faces 'a' and 'b' as the answer. It can also answer the problem "Which edge is adjacent to face a"
While it's entirely feasible to identify faces adjacent to an edge without emphasizing edge direction, it's essential to recognize the inherent subtleties. These nuances might become significant in advanced use cases or as our project progresses.
I advocate for the mesh arrangement for several reasons:
For creating a fast and reliable algorithm on a spherical surface, the mesh arrangement is nearly indispensable. Not only does it offer solutions to your adjacency concerns, but it also robustly addresses whether a specific point lies within a given polygon. Furthermore, it can shed light on other topological issues, such as identifying mesh "holes" and their locations. As previously mentioned, this direction aligns with my upcoming research focus.
The solution presented in #510 just aims to accelerate our present trajectory, enabling the integral function's swift availability. However, I anticipate utilizing the mesh arrangement to refine the algorithm down the line.
Incorporating mesh arrangement into our workflow will preempt the need to keep re-building the wheel repeatedly. It also helps us steer clear of extensive code refactoring in the future.
But I also understand your concern about bringing out a working solution as soon as possible. And I am just sharing my thoughts about the mesh arrangement here. I am always open to any suitable solutions or suggestions related to our project
Originally posted by @hongyuchen1030 in https://github.com/UXARRAY/uxarray/issues/512#issuecomment-1765662566