Isolate the face before deleting it: contradiction in the code?

Have some feature requests, feedback, cool stuff to share, or want to know where FreeCAD is going? This is the place.
Forum rules
Be nice to others! Read the FreeCAD code of conduct!
m3g1dd0
Posts: 7
Joined: Sat Aug 28, 2021 4:41 am

Isolate the face before deleting it: contradiction in the code?

Postby m3g1dd0 » Mon Aug 30, 2021 11:13 am

I want to verify an issue by this post. Looks like there is a discrepancy in the code.

Code statements

FreeCAD has this code for repairing mesh:

https://github.com/FreeCAD/FreeCAD/blob ... .cpp#L1410

Code: Select all

void MeshTopoAlgorithm::RemoveDegeneratedFacet(unsigned long index)
{
  // coincident corners (either topological or geometrical)
  for (int i=0; i<3; i++) {
  
      // ...
  
      // isolate the face and remove it
      rFace._aulNeighbours[0] = ULONG_MAX;
      rFace._aulNeighbours[1] = ULONG_MAX;
      rFace._aulNeighbours[2] = ULONG_MAX;
      _rclMesh.DeleteFacet(index); // *** Facet is isolated before deleting
      return;
      
      // ...
  }  
  
  // We have a facet of the form
  // P0 +----+------+P2
  //         P1
  for (int j=0; j<3; j++) {
  
  // ...
  
      else
        _rclMesh.DeleteFacet(index); // *** Facet is NOT isolated before deleting
      return;

// ...

  }

}
Difference

The above statements contain two calls to this method:

Code: Select all

MeshKernel::DeleteFacet
With this difference:
  • The first call isolates the facet before calling delete method
  • The second call doesn't isolate the facet before calling delete method
Note

It should be noted that the delete method itself depends upon neighborhood data to re-adjust neighbors, so by isolating a facet, we are basically throwing away its neighborhood data. Hence, its neighborhood cannot be re-adjusted:

Code: Select all


bool MeshKernel::DeleteFacet (const MeshFacetIterator &rclIter)
{
    // ...
    
    // *** The following loop depends upon the neighborhood data.
    // *** So if facet is isolated before calling this method,
    // *** the following loop is skipped and the neighborhood cannot be re-adjusted.
    // *** Am I right?
    
    // invalidate neighbour indices of the neighbour facet to this facet
    for (i = 0; i < 3; i++) {
        ulNFacet = rclIter._clIter->_aulNeighbours[i];
        if (ulNFacet != ULONG_MAX) {
            for (j = 0; j < 3; j++) {
                if (_aclFacetArray[ulNFacet]._aulNeighbours[j] == ulInd) {
                    _aclFacetArray[ulNFacet]._aulNeighbours[j] = ULONG_MAX;
                    break;
                }
            }
        }
    }

    // ...
}

Question

Why is there the above difference? Is there any specific reason for it?
jnxd
Posts: 239
Joined: Mon Mar 30, 2015 2:30 pm

Re: Isolate the face before deleting it: contradiction in the code?

Postby jnxd » Tue Sep 07, 2021 3:59 pm

m3g1dd0 wrote: Mon Aug 30, 2021 11:13 am ...
The above statements contain two calls to this method:

Code: Select all

MeshKernel::DeleteFacet
With this difference:
  • The first call isolates the facet before calling delete method
  • The second call doesn't isolate the facet before calling delete method
Note

It should be noted that the delete method itself depends upon neighborhood data to re-adjust neighbors, so by isolating a facet, we are basically throwing away its neighborhood data. Hence, its neighborhood cannot be re-adjusted:
..
Why is there the above difference? Is there any specific reason for it?
I tried to read through this code a little, but without enough documentation it's a little hard to tell how a "neighbours" are defined and arranged. However some observations can be made.

1. In MeshKernel::DeleteFacet(), neighbourhood data is used to invalidate the deleted face from its neighbours' arrays. This invalidation ONLY happens if the deleted face is in that neighbour's neighbourhood array.
2. In the first case (where isolation happens), we have already adjusted the neighbours of UN1 and UN2 (to each other), so they don't need to be invalidated. Isolating the face just seems to save us time. Not sure how the third neighbour is defined, but it SHOULD be invalid because it would share a degenerate edge (same point is both ends).
3. In the second case (where isolation doesn't happen), neighbour adjustment happens in the if branch and DeleteFacet is called in the else branch. So at call point the algorithm seems to give up on any adjustment. It's a different question as to why DeleteFacet is not called after adjustment [EDIT: OK it seems to be because the points of two facets are just being interchanged so we have two good facets instead of one good and one degenerate].
4. So finally I suppose when no adjustment is possible (the else branch) because the opposite face is already deleted for whatever reason, our current face in question is deleted and all neighbours "get the info" by the invalidation.

From git blame, it seems this code was written more than a decade ago by @wmayer. He might have some documentation about it.
m3g1dd0
Posts: 7
Joined: Sat Aug 28, 2021 4:41 am

Re: Isolate the face before deleting it: contradiction in the code?

Postby m3g1dd0 » Wed Sep 08, 2021 9:35 am

@jnxd Thanks for the explanation =)
jnxd
Posts: 239
Joined: Mon Mar 30, 2015 2:30 pm

Re: Isolate the face before deleting it: contradiction in the code?

Postby jnxd » Thu Sep 09, 2021 4:50 am

m3g1dd0 wrote: Wed Sep 08, 2021 9:35 am @jnxd Thanks for the explanation =)
OK I think I'll mark the bug resolved then.