Performance problem with tessellation

[christianstroh]

There is a performance issue when loading IFC files with tessellation.
Loading a specific file takes several minutes.
I ran Visual Studio's Performance Profiler to see where the hotspot was in the code.
It looks like the suspect is the tessellation.
I can provide the diagsession file if needed.
BIMvision loads the same file much faster - perhaps performance can be optimized here.

Assemblies and versions affected:

Project Xbim.Tessellator in solution Xbim.Essentials (master branch).

Steps (or code) to reproduce the issue:

Load a specific ifc file with XbimXplorer.

Minimal file to reproduce the issue:

IFC files need to be zipped to be uploaded. Then just drag & drop here

Expected behavior:

Faster loading.

Actual behavior or exception details:

It takes a long time to load.

[martin1cerny]

Hi @christianstroh. You have gone to a great depth with this already. Any suggestion for the actual optimisation? We find the triangulation in IFC files is often not very good. This code attempts to improve it by removing redundant edges. Do you have any other suggestions?

[christianstroh]

Hi. I haven't done this myself yet. In my free time I could spend some time looking at what state of the art algorithms there are.

[andyward]

I think it would be easier if you share the test harness you've built (and affected model)? It's tricky to see the hotspot from the screenshots. Not sure how much it will affect the performance but it looks like you're in Debug mode so won't be optimised.

On a cursory inspection I fail to see how AddEdge() can be so expensive... Just wondering if XbimTriangleEdge should have a GetHashCode() & Equals implementation as we're testing equality a lot?

[christianstroh]

The diagsession file is too large to be an attachment (35 MB). Can I send it to you by email?
I am not allowed to publish the IFC file.

I loaded the IFC file in release mode, which unfortunately isn't any faster.

The hot spot appears to be the call to XbimTriangulatedMesh.AddTriangle() within XbimTessellator.TriangulateFaces() - 62%.
Which is called within a foreach loop. You can perhaps simply replace this with Parallel.ForEach() as a first step?

The very performant state of the art algorithm is said to be the 'Delaunay triangulation'. This also works in three dimensions.
Alternatively, the 'Octree'.

[christianstroh]

This optimized code loads the file approximately 25% faster (128 instead of 171 seconds). I use Parallel.ForEach(), lock() - since XbimTriangulatedMesh doesn't seem to be thread-safe and Interlocked.Increment() for incrementing the integer.

        private readonly object lockObject = new object();

        private XbimTriangulatedMesh TriangulateFaces(IList<IIfcFace> ifcFaces, int entityLabel, float precision)
        {
            int faceId = 0;

            var faceCount = ifcFaces.Count;
            var triangulatedMesh = new XbimTriangulatedMesh(faceCount, precision);
            Parallel.ForEach(ifcFaces, ifcFace =>
            {
                //improves performance and reduces memory load
                var tess = new Tess();

                var contours = new List<ContourVertex[]>(/*Count?*/);
                foreach (var bound in ifcFace.Bounds) //build all the loops
                {
                    var polyLoop = bound.Bound as IIfcPolyLoop;

                    if (polyLoop == null) continue; //skip empty faces
                    var polygon = polyLoop.Polygon;

                    if (polygon.Count < 3) continue; //skip non-polygonal faces
                    var is3D = (polygon[0].Dim == 3);

                    var contour = new ContourVertex[polygon.Count];
                    if (bound.Orientation)
                    {
                        for (var j = 0; j < polygon.Count; j++)
                        {
                            var v = new Vec3(polygon[j].X, polygon[j].Y, is3D ? polygon[j].Z : 0);
                            lock (lockObject)
                            {
                                triangulatedMesh.AddVertex(v, ref contour[j]);
                            }
                        }
                    }
                    else
                    {
                        var i = 0;
                        for (var j = polygon.Count - 1; j >= 0; j--)
                        {
                            var v = new Vec3(polygon[j].X, polygon[j].Y, is3D ? polygon[j].Z : 0);
                            lock (lockObject)
                            {
                                triangulatedMesh.AddVertex(v, ref contour[i]);
                            }
                            i++;
                        }
                    }
                    contours.Add(contour);
                }

                if (contours.Any())
                {
                    if (contours.Count == 1 && contours[0].Length == 3) //its a triangle just grab it
                    {
                        lock (lockObject)
                        {
                            triangulatedMesh.AddTriangle(contours[0][0].Data, contours[0][1].Data, contours[0][2].Data, faceId);
                        }
                        Interlocked.Increment(ref faceId);
                        //faceId++;
                    }
                    else    //it is multi-sided and may have holes
                    {
                        tess.AddContours(contours);

                        tess.Tessellate(WindingRule.EvenOdd, ElementType.Polygons, 3);
                        var faceIndices = new List<int>(tess.ElementCount * 3);
                        var elements = tess.Elements;
                        var contourVerts = tess.Vertices;
                        for (var j = 0; j < tess.ElementCount * 3; j++)
                        {
                            var idx = contourVerts[elements[j]].Data;
                            if (idx < 0) //WE HAVE INSERTED A POINT
                            {
                                //add it to the mesh
                                lock (lockObject)
                                {
                                    triangulatedMesh.AddVertex(contourVerts[elements[j]].Position, ref contourVerts[elements[j]]);
                                }
                            }
                            faceIndices.Add(contourVerts[elements[j]].Data);
                        }

                        if (faceIndices.Count > 0)
                        {
                            for (var j = 0; j < tess.ElementCount; j++)
                            {
                                var p1 = faceIndices[j * 3];
                                var p2 = faceIndices[j * 3 + 1];
                                var p3 = faceIndices[j * 3 + 2];
                                lock (lockObject)
                                {
                                    triangulatedMesh.AddTriangle(p1, p2, p3, faceId);
                                }
                            }
                            Interlocked.Increment(ref faceId);
                            //faceId++;
                        }
                    }
                }
            });

            triangulatedMesh.UnifyFaceOrientation(entityLabel);
            return triangulatedMesh;
        }

[andyward]

It feels like adding parallelism is probably dodging the issue here. And as you see you're only getting 25% improvement. Fundamentally I'd suggest it's an algorithm problem.

I did a bit of analysis with some small but relatively complex test models using BenchmarkDotNet. A majority of the time is down in the area Martin hinted at: XbimTriangulatedMesh.UnifyFaceOrientation() and in particular XbimTriangulatedMesh.BalanceNormals() - which are invoked by XbimTessellator.TriangulateFaces()

// * Summary *

BenchmarkDotNet v0.13.10, Windows 11 (10.0.22621.2715/22H2/2022Update/SunValley2)
AMD Ryzen 5 5600X, 1 CPU, 12 logical and 6 physical cores
.NET SDK 7.0.400
  [Host]     : .NET 6.0.21 (6.0.2123.36311), X64 RyuJIT AVX2
  Job-PJNTCV : .NET 6.0.21 (6.0.2123.36311), X64 RyuJIT AVX2

InvocationCount=1  UnrollFactor=1

Method	ifcFile	Mean	Error	StdDev	Ratio	RatioSD	Gen0	Gen1	Gen2	Allocated	Alloc Ratio
'Original Algorithm'	Basin(...)n.ifc [21]	321.03 us	6.411 us	6.583 us	1.00	0.00	20.0000	10.0000	-	393.24 KB	1.00
'No normal correction'	Basin(...)n.ifc [21]	123.40 us	2.432 us	5.337 us	0.39	0.01	10.0000	10.0000	-	199.07 KB	0.51
'No face correction'	Basin(...)n.ifc [21]	99.10 us	1.702 us	1.421 us	0.31	0.01	-	-	-	158.82 KB	0.40
'Original Algorithm'	IFC4T(...)x.ifc [27]	8,128.72 us	161.305 us	260.478 us	1.00	0.00	420.0000	180.0000	50.0000	6288.23 KB	1.00
'No normal correction'	IFC4T(...)x.ifc [27]	4,788.67 us	92.146 us	81.685 us	0.58	0.02	180.0000	90.0000	20.0000	2982.94 KB	0.47
'No face correction'	IFC4T(...)x.ifc [27]	4,525.77 us	90.146 us	160.235 us	0.56	0.03	140.0000	60.0000	10.0000	2348.18 KB	0.37

So it seems these 'fixup' routines are adding 50%+ to the execution time on complex triangulated meshes, and also generating a lot of allocations. For now I've added some optional switches to skip them. We need to review their effectiveness. Sadly there's not a lot of test coverage to help with refactoring

@christianstroh rather than share the session are you able to provide a model and we can do some further investigation? Free free to send via a fileshare app or OneDrive/GoogleDrive.

[christianstroh]

I'll give feedback about the model.

[christianstroh]

Unfortunately, our customer does not want to pass the ifc file on to third parties.

However, I noticed in the viewer that the model only has a single geometry, instead of individual objects that could be selected. Maybe the tessellation doesn't handle this well.

[andyward]

No problem. If it helps we can do an NDA -just email me (See my profile)

But you can take a look yourself:
Do you want to pull this branch I pushed which has the benchmarking integrated?

If you build it locally you can add your client model in the 'test class

I'd probably reduce Iterations down to 1 initially and see what it says. Maybe remove 'BasinTessellation.ifc' from the test run as it's very small.

To run the benchmarking just run the RunBenchmark.BAT script

[andyward]

However, I noticed in the viewer that the model only has a single geometry, instead of individual objects that could be selected.

I'm assuming it's a really complex triangulated item. Worth noting you can isolate a single item from a larger model using Xbim Xplorer's 'IFC Stripping' feature. Perhaps you can share it with us that way?

In the benchmarking I did there's a model with a single relatively complex tesselation (about 4000 vertices) - but this takes only 8ms to process:

Assuming your model must have something much more complex

[christianstroh]

Please excuse the late reply, I was on vacation for several weeks.

I'm afraid our customer won't go along with an NDA either.

The model consists of a single geometry with many pipes and valves. Maybe the tessellation of these curves is too detailed.

I'll try your branch.

[christianstroh]

I had to stop the program after several hours. Even with Iterations set to 1.

We are trying to generate an IFC file with such geometries. We may be able to reproduce the problem with this.

[andyward]

If it's taking hours for a single iteration, it sounds like one the following

1. An infinite loop bug somewhere in GE
2. An immensely complex boolean object
3. 100K of complex objects

If you're able to enable verbose logging it may shed light on what's going on and which element(s) are causing the performance issues

Are you able to extract the problem element using the approach I mentioned above? (The IFC Stripping feature in XbimXplorer) That will create an IFC with just a single element in it. In 95% of circumstance these complex meshes have come from an object library not the design team. You may even be able to find it. If you can locate the item publicly point me at it and we'll take a look using the publicly available data.

[christianstroh]

We will try to find out which object(s) are causing the long loading. My colleague knows about 3D modeling and will try to export only parts of the geometry. No single object immediately stands out as the culprit.