Replies: 3 comments 2 replies
|
As it turns out, it took less time to try tricking the winding number into working than it took to post my question. Classic rubber duck action. Thanks for listening. Here is an image of a complex aircraft model with two translations -- one up and aft, the other up and forward. |
|
Nice!
FWIW, in my matlab library gptoolbox there's `linear_sweep.m` that does
sweeps along linear translations.
https://github.com/alecjacobson/gptoolbox/blob/master/mesh/linear_sweep.m
You can also use
https://github.com/libigl/libigl/blob/main/include/igl/copyleft/cgal/minkowski_sum.h
with your shape + line segment. I don't remember exactly but I think the
minkowski sum is implemented in a very slow way.
…-Alec
Message ID: ***@***.***
com>
|
|
Thanks for those pointers. Are there any papers / examples / writeups about how those work? |
|
not really. The minkowski sum is our mesh arrangements paper extended in
the most straightforward unoptimized way. The linear sweep I think I just
cooked up based on what I thought it should be. I think it should be quite
robust because it uses the mesh arrangements under the hood.
-Alec
…On Fri, Sep 5, 2025 at 5:33 PM Rob McDonald ***@***.***> wrote:
Thanks for those pointers. Are there any papers / examples / writeups
about how those work?
—
Reply to this email directly, view it on GitHub
<#2498 (reply in thread)>,
or unsubscribe
<https://github.com/notifications/unsubscribe-auth/AARDJGNHSRE45LNSC23LT333RH6S5AVCNFSM6AAAAACFYERKSKVHI2DSMVQWIX3LMV43URDJONRXK43TNFXW4Q3PNVWWK3TUHMYTIMZSGQYDOMA>
.
You are receiving this because you commented.Message ID:
***@***.***>
|
|
That helps. I'll take a look. Thanks much. As I understand it, your CSG stuff based on the mesh arrangements paper is all Copyleft because it uses stuff from CGAL, right? While I can certainly learn from it, I won't be able to use it. Although my project is open source, it is not GPL. I will certainly take a close look at how you track winding number through the process, I think that could make inside/outside determination faster and more robust (I currently use ray shooting and an octtree). I see from the paper that your method can work with non-manifold geometry to some extent. It seems like it still expects all of the input geometry to be manifold watertight surfaces -- though the solution may be non-manifold (for example, two cubes that share an edge). Can your method (perhaps with some extensions) work with non-watertight surfaces as input? Here is an example... Here, the red pod is a watertight surface that encloses a volume, while the green and gold wings are thin membrane surfaces. In my CSG algorithm, most things proceed as normal. For a Union, a triangle of the membrane that is inside a watertight body is culled. However, since the membrane has no interior volume, I skip it when classifying triangles from the other bodies. Working with both thick (manifold, water tight) and thin (non-manifold, membrane) surfaces in CSG is a pretty unusual use case that I haven't found other tools with the capability. I have found some codes that support taking a planar slice of a watertight mesh (another thing I need to do), but that is about as close as I've found. Our CSG code mostly works, but it is somewhat dated. It is not fully robust and I would love to find a performant robust library that would let me delete several thousand lines of code. Unfortunately, I haven't found any that support some of our more obscure use cases. Manifold is quite impressive and has improved quickly in a short amount of time. I think they use a similar winding number tracking approach as your paper. Unfortunately, their library does not work with non-manifold input and they are adamant against supporting it. At one point they suggested I might be able to duplicate a membrane sets of triangles with opposite-facing normals, but things fell apart near edges and corners (tris would share multiple edges at corners, which they would collapse, etc). It became clear that the obstacles were too great and I had to abandon their library. |
Uh oh!
There was an error while loading. Please reload this page.
I'm developing a simple Swept Volume calculator. My use case is focused on plain linear translation, so an exact swept volume of a mesh is possible. I start with a mesh, translate the 'shadow' side, construct 'edges', and then self-intersect the mesh, splitting triangles as needed. For the final step, I use the IGL Winding Number calculation to classify the split tris as inside / outside, discarding interior tris.
Since the winding number calculator works at survey points, I take the center of each triangle and perturb it (say 1e-6) in the direction of the tri's unit normal vector. I use the inside / outsideness of that point to classify the triangle.
The winding number calculation is the most expensive part of this process. I'm using the exact IGL winding number method -- the fast approximate version did not do a good job in my brief attempts. The exact one is fast enough for my purposes.
This is working remarkably well for single translations -- even for complex non-convex meshes.
I do not want to use an implicit swept volume calculator. I have tried both IGL's swept volume calculator and https://github.com/sgsellan/swept-volumes. These methods work, but they produce approximate results and take much longer than my exact CSG based approach.
Progressing past plain linear translation, I want to find the union of the swept volumes in two directions. I may be able to accomplish this by computing each swept volume separately and then taking the CSG union of them. There will be perfectly coincident faces, so this presents challenges. Instead, I am trying to construct all the swept faces and then let a single winding number calculation sort it out.
Unfortunately, I am getting undesirable results. Here (left image) is a simplified case.
The circle has been translated to two end positions. I am interested in the winding number at the point at the bottom. None of the edges are duplicated.
As the line integral is traversed, there are often two or three away-facing faces for a particular direction -- that is offset by only one towards-facing face. Consequently, the point of interest ends up with a negative winding number -- even though it is clearly outside the profile -- and even outside the convex hull of the shape.
I've read the "Robust Inside-Outside Segmentation using Generalized Winding Numbers" paper, and I go back and forth as to whether this result is expected.
During construction, I can also eliminate the 'top' of the original circle (right figure). This changes the results, but still has the same underlying problem.
It seems that my best course of action may be to lie to the winding number calculation by feeding it duplicate faces for the tris that are used more than once (3x for the left figure, 2x for the right).
Are there other avenues I should pursue?
All reactions