OuterWire problem of OpenCascade

Some fundamental parts of OpenCascade are surprisingly problematic. I recall filing a ticket #31172 about misbehavior in BRepTools::OuterWire() which remained unnoticed (or ignored) for decades. And there are some more active issues out there:

• #33632: "BRepTools::OuterWire returns internal wire"

• #29577: "Unify face OuterWire method"

The outer wire computation of OpenCascade sometimes fails and returns an inner wire of a face. Not surprisingly, we got the same issue in Analysis Situs (#328), where a spline hole was returned as an outer wire of the corresponding planar face. The situation with outer wire computation is actually quite horrible, because:

1. First of all, it's a heavy computation.
2. Second, this computation is unreliable (because we have bugs for pretty simple cases).
3. Third, there is no single right way to perform this computation as there are many tools doing the same thing.

OuterWire was giving some 25 years ago.

You might wonder why the heck an outer wire of a face should be COMPUTED rather than just indicated as being an "outer" contour with a Boolean flag. Well, I can tell you that I don't know. This is one of the questions that should have been asked to the library's early architects, but they are clearly no longer available. The computational way of determining whether a wire is inner or outer on a face requires us to literally reverse engineer this property. It goes without saying that such a situation is simply due to bad design. Okay, refactoring such fundamental things is not what we should expect from library developers. So, let's examine how we can reliably check if a wire is an outer one.

The first method is provided by BRepTools::OuterWire() function mentioned above. This function assumes that the outer wire's bounding rectangle fully encloses the inner wires' bounding rectangles. The idea is clear, and the image below depicts a typical arrangement of bounding rectangles where such reasoning works:

Bounding boxes in UV domain.

However, there is one tiny issue that invalidates this simple method. The problem is that bounding boxes for spline curves are computed based on the poles rather than the curve itself. This simplification allows for faster computations, but it cannot generate tight bounding boxes. I recall multiple times finding myself in a puzzling situation because I assumed bounding boxes were precise, while they were not. Here's how a problematic case looks like:

Bounding boxes in UV domain for a problematic test case.

Because the inner wire is a spline, its bounding box extends outside the curve, encompassing all control points that are unseen in the domain viewer above (hence the visual padding).

Control points of a spline curve from the problematic inner wire used above.

It seems that some 25 years ago the data exchange team was aware that BRepTools::OuterWire() is broken, and proposed their own method, which is ShapeAnalysis::OuterWire(). By the way, many things become clear if you bear in mind that the development process had been divided among different groups, and the data exchange team, for example, could hardly fix anything in the modeling team's business. So, it appears that we suffer from a management issue in good old (dead) Matra.

Trimming contours enclose the material of the face.

The logic behind ShapeAnalysis::OuterWire() in its original version was pretty funny. It first untrimmed the face, then placed the next candidate wire to the empty face, and finally checked an infinity-distant point for membership. If we untrim the outside wire, the infinite point is INSIDE. If we untrim an inner wire, no "material" flows out the face perimeter, and the infinite point remains OUTSIDE. It would be interesting to compare the performance of this approach to vanilla BRepTools::OuterWire(), however this logic was revamped in 2022 and is no longer in use. Moreover, since an empty face should be constructed from scratch, each iteration of such an algorithm would inevitably use extra heap allocations, and this fact wouldn't make you happy.

Hard times of outer wire computation.

The revised version of this logic calculates the area of a 2D wire and verifies its sign. The new logic implies that a properly oriented wire will give a positive area for counterclockwise contours and a negative area for clockwise. While this idea appears to be legal, extensive testing on thousands of examples in Analysis Situs revealed hundreds of regressions. One is shown in the picture below.

Somewhat typical situation with alternative tools.

Finally, I gave up on the ShapeAnalysis package because it appears that the provided implementation was not well tested. As it is often the case, functions exist but do not function properly.

Experiments indicate that fixing BRepTools::OuterWire() is easier than implementing any other method. After all, the bounding box strategy works in the vast majority of cases, with the only remaining step being to shrink UV rectangles. The patch is intended to improve the simple UV bounds computation that leaves padding for spline poles. Instead, let's compute the UV bounds of a wire as follows:

void ComputeWireUVBounds(const TopoDS_Face&  F,
                         const TopoDS_Wire&  W,
                         double&             umin,
                         double&             umax,
                         double&             vmin,
                         double&             vmax)
{
  TopoDS_Face FF = F;
  TopoDS_Wire WW = W;
  FF.Orientation(TopAbs_FORWARD);
  WW.Orientation(TopAbs_FORWARD);
  
  TopExp_Explorer ex(WW,TopAbs_EDGE);
  if ( !ex.More() )
  {
    return;
  }
  
  Bnd_Box2d B;
  ShapeAnalysis_Edge sae;
  ShapeAnalysis_Curve sac;
  for ( ;ex.More(); ex.Next() )
  {
    const TopoDS_Edge& edge = TopoDS::Edge( ex.Current() );
    Handle(Geom2d_Curve) c2d;
    double f, l;
    //
    if ( !sae.PCurve(edge, F, c2d, f, l, false) )
      continue;
    
    sac.FillBndBox(c2d, f, l, 20, false, B);
  }
  
  B.Get(umin, vmin, umax, vmax);
}

A key aspect here is the use of ShapeAnalysis_Curve::FillBndBox() function. This function constructs a tight bounding rectangle for a curve. We pass the magic number of 20 points (although 23 is more canonical for OpenCascade) as well as a Boolean flag indicating whether or not to use Newton iterations for exact fit. Here we pass false because our inclusion test does not require an exact bounding box. So we let the algorithm underestimate the bounding rectangle's size, which is better than overestimating it.

The fixed version of UV bounds computation.

It should be noted that precise fit can still be used with minimal influence on computation time. Testing hundreds of thousands of cases yields little difference in absolute numbers, despite the fact that the computation is formally faster for the less precise option.

Timing for outer wire computation with exact fit (click to enlarge).

Timing for outer wire computation without exact fit (click to enlarge).

The patched logic of outer wire computation has been implemented in asiAlgo_Utils::ComputeOuterWire() function of Analysis Situs. Use get-outer-wire Tcl function to give it a try.

Want to discuss this? Jump in to our forum.