Tuesday September 2, 2014

Cheetah, Creo, and 2D geometric constraint solvers

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.

  • http://twitter.com/DevonSowell DevonSowell

    interesting

  • http://twitter.com/DevonSowell DevonSowell

    the bizarre sounding audio tracks makes it difficult to view these videos

  • http://jonbanquer.blogspot.com/ Jon Banquer

    ” The author of this method, Nick Sidorenko, thinks that what we doing is quite new.” 

    Seems like he should know. The Cloud Invent website mentions that Nick Sidorenko worked for PTC in development. Based on what’s written on the Cloud Invent website it’s obvious Nick Sidorenko thinks the Creo constraint manager, as well as all the other constraint managers, have very serious issues.

    I don’t use Creo but I do use SolidWorks. There is no doubt in my mind that the SolidWorks constraint manager has very serious issues that never get the attention they deserve. This can easily be determined by anyone who takes the time to read the SolidWorks Forum where one can find numerous complaints from many users about SolidWorks constraint manager issues.

    SolidWorks uses the Siemens D-Cubed 2D DCM constraint manager. Here is just one of the many reasons Missler Software’s TopSolid CADCAM 7 doesn’t use Siemens D-Cubed 2D DCM constraint manager.

    http://www.youtube.com/watch?v=-y8T6R8IXmQ

    It seems to me that it’s Nick Sidorenko that needs to be interviewed. It concerns me how little the Cloud Invent website has been updated in the last year. I’m sure there is a reason for that but I am unable to determine what the reason is.

    Jon Banquer
    San Diego, CA
    http://whymastercamisthewrongchoice.blogspot.com/

  • http://evanyares.com Evan Yares

    Actually, I’m not so sure that Nick Sidorenko would know whether what he’s doing is new or not.  Some numeric methods are published, in academic papers.  But some aren’t.  For example, much of the work that D-Cubed does is never published.  It’s kept as “trade secret.”

    SolidWorks may have issues with constraints.  But those issues may have to do with their implementation of D-Cubed.  Remember, they originally built their software 18 years ago or so.  Have they updated, to use the latest D-Cubed tech?  Have they looked at *how* they use 2D DCM? I don’t have the answers to these things… and I suspect that no one but programmers inside of SolidWorks and D-Cubed really know the answers.

    DS does have experience migrating from D-Cubed to their own solver (which I understand was developed in conjunction with Ledas, in Novosibirsk.)  So, I don’t expect to see serious problems if and when they choose to migrate the new version of SolidWorks (V6) to that solver.

  • Jon Banquer

    SolidWorks 2012 did not use the latest version of the Siemens D-Cubed 2D
    constraint manager which included support for conics and was released
    almost a year ago:

    http://www.youtube.com/watch?v=_mwNItlxtC8

    SolidWorks 2013 beta was just released a few days ago. Not sure if it will use the latest version or not.

    Based on today’s press release in regard to Bricsys 2D and 3D constraint
    solvers perhaps it’s time to try and interview Dmitry Ushakov and ask him some
    questions about Cloud Invent’s claims and whether he concurs. It would also be nice to know what CAD applications are using Bricsys 2D and 3D constraint solvers:

    http://www.bricsys.com/common/news.jsp?item=542

    “The software development team of Bricsys Technologies Russia, a fully owned
    subsidiary of Bricsys NV and led by Dr. Dmitry Ushakov, continues the
    development of the state-of-the-art constraint solving technology currently
    embedded into dozen engineering applications including Bricscad V12.”

    “Based on a combination of advanced decomposition methods and a
    reliable non-linear solver, LGS 2D solves drawings with thousand geometric and
    dimensional constraints in less than a second.”

    “The secret of efficiency of LGS 3D (which is able to solve problems with
    thousands constraints in less than a second) is mainly located in its
    sophisticated decomposition methods, which split a large initial problem into a
    set of smaller ones. Version 6.0 contains a lot of new decomposition patterns
    introduced by analysis of different industrial cases. There are also several
    important improvements in the non-linear equation solver. Version 6.0 also fixes
    several problems reported by customers, including some cases with unnatural
    solutions, which are now solved naturally.”

    Jon Banquer

    San Diego, CA

    http://cadcamtechnologyleaders.blogspot.com/p/fully-integrated-cadcam.html

     

  • http://evanyares.com Evan Yares

    Good call on the 2D DCM video.

    I know Dmitry, and have actually been to visit Ledas in Siberia.

    Regards Cloud Invent’s claims: you sort of nail the essence of them with this quote:

    “The secret of efficiency of LGS 3D… is mainly located in its sophisticated decomposition methods, which split a large initial problem into a set of smaller ones.”

    Problem decomposition seems to be at the heart of most efficiency improvements in solvers, whether in LGS, DCM (which claims to be able to achieve O(n) in some cases), or in Cheetah.

    Bottom line is that Cheetah is *not* a commercial product yet.  It took Ledas years to get LGS 3D to the point where it is.  This stuff takes time.

  • Cary

    In a common practice or design, elements in a 2D sketch are not all inter-related, and typically the coefficient matrix of the constraint solving system is a sparse matrix. In such case, will the performance (without using the Cheetah solver) be so slow as shown in the video? 

  • Nick Sidorenko

    Just one small update that was done today – now you can download FreeCAD (with Cheetah inside) from our web site:

    http://www.cloud-invent.com/FreeCAD.aspx

    Enjoy,
    Nick Sidorenko

  • http://jonbanquer.blogspot.com/ Jon Banquer

    Downloaded FreeCAD (with Cheetah inside) from your web site. Now reading the included helpful PDF.

    Jon Banquer
    San Diego, CA
    http://whatwrongwiththecadcampress.blogspot.com/