Skip to content

Commit

Permalink
[pal] Provide more exit points for early cancelation
Browse files Browse the repository at this point in the history 
When a rendering operation was canceled, PAL had very few early
exit points. This often resulted in many canceled rendering operations
burning away in background threads as labeling candidates and solutions
were being generated for jobs which were no longer needed.

Add more exit points and cancel checks throughout various expensive
pal operations, allowing labeling jobs to terminate quickly.

Fixes #32489
  • Loading branch information
@nyalldawson
nyalldawson committed Nov 29, 2019
1 parent 8878e9b commit 09b8612
Show file tree
Hide file tree
Showing 5 changed files with 91 additions and 25 deletions.
4 changes: 2 additions & 2 deletions src/app/qgsapplayertreeviewmenuprovider.cpp
View file
Expand Up @@ -649,13 +649,13 @@ QList< LegendLayerAction > QgsAppLayerTreeViewMenuProvider::legendLayerActions(
#ifdef QGISDEBUG
if ( mLegendLayerActionMap.contains( type ) )
{
QgsDebugMsg( QStringLiteral( "legendLayerActions for layers of type %1:" ).arg( static_cast<int>( type ) ) );
QgsDebugMsgLevel( QStringLiteral( "legendLayerActions for layers of type %1:" ).arg( static_cast<int>( type ) ), 2 );

const auto legendLayerActions { mLegendLayerActionMap.value( type ) };
for ( const LegendLayerAction &lyrAction : legendLayerActions )
{
Q_UNUSED( lyrAction )
QgsDebugMsg( QStringLiteral( "%1/%2 - %3 layers" ).arg( lyrAction.menu, lyrAction.action->text() ).arg( lyrAction.layers.count() ) );
QgsDebugMsgLevel( QStringLiteral( "%1/%2 - %3 layers" ).arg( lyrAction.menu, lyrAction.action->text() ).arg( lyrAction.layers.count() ), 2 );
}
}
#endif
Expand Down
54 changes: 41 additions & 13 deletions src/core/pal/feature.cpp
View file
Expand Up @@ -617,7 +617,7 @@ std::size_t FeaturePart::createCandidatesAroundPoint( double x, double y, std::v
return numberCandidatesGenerated;
}

std::size_t FeaturePart::createCandidatesAlongLine( std::vector< std::unique_ptr< LabelPosition > > &lPos, PointSet *mapShape, bool allowOverrun )
std::size_t FeaturePart::createCandidatesAlongLine( std::vector< std::unique_ptr< LabelPosition > > &lPos, PointSet *mapShape, bool allowOverrun, Pal *pal )
{
if ( allowOverrun )
{
Expand All @@ -632,17 +632,17 @@ std::size_t FeaturePart::createCandidatesAlongLine( std::vector< std::unique_ptr
}

//prefer to label along straightish segments:
std::size_t candidates = createCandidatesAlongLineNearStraightSegments( lPos, mapShape );
std::size_t candidates = createCandidatesAlongLineNearStraightSegments( lPos, mapShape, pal );

if ( static_cast< int >( candidates ) < mLF->layer()->maximumLineLabelCandidates() )
{
// but not enough candidates yet, so fallback to labeling near whole line's midpoint
candidates = createCandidatesAlongLineNearMidpoint( lPos, mapShape, candidates > 0 ? 0.01 : 0.0 );
candidates = createCandidatesAlongLineNearMidpoint( lPos, mapShape, candidates > 0 ? 0.01 : 0.0, pal );
}
return candidates;
}

std::size_t FeaturePart::createCandidatesAlongLineNearStraightSegments( std::vector< std::unique_ptr< LabelPosition > > &lPos, PointSet *mapShape )
std::size_t FeaturePart::createCandidatesAlongLineNearStraightSegments( std::vector< std::unique_ptr< LabelPosition > > &lPos, PointSet *mapShape, Pal *pal )
{
double labelWidth = getLabelWidth();
double labelHeight = getLabelHeight();
Expand Down Expand Up @@ -765,6 +765,11 @@ std::size_t FeaturePart::createCandidatesAlongLineNearStraightSegments( std::vec

while ( currentDistanceAlongLine + labelWidth < distanceToEndOfSegment )
{
if ( pal->isCanceled() )
{
return lPos.size();
}

// calculate positions along linestring corresponding to start and end of current label candidate
line->getPointByDistance( segmentLengths.data(), distanceToSegment.data(), currentDistanceAlongLine, &candidateStartX, &candidateStartY );
line->getPointByDistance( segmentLengths.data(), distanceToSegment.data(), currentDistanceAlongLine + labelWidth, &candidateEndX, &candidateEndY );
Expand Down Expand Up @@ -862,7 +867,7 @@ std::size_t FeaturePart::createCandidatesAlongLineNearStraightSegments( std::vec
return lPos.size();
}

std::size_t FeaturePart::createCandidatesAlongLineNearMidpoint( std::vector< std::unique_ptr< LabelPosition > > &lPos, PointSet *mapShape, double initialCost )
std::size_t FeaturePart::createCandidatesAlongLineNearMidpoint( std::vector< std::unique_ptr< LabelPosition > > &lPos, PointSet *mapShape, double initialCost, Pal *pal )
{
double distanceLineToLabel = getLabelDistance();

Expand Down Expand Up @@ -922,6 +927,11 @@ std::size_t FeaturePart::createCandidatesAlongLineNearMidpoint( std::vector< std
int i = 0;
while ( currentDistanceAlongLine < totalLineLength - labelWidth )
{
if ( pal->isCanceled() )
{
return lPos.size();
}

// calculate positions along linestring corresponding to start and end of current label candidate
line->getPointByDistance( segmentLengths.data(), distanceToSegment.data(), currentDistanceAlongLine, &candidateStartX, &candidateStartY );
line->getPointByDistance( segmentLengths.data(), distanceToSegment.data(), currentDistanceAlongLine + labelWidth, &candidateEndX, &candidateEndY );
Expand Down Expand Up @@ -1193,7 +1203,7 @@ static LabelPosition *_createCurvedCandidate( LabelPosition *lp, double angle, d
return newLp;
}

std::size_t FeaturePart::createCurvedCandidatesAlongLine( std::vector< std::unique_ptr< LabelPosition > > &lPos, PointSet *mapShape, bool allowOverrun )
std::size_t FeaturePart::createCurvedCandidatesAlongLine( std::vector< std::unique_ptr< LabelPosition > > &lPos, PointSet *mapShape, bool allowOverrun, Pal *pal )
{
LabelInfo *li = mLF->curvedLabelInfo();

Expand Down Expand Up @@ -1257,6 +1267,9 @@ std::size_t FeaturePart::createCurvedCandidatesAlongLine( std::vector< std::uniq
return 0;
}

if ( pal->isCanceled() )
return 0;

QLinkedList<LabelPosition *> positions;
double delta = std::max( li->label_height / 6, total_distance / mLF->layer()->maximumLineLabelCandidates() );

Expand All @@ -1271,6 +1284,9 @@ std::size_t FeaturePart::createCurvedCandidatesAlongLine( std::vector< std::uniq
// placements may need to be reversed if using map orientation and the line has right-to-left direction
bool reversed = false;

if ( pal->isCanceled() )
return 0;

// an orientation of 0 means try both orientations and choose the best
int orientation = 0;
if ( !( flags & FLAG_MAP_ORIENTATION ) )
Expand Down Expand Up @@ -1393,7 +1409,7 @@ std::size_t FeaturePart::createCurvedCandidatesAlongLine( std::vector< std::uniq
*
*/

std::size_t FeaturePart::createCandidatesForPolygon( std::vector< std::unique_ptr< LabelPosition > > &lPos, PointSet *mapShape )
std::size_t FeaturePart::createCandidatesForPolygon( std::vector< std::unique_ptr< LabelPosition > > &lPos, PointSet *mapShape, Pal *pal )
{
double labelWidth = getLabelWidth();
double labelHeight = getLabelHeight();
Expand All @@ -1403,6 +1419,9 @@ std::size_t FeaturePart::createCandidatesForPolygon( std::vector< std::unique_pt

mapShape->parent = nullptr;

if ( pal->isCanceled() )
return 0;

shapes_toProcess.append( mapShape );

splitPolygons( shapes_toProcess, shapes_final, labelWidth, labelHeight );
Expand Down Expand Up @@ -1433,6 +1452,9 @@ std::size_t FeaturePart::createCandidatesForPolygon( std::vector< std::unique_pt
delete shape;
}

if ( pal->isCanceled() )
return 0;

//dx = dy = min( yrm, xrm ) / 2;
dx = labelWidth / 2.0;
dy = labelHeight / 2.0;
Expand All @@ -1449,6 +1471,9 @@ std::size_t FeaturePart::createCandidatesForPolygon( std::vector< std::unique_pt
{
for ( CHullBox &box : boxes )
{
if ( pal->isCanceled() )
return numberCandidatesGenerated;

if ( ( box.length * box.width ) > ( xmax - xmin ) * ( ymax - ymin ) * 5 )
{
// Very Large BBOX (should never occur)
Expand Down Expand Up @@ -1538,6 +1563,9 @@ std::size_t FeaturePart::createCandidatesForPolygon( std::vector< std::unique_pt

for ( px = px0; px <= box.width; px += dx )
{
if ( pal->isCanceled() )
break;

for ( py = py0; py <= box.length; py += dy )
{

Expand Down Expand Up @@ -1580,7 +1608,7 @@ std::size_t FeaturePart::createCandidatesForPolygon( std::vector< std::unique_pt
return nbp;
}

std::vector< std::unique_ptr< LabelPosition > > FeaturePart::createCandidates()
std::vector< std::unique_ptr< LabelPosition > > FeaturePart::createCandidates( Pal *pal )
{
std::vector< std::unique_ptr< LabelPosition > > lPos;
double angle = mLF->hasFixedAngle() ? mLF->fixedAngle() : 0.0;
Expand All @@ -1603,9 +1631,9 @@ std::vector< std::unique_ptr< LabelPosition > > FeaturePart::createCandidates()
break;
case GEOS_LINESTRING:
if ( mLF->layer()->isCurved() )
createCurvedCandidatesAlongLine( lPos, this, true );
createCurvedCandidatesAlongLine( lPos, this, true, pal );
else
createCandidatesAlongLine( lPos, this, true );
createCandidatesAlongLine( lPos, this, true, pal );
break;

case GEOS_POLYGON:
Expand All @@ -1621,13 +1649,13 @@ std::vector< std::unique_ptr< LabelPosition > > FeaturePart::createCandidates()
createCandidatesAroundPoint( cx, cy, lPos, angle );
break;
case QgsPalLayerSettings::Line:
createCandidatesAlongLine( lPos, this );
createCandidatesAlongLine( lPos, this, false, pal );
break;
case QgsPalLayerSettings::PerimeterCurved:
createCurvedCandidatesAlongLine( lPos, this );
createCurvedCandidatesAlongLine( lPos, this, false, pal );
break;
default:
createCandidatesForPolygon( lPos, this );
createCandidatesForPolygon( lPos, this, pal );
break;
}
}
Expand Down
16 changes: 10 additions & 6 deletions src/core/pal/feature.h
View file
Expand Up @@ -130,7 +130,7 @@ namespace pal
/**
* Generates a list of candidate positions for labels for this feature.
*/
std::vector<std::unique_ptr<LabelPosition> > createCandidates();
std::vector<std::unique_ptr<LabelPosition> > createCandidates( Pal *pal );

/**
* Generate candidates for point feature, located around a specified point.
Expand Down Expand Up @@ -175,18 +175,20 @@ namespace pal
* \param lPos pointer to an array of candidates, will be filled by generated candidates
* \param mapShape a pointer to the line
* \param allowOverrun set to TRUE to allow labels to overrun features
* \param pal point to pal settings object, for cancellation support
* \returns the number of generated candidates
*/
std::size_t createCandidatesAlongLine( std::vector<std::unique_ptr<LabelPosition> > &lPos, PointSet *mapShape, bool allowOverrun = false );
std::size_t createCandidatesAlongLine( std::vector<std::unique_ptr<LabelPosition> > &lPos, PointSet *mapShape, bool allowOverrun, Pal *pal );

/**
* Generate candidates for line feature, by trying to place candidates towards the middle of the longest
* straightish segments of the line. Segments closer to horizontal are preferred over vertical segments.
* \param lPos pointer to an array of candidates, will be filled by generated candidates
* \param mapShape a pointer to the line
* \param pal point to pal settings object, for cancellation support
* \returns the number of generated candidates
*/
std::size_t createCandidatesAlongLineNearStraightSegments( std::vector<std::unique_ptr<LabelPosition> > &lPos, PointSet *mapShape );
std::size_t createCandidatesAlongLineNearStraightSegments( std::vector<std::unique_ptr<LabelPosition> > &lPos, PointSet *mapShape, Pal *pal );

/**
* Generate candidates for line feature, by trying to place candidates as close as possible to the line's midpoint.
Expand All @@ -197,7 +199,7 @@ namespace pal
* by a preset amount.
* \returns the number of generated candidates
*/
std::size_t createCandidatesAlongLineNearMidpoint( std::vector<std::unique_ptr<LabelPosition> > &lPos, PointSet *mapShape, double initialCost = 0.0 );
std::size_t createCandidatesAlongLineNearMidpoint( std::vector<std::unique_ptr<LabelPosition> > &lPos, PointSet *mapShape, double initialCost = 0.0, Pal *pal = nullptr );

/**
* Returns the label position for a curved label at a specific offset along a path.
Expand All @@ -217,17 +219,19 @@ namespace pal
* \param lPos pointer to an array of candidates, will be filled by generated candidates
* \param mapShape a pointer to the line
* \param allowOverrun set to TRUE to allow labels to overrun features
* \param pal point to pal settings object, for cancellation support
* \returns the number of generated candidates
*/
std::size_t createCurvedCandidatesAlongLine( std::vector<std::unique_ptr<LabelPosition> > &lPos, PointSet *mapShape, bool allowOverrun = false );
std::size_t createCurvedCandidatesAlongLine( std::vector<std::unique_ptr<LabelPosition> > &lPos, PointSet *mapShape, bool allowOverrun, Pal *pal );

/**
* Generate candidates for polygon features.
* \param lPos pointer to an array of candidates, will be filled by generated candidates
* \param mapShape a pointer to the polygon
* \param pal point to pal settings object, for cancellation support
* \returns the number of generated candidates
*/
std::size_t createCandidatesForPolygon( std::vector<std::unique_ptr<LabelPosition> > &lPos, PointSet *mapShape );
std::size_t createCandidatesForPolygon( std::vector<std::unique_ptr<LabelPosition> > &lPos, PointSet *mapShape, Pal *pal );

/**
* Tests whether this feature part belongs to the same QgsLabelFeature as another
Expand Down
40 changes: 37 additions & 3 deletions src/core/pal/pal.cpp
View file
Expand Up @@ -119,6 +119,9 @@ bool extractFeatCallback( FeaturePart *featurePart, void *ctx )
double amin[2], amax[2];
FeatCallBackCtx *context = reinterpret_cast< FeatCallBackCtx * >( ctx );

if ( context->pal->isCanceled() )
return false;

// Holes of the feature are obstacles
for ( int i = 0; i < featurePart->getNumSelfObstacles(); i++ )
{
Expand All @@ -132,7 +135,10 @@ bool extractFeatCallback( FeaturePart *featurePart, void *ctx )
}

// generate candidates for the feature part
std::vector< std::unique_ptr< LabelPosition > > candidates = featurePart->createCandidates();
std::vector< std::unique_ptr< LabelPosition > > candidates = featurePart->createCandidates( context->pal );

if ( context->pal->isCanceled() )
return false;

// purge candidates that are outside the bbox
candidates.erase( std::remove_if( candidates.begin(), candidates.end(), [&context]( std::unique_ptr< LabelPosition > &candidate )
Expand All @@ -143,6 +149,9 @@ bool extractFeatCallback( FeaturePart *featurePart, void *ctx )
return !candidate->within( context->mapBoundary );
} ), candidates.end() );

if ( context->pal->isCanceled() )
return false;

if ( !candidates.empty() )
{
for ( std::unique_ptr< LabelPosition > &candidate : candidates )
Expand Down Expand Up @@ -175,6 +184,7 @@ struct ObstacleCallBackCtx
{
RTree<FeaturePart *, double, 2, double> *obstacleIndex = nullptr;
int obstacleCount = 0;
Pal *pal = nullptr;
};

/*
Expand All @@ -186,6 +196,8 @@ bool extractObstaclesCallback( FeaturePart *ft_ptr, void *ctx )
{
double amin[2], amax[2];
ObstacleCallBackCtx *context = reinterpret_cast< ObstacleCallBackCtx * >( ctx );
if ( context->pal->isCanceled() )
return false; // do not continue searching

// insert into obstacles
ft_ptr->getBoundingBox( amin, amax );
Expand Down Expand Up @@ -258,6 +270,7 @@ std::unique_ptr<Problem> Pal::extract( const QgsRectangle &extent, const QgsGeom
ObstacleCallBackCtx obstacleContext;
obstacleContext.obstacleIndex = &obstacles;
obstacleContext.obstacleCount = 0;
obstacleContext.pal = this;

// first step : extract features from layers

Expand All @@ -284,15 +297,26 @@ std::unique_ptr<Problem> Pal::extract( const QgsRectangle &extent, const QgsGeom
if ( layer->mergeConnectedLines() )
layer->joinConnectedFeatures();

if ( isCanceled() )
return nullptr;

layer->chopFeaturesAtRepeatDistance();

if ( isCanceled() )
return nullptr;

QMutexLocker locker( &layer->mMutex );

// find features within bounding box and generate candidates list
context.layer = layer;
layer->mFeatureIndex.Search( amin, amax, extractFeatCallback, static_cast< void * >( &context ) );
if ( isCanceled() )
return nullptr;

// find obstacles within bounding box
layer->mObstacleIndex.Search( amin, amax, extractObstaclesCallback, static_cast< void * >( &obstacleContext ) );
if ( isCanceled() )
return nullptr;

locker.unlock();

Expand All @@ -305,6 +329,9 @@ std::unique_ptr<Problem> Pal::extract( const QgsRectangle &extent, const QgsGeom
}
palLocker.unlock();

if ( isCanceled() )
return nullptr;

prob->mLayerCount = layersWithFeaturesInBBox.size();
prob->labelledLayersName = layersWithFeaturesInBBox;

Expand Down Expand Up @@ -354,6 +381,9 @@ std::unique_ptr<Problem> Pal::extract( const QgsRectangle &extent, const QgsGeom
// sort candidates by cost, skip less interesting ones, calculate polygon costs (if using polygons)
max_p = CostCalculator::finalizeCandidatesCosts( feat.get(), max_p, &obstacles, bbx, bby );

if ( isCanceled() )
return nullptr;

// only keep the 'max_p' best candidates
while ( feat->candidates.size() > max_p )
{
Expand All @@ -362,6 +392,9 @@ std::unique_ptr<Problem> Pal::extract( const QgsRectangle &extent, const QgsGeom
feat->candidates.pop_back();
}

if ( isCanceled() )
return nullptr;

// update problem's # candidate
prob->mFeatNbLp[i] = static_cast< int >( feat->candidates.size() );
prob->mTotalCandidates += static_cast< int >( feat->candidates.size() );
Expand All @@ -380,9 +413,7 @@ std::unique_ptr<Problem> Pal::extract( const QgsRectangle &extent, const QgsGeom
while ( !features.empty() ) // foreach feature
{
if ( isCanceled() )
{
return nullptr;
}

std::unique_ptr< Feats > feat = std::move( features.front() );
features.pop_front();
Expand All @@ -406,6 +437,9 @@ std::unique_ptr<Problem> Pal::extract( const QgsRectangle &extent, const QgsGeom
nbOverlaps += lp->getNumOverlaps();

prob->addCandidatePosition( std::move( lp ) );

if ( isCanceled() )
return nullptr;
}
}
nbOverlaps /= 2;
Expand Down

0 comments on commit 09b8612

Please sign in to comment.