| 427 | constexpr size_t minTrisInPart = 32768; |
| 428 | |
| 429 | static MeshTopology fromTrianglesPar( const Triangulation & t, const BuildSettings & settings, ProgressCallback progressCb ) |
| 430 | { |
| 431 | MR_TIMER; |
| 432 | |
| 433 | // reserve enough elements for faces and vertices |
| 434 | //auto [maxFaceId, maxVertId] = computeMaxIds( tris ); |
| 435 | const auto maxVertId = findMaxVertId( t, settings.region ); |
| 436 | |
| 437 | // numParts shall not depend on hardware (e.g. on std::thread::hardware_concurrency()) to be repeatable on all hardware |
| 438 | const size_t numParts = std::min( ( t.size() + minTrisInPart - 1 ) / minTrisInPart, (size_t)64 ); |
| 439 | assert( numParts > 1 ); |
| 440 | MeshTopology res; |
| 441 | |
| 442 | const size_t vertsInPart = ( (int)maxVertId + numParts ) / numParts; |
| 443 | std::vector<MeshPiece> parts( numParts ); |
| 444 | |
| 445 | Timer timer("partition triangles"); |
| 446 | if ( progressCb && !progressCb( 0.33f ) ) |
| 447 | return {}; |
| 448 | FaceBitSet borderTris( t.size() ); // triangles having vertices in distinct parts |
| 449 | BitSetParallelForAll( borderTris, [&]( FaceId f ) |
| 450 | { |
| 451 | if ( settings.region && !settings.region->test( f ) ) |
| 452 | return; |
| 453 | const auto & vs = t[f]; |
| 454 | auto v0p = int( vs[0] / vertsInPart ); |
| 455 | auto v1p = int( vs[1] / vertsInPart ); |
| 456 | auto v2p = int( vs[2] / vertsInPart ); |
| 457 | if ( v0p == v1p && v0p == v2p ) |
| 458 | return; |
| 459 | borderTris.set( f ); |
| 460 | } ); |
| 461 | |
| 462 | timer.restart("parallel parts"); |
| 463 | if ( progressCb && !progressCb( 0.4f ) ) |
| 464 | return {}; |
| 465 | tbb::parallel_for( tbb::blocked_range<size_t>( 0, numParts, 1 ), [&]( const tbb::blocked_range<size_t> & range ) |
| 466 | { |
| 467 | assert( range.begin() + 1 == range.end() ); |
| 468 | for ( size_t myPartId = range.begin(); myPartId < range.end(); ++myPartId ) |
| 469 | { |
| 470 | MeshPiece part; |
| 471 | Triangulation partTriangulation; |
| 472 | BuildSettings partSettings{ .region = &part.rem, .allowNonManifoldEdge = settings.allowNonManifoldEdge }; |
| 473 | part.vmap.resize( vertsInPart ); |
| 474 | const VertId myBeginVert( myPartId * vertsInPart ); |
| 475 | const VertId myEndVert( ( myPartId + 1 ) * vertsInPart ); |
| 476 | for ( FaceId f{0}; f < t.size(); ++f ) |
| 477 | { |
| 478 | if ( settings.region && !settings.region->test( f ) ) |
| 479 | continue; |
| 480 | if ( borderTris.test( f ) ) |
| 481 | continue; |
| 482 | const auto & vs = t[f]; |
| 483 | if ( vs[0] < myBeginVert || vs[0] >= myEndVert ) |
| 484 | continue; |
| 485 | VertId v[3] = { |
| 486 | VertId( vs[0] % vertsInPart ), |
no test coverage detected