use spatial index to limit rendering of features

qgis · Sep 24, 2018 · 2c8f238 · 2c8f238
1 parent 9b480af
commit 2c8f238
Show file tree

Hide file tree

Showing 6 changed files with 121 additions and 47 deletions.
diff --git a/src/core/mesh/qgsmeshlayerrenderer.cpp b/src/core/mesh/qgsmeshlayerrenderer.cpp
@@ -202,22 +202,42 @@ void QgsMeshLayerRenderer::copyVectorDatasetValues( QgsMeshLayer *layer )
 
 bool QgsMeshLayerRenderer::render()
 {
-
   renderScalarDataset();
-
-  renderMesh( mRendererSettings.nativeMeshSettings(), mNativeMesh.faces ); // native mesh
-  renderMesh( mRendererSettings.triangularMeshSettings(), mTriangularMesh.triangles() ); // triangular mesh
-
+  renderMesh();
   renderVectorDataset();
-
   return true;
 }
 
-void QgsMeshLayerRenderer::renderMesh(const QgsMeshRendererMeshSettings& settings , const QVector<QgsMeshFace> &faces)
+void QgsMeshLayerRenderer::renderMesh()
 {
-  if ( !settings.isEnabled() )
+  if ( !mRendererSettings.nativeMeshSettings().isEnabled() &&
+       !mRendererSettings.triangularMeshSettings().isEnabled() )
     return;
 
+  // triangular mesh
+  const QList<int> trianglesInExtent = mTriangularMesh.faceIndexesForRectangle( mContext.extent() );
+  if ( mRendererSettings.triangularMeshSettings().isEnabled() )
+  {
+    renderMesh( mRendererSettings.triangularMeshSettings(),
+                mTriangularMesh.triangles(),
+                trianglesInExtent );
+  }
+
+  // native mesh
+  if ( mRendererSettings.nativeMeshSettings().isEnabled() )
+  {
+    const QList<int> nativeFacesInExtent = QgsMeshUtils::nativeFacesFromTriangles( trianglesInExtent,
+                                           mTriangularMesh.trianglesToNativeFaces() );
+    renderMesh( mRendererSettings.nativeMeshSettings(),
+                mNativeMesh.faces,
+                nativeFacesInExtent );
+  }
+};
+
+void QgsMeshLayerRenderer::renderMesh( const QgsMeshRendererMeshSettings &settings, const QVector<QgsMeshFace> &faces, const QList<int> facesInExtent )
+{
+  Q_ASSERT( settings.isEnabled() );
+
   // Set up the render configuration options
   QPainter *painter = mContext.painter();
   painter->save();
@@ -238,27 +258,28 @@ void QgsMeshLayerRenderer::renderMesh(const QgsMeshRendererMeshSettings& setting
   const QVector<QgsMeshVertex> &vertices = mTriangularMesh.vertices(); //Triangular mesh vertices contains also native mesh vertices
   QSet<QPair<int, int>> drawnEdges;
 
-  for ( int i = 0; i < faces.size(); ++i )
+  for ( const int i : facesInExtent )
   {
     if ( mContext.renderingStopped() )
       break;
 
     const QgsMeshFace &face = faces[i];
-    if (face.size() < 2)
+    if ( face.size() < 2 )
       continue;
 
-    for (int j=0; j<face.size(); ++j) {
+    for ( int j = 0; j < face.size(); ++j )
+    {
       const int startVertexId = face[j];
-      const int endVertexId = face[ (j + 1) % face.size()];
-      const QPair<int, int> thisEdge(startVertexId, endVertexId);
-      const QPair<int, int> thisEdgeReversed(endVertexId, startVertexId);
-      if (drawnEdges.contains(thisEdge) || drawnEdges.contains(thisEdgeReversed))
+      const int endVertexId = face[( j + 1 ) % face.size()];
+      const QPair<int, int> thisEdge( startVertexId, endVertexId );
+      const QPair<int, int> thisEdgeReversed( endVertexId, startVertexId );
+      if ( drawnEdges.contains( thisEdge ) || drawnEdges.contains( thisEdgeReversed ) )
         continue;
-      drawnEdges.insert(thisEdge);
-      drawnEdges.insert(thisEdgeReversed);
+      drawnEdges.insert( thisEdge );
+      drawnEdges.insert( thisEdgeReversed );
 
-      const QgsMeshVertex & startVertex = vertices[startVertexId];
-      const QgsMeshVertex & endVertex = vertices[endVertexId];
+      const QgsMeshVertex &startVertex = vertices[startVertexId];
+      const QgsMeshVertex &endVertex = vertices[endVertexId];
       const QgsPointXY lineStart = mContext.mapToPixel().transform( startVertex.x(), startVertex.y() );
       const QgsPointXY lineEnd = mContext.mapToPixel().transform( endVertex.x(), endVertex.y() );
       painter->drawLine( lineStart.toQPointF(), lineEnd.toQPointF() );

diff --git a/src/core/mesh/qgsmeshlayerrenderer.h b/src/core/mesh/qgsmeshlayerrenderer.h
@@ -90,7 +90,8 @@ class QgsMeshLayerRenderer : public QgsMapLayerRenderer
     bool render() override;
 
   private:
-    void renderMesh(const QgsMeshRendererMeshSettings& settings, const QVector<QgsMeshFace> &faces);
+    void renderMesh();
+    void renderMesh( const QgsMeshRendererMeshSettings &settings, const QVector<QgsMeshFace> &faces, const QList<int> facesInExtent );
     void renderScalarDataset();
     void renderVectorDataset();
     void copyScalarDatasetValues( QgsMeshLayer *layer );

diff --git a/src/core/mesh/qgsmeshvectorrenderer.cpp b/src/core/mesh/qgsmeshvectorrenderer.cpp
@@ -92,12 +92,14 @@ void QgsMeshVectorRenderer::draw()
   pen.setColor( mCfg.color() );
   painter->setPen( pen );
 
+  const QList<int> trianglesInExtent = mTriangularMesh.faceIndexesForRectangle( mContext.extent() );
+
   if ( mCfg.isOnUserDefinedGrid() )
-    drawVectorDataOnGrid();
+    drawVectorDataOnGrid( trianglesInExtent );
   else if ( mDataOnVertices )
-    drawVectorDataOnVertices();
+    drawVectorDataOnVertices( trianglesInExtent );
   else
-    drawVectorDataOnFaces();
+    drawVectorDataOnFaces( trianglesInExtent );
 
   painter->restore();
 }
@@ -190,39 +192,50 @@ bool QgsMeshVectorRenderer::calcVectorLineEnd(
 }
 
 
-void QgsMeshVectorRenderer::drawVectorDataOnVertices()
+void QgsMeshVectorRenderer::drawVectorDataOnVertices( const QList<int> &trianglesInExtent )
 {
   const QVector<QgsMeshVertex> &vertices = mTriangularMesh.vertices();
+  const QVector<QgsMeshFace> &triangles = mTriangularMesh.triangles();
+  QSet<int> drawnVertices;
 
   // currently expecting that triangulation does not add any new extra vertices on the way
   Q_ASSERT( mDatasetValuesMag.count() == vertices.count() );
 
-  for ( int i = 0; i < vertices.size(); ++i )
+  for ( int triangleIndex : trianglesInExtent )
   {
     if ( mContext.renderingStopped() )
       break;
 
-    const QgsMeshVertex &vertex = vertices.at( i );
-    if ( !mContext.extent().contains( vertex ) )
-      continue;
+    const QgsMeshFace triangle = triangles[triangleIndex];
+    for ( int i : triangle )
+    {
+      if ( drawnVertices.contains( i ) )
+        continue;
+      drawnVertices.insert( i );
 
-    double xVal = mDatasetValuesX[i];
-    double yVal = mDatasetValuesY[i];
-    if ( nodataValue( xVal, yVal ) )
-      continue;
+      const QgsMeshVertex &vertex = vertices.at( i );
+      if ( !mContext.extent().contains( vertex ) )
+        continue;
 
-    double V = mDatasetValuesMag[i];  // pre-calculated magnitude
-    QgsPointXY lineStart = mContext.mapToPixel().transform( vertex.x(), vertex.y() );
+      double xVal = mDatasetValuesX[i];
+      double yVal = mDatasetValuesY[i];
+      if ( nodataValue( xVal, yVal ) )
+        continue;
 
-    drawVectorArrow( lineStart, xVal, yVal, V );
+      double V = mDatasetValuesMag[i];  // pre-calculated magnitude
+      QgsPointXY lineStart = mContext.mapToPixel().transform( vertex.x(), vertex.y() );
+
+      drawVectorArrow( lineStart, xVal, yVal, V );
+    }
   }
 }
 
-void QgsMeshVectorRenderer::drawVectorDataOnFaces()
+void QgsMeshVectorRenderer::drawVectorDataOnFaces( const QList<int> &trianglesInExtent )
 {
   const QVector<QgsMeshVertex> &centroids = mTriangularMesh.centroids();
-
-  for ( int i = 0; i < centroids.count(); i++ )
+  const QList<int> nativeFacesInExtent = QgsMeshUtils::nativeFacesFromTriangles( trianglesInExtent,
+                                         mTriangularMesh.trianglesToNativeFaces() );
+  for ( int i : nativeFacesInExtent )
   {
     if ( mContext.renderingStopped() )
       break;
@@ -243,15 +256,15 @@ void QgsMeshVectorRenderer::drawVectorDataOnFaces()
   }
 }
 
-void QgsMeshVectorRenderer::drawVectorDataOnGrid()
+void QgsMeshVectorRenderer::drawVectorDataOnGrid( const QList<int> &trianglesInExtent )
 {
   int cellx = mCfg.userGridCellWidth();
   int celly = mCfg.userGridCellHeight();
 
   const QVector<QgsMeshFace> &triangles = mTriangularMesh.triangles();
   const QVector<QgsMeshVertex> &vertices = mTriangularMesh.vertices();
 
-  for ( int i = 0; i < triangles.size(); i++ )
+  for ( const int i : trianglesInExtent )
   {
     if ( mContext.renderingStopped() )
       break;
@@ -263,11 +276,8 @@ void QgsMeshVectorRenderer::drawVectorDataOnGrid()
 
     const int nativeFaceIndex = mTriangularMesh.trianglesToNativeFaces()[i];
 
-    QgsRectangle bbox = QgsMeshLayerUtils::triangleBoundingBox( p1, p2, p3 );
-    if ( !mContext.extent().intersects( bbox ) )
-      continue;
-
     // Get the BBox of the element in pixels
+    QgsRectangle bbox = QgsMeshLayerUtils::triangleBoundingBox( p1, p2, p3 );
     int left, right, top, bottom;
     QgsMeshLayerUtils::boundingBoxToScreenRectangle( mContext.mapToPixel(), mOutputSize, bbox, left, right, top, bottom );
 

diff --git a/src/core/mesh/qgsmeshvectorrenderer.h b/src/core/mesh/qgsmeshvectorrenderer.h
@@ -65,11 +65,11 @@ class QgsMeshVectorRenderer
 
   private:
     //! Draws for data defined on vertices
-    void drawVectorDataOnVertices();
+    void drawVectorDataOnVertices( const QList<int> &trianglesInExtent );
     //! Draws for data defined on face centers
-    void drawVectorDataOnFaces();
+    void drawVectorDataOnFaces( const QList<int> &trianglesInExtent );
     //! Draws data on user-defined grid
-    void drawVectorDataOnGrid();
+    void drawVectorDataOnGrid( const QList<int> &trianglesInExtent );
     //! Draws arrow from start point and vector data
     void drawVectorArrow( const QgsPointXY &lineStart, double xVal, double yVal, double magnitude );
     //! Calculates the end point of the arrow based on start point and vector data

diff --git a/src/core/mesh/qgstriangularmesh.cpp b/src/core/mesh/qgstriangularmesh.cpp
@@ -55,6 +55,7 @@ bool QgsMeshFeatureIterator::fetchFeature( QgsFeature &f )
   const QgsMeshFace &face = mMesh->faces.at( it ) ;
   QgsGeometry geom = QgsMeshUtils::toGeometry( face, mMesh->vertices );
   f.setGeometry( geom );
+  f.setId( it );
   ++it;
   return true;
 }
@@ -232,6 +233,18 @@ int QgsTriangularMesh::faceIndexForPoint( const QgsPointXY &point ) const
   return -1;
 }
 
+QList<int> QgsTriangularMesh::faceIndexesForRectangle( const QgsRectangle &rectangle ) const
+{
+  const QList<QgsFeatureId> faceIndexes = mSpatialIndex.intersects( rectangle );
+  QList<int> indexes;
+  for ( const QgsFeatureId fid : faceIndexes )
+  {
+    int faceIndex = static_cast<int>( fid );
+    indexes.append( faceIndex );
+  }
+  return indexes;
+}
+
 QgsGeometry QgsMeshUtils::toGeometry( const QgsMeshFace &face, const QVector<QgsMeshVertex> &vertices )
 {
   QVector<QgsPoint> ring;
@@ -246,3 +259,14 @@ QgsGeometry QgsMeshUtils::toGeometry( const QgsMeshFace &face, const QVector<Qgs
   polygon->setExteriorRing( new QgsLineString( ring ) );
   return QgsGeometry( std::move( polygon ) );
 }
+
+QList<int> QgsMeshUtils::nativeFacesFromTriangles( const QList<int> &triangleIndexes, const QVector<int> &trianglesToNativeFaces )
+{
+  QSet<int> nativeFaces;
+  for ( const int triangleIndex : triangleIndexes )
+  {
+    const int nativeIndex = trianglesToNativeFaces[triangleIndex];
+    nativeFaces.insert( nativeIndex );
+  }
+  return nativeFaces.toList();
+}
diff --git a/src/core/mesh/qgstriangularmesh.h b/src/core/mesh/qgstriangularmesh.h
@@ -31,6 +31,7 @@
 
 class QgsRenderContext;
 class QgsCoordinateTransform;
+class QgsRectangle;
 
 //! Mesh - vertices and faces
 struct CORE_EXPORT QgsMesh
@@ -124,6 +125,17 @@ class CORE_EXPORT QgsTriangularMesh
      */
     int faceIndexForPoint( const QgsPointXY &point ) const ;
 
+    /**
+     * Finds indexes of triangles intersecting given bounding box
+     * It uses spatial indexing
+     *
+     * \param rectangle bounding box in map coordinate system
+     * \returns triangle indexes that intersect the rectangle
+     *
+     * \since QGIS 3.4
+     */
+    QList<int> faceIndexesForRectangle( const QgsRectangle &rectangle ) const ;
+
   private:
     // vertices: map CRS; 0-N ... native vertices, N+1 - len ... extra vertices
     // faces are derived triangles
@@ -141,6 +153,12 @@ namespace QgsMeshUtils
 {
   //! Returns face as polygon geometry
   QgsGeometry toGeometry( const QgsMeshFace &face, const QVector<QgsMeshVertex> &vertices );
+
+  /**
+   * Returns unique native faces indexes from list of triangle indexes
+   * \since QGIS 3.4
+   */
+  QList<int> nativeFacesFromTriangles( const QList<int> &triangleIndexes, const QVector<int> &trianglesToNativeFaces );
 };
 
 #endif // QGSTRIANGULARMESH_H