4
\$\begingroup\$

This is a fairly complex question, so please bear with me.

I'm attempting to calculate an edge loop based on the intersection of a plane with a mesh, bounded by a sphere.

Here is a mockup of what the expected result might look like:

enter image description here

The black lines represent the intersected mesh, the orange line the result. Blue and cyan lines are vertex and face normals, respectively. The sphere origin would be somewhere inside the mesh. The orange vertices and sphere origin would also be coincident with the plane. Note that the edge loop is not part of the mesh. This is not a mesh split - just a list of vertices forming a loop along it.

Faces included in the edge should be pointed toward the sphere origin side, and any islands should be ignored (greedy), as shown in this mock up:

enter image description here

In the event that a closed loop cannot be found, the function should return null or an empty array.

I'm working on this in Unity, so I will use its API to further illustrate. The signature I expect to use looks like this:

Vector3[] CalculateCorridorLoop(Vector3 planeNormal,
                                Vector3 origin,
                                float radius,
                                MeshFilter meshSource)

So far...

I've tried a few different approaches, but I'm now leaning toward a more brutal approach. To come up with those mockups I simply used Blender's knife tool, duplicated the edge loop, and then dissolved the edges on the mesh. If I could calculate an edge loop for every face intersecting the plane then project the edges and origin into 2D space using the plane, it simply becomes a problem of finding the outermost loop containing the origin, which is itself contained by the circle.

Of course I get the feeling I've spent so much time on this I've overthought it and missed something simpler - although even that doesn't seem very straightforward. I think I'd need to keep track of which edges belong to which triangles to keep track of which vertex goes with which loop.

I found this paper, Fast Algorithm To Split And Reconstruct Triangular Meshes, which also uses planes for splitting, but seems to integrate the vertices into the mesh as it goes - whereas I just want the resulting edge loops. Though it's entirely possible I'm reading it wrong.

\$\endgroup\$
2
\$\begingroup\$

Unity uses indexed meshes which will help (as long they are indexed properly and clean).

  • Find a triangle that intersect the plane
  • Mark it as scanned
  • Find the two edges of that triangle that also intersect the plane
  • Use one edge as the start and end of the loop
  • Use the other edge to find the next triangle that intersect the plane, it is the one that will have two of the same vertices.
  • Mark it as scanned
  • Find the next edge intersecting the plane
  • Repeat until you've returned to the start edge.

This gives you 1 ordered loop. Repeat with all the unscanned triangles to find all the loops.

Ignore the loops inside other loops using a 2D Point-In-Poly test projected on the cutting plane.

You may still end up with 2 or more loops. For example think of the ways you can slice a donut: You can get two loops outside of one another.

\$\endgroup\$
  • \$\begingroup\$ Seems to work for the most part. I found a literal edge case, though. Also need to check whether edges are coincident with the plane. \$\endgroup\$ – jzx Jan 3 '16 at 0:49
  • 1
    \$\begingroup\$ There's a simple trick for this: make sure none of the vertices are right on the plane. Move them away by a "small value" using the plane's normal if they're too close. This also prevents some rounding errors. "small value" should be calculated according to the mesh's size. mesh_size/(1<<16) is a good value for 32bit floating point math (24bit mantissa, that leaves 8bits below the epsilon value to be safe). \$\endgroup\$ – Stephane Hockenhull Jan 3 '16 at 1:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.