All-inclusive bounding box

by - 21:36

Working on CAD Exchanger (http://www.cadexchanger.com) I have come across an issue that completely stumble me first. As I started working on mesher performance and gathered initial measurements on a set of sample models, I collected data on default precision (deflection) used to tessellate 3D models. By default, Open CASCADE visualization computes deflection as 0.4% of a maximum dimension of a bounding box. Don't ask me about any logic behind above number (I bet one day it was 1/1000 and then multiplied by 4 ;-)).

Some models were originally IGES or STEP and to speed up bounding box computations I imported them into CAD Exchanger and exported to BRep and used those BRep files. A few days later I decided to extend performance measurements on importers to gather more data on common algorithms. If anyone ever tried to profile Open CASCADE-based algorithms he/she likely noticed BSplCLib::Bohm() among hotspots, so I wanted to measure its total contribution into workload, not just at the phase of mesh computation. What was my surprise when the same models started reporting different deflections and bounding boxes! I could not blame my recent modifications as the same behavior was reproduced on a reference version. What the heck is that then ?!

By some lucky chance revelation came fast enough. As I was experimenting in DRAW, I noticed that bounding box changed (and significantly!) depending if the model had or did not have triangulation inside. So, when I first used brep files exported from CAD Exchanger they did contain tessellation (as they were displayed before export) and when I started using IGES or STEP in my test harness they did not. Wow !

To be sure of the assumption I dove into the source code – indeed, BRepBndLib::Add() has different branches depending if returned triangulation is null or not. That was it! What is noticeable is that bounding boxes built using triangulation are more precise comparing to those built using geometry representations. Certainly that is understandable.

Later the same day I encountered the same symptoms which were somewhat outstanding and made me dig further. Compare two pictures below – a bounding box on geometry representation is about twice as big along the X axis as a box built on tessellation!



Well, 5%-10% which I noticed until then were reasonable but 100% ?! A few minutes with DRAW and debugger root-caused a face and the code in charge. It was a tiny face that generated the excess. Debugging revealed that BndLib_AddSurface::Add() simply extends the bounding box to encompass all the poles of the underlying NURBS surface. Thus, even for a small face on large surface it adds a bounding box of a surface.



This seems to be a trade-off between speed and accuracy. In some cases such a rough approximation probably may even help – for instance, in some intersection algorithms. But it also may have a downside – in visualization. Imagine the following scenario. Create a brep model (from scratch or read from a file without triangulation), try to visualize it, internally it will compute a bounding box to define deflection, bounding box can be significantly larger than the original shape and hence a deflection will be larger. Save it to a brep file (it will store triangulation). Read it back and try to visualize again. This time it will compute bounding box using triangulation and chances are it will be smaller, and deflection will be smaller. Triangulation will therefore be recomputed and visualization mesh will be finer. Save it again and repeat ;-). So if you see examples when you import a brep file, visualize it, save it back and see different file sizes and/or finer display, this can be it!

I will never stop being surprised by Open CASCADE ;-)

You May Also Like

3 comments

  1. Maybe it would be better to calculate the first approximate bounding box with a really coarse triangulation, that gives anyway a good bounding box. Or just use the wires to limit the boundingbox of a face.

    In effect is a bit strange :)

    There a lot of things that could be improved in OpenCascade, but the community is not really involved in that!

    ReplyDelete
  2. Hi Roman,

    I remember having a similar problem, which I can't reproduce now... I was constructing a face using BRepOffsetAPI_ThruSections based on (opened) spline curves and wanted to compute the bounding box for it. The BB was much bigger than the face itself and I guess I wasn't displaying the shape.

    Pawel

    ReplyDelete
  3. Hi Roman,

    I've been following your notes for some time. In my opinion "Topology and Geometry in Open Cascade" is an excellent, although short, introduction into Open Cascade concepts. I remarked you spent some time on figuring out (some of) the (speed-wise) bottlenecks of the boolean operations. As there are many posts on the OCC forum regarding the speed/robustness of the OCC booleans, I must admit I'm surprised nobody is interested in non-regularized booleans. I played with the ACIS kernel about one year ago. As I recall non-regularized booleans can be very conveniently performed with ACIS whereas no such option exists in OCC. Open Cascade is around for a while, therefore I really doubt nobody (except me :) ) was interested in these non-regularized booleans so far. I work in the field of numerical modeling of microwave circuits by BEM/FEM. The topology/geometry of the structures I need to model is relatively simple, thus I emulated the non-regularized booleans I needed (sometimes building the topology, "by hand" from vertex to solid).
    Could you shed some light on this (regularized vs. non-regularized) matter ?

    Vali Catina

    ReplyDelete