polygon_2d.h File Reference

#include "object_2d.h"
#include "../accelerators/container_2d.h"
#include <geometry/shape_poly_set.h>
#include <vector>

Go to the source code of this file.

Classes
struct	POLYSEGMENT
struct	SEG_NORMALS
struct	SEGMENT_WITH_NORMALS
struct	OUTERS_AND_HOLES
	Handle a subset of a polygon. More...
class	POLYGON_2D
	Represent a sub polygon block. More...
class	DUMMY_BLOCK_2D
	A dummy block defined by a 2d box size. More...

Typedefs
typedef std::vector< POLYSEGMENT >	SEGMENTS
typedef std::vector< SEGMENT_WITH_NORMALS >	SEGMENTS_WIDTH_NORMALS
	List used to test ray2d intersections. More...

Functions
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...
void	Polygon2d_TestModule ()

Typedef Documentation

SEGMENTS

typedef std::vector< POLYSEGMENT > SEGMENTS

Definition at line 61 of file polygon_2d.h.

SEGMENTS_WIDTH_NORMALS

typedef std::vector< SEGMENT_WITH_NORMALS > SEGMENTS_WIDTH_NORMALS

List used to test ray2d intersections.

It will be a subset of an original polygon. The normals will be passed already interpolated.

Definition at line 69 of file polygon_2d.h.

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().

Polygon2d_TestModule()

void Polygon2d_TestModule

(

)