Home -> Projects -> B-Rep CAD kernel
For this project I often worked with Andres Erbsen and discussed it with several others, including Istvan Chung, Isaac Grosof, and Herng Yi. The project will be released under some version of GPL and potentially other licenses.
The two common 3D representations for mechanical CAD are boundary representation (b-rep) and function representation (f-rep). In a b-rep model, the solid is represented as a set of (oriented) bounding surfaces. These surfaces in turn may be composed of line segments, points, arcs, etc. In an f-rep model, the solid is represented by a function. The boundary of the solid is given by the zeros of the function, the interior by negative values, and the exterior by positive values. Depending on the type of f-rep, the magnitude of the function may also encode the shortest distance to the surface.
Most academic and free/open source CAD programs use f-reps. It turns out to be much easier in practice to write a correct f-rep CAD program than a b-rep program. Many useful CAD operations can be encoded by the composition of simple functions (min, max, etc) and geometric primitives typically correspond to simple equations.
While many operations are simple in f-reps, some useful mechanical operations are hard to implement. For example, it is hard to represent the instruction “round this edge” in an f-rep kernel. It is also inconvenient to extract geometric data from the current model to build off of it (i.e. create a circle tangent to the circle resulting from a revolve command – instead the user has to do the math themselves to produce the correct circle).
B-rep corresponds closely to how engineers typically think about solids and tends to have simple encodings for common mechanical operations. It’s easy to round edges, or make holes line up, or reference a new object relative to the edge of one that is already created. While f-reps are more popular in academia, industry standard mechanical CAD programs all use b-reps.
It is much harder to make correct b-rep kernels than f-rep kernels. As a result, there are no free b-rep kernels (that I am aware of) – they simply take too much time and effort. There are two b-rep kernels used in industry, ACIC and Parasolid, and all industry CAD programs license them. It is estimated that creating a functional b-rep kernel by standard methods would take at least 120 engineering man years [citation needed].
B-rep kernels are hard to implement correctly because instability in numerical calculations can cause topological problems. Imagine that you are cutting a hole in a cube approximately all the way through to the far face. The exact depth of the hole matters a lot – if it’s exactly all the way through then the representation of the far face needs to be modified, but if it doesn’t quite reach the far side then the topology doesn’t change. Similarly, in many situations “simple” b-rep algorithms would compute a point twice by two different methods, but this might not be acceptable because the computations might not come out exactly the same and it would be unclear if the two points were equal or not. B-rep kernels must work around this problem.
Commercial CAD systems use constraint solvers to resolve their models. In some ways this is convenient: the user can model objects independently, leaving some number of degrees of freedom (DOFs) unspecified, and later constrain them relative to each other to constrain those DOFs. Since all commercial CAD systems depend on constraint solving, it has become a standard part of the professional CAD workflow.
However, constraint solving has significant downsides. When the CAD program resolves a model’s constraints, it is supposed to find a way to solve that’s “similar” to its previous solution so the model doesn’t change in a way the user doesn’t expect. Of course, this requirement is not well defined and CAD software does not always meet it (even though companies invest lots of effort in preserving model semantics between solves). It is widely considered an important skill in the CAD community to design models that behave sanely under the CAD program’s constraint solver. The way I see it, that’s a way of saying that it is left to the user to deal with a finicky program.
Propaganda: Constraint solvers are wrong. Instead of piecing together two objects independently and later constraining the to each other, objects can only interact with fully defined before they are fully defined. This constraint on workflow creates a clear dependency tree for CAD objects, substantially reducing the demands on CAD programs. As a side effect, it would also make it easier for the user to understand what the CAD program is doing for them and thus let them use it more effectively.
Unfortunately, constraint solving is occasionally significantly easier than defining objects based on fully defined objects. I would consider it reasonable for CAD programs to have a constraint solving mode for this purpose, so long as users couldn’t stay in this mode for too long. If used responsibly, occasional constraint solving wouldn’t make the CAD model unstable.
In this project, I am designing a new b-rep kernel. I know I just told you that this task should take ~120 man years to complete by standard methods, but I believe I can improve upon these methods and make the problem substantially easier. In particular:
As far as I can tell these are the most difficult parts of a b-rep kernel, and by avoiding them I hope to save most of 120 man years of effort.
I worked with two ideas for avoiding numerical stability issues. This first (and most pure) idea is to solve everything symbolically. I prototyped this method with sage/sagemath, a free open-source symbolic algebra system built on python. I tested with 2D CAD, and wrote functions for generating lines and circles independently and tangent to each other. The test was successful, but I was unable to convince myself that sage (or some other solver) would always be able to decide inequalities (which is important for intersections). I shelved symbolic solving temporarily to explore other options. There are more details on symbolic solving below.
The other major idea for avoiding numerical stability issues is to use interval arithmetic to track error during calculations. The idea behind this approach is that error in the model is acceptable as long as it is bounded by a sufficiently small number (say the tolerance of the machine eventually used to produce the part or the precision of the device used to take measurements to produce the model). Under this model topological stability isn’t required – thin gaps and thin connections can be treated the same way by the CAD program. This should not be important when it comes time to produce a physical part (do physics simulations, etc) from the CAD because “thin” can be chosen to be sufficiently small that the mass in that volume has no structural importance.
The output is the specification of a volume such that each point is correctly labeled as inside or outside the volume if all points within the sphere of (radius) tolerance share the same label in a perfectly constructed volume. Notably this definition allows for arbitrarily bad representations of surfaces (as long as the representation stays close to the surface). I’m ok with that for now, but it should be possible to provide bounds on the number of features created and where these features come from.
This is a useful specification for the user, but not the specification the CAD program needs to operate on. In particular, the CAD program produces primitives (lines, circles, etc) as a function of variables (endpoints, center/radius, etc) and it can handle tolerances on these variables. The relationship between these types of tolerance is expressed by the point containment algorithm – in addition to producing an answer for whether or not each point is contained by a volume, this algorithm needs to produce maximum allowable tolerances on each variable from the user-specified tolerance on the volume.
Once all tolerances are expressed as maximum allowable variation on variables used to construct primitives, back-propagation of error is more straight-forward. For every method of constructing a primitive there must be a function that produces the required tolerance on its inputs to produce a given tolerance on its outputs. Furthermore, this function is not allowed to “blow up” and require arbitrarily good input tolerance to produce reasonable output tolerance.
It turns out to be difficult/impossible to do interval arithmetic on floats because processors don’t give guaranties on the precision of floating point operations. However, it should be possible on large integer/fixed point implementations to track tolerance arbitrarily well. Also, it should be possible to make all intervals end on rational numbers (think Taylor approximations of square roots, centered on a floating point approximation of the correct answer) and do lossless computation on the rational bounds. Either of these models of computation should work for interval CAD.
This topic goes beyond my understanding of mathematics, but precise definitions on interval CAD might actually make it equivalent to symbolic CAD. My understanding is that polynomial symbolic solvers keep track of polynomials and intervals that bound the relevant roots of these polynomials. If the user can guarantee that any points they enter/“care about” are either separated by the specified tolerance or symbolically equal that might be a strong enough guarantee to prove interval CAD and symbolic CAD equivalent. Probably in order to make them equivalent interval CAD would have to keep track of polynomials as well, but my understanding is that correctly handling intervals around roots is the hard part and doing math on polynomials is the easy part of symbolic solving.
TODO