Open CASCADE notes

Standard allocator interface.

2011-11-24T20:12:00.002+04:00

As you know, Open CASCADE has its own memory allocation mechanism, which entry points are Standard::Allocate() and Standard::Free(). They forward (de-)allocation requests to a current memory manager, which can either be a). default system allocator (if environment variable MMGT_OPT=0), b). own Open CASCADE's (MMGT_OPT=1), or c). Intel TBB (MMGT_OPT=2).

Most Open CASCADE classes (e.g. all which are defined in .cdl files) redefine operators new and delete to use Standard::Allocate() and Standard::Free() respectively – look at any .hxx file.

Using common memory allocation mechanism allows to decrease memory footprint and/or increase performance, especially when using TBB allocator (in multi-threaded apps). However, you may easily miss this advantage in your application in the following typical cases:
1. You dynamically allocate objects of your classes and their new/delete operators do not use Standard::Allocate()/::Free().
2. You use standard containers (std::vector, std::map, std::list,...).
#1 is easily addressed by redefining new/delete operators in your base class(es) in a way similar to OCC.
#2 is more tough, as standard collections by default use standard allocator (std::allocator<T>). So all auxiliary elements (e.g. list nodes) are allocated outside of OCC-governed memory allocator.

This was until now. Hereby I would like to share a code that implements the standard allocator interface as defined by the ISO C++ Standard 2003 (and also conforming to a recently published C++11). Download Standard_StdAllocator.hxx.

This is a pure header implementation, so no .cxx files and linking with libraries is needed; just copy to your project and start using. Implementation is derived from Intel tbb::tbb_allocator, which itself just follows the C++ standard requirements.

The file is intentionally made copyright-free and put into a Public domain, the most permissive way. I also hope that the OCC team will be willing to pick up this file and integrate into OCC.

The simplest example can be as follows:

typedef Standard_StdAllocator<void> allocator_type;

std::vector<TopoDS_Shape, allocator_type> aSVec;
TopoDS_Solid aSolid = BRepPrimAPI_MakeBox (10., 20., 30.);
aSVec.push_back (aSolid);

std::list<int_Shape, allocator_type> aList;
aList.push_back (1);

There is also a unit test (download Standard_StdAllocatorTest.cxx). The code is based on Qt test framework and should be self-explaining to port to any other test framework.

Those who are curious enough may offer similar standard allocator implementation for NCollection_BaseAllocator which is used in NCollection containers. It is as straightforward as this one.

Is my memory leaking? Part3.

2011-06-19T20:30:00.002+04:00

(continued)

OK, now when you have some clues of possible root-causes, what's next ?

#1.If you believe you found a memory leak, first of all, do not panic. Be patient to identify if this is a true leak or a false positive. For that:

#2. Use efficient memory checking tools (Intel Parallel Inspector XE, Valgrind, etc).

#3. If you want to exclude custom memory allocator, be sure to set environment variable MMGT_OPT=0 and experiment further.

#4. If the issue has gone and you suspect it to be an allocator problem, then the chance is that it's a false positive, not an allocator issue. Though you may continue investigating, of course ;-).

#5. When designing architecture of your application, make sure you understand how your memory is managed. Do consider consistent use of smart pointers – e.g. boost's or Open CASCADE handles. That will save you multiple hours of tedious debugging.

#6. If you are paranoic about memory consumption then you might want to periodically call Standard::Purge() when using the OCC allocator (MMGT_OPT=1). It is supposed to free unused small memory blocks. You could do this when closing the MDI doc, for instance. (I never used myself though.)

#7. Advanced developers may want to step further and use fine-tune optimization techniques like use of memory pools (or regions). See NCollection_IncAllocator as an example of such. NCollection containers can accept it as an extra argument. TBB is going provide support for thread-safe pools in future versions.

#8. Black belts may also want to experiment with memory tracing routines that have been enabled in OCC allocator. See Standard_MMgrOpt::SetCallBackFunction() which is called after each alloc/free. This can be any user callback function that traces sizes of requested/freed chunks, addresses, etc.

So, here is what I was able to recall on this subject, and hope it will be helpful.
As I said in the beginning, any extensions or other best practices are welcome.

Roman

Is my memory leaking? Part2.

2011-06-09T20:45:00.002+04:00

(continued)

Having discussed possible symptoms, now let's try to understand their possible root-causes.

1. True leaks.
When developing in native (C/C++) code you may just forget to free allocated memory. This can be for example:

a. Something as simple as such:
{
char* p = (char*)malloc (1 * 1024);

//do work...

//free (p); //will never forget to uncomment this later
}

b. Architecture design deficiency. Unclear object ownership, management of their life-span leading to failure in proper destroying objects.
I found this shortage in Salome (the SMESH module in particular). There is proliferation of plain pointers (not smart pointers, like boost::shared_ptr) with complex dependencies between objects. I presume multiple developers maintaining the code just forgot some day which objects should destroy which. Here is the most recent work-around I had to make – to destroy sub-meshes in SMESH_Mesh you have to call SetShapeToMesh() with a null shape. This will destroy all objects stored in internal map which otherwise will be leaked (the SMESH_Mesh::~SMESH_Mesh() destructor does not destroy them):

/*! Frees resources allocated in SMESH_Mesh which otherwise leak
- bug in Salome.
*/
Mesh_MeshImpl::~Mesh_MeshImpl()
{
TopoDS_Shape aNull;
mySMesh->ShapeToMesh (aNull);
}

where mySMesh is defined as follows:

boost::shared_ptr mySMesh;

c. Cycles between smart pointers. If you have two smart pointers referring to each other, they won't get destroyed (as reference counter will never reach zero). I described this issue in the very first post.

True leaks are usually well caught by memory checkers.

2. Memory caching by memory allocators.

Many complex software comes with integrated memory allocators that are able to manage memory more efficiently (at least in terms of speed and/or footprint) than default allocators (part of OS or C run-time library). Open CASCADE comes with its own (activated by environment variable MMGT_OPT=1), with Intel TBB (MMGT_OPT=2), or default system allocator (MMGT_OPT=0).

Though OSes provide better and better allocators, custom ones are likely to stay for foreseeable future due to efficient solving of particular problems (e.g. thread-safety and scalability as TBB). If you are curious, you might want to check some comparisons I conducted with default, OCC and TBB allocators here.

The central idea of allocators is caching and reuse of previously allocated memory chunks for further allocations. Thus, when your application object is destroyed, its memory is effectively retained by the allocator and is not returned to the system. That is why, in particular, you won't see in Task Manager the memory level returning to the previous level even if all your document objects got destroyed after closing the MDI document. Allocators may apply different policies to retain/return these memory blocks. For instance, both OCC and TBB have different approaches for small and large blocks; the latter are returned faster (as the chances of their reuse are smaller), while the former may never be returned until application terminates.

3. Static objects residing in memory.

It is a wide spread practice to create static objects which live throughout the application life-time and get destroyed only upon program termination. Consider this:

myfile.cpp:

static boost::shared theSingleton = new MyClass();

MyClass* MyClass::Instance()
{
return theSingleton.get();
}

theSingleton will be created during loading the library containing it, and will be destroyed when it is unloaded (effectively when the application terminates unless it is explicitly unloaded before that).

There are multiple examples of such constructs in OCC code.

Below is the Inspector screenshot of the (false positive) leak reported on the screenshot in Part1:

Static objects in TKTopAlgo

4. Unused data residing in memory.

Similar to above, there are cases when some data are stored with the help of static objects and used to pass between the algorithm calls. I gave some examples in an earlier post. I believe this is a bad design and should be avoided but it may happen in third-party code. It's not really a leak but essentially wasting memory, which again only gets freed upon program termination.

(to be continued)

Is my memory leaking? Part1.

2011-06-02T12:45:00.006+04:00

There often appear posts on the Open CASCADE forum, either as questions or as blames that there are persistent memory leaks. Truth to be told, this happens on many forums of other software products I visited, so this is not something OCC-specific.
So I'd like to shed some light, which would hopefully help someone to understand the issue in the future. As always, extensions and any comments are welcome.

So how one detects there is a memory leak? I would suggest the following possibilities (presumably in the order of decreasing frequency of use by developers):

Using Visual Studio built-in features
(I never use these though).
Put the following lines in the source file or your executable:

#define _CRTDBG_MAP_ALLOC
#include <stdlib.h>
#include <crtdbg.h>

And into the main() function:
_CrtSetDbgFlag ( _CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF );

For more information you can read this MSDN page (select appropriate VS version).

Under the debugger, in the Output window you will see something like:

Detected memory leaks!
Dumping objects ->
{35171} normal block at 0x04CD0068, 260 bytes long.
Data: < > 02 00 00 00 00 00 00 00 CD CD CD CD CD CD CD CD
{349} normal block at 0x0330E350, 100 bytes long.
Data: < > CD CD CD CD CD CD CD CD CD CD CD CD CD CD CD CD
{246} normal block at 0x03309390, 108 bytes long.
Data: < E ( > 01 00 00 00 1A 00 00 00 45 01 00 00 28 0A 00 00

Once you see this you might find yourself yelling – "how may this !@#$% product exist with such fundamental bugs ?!!". But as soon as you see this attributes to your code, you may go "hmm, is this really an error?" As you start digging deeper, things may go different ways. You may discover a bug in your product or a tool limitation (the latter is more likely though).

Windows Task Manager
You notice the level of consumed memory before you start some piece of your code (e.g. opening a document in an MDI application).

MDI app memory level before opening a document

Then do some actions and see the new level. For instance, after closing the document in the MDI app, you would expect the level returns to a previous one. If not (and as a rule, not!) you start asking why.

Same app memory level after closing an opened document

Specialized memory checking tools
This includes Valgrind, Bounds Checker (never used those two), Rational Purify, Intel Parallel Inspector XE, etc. I used Purify in late 1990es and as of 2008 sticked to Intel Inspector. Here is a sample report generated by Inspector:

Intel Parallel Inspector XE reporting memory leaks

You can try an evaluation version on the Intel site here.

Debug print
Adding simple outputs in constructor and destructor is simple yet effective practice to quickly check if your object is destroyed whenever you expect.

Custom memory checkers/profilers
You might want to write some ad-hoc memory profiler – some hooks that trace allocation and deallocation routines (malloc/free, new/delete) – counting allocated and deallocated bytes. I myself created one when tracing memory in CAD Exchanger. If there is sufficient interest, I could publish it. The idea is to detect pieces of code where you expect that all allocated memory during that region will be deallocated upon its end.

(to be continued...)

6.5.0 Visualization Highlights. Part2

2011-05-16T23:02:00.004+04:00

Integrating new gradient support I noticed that the Visual3d_Layer class has been extended to contain multiple items called Visual3d_LayerItem. Exploring this further I realized that this was a way to offer an extensible way to support multiple user-defined objects. One of these is a color scale in a 3D view defined as V3d_ColorScaleLayerItem subclass.

Experimenting with this new concept I went on to redefine the way how the CAD Exchanger logo was implemented. It is a part of the over-layer, one which draws 'on top' of objects in a main scene. See the screenshot below:

Logo displayed in front of a 3D model

So I subclassed Visual3d_LayerItem and redefined its RedrawLayerPrs() method to do the actual work. Check this archive to see the full code.

Here is how you can add this object into the layer:
//create an overlayer
Handle(V3d_View) aView = ...;
Handle(Visual3d_Layer) anOverLayer = new Visual3d_Layer (aView->Viewer()->Viewer(), Aspect_TOL_OVERLAY, Standard_True /*aSizeDependant*/);

...
//create a texture layer item
const Handle(Visual3d_Layer)& aLayer = aView->Viewer()->Viewer()->OverLayer();
Handle(QOOcc_TextureLayerItem) aTexture = new QOOcc_TextureLayerItem (QImage (":/viewlogo.png"), aView, aLayer.operator->());
aTexture->SetPosition (Aspect_TOC_BOTTOM_RIGHT);
anOverLayer->AddLayerItem (aTexture);

This way you may add as many items as you want. The only downside (or assumption if you will), which is likely in place is that all items have to be drawn with the same coordinate system that needs to be supported for the layer (using Visual3d_Layer::SetOrtho()). So RedrawLayerPrs() needs to be written with a single convention in mind, and you seem unable to work with individual settings. It would be great to hear whether this assumption is correct or not – from both the OCC folks and anyone having practical experience.

6.5.0 Visualization Highlights. Part1

2011-05-16T22:41:00.003+04:00

Open CASCADE 6.5.0 has introduced a few nice (undocumented, as often) features in its Visualization module and I'm going to highlight a couple of them today. Even if the version 6.5.0 made some mixed impressions (with regressions in BRepMesh being most unpleasant ones), visualization was really nice. So kudos to the involved folks!

When migrating CAD Exchanger to 6.5.0 I wanted to rework the way a gradient background is displayed. The previous way was described in the old blog post. 6.5.0 has added a 'built-in' support for gradients offering various options (horizontal, vertical, diagonal, corners, etc). Below is a sample screenshot made in DRAW:

Built-in gradient background support in 6.5.0 (using diagonal1 option).

You might want to experiment more using the vsetgradientbg command. The new API can be used as simply as follows:

Handle(V3d_View) myView = ...;
if (theEnable) {
myView->SetBgGradientColors (myTopBackgroundColor, myBottomBackgroundColor, Aspect_GFM_HOR, Standard_False);
} else {
myView->SetBgGradientColors (myTopBackgroundColor, myBottomBackgroundColor, Aspect_GFM_NONE, Standard_False);
}

Thoughts on Git repository and community

2011-03-22T00:13:00.002+03:00

Thomas Paviot announced a git repository that is aimed to accumulate community produced patches in an effort to systematize and ease their production and use. That effort addresses very limited community support from the OCC company side which often begs a question of the company's commitment to Open Source model. That often provokes emotional debates on the forum and I suggest that we put this offline (we can continue in a separate topic though).

I view Thomas' effort as much more constructive than typical claims, so it does deserve recognition, at least in my eyes. I appreciate it like other efforts, including a Wiki site initiated by Fabian Hachenberg, multiple fixes from Denis Barbier and Peter Dolby, numerous projects showcasing and leveraging OCC (pythonOCC by Thomas Paviot and Jelle Feringa, Salome ports by Fotios Sioutis, qtocc by Pete Dolby, etc) and even simple bug reports. As the old saying goes, "it's better to light a candle than to curse the darkness". So every constructive input is more valuable than an emotional claim.

This post is to share some initial thoughts. I suggest that we continue discussing details of Thomas' proposal on some other place, not the org forum. This is just to avoid unnecessary potential sensitive issues. The blog format is likely not too convenient either and another forum (e.g. on wiki) could be preferred.

Repository structure
Let's start with something simple and clear. Arthur Magill has suggested a 3 level structure which I would simplified down to 2:
- One master (mainline / trunk) branch per each OCCT version. The branch would start with pristine version of OCCT (say 6.5.0) and incrementally accumulate fixes. There must be reasonably strict gatekeeping process to maintain it stable. Fixes must be code-reviewed and tested to make this branch.
- Set of experimental branches maintained by individuals, projects, etc. These are sandboxes where volunteers can maintain their own version and which can contain fixes they selectively pick up or produce. No gatekeeping, everything is up to an owner.

Master branch commit process
To make the master branch as stable as possible, some efforts must be applied. I would start with 3 most important:

Code completeness. For instance, if you modify the header file then modify both original .cdl file (if applies) and .hxx file. If you modify a .vcproj file for Visual Studio 2008 32 bit then modify files for other flavors of Visual Studio (e.g. 2005, 2010, 32 and 64 bits) and automake files.
Testing. Apply reasonable effort to test your modifications.
Code review. OCCT is complex and caution must be taken to analyze potential implications (side effects, performance, memory footprint, platform specificities, etc). Ultimately, the best would be to have single decision maker(s) to approve or veto the modification. Participation of OCC team lead engineers would be really helpful. Ideas are welcome.

In the end of the day, the patch should make the official version of OCCT. To make it happen, the community should apply its efforts and due diligence. I could help in code reviewing testing as far as CAD Exchanger allows.

Consolidation of community resources
To avoid unnecessary proliferation of resources and thus confusion on what to use when, I suggest we define the tools and start sticking to them. Ideally, I would love to see all this hosted on opencascade.org but given continuous unwillingness to support that let's host them outside. If we find another single platform we might want to settle down there.

Git repository – to ease fixes sharing.
Forum. To discuss issues which OCC company does not appreciate on its forum (projects announcement, company policies, etc). More feature-rich forum (e.g. typical phpBB) would help overcome limitations of the ancient org forum.
Wiki – to document knowledge, maintain useful links, etc.
(?) Bug tracking. Org forum should probably suffice unless there are volunteers to track the bugs along the life cycle.
What else ?

Sourceforge could be a good single place but my experience with it was far from smooth, so I gradually gave up. On the contrary, http://opencascade.wikidot.com is very nice to work with.

Next steps
Thus, the next steps that I see are:
1. Define a must have list of tools for efficient community functioning. Start with forum, and use this blog until that. Once the forum is defined, continue discussions there.
2. Agree on the git structure and basic policies.
3. Start using it.

I would be thrilled to see OCC folks participating in the discussions and activities as much as they can. I agree with Thomas' statement that we all share same interests.

Thanks !

3D view navigation: mouse wheel support and more

2011-02-09T18:11:00.002+03:00

With recently released CAD Exchanger 2.1 Beta, which adds some GUI improvements, I thought to share some experience about that.
Default OCC viewer suggests some conventions based on using the Ctrl button and mouse buttons:
- Ctrl + MB1 (left button) – zoom;
- Ctrl + MB2 (middle button) – pan;
- Ctrl + MB3 (right button) – rotate.
This seems to be not only inconsistent with typical conventions in CAD systems but also challenging for user experience. For instance, MB3 is normally expected to open a context menu.
So following CAD Exchanger users’ feedback, I had to implement different navigation based on Solidworks and other conventions. They are based on using MB2:
- MB2 – rotate
- Shift + MB2 – zoom
- Ctrl + MB2 – pan.

In addition, support for mouse wheel (to zoom in/out), which is a commonly used convention, has been added. For Qt-based viewer it appeared to be quite easy:

void QOOcc_View3d::wheelEvent (QWheelEvent* theEvent)
{
if (theEvent->orientation() == Qt::Vertical) {
int numDegrees = theEvent->delta() / 8; //number of degrees the wheel rotated by
//let 100 degrees be approximately 2x zoom (see V3d_View::Zoom())
int numSteps = numDegrees;

myView->Zoom (0, 0, numSteps, 0);
theEvent->accept();
}
}

Apparently, QtOCC project by Peter Dolby already implemented that (though I did not notice). But Peter used V3d_View::SetScale(). Either should work anyway.

Perhaps, wheel support could be added into default OCC viewers and default OCC conventions could be revisited to better align with industrial ones.

Parasolid developer community ?

2010-11-24T17:45:00.004+03:00

By any lucky chance, does anyone reading my blog, know any community of Parasolid developers ?

I tried to register at http://developer.hoops3d.com/forums but it seems dead - no forum threads, no approval/rejection replies, etc.

Asked the same question on http://forums.spatial.com but people there did not know :-(.

I even had a phone call with Siemens and their rep promised to help but no follow up after that :-(.

I had some clarifying questions when working on Parasolid support in CAD Exchanger but could figure them out myself. But it would still be useful moving forward.

Thanks in advance!

Adapters. Part 1

2010-11-08T21:37:00.001+03:00

Those of you who have been developing software for quite some time likely came across the adapter pattern. It's one of the classical patterns described in the famous Design Pattern's book by Erich Gamma et al. The concept is simple yet powerful allowing you to adapt one interface to another.

How different is computing an intersection between two curves and between two edges ? Not that much – you just need to minimize a function representing a distance between any two points along each. What about a distance between two wires ? Just the same. And what about an intersection between an edge and a wire ? Or between a curve and an edge? What if you need to build a tube (or pipe) surface along the curve or along the wire ? Would that make any difference? Nope, either.

OK, but how would your algorithm API look like ? Will it accept Geom_Curve, TopoDS_Edge and TopoDS_Wire all at once and in any possible combination? Wouldn't it be weird and unreadable ? What about efforts to maintain it ?

The adapter pattern is the answer. You just have an abstract class that would provide an interface, which the algorithm could use. And particular implementation (for curves, edges or wires) would be provided by subclasses.

That's exactly what is provided by Open CASCADE adapters – abstract Adaptor3d_Curve, implementation for curves - GeomAdaptor_Curve, for edges – BrepAdaptor_Curve, and for wires – BRepAdaptor_CompCurve. The pipe algorithm (GeomFill_Pipe) accepts adapters (not Geom_Curve) to construct a surface. This provides a good flexibility for you to feed your objects.

Here is a sample code:

TopoDS_Wire aSpineWire = ...;
TopoDS_Edge aGuide1 = ..., aGuide2 = ...;
Handle(BRepAdaptor_HCompCurve) aSpineAdaptor = new BRepAdaptor_HCompCurve (aWire);
Handle(BRepAdaptor_HCurve) aGuideAdaptor1 = new BRepAdaptor_HCurve (aGuide1), aGuideAdaptor2=new BRepAdaptor_HCurve (aGuide2);
GeomFill_Pipe aPipe (aSpineAdaptor, aGuideAdaptor1, aGuideAdaptor2, aRadius);
aPipe.Perform (aTol, anIsPolynomial);

In the code above, *_H* are just handle-based equivalents, subclasses of Adaptor3d_HCurve.

Another good example is Extrema that is used to compute distances between the curve (and surface) adapters. You can feed curves, edges or wires to calculate extremum distances (including intersections).

Unfortunately, Open CASCADE API is not consistent in terms of use of adapters and often abuses hard-coded types where adapters would have been a better choice. For instance, the very
GeomFill_Pipe abuses Geom_Curve in some constructors while Adaptor3d_Curve could be used.GeomConvert_ApproxCurve which approximates a curve with B-Spline could have accepted an adapter thereby providing powerful possibilities to create a single NURBS-curve from TopoDS_Wires, for example.

In the follow-up post I'll try to show some example of how you could create your own adaptor, but hopefully this one already sheds some light on the concept and will give you some food for thoughts and experimenting.

(to be continued...)

Data model highlights – Parasolid, ACIS, Open CASCADE

2010-10-29T19:39:00.003+04:00

Working on the Parasolid importer of CAD Exchanger I had a new chance to observe specificities of another modeling kernel used to describe a B-Rep (Boundary Representation) model. This post highlights a few high-level differences between Parasolid, ACIS and Open CASCADE related to data models.

Comparing to ACIS, Parasolid seems to use a smaller set of primitives. Of course, there are typical elementary curves and surfaces (lines, circles, planes, cylinders, ...), NURBS, basic swept surfaces (revolution, extrusion), offsets. Parasolid defines geometrical object orientation right at the geometrical level by specifying a boolean flag at each curve or surface. An original surface normal is defined by cross-product of U and V derivatives, and can be confirmed or reversed by that boolean flag. ACIS defines normals by using special values of some key parameters, ignoring U and V parameterization. For instance, a sphere with a normal oriented inward would be defined in ACIS as having a negative radius. If you remember, Open CASCADE defines orientation as attached to the topology entity (face for surface, edge for curve).

Transformations in Parasolid can only be applied to component instances in assemblies. ACIS uses transformations only attached to bodies (the top-level entity which is a collection of solids). Open CASCADE can use location at any topology level, from vertex to arbitrary compound. This flexibility allows to reduce the model memory footprint – for instance, a solid box can be represented by single face with 6 different locations. The downside, however, is that you must take extra pre-cautions to not unintentionally modify shared objects, e.g. by creating copies as needed.
Unlike Open CASCADE, both ACIS and Parasolid often share underlying geometries – faces referring to the same surface are quite common in each. Open CASCADE discourages this to prevent modifications. Another benefit, which I realized recently – reduce data race risks in multi-threaded applications.

Among Parasolid geometrical types, I found just a couple of most interesting. The first one, which does not present in ACIS and Open CASCADE, is an intersection curve. An intersection curve is defined by a set of points, two surfaces being intersected and a law to define tangents and parameterization of the curve.
Another one is a rolling_ball_blend surface defined by two support surfaces, spine curve and a ball radius (see image below). Although, ACIS also has such type, the kinds of supports are often different. Whereas ACIS often uses support curves (which it calls ‘spring curves’), Parasolid most often uses surfaces. This added extra challenge to implement conversion as Open CASCADE’s GeomFill_Pipe (I described in the past) does not offer such combination.

Parasolid does not offer that broad set of procedural surfaces that ACIS does (variable_blend, net, skin, tube, law, etc). However it still has a larger set than Open CASCADE which is based on the STEP ISO010303-42 standard. Open CASCADE set is really a subset of what two other offer, except maybe support of Bezier curves and surfaces, and the fact that pcurve can have any type, not just B-Spline as two kernels require.

All 3 kernels have a concept of 3D and 2D representations for face boundaries. Parasolid has a notion of ‘fin’ or ‘half-edge’, and ACIS uses ‘coedge’ which is an entity referred by face’s loops and in its turn, refers to edge and optionally a p-curve. Interestingly, in Parasolid it can have either 3D or 2D representation but not both (though I did encounter one file in 1000+) that violated this requirement.

As far as tolerances are concerned, Parasolid, like Open CASCADE, does use local tolerances attached to the topological entities. ACIS introduced local tolerances in some intermediate versions only.

Similar to ACIS-SAT, the Parasolid-XT file format has evolved from version to version. Unlike ACIS, it is virtually human-unreadable due to use of numbers as type identifiers. Parasolid uses a concept of schemas that define entities type number, field layout, etc. To support backward compatibility, they introduced dynamic extension by embedding schema definitions into the file itself. Open CASCADE file format has never changed for last 15 years at least.

CAD Exchanger 2.0.2 Beta now available

2010-10-27T20:00:00.004+04:00

(Repost from www.cadexchanger.com)

October 26, 2010. CAD Exchanger 2.0.2 Beta is available
This version introduces Parasolid-XT importer. We decided to follow an effective approach used for ACIS-SAT by first proposing it to Beta customers and addressing their feedback. If you would like to join the Invitational Beta, drop us an email at info@cadexchanger.com. Public release should become available later this quarter or early 2011.

GUI and CLI (Command Line Interface) versions are available immediately. SDK should be available shortly.

CAD Exchanger 2.0.1 is now available!

2010-09-13T08:28:00.002+04:00

Version 2.0.1 is a maintenance release featuring improvements and bug fixes over v2.0. Consult the CHANGES file for details and visit the download page to get the release. For SDK evaluation please contact us at info@cadexchanger.com.

Feel free to share your feedback on the forum or email directly.
Thanks!

Handles and Templates

2010-08-06T19:46:00.001+04:00

Sometimes you might want to use a template class that would inherit Standard_Transient (or its subclass). As you need to pair it with a handle counterpart (which would have to inherit respective Handle_Standard_Transient subclass), you can't do this with the DEFINE_STANDARD_HANDLE macro directly. This post explains how you could do this.

ACIS and Parasolid formats (like IGES or STEP for instance) represent a file as a list of entities that have id's. To represent an ACIS or a Parasolid file in memory, the Base_FileModel class is used. It basically provides access to the file header and manages a set of entities where an entity is of course specific to each format. To ease sharing Base_FileModel it should be manipulated by handle (i.e. inherit Standard_Transient). Here is how this is done:

template class Base_FileModel : public Base_Transient
{
public:

//! Defines a type to index entities.
/*! @todo It must be signed (e.g. to address -1 in ACIS. Should it be consistent with size_t (for 64bit port)?
*/
typedef int Index_t;

//! Defines an entity type.
/*! Equals to the template parameter.*/
typedef En Entity_t;

//! Returns a number of entities.
/*! An empty model returns 0.*/
size_t NbEntities() const { return myRevEntMap.Size() - 1; }

//! Adds an entity.
/*! Returns a rank number with which \a theEntity has been added into the model. By
default, a new rank number is maximum rank number + 1.
Null entities are ignored.

This method is not thread-safe.

\sa Bind().
*/
Index_t Add (const Entity_t& theEntity)
{
Index_t aRank = myNullRank;
if (!theEntity.IsNull()) {
aRank = myEntVec.Size() + myNullRank;
Bind (aRank, theEntity);
}
return aRank;
}
...
protected:

//! Constructor.
/*! \a theNullRank defines a null rank used to designate a null entity (e.g. 0 for
Parasolid or -1 for ACIS).
*/
Base_FileModel (const FileHeader_t& theHeader, const Index_t theNullRank) :
myHeader (theHeader), myNullRank (theNullRank)
{
const Entity_t aNull;
myEntVec.SetValue (Index (theNullRank), aNull);
myRevEntMap.Bind (aNull, theNullRank);
}

...

NCollection_Vector myEntVec;
NCollection_DataMap myRevEntMap;
const Index_t myNullRank;

private:
Base_FileModel (const Base_FileModel&);
Base_FileModel& operator= (const Base_FileModel&);
};

Here is how a particular class (for ACIS) is defined:

DEFINE_STANDARD_HANDLE(ACISBase_Model,Base_Transient)

class ACISBase_Model : public Base_FileModel
{
public:

//! Constructor
/*! Creates a model with a new ACISBase_FileHeader.*/
ACISBase_Model() : Base_FileModel (
new ACISBase_FileHeader(), EntityNullRank) {}

...
};

Similarly in ACISBase_Model.cxx:

IMPLEMENT_STANDARD_HANDLE(ACISBase_Model,Base_Transient)
IMPLEMENT_STANDARD_RTTIEXT(ACISBase_Model,Base_Transient)

That's it !

Side effects of the Handle

2010-07-20T12:17:00.002+04:00

Last week-end, working on refactoring existing CAD Exchanger ACIS converter code (to maximize its reusability for the Parasolid one which is under development), I encountered an issue which might be interesting for a broader audience.

Inside the CAD Exchanger SDK, there is a function that accepts a pointer to the object (Base_Generator*) that inherits Standard_Transient (i.e. which can be manipulated by handle).

DEFINE_STANDARD_HANDLE(Base_Generator,Standard_Transient)
class Base_Generator : public Standard_Transient
{
...
};

class Base_GDriver
{
...

//! Translates an object into a result.
virtual void Paste (const Source& theSource,
Target& theTarget,
Base_Generator* theGenerator) const = 0;
};

I don’t remember the fundamental reason why the pointer was originally preferred to a const reference (i.e. const Handle(Base_Generator)&) , likely becase to avoid splitting Base_Generator.hxx into two headers – one defining the Base_Generator class and the other – Handle_Base_Generator, as Base_Generator.hxx itself included the header defining Base_GDriver. That does not matter much in this context anyway.

Inside the upper-level code which creates an instance of Base_Generator subclass (ACISGTopo_RGenerator), I decided to avoid using a handle and allocating a dynamic memory and simply created it on stack. That is, instead of:
Handle(ACISGTopo_RGenerator) aRGenerator = new ACISGTopo_RGenerator();
I simply use:
ACISGTopo_RGenerator aRGenerator;
This is fine as the object is not used outside the scope and no smart pointer is required.

However, when I started regression testing, I have encountered an access violation exception. Debugging led to a code that has been modified during the refactoring:

void ACISGGeom_BaseIntCurDriver::Paste (
const Handle(Standard_Transient)& theSource,
Handle(Standard_Transient)& theTarget,
Base_Generator* theGenerator) const

{
...

const Standard_Real aTol =
Handle(ACISGTopo_RGenerator)::DownCast (theGenerator)->Model()->Header()->ResAbs();

...
}

Anyone sees the issue now ?
That should be obvious if you have dealt with handles quite enough. Here is the explanation. During DownCast() a temporary handle object created. During its creation it increments the reference counter (which is 0 by default in aRGenerator). Upon its destruction it decrements it back to 0 and the handle’s destructor calls the object destructor thereby destroying the aRGenerator and deallocating its memory. That’s it!

I ended up changing the ACISGGeom_BaseIntCurDriver::Paste() to use static cast:
const Standard_Real aTol = static_cast(theGenerator)->Model()->Header()->ResAbs();
as this is a guaranteed cast in this particular case.

In general, the most reliable approach would be to wrap aRGenerator with a handle (instead of creating it on a stack).

So, a few closing thoughts:
1. Test, test, test !
2. Even if you understand bolts and nuts of the handle, you can still be surprised;
3. If you have to supply a pointer to your object that inherits Standard_Transient into a third-party code, make sure your always wrap it with a Handle;
4. If the Handle_ constructors that accepts a pointer to an object (e.g. Handle_Standard_Transient (const Standard_Transient*) ) were declared with ‘explicit’ keyword then the compiler would fail at DownCast() and this could be a hint to a developer to think carefully what might happen. Perhaps a candidate for a next modification of the OCC source code ?

Take care!

CAD Exchanger 2.0 is available!

2010-06-30T22:31:00.002+04:00

(Repost of the announcement)

CAD Exchanger 2.0 is available!

We are excited to announce a new release - version 2.0, which includes multiple new features, enhancements and bug fixes.

Version 2.0 features X3D support and is based on significantly redesigned and improved SDK, including its port to new OSes (Linux and MacOS), broader use of multi-threading which significantly improves performance, better support of some ACIS entities and much more. For a full list of changes, please refer to the CHANGES file.

As usual, free evaluation is available for download at http://www.cadexchanger.com/download.html

You know, we always value your feedback. Please drop us a line at info@cadexchanger.com, even if you simply like the tool.

Enjoy !
The development team

Open CASCADE and multi-threading again. B-Splines…

2010-05-02T12:42:00.000+04:00

This a small continuation of a series on parallelism and Open CASCADE started last year. This post is just about a particular class but it is fundamental enough deserving a separate mention.

Geom_BSplineCurve, Geom_BSplineSurface, Geom2d_BSplineCurve, Geom_BezierCurve, Geom_BezierSurface, Geom2d_BezierCurve. They implement B-Spline and Bezier curves and surface.

Supposedly for optimization of calculation of points and derivatives, they use a cache that stores information used in calculation of the lastest B-Spline segment. In 2008, when I was working on Extrema performance improvements, I made some experiments about this cache efficiency. I tried several different workloads – Boolean operations, curve projections, IGES and STEP imports, and several others – but cache misses were ~50%-75%. That is, in more than a half cases, the cache had to be flushed out and recalculated. This made me wonder if this technique makes sense at all, if such computation-intensive algorithms do not really take advantage of it. Of course, to claim that I had to conduct more thorough experiments which I did not have time for. So I just left that issue alone. (But if anyone has some insights I would be interested to hear.)

The issue popped up in a year (December 2009 or early January 2010) when I was preparing a public release of the ACIS converter of CAD Exchanger. Until that it was parallelized and took advantage of multi-core machines performing translation in multi-threaded mode. However on some models from time to time I was receiving spontaneous crashes which made me wonder about root-causes. As symptoms looked as data races, I launched Intel Parallel Inspector to see if it's true.

What was my surprise when I saw that the root-cause was ... Geom_BSplineCurve::D0() ! My first impression was that Inspector was probably too jealous about OCC and is plain wrong, as D0() is just calculation of a point on the curve. Moreover it's a const method. How come a data race can be between two const methods ? But looking deeper at stacks, source code and applying some brain power, I realized that. Yep! D0() first casts a const pointer to a non-const pointer and calls a non-const method:

Geom_BSplineCurve * MyCurve = (Geom_BSplineCurve *) this ;
MyCurve->ValidateCache(NewU) ;

So, what does that mean ? It means that when the same B-Spline curve is used in 2 or more threads they read/write the cache without synchronization, thereby overriding data and creating a data race. Obviously, the value returned by D0() can be totally wrong what leads to subsequent crashes in the algorithm that calls it (e.g. projection of a 3D curve on a B-Spline surface). As this situation (simultaneous use of the same surface object in different threads) is rather rare, crashes did not always happen.

I did not have time before that release to fully solve the problem, so had to simply disable parallelism in the ACIS converter. Now I'm returning to this issue and I'm going to introduce object copying before use in multiple threads (what would add some overhead but this will be a 'cold path' as such cases would be still be rare).

So if you consider use of Open CASCADE in multi threads beware of this potential issue. Make sure you have protected access (e.g. copy the objects, access synchronization, etc) or independent copies of the B-Splines.

Porting on MacOS

2010-04-22T22:47:00.002+04:00

This is probably a sort of “me too” story. There are several posts on the Open CASCADE forum explaining how different developers struggled with making it work on Mac. These posts were great sources for me to make my way. As Isaac Newton said “If I have seen further it is only by standing on the shoulders of giants”. So this post is primarily to give credit back to those experimentors and to help those who will follow up.

This entire effort has started to meet a CAD Exchanger SDK prospect who requested its version on MacOS. CAD Exchanger SDK was Windows-only and to fill this gap I first started Linux port (as Linux is officially supported by OCC, and I had Linux experience unlike Mac). “Eat an elephant – one bite at a time”. Linux port helped to port the entire build system, to solve some compilation problems (gcc is often more paranoic than Microsoft compiler), to solve some non-Windows specific problems (like crash of an application with MMGT_REENTRANT set to 1. If you are on Linux or Mac, can you try to see it happens ;-) ?)

My major starting points for Mac were the following posts:
http://www.opencascade.org/org/forum/thread_15606/
http://www.opencascade.org/org/forum/thread_14128/. So many thanks go to Emmanuel, Torsten Sadowski, pythonOCC team (jelle and Thomas Paviot), and others.

I have eventually used MacOS 10.5 (Leopard) with gcc4.0.1. My exact sequence of actions was the following:

Made sure that there is a /usr/X11 directory (I first used a machine with only /Developer/SDKs/MacOSX10.4u.sdk/usr/X11R6 and faced with issue of isysroot and other headache. Though build was almost fine, the executable won’t start and eventually I gave up)
Downloaded and unpacked OpenCASCADE_src.tgz (e.g. into /users/rlygin/dev/Dev/OCC/fix-mac32)
export CASROOT=/users/rlygin/dev/Dev/OCC/fix-mac32
# remove shipped ltmain.sh – see previous post
cp ${CASROOT}/make/ltmain.sh ${CASROOT}/make/ltmain.sh.sav
ln –s /usr/share/libtool/ltmain.sh ${CASROOT}/make/ltmain.sh
cd ${CASROOT}
aclocal
automake
autoconf
export INSTALL_DIR=${CASROOT}/install
export CPPFLAGS="-I/usr/X11/include -arch i386"
export LDFLAGS="-arch i386 -Wl,-dylib_file,/System/Library/Frameworks/OpenGL.framework/Versions/A/Libraries/libGL.dylib:/System/Library/Frameworks/OpenGL.framework/Versions/A/Libraries/libGL.dylib"
The latter option is to work-around 10.5 OpenGL bug described here and here.
For release mode:
./configure --with-xmu-include=/usr/X11R6/include --with-xmu-library=/usr/X11R6/lib --with-gl-include=/usr/X11R6/include --with-gl-library=/usr/X11R6/lib --with-dps-include=/usr/X11R6/include --with-dps-library=/usr/X11R6/lib --with-x-include=/usr/X11R6/include --with-x-libraries=/usr/X11R6/lib --with-x --enable-static=no --enable-shared=yes --enable-production=yes --without-tcl --without-tk --disable-draw --disable-wok --disable-wrappers --prefix=${INSTALL_DIR}
Though I have explicitly specified all those --with-xmu- etc options they seemed to have no effect and what matters is CPPFLAGS and LDFLAGS. Notice also that I disabled Draw, WOK and the Wrappers modules.

Watch for the output and ensure that all your intended modules are correctly configured. Then type:
make
make install

On a properly configured machine the above worked just fine and after a few hours there was a working build. However lauching the unit test framework I quickly faced with an exception on a test case related to use of Standard_Transient in multi-threaded mode. The root-cause came up quickly – race condition in Standard_Transient reference count. See Standard_Atomic.hxx:
//===================================================
// Default stub implementation, not atomic actually
//===================================================
#else

inline void Standard_Atomic_Increment (int volatile* var)
{
++(*var);
}

...

Thus, it was simply not thread-safe at all. Fortunately the fix was easy to make – just use Linux implementation (as gcc is also used on MacOS):
#elif defined(LIN) || defined(__APPLE__)

inline void Standard_Atomic_Increment (int volatile* var)
{
// C equivalent:
// ++(*var);

__asm__ __volatile__
(
"lock incl %0"
: "=m"(*var) // out
: "m" (*var) // in
);
}
...

So, hopefully the Open CASCADE team will integerate this fix as it already kindly did for all other fixes previous pioneers did for MacOS.
After the fix everything worked as expected.

I have currently only ported CAD Exchanger SDK. GUI and Command Line (CLI) remain Windows-only. So no real attempts to make OpenGL-related code work on Mac yet. Perhaps it will uncover some new problems. If anyone knows this one upfront it would be great to learn their experience …

Porting on Linux

2010-04-05T15:24:00.001+04:00

Another brief post, now about my experience to port on Linux. This may sound something trivial to Linux experts but perhaps will save a few hours of tedious work to someone who is not a guru.

I was following the Build Instructions outlined in the OCC user’s documentation to use autoconf/automake tools. My build box was RHEL4 Update 4. So I diligently downloaded the OCC source archive, ungzipped’ed it and ran ./configure with some required options (e.g. --disable-wrappers,...). Then make.

There were multiple hiccups along the way but after several hours I could get built libraries inside ./ros/adm/make/*/.libs. To my surprise they did not contain the .so suffix and so I was stuck as I could not do anything about it. I emailed to my colleagues at OCC begging for some help. They were generous enough to offer some hints, so thanks for that again Igor ;-) ! In parallel, Google gave a couple of helpful links as well:
http://lists.kde.org/?l=kdevelop&m=111840274221191&w=2
http://osdir.com/ml/gnu.libtool.bugs/2003-07/msg00005.html

Root-cause: it was a mismatch between the libtool pre-installed on the system (which was of version 1.5.6) and ltmain.sh shipped with OCC (which expected libtool 1.4.3). Linking ./ros/make/ltmain.sh to /usr/share/libtool/ltmain.sh solved the problem. ./configure and make went smoothly and now all the libraries do contain .so.

This experience made me think that this step – ignoring shipped ltmain.sh and using pre-installed one should just always be done.

Any thoughts on this ?

P.S. Looking deeply into libtool which is autodenerated by ./configure, I still can’t figure out when ${shared_ext} is being defined to .so. So if anyone has mastered all this mechanism, I’d be interested to know ...

Mixing run-times

2010-03-31T15:34:00.001+04:00

A brief post not related to Surface modeling but still hopefully useful...

Last week-end I was testing a first version of the X3D converter to be added to CAD Exchanger. X3D stands for eXtensible 3D format (ISO19975) which could be seen as a successor of VRML format. Check http://www.web3d.org for more details.

The persistent representation uses XML as a file format, and I use Open CASCADE XML formatter for that. Once the XML document has been created, it is fed into LDOM_XmlWriter (part of Open CASCADE) which dumps contents to the file. LDOM_XmlWriter accepts FILE* as a file object.

Now beings the problem. When OCC is compiled with vc7.1 (Visual Studio 2003) and the X3D converter – with vc8 (VS2005), the application crashes during output to an XML file (inside the fwrite() function). I was trying to use VS2003 for OCC binaries as some CAD Exchanger SDK users preferred that. The same problem shows up if OCC binaries are compiled with VS2005 and the X3D converter is compiled with VS2008.

The root cause of the crash is that a FILE pointer is checked against pre-defined constant pointers to file objects (including stdout, stderr, etc) inside the run-time library. And when this pointer has been created in one run-time (vc8) and is checked inside the other (vc7.1), a different code branch is executed eventually leading to null pointer access and hence crash.

Thus, interoperability between run-times is really very limited and you should do as much as you can to avoid mixing different run-times in one application. In particular, if you are using open source software (Open CASCADE and others), make sure you rebuild them with the same run-time. If you are distributing closed source, make sure you prebuild binaries for multiple run-times.

Hope this helps if you ever encounter with such an issue, or better yet - *before* you encounter ;-).

Surface modeling. Part6

2010-03-02T09:33:00.002+03:00

(continued...)

Plating
This is one of the advanced techniques of surface modeling that Open CASCADE offers. Other names for it are hole filling, or constrained filling. ACIS calls it covering.

It involves creation of a surface that meets several constraints:
- point constraints – the surface must pass through given points;
- point constraints and tangency, and (optionally) curvature – the same as above + extra Gn requirements with respect to another surface;
- curve constrains – the surface must pass through given curves;
- curve with tangency constraint – the same + extra Gn requirements.

The latter type of constraint is used to produce class A surfaces, G1 tangent to adjacent surfaces. This is important, for instance, in auto industry when designing nice-looking car bodies, to ensure correct smooth refraction of light to avoid sharp edges.

Constraints can be mixed (e.g. 3 curve constraints, 1 curve with tangency constraint, 2 point constraints).

The main algorithm to construct plate surface is GeomPlate_BuildPlateSurface. I use it in CAD Exchanger to translate vertex_blend ACIS surfaces as well as net surfaces. The former is supposed to result from vertex blending and producing a surface G1-continous to neighbours. The image below shows one:

Net surface in ACIS is defined through two sets of curves going in approximately perpendicular directions and forming a grid-like structure. So the resulting surface is supposed to cover that grid as if a roof covered roof-timbers. The image below illustrates this:

As usual, here is an excerpt from the CAD Exchanger code:

/*! The objects in \a theBoundaries must be of the type Adaptor3d_HCurveOnSurface or
GeomAdaptor_HCurve indicating type of a constraint. Otherwise an exception
Standard_TypeMismatch is thrown.

If the \a theBoundaries list is empty then Standard_ConstructionError is thrown.

If the algorithm fails returns a null surface.
*/
Handle(Geom_Surface) ACISAlgo::MakeSurface (const TColStd_ListOfTransient& theBoundaries,
const Standard_Real theTol,
const Standard_Integer theNbPnts,
const Standard_Integer theNbIter,
const Standard_Integer theMaxDeg)
{
//constants for algorithm
const Standard_Integer aNbIter = theNbIter; //number of algorithm iterations
const Standard_Integer aNbPnts = theNbPnts; //sample points per each constraint
const Standard_Integer aDeg = 3; //requested surface degree ?
const Standard_Integer aMaxDeg = theMaxDeg;
const Standard_Integer aMaxSeg = 10000;
const Standard_Real aTol3d = 1.e-04;
const Standard_Real aTol2d = 1.e-05;
const Standard_Real anAngTol = 1.e-02; //angular
const Standard_Real aCurvTol = 1.e-01; //curvature

Handle(Geom_Surface) aRes;
GeomPlate_BuildPlateSurface aPlateBuilder (aDeg, aNbPnts, aNbIter, aTol2d, aTol3d,
anAngTol, aCurvTol);

TColStd_ListIteratorOfListOfTransient anIt (theBoundaries);
if (anIt.More()) {
int i = 1;
for (; anIt.More(); anIt.Next(), i++) {
const Handle(Standard_Transient)& aCur = anIt.Value();
if (aCur.IsNull()) {
assert (0);
Standard_ConstructionError::Raise ("ACISAlgo::MakeSurface()");
} else if (aCur->IsKind (STANDARD_TYPE (Adaptor3d_HCurveOnSurface))) {
//G1 constraint
const Handle(Adaptor3d_HCurveOnSurface)& aHCOS =
Handle(Adaptor3d_HCurveOnSurface)::DownCast (aCur);
Handle (GeomPlate_CurveConstraint) aConst =
new GeomPlate_CurveConstraint (aHCOS, 1 /*GeomAbs_G1*/,
aNbPnts, aTol3d, anAngTol, aCurvTol);
aPlateBuilder.Add (aConst);
} else if (aCur->IsKind (STANDARD_TYPE (GeomAdaptor_HCurve))) {
//G0 constraint
const Handle(GeomAdaptor_HCurve)& aHC =
Handle(GeomAdaptor_HCurve)::DownCast (aCur);
Handle (GeomPlate_CurveConstraint) aConst =
new GeomPlate_CurveConstraint (aHC, 0 /*GeomAbs_G0*/, aNbPnts, aTol3d);
aPlateBuilder.Add (aConst);
} else {
Standard_TypeMismatch::Raise ("ACISAlgo::MakeSurface()");
}
}
} else {
Standard_ConstructionError::Raise ("ACISAlgo::MakeSurface()");
}

//construct
aPlateBuilder.Perform();

if (!aPlateBuilder.IsDone()) {
return aRes;
}

const Handle(GeomPlate_Surface)& aPlate = aPlateBuilder.Surface();
//approximation (see BRepFill_Filling - when no initial surface was given)
Standard_Real aDMax = aPlateBuilder.G0Error();
TColgp_SequenceOfXY aS2d;
TColgp_SequenceOfXYZ aS3d;
aPlateBuilder.Disc2dContour (4, aS2d);
aPlateBuilder.Disc3dContour (4, 0, aS3d);
Standard_Real aMax = Max (aTol3d, 10. * aDMax);
GeomPlate_PlateG0Criterion aCriterion (aS2d, aS3d, aMax);
{
//data races in AdvApp2Var used by GeomApprox_Surface, use global mutex
Standard_Mutex::Sentry aSentry (theBSMutex);
GeomPlate_MakeApprox aMakeApprox (aPlate, aCriterion, aTol3d, aMaxSeg, aMaxDeg);
aRes = aMakeApprox.Surface();
}
return aRes;
}

The code above deals with curve or curve-with-tangency constraints only but you could add point constraints in the same way.

The algorithm starts with creation of initial approximation which you can either specify or it will create a plane otherwise. I have not come across a need of pre-specifying an initial surface but perhaps that would give some hints to the algorithm in complex cases. If there is anyone with such experience, it would be interesting to hear.

To be continued...

P.S. Writing this post in a hotel on the US west coast, Hillsboro, Oregon. The nature here is the greatest I have ever seen. Always enjoying when returning to Oregon...

Surface modeling. Part5

2010-01-27T20:52:00.002+03:00

(continued...)
Time remains the most scarce resource but I feel obliged to share some new materials with you as you may expect continuation of the series. As usual, many thanks for your patience and interest !

Skinning and lofting
This is a technique to create a model (surface or shell, or solid body) using curve constraints which the surface passes through. Below is an example of a surface built using skinning:

Skinning and lofting are actually the same technique and Open CASCADE does not make a difference between them. ACIS kernel does make a little difference (in terms of types of the inputs parameters and way of constraints definition) but also stresses that these are very similar.

Here is how you would create a surface using skinning technique:
Handle(Geom_Surface) ACISAlgo::MakeSkinSurface (
const NCollection_List<Handle(Geom_Curve)>& theSections)
{
//populate section generator
GeomFill_SectionGenerator aSecGenerator;
for (NCollection_List<Handle(Geom_Curve)>::Iterator anIt (theSections); anIt.More();
anIt.Next()) {
const Handle(Geom_Curve)& aCurve = anIt.Value();
aSecGenerator.AddCurve (aCurve);
}
aSecGenerator.Perform (Precision::PConfusion());

Handle(GeomFill_Line) aLine = new GeomFill_Line (theSections.Size());

//parameters
const Standard_Integer aMinDeg = 1, aMaxDeg = BSplCLib::MaxDegree(), aNbIt = 0;
Standard_Real aTol3d = 1e-4, aTol2d = Precision::Parametric (aTol3d);

//algorithm
GeomFill_AppSurf anAlgo (aMinDeg, aMaxDeg, aTol3d, aTol2d, aNbIt);
anAlgo.Perform (aLine, aSecGenerator);

Handle(Geom_Surface) aRes;
if (!anAlgo.IsDone()) {
return aRes;
}

aRes = new Geom_BSplineSurface(anAlgo.SurfPoles(), anAlgo.SurfWeights(),
anAlgo.SurfUKnots(), anAlgo.SurfVKnots(), anAlgo.SurfUMults(), anAlgo.SurfVMults(),
anAlgo.UDegree(), anAlgo.VDegree());

...

Curves must be bounded and consistently parameterized (so that parameter growth was in one direction). Final B-Spline will be parameterized [Umin, Umax; 0., 1.], where U parametrization is calculated depending on the curves parametrization. U parameter goes along the section curves, and V parameter goes across the curves.

When working at topological level you can use the following code:

Standard_Boolean anIsSolid = Standard_False;
Standard_Boolean anIsRuled = Standard_False;

BRepOffsetAPI_ThruSections aGenerator (anIsSolid,anIsRuled);

...
//add constraints
for (...) {
aGenerator.AddWire (TopoDS::Wire (aConstraint));
}

Standard_Boolean anIsCheck = ...;
aGenerator.CheckCompatibility (anIsCheck);

aGenerator.Build();

const TopoDS_Shape& aResult = Generator.Shape();

The topological algorithm may attempt to create a closed solid if the boundary constraints are planar.

Unlike ACIS, Open CASCADE only allows to specify curve constraints but does not give a way to specify tangential ones. So you will basically rely on underlying algorithms which try to smoothen the surface being built.

To be continued...

CAD Exchanger Public Beta Update 2 is available

2010-01-10T10:11:00.004+03:00

After individual Invitational Beta for ACIS-SAT support, public Beta Update2 is finally released.

Highlighted features: ACIS-SAT import and export (geometry and colors), Command Line mode and CAD Exchanger SDK. List of all changes is here. Go to download page to get the release.

As usual, feedback is very much appreciated and welcomed. Here in the blog, or on the forum, or directly at info@cadexchanger.com.

Thanks !

screenshot of the model imported from ACIS-SAT

Surface modeling. Part4

2009-12-21T19:12:00.002+03:00

(continued...)
Constructing arbitrary sweep surfaces
GeomFill algorithms considered in the previous posts internally use Approx_SweepFunction subclasses that define particular techniques to calculate cross-sections.
You can create your own subclass to model a particular sweep surface. Approx_SweepFunction has a few pure virtual methods which your subclass must redefine. For instance, in ACIS-SAT import for CAD Exchanger I use it to generate variable-radius surfaces. In ACIS, such surfaces are defined with the help of so called support surfaces (left and right), path curve, left and right radius functions, cross-section forms (circular, elliptical, chamfer, etc). Below is an example of such surface (in dark yellow) with elliptical section; support surfaces are in green and bright yellow, and path is red.

Here is an exceprt of the method that calculates a cross section at parameter along the path:

Standard_Boolean ACISAlgo_VarBlendSweepFunction::D0 (const Standard_Real theParam,
const Standard_Real,
const Standard_Real,
TColgp_Array1OfPnt& thePoles,
TColgp_Array1OfPnt2d&,
TColStd_Array1OfReal& theWeights)
{
gp_Pnt2d aLRad, aRRad;
// left radius
aLRad = myLRad->Value(theParam);
// right radius
if (myRRad == myLRad) {
aRRad = aLRad;
} else {
aRRad = myRRad->Value(R2Param);
}

gp_Pnt aPathPnt;
gp_Vec aNormal;
myPath->D1 (theParam, aPathPnt, aNormal);

const gp_Ax2 Axis (aPathPnt, aNormal);
const gp_Pln aSecPln (Axis);
Handle(Geom_Plane) aGSecPln = new Geom_Plane(Axis);

//intersection of a section plan with support surfaces
Handle(TColGeom2d_HArray1OfCurve) aLCArr, aRCArr;
if (!::Intersect (aGSecPln, aSecPln, myLSurf, aLCArr) || !::Intersect (aGSecPln, aSecPln, myRSurf, aRCArr))
return Standard_False;

//compute a section in 2D and restore it into 3D
const Standard_Integer n = thePoles.Upper();
TColgp_Array1OfPnt2d aPArr (1, n);
if (!mySec->ComputeSection (Axis, aLCArr, aLRad, aRCArr, aRRad, aPArr, theWeights))
return Standard_False;

for (Standard_Integer i = 1; i <= n; i++) {
thePoles.SetValue (i, ElCLib::To3d (Axis, aPArr (i)));
}
return Standard_True;
}

The above redefined virtual method D0() populates poles and weights arrays of the B-Spline curve which defines a cross-section.

Here is how to construct your surface using Approx_SweepFunction subclass:
...
Handle(ACISAlgo_VarBlendSweepFunction) aSweep = new ACISAlgo_VarBlendSweepFunction (...);

Approx_SweepApproximation anApprox (aSweep);
const Standard_Real aTol = 1e-4;
anApprox.Perform (aHPath->FirstParameter(), aHPath->LastParameter(), aTol, aTol,
Precision::Parametric (aTol), 1-3,
(GeomAbs_Shape)Min (GeomAbs_C1, aHPath->Continuity()), BSplCLib::MaxDegree(), aMaxSeg);
Handle(Geom_Surface) aRes;
if (anApprox.IsDone()) {
aRes = new Geom_BSplineSurface(anApprox.SurfPoles(),
anApprox.SurfWeights(), anApprox.SurfUKnots(), anApprox.SurfVKnots(),
anApprox.SurfUMults(), anApprox.SurfVMults(),
anApprox.UDegree(), anApprox.VDegree());

I guess using the above technique you can create arbitrary sweep surfaces, e.g. like the one below:

Topological algorithms
As mentioned in the first post of this series, as a rule Open CASCADE offers algorithms both at geometrical and topological level. Until now I was mainly focused on the geometrical level (just because I myself used it :-)). Let me try to give a brief mapping with a topo one:

1. Sweep of 1 curve along the other (including pipe with constant section)
a. GeomFill_Pipe (path, profile)
b. BRepOffsetAPI_Pipe (path, profile)
2. Pipe with constant radius (tube-like):
a. GeomFill_Pipe (path, radius):
b. BRepOffsetAPI_Pipe (path, profile) where profile must be pre-created
3. Pipe with constant radius with rail curves
a. GeomFill_Pipe (path, radius, rail1, rail2)
b. Unsupported ?
4. Pipe with variable radius
a. GeomFill_Sweep (path, radius_function)
b. Unsupported ?

Note that topo algorithms can use elements of diffent dimensions for profile object. This defines a type of a result. For instance, a pipe of vertex will generate an edge, edge – face, wire – shell, face-solid, etc.

Brief note on BRepOffsetAPI_MakePipeShell. As it works with wire spines, it must be able to deal with discontinuties between the edges (when edges intersect with sharp edges). It offers 3 modes:
- intersection and rounding
- extension and intersection
- modifying trihedron mode used when sweeping a profile along the following edge in a spine.
The following picture shows these modes respectively in red, green and blue:

To be continued...

Surface modeling. Part3

2009-11-30T23:49:00.005+03:00

(continued...)

Pipe with constant radius
A particular case of a pipe with a constant section is a pipe with a constant radius. In ACIS such surfaces are called tubes.

Here is a sample screenshot:

Here is an example of creation:

GeomFill_Pipe aTube (thePath, theRadius);
aTube.Perform (aTol, Standard_False, (GeomAbs_Shape)Min (GeomAbs_C1, thePath->Continuity()), aMaxDeg, aMaxSeg);

Pipe with constant radius and two rail curves
As a convenience, the pipe algorithm allows to specify two rail curves. Rails are those which limit the cross section.
This algorithm flavor can be used to model so-called rolling ball surfaces. ACIS defines rolling-ball surfaces as if you have a ball of a constant radius that rolls along the path and always touches two limiting faces. The traces that the ball makes on those boundary faces are called spring or rail curves.

Open CASCADE algorithm accepts the radius, the path and two rail curves and creates a surface with limited circular sections. Each section is constructed by intersecting a plane at every path point and perpendicular to it with rail curves.

Here are sample screenshots of rolling ball surfaces:

On both images the pipes are shown in red and rail curves in blue. The 2nd screenshot also contains a full tube of which a fragment is constructed using 2 rail curves. This tube is a trace that a full rolling ball would make.

Important note to make is that Open CASCADE requires that rail curves follow the path parametrization. This means that the rail curves' ranges must be at least as big as the path's and be consistent between each other.

Pipe with variable radius
In addition to constant radius, you might want to create tubes (i.e. pipes with circular sections) with variable radii. For instance, like this:

Open CASCADE does not offer direct API to construct such surfaces but you can do these using lower level API it offers. For instance, here is my code excerpt:

/*! Set radius evolution function with SetEvol() before calling this method.

If \a theIsPolynomial is true tries to create polynomial B-Spline, otherwise - rational.

\sa Surface(), Error().
*/
void ACISGGeom_Pipe::Perform (const Standard_Real theTol,
const Standard_Boolean theIsPolynomial,
const GeomAbs_Shape theContinuity,
const Standard_Integer theMaxDegree,
const Standard_Integer theMaxSegment)
{
mySurface.Nullify();
myError = -1.;

if (myEvol.IsNull())
return;

//circular profile
Handle(Geom_Circle) aCirc = new Geom_Circle (gp::XOY(), 1.);
aCirc->Rotate (gp::OZ(), PI / 2.);

//code inspired by GeomFile_Pipe when using for constant radius and corrected
//trihedron orientation

//perpendicular section
Handle(GeomFill_SectionLaw) aSec = new GeomFill_EvolvedSection (aCirc, myEvol);
Handle(GeomFill_LocationLaw) aLoc = new GeomFill_CurveAndTrihedron (
new GeomFill_CorrectedFrenet);
aLoc->SetCurve (myPath);

GeomFill_Sweep Sweep (aLoc, myIsElem);
Sweep.SetTolerance (theTol);
Sweep.Build (aSec, GeomFill_Location, theContinuity, theMaxDegree, theMaxSegment);
if (Sweep.IsDone()) {
mySurface = Sweep.Surface();
myError = Sweep.ErrorOnSurface();
}
}

In this case myEval is Handle_Law_BSpFunc object constructed from 2D B-Spline which defines radius evolution:

/*! Creates an internal Law_BSpFunc object which represents an evolution function. Uses X
coordinates of the \a theEvol B-Spline curve.

\a theFirst and \a theLast are boundaries of the path curve.
*/
static Handle(Law_BSpFunc) CreateBsFunction (const Handle(Geom2d_BSplineCurve)& theEvol,
const Standard_Real theFirst,
const Standard_Real theLast)
{
//knots are recalculated from theEvol prorate to [theFirst, theLast] range
Standard_Integer i;
const Standard_Integer aNbP = theEvol->NbPoles();
TColgp_Array1OfPnt2d aPArrE (1, aNbP);
theEvol->Poles (aPArrE);
TColStd_Array1OfReal aPArr (1, aNbP);
for (i = 1; i <= aNbP; i++)
aPArr(i) = aPArrE(i).X();

const Standard_Integer aNbK = theEvol->NbKnots();
TColStd_Array1OfReal aKArrE (1, aNbK), aKArr (1, aNbK);
theEvol->Knots (aKArrE);
TColStd_Array1OfInteger aMArr (1, aNbK);
theEvol->Multiplicities (aMArr);

const Standard_Real aKF = aKArrE(1), aKL = aKArrE (aNbK);
const Standard_Real aKRatio = (theLast - theFirst) / (aKL - aKF);
for (i = 1; i <= aNbK; i++) {
aKArr(i) = theFirst + (aKArrE(i) - aKF) * aKRatio;
}

Handle(Law_BSpline) aBs;
if (theEvol->IsRational()) {
TColStd_Array1OfReal aWArrE (1, aNbP);
theEvol->Weights (aWArrE);
aBs = new Law_BSpline (aPArr, aWArrE, aKArr, aMArr, theEvol->Degree(),
theEvol->IsPeriodic());
} else {
aBs = new Law_BSpline (aPArr, aKArr, aMArr, theEvol->Degree(), theEvol->IsPeriodic());
}

Handle(Law_BSpFunc) aFunc = new Law_BSpFunc (aBs, theFirst, theLast);
return aFunc;
}

/*! Uses X coordinates of the \a theEvol B-Spline curve to set evolution function.
*/
void ACISGGeom_Pipe::SetEvol (const Handle(Geom2d_BSplineCurve)& theEvol)
{
myEvol = ::CreateBsFunction (theEvol, myPath->FirstParameter(), myPath->LastParameter());
}

Below are examples of radius function (as 2D B-Spline) and resulting surface:

Common comments
Pipe surfaces are parametrized in U along the cross section and in V along the path. Surface parametrization inherits the path range and adjusts U to a section range. For instance, tubes are parametrized from 0 to 2*PI in U.

To be continued...

Invitational Beta for ACIS-SAT support just started

2009-11-30T23:45:00.002+03:00

ACIS-SAT format support now available in CAD Exchanger and for any other Open CASCADE-based application

CAD Exchanger has been extended with support of ACIS-SAT import and export. After several months of hard work and thorough testing this new format is now available to our users.
CAD Exchanger supports ACIS from version R1.5 to the latest R20 released in 2009. The scope includes a full set of geometrical and topological objects.

For developers on Open CASCADE, the ACIS-SAT plugin can be delivered as SDK that can be directly integrated with Open CASCADE-based application using either TopoDS_Shape interface or a BRep file.

We have conducted thorough testing through the database of 1000+ models before this announcement, so you should not be annoyed by any severe bug. But there can be some corner cases which could potentially reveal some issues. So please let us know if you find anything. But if you just like the product and it works fine in our case please tell us this as well. We need your feedback !

To get immediate download access please email us at info@cadexchanger.com.

Public Beta will be made available early next year after addressing feedback from our most active users. Sign up now to get your voice heard !

Surface modeling. Part2

2009-10-26T10:10:00.002+03:00

Sweep surfaces
Sweep surfaces are constructed using a spine and a profile that moves along it.
Here is a screenshots of a typical sweep surfaces:

The sweep surface is constructed using GeomFill_Pipe. Perhaps the name pipe stems from the fact that a particular case when the profile is closed produces a pipe-like surface.

GeomFill_Pipe Pipe;
GeomFill_Pipe aPipe (aPath, aProfile, GeomFill_IsFixed);
aPipe.GenerateParticularCase(Standard_True);
aPipe.Perform(aTol, Standard_False, GeomAbs_C1, BSplCLib::MaxDegree(), 1000);
const Handle(Geom_Surface)& aSurface = aPipe.Surface();

This code is an excerpt from the CAD Exchanger, the translation driver for ACIS sum_spl_sur, which is defined as a sum of two curves.

By default, the sweep surface is created as a B-Spline, either rational or polynomial – depending on the parameter in the Perform() method. If you want to generate elementary surface (torus, cylinder, sphere, etc) when curves configuration allows, then call GenerateParticularCase() with Standard_True.

The algorithm can also return an approximation error – use ErrorOnSurf() to get it.

Sweeping is constructed dragging a profile along the spine and modifying its orientation along the latter. This behavior is controlled by a parameter of the type GeomFill_Trihedron. The following images illustrate how resulting surface is different for the same spine and profile (semi-circles):

GeomFill_IsFixed

GeomFill_IsFrenet

GeomFill_IsConstantNormal

You can experiment in DRAW using the 'sweep' command and providing various options.

Pipes
GeomFill_Pipe offers a few pre-defined construction techniques to construct a sweep surface:
- a pipe with constant section;
- a circular section pipe with constant radius;
- a circular section pipe with constant radius with two rails.

Pipes with constant section has been considered above. Here are two more examples of such pipes:

To be continued...

Surface modeling. Part1

2009-10-10T00:13:00.003+04:00

Surface modeling is a fundamental feature of any 3D geometric modeler. As you know, Open CASCADE offers a set of elementary surfaces (planar, conical, spherical, etc), Bezier and B-Spline, revolved, extruded and offset surfaces. There is also a trimmed surface which trims an underlying surface in parameter space.

Open CASCADE implements a subset of STEP (ISO standard 10303, part 42) for geometrical and topological entities, though with some minor deviations.

The surface object only contains a final geometrical representation and does not provide any information on how it was created. This differentiates it, for instance, from ACIS which uses a notion of so called procedural surfaces which may contain both a construction technique and an optional final approximation. For instance, a skin surface comes with description of a set of section curves the surface was 'skinned' through and resulting NURBS approximation. This leads to increase in number of entity types to be supported by the modeler and likely complexity of modeling algorithms that use them. (This also makes me suffer developing extra classes to represent all this variety in the CAD Exchanger translator and to translate them into Open CASCADE. I can successfully re-import all SAT files exported from Open CASCADE but not all possible SAT types yet). By the way, if there are readers who are familiar with ACIS their comments would be valuable to check how OCC capabilities compare with those of ACIS.

Open CASCADE favors different approach where knowledge of the performed modeling algorithms is stored elsewhere (e.g. in OCAF using function drivers). The B-Rep model only contains a result of an operation and thus is more compact.

Another point to make is that OCC offers algorithms both at geometry level (dealing with Geom_Surface and/or Geom_Curve objects) and topology level (TopoDS_Shape subclasses). The latter may use the former but this dual API is not always provided. Some algorithms are only available at the geometry level and some are only at topology. (If you are not certain about this distinction please make sure you re-read a series of posts earlier this year).

Let's see what modeling techniques you can use with Open CASCADE. I bet there is no point in going through description of construction techniques of elementary surfaces. Documentation and header files are just enough for that. Let's rather check what kind of advanced stuff OCC has.

Ruled surfaces
Ruled surface is constructed by connecting two curves (i.e. points along them) with lines. Particular case of a ruled surface is plane (as it can be built on two parallel lines). If you take two parallel circles then a ruled surface will be a cylinder or a cone.

Here is how it may look in general case:

Last spring, when we were in Spain and visiting Sagrada Familia in Barcelona (the central city cathedral, which is an on-going construction for several decades), there was an exhibition of Antoni Gaudi's construction techniques. Gaudi was an architect and he reused many techniques from nature. Among those there was a use of ruled surfaces – see some photos here or even read a paper 'Gaudi and CAD'.

You can create a ruled surface at geometry level as follows:
Handle(Geom_Curve) aCrv1 = ...;
Handle(Geom_Curve) aCrv2 = ...;
Handle(Geom_Surface) aSurf = GeomFill::Surface (aCrv1, aCrv2);

If you dealing at topology level you can create either a face using two edges or a shell using two wires. You need to use BRepFill:
TopoDS_Edge anEdge1 = ...;
TopoDS_Edge anEdge2 = ...;
TopoDS_Face aFace = BRepFill::Face (anEdge1, anEdge2);

TopoDS_Wire aWire1 = ...;
TopoDS_Wire aWire2 = ...;
TopoDS_Face aShell = BRepFill::Shell (aWire1, aWire2);

Here is a shell of two faces lying on ruled surfaces:

When using BRepFill::Shell(), wires must contain the same number of edges. If not you may need to re-approximate the edges. For instance you can reuse ShapeAlgo_Container::HomoWires() or create some similar algorithm, or re-approximate a wire using BRepAdaptor_CompCurve adaptor and Approx_Curve3d. The latter will produce a single B-Spline curve from a wire, which you can later use with GeomFill or create a TopoDS_Edge from of it to use BRepFill.

To be continued...

Back again

2009-10-09T21:22:00.002+04:00

Hi folks!

It took me a few weeks to get back to writing a new post, though I keep on reading most forum posts.

First, I wanted the latest post about seminar on parallel programming and Open CASCADE to stay a bit longer to let more people notice it. There were several feedbacks from the readers, all extremely positive and supportive. Many thanks again to those who replied, that was important. However, the number was still too small to justify the event so we will have to defer it for some time. There will be free webinars by Intel so those who are interested can participate online.

Many other things have been happening during this time. First, I have changed a position in Intel. My new job is engineering management of a local team that develops Threading Building Blocks and Open MP, two run-time libraries that are aimed at facilitation of creation of multi-threaded applications. Both are part of Parallel Composer, and the former is also available in Open Source. If you had been following my recent posts, I was describing my experience with TBB, which I became a fan of.

The team is quite mature and involves senior professionals, and the technical stuff is still quite of a challenge for me, so I continue ramping up. It turned out that my earlier experiments with TBB appeared to be a good upfront investment that now starts paying off. In general, throughout my career I observe that in order to successfully manage engineers you need be a good engineer ;-). You need to speak one language with people you work with.

Second, developing the ACIS-SAT translator for CAD Exchanger has also been time-consuming. The progress has been good so far and the exporter is feature complete, while the importer is mostly complete.

There were several interesting notes while working on the ACIS translator. I have adopted the Qt test framework for unit and integration testing, and was again fascinated how effective early testing can be. Indeed, the cost of a fix for a bug found during unit testing is just a small fraction of one found by your customer a few months later. I am trying to develop a discipline of having a test case for any new functionality, or even to have a test before the code is developed. An overhead that pays off in the future.

I thought what could be interesting for you, my readers. Though there are some draft notes made during last months let me try to offer you something new. I thought to share with you some techniques on surface modeling which could be done with Open CASCADE. I had not been working with it for years and don't remember many details but touched this topic now when developing translation of ACIS surfaces. So I may need some time to gather and to structure information on this topic. Answers can be slow as I will be studying some of these issues with you ;-).

So, let me start a separate series on this...

Seminar on parallel development and Open CASCADE

2009-08-24T20:45:00.001+04:00

Folks,

Today I would like to come with a question to you.

As you probably noticed, in several last posts, I was uncovering multi-threading programming issues. This subject has really caught me and applying it in Open CASCADE-based software reveals huge potential. Talking to my readers, on this blog and outside, I conclude that the issue of parallel programming and performance (regardless of Open CASCADE) is important for many developers and their employers. So, I thought to come out to you with the following idea.

What would be your thoughts on organizing some sort of technical seminar/training on parallel development ? This could be combined with training/consulting on Open CASCADE if there is a need. Regarding the former part (multi-threading) I would work with my colleagues at Intel to get support. Intel is very serious and working hard to promote this knowledge among mainstream software developers, and likely this idea will be supported if there is sufficient audience. Regarding the latter (Open CASCADE) I could check with Open CASCADE team if this will be of interest of them.

The challenge is how to find a place in the world for us to meet. Obviously, it will depend on locations of those who will respond.

So could you please think of this idea and let me know if you might be interested in such an arrangement. Certainly there will be some expenses involved (traveling and lodging) but all together we'll try to figure out how to minimize them.

Sounds too crazy? Post your comments with any ideas here or just send me an email at roman.lygin@gmail.com.

Thanks a lot in advance ! Let's make it happen !!!

const Handle & vs Handle

2009-08-07T10:02:00.002+04:00

Quick post. The addressed issue may seem quite obvious for professional C++ developers yet it's often overlooked.

Case1. When you need to downcast a handle to superclass to one to subclass bets are you are following Open CASCADE conventions:

Handle(Geom_Curve) aCurve = ...;
...
Handle(Geom_Line) aLine = Handle(Geom_Line)::DownCast (aCurve);
gp_Ax1 anAx1 = aLine->Position();
...

Case2. When you have a function returning a const Handle& you likely often write:

const Handle(MyClass)& GetMyClassInstance();

Handle(MyClass) anInstance = GetMyClassInstance();
//though you could write const Handle(MyClass)& anInstance

Both are totally valid code. But have you ever thought about what happens inside ? Remember that a Handle is not just simple type (like pointer), there is certain overhead inside. This overhead is to maintain a reference counter (increment, decrement) any time you copy a handle. If you use debugger and follow step-by-step instructions you will go through Handle_Standard_Transient::BeginScope(), EndScope(), copy constructor, assignment operator, etc.

This overhead is quite negligible when you deal with a few (hundreds ?) objects. However it may become noticeable when you are making performance-critical computations or deal with dozens of hundreds of objects. For instance, I did notice this when translating huge ACIS-SAT files with CAD Exchanger. Surprisingly BeginScope() and EndScope() appeared among top 5 hotspots.

Bad news is that such issue may often be hidden by other types, not necessarily handles themselves. The most frequent case, which Open CASCADE itself is vastly contaminated with is TopoDS_Shape. As you remember, TopoDS_Shape contains a field myTShape of the TopoDS_TShape type (subclass of Handle_Standard_Transient). So whenever you use something like:

1). TopoDS_Edge anEdge = TopoDS::Edge (aShape);
//instead of const TopoDS_Edge& anEdge = TopoDS::Edge (aShape);

or

2). const TopoDS_Shape& GetShape();

TopoDS_Shape aShape = GetShape();

//instead of const TopoDS_Shape& aShape = GetShape();

or

3). have a class returning TopoDS_Shape instead of const TopoDS_Shape& while it could have (e.g. when returning its own field)

class MyClass
{
public:
...
TopoDS_Shape Child() const { return myChild; }
//instead of const TopoDS_Shape& Child();

private:
TopoDS_Shape myChild;
};

You always assume a penalty of copy constructors and reference counters. Beware and pay attention to that !

Here are some quick recommendations on how to avoid this overhead:

a). use const Handle()& (or any other type) as return type whenever possible;
b). use const& as local variables whenever possible;
c). substitute Handle(MyClass)::DownCast() with direct cast (but only if you are certain of the type!):

Handle(Standard_Transient) aTarget;
const Handle(MyClass)& aMyClass = * static_cast (&aTarget);

We touched c) in a very first post here. I'm currently thinking to extend Handle class with such a method to cast to const Handle&. Thus, Handle could cast the same as two C++ operators dynamic_cast and static_cast.

Any thoughts on this ?

Scalability issues in CAD data exchange

2009-07-30T20:25:00.004+04:00

(This is a re-post from Intel Software Network)

Continuing to eat our own dog food (i.e. to use Intel tools) let me share some recent practical experience.

I was measuring the parallelized part of the ACIS-SAT converter of CAD Exchanger (my personal project) to investigate its scalability. (SAT is a file format of ACIS, a well known 3D modeling kernel) The way to do this was to execute the same test case on the same architecture (e.g. Core 2 Duo or Core i7) changing the number of threads. Obviously, the ideal curve is 1/n where n is a number of cores. Below is the data I collected on a few files:

It includes measurements made on Core based Xeon 5300 (Clovertown) and the Corei7-based Xeon 3500 (Nehalem). Both are 4 cores with HT (hyper-threading). As you can see, Core i7 outpaces Core (each dashed curve is below the solid one) but the nature of the curve is the same for any file – it scales well from 1 to 2 to 4 but then becomes almost a constant (except maybe the pink one which corresponds to rather small ACIS file).

So why is that ? Discussing this issue with my colleagues at Intel, the first guess was that the application consumes all the bus bandwidth trying to load data from memory. That is, though the cores are free to execute the application cannot be fed it with data. We used another experimental Intel tool (Intel Performance Tuning Utility, available for free download at http://whatif.intel.com) to check this. This did not prove to be true – the experiments showed that though there are a lot of objects in memory they are allocated quite locally and can fit into Level 2 cache and so there are no bottlenecks of working with RAM.

So what else then ? Another guess was HT and that the OS perhaps not optimally distribute the workload among the cores and that a work running on the same core (there are actually 4 physical cores) but in different threads start competing for data. So I took another machine with 2 processors (i.e. 8 physical cores) with disabled HT. The data slightly changed – running in 5 threads gave speed up over 4 cores but then again, the time remained flat when increasing number of threads from 5 to 8.

To dive deeper into what happens I launched Intel Thread Profiler which (along with VTune Performance Analyzer) is a predecessor of Parallel Amplifier but has a nice feature which is not yet available in Amplifier – timeline.

I only focused on the parallelized part (highlighted on the image below).

As we can see, 7 other threads already finished their work (dark green became light green) while one thread (in this case, thread 1) continued to work. So this was an obvious example of non-scalability – adding more threads won’t help as there was only one working !

I execute parallel processing using tbb::parallel_for which has parameters of grain size and a partitioner. They define how the work is split into chunks. To track how TBB does this I used profiling API that added some marks to the timeline indicating start and end of processing each solid and their indexes.

We can see now that this time thread 5 was given the largest solids with indexes 14 and 15. That is, default values for grainsize and portioning strategy resulted that one thread was given several complex solids in a row which caused longer time to complete. Given that processing each solid involves multiple complex algorithms, it is safe to split processing into one solid at a time (this outweighs overhead implied by TBB for splitting). Here is a new code:

//use simple partitioner and grain size of 1 to ensure individual processing
tbb::parallel_for(tbb::blocked_range(1,aNbEntities+1,1),
ApplyPostProcess(this, theMap),
tbb::simple_partitioner() /*auto_partitioner()*/);

This immediately resulted in better performance! While one thread was processing a complex solid others were given those which remained. Of course, even in this case the duration will always be defined by the longest time of one solid processing. Moreover, even with such simplified approach there are still rooms for improvements – e.g., the workload can be sorted in the order of decreasing complexity. This will ensure that the ‘heaviest’ solids will be distributed and processed first, while ‘lighter’ solids will be deferred. This will significantly reduce chances of imbalances. Of course, this recommendation assumes that sorting is substantially faster than processing itself.

So, I hope this post will make you think how your workload is really parallelized, how you can use Intel tools to see this and how you can manage and improve it.

CAD Exchanger Beta Update 1 is available

2009-07-21T15:25:00.002+04:00

The CAD Exchanger product team is pleased to announce availability of the Beta Update 1 release of a new product to speed up translation of 3D data across multiple CAD formats.

Beta Update 1 can be freely downloaded from http://www.cadexchanger.com/download.html.

It addresses Beta users' feedback and introduces a few new features:
- New display mode - triangulation. Displays underlying triangulation of surface models.
- Ability to change precision of the surface models triangulation. This parameter affects visualization quality and conversion of the surface models into mesh formats (such as STL, VRML, etc)
- VRML 2.0 (1997) export is now supported.
- BRep and STL exporters now do not export hidden models (i.e. unchecked in the Model Explorer).
- Automatic checking for updates. User will be automatically notified when new product releases become available.
- Skipping invisible (blank) entities when importing IGES files at user's discretion.

For a full list please refer to Release Notes.

CAD Exchanger currently supports import, view, and export of IGES, STEP, STL, VRML and BRep formats (more are coming).

We continue to look forward to users' feedback that will help us prioritize development activities. Please share your experience at users' forum at http://www.cadexchanger.com/forum.

Sincerely,
The CAD Exchanger Team

Developing parallel applications with Open CASCADE. Part 4

2009-07-06T16:13:00.002+04:00

( continued...)

Open CASCADE threads
Open CASCADE provides thread abstraction in the form of OSD_Thread class that encapsulates OS-specific threads. It accepts a variable of the OSD_ThreadFunction type which is essentially a pointer to a function defined as follows:

typedef Standard_Address (*OSD_ThreadFunction) (Standard_Address data);

Here is a simple example of using Open CASCADE threads:

static Standard_Mutex aMutex;

Standard_Address Test_ThreadFunction (Standard_Address /*theData*/)
{
Standard_Mutex::Sentry aSentry (aMutex);
std::cout << "Running in worker thread id:" << OSD_Thread::Current() << std::endl;
}

int main (int argc, char *argv[])
{
const int MAX_THREAD = 5;
OSD_Thread aThreadArr[MAX_THREAD];

std::cout << "Running in master thread id: " << OSD_Thread::Current() << std::endl;

OSD_ThreadFunction aFunc = Test_ThreadFunction;
int i;
for (i = 0; i < MAX_THREAD; i++) {
aThreadArr[i].SetFunction (aFunc);
}
for (i = 0; i < MAX_THREAD; i++) {
if (!aThreadArr[i].Run (NULL))
std::cerr << "Error: Cannot start thread " << i << std::endl;
}

for (i = 0; i < MAX_THREAD; i++) {
Standard_Address aRes;
if (!aThreadArr[i].Wait (aRes))
std::cerr << "Error: Cannot get result of thread " << i << std::endl;
}
return 0;
}

The code of a function accepted by OSD_Thread::SetFunction() will be executed in a separate thread. Running the above example you should see different id's for master and worker threads.

OSD_Thread::Run() instance accepts a parameter of type void* which can be a pointer to some data object or is a type cast from some compatible type (e.g. integer). The same convention applies to an output parameter of OSD_Thread::Wait().

Of course, you are not obliged to use OSD_Threads and may prefer to use other implementations (system threads, Qt, Intel Threading Building Blocks, Open MP, etc). I have become a big fan of Intel TBB and am using it in CAD Exchanger.

Synchronization objects
Currently Open CASCADE provides the only synchronization object called Standard_Mutex which corresponds to Critical Section on Windows. You should get some knowledge on this subject to effectively use synchronization in your code.

For instance, to minimize contention you should protect the minimum required section of the code with a synchronization object. Using Standard_Mutex::Sentry you may create an additional nested scope for that:

void MyClass::MyMethodThatCanRunConcurrently()
{
//thread-safe code
...
{
//code requiring serialization
Standard_Mutex::Sentry aSentry (myMutex);
MyNotConcurrentMethod();
}

//thread-safe code again
...
}

The most convenient and efficient use of Standard_Mutex is through Standard_Mutex::Sentry which implements a scoped object which acquire and releases locks on a mutex. The Sentry object locks the mutex during its construction and unlocks it during destruction. This guarantees that the mutex will be unlocked even in the case of an exception raised during execution. Otherwise this could create a deadlock – other threads continue to wait for the locked mutex while there is no one who could unlock it.

It must be noted that Standard_Mutex is currently implemented inefficiently and therefore can hardly be recommended for use as is. Its method Standard_Mutex::Lock() is uses repetitive calls to TryEnterCriticalSection() and sleep(). This may result in wasting processor resources instead of yielding them to another task. It seems that developers attempted to implement a spin lock which can be useful for very short critical sections (where it is more efficient to spin than to immediately go into wait mode). However this must have been done differently – using critical section with spin count. I had to patched Standard_Mutex to eliminate this TryEnter...() behavior.

During my earlier experiments I have implemented other objects – wait condition and semaphore – but as they did not make part of Open CASCADE, there is no point describing them here.

(to be continued...)

Developing parallel applications with Open CASCADE. Part 3

2009-06-29T20:39:00.004+04:00

( continued...)

Data races
Data races is one of the most frequent problems that pop up when transitioning from sequential to parallel programming. When you develop a sequential code you usually make totally different assumptions on how you code would execute. It may require some imagination to understand how your code may work in multi-threaded environment and to anticipate which problems may happen.

Data races may result in really unpredictable application behavior – from sometimes correct results to non-reproducible incorrect results, and to spontaneous crashes. If you observe such behavior it may likely be due to a data race in your code or in 3rd party library. To catch it you can use Intel Parallel Inspector which is able to identify different memory and thread errors. Here is how it looks when catching an error in Open CASCADE:

Open CASCADE contains quite a lot of data races prone places if used in parallel applications as is. I first mentioned about data races in OpenCASCADE when experimented with IGES translation last year (search for forum threads on that). Working on ACIS importer revealed a few more. Most frequent examples are the following:

a). return of const& to a static variable inside the function. For instance:
const gp_Dir& gp::DX()
{
static gp_Dir gp_DX(1,0,0);
return gp_DX;
}

This works perfectly fine in a single-threaded application but may create a problem in a parallel one. When two threads simultaneously call gp::DX() for the first time, there is concurrent write-access to gp_DX variable and result is unpredictable. The fix in this case is to put definition outside of the function and thus to initialize the variable during load time:

static gp_Dir gp_DX(1,0,0);
const gp_Dir& gp::DX()
{
return gp_DX;
}

b). Use of static variables defined in a file.
These cases range from forced use when a variable cannot be part of an argument list or a class member to ugly usages that I can only attribute to non-understanding of C++. Fixes for these cases were symmetrical – from using Standard_Mutex whenever it was unavoidable to creating auto variables on a stack.

The example of the first case was GeomConvert_ApproxCurve.cxx which defines a C-style function that must use data outside of it (e.g. as a member of a class that calls it). The API of this function is prescribed elsewhere and itself is specified as an argument to some class.

static Handle(Adaptor3d_HCurve) fonct = NULL;
static Standard_Real StartEndSav[2];

extern "C" void myEval3d(Standard_Integer * Dimension,
// Dimension
Standard_Real * StartEnd,
// StartEnd[2]
Standard_Real * Param,
// Parameter at which evaluation
Standard_Integer * Order,
// Derivative Request
Standard_Real * Result,
// Result[Dimension]
Standard_Integer * ErrorCode)
// Error Code
{
...
StartEndSav[0]=StartEnd[0];
StartEndSav[1]=StartEnd[1];
...
}

In this case I had to protect fonct and StartEndSav with Standard_Mutex in the caller class to prevent data race. Reading Open CASCADE 6.3.1 Release Notes, I noticed that this issue was addressed and the OCC team made deeper changes introducing a class (not a C function) what allows to handle data transfer in a way not involving synchronization. This is good and I will be able to roll back my fixes.

c). Special case of BSplCLib, BSplSLib and PLib.

This case was already discussed in the blog last December in context of speeding up Boolean Operations. Let me briefly remind you the issue. For B-Splines calculations, version 6.3.0 (and prior) uses an auxiliary array of doubles allocated on heap; it is reallocated if new requested size is greater than previously allocated or is simply reused if already allocated buffer suffices. This is done in order to avoid frequent allocation/deallocation as this creates a bottleneck but obviously is not thread-safe.

So discussing then, Andrey Betenev suggested using auto variables (allocated on stack) as there is a limitation of a maximum B-Spline degree. Digging the code I realized that though in 99+% cases this will work, there can still be cases when any maximum threshold can be exceeded. This is because the number of poles in B-Splines is unlimited (and there are curves featuring more than 8192 poles!). So I implemented an improved alternative that use auto-buffers if the requested size is less than some threshold and uses heap otherwise.

template class BSplCLib_DataBuffer
{
public:

//8K * sizeof (double) = 64K
static const size_t MAX_ARRAY_SIZE = 8192;

BSplCLib_DataBuffer (const size_t theSize) : myHeap (0), myP (myAuto)
{
Allocate(theSize);
}

BSplCLib_DataBuffer () : myHeap (0), myP (myAuto) {}

virtual ~BSplCLib_DataBuffer()
{ Deallocate(); }

void Allocate (const size_t theSize)
{
Deallocate();
if (theSize > MAX_ARRAY_SIZE)
myP = myHeap = new T [theSize];
else
myP = myAuto;
}

operator T* () const
{ return myP; }

protected:

BSplCLib_DataBuffer (const BSplCLib_DataBuffer&) : myHeap (0), myP (myAuto) {}
BSplCLib_DataBuffer& operator= (const BSplCLib_DataBuffer&) {}

void Deallocate()
{
if (myHeap) {
delete myHeap;
myHeap = myP = 0;
}
}

T myAuto [MAX_ARRAY_SIZE];
T* myHeap;
T* myP;
};

(to be continued...)

Developing parallel applications with Open CASCADE. Part 2

2009-06-23T20:38:00.003+04:00

(continued...)
By the way, you must set this environment variable (MMGT_OPT) as well as other ones that control Open CASCADE memory management, before your application starts. This is important as selection of a memory manager is done during dll's loading. This is also a very inconvenient limitation that forbids to assign a custom memory manager in run-time.

Due to extensive memory allocation and deallocation during app life-cycle, it may become a hotspot. Look for instance, at the following screenshot received on a CAD Exchanger ACIS translator.

When measuring concurrency and waits & locks (the other two analysis types offered by Amplifier) using direct OS memory manager (as Open CASCADE one could not be used as explained in a previous post), I noticed that it also causes the greatest wait time.

On one hand, this is a very good indication that the rest of the code runs pretty fast. On the other, it indicates that memory management can really become a bottleneck. Analyzing the problem deeper I switched to the mode to see direct OS functions (toggling off the button on Amplifier toolbar) and here is what I saw:

What does it show to us ? That 2 system functions – RtlpFindAndCommitPages() and ZwWaitForSingleObject() – are hotspots and stack unwinding shows that they are called from memory allocation / deallocation routines !

The first hotspot is explained by the fact that ACIS translator creates multiple tiny objects containing results of translation (on this particular test case – 22000+). This causes strong memory fragmentation which forces the system to constantly look for new memory chunks.

The second (which goes through critical section) is caused by the default mechanism of memory management on Windows. As you might know, heap allocation in Windows is done sequentially using a mutex (critical section) with spin count of ~4000, i.e. when one thread requests memory allocation and in parallel another one tries to do the same, this latter thread does not go immediately to sleep mode but 'spins for 4000 times letting the former one to complete.

All this is caused by the direct use of calloc/malloc/free, and new/delete. To overcome this issue I have tried a technique offered by Intel Threading Building Blocks 2.2 which allows to substitute all calls to C/C++ memory management with calls to tbb allocator. This is done extremely easy with including a simple statement

#include "tbb/tbbmalloc_proxy.h"

The TBB allocator runs concurrently (without locks inside) and also works in a way similar to Open CASCADE – reuses once allocated blocks without returning them to the OS. This solved both hotspots issue and gave additional speed! Check out comparison of results:

On a side note, notice that on previous images there are not only calls via Standard_MMgrRaw::Allocate() and ::Free() (which are called via Standard::Allocate() and ::Free() when MMGT_OPT=0). There are also direct calls from arrays (TColgp_Array1OfPnt2d, etc) and others (highlighted in violet). They correspond to calls of new[] operator which is not redefined in Open CASCADE classes and therefore bypass Open CASCADE memory manager. Andrey Betenev once pointed this out to me, and here are the clear evidence of this observation. So, this should lead to an action on OCC team side, if they want to fix this oversight.

So, the summary are:
- default (optimized) Open CASCADE memory manager (MMGT_OPT=1) is not applicable to the parallel apps
- raw memory manager (MMGT_OP=0) forwarding calls to OS malloc/free can lead to fragementations and bottlenecks on workloads extensively using memory;
- to overcome this you need special memory manager, for instance Intel TBB that substitutes OS memory management routines.

(to be continued...)

Performance tests of CAD Exchanger ACIS translator

2009-06-20T01:06:00.002+04:00

As I already mentioned, I have been developing an ACIS translator for CAD Exchanger designing its architecture for multi-core from the very beginning. Today I performed a series of performance tests of its Alpha version executing multiple-files (from 150Kb to 55Mb) on different hardware (2/4/8 cores). The same set of tests have been executed against another ACIS translator and I am proud to state that mine has fully outperformed it ! The lowest gain was about 15% on a smaller file and the highest gain was 10x on the biggest one (it took CAD Exchanger ACIS translator only 23 seconds while the competitor needed 230seconds to translate a model of 55Mb). Obviously the latter gain will be most noticeable for the user.

I made some video running a live test of one model to demonstrate parallelism on an Intel Core i7 workstation. Sorry for sound artifacts – I was simply using my laptop for video recording, so you may notice hard disk crunching :-(.

There are several phases in the ACIS translator – parsing a file, creating a transient file model in memory, converting it into Open CASCADE shape, and eventually shape analysis and correction. Conversion and correction which take the largest share of time are fully concurrent and scale very well in most cases. Parsing a file is obviously a single-threaded task. And a phase of creating a transient model, even though architecture allows to make it fully parallel I had to execute sequentially being a hostage of Microsoft STL bug mentioned in an earlier post. With growing number of cores this phase becomes considerable comparing to others thus making the whole translation worse scalable. Hope that Microsoft will fix it earlier than I decide to implement own string parsing ;-).

The code takes advantage of Intel Threading Building Blocks which I loved for its ease of use, excellent scalability and very low overhead (I did not notice much difference running TBB with only one thread vs simple sequential execution). There are also a couple of know-how architectural algorithms that made this concurrency possible, which I am quite proud of;-).

Development of the ACIS translator will continue and should make it into the CAD Exchanger GUI eventually. It will also be offered as a C++ software library that you could use in your Open CASCADE-based application to read ACIS-SAT files. By the way, I was impressed to find hundreds of ACIS files all over the internet which really underlines its popularity.
If you would like to evaluate it please let me know.

Thanks !

Developing parallel applications with Open CASCADE. Part 1

2009-06-09T19:50:00.002+04:00

As mentioned in an earlier post, I am now working on an ACIS importer for CAD Exchanger and am developing it to be parallel. The results are very promising so far (except STL streams parsing due to the Microsoft bug mentioned in that post, though I'm now installing VS2008SP1 to check if it has been fixed). So I decided to share my experience in this blog and hope it will be useful for other developers (questions on the forum about parallelism appear more frequently now). Also hope that Open CASCADE team will benefit from these findings.

As a quick note already made several time, let me underline that in multi-core era parallel applications will become mainstream in some mid-term and you better prepare yourself for that trend now. This can be good for your career path and these skills can be among your competitive advantages. Recently released Intel Parallel Studio eases work of developers to develop and to debug multi-threaded applications (it has become a vital part of my toolbox). There are good basic books on this subject. I am now reading "Patterns for Parallel Programming" by Timothy Mattson et al (recommended by one my skilled colleague), an analogue of famous "Design Patterns" by Erich Gamma (the must read book for any professional software developer). It helped me shape the architecture of the ACIS importer for CAD Exchanger.

Getting back to Open CASCADE, I can definitively say that it is quite usable for parallel applications but like any other software library requires precautions.

General comments.
You will get major gain if you look at your problem from a higher level, from the problem domain, and not from a particular algorithm perspective. Identify what can be done concurrently and what requires sequential execution. For instance, in my initial experiments with IGES translation (see here) I intentionally focused on parallelizing translation of components of IGES groups and this worked reasonably well. But overall gain for entire translation was very modest because it was not this part that took most part – it was Shape Healing that ate about 50%-70% of a total time, and it remained sequential. So, until you restructure your algorithms your improvements will be limited. Working on the ACIS reader I had to completely redesign traditional architecture of waterfall approach (when a model is traversed from a root entity down to a leaf) and consequent shape healing. This gave tremendous outcome. The Patterns book gives concrete recommendations that help identify ‘patterns' in your algorithms.

Handles
With 6.2.x Open CASCADE handles (hierarchy of Handle_Standard_Transient subclasses) come with thread-safe implementation for reference counting. To take advantage of that you must either define MMGT_REENTRANT system variable to non-null or call Standard::SetReentrant (Standard_True) before you start using handles across threads. This makes reference counter to rely on atomic increment/decrement (e.g. InterlockedIncrement() on Windows) instead of ++ which can be not atomic.

void Handle(Standard_Transient)::BeginScope()
{
if (entity != UndefinedHandleAddress)
{
if ( Standard::IsReentrant() )
Standard_Atomic_Increment (&entity->count);
else
entity->count++;
}
}

Memory management
By default, Open CASCADE ships with MMGT_OPT variable defined to 1. This forwards all Standard::Allocate() and ::Free() calls to the Open CASCADE memory manager (Standard_MMgrOpt) which optimizes memory allocation mitigating memory fragmentations. (Probably it deserves a separate post to describe insights of the memory manager.)

Standard_MMgrOpt is thread-safe itself and safely regulates simultaneous memory allocation/deallocation requests from several threads. However it is based on Standard_Mutex (more on it in the future) which in its current implementation introduces extreme overhead and makes this optimized memory management worthless in parallel applications (while in a single threaded environment it works just fine).

So, to overcome this deficiency you should use MMGT_OPT=0. It activates Standard_MMgrRaw that simply forward calls to malloc/free…

(to be continued...)

Intel Parallel Studio launched !

2009-05-26T20:08:00.004+04:00

Today is THE day! Intel announced availability of the Parallel Studio, the suite of software tools to ease development of parallel applications. Work on it has been my best experience at Intel so far. I do adore it !

Respected 3rd party announcements: Dr. Dobbs, SD Times

Parallel Studio home, featuring Open CASCADE team's testimonial:

"Intel® Parallel Inspector and Intel® Parallel Amplifier greatly simplified the task of finding hotspots and memory leaks. We were pleased with the 2X overall performance improvement and the elimination of several previously unidentified memory leaks."
– Vlad Romashko
Software Development Manager
OpenCascade S.A.S.

Parallelizing C++ streams

2009-05-25T09:25:00.002+04:00

This post won't be directly about Open CASCADE but it may be helpful to those who are looking forward to parallelizing their applications. My personal strong belief is that multi-threading is unavoidable for long-term success and one must be prepared to make steps into that direction (better sooner than later). Era of free MHz is over, multi-threading is the only choice to scale in the future.

So. I am now developing an ACIS translator for CAD Exchanger and am designing its architecture to employ multi-threading whenever reasonable. Keeping it efficient, streamlined and light-weight forces to think and to refactor implementation several times but it pays off.

One of the examples where I was looking to integrate multi-threading was a conversion between persistent representation of an ACIS file (barely with a set of containers of ascii strings directly read from the file) into transient representation (which is a set of C++ objects representing ACIS types with data fields and cross-references between each other). The approach is that at the first pass empty transient objects are created and at the second their data is retrieved from persistent objects and references are created using already created placeholders. This allows to process each object fully independently from the others and thus represents an excellent case for multi-threading. First I made a sequential conversion and on the file of 15Mb consisting of 110,000+ entities this mapping took ~3 seconds. This became a benchmark to compete with.

To ease parsing of persistent entities strings I use C++ streams that wrap char* buffers, and operator >> to recognize doubles, integers, characters, etc. The makes the code concise and easy to understand. To enable parallelism I am using Intel Threading Building Blocks, a software library (available under commercial and Open Source license) facilitating solving many frequent tasks met in development of multi-threaded software including parallel loops, concurrent data containers, synchronization objects and so on. It already won several software awards and gains recognition of broad developers audience world-wide. It is developed in the same team that develops Parallel Amplifier, Inspector (and now Advisor) where I currently am at Intel.

The code looked quite straightforward (sequential part is commented out):

/*! \class ApplyPaste
\brief The ApplyPaste class is used for concurrent mapping of persistent representation into transient.

This is a functor class supplied to Intel TBB tbb::parallel_for(). It
uses ACISBase_RMapper to perform conversion on a range of entities that TBB
will feed to it.
*/
class ApplyPaste {
public:

//! Creates an object.
/*! Stores \a theMapper and model entites for faster access.*/
ApplyPaste (const Handle(ACISBase_RMapper)& theMapper) : myMapper (theMapper),
myMap (theMapper->File()->Entities())
{
}

//! Performs mapping on a range of entities
/*! Uses ACISBase_RMapper::Paste() to perform mapping.
The range \a r is determined by TBB.
*/
void operator() (const tbb::blocked_range& r) const
{
const ACISBase_File::EntMap& aPEntMap = myMap;
const Handle(ACISBase_RMapper)& aMapper = myMapper;
Handle (ACISBase_ACISObject) aTarget;
for (size_t i = r.begin(); i != r.end(); ++i) {
const Handle(ACISBase_PEntity)& aSource = aPEntMap(i);
aMapper->Paste (aSource, aTarget);
}
}
private:
const ACISBase_File::EntMap& myMap;
const Handle(ACISBase_RMapper)& myMapper;
};

/*! Uses either consequential or parallel implementation.
*/
void ACISBase_RMapper::Paste()
{
boost::timer aTimer;
Standard_Integer aNbEntities = myFile->NbEntities();

//parallel
tbb::parallel_for(tbb::blocked_range(0,aNbEntities), ApplyPaste(this),
tbb::auto_partitioner());

//sequential
//const ACISBase_File::EntMap& aPEntMap = myFile->Entities();
//Handle (ACISBase_ACISObject) aTarget;
//for (Standard_Integer i = 0; i < aNbEntities; i++) {
// const Handle(ACISBase_PEntity)& aSource = aPEntMap(i);
// Paste (aSource, aTarget);
//}

Standard_Real aSecElapsed = aTimer.elapsed();
cout << "ACISBase_RMapper::Paste() execution elapsed time: " << aSecElapsed << " s" << endl;
}

How disappointed was I to get a new elapsed time of ... 17sec on my new Core 2 Duo laptop (instead of 3secs in sequential code) ! What the heck ?! Obviously it could not be attributed to overhead caused by tbb, otherwise there was no point in using it. But what then ?

I immediately launched Intel Parallel Amplifier to see what goes wrong. Here is what I saw:

Unused CPU time (i.e. when one or more cores were not working) was 33.8s i.e. at least one core did not work. Hotspot tree showed that there was some critical section (a synchronization object that regulates exclusive access to some shared resource) called from std::_Lockit::_Lockit() constructor which itself most of the times was called from std::locale::facet::_Incref() or _Decref(). Mystery at the first glance. So I rebuilt my app in debug mode and started debugger and what ? Everything became clear.

The root cause is a critical section used to protect a common locale object. operator >>() inside creates a basic_istream::sentry object on the stack. Its constructor calls (through another method) ios_base::locale() which returns a std::locale object by calling its copy constructor (see syntax below). The copy constructor calls Incref() to increment a reference counter. Incrementing reference counter is surrounded by a critical section.

locale __CLR_OR_THIS_CALL getloc() const
{ // get locale
return (*_Ploc);
}

So, all streams compete for the same locale object! Moreover, critical section is created with spin count = 0. That means if one thread tries and fails to acquire a lock (enter critical section) while another thread is using it, it immediately goes into a sleep mode. When the lock gets freed the thread gets awaken. But all this is extremely expensive and therefore it creates that very overhead ! Should spin count be a non-null then it would run much faster – the spin count determines amount of tries to acquire a lock before the thread goes to sleep. For example, memory management routines (e.g. malloc()) use spin count of 4000 or so, and this makes multi-threaded apps run effectively even concurrently allocating memory. Why not to do the same for streams ?

OK, I tried to persist and talked to colleagues around. One of them gave me a link to http://msdn.microsoft.com/en-us/library/ms235505.aspx which among the rest discusses thread-specific locale. This looked promising. But after experimenting and reading http://msdn.microsoft.com/en-us/library/ms235302(VS.80).aspx I found this of no help :-(. The matter of the fact is that only C runtime locale can be made local to threads while C++ streams always use global locale::global. Gosh ! Microsoft ! Why ?!

So this is here I am now. I will keep on searching but if you ever dealt with using STL streams in multi-threaded environments or barely heard about this please let me know. I will appreciate any reference. The option to implement an own string parser (to avoid STL streams) is currently the least preferred but eventually is not excluded.

Nonetheless, experience with TBB runs extremely positively. I have integrated it into conversion part which converts transient representation into Open CASCADE shapes. Parallel execution and using of tbb::concurrent_hash_map for storage outperforms sequential implementation and will scale well over larger number of cores. I'll keep you posted on how it's going.

Take care,
Roman

[off-topic] ¡Hola! – Back from Spain

2009-05-20T01:29:00.002+04:00

It has been a long month after my previous post on this blog. As we achieved an RTM (Release-To-Manufacturing) milestone with the Parallel Studio I decided to take some break and we spent a few days in Spain with my family. This was a first time for me to be there and I would definitively like to return. We could not see everything we hoped to – swine flu had adjusted our plans as we arrived there :-(.

In Europe, Spain is known to be affected largely enough by the developing financial crisis. Though I deem the crisis is for good overall, I am very sympathetic to people who might be affected by it. Unlike many optimists out there I believe that much worse is still ahead of us.

What was good to see is that Spain does a lot of things that are a right answer for this downturn. This started with relatively low trip prices which did not seem believable a year ago. To retain tourist traffic the consulate opens a multi-entry Shengen visa valid for 180 days. For a reasonable trip price we got an excellent 3* hotel near Barcelona, one block from the sea, which exceeded some Egyptian 5* hotels. Upon arrival we were given a full boarding though we only paid for HB, and the food was spectacular. As it's not yet a high season (and we normally try to take advantages of this) and preparing for the worse, sellers are very open to offer discounts. As an example, Port Aventura, an entertainment park was offering 50% discount giving 2 days ticket for the price of 1. My daughter was happy to enjoy this.

Consequences of a recent boom are still observed. Like many other countries, Spain fell a victim of a real estate bubble. In a main street of a tourist town where we stayed real estate agencies were met every 100m or even more frequently. More than a half did not show signs of life for all our stay. Some have just been left abandoned. Stopped constructions, even in lovely locations, even almost completed, were frequent. Sales ads on every (!) multi-apartment house along the entire beach, sometimes up to 10+ on each. Natural consequences of craziness. It's good that Spain started it earlier, this is yet to come in Russia.

Regarding sight seeing, we spent most of the days in Barcelona. Of course, (almost) all "must see" locations – The Gothic Castle, Sagrada de Familia, Gaudi buildings, Guel park, Rambla and many other things. We were impressed with St. Maria del Mar church which appeared so small from outside and that monumental inside with a big Rose above the entrance. We could not make the Picasso museum twice, so this remains at least one reason to return. We went another day to Figueres, the home town of Salvador Dali, where he established a museum in the building of a once burnt out theater. What a special man ! His will was to get buried between two lavatory pans and it was fulfilled – his grave is under two working toilets in the museum. As we were walking through the museum I could not say it was too impressive (of course, tiredness added to that) but returning back home I re-thought and concluded that you can't assess a big thing when you are near it, you have to step back to realize it better.

So overall it was a great trip! If there are Spanish readers of this blog – you live in a great country, full of glory history and you have all the rights to be proud of it !

As for me, I returned back to work and we are now full steam ahead for new challenges and projects. I try to find some time to keep on developing CAD Exchanger. There are some interesting findings in that development so I hope to post some of them here.

Take care everyone.
Roman

All-inclusive bounding box

2009-04-16T21:36:00.004+04:00

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 ;-)

CAD Exchanger Beta is available!

2009-04-06T23:37:00.003+04:00

This has been a long awaited moment - my personal project CAD Exchanger is up to being made publicly available! The first Beta is out and the official announcement is below. If anyone has to deal with CAD data translation you might want to use it as a preview or as an additional tool. Please submit your comments, bug reports, suggestions, recommendations, and what not at the user's forum (link below). Thanks!

April 6, 2009.

The CAD Exchanger product team is pleased to announce availability of the first Beta release of a new product to speed up translation of 3D models across multiple CAD file formats.

CAD Exchanger enables importing, viewing, and exporting models from and to IGES, STEP, STL and Open CASCADE BRep formats (more are coming). We hope you will enjoy streamlined interface and ease-of-use of the product.

We are looking forward to users’ feedback that will help us prioritize development activities. Please share your experience at users’ forum at www.cadexchanger.com/forum.

Download a fully free Beta version from www.cadexchanger.com/download.html and start using it today !

Sincerely,
The CAD Exchanger Team

Unnoticeable memory leaks. Part 2

2009-03-28T17:35:00.003+03:00

(Continued...)

As there are multiple objects referencing each other there is no single one to check a reference count of. So I had to choose a slightly different approach which you can reuse in your cases. I have created Standard_Transient* pointers to the objects I wanted to track counts of. Using Handles is non-applicable as assignment increases a ref count and therefore prevents destroying objects. To enforce destruction the handle objects are simply put inside the scope. Here is a code snippet:

Standard_Transient *apWS, *apModel, *apTR, *apTP, *apTW, *apFP, *apG;
{
IGESCAFControl_Reader aReader;
...
apWS = aReader.WS().Access();
apModel = (aReader.WS()->Model()).Access();
apTR = (aReader.WS()->TransferReader()).Access();
apTP = (aReader.WS()->TransferReader()->TransientProcess()).Access();
apTW = (aReader.WS()->TransferWriter()).Access();
apFP = (aReader.WS()->TransferWriter()->FinderProcess()).Access();
apG = (aReader.WS()->HGraph()).Access();
}

The objects' counters while within the scope ranged from 1 to 8 confirming they have been significantly reused inside the Data Exchange framework. When exiting the scope the cascade of objects is destroyed nullifying most references except one – of IGESData_IGESModel, the object that represents a graph of the IGES entities in memory.

This proved suspicions that memory is not fully cleaned upon reading of an IGES file. That is, once you have read an IGES file and started using 3D models contained in it, memory still contains a lot of unused information. Unnoticed memory leak.

Experimenting further I have found a root-cause which was in an extra handle to the IGES model inside the IGESToBRep_Actor class which itself always remained in the IGESControl_Controller which was supposed to reside in memory for the life cycle of the app (it's a registered in a global container). Allocated memory is freed upon next IGES file import and this repeats over and over again.

So, as a work-around I had to add the following line after the IGES file has been read.

Handle(IGESToBRep_Actor)::DownCast (aReader.WS()->TransferReader()->Actor())->SetModel (new IGESData_IGESModel);

Note that specifying a null model is impossible since IGESToBRep_Actor::SetModel() tries to access it assuming its non-null. You may want to add the above line to your code reading IGES.

Fortunately, similar checks in IGES export revealed that no memory is left orphaned. I only checked objects similar to those used in testing IGES import, not sure if there are no any tiny orphans.

Hope these findings will be useful for you and that you can check your code in critical places to make sure you do not produce memory leaks. Good luck !

(end)

P.S. I used the autoexp.dat for Microsoft Visual Studio debugger to facilitate display of the Open CASCADE handles. This was described in an earlier post.

Unnoticeable memory leaks. Part 1

2009-03-28T16:03:00.004+03:00

(I have been relatively silent for several last days to respond to comments here on the blog and on the forum. My apologies if this frustrated you. At Intel, we are approaching a release cycle of Intel Parallel Studio and this requires a good deal of efforts to synchronize among multiple teams to ensure that something important is not overlooked. In addition to other activities, this eats much of my time).

This time I'd like to touch a subject what often does not get developers' attention it probably deserves. It's about memory leaks; and not about those which you can easily detect with specialized tools (including Intel Parallel Inspector, part of the Parallel Studio). It's not even about pseudo-leaks that some novice Open CASCADE users blame it of (I hope someday to write more about CASCADE memory management) when freed memory is not returned to the system but remains under the Open CASCADE memory manager. I mean cases when memory is still occupied by some (formally) useful contents but which your application doest not track/need any longer. This may result in orphan data residing in memory and eating out megabytes.

Let me show you a couple of particular examples that could inspire you to review your code for similar cases.

I was recently debugging my app which uses OCAF. There was a document class that contains a handle to OCAF document (TDocStd_Document) and a singleton application class that contains a handle to TDocStd_Application subclass. So once I put a breakpoint into my document destructor to check a reference count of the OCAF document. I expected it to be 1 so that upon destruction of my document, the ref count is decremented to 0 calling a destructor of TDocStd_Document and freeing its memory. To my surprise there a ref count was 3.

Tracing documentation creation revealed 2 additional references – one was from the global session object that registered all open documents and the other was from the TDocStd_Owner attribute that was attached to a root label (this is done automatically by OCAF). Searching around promptly gave an answer – I forgot to call TDocStd_Application::Close() before destroying my document. Once this had been done, document reference count correctly decremented to 0 and started freeing occupied memory.

The point is that until I discovered this manually, there were no any symptoms that document contents (which can be quite memory consuming for a complex structured doc) remained orphaned. The application continued to run and exit gracefully.

Another time I intentionally tried to inspect memory deallocation when importing and exporting IGES. The Data Exchange framework in Open CASCADE is too feature-rich and its architecture involves numerous classes with references between each other. My concern was that there could be cyclic handle cross-references making objects non-destroyable (recall my first posts on Handles about this potential issue). Another suspicion was that some data are not fully cleaned upon after every translation. So I went and used the debugger to see what happens...

(to be continued...)

Distributing your software

2009-03-18T22:52:00.002+03:00

Many software developers often prefer to focus on code design and development. They find writing technical specifications, fixing bugs, composing documentation or making installers too boring for their creative minds. Yes, developing with the Open Source free CAD/CAM/CAE kernel can be fascinating, but productization is a mandatory part of any successful software product.

Let me share with you a relatively easy way how to streamline your installation of your Open CASCADE based application. I will focus on defining your redistributables and setting environment variables.

Dynamic libraries
Here is how you can check which dynamic libraries you need (on Windows):
1. Run Depends.exe which is part of MS Visual Studio installation (e.g. c:\Program Files\Microsoft Visual Studio 8\Common7\Tools\Bin\Depends.exe) and load your executable (or a toolkit). The application will build a dependency tree of dynamic libraries. Pick up those which belong to Open CASCADE (and to other toolkits you might be using).
2. Add TKOpenGl.dll as it’s not directly linked and is loaded at run-time.
3. If you use OCAF, add FWOSPlugin.dll and other dlls corresponding to your formats. For instance, if you use XDE and Xml persistence and do not add your own attributes you need XmlXCAFPlugin.dll and other libraries it depends on. Again, use Depends.exe to unwind dependencies.

Resource files
The number of resource files you will need to ship depends on which modules you use. Here are ones that can be most frequently used:
1. Data Exchange.
Include %CASROOT%\src\SHMessage\SHAPE.<>, %CASROOT%\src\XSMessage\IGES.<>, XSTEP.<> where <> is either us or fr depending on which you intend to use. <> is controlled by the CSF_LANGUAGE variable and defaults to us.
Add %CASROOT%\src\XSTEPResource\IGES, STEP. You will need to set system variables CSF_SHMessage, CSF_XSMessage, CSF_IGESDefaults, CSF_STEPDefaults to refer to directory(ies) where the files are installed.
2. OCAF
You will need a resource file named <> and a variable CSF_ <> Defaults with contents describing a format, file extensions, and identifiers (GUIDs) of storage and retrieval document drivers. XDE applications may directly use the XCAF file from the StdResource directory.
Then you will need a file named Plugin and a CSF_PluginDefaults variable. The Plugin file must contain a line to refer to FWOSPlugin.dll and other drivers if your application maintains store/retrieve operations.
If you use Xml storage format, you will need %CASROOT%\src\XmlOcafResource and the CSF_XmlOcafResource variable.

3. Textures
If you plan to use prebuilt textures you will need to ship files from %CASROOT%\src\Textures and to set the CSF_MDTVTexturesDirectory variable.

There are also fonts and units-related files but I don’t remember any use case where they might be needed. If anyone does please reply with the comments.

System variables
You will need to set the following variables:
- CSF_GraphicShr (set to TKOpenGl.dll or a full path where it is located)
- Those mentioned above (if you use respective resource files)
- Optionally MMGT_* that control memory management (e.g. MMGT_OPT=1 activates Open CASCADE memory manager while MMGT_OPT=0 – standard malloc/free).

Setting environment variables can be done via a bat file which can be created to use some single variable that is set according to the user environment, and all other variables are set relative to it. I am now using another way – setting all variables inside the application itself. This makes it more robust. The following code is executed before main():

//set environment vars to not depend on pre-set environment
OSD_Environment ("CSF_LANGUAGE", "us").Build();
OSD_Environment ("CSF_GraphicShr", "TKOpenGl.dll").Build();

const int aMaxPath = 256;
TCHAR szPath[aMaxPath];
char aPath [aMaxPath];
DWORD aRes = GetModuleFileName (NULL, szPath, aMaxPath);
QOLib_ASSERT (aRes);
char *p = aPath, *q = (char*)szPath;
while (*p++ = *q++) {
q++;
}
TCollection_AsciiString aCasRootDir (aPath);
aCasRootDir.Trunc (aCasRootDir.SearchFromEnd ("\\") - 1);
aCasRootDir.Trunc (aCasRootDir.SearchFromEnd ("\\") - 1);
OSD_Environment ("CASROOT", aCasRootDir).Build();

TCollection_AsciiString aResDir = aCasRootDir + "/resources";
OSD_Environment ("CSF_SHMessage", aResDir).Build();
OSD_Environment ("CSF_XSMessage", aResDir).Build();
...

The only limitation is that MMGT_* cannot be set this way, as they are also verified before the main() function. This does not bother me as I’m using default values, likely you won’t be affected either.

The approach above allows you to launch your executable from any location (Start menu, its working directory, etc) without a headache of prior tweaking a user’s environment.

After including required libraries and resource files, and setting environment variables, you should be ready to go. Good luck!

What is your Open CASCADE-based project about ?

2009-03-11T15:45:00.001+03:00

People on the Open CASCADE forum are focused on technical stuff asking for help in particular algorithms usage. I'm often curious what their problem domains are. I have witnessed OpenCASCADE being used in so different areas (medicine, ship building, CAM/CNC, geology and what not) and every time these looked impressive. So, where do *you* apply Open CASCADE ?

If you want to promote your project here, insert a link, an image etc just go ahead and advertise ;-). Be proud to present your work to other readers!

Eager to see your comments ...

Topology and Geometry in Open CASCADE. Part 6

2009-03-06T15:06:00.001+03:00

Continued...

Back references
As you likely noticed using OpenCASCADE or analyzing the diagram in Part1, shapes refer to their sub-shapes and not the other way round. This is understandable as the same (sub-)shape can belong to multiple parent shapes. For instance, any shared edge will belong to at least two faces.
However it is sometimes needed to trace parent shape back from a child. To do this use TopExp::MapShapesAndAncestors().

TopTools_IndexedDataMapOfShapeListOfShape anEFsMap;
TopExp::MapShapesAndAncestors (myShape, TopAbs_EDGE, TopAbs_FACE, anEFsMap);

The code above fills out a map of parent faces for each edge in myShape. If myShape is a solid box, each edge will map to 2 faces. If you explore the same box into faces and try to fill out edge's ancestors in context of each face, then obviously the map will contain a single face for each edge – that very face you are currently in.

Adaptors
Some Open CASCADE algorithms can work on objects representing a curve. However they provide an API that does not accept Geom_Curve but rather Adaptor3d_Curve. For instance, Extrema does so what enables its use in intersection, projection and other algorithms both on geometrical curves (Geom_Curve) and topological edges (TopoDS_Edge). Other examples – calculation of lengths, or surface areas. This approach is known as Adapter pattern.
GeomAdaptor3d_Curve subclasses Adaptor3d_Curve to ‘adapt' Geom_Curve, BRepAdaptor_Curve to TopoDS_Edge, BRepAdaptor_CompCurve to TopoDS_Wire. There are similar classes for 2D curves and surfaces.

So you could write the following to measure lengths of a curve and an edge:

Handle(Geom_Curve) aCurve = ...;
Standard_Real aCurveLen = GCPoints_AbscissaPoints::Length (GeomAdaptor_Curve (aCurve));

TopoDS_Edge anEdge = ...;
Standard_Real anEdgeLen = GCPoints_AbscissaPoints::Length (BRepAdaptor_Curve (anEdge));

Conclusion
So, this has been a long story about fundamental concepts of Open CASCADE. Hope you are now more familiar with them and understand what geometry and topology are. As a first step, make yourself correctly use the terms – curve or edge, surface or face, point or vertex. This will help you and people reading your questions clearly distinguish if you mean geometry or topology. Once you have started using correct definitions and keeping in mind their distinctions, part of your problems may simply go away.

That's it! Full up with this elephant ;-) ?

Topology and Geometry in Open CASCADE. Part 5

2009-02-27T13:18:00.002+03:00

Continued...

Other topology types
So far we considered vertex, edge, and face – those which have connection with geometry. The rest – wire, shell, solid, compsolid and compound – do not connect with geometry directly and are just containers for other topological entities:
- wire consists of edge(s);
- shell – of face(s);
- solid – of shell(s);
- compsolid – of solid(s) sharing common face(s);
- compound – of any arbitrary type (including compound).

A minor note on solids. A solid is expected to contain a single shell that describes its external boundary. If there are two or more shells, it's considered to be a solid with voids but Open CASCADE can be not too robust to work with such bodies. So beware.

Iteration over children
The are two ways to iterate over child subshapes.
1. Direct children can be retrieved using TopoDS_Iterator.
The following function will traverse through entire shape structure:
void TraverseShape (const TopoDS_Shape& theShape)
{
TopoDS_Iterator anIt (theShape);
for (; anIt.More(); anIt.Next()) {
const TopoDS_Shape& aChild = anIt.Value();
TraverseShape (aChild);
}
}
TopoDS_Iterator has two flags specifying whether to take into account location and orientation of a parent shape when extracting a child. If the location flag is on then any child is returned as if it were a standalone shape and placed exactly at its location in 3D space (i.e. the user would see an extracted edge right where it is displayed in the context of its parent wire). If the orientation flag is on, then returned child orientation will be a product of a parent and own child orientation (e.g. two reversed or forward will give forward, reversed and forward in any combination will give reversed).
If flags are off, then a child shape is returned with its own location and orientation as stored inside (recall diagram 2 in Part1). By default both flags are on.

2. Children of a particular subtype
If you want to retrieve all edges of your shape you can do the following:
TopExp_Explorer anExp (theShape, TopAbs_EDGE);
for (; anExp.More(); anExp.Next()) {
const TopoDS_Edge& anEdge = TopoDS::Edge (anExp.Current());
//do something with anEdge
}

TopExp_Explorer has an additional parameter that specifies which parent type you want to skip. For example, if you want to retrieve only floating edges (i.e. not belonging to any face – refer to Part3), you can do the following:
TopExp_Explorer aFloatingEdgeExp (theShape; TopAbs_EDGE, TopAbs_FACE);

More on location and orientation
As already described in the previous chapters, an individual location of a geometrically bounded entity (vertex, edge, face) defines a displacement relative to its underlying geometry. Location of any topology entity (regardless if it has geometric binding or not) also defines a displacement relative to its children. For instance, if a wire has a location consisting of a translation part along the {0, 0, 10} vector then it just means that all its edges are actually translated along the Z axis by 10 units.

The same works for orientation. Parent orientation affects its children orientation when extracting them from inside the shape. There is one important exception however – which is about edge orientation within a face. If you recall Part4 we discussed there that face material lies on the left of forward edge pcurves and on the right of the reversed edge pcurves. This reversed or forward orientation of an edge must be calculated *excluding* own face orientation. That is, if you need to use edge pcurves you should rather use:

TopExp_Explorer aFaceExp (myFace.Oriented (TopAbs_FORWARD), TopAbs_EDGE);
for (; aFaceExp.More(); aFaceExp.Next()) {
const TopoDS_Edge& anEdge = TopoDS::Edge (aFaceExp.Current());
}
This exception becomes understandable if you try to understand the details. Let's construct a face bottom-up:

Handle(Geom_Surface) aSurf = new Geom_Plane (gp::XOY());

//anti-clockwise circles if too look from surface normal
Handle(Geom_Curve) anExtC = new Geom_Circle (gp::XOY(), 10.);
Handle(Geom_Curve) anIntC = new Geom_Circle (gp::XOY(), 5.);
TopoDS_Edge anExtE = BRepBuilderAPI_MakeEdge (anExtC);
TopoDS_Edge anIntE = BRepBuilderAPI_MakeEdge (anExtC);
TopoDS_Wire anExtW = BRepBuilderAPI_MakeWire (anExtE);
TopoDS_Wire anIntW = BRepBuilderAPI_MakeWire (anIntE);
BRep_Builder aB;
TopoDS_Face aFace;
aB.MakeFace (aFace, aSurf, Precision::Confusion());
aB.Update (aFace, aSurf);
aB.Add (aFace, anExtW);
aB.Add (aFace, anIntW.Reversed()); //material should lie on the right of the inner wire

aFace has a forward orientation (default). Let's explore its edges and pcurves. Though we did not explicitly add them, recall (see Part 3) that for planes they can be computed on the fly:

void TraversePCurves (const TopoDS_Face& theFace)
{
TopExp_Explorer anExp (theFace, TopAbs_EDGE);
for (; anExp.More(); anExp.Next()) {
const TopoDS_Edge& anEdge = TopoDS::Edge (anExp.Current());
Standard_Real aF, aL;
Handle(Geom2d_Curve) aPCurve = BRep_Tool::CurveOnSurface (anEdge, theFace, aF, aL);
}
}

Returned pcurves will be as shown below (material will be on the left of red and on the right of blue).

Everything is correct. Now imagine we reverse the face and explore again:

TopoDS_Face aRFace = TopoDS::Face (aFace.Reversed());
TraversePCurves (aRFace);

What will we see ? All the edges will be extracted with opposite orientations and respectively their pcurves will mean that material is beyond an external wire and within an internal wire. This is clearly wrong, though original aRFace is perfectly correct. Recall Part4 that a face orientation just shows face logical orientation regarding its underlying surface. In our case aRFace will be just aFace with a normal {0, 0, -1}.

Thus, the only way out is to do the following:
TopExp_Explorer anExp (theFace.Oriented (TopAbs_FORWARD), TopAbs_EDGE);

This will ensure that edges will show orientation regarding surface (not face!) normal. I made exact same comment in Part 4. Open CASCADE algorithms take care of this particular case, make sure so do you.

Hope orientation is now also a well swallowed bit of an elephant we have been eating in this series. I think we are almost done with it. There are a few tiny bones to pick, and unless you are still hungry we will finish it in the last post to follow. Bon appetite ;-)

To be continued...

Topology and Geometry in Open CASCADE. Part 4

2009-02-20T23:14:00.003+03:00

Continued...

Though the next topology type after the edge considered in the previous post is a wire, let's jump to the face which is the last topology entity that binds with geometry. We'll consider a wire as well as the rest of topology types in the future posts. Frankly, I was not originally going to speak of them but several folks on the blog asked to.

Face
A face is a topology entity that describes a boundary unit of the 3D body. A face is described with its underlying surface and one or more wires. For instance a solid cylinder consists of 3 faces – bottom and top, and lateral. Each of respective underlying surfaces is infinite (Geom_Plane and Geom_CylindricalSurface), while each face bounds its surface with a wire – two of them consists of a single edge lying on Geom_Circle and the lateral face consists of 4 edges – 2 are shared with top and bottom faces, and remaining two represent a seam edge (see previous post on edges), i.e. the face contains it twice in its wire (with different orientations).

Surface
Let's briefly recall what a surface is. If you had a course of mathematical analysis in your higher school you likely remember this by heart, if not you might want to read some articles to educate yourself. First part of this one on wikipedia give simple examples of parametric surfaces.

A surface maps its 2D parametric space {U,V} into a 3D space object (though still two-dimensional). Compare it with molding when a planar steel sheet is transformed into something curved. Parametric space can be bounded or unbounded, or (un)bounded in one direction only. For instance, a plane's parametric space is unbounded, while NURBS is bounded, and a cylindrical surface is bounded in U (from 0 to 2*PI) and is unbounded in V (-infinity, + infinity).
Geom_Surface::Value() returns a 3D point (X, Y, Z) from a point in a parametric space (U, V). For instance any location on Earth is described by latitude (V) and longitude (U), but can be viewed as 3D point in the Universe (if Earth center had some origin defined).

Let's recall that an edge must have both a 3D curve and a pcurve in its face surface space. Open CASCADE requires that face boundaries (wires) represent closed contours in 3D and 2D space. Therefore a face cylinder's lateral face is described as we considered above.

Not all modeling kernels impose such restrictions. I remember a cylinder coming from Unigraphics (via STEP) which lateral face was described with 2 wires, each consisting of a circular edge. We had a few discussions with my colleagues from the Data Exchange team on how to recognize such cases and how to convert them into Open CASCADE valid wire. As a result, Shape Healing's ShapeFix_Face has been extended with FixMissingSeam().

Orientation
Face orientation shows how face normal is aligned with its surface normal. If orientation is TopAbs_FORWARD then normals match, if TopAbs_REVERSED then they are opposite to each other.
Face normal shows where body material is – it lies ‘behind' the face. In a correct solid body all face normals go ‘outward' (see below):

Material on the face is defined by orientation of its edges. The side is defined by a cross product of a surface (not face!) normal and edge derivative. Edge derivative equals its 3D curve derivative if edge is forward and is opposite, if reversed. Perhaps easier understanding can be got if to consider edge pcurves: if an edge is forward then material is on the left, if reversed, material is on the right. This may sound complicated but once you get it, it will be simpler ;-). We'll speak more of orientation in a dedicated chapter.

Tolerance
Geometric meaning of a face tolerance is a thickness of a pie surrounding a surface.

A face tolerance is used by modeling algorithms significantly more rarely than edge's or vertex' and is often retained at default level (Precision::Confusion()).
By convention, Open CASCADE requires that the following condition is respected:
Face tolerance <= Edge tolerance <= Vertex tolerance, where an Edge lies on a Face, and a Vertex – on an Edge.

Triangulation
In addition to underlying surface, a face may contains a tessellated representation (composed of triangles). It is computed, for example, when a face is displayed in shading mode. Visualization algorithms internally call BRepMesh::Mesh() which calculates and adds triangulation for every face.

Additional location
Unlike an edge or a vertex, a face has an additional location (TopLoc_Location) which is a member field of BRep_TFace. So, do not forget to take it into account when using underlying surface or triangulation. Stephane has recently pointed this out on a forum.

Creating a face bottom-up and accessing its data
Like in the case of a vertex and an edge, BRep_Builder and BRep_Tool is what you need.
BRep_Builder aBuilder;
TopoDS_Face aFace;
aBuilder.MakeFace (aFace, aSurface, Precision::Confusion());
...

TopLoc_Location aLocation;
Handle(Geom_Surface) aSurf = BRep_Tool::Surface (aFace, aLocation);
gp_Pnt aPnt = aSurf->Value (aU, aV).Transformed (aLocation.Transformation());
//or to transform a surface at once
//Handle(Geom_Surface) aSurf = BRep_Tool::Surface (aFace);
//gp_Pnt aPnt = aSurf->Value (aU, aV);

Handle(Poly_Triangulation) aTri = BRep_Tool::Triangulation (aFace, aLocation);
aPnt = aTri->Nodes.Value (i).Transformed (aLocation.Transformation());

Hope this was not too boring ;-). Just bookmark it and get back when you need it!

To be continued...

Topology and Geometry in Open CASCADE. Part 3

2009-02-12T23:08:00.003+03:00

Continued...

OK, let's continue to eat our elephant bit by bit. The next bit is edge. Hope you won't get difficulties with it.

Edge
Edge is a topological entity that corresponds to 1D object – a curve. It may designate a face boundary (e.g. one of the twelve edges of a box) or just a ‘floating' edge not belonging to a face (imagine an initial contour before constructing a prism or a sweep). Face edges can be shared by two (or more) faces (e.g. in a stamp model they represent connection lines between faces) or can only belong to one face (in a stamp model these are boundary edges). I'm sure you saw all of these types – in default viewer, in wireframe mode, they are displayed in red, yellow and green respectively.

Edge contains several geometric representations (refer to the diagram in Part1):
- Curve C(t) in 3D space, encoded as Geom_Curve. This is considered as a primary representation;
- Curve(s) P(t) in parametric 2D space of a surface underlying each face the edge belongs to. These are often called pcurves and are encoded as Geom2d_Curve;
- Polygonal representation as an array of points in 3D, encoded as Poly_Polygon3D;
- Polygonal representation as an array of indexes in array of points of face triangulation, encoded as Poly_PlygonOnTriangulation.

The latter two are tessellation analogues of exact representations with the help of former two.

These representations can be retrieved using already mentioned BRep_Tool, for instance:

Standard_Real aFirst, aLast, aPFirst, aPLast;
Handle(Geom_Curve) aCurve3d = BRep_Tool::Curve (anEdge, aFirst, aLast);
Handle(Geom2d_Curve) aPCurve = BRep_Tool::CurveOnSurface (anEdge, aFace, aPFirst, aPLast);

The edge must have pcurves on all surfaces, the only exception is planes where pcurves can be computed on the fly.

The edge curves must be coherent, i.e. go in one direction. Thus, a point on the edge can be computed using any representation - as C(t), t from [first, last]; S1 (P1x (u), P1y(u)), u from [first1, last1], where Pi – pcurve in parametric space of surface Si

Edge flags

Edge has two special flags:
- "same range" (BRep_Tool::SameRange()), which is true when first = first_i and last = last_i, i.e. all geometric representations are within the same range;
- "same parameter" (BRep_Tool::SameParameter()), which is true when C(t) = S1(P1x(t), P1y(t)), i.e. any point along the edge corresponds to the same parameter on any of its curves.

Many algorithms assume that they are both set, therefore it is recommended that you ensure that these conditions are respected and flags are set.

Tolerance
Edge's tolerance is a maximum deviation between its 3D curve and any other representation. Thus, its geometric meaning is a radius of a pipe that goes along its 3D curve and encompass curves restored from all representations.

Special edge types
There are two kinds of edges that are distinct from others. These are:
- seam edge – one which is shared by the same face twice (i.e. has 2 pcurves on the same surface)
- degenerated edge – one which lies on a surface singularity that corresponds to a single point in 3D space.
The sphere contains both of these types. Seam-edge lies on pcurves corresponding to surface U iso-lines with parameters 0 and 2*PI. Degenerated edges lies on North and South poles and correspond to V iso-lines with parameters –PI/2 and PI/2.

Other examples - torus, cylinder, and cone. Torus has two seam-edges – corresponding to its parametric space boundaries; cylinder has a seam-edge. Degenerated edge represents on a cone apex.

To check if the edge is either seam or degenerated, use BRep_Tool::IsClosed(), and BRep_Tool::Degenerated().

Edge orientation
Forward edge orientation means that its logical direction matches direction of its curve(s). Reversed orientation means that logical direction is opposite to curve's direction. Therefore, seam-edge always has 2 orientations within a face – one reversed and one forward.

To be continued...

P.S. As usual, many thanks to those who voted and sent comments. Is this series helpful ?

Topology and Geometry in Open CASCADE. Part 2

2009-02-09T11:44:00.003+03:00

Continued...

Vertex
Vertex has a primary geometric representation which is a point in 3D space encoded as gp_Pnt. It may have other representations but they are virtually never used in practice.

Another important attribute of a vertex is its tolerance which indicates possible inaccuracy of its placement. Geometrical meaning of the vertex tolerance T is a sphere with a radius T centered in vertex’s point. This sphere must encompass curves ends of all edges connected at that point.

Tolerances
Let me elaborate a little bit on tolerances.

Unlike some other geometric libraries which have some global precision (e.g. as 1/1000th of the model bounding box dimension), Open CASCADE treats tolerances as local properties. As indicated in the diagram in Part1, tolerance is a field of any vertex, edge, or face instance. This approach helps to describe the model with higher accuracy in general. Look at the picture below:

Individual tolerances allow to specify local inaccuracies while leaving the rest of the model well defined. If you have to build your shape bottom up, the best approach is to specify the smallest valid tolerance. By default, it is Precision::Confusion() which is 1e-07.

In general some modeling algorithms are quite sensitive to tolerances, especially if they have to work with a single value to be specified by the user. For instance, importing a model from another 3D geometric kernel (via IGES or STEP formats, or directly from native format of other kernels or CAD systems), involves a global precision specified in a file header. The importer tries to be robust regardless of that value, no matter how coarse it is (e.g. it could that big so that some tiny faces are fully encompassed by its boundaries what would even violate the standard).

Another example is Sewing (stitching topologically disconnected faces into a shell). Gaps between faces can be quite different across the model. Specifying too small tolerance would leave too many disconnected faces, specifying too big upfront would connect too distant faces (maybe even implied too be disconnected by user intent, like tiny holes).

Coming back to vertices, let me mention about their orientation field. It does not have a direct geometric meaning, but by convention vertex with TopAbs_FORWARD orientation must match an edge’s end corresponding to the smaller parameter of its curve. Respectively a vertex with TopAbs_REVERSED – to the curve’s end with greater parameter. For instance, if you have an edge lying on a circular arc of radius 1 on plane Z=0 starting at point (1, 0, 0) and moving anti-clockwise (if to look in the direction opposite to Z axis) then its forward vertex will have a point (1, 0, 0) and reversed one – (0, 1, 0):

Building a vertex bottom-up
BRep_Builder is the tool that actually performs low-level operations.

gp_Pnt aPoint (100., 200., 300.);
BRep_Builder aBuilder;
TopoDS_Vertex aVertex;
aBuilder.MakeVertex (aVertex, aPoint, Precision::Confusion());
aVertex.Orientation (TopAbs_REVERSED);

There is a convenience class BRepBuilderAPI_MakeVertex which eventually uses BRep_Builder inside. So, if you have to construct topology bottom up make sure you are familiar with BRep_Builder.

Accessing vertex info
BRep_Tool is the tool that provides access to geometry of the topological entities. Most its methods are static.

Standard_Real aTolerance = BRep_Tool::Tolerance (aVertex);
gp_Pnt aPoint = BRep_Tool::Pnt (aVertex);

To be continued...

Topology and Geometry in Open CASCADE. Part 1

2009-02-04T23:36:00.003+03:00

Let us consider these fundamental concepts of Open CASCADE. From time to time questions about them pop up on the forum, so I hope this post will be useful for many readers. Understanding these concepts is important if you have to work with most modeling algorithms and especially if you want to develop you own. You might also want to re-read various chapters from the Modeling Data User's Guide to refresh you memory.

Abstract topology
Open CASCADE topology is designed with reference to the STEP standard ISO-10303-42. Perhaps reading some its concepts would be helpful (I myself did this once in 1997).

The structure is an oriented one-way graph, where parents refer to their children, and there are no back references. Abstract structure is implemented as C++ classes from the TopoDS package. Here is an inheritance diagram taken from the Doxygen-generated documentation.

TopoDS_Shape is manipulated by value and contains 3 fields – location, orientation and a myTShape handle (of the TopoDS_TShape type) – see the diagram below (this and other contain only most important fields):

myTShape and Location are used to share data between various shapes and thus save huge amounts of memory. For example, an edge belonging to two faces has equal Locations and myTShape fields but different Orientations (Forward in context of one face and Reversed in one of the other).

Connection with Geometry
Now let's consider how this abstract topology structure is connected with geometry.

This is done by inheriting abstract topology classes from the TopoDS package by those implementing a boundary representation model (from the BRep package). Only 3 types of topological objects have geometric representations – vertex, edge, and face (see the diagram below).

Let's consider them more closely.

To be continued...

How do you measure your progress ? Part 3

2009-01-29T10:21:00.003+03:00

(continued)

Performance considerations
Using progress indicator obviously adds certain overhead as calculating current position and redrawing a widget eats some CPU time. So, be careful to not abuse an indicator by updating it after every tiny operation. Instead you might prefer to request its update after some chunks of operations (e.g. after every 10th).

int aNbOps = ...;
int aThreshold = 10;
int aNbChunks = aNbOps / aThreshold;

anIndicator->SetRange (0, aNbChunks);
for (i = 1; i <= aNbOps; i++) {
if (i % aThreshold)
anIndicator->Increment();
}

Inserting your indicator into Open CASCADE algorithms
Once you have implemented your subclass, you can pass it to OCC algorithms. As I said above, at the moment, Open CASCADE currently supports progress indicators in IGES, STEP and BRep readers and writers.
Here are examples of how you can provide your indicators into IGES and BRep readers.

IGESCAFControl_Reader aReader;
Handle(Message_ProgressIndicator) anIndicator = ...;

//to make progress indicator work more smoothly divide the transfer into
//two steps: loading (30%) and mapping (70%), including shape healing
anIndicator->NewScope (30, (Standard_CString)qApp->translate ("Exchanger", "Loading file").toAscii());
Standard_Boolean aRes = (aReader.ReadFile (theFileName.ToCString()) == IFSelect_RetDone);
anIndicator->EndScope ();
if (aRes) {
//setting progress into the reader object to track every entity
//(using TransientProcess() is possible only after ReadFile())
aReader.WS()->MapReader()->SetProgress (anIndicator);
anIndicator->NewScope (70, (Standard_CString)qApp->translate ("Exchanger", "Translating file").toAscii());
aRes = aReader.Transfer (theDoc);
anIndicator->EndScope ();
//work-around to decremenet reference counter inside TransientProcess
aReader.WS()->MapReader()->SetProgress (NULL);
}

Importing native BRep file is more straightforward:
Standard_Boolean aResult = BRepTools::Read (aShape, theFileName.ToCString(), aBuilder, anIndicator);

Multi-threading issues
In its current implementation Message_ProgressIndicator is exclusively tailored for use within a single thread. This stems from its implementation concept based on a stack of nested sub-ranges – every time you signal a progress (e.g. with Increment() or EndScope()) it applies to the current open sub-range. This makes it unusable for multi-threaded environment where concurrent threads can perform their own chunks of tasks and report progress. I first encountered this working on parallelizing IGES import.

Upon part 1 publication, Andrey from OCC was very kind to let me know that they are prototyping multi-threaded version of the progress indicator. So chances are it can appear in near releases. Anyway, as long as you use the indicator in a single thread even within a multi-threaded environment (e.g. if your OCC-based algorithms run in a separate worker thread) you are safe to go.

So, go and plan your goal, set your range, make your next step and report how closer you are now ;-).

How do you measure your progress ? Part 2

2009-01-28T23:06:00.003+03:00

(continued)

GUI coupling
You will want to subclass Message_ProgressIndicator to couple with your favorite GUI toolkit you are using to develop your application. An alternative choice is to provide simple text output (e.g. for debugging purposes). Either way, you will have to redefine Show() and UserBreak() methods.

In my QOLib (Qt/Open CASCADE Library) I used Qt's QProgressDialog widget to visualize a progress bar and a cancel button. You might want to use your own QWidget consisting of QProgressBar, QLabel and optionally QButton.

Here are some code snippets from QLib:

class QOBase_ProgressIndicator : public Message_ProgressIndicator
{
public:
//! Creates an object.
Standard_EXPORT QOBase_ProgressIndicator (QWidget* theParent,
int theMinVal = 0, int theMaxVal = 100, Qt::WindowFlags theFlags = 0);

//! Deletes the object.
Standard_EXPORT virtual ~QOBase_ProgressIndicator ();

//! Updates presentation of the object.
Standard_EXPORT virtual Standard_Boolean Show (const Standard_Boolean theForce);

//! Returns True if the user has signaled to cancel the process.
Standard_EXPORT virtual Standard_Boolean UserBreak();

protected:

QProgressDialog* myProgress;

public:
DEFINE_STANDARD_RTTI(QOBase_ProgressIndicator)
};

/*! Creates a widget using specified paramters to initialize QProgressIndicator.
\a theMin and \a theMax are also used to set the range for \a this progress
indicator.
*/
QOBase_ProgressIndicator::QOBase_ProgressIndicator (QWidget* theParent,
int theMinVal, int theMaxVal,
Qt::WindowFlags theFlags)
{
QOLib_ASSERT (theMinVal < theMaxVal);
myProgress = new QProgressDialog (theParent, theFlags);
myProgress->setWindowModality (Qt::WindowModal);
myProgress->setMinimum (theMinVal);
myProgress->setMaximum (theMaxVal);
myProgress->setMinimumDuration (500); //the dialog will pop up if operation takes >500ms

SetScale (theMinVal, theMaxVal, 1); //synch up ranges between Qt and Open CASCADE
}

/*! Destroys the associated progress dialog.*/
QOBase_ProgressIndicator::~QOBase_ProgressIndicator ()
{
if (myProgress) {
delete myProgress;
myProgress = 0;
}
}

/*! Updates visual presentation according to currently achieved progress.
The text label is updated according to the name of a current step.

Always returns TRUE to signal that the presentation has been updated.
*/
Standard_Boolean QOBase_ProgressIndicator::Show (const Standard_Boolean theForce)
{
Handle(TCollection_HAsciiString) aName = GetScope(1).GetName(); //current step
if (!aName.IsNull())
myProgress->setLabelText (aName->ToCString());

Standard_Real aPc = GetPosition(); //always within [0,1]
int aVal = myProgress->minimum() + aPc *
(myProgress->maximum() - myProgress->minimum());
myProgress->setValue (aVal);
QApplication::processEvents(); //to let redraw and keep GUI responsive

return Standard_True;
}

/*! Returns True if the user has clicked the Cancel button in QProgressDialog.
*/
Standard_Boolean QOBase_ProgressIndicator::UserBreak()
{
return myProgress->wasCanceled();
}

Open CASCADE ships with a Tcl/Tk-based implementation (see class Draw_ProgressIndicator). Unfortunately, version 6.3.0 has (unintentionally) eliminated the XProgress Draw command that you could use to activate it and use inside the Draw session. I reported this to the folks at OCC, so hopefully they will restore it in upcoming releases. If you are impatient you could simply port it from previous versions.

(To be continued...)

How do you measure your progress ? Part 1

2009-01-27T23:51:00.002+03:00

It's important to set measurable goals in your life and to periodically check how you advance. Your application should also communicate its status in execution of a long operation, otherwise your users may decide the application hung up and to kill it.

Open CASCADE offers a mean to help you to signal that your app is still alive. It's Message_ProgressIndicator, a class manipulated by handle that you can pass to some algorithms. Currently it is supported by IGES and STEP translators, as well as by BRep loader (starting from version 6.3). Well, not much but still is a good start. OCC team might want to extend its use into some CPU-hungry algorithms (e.g. Boolean operations or others).

Nonetheless, you might want to use it even in your own algorithms thanks to its rich capabilities.
Let's consider them more closely.

Message_ProgressIndicator extends a simple concept of a progress indicator as a container of integer [min, max] range and a current value.

First nice thing is that Message_ProgressIndicator offers a range of double (not int) range and a custom step.

Handle(MyProgressIndicator) anIndicator = new MyProgressIndicator;
Standard_Real aStartAngle = 0.5 * PI;
Standard_Real anEndAngle = 1.5 * PI;
Standard_Real aDelta = PI / 6.;
anIndicator->SetRange (aStartAngle, anEndAngle);
anIndicator->SetStep (aDelta);

for (Standard_Real aCurrentAngle = aStartAngle; aCurrentAngle <= aStartAngle; aCurrentAngle += aDelta, anIndicator->Increment()) {
...
}

To get a current value on the global range use Message_ProgressIndicator::GetPosition() which returns a value in the range [0, 1].

Next cool thing is that the indicator supports nested regions. That is extremely valuable if your operation is a subpart of a larger operation it may have no idea of. Imagine that your algorithm of building custom visual presentation (AIS_InteractiveObject subclass) can be an ending step of both your complex modeling algorithm and of simple restoring a model from a file.

An operation can allocate a sub-range for its sub-operations so that they report progress within their sub-ranges. The progress indicator will take care to map local value into a global range.

void MyLongOperation ()
{
Handle(Message_ProgressIndicator) anIndicator = new MyIndicator;
anIndicator->SetRange (0, 100); //100% complete

anIndicator->NewScope (60., "The longest suboperation"); //first sub operation takes 60%
MyLongSubOperation1 (anIndicator);
anIndicator->EndScope ();

anIndicator->NewScope (30.); // 30%
MyLongSubOperation2 (anIndicator);
anIndicator->EndScope ();

anIndicator->NewScope (10.); // 10%
MyLongSubOperation3 (anIndicator);
anIndicator->EndScope ();

}

void MyLongSubOperation1 (const Handle(Message_ProgressIndicator)& theIndicator)
{
Standard_Integer aNbSteps = ...; //small chunks of work
theIndicator->SetRange (0, aNbSteps);
for (int i = 1; i <= aNbSteps; i++, theIndicator->Increment()) {
...
}

}

In the above code the entire global range has been split into 3 non-equal chunks proportionate to estimated duration of each MyLongSubOperation...(), and each is executed in its own subrange. Thus SetRange() in MyLongSubOperation1() affects its allocated subrange.

Third, sub-ranges can have their own names what can be used by displaying widgets to reflect a current phase. The name can be specified with SetName() or directly in NewScope().

Indicator can also be used to signal a user's action to break the operation. Redefine and use UserBreak() virtual method.

There are other nice features like support of infinite regions or Message_ProgressSentry class, which is a convenient wrapper and especially useful for cases when an indicator can be a null handle. Check how the latter is used in IGESToBRep_CurveAndSurface.cxx for example.

Designing your own indicator
Message_ProgressIndicator is an abstract class, so you must subclass it and redefine two pure virtual methods – Show() and UserBreak(). They define how progress indicator must be displayed and whether the user signaled that operation needs to be canceled. Let me show you an example of that in the next part.

To be continued...

The King is dead. Long live the King !

2009-01-14T22:33:00.002+03:00

This post will be about Qt. If you are the fan of Trolltech's products or the company itself as much as I was, you will likely be astonished if you have not been yet. Today, Jan 14, the company announced they would license Qt under LGPL. Everywhere including Windows. Read the announcement here.

Qt Software (new name of Trolltech, much lacking its previous brightness, imho) management states this was a logical move after multiple years of practicing a dual model (GPL & commercial) and that it will boost further Qt proliferation. I'm shocked and excited at the same time, and this seems to be a common reaction based among the comments flooding the announcement.

My first shout the second I heard this from a colleague was "they went crazy, this will suck up their revenue". (If you are not familiar with GPL and LGPL, let me describe it in a couple of words. GPL forces you to disclose your source code, while LGPL – not, if you are using it correctly. That's why Trolls were successful in their dual model – their commercial customers preferred to buy expensive licenses, while Open Source community was supportive of GPL. I touched licensing issues in one of my previous posts).

I immediately jumped to their web-site, watched the video and read the FAQ, and then went to their blog where their VP announced it. While I was typing their url in Firefox, I kept on thinking "how will they earn their money now, home come ?". A guess popped up very quickly – Nokia (I hope you know that Nokia acquired Trolltech last year). With such a Sugar Daddy behind you, you can afford such things. Yep, that seems to be it – the video confirmed that (citation). So, is revenue no longer a concern ? Quite possibly, and Nokia rather puts a stake on Qt's farther penetration. The company intends to reinforce Open Source community's contribution by simplifying some contribution processes and introducing new web tools. Let's see if that works.

More gloomy thoughts on this. Perhaps this all makes sense for Nokia, I don't know. I am still puzzled with a business sense for it to have acquired Trolltech for amazing $153M. Neither the business strategy, nor the price did not sound reasonable for me. Have anyone clearly understood the logic supporting this deal ? I'd be interested to hear your comments. If you read Trolltech's financial statements for 2 last years (after they went public on Oslo stock exchange in 2006), you might have noticed they never reported positive net income for the period of being a public company. Why buy such a company if you can't convert it into a cash generator ? What also concerns me is lack of understanding of a long-term strategy of Nokia with respect to Qt and the company. If they give up an idea of earning money with it, what can be the next step ? Can it be that they say, OK, Qt is now fully free (as in beer and in speech), you, the Community, go and maintain it ? Here are the better procedures and tools for that. And we, at Nokia, will assign brilliant Troll developers to internal projects. Possible ? Or, after a few years when Qt is everywhere, they could say, well, that loose license model we announced in 2009 undermines our revenue too much and we have to revisit it, we are now back to the old model (GPL & commercial). Free drug trick. I hope Nokia is not (that) evil, and it has a plan. Maybe I'm too paranoid but when such sound moves happen I try to understand where a real point is. I don't see it now :-(. If you do please share, that would be really interesting.

Now back to the ground. What does today's announcement mean for us ? If you are a small or a mid-size company then I suggest that you consider transition to the LGPL licensed edition (at least I would do this). This can save you several thousands or dozens of thousands dollars a year. To stay compliant you must dynamically link with the LGPL'ed Qt library and must not strip your binaries or otherwise prevent reverse-engineering.

I myself also hope to benefit from this Troll's decision. Currently I am resurrecting own previously developed toolkit – QOLib – Qt/Open CASCADE Library – I used to develop some tools about 6 years ago with Qt3. With the LGPL'ed edition there are no more concerns that previously forced me to cautiously package the toolkit in order not to breach the former license. In this sense, I cannot but welcome today's decision. No more viral threat, Qt the Great remains.

The King is dead. Long live the King !

P.S. Typing this post using a laptop while sitting in my car at a service station waiting to change oil in the car (previous one did not let the engine start at -15C). Will upload when back home.

Call for action. Building CAD/CAM/CAE development resource index

2009-01-10T16:06:00.002+03:00

After I have started this blog there were a few inquiries from people asking to share resources that would help novices to better understand the CAD/CAM/CAE (CAx) world. I shared what I had (well, some links got broken over time), and thought this could be of a broader interest, virtually for anyone in the development community.

Can we all together try this out and build some useful list ? Let's think how to make and to maintain it manageable. For instance, is there any ready-to-use rating mechanism that visitors could use to rate the usefulness of every resource ? Please advise if you know such.

Anyway, let's start with something simple and see how it goes.

As a first step, I suggest a simple one-level classification. Let's first focus on CAx.

- Theory (books, papers, articles, courses on mathematical apparatus and models)
- Software (geometric kernels, libraries, components, etc)
- Developers communities (forums, blogs, wiki's etc dedicated to CAx development)
- Informational resources (portals, newsletters, etc)
- Models (2D or 3D models in neutral or proprietary formats that can be freely used)

Provide your links using comments to this post. Include category, brief description and advantages of the resource (up to 50 words). The goal is not to have it exhausted but to contain most useful links. So, if there are resources that outshine others, we will not hesitate to remove some.

If you have any ideas how to make this most useful, please speak up.

So, let's try...

Extreme fight with Extrema. Part 3

2008-12-29T18:02:00.004+03:00

(continued)

However this did not fully solve the problem of caching results. As I mentioned earlier, B-Splines are split into C2 intervals which are processed individually. For example, on one B-Spline there were 20 C2 intervals, so caching only worked within each of them but every time a new subrange of the another edge's range was called, all data were recalculated. So, I extended caching capabilities to support lists of caches and every time a new subrange of the 1st edge's range is used, points along subranges of the 2nd edge's range are retrieved from the cache. After this modification, D0() is called only 475K times, which is 570 times less comparing with initial baseline (273.2M). CPU time reduced by 2+x. Yes, I did it !

* New targets *
So, what remains ? Looking at new hotspots below, you can see that Extrema_ECCOfExtCC::Perform() remained among top 3.

What's inside ? Looking at its top 3 hotspots (1st and 2nd are shown below, and the 3rd is similar to the 2nd) are connected with access to the array of doubles TbDist2 (containing square distances between sample points along two curves).

I suspect these are due to data latency, e.g. cache misses, i.e. when referenced data are not available in processor cache and they are loaded from RAM, which is time consuming. When some data are loaded from memory, some adjacent memory is also loaded by the processor (it assumes that you may need some of it and does this in advance). With TbDist2 this is not quite the case – because for each element [i, j] eight neighbors are checked ([i-1,j-1], [i-1,j]…[i+1,j+1]). Data for most of them are not adjacent in memory and therefore there are likely many misses here. And due to millions of calls (which as you correctly guess did not change after above modifications) result in a hotspot. I am not sure if there is anything that can be done with this, and I will probably have to talk to my Intel colleagues to check what can be done in a case like this. Perhaps the only possible solution lies upstream in reducing a number of subranges edges are split into. Today, after brief emails with the OCC team, I have no clues if/how this can be done. So, this will be up to them to continue in that direction.

Two other hot-spots – PLib::EvalPolynomial(), BSplCLib::CacheD1() – are connected with calling first derivative on B-Spline curve. Geom_BSplineCurve::D1() is called when finding a root of function of minimizing a distance between two curves. BSplCLib::Bohm() is called 2.4M times and PLib::EvalPolynomial() – 30M times. I did not find the way to cache calculations (if you see such, please let me know) and probably the solution is also upstream.

* Next steps *
So, this where I am now, and frankly I am about to pause here ;-). I sent modifications to OCC for validation on the regression database (keep fingers crossed ;-)). If they are OK, I'm going to make similar modifications for 2D case to ensure consistency and perhaps some other polishing in Extrema for easier future maintenance.

Of course, there is a possibility to try multi-threading on BOPs but I am not yet up to this, as this will require deeper understanding of the algorithms and its concurrency possibilities. We'll see…

Meanwhile I'll try to post fixes on the SourceForge if anyone would like to try them. As usual, any feedback will be appreciated, especially if you witness performance improvements or degradation.

(end)

Please rate this post using the voting buttons below.

P.S.
After the fist article I received a few more test cases, and even more, a set of modifications in BOP on performance improvements. They have been made by one of OCC customer, registered here as Solar Angel. Per his estimations speed up in Cut (as common part seems not affected) was from a few minutes to a matter of seconds. Cool! I was excited to get these fixes and get in touch with the guy again after several years !

Extreme fight with Extrema. Part 2

2008-12-29T17:16:00.004+03:00

(continued)

*sqrt()*
The first one of such was sqrt(), which was among top 5 hotspots. As it is a system function, I did not notice it until pressed a button on the Amplifier toolbar (the matter of fact is that by default Amplifier attributes system functions time to its callers).

After unwinding its stacks I found the reason. Extrema used gp_Pnt::Distance() (or sometimes gp_Vec::Magnitude()) everywhere both to compute exact distances and to find out if one point is closer than another. Well, this had a price for such an abuse – 6.5% of total CPU time. Without sacrificing any correctness, distances can be replaced with square distances. This is a hint for you – try to use SquareDistance() or SquareModulus() wherever possible instead of their countparts invoking sqrt(), if you have multiple calculations. So after made modifications, I managed to save about 5-6% (I did not eliminate all the calls).

*IsCacheValid()*
Another finer improvement related to Geom_BSplineCurve. As we already noticed and will see more precisely below, calculations of points along B-Spline curves were intensively performed. This involves Geom_BSplineCurve::IsCacheValid() (to check if a local cache can be used for faster computations). Its time was 6.25%, and looking at the source and assembly code helped to understand why:

Reason – division (the fdiv instruction) by spinlenghtcache to normalize an original range into [0, 1). Actually it could be easily avoided and I simplified the code also eliminating multiple branching to increase readability (and possibly performance, as branching is expensive). Compare:

This gave about 60% time reduction of this function. Well, floating point operations are expensive, and even if subtraction is not as expensive as division, it still takes time.

*Calculations of B-Spline curve points*
Unwinding the stacks of the top hotspot PLib::NoDerivativeEvalPolynomial() helped locate the place where it was called from – Geom_BSplineCurve::D0() – which in its turn was called from Extrema (remember above mentioned tons of calls from inside ?). I put a counter and measured that number of calls was 272,3 millions ! Wow !

As nothing in the method itself promised any improvements, I had to made modifications upstream. In Extrema.

*Extrema*

Until now Extrema architecture regarding curve-curve case was very inflexible. It always redid all computations flushing out results of any previous call. On the other hand, point-surface and curve-surface has some caching, so I wonder why developers missed it for this case.

Anyway, I extended the API to be able to first set every curve and/or its ranges and later perform calculations. To take advantage of that, I also had to modify IntTools_BeanBeanIntersector::ComputeUsingExtrema() to set curve for theRange2 (specified as its argument) only once. This was a first step and reduced number of calls to Geom_BSplineCurve::D0() / PLib:: PLib::NoDerivativeEvalPolynomial() to 8.6M.

(To be continued)

Extreme fight with Extrema. Part 1

2008-12-29T13:59:00.003+03:00

Those who regularly follow my blog likely remember that after recent speed up of Boolean Operations (see Why are Boolean Operations so slooo...ooow?) there remained a test case from Pawel K that almost was not affected. So I accepted a challenge and spent more time on this. Many thanks to Pawel for providing these models. Though they appeared to be very peculiar (such as tiny ellipse arcs and huge B-Splines of 300+ poles and 40+ knots) they allowed to detect a problem with wider impact.

Bottom line first: achieved speed up is 2.3x (from 113s to 49s). Not bad, but not quite a breakthrough because elapsed time is still in order of dozens of seconds. There are some (not obvious) further directions for optimization but they will likely be even more time-consuming, so I am not yet ready to commit to that (moreover as I already spent half of my vacations ;-)).
But what is more important is that made modifications open a door to speed up other OCC algorithms, as modified was the core component – Extrema. Today's story is about changes in it…

So, as usual, I used Intel Parallel Amplifier (by the way, we just RTM'ed, Released to Manufacturing, the version for public beta which should be available in January) to understand hotspots.

They were totally different than in the cases I dealt with in my previous experiment and it promptly became obvious they related to edge-to-edge intersections (see stack on the right).

Looking at IntTools_BeanBeanIntersector::ComputeUsingExtrema() it became understandable what was happening.

Each pair of edges which is a candidate for intersection (e.g. if their bounding boxes intersect) is analyzed. Each edge is split into certain number of ranges (e.g. ellipse – into 40) and then these ranges are analyzed with the other edge's ranges. And though inside ComputeUsingExtrema() the 2nd range does not change, the Extrema object (used to calculate the smallest distance) is created from scratch and initialized with it every time. Diving further with the debugger into Extrema, I found out that B-Splines are split into C2 intervals (which on Pawel's model were about 20!). Along each curve interval, a few sample points (32 by default) are taken. Distances are measured on the fly and candidates are further passed to math_Function* for precise calculations. Inside it the number of sample points is sometimes magically increased by 2x (just for more reliable sampling, ah ?) So, tons and tons of calculations without any attempt to reuse what already been calculated some time before.

The main idea for optimization was obvious – cache and reuse. This would require some change in Extrema API (as it did not support that) which I eventually did. It is currently limited to 3D curves only, similar improvements for other cases are deferred until OCC folks (who I sent the fixes today to) can confirm there are no regressions.

But before proceeding to API redesign, I decided to make finer improvements to make sure tiny bottlenecks do not go away from radar due to larger-scale improvements.

(To be continued).

Sexy background

2008-12-21T21:54:00.006+03:00

If you want to add a special touch to your application, here are a couple of hints on ‘personalizing’ your 3D view.

*Adding an image as background*
Use V3d_View::SetBackgroundImage() that accepts a filename to gif, bmp or xwd image and a placement option (center, stretched or tiled) defined by the Aspect_FillMethod enumeration. Calling its with Aspect_FM_NONE erases the image.
Here’s an original image and its use with the Aspect_FM_STRETCH option:

You may want to extend pre-built options, and for instance add an image to a bottom-right corner to add your company logo.

* Gradient background *
This is a frequently used background style in CAD applications. Open CASCADE does not offer a direct API to set it, but it can be implemented. The following is an excerpt from my extension of DRAWEXE:

static void UpdateGradientBackground (const Handle(Visual3d_Layer)& theLayer,
const Quantity_Color& theTopColor,
const Quantity_Color& theBottomColor)
{
int aWidth = ..., aHeight = ...; //e.g. QWidget::width() and height() for Qt-based apps
theLayer->Clear(); //make sure we draw on a clean layer
theLayer->Begin();
theLayer->SetViewport (aWeight, aHeight);
//now draw a polygon using top and bottom colors
//remember that default boundary is [-1,1;-1,1] and origin is in the left bottom corner

//check position for the middle color - if transition should be non-uniform then
//additional points should be inserted and techiques changes - 2 polygons instead of 1
theLayer->BeginPolygon();
theLayer->SetColor (theTopColor);
theLayer->AddVertex (-1,1);
theLayer->AddVertex (1,1);

theLayer->SetColor (theBottomColor);
theLayer->AddVertex (1,-1);
theLayer->AddVertex (-1,-1);
theLayer->ClosePrimitive();
theLayer->End();
}

static int VSetBgColor (Draw_Interpretor& di, Standard_Integer argc, const char** argv)
{
Handle(V3d_View) V3dView = ViewerTest::CurrentView();
if ( V3dView.IsNull() ) return 1;

static Handle(Visual3d_Layer) aLayer;

if (argc == 4) {
if (!aLayer.IsNull()) {
//switch to a single color mode
aLayer->Destroy(); //explicit destruction is required as destructor
// will not be called (one reference remains in Visual3d_ViewManager)
aLayer.Nullify();
}
V3dView->SetBackgroundColor (Quantity_Color (atof(argv[1]), atof(argv[2]), atof(argv[3]), Quantity_TOC_RGB));
} else if (argc == 7) {
Quantity_Color aTopColor (atof(argv[1]), atof(argv[2]), atof(argv[3]), Quantity_TOC_RGB);
Quantity_Color aBottomColor (atof(argv[4]), atof(argv[5]), atof(argv[6]), Quantity_TOC_RGB);
if (aLayer.IsNull()) {
Standard_Boolean aSizeDependant = Standard_True; //each window to have particular mapped layer?
aLayer = new Visual3d_Layer (V3dView->Viewer()->Viewer(),
Aspect_TOL_UNDERLAY, aSizeDependant);
}
UpdateGradientBackground(aLayer, aTopColor, aBottomColor);
} else {
di << "Usage : " << argv[0] << " {color(R G B) | top_color(R G B) bottom_color(R G B)} \n";
return 1;
}

return 0;
}

Here’s an example view:

Please rate this post using the voting buttons below.

License to kill. License to use

2008-12-15T14:01:00.002+03:00

Famous James Bond 007 had a license to kill; the "00" designation in his code number meant he had a sanction to apply a deadly force. In order to use any software you also need a license. Let me repeat, *any* software, even one which you can download free of charge with a couple of mouse clicks.

When accepting a license you become bounded by a legal agreement that the software is available under. Tell me honestly, how many of you and how often do you read the license agreement shown during install screen that makes you select a radio-button "Yes, I accept this license" before clicking Next? I bet very few, and I’m not a role model either ;-).

The fact that you can freely download some software does not imply you can use it and distribute your software based on it at your own wish. The most famous example is GPL'ed software (General Public License) which is known to be 'viral', i.e. making your own software GPL'ed. This at least applies to GPL version 2; version 3 comes with some more sophisticated terms which I did not fully study yet.

So, what about Open CASCADE license ? Among most important aspects, I'd underline that it's quite permissive and allows you to use OCC in your project (open or closed source, free of charge or for a fee), that can be distributed under your own proprietary license. Like most other Open Source licenses it requires that you include a copy of the license into your distribution. All modifications to Open CASCADE software you might make must be made available in source code, under the same license to anyone.

The summary on the site says it is "LGPL-like". I must confess this was my own suggested wording which we put with the web team, when I worked at Open CASCADE. We put that note to contrast it with GPL. It was based on my then knowledge of the subject. Working at Intel, where licensing issues are explained as part of mandatory trainings I now view this is not exactly the case. LGPL is still quite viral (though much less than GPL) and is not too welcomed in commercial applications. The OCC Public license has quite different focuses.

I believe the OCC license is somewhat weird and should better be changed. There are several existing widely recognized and adopted Open Source licenses. Any time the company comes out with its own 'open source' or 'public' license, it creates a headache for potential users and company's lawyers to read it and to understand implied rights and obligations. For average people (even native English speakers), juridical vocabulary is Greek. Take the Tax Code of your country, open it and start reading on an arbitrary page. I bet you will have to re-read each paragraph several times before you get an idea of what it is about, not saying a word about tiny details where, as we know, the evil is. So, if you really want to give your software into the Open Source world, you better choose something existing.

In this regard, Intel's move in 2005 was very symbolic to discontinue its own (and, by the way, recognized and approved) Open Source license. Motivation ? Exactly that, stop license proliferation and ease Intel’s software adoption. Look what other successful people or companies do – learn and do the same ;-).

So, my modest suggestion to the Open CASCADE company is to consider favoring some well recognized Open Source license and to migrate to it. This will ease OCC adoption and will benefit all parties.

We can continue discussion in comments. So feel free to throw in your ideas !

Why are Boolean Operations so slooo...ooow ? Part 3

2008-12-06T17:28:00.005+03:00

(continued)

For my experiments I used my own patched version of Open CASCADE 6.3.0 that accumulated all the modifications for prototyping multi-threading I mentioned earlier on the forum. One set of the modifications in it are thread-safe versions of BSplSlib, BSplCLib and PLib. Original 6.3.0 uses static array which are re-used by further calls to ::D0(), D1(), etc what is obviously not thread-safe (or even non-reentrant), so a few months back I changed them to use local variables which would be allocated/destroyed upon every relevant *Lib function call. This was just fine for IGES import scenarios but working on BOPs I noticed that my code revealed performance regressions to 6.3.0. See the image below:

So it was obvious that constant allocations/destructions were not an option. I checked how many times reallocation (or actually allocation) was used on a BOP test case, and it was 11.7 millions; allocated buffers were from 2 to 264 doubles long. Well, I had to return back the previous approach (i.e re-allocation in the case when new requested buffer exceeded previously allocated one). But how to ensure re-enterability ? The answer was quite obvious – TLS, or Thread-Local Storage. That is, each thread has its own buffer, and it's only used by that thread. So, I wrote a class (let’s tentatively name it TLSManager) that contains a map (hash-table) of {Standard_ThreadId, set of buffers}, and returns a requested buffer depending on a thread id from which a buffer was requested.

Another obvious problem poped up – TLSManger must be thread-safe but using Standard_Mutex to protect it would be an overkill. There is a solution to this typical problem, which is a read-write-lock, i.e. an object that allows multiple concurrent read-accesses to a shared resource (in our case a map with buffer sets) and exclusive write-access (when a new set of buffers is created for a new thread). Well, I went and re-invented a wheel, and added a class OSD_ReadWriteLock. Doing this (like when adding other thread classes in OSD a while ago) I once again thought that OCC should rather bring in Boost (www.boost.org) than re-designing own wheels. Salome does use Boost, so OCC can obviously too. For instance, Boost also offers a template for TLS - http://www.boost.org/doc/libs/1_37_0/doc/html/thread/thread_local_storage.html.

Once the RWL class has been written, I created a simple test case to check it and used Intel Parallel Inspector for that. Inspector allows to identify memory errors (leaks, uninitialized memory use, etc) and thread errors (data races, deadlocks, etc). Thread checker is one of a kind (there are now other software as far as I know) but its overhead is substantial.

Well, this session with Inspector that was something! It reported data races, as if my RWL were simultaneously read and wrote into the same memory (object member).

I spent several hours and felt like a full dumb looking at my one page code trying to root-cause the errors and beating my head over the keyboard and anything else around. Crazy Friday evening at home! When I gave up, I recompiled my unit test to use Qt’s QReadWriteLock, and what ? Same data races!

That made me doubt even further; I wrote down all behavior scenarios on a paper sheet and reaffirmed that there cannot be any data races, everything was protected. It’s just plain crazy false positive (i.e. a report on a problem that actually does not exist)! I know that Inspector has false positives issues but I could not imagine it would beat me that much. So, I am looking forward to talking to my Intel colleagues about that. (Make a note for you, when you download Inspector and notice the same problem, you might want to recall my case – perhaps it will be some unfixed false positive ;-)).

OK, now being confident in my RWL and I went and tried TLSManger with RWL in BSplSLib. And ? The regression has gone ! This small overhead for RWL use (instead of former shared static buffers) became actually unnoticeable. Excellent!

With all those modifications, overall speed up vs 6.3.0 was about 4x on Open CASCADE test case. I tried a simpler model sent by forum participants, and it revealed 20x speed up. Very small cases running at a fraction of a second did not reveal substantial speed up. Thus, in general we can roughly project speed up in 3x-10x range in average.

There is still something to do, e.g. to design TLSManager in CDL and migrate PLib and BSplCLib to it. I will do this as time permits, hopefully sooner while my memory is fresh.

And, by the way, if you want to try out your models with a new version, please feel free to send me the models via email or a download link. Those who eager to get the fixes, just let me know ;-)

Looking back, I think that time spent on it was worth it. I do hope that these findings will inspire the OCC team to dig further and to find further rooms for improvements, beyond BOP. I hope that my colleagues at Intel will appreciate 14 bug reports and enhancement requests I compiled during these days, and that by a commercial release the tools will be even better than they are today. I was able to learn something new in depths of OCC Modeling algorithms, and this was good. Folks from the Community will benefit via future OCC releases that would hopefully include my modifications.

I will continue to prepare OCC test cases for app testing, and if there is anything interesting, I will share with you.

Let me add a few more words on performance. Being at Intel I now view it a bit differently than when working at a software development company. Guys, times are changing (or already changed if you want). Free lunch, when your app would run faster just with every new released processor, is over. Megahertz era is over. To make your application run faster you must make it multi-threaded and scalable. Performance is not just that your app runs faster. Higher performance means more features. Look at spell checker in MS Word – it checks as your type your document. It’s just because it’s fast enough and because it runs in a parallel thread.
If you want to stay competitive in the market, you must parallel. No other way. It’s challenging but fortunately there are tools to help with that. And I am happy that somehow I relate to them. Go and try Intel tools (www.intel.com/go/parallel).

Endorsement ? Well, may be. Sincere ? Absolutely ! (I practice what I preach ;-) )

Good luck !
(end)

P.S. Please rate this article using the voting buttons below.

Why are Boolean Operations so slooo...ooow ? Part 2

2008-12-06T17:19:00.006+03:00

(continued)

So, I dove into the code and found out that the constructors were plain initializers of internal fields (e.g. double, integer, pointer). All three constructors look similar. Unwinding stacks revealed the root-cause – objects were created using new[] operator (e.g. ptr = (void*) (new IntPolyh_Triangle [N]) ) which was called on *huge* amount of copies. Look at this:

Each IntPolyh_MaillagaAffinage constructor creates arrays of 10 000 points, 20 000 triangles, and 30 000 edges for each face. Are they all really used ? With the debugger I stepped all the steps where these arrays are filled in, and what I did find ? Very often they are filled in with less than 100 elements. A few dozens effectively used while allocating for dozens of thousands ?! Unbelievable !
Two additional observations:
1. initialized elements in the array have never been read and have always been rewritten.
2. effective number of elements can be easily calculated upfront (e.g. n * m)

So, I looked into all IntPolyh classes to ensure that this is a common usage model, so that I could easily fix this with a deferred initialization with a particular number of elements. As usually, life is not that simple as it sometimes seems. Some classes (e.g. IntPolyh_ArrayOfEdges) implied that a number of effective uses can grow over time, and this feature was really used during mesh refinement. Moreover I found that many classes implement the same pattern of an array – where there is a number of allocated elements and number of effectively used. However we already saw above how ineffectively that strategy could be used :-(.

IntPolyh contains 7 classes IntPolyh_Array* that implement this pattern and are implemented as code duplication.

So, I went and created a single generic class IntPolyh_DynamicArray which would allocate memory with Standard::Allocate() (in order to not call new[] and constructors) and could grow over time if previously allocated memory was not enough. All 7 classes became instances of this template what significantly reduces a size of code to maintain.

Next, I made deferred initialization of these arrays when the number of elements to fill them in with is known (e.g. IntPolyh_MaillageAffinage::FillArrayOfPnt()).

There are other possible easy improvements to be made such as inlining all relevant methods of _Point, _Edge, etc. I did not do this right now and leave this up to the Open CASCADE team.

After these modifications time attributed to TKGeomAlgo.dll (measured with Amplifier) decreased as much as 5x-18x (from 2 to 7.28sec vs original 36.07s) !!! Overall speed up was about 3.5x (see screenshot below).

So, this was a relatively ‘low hanging fruit’ to tear off. And it gave such impressive results. I believe there are more than what can be done to improve, and I encourage OCC folks to do more, up to and including multi-threading. I don’t know BOP internals but I would check if running face-face intersection in parallel threads is feasible.

However, this was not the end of my own research.

(to be continued)

Why are Boolean Operations so slooo...ooow ? Part 1

2008-12-06T15:47:00.008+03:00

Open CASCADE Boolean Operations (BOPs) have frequently been claimed to be slow. Have anyone tried to find out why ?

As you probably remember, I recently mentioned in another post that at Intel we have decided to integrate Open CASCADE into our application testing database. So I took on a challenge to create a few test cases to regularly check Intel Parallel Amplifier and Inspector (part of new Intel Parallel Studio).

In addition to my recent test cases with IGES import which has been prototyped to run in multi-threading mode, this time I have proceeded to Boolean Operations (BRepAlgoAPI). I requested a few models on the forum but replies were surprisingly not numerous :-(. Anyway, I am thankful to Evgeny L, Prasad G, Pawel K, as well as to Igor F for their examples.

The bottom line. On relatively complex models, overall achieved speed up was from 4x (100+ faces in a model) to 20x (several dozens faces). Examples of reduced CPU time – from 80secs to 20s, from 30s to 1.4s. (Disclaimer: once this article has been drafted during last week-end, I experimented with another set of models sent by Pawel Kowalski. They revealed other different bottlenecks than mentioned below, and therefore described improvements do not affect them. I’ll be continuing my experiments as time permits and will hopefully post further findings)

* Story *
So let us follow the steps which have been made.

I have focused on the BopTools_DSFiller class which is central to the Boolean Operations (BOP) as it prepares the models by intersecting them so that later on fuse, common, and cut just take its results and reconstruct requested combination.

As a first test case, I took two models provided by my former colleagues at OCC who participated in Intel Parallel Studio beta program. These were two solids of 130+ faces each, and BopTools_DSFiller::Perform()took 67secs of CPU time.

I installed the latest build of Intel Parallel Amplifier (reminder: public Beta will be available in early January and you can subscribe already now here – www.intel.com/go/parallel). The only applicable analysis type was ‘Hotspot Analysis’ which identifies most CPU-consuming functions. Amplifier also offers ‘Concurrency Analysis’ and ‘Waits & Locks Analysis’ but these were irrelevant as BOPs currently run in single thread only, while they are tailored to multi-threaded apps.

* First findings *
Top functions that Amplifier reported were located in TKGeomAlgo.dll and related to the IntPolyh package. Not surprising as BOPs are based on meshes intersection and IntPolyh creates those meshes.
Top 3 functions – constructors of IntPolyh_Triangle, _StartPoint, and _Edge altogether took almost 20 seconds (see the image below).

(to be continued)

Adding colors and names to your application. Part 3

2008-12-03T20:13:00.004+03:00

(continued)

* Visualization of the shapes*

The XDE framework provides functionality to display contents in 3D viewer with the help of XCAFPrs_AISObject, which eventually inherits AIS_InteractiveObject and thus can be used in a usual manner.

Since XDE is OCAF-based you should couple it with AIS in OCAF-specific way, i.e. associating a driver (TPrsStd_Driver descendant) that creates an interactive object. In this case the driver is XCAFPrs_Driver that creates an instance of XCAFPrs_AISObject. Below is a code skeleton:

TDF_Label anAccess = aDoc->GetData()->Root();
Handle(TPrsStd_AISViewer) anAISViewer;
if (!TPrsStd_AISViewer::Find (anAccess, anAISViewer)) {
Handle(V3d_Viewer) aViewer = ...;
anAISViewer = TPrsStd_AISViewer::New (anAcces, aViewer);
}

// collect sequence of labels to display
Handle(XCAFDoc_ShapeTool) aShapeTool = XCAFDoc_DocumentTool::ShapeTool (aDoc->Main());
TDF_LabelSequence seq;
aShapeTool->GetFreeShapes (seq);

// set presentations and show
for ( Standard_Integer i=1; i <= seq.Length(); i++ ) {
Handle(TPrsStd_AISPresentation) prs;
if ( ! seq.Value(i).FindAttribute ( TPrsStd_AISPresentation::GetID(), prs ) ) {
prs = TPrsStd_AISPresentation::Set(seq.Value(i),XCAFPrs_Driver::GetID());
}
prs->Display(Standard_True);
}
TPrsStd_AISViewer::Update(aDoc->GetData()->Root());

Here’s a 3D viewer screenshot.

In order to enable display of names, then XCAFPrs::SetViewNameMode() must be called with Standard_True (before display). Below is an example of 3D view with names display turned on:

Note that displayed text labels adversely impact performance, and in the case of numerous displayed labels, your viewer can become significantly less responsive.

* Non-OCAF based documents *

If for any reason you don’t use OCAF and want to exchange attributes with IGES and STEP, you will have to do this on your own directly accessing objects representing file entities. Look at source code of STEPCAFControl and IGESCAFControl packages to copy XDE behavior.

(The end)
Please rate this article using the voting buttons under the text.

Adding colors and names to your application. Part 2

2008-12-02T20:00:00.006+03:00

(continued)

OCC_UT_MyXDEApp could have inherited XCAFApp_Application and redefinition of Formats() and ResourcesName() would not have been required. But XCAFApp_Application’s constructor has been declared private (instead of protected) what disables inheritance :-(. Perhaps, OCC folks could correct that.

The document is created in a straightforward way:

Handle(TDocStd_Application) anApp = OCC_UT_MyXDEApp::GetApplication(); Handle(TDocStd_Document) aDoc; anApp->NewDocument ("XmlXCAF", aDoc);

The screenshot below shows the structure of a new document created with above application.

Note that XCAFDoc_DocumentTool has been assigned to the label 0:1:1:1 and it created a sub-tree with several pre-defined labels (XCAFDoc_ShapeTool, _ColorTool, etc).

OCC provides persistence for XDE-specific attributes in all three supported format (see StdResource) – standard textual, xml and binary. Some attributes (e.g. XCAFDoc_MaterialTool) are not stored in a file and are re-creating during read process.

TCollection_ExtendedString anErrorMsg;
anApp->SaveAs (aDoc, "C:\\Dev\\3dmodels\\sampledoc.xml", anErrorMsg);
if (anErrorMsg.Length()) {
std::cout << "Error occurred - " << TCollection_AsciiString (anErrorMsg).ToCString() << std::endl;

}

Here is a resulting XML file:

* Import /export with IGES and STEP *

To read/write colors and names from/to IGES or STEP you have to use classes {IGES,STEP}CAFControl_{Reader,Writer}, e.g. IGESCAFControl_Reader or STEPCAFControl_Writer.

IGESCAFControl_Reader aReader; IFSelect_ReturnStatus aStatus = aReader.ReadFile (aFileName); if (aStatus == IFSelect_RetDone) { Standard_Boolean aRes = aReader.Transfer (aDoc); }

Here is a document content after import of a sample file:

(to be continued)

Adding colors and names to your application. Part 1

2008-12-02T12:41:00.002+03:00

If you have to exchange data with other applications via IGES or STEP (or perhaps other formats, if you are a commercial client of the Open CASCADE company), you might want to enrich your application with meta data in addition to geometry. We will consider names and colors which are often asked about on the Open CASCADE forum.

OCC provides a ready-to-use framework – called XDE (eXtended Data Exchange) – which is based on OCAF. XDE offers a pre-defined document sub-structure to store colors, names, layers as well as other attributes (see XDE User’s Guide for details). This is done through a set of attributes defined in the XCAFDoc package that provides API to access data.

*Basic definitions*

Let’s start with assumption that your application uses OCAF for data description. In order to make your OCAF document XDE-compliant, you need to add XCAFDoc_DocumentTool attribute to your label of choice. It will add other required attributes to the sublabels. The easiest way is to extend your application class deriving TDocStd_Application, for example as follows:

DEFINE_STANDARD_HANDLE(OCC_UT_MyXDEApp,TDocStd_Application)
class OCC_UT_MyXDEApp : public TDocStd_Application
{
public:
//singleton pattern
Standard_EXPORT static const Handle(OCC_UT_MyXDEApp)& GetApplication();

virtual void Formats (TColStd_SequenceOfExtendedString& theFormats)
{ XCAFApp_Application::GetApplication()->Formats (theFormats); }

virtual Standard_CString ResourcesName()
{ return XCAFApp_Application::GetApplication()->ResourcesName(); }

Standard_EXPORT virtual void InitDocument (const Handle(TDocStd_Document)& theDoc) const;

protected:
OCC_UT_MyXDEApp() {}

public:
DEFINE_STANDARD_RTTI(OCC_UT_MyXDEApp)
};

IMPLEMENT_STANDARD_HANDLE(OCC_UT_MyXDEApp,TDocStd_Application)
IMPLEMENT_STANDARD_RTTIEXT(OCC_UT_MyXDEApp,TDocStd_Application)

const Handle(OCC_UT_MyXDEApp)& OCC_UT_MyXDEApp::GetApplication()
{
static Handle(OCC_UT_MyXDEApp) anApp = new OCC_UT_MyXDEApp;
return anApp;
}

void OCC_UT_MyXDEApp::InitDocument (const Handle(TDocStd_Document)& theDoc) const
{
//create a child of the main label and put XCAFDoc_DocumentTool there (i.e.
//one level below comparing to default XDE)
TDF_Label aL = theDoc->Main().FindChild (1, Standard_True); //0:1:1
XCAFDoc_DocumentTool::Set (aL.FindChild (1, Standard_True), Standard_False); //0:1:1:1
}

(to be continued)

Sharpening your tools

2008-11-28T18:40:00.001+03:00

Let me share with you a couple of simple things that could make your life a bit easier if you use Microsoft Visual Studio for development on Open CASCADE.

1. Highlighting Open CASCADE class names in the editor

This will improve your code readability and what is more important, can serve as additional quick check whether you correctly spell a OCC class name before you get a compiler error ;-).

What you just need to do is to copy the file UserType.dat shipped with Open CASCADE (tools subdirectory) it to where devenv.exe is located. For instance, on my laptop it’s here - c:\Program Files\Microsoft Visual Studio 8\Common7\IDE\. If you already have some UserType.dat, just concatenate the contents.

2. More convenient display of Open CASCADE data types in debugger

Have you even been tired of clicking in a deep nested tree in the Watcher window to dig down from your surface just to check its reference count ? If yes, this can be for you.

As you might know, the debugger allows you to display complex types (e.g. classes) not only as default ‘{…}’. To do that you can describe display rules, modifying the autoexp.dat file.
I have found and extended one with a few frequently used OCC types. Go download it here and insert into autoexp.dat, located inside Visual Studio hierarchy. For instance, for VS2005 it is here - c:\Program Files\Microsoft Visual Studio 8\Common7\Packages\Debugger\Autoexp.dat.
Compare these two screenshots. The one below (with modified autoexp.dat) displays everything what one above does but in a more concise form without forcing you to expand the tree.

OCC team: feel free to include this file or its extended version into Open CASCADE release ;-).

There is yet another functionality – skipping stepping into a function in the Debugger, so that when you click F11, it bypasses some internal functions you don’t want to spend your time in. This is an undocumented technique described here. I did not try it but you may want to. If you are a success, please share your settings with us, this will likely be helpful for several people.

There are likely more than that. If anyone is willing to share his/her experience, please send me an email at roman.lygin@gmail.com and I can post it.

Building from scratch. Part 2

2008-11-26T13:34:00.002+03:00

(continued)

First, do you know where WOK name comes from ? It’s not just Workshop Organization Kit as named in the documentation. In Chinese cuisine wok is a deep convex pan in which chef cooks food (I’m sure you saw it, right ?) The name was given by a former Matra Datavision employee who was of Chinese origin and initiated it. WOK was used in MDTV in multi-site, multi-team, cross-platform environment who intensively worked on development of one product bundle (Euclid Quantum) that contained many components (including its foundation – CAS.CADE). The source base was huge, release cycles were asynchronous and this could not fit into one source control repository that would permanently built. Take into account state of the art hardware of that time (slow Sun workstations, networks, etc). So development environment had to reflect that and WOK really enabled that dispersed and hierarchical environment. You could take a piece of software and put into your local workbench or creates a tree of workbenches and develop.

Time passed, Euclid Quantum dissolved, CAS.CADE transformed into Open CASCADE, but WOK is still alive though not developed anymore. It’s pure legacy, and current investment into it would unlikely be justified. WOK still does its job enabling cross-platform and multi-team software development but it’s way too heavy for that. It’s like if you used a truck to drive to your office one mile away from your home.

In terms of building time WOK does not stand any competition with VS which builds in parallel threads. Building Data Exchange module in Release mode on quad-core Xeon processor took 13 minutes where WOK was crunching for 32.

My personal view on development environment is that you should borrow what is available outside. Don’t re-invent a wheel when others produce good ones you can freely use. There are options available out there, with wide adoption, with active evolution. Go and grab some. In our team in Intel we use SVN and SCONS-based build system (of course, with custom tweaks to setup a whole infrastructure around it – promotion process, unit and integration tests, build rotation, etc). I heard Google’s Chrome also uses SCONS. There are also cmake, qmake (Qt-tailored) and likely many other decent options.

Migration has a cost, but if you count long term benefits, you can change your mind. My humble opinion.

Building from scratch. Part 1

2008-11-26T13:04:00.002+03:00

As I said in my previous post, we decided to integrate OCC into our team’s app test database at Intel. So I committed to enable that integration and proceeded to the task.

In order to get correct data when profiling an application (including using Intel Parallel Amplifier and Inspector), it must be compiled with /Zi option and linked with /DEBUG options to enable symbol information and store it in pdb. For performance tuning it should also be compiled with /O2 (maximize speed), and software vendors usually apply it. So, I needed all these three. This is not a default combination offered by Visual Studio (/Zi and /DEBUG come in Debug configuration with /Od and Release come with /O2 but without /Zi and /DEBUG). OCC ships *.vcproj files with those conventions. So I had to manually update all *.vcproj and for the Release config to set /Zi and /DEBUG. This was a first challenge, as OCC does not provide a single VS solution (*.sln) where I could select all projects and modify only once (fortunately Visual Studio provides multiple selection of the projects to change settings at once). So I had to reopen each solution one by one. I was luck as setting /Zi and /DEBUG could be done at the project file level and each source file (*.cxx) inherited these settings. This is not the case for optimization parameters (/O2) which are set in OCC shipped *.vcproj files on individual basis, for each source file. I believe this was done by intended oversight in some scripts generating *.vcproj from WOK. But this did not make my life easier two months ago when I initially had to set /Od for Release configurations (and I had to ‘grep’ project files and remove individual settings then). OCC folks in charge of the build environment and those who tweak OCC files might want to take this note into account.

Rebuilding OCC in MSVS (I am currently using 2005, by the way) was straightforward and seamless. Just had to reopen a new solution every few minutes and click Build Solution. The fact that there is no single global solution is a bit irritating though. I remember in the past we refrained from creating it because VS98 simply could not deal with it (running out of memory or something like that). Is it still the problem on newer VS (2003 and beyond), did anyone try ?
What was a bit annoying is number of warnings, sometimes really ugly (like intentional semicolon after some ‘if’ in Foundation Classes or constant arithmetic overflow in Modeling Algorithms). Right now in our team at Intel we are also fighting with warnings and set an aggressive goal to treat warnings as errors (we are not there yet however). Every code promotion will be rejected if it reveals warnings. Though it adds some overhead (and some developers complain) I believe this is beneficial for the product. So, if OCC team adopts that behavior sometime, we may see OCC compiled with 0 warnings ;-).

A few words on WOK. As I have to use my patched version of OCC 6.3.0 (to enable multi-threading and use some other modifications), I had to start with WOK. There are modifications in CDL extractor (that generates *.hxx from *.cdl) and in addition that are several new classes (with *.cdl definitions). Well, WOK is not something an average developer would (and should!) understand. It’s a beast in its own. Two months ago I spent a good deal of time to install it on my laptop and even this time when migrating to a lab workstation I had to be very careful in setting up an environment in multiple *.edl and *.bat files. Unless you spent several months or years with it, any mistake can cost you hours to figure out what goes wrong. I would seriously recommend you not to use it unless you really have to and understand what you are doing. WOK however was a great idea in 1990-es and let me shed some light on it.

(to be continued)

Open CASCADE inside Intel, or ... Intel inside

2008-11-24T12:32:00.002+03:00

Just finished the meeting with my Intel colleagues where we decided that Open CASCADE would be integrated into an internal application database for testing our software products. I am a program manager in the team that is developing new products – Intel Parallel Amplifier and Parallel Inspector, which will be part of the Intel Parallel Studio (www.intel.com/go/parallel). They are approaching public Beta program (feel free to sign up by the way!) and are currently in hands of our few Beta customers. Guess who is among those few ?

Why did we chose Open CASCADE software for app testing? Because it helps make Intel products better ! It already allowed us to find several bugs before we released first Beta, and we are still discovering more with it. Despite that it’s single-threaded today there are steps to multi-threading. I am also going to use the multi-threading framework prototype for testing it in parallel mode (mentioned on the forum in October).

I really enjoy situations like this – when you can combine interests of several parties. It’s good for Intel, it’s good for Open CASCADE, it’s good for me ;-). I love to be a ‘deal maker’, and you ?

Disclaimer: Whenever I talk about Intel, this represents my sole personal opinion, it does not reflect any official position of the company. That’s a policy. I had to say it. I did.

Open CASCADE Handles. Let's handle'em. Part 3

2008-11-21T12:54:00.002+03:00

(continued)

3. Bypass DownCast() in critical places.
Compare:
a.
Handle(Standard_Transient) aTransient = new OCC_UT_Id(1);

for (i = 0 ; i < aNbCycles; i++) {
anId = Handle(OCC_UT_Id)::DownCast (aTransient)->Id();
}
b.
for (i = 0 ; i < aNbCycles; i++) {
Handle(OCC_UT_Id)& anIdHTmp = *((Handle(OCC_UT_Id)*) &aTransient);
anId = anIdHTmp->Id();
}
c. for (i = 0 ; i < aNbCycles; i++) {
OCC_UT_Id* anIdPTmp = (OCC_UT_Id*)aTransient.Access();
anId = anIdPTmp->Id();
}

a. takes 1.75s, b. and c. – ~0.04s, or are 40+ times faster (in some runs 100+) !

You will find use of b. in BRep_Tool methods, by the way.

However beware of cases with potential problems. Never use direct cast unless you can reliably check, if you can safely use it. For instance, the following code throws an exception instead of returning a null handle:
TopoDS_Face aFace;
TopLoc_Location aLoc;
Handle(Geom_Surface) aSurf = BRep_Tool::Surface (aFace, aLoc);

These were my insights. Anybody to share others ? I’d love to hear.

As Handles() are most widely used classes, their implementation must be flawless. In this regard, I wonder if use of UndefinedHandleAddress (equal to 0xfefd0000 or 0xfefdfefdfefd0000 on 64-bit platforms – see Hande_Standard_Transient.hxx) to denote a null handle makes any sense. Perhaps, plain zero would be enough, and this would save on comparison operators. Is someone willing to experiment ? OCC folks ?

*Multi-threading considerations*
In the conclusion, let me add that Handle() is not (yet?) thread-safe. You need to protect a handle instance with critical section (e.g. with Standard_Mutex) to use concurrently. Otherwise you may have a data race (concurrent access to unprotected data) and may end up with broken reference counter and consequently memory leaks, access violations, or other headaches.

Well, that was it, folks. So, how useful was it ? Please post your comments and tell me what you think. This is important for me. Thanks.
Roman

Open CASCADE Handles. Let's handle'em. Part 2

2008-11-20T23:40:00.002+03:00

(continued)

*Standard_Transient and MMgt_TShared*
If you are attentive enough, you will likely notice that most handle classes inherit MMgt_TShared, while it does not add any value to Standard_Transient. The comments in the cdl file claims it supports reference counting. Well, reference counter is inside Standard_Transient ! I dove into the source code of Open CASCADE 3.0 (released in 1999, the first open source release) and it is the same. So, it seems this change was done more than ten years ago, but the orphan MMgt_TShared is still alive. So, I am now using Standard_Transient only and advised OCC folks to remove MMgt_TShared eventually. So, you might want to migrate to Standard_Transient as your base class as well.

*Cyclic dependencies*
The underlying objects won’t get destroyed if you have cyclic dependence (i.e. one object referring to the other), and you will end up with a memory leak. For instance the following class is prone to such a cyclic dependency:

DEFINE_STANDARD_HANDLE(OCC_UT_Employee,Standard_Transient)
class OCC_UT_Employee : public Standard_Transient
{
public:
OCC_UT_Employee (const Handle(OCC_UT_Employee)& theBoss) : myBoss (theBoss) {}
const Handle(OCC_UT_Employee)& Boss() const { return myBoss; }
void AddDirectReport (const Handle(OCC_UT_Employee)& theReport);

private:
Handle(OCC_UT_Employee) myBoss;
TColStd_ListOfTransient myDirectReports;
public:
DEFINE_STANDARD_RTTI(OCC_UT_Employee)
};

As Foundation Classes User’s Guide suggests you either have to use pointers in some case (e.g. OCC_UT_Employee* myBoss) or nullify some references first (myBoss.Nullify()).

*Handle overhead*
Like for anything in this world, you have to pay for convenience of using a handle. Any assignment or deallocation leads to execution of several instructions (comparisons, function calls, branching, etc). Keep that mind. If you are using handle in performance-critical places, think how you can optimize. Some hints on top of my head:

1. Make DownCast() to some expected type first and then use inside a cycle.
Compare two implementations:

static void CheckEmployee (const Handle(Standard_Transient)& theEmployee)
{
for (int i = 0 ; i < aNbCycles; i++) {
Handle(OCC_UT_Employee) anEmp = Handle(OCC_UT_Employee)::DownCast (theEmployee);
}
}

static void CheckEmployee (const Handle(Standard_Transient)& theEmployee)
{
Handle(OCC_UT_Employee) anEmployee = Handle(OCC_UT_Employee)::DownCast (theEmployee);
for (int i = 0 ; i < aNbCycles; i++) {
Handle(OCC_UT_Employee) anEmp = anEmployee;
}
}

With aNbCycles equal 10 millions, on my laptop, the former takes 1.6 secs, and the latter – 0.42 secs, or 3.8X speed up.

2. Avoid copies
Make your class methods return const Handle()& whenever possible and assign to the same type in the caller, rather than using plain Handle(). Consider the following two cases:

a. Imagine you initially defined the Boss() method in OCC_UT_Employee class as follows:
Handle(OCC_UT_Employee) Boss() const { return myBoss; }

and use it as follows:
static void CheckBoss (const Handle(Standard_Transient)& theEmployee)
{
Handle(OCC_UT_Employee) anEmployee = Handle(OCC_UT_Employee)::DownCast (theEmployee);
for (int i = 0 ; i < aNbCycles; i++) {
Handle(OCC_UT_Employee) aBoss = anEmployee->Boss();
}
}

b. Now you switch to const Handle()&:

const Handle(OCC_UT_Employee)& Boss() const { return myBoss; }
...
static void CheckBoss (const Handle(Standard_Transient)& theEmployee)
{
Handle(OCC_UT_Employee) anEmployee = Handle(OCC_UT_Employee)::DownCast (theEmployee);
for (int i = 0 ; i < aNbCycles; i++) {
const Handle(OCC_UT_Employee)& aBoss = anEmployee->Boss();
}
}

Speed up is from 0.26s to 0.03s, or 8.5x ! However, admittedly, Open CASCADE code itself is contaminated with these issues. OCC folks: if you are reading this, please take a note ;-).

(to be continued)

Open CASCADE Handles. Let's handle'em. Part 1

2008-11-20T20:22:00.002+03:00

Let me start the first article with something simple yet important if you want to develop on Open CASCADE.
You likely noticed that many classes inherit Standard_Transient, directly or via other ancestors, e.g. Geom_Surface or AIS_InteractiveObject, and that in the code that are used as Handle(Geom_Surface).

Open CASCADE tries to never use pointers (at least in API). Whenever it needs a shared object it uses a handle.

Handle is a well known concept often referred to as a smart pointer. The Boost library (www.boost.org) , for instance, has several classes for smart point and, intrusive_ptr seems to be the closest equivalent to OCC’s Handle. Qt (www.trolltech.com) has QPointer.

Handle provides you with a mechanism to automatically refer to an object without a headache of destruction. The underlying object (Standard_Transient descendant) will get destroyed when the last handle pointing to it is destroyed.
In addition to that handle provides safe type recognition and downcasting. Read Foundation Classes User’s Guide for more details.

Unlike Boost or Qt which define smart pointers with templates, Open CASCADE uses two parallel explicit class hierarchies: one deriving from Standard_Transient and another from Handle_Standard_Transient. When CDL extractor generates a header file, or when you are using a macro DEFINE_STANDARD_HANDLE, then you end up with a new handle class. I believe a choice in favor of hierarchy of Handles was done for historical reason when old compilers in 1990es did not support templates well. Presumably, for the same reason TCollection classes are also based on #defines (until in 2002 there appeared NCollection which is template-based).

For the sake of truth, I must note that there is yet another parallel hierarchy – for so called persistent classes inheriting Standard_Persistent. But as they are almost never used directly we can omit them in this article. But everything said here, applies to those classes as well.

To create your handle class you need to use the following macros defined in Standard_DefineHandle.hxx:

DECLARE_STANDARD_HANDLE(class_name,ancestor_name)
DEFINE_STANDARD_RTTI(class_name)

IMPLEMENT_STANDARD_HANDLE(class_name,ancestor_name)
IMPLEMENT_STANDARD_RTTIEXT(class_name,ancestor_name)

For instance :

DEFINE_STANDARD_HANDLE(OCC_UT_Id,Standard_Transient)
class OCC_UT_Id : public Standard_Transient
{
public:
OCC_UT_Id() : myId (0) {}
OCC_UT_Id(const Standard_Integer theId) : myId (theId) {}
Standard_Integer Id() const { return myId; }
private:
Standard_Integer myId;
public:
DEFINE_STANDARD_RTTI(OCC_UT_Id)
};

IMPLEMENT_STANDARD_HANDLE(OCC_UT_Id,Standard_Transient)
IMPLEMENT_STANDARD_RTTIEXT(OCC_UT_Id,Standard_Transient)

Most curios folks might have noticed that DEFINE_STANDARD_RTTI does not really need an argument as it translates into method declaration inside the class, but it’s kept for better consistency ;-).

Until 6.3.0, the Open CASCADE CDL extractor generated explicit code for handle (e.g. Handle_Geom_Surface.hxx). I have recently sent a modified version thereof to the folks in the company so that it now generates macros-using header making code cleaner. May it eat own food.

Another note. On the forum I saw people using macros IMPLEMENT_STANDARD_RTTI along with IMPLEMENT_STANDARD_TYPE, IMPLEMENT_STANDARD_SUPERTYPE,
IMPLEMENT_STANDARD_SUPERTYPE_ARRAY, etc trying to imitate CDL extractor (what it puts into drv subdirectory). Don’t bother with that, folks. IMPLEMENT_STANDARD_RTTIEXT will do all the work for you, and you code will be cleaner.

(to be continued)

My first blog post. Introduction

2008-11-19T19:49:00.002+03:00

This is my first experience as a blogger. Ever. No idea if it will work out or not. Let's see together.

I had been working at Open CASCADE for 7 years till 2004, before moved to Intel where I am now. These were fantastic years, that gave me invaluable experience in software development and project management, customer relationship, and working across multiple geos and cultures.

My path started in 1997 as a software engineer in the CAD Data Exchange team, and this proved to be lucky as it allowed to learn much of the OCC code, as data exchange employs multiple OCC algorithms. If you ever happened to look into the source code of IGES, STEP, or Shape Healing modules you have probably noticed either my full name there (e.g. in IGESToBRep_IGESBoundary.cxx) , or an acronym 'rln' (e.g. in ShapeFix_Wire.cxx). Every Open CASCADE employee has an acronym, widely used internally (I remember meeting minutes containing something like "Attendees: ABV, PDN, GKA, SMH, SZV, ..."). RLN was mine. By the way, it was funny not to find this system in Intel which is overwhelmed with TLAs (Three Letter Acronyms), people use first names here (sometimes with a first letter of a last name - for example, Roman S - if there are several Romans in context).

I'm still in quite close touch with the Open CASCADE team, we are friends with many guys there. Even at Intel from time to time I dive into OCC to check what is new there, and take a chance to develop something(a few weeks ago I prototyped a framework for multi-threading in OCC).

So why a blog ? What is it for ?

- To share my inspiration. Sometimes I cannot resist to reply being caught by some question on the forum or to break for a lunch in the middle of some started prototype. Can you imagine a crazy guy who would develop a corporate product at home because his job did not imply his doing that in working hours? Well, that was about me in 2001 when I switched to full time management. Despite all its deficiencies, I believe OCC is a great product but substantially undervalued, imho. It does not have recognition it could have.
- To share knowledge and help others. There are people struggling on the forum asking same questions again and again, which I could answer in a matter of seconds. Reference documentation is not always enough, sometimes an overview would be a better option.

Is there anything in it for me ? First off, to learn more about who and how uses it. Visiting customers in the past, I saw impressive OCC-based apps so that I was ready to shout 'how did you do that ?'. So, if people would like share their tricks, I will be happy to learn with others. Software skills are important to maintain.

I am thinking to put my notes into the form of short (or not so short) articles that would be interesting for a community. So, if you already have some particular interest please advise what you would like to see.

A few clarifications:
- This blog is not supposed to be a one-way channel. Comments are encouraged and appreciated. Opinions and experiences are welcomed. If anyone will be ready to add his/her own article, then it will be great.
- I don't know all tiny details of OCC (and doubt there is a single person to meet that expectation). There are shadow areas, which I am not ready to comment upfront. But I can dig into it or share some insights as needed. Again, if there are people with deeper knowledge, their contribution will be invaluable.
- And yes, this blog is my personal initiative, in no way is it sponsored by Open CASCADE or any other parties.

Thank you.
Roman