Performance degradation if using linear cell complex with surface mesh

[Supranaturaler]

Issue Details

This is really weired. If I use linear cell complex without surface mesh (ie: comment line 49), the traversing of linear cell complex costs about 2s.

However, if I uncomment line 49, the time increases to 10s, about 5 times degradation. I guess some configurations in surface mesh may have effect on linear cell complex. But I can't figure out the place. Plz help!

Source Code

#include "CGAL/Exact_predicates_exact_constructions_kernel.h"
typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
typedef Kernel::Point_3 Point_3;

#include "CGAL/Linear_cell_complex_for_combinatorial_map.h"
struct VertexAttribute
{
    int vertexID = -1;
};

struct EdgeAttribute
{
    int edgeID = -1;
};

struct FaceAttribute
{
    int faceID = -1;
};

struct VolumeAttribute
{
    int volumeID = -1;
};

struct LCCItem
{
    template <class CMap>
    struct Dart_wrapper
    {
        typedef CGAL::Cell_attribute_with_point<CMap, VertexAttribute, CGAL::Tag_true> VertexCellAttribute;
        typedef CGAL::Cell_attribute_with_point<CMap, EdgeAttribute, CGAL::Tag_true> EdgeCellAttribute;
        typedef CGAL::Cell_attribute<CMap, FaceAttribute, CGAL::Tag_true> FaceCellAttribute;
        typedef CGAL::Cell_attribute<CMap, VolumeAttribute, CGAL::Tag_true> VolumeCellAttribute;
        typedef std::tuple<VertexCellAttribute, EdgeCellAttribute, FaceCellAttribute, VolumeCellAttribute> Attributes;
    };
};

typedef CGAL::Linear_cell_complex_traits<3, Kernel> LCCTraits;
typedef CGAL::Linear_cell_complex_for_combinatorial_map<3, 3, LCCTraits, LCCItem> LCCMesh;

#include "CGAL/Linear_cell_complex_constructors.h"
typedef CGAL::Linear_cell_complex_incremental_builder_3<LCCMesh> LCCBuilder;

#include "CGAL/Surface_mesh.h"

int main(int argc, char* argv[])
{
    //CGAL::Surface_mesh<Point_3> surfaceMesh;
    int size = 100;
    int xSize = size, ySize = size, zSize = size;
    std::vector<double> vecX, vecY, vecZ;
    for (size_t i = 0; i < size; ++i)
    {
        vecX.push_back(i);
        vecY.push_back(i);
        vecZ.push_back(i);
    }

    LCCMesh lccMesh;
    LCCBuilder lccBuilder(lccMesh);

    for (int i = 0; i < size; ++i)
    {
        for (int j = 0; j < size; ++j)
        {
            for (int k = 0; k < size; ++k)
            {
                lccBuilder.add_vertex(Point_3(vecX[i], vecY[j], vecZ[k]));
            }
        }
    }

    int startIndex = 0;
    for (int i = 0; i < xSize; ++i)
    {
        for (int j = 0; j < ySize; ++j)
        {
            for (int k = 0; k < zSize; ++k)
            {
                if (i != xSize - 1 && j != ySize - 1 && k != zSize - 1)
                {
                    lccBuilder.begin_surface();
                    int index1 = startIndex;
                    int index2 = startIndex + zSize;
                    int index3 = startIndex + ySize * zSize + zSize;
                    int index4 = startIndex + ySize * zSize;
                    int index5 = startIndex + ySize * zSize + 1;
                    int index6 = startIndex + 1;
                    int index7 = startIndex + zSize + 1;
                    int index8 = startIndex + ySize * zSize + zSize + 1;

                    lccBuilder.begin_facet();
                    lccBuilder.add_vertex_to_facet(index1);
                    lccBuilder.add_vertex_to_facet(index2);
                    lccBuilder.add_vertex_to_facet(index3);
                    lccBuilder.add_vertex_to_facet(index4);
                    lccBuilder.end_facet();

                    lccBuilder.begin_facet();
                    lccBuilder.add_vertex_to_facet(index5);
                    lccBuilder.add_vertex_to_facet(index8);
                    lccBuilder.add_vertex_to_facet(index7);
                    lccBuilder.add_vertex_to_facet(index6);
                    lccBuilder.end_facet();

                    lccBuilder.begin_facet();
                    lccBuilder.add_vertex_to_facet(index1);
                    lccBuilder.add_vertex_to_facet(index4);
                    lccBuilder.add_vertex_to_facet(index5);
                    lccBuilder.add_vertex_to_facet(index6);
                    lccBuilder.end_facet();

                    lccBuilder.begin_facet();
                    lccBuilder.add_vertex_to_facet(index3);
                    lccBuilder.add_vertex_to_facet(index2);
                    lccBuilder.add_vertex_to_facet(index7);
                    lccBuilder.add_vertex_to_facet(index8);
                    lccBuilder.end_facet();

                    lccBuilder.begin_facet();
                    lccBuilder.add_vertex_to_facet(index5);
                    lccBuilder.add_vertex_to_facet(index4);
                    lccBuilder.add_vertex_to_facet(index3);
                    lccBuilder.add_vertex_to_facet(index8);
                    lccBuilder.end_facet();

                    lccBuilder.begin_facet();
                    lccBuilder.add_vertex_to_facet(index1);
                    lccBuilder.add_vertex_to_facet(index6);
                    lccBuilder.add_vertex_to_facet(index7);
                    lccBuilder.add_vertex_to_facet(index2);
                    lccBuilder.end_facet();

                    lccBuilder.end_surface();
                }

                startIndex++;
            }
        }
    }

    std::chrono::high_resolution_clock::time_point startTime = std::chrono::high_resolution_clock::now();

    for (LCCMesh::One_dart_per_cell_range<3>::iterator volumeIter(lccMesh.one_dart_per_cell<3>().begin()),
        volumeEndIter(lccMesh.one_dart_per_cell<3>().end()); volumeIter != volumeEndIter; ++volumeIter)
    {
        if (lccMesh.attribute<3>(volumeIter) == nullptr)
        {
            lccMesh.set_attribute<3>(volumeIter, lccMesh.create_attribute<3>());
        }

        lccMesh.info<3>(volumeIter).volumeID = 0;
    }

    std::chrono::high_resolution_clock::time_point endTime = std::chrono::high_resolution_clock::now();
    std::chrono::milliseconds elapsedTime = std::chrono::duration_cast<std::chrono::milliseconds>(endTime - startTime);
    std::cout << "traverse One_dart_per_cell_range, total cost: " << elapsedTime.count() * 1E-3 << std::endl;

    return EXIT_SUCCESS;
}

Environment

• Operating system (Windows/Mac/Linux, 32/64 bits): Windows 11 home basic 64 bits
• Compiler: MSVC-2019-Community
• Release or debug mode: Release
• Specific flags used (if any):
• CGAL version: CGAL-5.4
• Boost version: boost_1_78_0
• Other libraries versions if used (Eigen, TBB, etc.):

[gdamiand]

This is indeed really weird !! I don't understand why creating an empty surface mesh increase the traversal time ! Maybe a cache effect ?

I tested the code, and observe also a degradation, but on my system it is very small: 0.7s to 0.8s (thus 1.15 times degradation).

A last comment: you can replace the loop for (LCCMesh::One_dart_per_cell_range<3>::iterator volumeIter(lccMesh.one_dart_per_cell<3>().begin()), volumeEndIter(lccMesh.one_dart_per_cell<3>().end()); volumeIter != volumeEndIter; ++volumeIter)

by for (LCCMesh::Dart_range::iterator volumeIter(lccMesh.darts().begin()), volumeEndIter(lccMesh.darts().end()); volumeIter != volumeEndIter; ++volumeIter)

Indeed, since in the loop you test if (lccMesh.attribute<3>(volumeIter) == nullptr), you can iterate through all the darts, and only for the first dart of a new volume this test will be true (or if you keep your version, you can remove the test).

This new version is faster.

[Supranaturaler]

It's acceptable to range between 0.7~0.8s. But 5 times degradation, it's hard to explain. I find this usually occurs when I run the program using visual studio. If I run the program alone, the degradation is small, but still occurs once or twice. Maybe I should do some more tests.

[sloriot]

Are you using the Ceres library?

[Supranaturaler]

Are you using the Ceres library?

I have never used this library