face union

[wmayer]

As a performance test try also this:

Code: Select all

App.ActiveDocument.addObject("Part::Box","Box")
App.ActiveDocument.recompute()
import MeshPart
__doc__=FreeCAD.getDocument("Unnamed")
__mesh__=__doc__.addObject("Mesh::Feature","Mesh")
__mesh__.Mesh=MeshPart.meshFromShape(__doc__.getObject("Box").Shape,1,0,0,0.1)

import Part
FreeCAD.getDocument("Unnamed").addObject("Part::Feature","Mesh001")
__shape__=Part.Shape()
__shape__.makeShapeFromMesh(FreeCAD.getDocument("Unnamed").getObject("Mesh").Mesh.Topology,0.100000)
FreeCAD.getDocument("Unnamed").getObject("Mesh001").Shape=__shape__
__shape__.removeSplitter()
Part.show(__shape__)

[yorik]

I think you guys are adding some extremely important stuff to OCC! Wouldn't the OCE people be interested in this too?

[tanderson69]

The other issue you have noticed must be solved differently.

I am with yah.

To have an example showing this issue you can load the solid from the mantis item and run this piece of code:

Thanks for the python lesson. I ran your code and did the same test and with more faces. I even did one with all the body faces. Everyone worked as you would expect....So I am thinking maybe there is some slop (tolerance) in the original body that gets fixed by the python shell command. Doesn't the shell command use the occ sewing? Where did this model come from?

I will take a look at your performace test next.

Wouldn't the OCE people be interested in this too?

Lets get some mileage first and build up some confidence.

[tanderson69]

As a performance test try also this:

Fast it is not!

[wmayer]

Doesn't the shell command use the occ sewing? Where did this model come from?

Look at the method PyInit here: http://free-cad.svn.sourceforge.net/vie ... iew=markup
It uses BRep_Builder to add the faces step by step. If BRepCheck_Analyzer detects any problems we use ShapeUpgrade_ShellSewing to sew them together.

Fast it is not!

I guess it has a runtime of O(n^2) or so. Once I implemented a similar algorithm to directly create a shape from a mesh. Look here: http://free-cad.svn.sourceforge.net/vie ... iew=markup

[tanderson69]

It uses BRep_Builder to add the faces step by step. If BRepCheck_Analyzer detects any problems we use ShapeUpgrade_ShellSewing to sew them together.

I am wondering if the sew is actually called for the mantis part? Take a look at the attached file. There is the original solid and two others appropriately named working and noworking. Ignore the box. the only difference between the pair (working and noworking solids) is the subtraction of the box. this pair have the same number of faces, edges and vertices. I only used cuts on the original solid to derive the pair. So I fed these two into my standalone app and here is the output. I added a ShapeAnalysis_Shell::hasFreeEdges.

noworking:

Code: Select all

shell does not have free edges
equality group count: 1
      adjacency group count: 0

working:

Code: Select all

shell does not have free edges
equality group count: 1
      adjacency group count: 1
         face count is: 2

so basically ModelRefine::hasSharedEdges is failing. I am thinking there is something wrong with the original solid that none of the checking routines find, but somehow get fixed in the modeling routines. I might also be ignorant about the meaning of shell free edges and edge.IsSame.


speed:
I will be honest. I thought about efficiency for about 2 seconds up front and 2 seconds in the back. There are going to be a bunch of ways to improve the performance. I got to get out of here so I can get into that right now.

Look here: http://free-cad.svn.sourceforge.net/vie ... iew=markup

The bounding box is a great idea. If you look at FaceTypedPlane::buildFace in my code. You will look at the stupid idea I had and a long comment about how I don't like it.

[wmayer]

so basically ModelRefine::hasSharedEdges is failing. I am thinking there is something wrong with the original solid that none of the checking routines find, but somehow get fixed in the modeling routines. I might also be ignorant about the meaning of shell free edges and edge.IsSame.

Strange. Even IsPartner() which is less restrictive fails. So, that actually would mean there are two TShapes. But I remember I had recently the same problem but can't remember in which context.

The bounding box is a great idea. If you look at FaceTypedPlane::buildFace in my code. You will look at the stupid idea I had and a long comment about how I don't like it.

You may also have a look at FeatureSketchBased.cpp from PartDesign module.

[wmayer]

In modelRefine.cpp line 474, there is an error:

Code: Select all

if (faceTest.State() == TopAbs_EXTERNAL)

TopAbs_EXTERNAL is an TopAbs_Orientation. So, you actually have to use either TopAbs_IN, _OUT, _ON, _UNKNOWN.

[tanderson69]

So, you actually have to use either TopAbs_IN, _OUT, _ON, _UNKNOWN.

yup.

Strange. Even IsPartner() which is less restrictive fails. So, that actually would mean there are two TShapes. But I remember I had recently the same problem but can't remember in which context.

I think this is an OCC bug and we should ignore it for now and revisit it if it causes too many problems in the future.

You may also have a look at FeatureSketchBased.cpp from PartDesign module.

I am guessing that for the sketcher you had to have a much broader approach to the boundary analysis than what we need for the face union. The sketcher might have several outer boundaries and may have some inners, where with the face union we have one outer and if there are more boundaries we know they are inner. So, for the face union we should be able to just use the boundary with the largest bounding box for the outer boundaries and the rest are interior boundaries. Then we won't have to build the faces just to test.

back to speed: There are basically three steps(loops) right now to get the faces grouped together that can be replaced. the steps are:
put all the faces together that are the same type: planar cylindrical etc..
put all the faces together that are equal(defined by the typedclass).
put all the faces together that are adjacent.

the first 2 steps could probably be combinded into one without too much trouble and that would eliminate one loop. I think the 3rd step should remain on it's own as it uses recursion and would be a killer if we had to bring that out to a main loop. I think when we get to the adjacent find it would be beneficial to set up some kind of map from the faces to the edges instead of constantly calling getFaceEdges. I am not convinced that I have the recursion right. When I was testing that the edge.isSame problem I saw a bunch more calls to getFaceEdges than I expected. I will have to get my head back into that and it might be a significant bottleneck.

Your time complexity estimate could be spot on, but I think more relevant to the adjacency portion and not the whole operation. I would like to see the time comparison between a meshed cube with 100 faces on each side with a meshed cube that has 595 face on one side and 1 face on the other five sides. With the problem domain I was considering (basic primitive booleans and the resultant faces), I figured that the adjacency algorithm was going to be working with a very small subset of faces. Thinking the type and equality checks would eliminate most of our faces from our working sets. My point is that we should be careful about optimizing to a mesh box as that will probably tell us that the adjacency code is slow were in the real world it could be something else. I am making an assumption that merging faces of a mesh isn't something that we need to do in the real world. Is it?

[wmayer]

When I was testing that the edge.isSame problem I saw a bunch more calls to getFaceEdges than I expected. I will have to get my head back into that and it might be a significant bottleneck.

I should use the OCC debug libs and look what's going on there.

I would like to see the time comparison between a meshed cube with 100 faces on each side with a meshed cube that has 595 face on one side and 1 face on the other five sides.

We're using a region-growing algorithm where we start with an arbitrary triangle. Starting form this we visit its neighbours, visit the neighbours of the neighbours, ... until we have visited all triangles. For the start triangle we already have a plane defined. For its neighbours we then check which of them fits to the plane. Afterwards we have a list of segments. Then for each segment we can easily extract the boundaries and build a CAD face of it.

For a cube with 100 faces or 595 faces you probably don't see a big difference because here we should reach a time complexity of O(n).

My point is that we should be careful about optimizing to a mesh box as that will probably tell us that the adjacency code is slow were in the real world it could be something else. I am making an assumption that merging faces of a mesh isn't something that we need to do in the real world. Is it?

Sure, you're right. But in case we find some intelligent algorithm that is quite fast in this worst-case scenario then it is fast in all other cases, too.