polygon_2d.cpp File Reference

#include "polygon_2d.h"
#include "../ray.h"
#include <wx/debug.h>

Go to the source code of this file.

Macros
#define	MAX_NR_DIVISIONS   96

Typedefs
typedef std::vector< SFVEC2F >	KF_POINTS

Functions
static bool	polygon_IsPointInside (const SEGMENTS &aSegments, const SFVEC2F &aPoint)
static bool	intersect (const SEGMENT_WITH_NORMALS &aSeg, const SFVEC2F &aStart, const SFVEC2F &aEnd)
static void	extractPathsFrom (const SEGMENTS_WIDTH_NORMALS &aSegList, const BBOX_2D &aBBox, SEGMENTS_WIDTH_NORMALS &aOutSegThatIntersect)
static void	polygon_Convert (const SHAPE_LINE_CHAIN &aPath, SEGMENTS &aOutSegment, float aBiuTo3dUnitsScale)
void	ConvertPolygonToBlocks (const SHAPE_POLY_SET &aMainPath, CONTAINER_2D_BASE &aDstContainer, float aBiuTo3dUnitsScale, float aDivFactor, const BOARD_ITEM &aBoardItem, int aPolyIndex)
	Use a polygon in the format of the ClipperLib::Path and process it and create multiple 2d objects (POLYGON_2D and DUMMY_BLOCK_2D) that can be used to represent this polygon area. More...

Macro Definition Documentation

MAX_NR_DIVISIONS

#define MAX_NR_DIVISIONS   96

Definition at line 270 of file polygon_2d.cpp.

Typedef Documentation

KF_POINTS

typedef std::vector<SFVEC2F> KF_POINTS

Definition at line 268 of file polygon_2d.cpp.

Function Documentation

ConvertPolygonToBlocks()

void ConvertPolygonToBlocks	(	const SHAPE_POLY_SET &	aMainPath,
		CONTAINER_2D_BASE &	aDstContainer,
		float	aBiuTo3dUnitsScale,
		float	aDivFactor,
		const BOARD_ITEM &	aBoardItem,
		int	aPolyIndex
	)

Use a polygon in the format of the ClipperLib::Path and process it and create multiple 2d objects (POLYGON_2D and DUMMY_BLOCK_2D) that can be used to represent this polygon area.

Parameters

aMainPath	the polygon are that was converted from the pcb board
aDstContainer	the destination container to put the created sub blocks
aBiuTo3dUnitsScale	the rendering target 3d scale
aDivFactor	a division factor (in 3Dunits) to divide the polygon plane, 0.0f will use the internal polygon segm statistics

Definition at line 378 of file polygon_2d.cpp.

{
    // Get the path
    wxASSERT( aPolyIndex < aMainPath.OutlineCount() );

    const SHAPE_LINE_CHAIN& path = aMainPath.COutline( aPolyIndex );

    BOX2I pathBounds = path.BBox();

    // Convert the points to segments class
    BBOX_2D bbox;
    bbox.Reset();

    // Contains the main list of segments and each segment normal interpolated
    SEGMENTS_WIDTH_NORMALS segments_and_normals;

    // Contains a closed polygon used to calc if points are inside
    SEGMENTS segments;

    segments_and_normals.reserve( path.PointCount() );
    segments.reserve( path.PointCount() );

    SFVEC2F prevPoint;

    for( int i = 0; i < path.PointCount(); i++ )
    {
        const VECTOR2I& a = path.CPoint( i );

        const SFVEC2F point( (float) ( a.x ) * aBiuTo3dUnitsScale,
                             (float) ( -a.y ) * aBiuTo3dUnitsScale );

        // Only add points that are not coincident
        if( ( i == 0 ) || ( fabs( prevPoint.x - point.x ) > FLT_EPSILON )
          || ( fabs( prevPoint.y - point.y ) > FLT_EPSILON ) )
        {
            prevPoint = point;

            bbox.Union( point );

            SEGMENT_WITH_NORMALS sn;
            sn.m_Start = point;
            segments_and_normals.push_back( sn );

            POLYSEGMENT ps;
            ps.m_Start = point;
            segments.push_back( ps );
        }
    }

    bbox.ScaleNextUp();

    // Calc the slopes, normals and some statistics about this polygon
    unsigned int i;
    unsigned int j = segments_and_normals.size() - 1;

    // Temporary normal to the segment, it will later be used for interpolation
    std::vector<SFVEC2F> tmpSegmentNormals;
    tmpSegmentNormals.resize( segments_and_normals.size() );

    float medOfTheSquaresSegmentLength = 0.0f;

#ifdef PRINT_STATISTICS_3D_VIEWER
    float minLength = FLT_MAX;
#endif

    for( i = 0; i < segments_and_normals.size(); j = i++ )
    {
        const SFVEC2F slope = segments_and_normals[j].m_Start - segments_and_normals[i].m_Start;

        segments_and_normals[i].m_Precalc_slope = slope;

        // Calculate constants for each segment
        segments[i].m_inv_JY_minus_IY =
                1.0f / ( segments_and_normals[j].m_Start.y - segments_and_normals[i].m_Start.y );

        segments[i].m_JX_minus_IX =
                ( segments_and_normals[j].m_Start.x - segments_and_normals[i].m_Start.x );

        // The normal orientation expect a fixed polygon orientation (!TODO: which one?)
        //tmpSegmentNormals[i] = glm::normalize( SFVEC2F( -slope.y, +slope.x ) );
        tmpSegmentNormals[i] = glm::normalize( SFVEC2F( slope.y, -slope.x ) );

        const float length = slope.x * slope.x + slope.y * slope.y;

#ifdef PRINT_STATISTICS_3D_VIEWER
        if( length < minLength )
            minLength = length;
#endif

        medOfTheSquaresSegmentLength += length;
    }

#ifdef PRINT_STATISTICS_3D_VIEWER
    float minSegmentLength = sqrt( minLength );
#endif

    // This calc an approximation of medium lengths, that will be used to calc
    // the size of the division.
    medOfTheSquaresSegmentLength /= segments_and_normals.size();
    medOfTheSquaresSegmentLength = sqrt( medOfTheSquaresSegmentLength );

    // Compute the normal interpolation
    // If calculate the dot between the segments, if they are above/below some
    // threshold it will not interpolated it (ex: if you are in a edge corner
    // or in a smooth transaction)
    j = segments_and_normals.size() - 1;

    for( i = 0; i < segments_and_normals.size(); j = i++ )
    {
        const SFVEC2F normalBeforeSeg = tmpSegmentNormals[j];
        const SFVEC2F normalSeg       = tmpSegmentNormals[i];
        const SFVEC2F normalAfterSeg  = tmpSegmentNormals[( i + 1 ) % segments_and_normals.size()];

        const float dotBefore = glm::dot( normalBeforeSeg, normalSeg );
        const float dotAfter  = glm::dot( normalAfterSeg, normalSeg );

        if( dotBefore < 0.7f )
            segments_and_normals[i].m_Normals.m_Start = normalSeg;
        else
            segments_and_normals[i].m_Normals.m_Start =
                    glm::normalize( ( normalBeforeSeg * dotBefore ) + normalSeg );

        if( dotAfter < 0.7f )
            segments_and_normals[i].m_Normals.m_End = normalSeg;
        else
            segments_and_normals[i].m_Normals.m_End =
                    glm::normalize( ( normalAfterSeg * dotAfter ) + normalSeg );
    }

    SFVEC2UI grid_divisions;

    if( aDivFactor < 0.0f )
    {
        grid_divisions = SFVEC2UI( 1 );
    }
    else
    {
        if( aDivFactor <= FLT_EPSILON )
            aDivFactor = medOfTheSquaresSegmentLength;

        grid_divisions.x = (unsigned int) ( ( bbox.GetExtent().x / aDivFactor ) );
        grid_divisions.y = (unsigned int) ( ( bbox.GetExtent().y / aDivFactor ) );

        grid_divisions = glm::clamp(
                grid_divisions, SFVEC2UI( 1, 1 ), SFVEC2UI( MAX_NR_DIVISIONS, MAX_NR_DIVISIONS ) );
    }

    // Calculate the steps advance of the grid
    SFVEC2F blockAdvance;

    blockAdvance.x = bbox.GetExtent().x / (float) grid_divisions.x;
    blockAdvance.y = bbox.GetExtent().y / (float) grid_divisions.y;

    wxASSERT( blockAdvance.x > 0.0f );
    wxASSERT( blockAdvance.y > 0.0f );

    const int leftToRight_inc = ( pathBounds.GetRight() - pathBounds.GetLeft() ) / grid_divisions.x;

    const int topToBottom_inc = ( pathBounds.GetBottom() - pathBounds.GetTop() ) / grid_divisions.y;

    // Statistics
    unsigned int stats_n_empty_blocks       = 0;
    unsigned int stats_n_dummy_blocks       = 0;
    unsigned int stats_n_poly_blocks        = 0;
    unsigned int stats_sum_size_of_polygons = 0;

    // Step by each block of a grid trying to extract segments and create polygon blocks
    int   topToBottom = pathBounds.GetTop();
    float blockY      = bbox.Max().y;

    for( unsigned int iy = 0; iy < grid_divisions.y; iy++ )
    {
        int   leftToRight = pathBounds.GetLeft();
        float blockX      = bbox.Min().x;

        for( unsigned int ix = 0; ix < grid_divisions.x; ix++ )
        {
            BBOX_2D blockBox( SFVEC2F( blockX, blockY - blockAdvance.y ),
                              SFVEC2F( blockX + blockAdvance.x, blockY ) );

            // Make the box large to it will catch (intersect) the edges
            blockBox.ScaleNextUp();
            blockBox.ScaleNextUp();
            blockBox.ScaleNextUp();

            SEGMENTS_WIDTH_NORMALS extractedSegments;

            extractPathsFrom( segments_and_normals, blockBox, extractedSegments );

            if( extractedSegments.empty() )
            {

                SFVEC2F p1( blockBox.Min().x, blockBox.Min().y );
                SFVEC2F p2( blockBox.Max().x, blockBox.Min().y );
                SFVEC2F p3( blockBox.Max().x, blockBox.Max().y );
                SFVEC2F p4( blockBox.Min().x, blockBox.Max().y );

                if( polygon_IsPointInside( segments, p1 ) || polygon_IsPointInside( segments, p2 )
                  || polygon_IsPointInside( segments, p3 )
                  || polygon_IsPointInside( segments, p4 ) )
                {
                    // In this case, the segments are not intersecting the
                    // polygon, so it means that if any point is inside it,
                    // then all other are inside the polygon.
                    // This is a full bbox inside, so add a dummy box
                    aDstContainer.Add( new DUMMY_BLOCK_2D( blockBox, aBoardItem ) );
                    stats_n_dummy_blocks++;
                }
                else
                {
                    // Points are outside, so this block completely missed the polygon
                    // In this case, no objects need to be added
                    stats_n_empty_blocks++;
                }
            }
            else
            {
                // At this point, the borders of polygon were intersected by the
                // bounding box, so we must calculate a new polygon that will
                // close that small block.
                // This block will be used to calculate if points are inside
                // the (sub block) polygon.

                SHAPE_POLY_SET subBlockPoly;

                SHAPE_LINE_CHAIN sb = SHAPE_LINE_CHAIN( { VECTOR2I( leftToRight, topToBottom ),
                        VECTOR2I( leftToRight + leftToRight_inc, topToBottom ),
                        VECTOR2I( leftToRight + leftToRight_inc, topToBottom + topToBottom_inc ),
                        VECTOR2I( leftToRight, topToBottom + topToBottom_inc ) } );

                //sb.Append( leftToRight, topToBottom );
                sb.SetClosed( true );

                subBlockPoly.AddOutline( sb );

                // We need here a strictly simple polygon with outlines and holes
                SHAPE_POLY_SET solution;
                solution.BooleanIntersection( aMainPath, subBlockPoly,
                                              SHAPE_POLY_SET::PM_STRICTLY_SIMPLE );

                OUTERS_AND_HOLES outersAndHoles;

                outersAndHoles.m_Holes.clear();
                outersAndHoles.m_Outers.clear();

                for( int idx = 0; idx < solution.OutlineCount(); idx++ )
                {
                    const SHAPE_LINE_CHAIN& outline = solution.Outline( idx );

                    SEGMENTS solutionSegment;

                    polygon_Convert( outline, solutionSegment, aBiuTo3dUnitsScale );
                    outersAndHoles.m_Outers.push_back( solutionSegment );

                    stats_sum_size_of_polygons += solutionSegment.size();

                    for( int holeIdx = 0; holeIdx < solution.HoleCount( idx ); holeIdx++ )
                    {
                        const SHAPE_LINE_CHAIN& hole = solution.Hole( idx, holeIdx );

                        polygon_Convert( hole, solutionSegment, aBiuTo3dUnitsScale );
                        outersAndHoles.m_Holes.push_back( solutionSegment );
                        stats_sum_size_of_polygons += solutionSegment.size();
                    }
                }

                if( !outersAndHoles.m_Outers.empty() )
                {
                    aDstContainer.Add( new POLYGON_2D( extractedSegments, outersAndHoles,
                                                       aBoardItem ) );
                    stats_n_poly_blocks++;
                }
            }

            blockX += blockAdvance.x;
            leftToRight += leftToRight_inc;
        }

        blockY -= blockAdvance.y;
        topToBottom += topToBottom_inc;
    }
}

References CONTAINER_2D_BASE::Add(), SHAPE_POLY_SET::AddOutline(), SHAPE_POLY_SET::BooleanIntersection(), SHAPE_POLY_SET::COutline(), extractPathsFrom(), BOX2< Vec >::GetBottom(), BBOX_2D::GetExtent(), BOX2< Vec >::GetLeft(), BOX2< Vec >::GetRight(), BOX2< Vec >::GetTop(), SHAPE_POLY_SET::Hole(), SHAPE_POLY_SET::HoleCount(), OUTERS_AND_HOLES::m_Holes, OUTERS_AND_HOLES::m_Outers, POLYSEGMENT::m_Start, SEGMENT_WITH_NORMALS::m_Start, BBOX_2D::Max(), MAX_NR_DIVISIONS, BBOX_2D::Min(), SHAPE_POLY_SET::Outline(), SHAPE_POLY_SET::OutlineCount(), path, SHAPE_POLY_SET::PM_STRICTLY_SIMPLE, polygon_Convert(), polygon_IsPointInside(), BBOX_2D::Reset(), BBOX_2D::ScaleNextUp(), SHAPE_LINE_CHAIN::SetClosed(), BBOX_2D::Union(), VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by RENDER_3D_RAYTRACE::Reload().

extractPathsFrom()

static void extractPathsFrom ( const SEGMENTS_WIDTH_NORMALS &  aSegList, const BBOX_2D &  aBBox, SEGMENTS_WIDTH_NORMALS &  aOutSegThatIntersect  )

static

Definition at line 305 of file polygon_2d.cpp.

{
    wxASSERT( aSegList.size() >= 3 );

    unsigned int i;
    unsigned int j = aSegList.size() - 1;

    const SFVEC2F p1( aBBox.Min().x, aBBox.Min().y );
    const SFVEC2F p2( aBBox.Max().x, aBBox.Min().y );
    const SFVEC2F p3( aBBox.Max().x, aBBox.Max().y );
    const SFVEC2F p4( aBBox.Min().x, aBBox.Max().y );

    aOutSegThatIntersect.clear();

    for( i = 0; i < aSegList.size(); j = i++ )
    {
        if( aBBox.Inside( aSegList[i].m_Start ) || aBBox.Inside( aSegList[j].m_Start ) )
        {
            // if the segment points are inside the bounding box then this
            // segment is touching the bbox.
            aOutSegThatIntersect.push_back( aSegList[i] );
        }
        else
        {
            // Check if a segment intersects the bounding box

            // Make a bounding box based on the segments start and end
            BBOX_2D segmentBBox( aSegList[i].m_Start, aSegList[j].m_Start );

            if( aBBox.Intersects( segmentBBox ) )
            {

                const SEGMENT_WITH_NORMALS& seg = aSegList[i];

                if( intersect( seg, p1, p2 ) || intersect( seg, p2, p3 ) || intersect( seg, p3, p4 )
                  || intersect( seg, p4, p1 ) )
                {
                    aOutSegThatIntersect.push_back( seg );
                }
            }
        }
    }
}

References BBOX_2D::Inside(), intersect(), BBOX_2D::Intersects(), BBOX_2D::Max(), and BBOX_2D::Min().

Referenced by ConvertPolygonToBlocks().

intersect()

static bool intersect ( const SEGMENT_WITH_NORMALS &  aSeg, const SFVEC2F &  aStart, const SFVEC2F &  aEnd  )

static

Definition at line 273 of file polygon_2d.cpp.

{
    const SFVEC2F r = aEnd - aStart;
    const SFVEC2F s = aSeg.m_Precalc_slope;
    const SFVEC2F q = aSeg.m_Start;

    const float rxs = r.x * s.y - r.y * s.x;

    if( fabs( rxs ) > glm::epsilon<float>() )
    {
        const float inv_rxs = 1.0f / rxs;

        const SFVEC2F pq = q - aStart;

        const float t = ( pq.x * s.y - pq.y * s.x ) * inv_rxs;

        if( ( t < 0.0f ) || ( t > 1.0f ) )
            return false;

        const float u = ( pq.x * r.y - pq.y * r.x ) * inv_rxs;

        if( ( u < 0.0f ) || ( u > 1.0f ) )
            return false;

        return true;
    }

    return false;
}

References SEGMENT_WITH_NORMALS::m_Precalc_slope, SEGMENT_WITH_NORMALS::m_Start, and r.

Referenced by EC_LINE::Apply(), EC_PERPLINE::Apply(), CornerListToPolygon(), and extractPathsFrom().

polygon_Convert()

static void polygon_Convert ( const SHAPE_LINE_CHAIN &  aPath, SEGMENTS &  aOutSegment, float  aBiuTo3dUnitsScale  )

static

Definition at line 351 of file polygon_2d.cpp.

{
    aOutSegment.resize( aPath.PointCount() );

    for( int j = 0; j < aPath.PointCount(); j++ )
    {
        const VECTOR2I& a = aPath.CPoint( j );

        aOutSegment[j].m_Start = SFVEC2F( (float) a.x * aBiuTo3dUnitsScale,
                                          (float) -a.y * aBiuTo3dUnitsScale );
    }

    unsigned int i;
    unsigned int j = aOutSegment.size() - 1;

    for( i = 0; i < aOutSegment.size(); j = i++ )
    {
        // Calculate constants for each segment
        aOutSegment[i].m_inv_JY_minus_IY = 1.0f /
                ( aOutSegment[j].m_Start.y - aOutSegment[i].m_Start.y );

        aOutSegment[i].m_JX_minus_IX = ( aOutSegment[j].m_Start.x - aOutSegment[i].m_Start.x );
    }
}

References SHAPE_LINE_CHAIN::CPoint(), SHAPE_LINE_CHAIN::PointCount(), VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by ConvertPolygonToBlocks().

polygon_IsPointInside()

static bool polygon_IsPointInside ( const SEGMENTS &  aSegments, const SFVEC2F &  aPoint  )

static

Definition at line 34 of file polygon_2d.cpp.

{
    wxASSERT( aSegments.size() >= 3 );

    unsigned int i;
    unsigned int j        = aSegments.size() - 1;
    bool         oddNodes = false;

    for( i = 0; i < aSegments.size(); j = i++ )
    {
        const float polyJY = aSegments[j].m_Start.y;
        const float polyIY = aSegments[i].m_Start.y;

        if( ( ( polyIY <= aPoint.y ) && ( polyJY >= aPoint.y ) )
          || ( ( polyJY <= aPoint.y ) && ( polyIY >= aPoint.y ) ) )
        {
            const float polyJX = aSegments[j].m_Start.x;
            const float polyIX = aSegments[i].m_Start.x;

            if( ( polyIX <= aPoint.x ) || ( polyJX <= aPoint.x ) )
                oddNodes ^= ( ( polyIX + ( ( aPoint.y - polyIY ) * aSegments[i].m_inv_JY_minus_IY )
                              * aSegments[i].m_JX_minus_IX )
                            < aPoint.x );
        }
    }

    return oddNodes;
}

Referenced by ConvertPolygonToBlocks(), and POLYGON_2D::IsPointInside().