test_shape_poly_set_triangle_index.cpp

Go to the documentation of this file.

/*
 * This program source code file is part of KiCad, a free EDA CAD application.
 *
 * Copyright The KiCad Developers, see AUTHORS.txt for contributors.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <https://www.gnu.org/licenses/>.
 */

 
#include <boost/test/unit_test.hpp>
 
#include <limits>
#include <vector>
 
#include <geometry/shape_poly_set.h>
#include <geometry/shape_compound.h>
#include <geometry/shape_segment.h>
#include <geometry/shape_rect.h>
 
namespace
{

SHAPE_LINE_CHAIN MakeNgon( const VECTOR2I& aCentre, int aRadius, int aVertices )
{
    SHAPE_LINE_CHAIN chain;
 
    for( int ii = 0; ii < aVertices; ++ii )
    {
        double angle = 2.0 * M_PI * ii / aVertices;
        chain.Append( aCentre.x + KiROUND( aRadius * cos( angle ) ), aCentre.y + KiROUND( aRadius * sin( angle ) ) );
    }
 
    chain.SetClosed( true );
    return chain;
}
 

SHAPE_POLY_SET MakeBlob()
{
    SHAPE_POLY_SET poly;
    poly.AddOutline( MakeNgon( VECTOR2I( 0, 0 ), 1000000, 180 ) );
    poly.AddHole( MakeNgon( VECTOR2I( -400000, 0 ), 150000, 60 ) );
    poly.AddHole( MakeNgon( VECTOR2I( 400000, 250000 ), 120000, 60 ) );
    poly.CacheTriangulation();
    return poly;
}
 

struct PROBE_RESULT
{
    bool collides;
    int  actual;
 
    bool operator==( const PROBE_RESULT& aOther ) const
    {
        return collides == aOther.collides && actual == aOther.actual;
    }
};
 
 
std::ostream& operator<<( std::ostream& aStream, const PROBE_RESULT& aResult )
{
    return aStream << "{ collides=" << aResult.collides << " actual=" << aResult.actual << " }";
}
 
 
PROBE_RESULT Probe( const SHAPE_POLY_SET& aPoly, const SHAPE& aShape, int aClearance )
{
    PROBE_RESULT r;
    r.actual = -1;
    r.collides = aPoly.Collide( &aShape, aClearance, &r.actual, nullptr );
    return r;
}
 

PROBE_RESULT ReferenceScan( const SHAPE_POLY_SET& aPoly, const SHAPE& aShape, int aClearance )
{
    PROBE_RESULT r;
    r.collides = false;
    r.actual = -1;
 
    int best = std::numeric_limits<int>::max();
 
    for( unsigned ii = 0; ii < aPoly.TriangulatedPolyCount(); ++ii )
    {
        const SHAPE_POLY_SET::TRIANGULATED_POLYGON* tpoly = aPoly.TriangulatedPolygon( ii );
 
        for( const SHAPE_POLY_SET::TRIANGULATED_POLYGON::TRI& tri : tpoly->Triangles() )
        {
            int triActual;
 
            if( aShape.Collide( &tri, aClearance, &triActual, nullptr ) )
                best = std::min( best, triActual );
        }
    }
 
    if( best < std::numeric_limits<int>::max() )
    {
        r.collides = true;
        r.actual = std::max( 0, best );
    }
 
    return r;
}
 

bool ProbeBool( const SHAPE_POLY_SET& aPoly, const SHAPE& aShape, int aClearance )
{
    return aPoly.Collide( &aShape, aClearance );
}
 

bool ReferenceScanBool( const SHAPE_POLY_SET& aPoly, const SHAPE& aShape, int aClearance )
{
    for( unsigned ii = 0; ii < aPoly.TriangulatedPolyCount(); ++ii )
    {
        const SHAPE_POLY_SET::TRIANGULATED_POLYGON* tpoly = aPoly.TriangulatedPolygon( ii );
 
        for( const SHAPE_POLY_SET::TRIANGULATED_POLYGON::TRI& tri : tpoly->Triangles() )
        {
            if( aShape.Collide( &tri, aClearance ) )
                return true;
        }
    }
 
    return false;
}
 

void WarmAndRequireIndexed( SHAPE_POLY_SET& aPoly )
{
    SHAPE_RECT warmup( VECTOR2I( 0, 0 ), 1000, 1000 );
    aPoly.Collide( &warmup, 0 );
 
    BOOST_REQUIRE( aPoly.TriangulatedPolyCount() > 0 );
    BOOST_REQUIRE( aPoly.TriangulationIndex() != nullptr );
}
 

const std::vector<VECTOR2I> g_probes = {
    VECTOR2I( 0, 0 ),            // deep inside
    VECTOR2I( 999000, 0 ),       // just inside the outline
    VECTOR2I( 1001000, 0 ),      // just outside the outline
    VECTOR2I( -400000, 0 ),      // centre of hole 1
    VECTOR2I( -250000, 0 ),      // just outside hole 1
    VECTOR2I( 400000, 250000 ),  // centre of hole 2
    VECTOR2I( 3000000, 3000000 ) // far away
};
 
} // namespace
 
 
BOOST_AUTO_TEST_SUITE( SPSTriangleIndex )
 
 

BOOST_AUTO_TEST_CASE( FirstColdCollideBuildsTheIndex )
{
    SHAPE_POLY_SET poly;
    poly.AddOutline( MakeNgon( VECTOR2I( 0, 0 ), 1000000, 180 ) );
    poly.AddHole( MakeNgon( VECTOR2I( -400000, 0 ), 150000, 60 ) );
    poly.AddHole( MakeNgon( VECTOR2I( 400000, 250000 ), 120000, 60 ) );
 
    SHAPE_RECT probe( VECTOR2I( 0, 0 ), 1000, 1000 );
    poly.Collide( &probe, 0 );
 
    BOOST_REQUIRE( poly.TriangulatedPolyCount() > 0 );
    BOOST_REQUIRE( poly.TriangulationIndex() != nullptr );
}
 

BOOST_AUTO_TEST_CASE( TriPointersSurviveMove )
{
    SHAPE_POLY_SET poly = MakeBlob();
 
    WarmAndRequireIndexed( poly );
 
    std::vector<const SHAPE*> before;
    poly.GetIndexableSubshapes( before );
    BOOST_REQUIRE( before.size() > 64 );
 
    std::vector<VECTOR2I> firstVertexBefore;
 
    for( const SHAPE* s : before )
        firstVertexBefore.push_back( static_cast<const SHAPE_LINE_CHAIN_BASE*>( s )->GetPoint( 0 ) );
 
    const VECTOR2I delta( 123456, -654321 );
    poly.Move( delta );
 
    std::vector<const SHAPE*> after;
    poly.GetIndexableSubshapes( after );
 
    BOOST_REQUIRE_EQUAL( before.size(), after.size() );
 
    for( size_t ii = 0; ii < before.size(); ++ii )
    {
        // Same objects, not clones: a DRC_RTREE built before the Move must stay valid.
        BOOST_CHECK_EQUAL( (const void*) before[ii], (const void*) after[ii] );
 
        VECTOR2I moved = static_cast<const SHAPE_LINE_CHAIN_BASE*>( after[ii] )->GetPoint( 0 );
        BOOST_CHECK_EQUAL( moved, firstVertexBefore[ii] + delta );
    }
}
 

BOOST_AUTO_TEST_CASE( CompoundNearMissNotPruned )
{
    SHAPE_POLY_SET poly = MakeBlob();
 
    // Two segments forming a compound, sitting a known distance outside the outline.
    const int      gap = 20000;
    const VECTOR2I a( 1000000 + gap, -100000 );
    const VECTOR2I b( 1000000 + gap, 100000 );
 
    SHAPE_COMPOUND compound;
    compound.AddShape( new SHAPE_SEGMENT( a, b, 0 ) );
    compound.AddShape( new SHAPE_SEGMENT( b, b + VECTOR2I( 50000, 0 ), 0 ) );
 
    // Comfortably clear.
    BOOST_CHECK_EQUAL( Probe( poly, compound, gap / 2 ), ReferenceScan( poly, compound, gap / 2 ) );
 
    // Clearance large enough that the near-miss triangles matter: a pruned candidate set
    // would report no collision here while the full scan reports one.
    BOOST_CHECK_EQUAL( Probe( poly, compound, gap * 4 ), ReferenceScan( poly, compound, gap * 4 ) );
 
    BOOST_CHECK( Probe( poly, compound, gap * 4 ).collides );
}
 

BOOST_AUTO_TEST_CASE( MinDistanceMatchesFullScan )
{
    SHAPE_POLY_SET poly = MakeBlob();
 
    const std::vector<std::pair<VECTOR2I, int>> cases = {
        { VECTOR2I( 1000000, 0 ), 0 },      // on the outline, between two triangles
        { VECTOR2I( 1010000, 0 ), 10000 },  // exactly at clearance distance
        { VECTOR2I( 1010000, 0 ), 9999 },   // one IU inside
        { VECTOR2I( 1010000, 0 ), 10001 },  // one IU outside
        { VECTOR2I( -400000, 0 ), 100000 }, // inside a hole, reaching its rim
        { VECTOR2I( 0, 999000 ), 5000 }     // near the outline on another axis
    };
 
    for( const auto& [pt, clearance] : cases )
    {
        SHAPE_RECT probe( pt, 1, 1 );
        BOOST_CHECK_EQUAL( Probe( poly, probe, clearance ), ReferenceScan( poly, probe, clearance ) );
    }
}
 

BOOST_AUTO_TEST_CASE( SubThresholdPolygonMatchesFullScan )
{
    SHAPE_POLY_SET poly;
    poly.AddOutline( MakeNgon( VECTOR2I( 0, 0 ), 1000000, 8 ) ); // 8 vertices -> ~6 triangles
    poly.CacheTriangulation();
 
    size_t triangles = 0;
 
    for( unsigned ii = 0; ii < poly.TriangulatedPolyCount(); ++ii )
        triangles += poly.TriangulatedPolygon( ii )->GetTriangleCount();
 
    // If this ever exceeds the threshold (RTREE_THRESHOLD, 32) the case stops testing what it
    // claims to.
    BOOST_REQUIRE( triangles < 32 );
 
    const std::vector<VECTOR2I> probes = { VECTOR2I( 0, 0 ), VECTOR2I( 900000, 0 ), VECTOR2I( 1100000, 0 ),
                                           VECTOR2I( 0, 900000 ) };
 
    for( const VECTOR2I& pt : probes )
    {
        SHAPE_RECT probe( pt, 1000, 1000 );
        BOOST_CHECK_EQUAL( Probe( poly, probe, 0 ), ReferenceScan( poly, probe, 0 ) );
        BOOST_CHECK_EQUAL( ProbeBool( poly, probe, 0 ), ReferenceScanBool( poly, probe, 0 ) );
    }
}
 

BOOST_AUTO_TEST_CASE( CheckIndexDropped )
{
    // Move: the index is dropped, and the rebuilt one must describe the new positions.
    SHAPE_POLY_SET poly = MakeBlob();
    WarmAndRequireIndexed( poly );
 
    const VECTOR2I delta( 5000000, 0 );
    poly.Move( delta );
    BOOST_CHECK( poly.TriangulationIndex() == nullptr );
 
    for( const VECTOR2I& pt : g_probes )
    {
        SHAPE_RECT shifted( pt + delta, 1000, 1000 );
        BOOST_CHECK_EQUAL( Probe( poly, shifted, 0 ), ReferenceScan( poly, shifted, 0 ) );
        BOOST_CHECK_EQUAL( ProbeBool( poly, shifted, 0 ), ReferenceScanBool( poly, shifted, 0 ) );
 
        // The old location must now be empty.
        SHAPE_RECT stale( pt, 1000, 1000 );
        BOOST_CHECK_EQUAL( Probe( poly, stale, 0 ), ReferenceScan( poly, stale, 0 ) );
    }
 
    // RemoveAllContours discards the triangles outright.
    poly = MakeBlob();
    WarmAndRequireIndexed( poly );
    poly.RemoveAllContours();
    BOOST_CHECK( poly.TriangulationIndex() == nullptr );
 
    // Re-triangulating replaces every polygon, so the index must not survive it either.
    poly = MakeBlob();
    WarmAndRequireIndexed( poly );
    poly.AddHole( MakeNgon( VECTOR2I( 0, -500000 ), 100000, 60 ) );
    poly.CacheTriangulation();
    BOOST_CHECK( poly.TriangulationIndex() == nullptr );
 
    for( const VECTOR2I& pt : g_probes )
    {
        SHAPE_RECT probe( pt, 1000, 1000 );
        BOOST_CHECK_EQUAL( Probe( poly, probe, 0 ), ReferenceScan( poly, probe, 0 ) );
        BOOST_CHECK_EQUAL( ProbeBool( poly, probe, 0 ), ReferenceScanBool( poly, probe, 0 ) );
    }
 
    // The new hole must read as empty.
    SHAPE_RECT inNewHole( VECTOR2I( 0, -500000 ), 1000, 1000 );
    BOOST_CHECK_EQUAL( Probe( poly, inNewHole, 0 ), ReferenceScan( poly, inNewHole, 0 ) );
 
    // Copy assignment, against a blob far from the first.
    SHAPE_POLY_SET target = MakeBlob();
    WarmAndRequireIndexed( target );
 
    SHAPE_POLY_SET other;
    other.AddOutline( MakeNgon( VECTOR2I( 8000000, 8000000 ), 900000, 180 ) );
    other.CacheTriangulation();
 
    target = other;
 
    BOOST_REQUIRE( target.TriangulatedPolyCount() > 0 );
    BOOST_CHECK( target.TriangulationIndex() == nullptr );
 
    const std::vector<VECTOR2I> probes = {
        VECTOR2I( 8000000, 8000000 ), // inside the new geometry
        VECTOR2I( 8890000, 8000000 ), // just inside its edge
        VECTOR2I( 8910000, 8000000 ), // just outside its edge
        VECTOR2I( 0, 0 )              // where the OLD geometry used to be
    };
 
    for( const VECTOR2I& pt : probes )
    {
        SHAPE_RECT probe( pt, 1000, 1000 );
        BOOST_CHECK_EQUAL( Probe( target, probe, 0 ), ReferenceScan( target, probe, 0 ) );
        BOOST_CHECK_EQUAL( ProbeBool( target, probe, 0 ), ReferenceScanBool( target, probe, 0 ) );
    }
}
 
 
BOOST_AUTO_TEST_SUITE_END()