1

The mesh surface is guaranteed to be free of holes (though if there’s a solution that allows for holes it would be good to know). The mesh is concave - for sake of argument, imagine an H made of cylinders.

The mesh is cut by a plane, which results in a number of new vertices. These vertices create one or more ‘edge loops’ - for example, cutting off the bottom two legs of the H would result in two separate edge loops.

I need to start at [any vertex not covered yet] and traverse the edge loop containing that vertex in an order, so it can be used to create triangles to cover the open area.

I have the cut working, and it’s creating vertices in the right positions. My problem is in finding the edge loop.

Here’s my concept: Traverse every triangle. If one point of the triangle is on a different side of the cut than the other two, slice the triangle’s edges as appropriate. If those edges have already been sliced, use the vertex already created for that slice instead of making a new one. Now record the two vertices as a single edge to be sorted into loops later.

Every triangle edge that gets sliced once should be sliced twice, since the mesh surface is hole-less, right? MOST of my edges are sliced twice, but a small number (more than two, not consistent over the mesh but consistent given the same cut) are only sliced once, which results in recording an ‘edge’ with only one vertex.

Here’s the code I have:

var edges = new Dictionary< int[], int >();
// edges[ [x,y] ] is the index of the vertex created between vertices x and y

for ( triangle in triangles ) {
  if ( *a point is separated from the others* ) {
    lp = *'lone point', index of the lone vertex*
    for ( *each other vertex of the triangle* ) {
      op = *'other point', index of this vertex*
     
      // key for accessing the edge dictionary -
      //  it's the same edge regardless of point order, so sort them 
      if ( lp < op ) key = [lp,op]; else key = [op,lp];
      if ( edges.ContainsKey( key ) ) {
        rehits++;
        *re-use existing vertex*
      } else {
        *create vertex #newvix*
        adds++;
        edges.Add( key, newvix );
      }
    }
  }
}

How am I landing more adds than re-hits?

Visualization: alt text

Video: 2. Every edge crossed by the cut plane should glow - the ones that don’t glow are the ones where edgeToIndex did not contain the key.

2

This stuff is dumb. The answer is dumb. I can be pretty dumb.

Answer: Doesn’t matter. All meshes have holes. If they don’t, they will once you slice through them since the new surface must have a hole between it and the old surface or it’ll be smooth-shaded and I don’t think that’s ever wanted. So stop trying to cheat and just deal with the holes.

class PolyPoint {
  var edgeIndex : int; // the vix of the newedge vertex i represent
  var surfaceIndex : int; // the vix of the newsurface vertex i am in the same place as
  var end1 : int; // my clockwise-next vix
  var end2 : int; // my counter-c-previous vix
}

For each cut triangle, create two polypoints and assign their edge index. Each of them has one of its ends assigned, and the other is left pointing to nothing for now (because we don’t know). You need to know the triangle’s wind order to pick which ends are assigned. Ughmath.

For each newedge vertex, if there exists a newsurface vertex at this vertex’s position, set this vertex’s polypoint.surfaceIndex to that vertex. Otherwise, create a newsurface vertex at this position and give it a new polypoint entry with no data set except for surfaceIndex.

Now that the surface loop(s) vertices are created, add the connections in. For each newedge vertex… y’know what, copypaste:

for ( vix = firstNewEdgeVix; vix < firstNewSurfaceVix; vix++ ) {
	polypoint = pointDict[vix];
	if ( polypoint.end1 > 0 ) {
		pointDict[ polypoint.surfaceIndex ].end1 = pointDict[ polypoint.end1 ].surfaceIndex;
	}
	if ( polypoint.end2 > 0 ) {
		pointDict[ polypoint.surfaceIndex ].end2 = pointDict[ polypoint.end2 ].surfaceIndex;
	}
}

Tell each edgepoint that its ends are the surfacepoints of its ends. (translate from edge index to surface index)

From there you just locate loop ends, if any (“end1==0 || end2==0”), start anywhere, and follow the end1 or end2 around to create your loops, occasionally skipping from endpoint to endpoint or swapping from end1 to end2 traversal if an unmatched endpoint is encountered

This stuff must be documented somewhere already. But I can’t find it. Is this really not a documented thing? Has everyone had to rebuild this particular wheel? :frowning:

Oh well. At least I’ve almost got it, just have to find the winding order of a triangle relative to… This is complex nightmare math abominations. I need to go shoot some robutts.