Last week, I wrote, in Solving the CAD concurrency problem, about 2D geometric constraint solvers.
Solvers are one of the major components used in 3D CAD programs, and are the main part of the sketcher used in parametric feature (history based) modelers. They’re also used behind the scenes in direct modeling CAD systems. They’re pretty important, and have a significant effect on a CAD program’s performance.
Cloud Invent, a small software developer, made up—so far as I can tell—mostly of PhD mathematicians, recently posted a couple of interesting videos on YouTube. The first video showed the performance of the sketcher in PTC Creo Parametric 1.0, when dealing with massively large sketches.
The next video they posted was of their “Cheetah” solver, running on an identical sketch.
If you take the time to watch these two videos, you’ll see a couple of important things. First, the Creo Parametric solver seems to fall apart (become unstable) once faced with a large sketch. And the Cheetah solver doesn’t.
I chatted (by email) last week with both the folks from Cloud Invent, and from PTC, to try and understand what I was really seeing. I also duplicated the demo from the videos using Autodesk Inventor, which uses Siemens PLM’s 2D DCM constraint manager.
Lev Kantorovich, from Cloud Invent, responded to my questions.
Q: What are you doing differently in Cheetah that what’s being done with other 2D constraint solvers?
A: The main advantage of our solver is that it has O(n) memory and time requirements (to compare, solver of PTC requires O(n2) amount of memory and O(n3) arithmetic operations to solve a system of constraint equations. The situation is similar with other solvers).
Modern solvers (that of PTC) use general purpose methods of linear algebra. But the system of linear equations that appears in CAD is not “general purpose” – the matrix of such a system is very sparse. We know in advance that each row of this matrix has a fixed number of non-zeros (let’s say, not more than twenty non-zeros). If you can use this information efficiently, you will dramatically improve performance and decrease memory requirements of the solver.
That is exactly what we managed to do in our Cheetah solver. I do apologize that I can’t provide you the detailed information about our algorithm (there is a remarkable mathematic work behind this and five or six PhD dissertations in some of the leading USA universities – in the end of the nineties this issue was in focus of the researchers), but I want to mention one additional advantage of the approach – our methods are well suited for parallel processing.
Q: Are you supporting 3D constraints?
A: So far we tested our solver in 2D sketcher only, but I don’t see any reasons why it shouldn’t work for 3D constraints as well. Actually, this is the most interesting direction.
Traditional parametric CAD lives only in 2D sections – this is part of “parametric feature-based approach” to solid modeling. The reason for this is quite simple – these solvers can resolve only small models. That’s why complicated solid model is divided into hierarchic list of simple features (each one having its own parametric sketch) – known as “history tree”.
But we have a solver that is powerful enough to constrain the whole 3D model (using all reasonable 3D constraints). Now we can try to go away from the feature based approach with its notorious history tree and to unify in one 3D workspace parametric and direct modeling approaches. This is, actually, our main target.
Q: On your website, you say other solvers solve equations in the wrong manner, “using archaic numeric methods” (e.g., Newton iteration, Gauss eliminations and Gram-Schmidt orthogonalization.) That hints that you might be using symbolic methods—or perhaps a hybrid numeric-symbolic method?
A: No, we don’t use symbolic methods.
Our method may be described as:
By using the specifics of the system of linear equations (very sparse matrix), we subdivide the set of all equations into small groups and solve these small subsystems corresponding to these groups. Each subsystem has fixed requirements for memory and computation. The tricky part is how to choose these groups and how to coordinate data exchange between them – we use the iterative approach for that.
Q: You say that you have O(n) memory and computational efficiency. That accounts for number of geometric elements (n), but what about number of constraints (m)?
A: In Cheetah the number of arithmetic operations that is required to resolve system of equations is O(m), i.e., proportional to the number of constraints. It means that if you have millions of geometric entities, but few constraints, the system will be resolved fast.
Q: I’m not clear if you’re solving linear or non-linear equations.
A: We solve non-linear equations, but we do it in the standard way – by linearization on each step of non-linear iterations. Normally, there are very few non-linear steps (two, three, rarely more). Our “know how” is in solving corresponding linear equations.
Q: Can you give me more detail on your support for parallelism?
A: The parallelism is based on what was written above about our method – each small group of equations can be processed independently. The author of this method, Nick Sidorenko, thinks that what we doing is quite new.
Q: You don’t mention anywhere what type of objects you support (e.g. points, lines, circles, arcs, ellipses, planes, cylinders, spheres, NURBS, parametric curves, surfaces), or what type of constraints you support (e.g. coincidence, parallelism, tangency, curvature, etc.)
A: At this moment we have only the prototype. We were focused on proving concept of the algorithm (solving system of the sparse linear equations). We tested it with the 2D sketcher; we haven’t tested yet 3D objects (planes, cylinders, spheres, NURBS, parametric curves, surfaces).
Q: Do you have a Cheetah solver prototype available yet?
A: The prototype will be available soon for download from our site. It works at the moment with line segments and circles only. The set of constraints is also restricted – horizontal, vertical, same point, equal, parallel, perpendicular, tangent (between line and circle). It is also possible to set length of a line segment, distance between two points, radius of a circle, angle between two lines.
Once again, our goal was not a full range parametric sketcher. We used FreeCAD as a test platform for the algorithm. Perhaps, in the nearest future we’ll add more geometric entities (at least, circle arcs, and, may be, ellipses) and more geometric constraints.
Since Cloud Invent was using Creo Parametric as an example of a typical 2D solver, I wanted to get a response from PTC. Brian Thompson answered my questions.
Q: Do your customers seem generally satisfied with the interactive performance of the sketcher?
A: Yes, except when importing some large cosmetic sketches – i.e., something that users don’t want to reference in another feature. For this use case, our cosmetic sketch can be unconstrained, allowing much larger sketches to be imported without solver involvement.
Q: Does the sketcher’s performance have a significant effect on the overall regeneration time for 3D parametric models?
A: No, because highly complex relationships are generally not captured in sketches. They are generally captured at a higher level.
Q: Has your solver fundamentally changed in its underlying design from the early days of Pro/E?
A: Very tough question depending upon how you define “fundamentally”, but yes. Consider that early sketches had to be regenerated, while now we have a constraint-based solver. Then, consider that this constraint-based solver has had significant performance enhancements since its inception.
Q: Do you anticipate any significant improvements in the future, such as using some of the more modern developments for parallel solutions of systems of linear equations?
A: 2D is an area that we will continue to invest – improvements in 2D user experience and performance will be on the table for many releases to come as our 2D strategy on the Creo platform grows and matures.
Julie Blake, of PTC, also responded, when I pointed out the Cloud Invent videos to her:
As you could tell I’m sure, the video is a very academic example, not something used in production. However, the sketching environment overall is something that is important to PTC and is of course fundamental to geometry creation in any CAD application. The Creo team has continuously worked to improve the sketcher performance over the past several years and our general 2D capabilities – regardless of which app they are in – are expected to be a continued area of focus for us over many releases to come.
Julie was right. The Cheetah solver is not a commercial product yet. Though I suspect they have the first 90% of the work done on it, that just means they need to finish the other 90%. (That’s a software developer’s joke.)
As I looked carefully at the Cloud Invent video that showed Creo’s performance, what I saw, reading between the lines, was not instability in the Creo 2D solver. Rather it was a performance issue. With a very large sketch, the interactive performance of Creo got sluggish. If you just move and click your mouse when the system is responding slowly, you’re going to get unpredictable results. This is true with Creo, or with any interactive computer program.
I can’t say that I’m completely pleased with Creo’s ability to handle really large sketches. Yet, I’m not the one using the program. If Creo users are generally happy with its performance in this realm, then it’s good enough by my book. Creo’s support for unconstrained cosmetic sketches provides a reasonable solution for very large sketches. (If you’re a Creo user, and have any thoughts on this, please add a comment below.)
I find what Cloud Invent is doing to be quite interesting, and I’m hopeful that they’ll be able to get their product to point where it’s commercially viable. I suspect, though, that their best path to market may through working with (or being acquired by) a major CAD or components company. Preferably one with a whole bunch of users who’ll benefit from having access to Cloud Invent’s technology.
