fix frustum culling for terrain

qgis · Sep 15, 2017 · 56ed9b0 · 56ed9b0
1 parent 7f1f8a6
commit 56ed9b0
Show file tree

Hide file tree

Showing 4 changed files with 61 additions and 42 deletions.
diff --git a/src/3d/aabb.h b/src/3d/aabb.h
@@ -37,6 +37,8 @@ class _3D_EXPORT AABB
     float zCenter() const { return ( zMax + zMin ) / 2; }
 
     QVector3D center() const { return QVector3D( xCenter(), yCenter(), zCenter() ); }
+    QVector3D minimum() const { return QVector3D( xMin, yMin, zMin ); }
+    QVector3D maximum() const { return QVector3D( xMax, yMax, zMax ); }
 
     bool intersects( const AABB &other ) const
     {

diff --git a/src/3d/chunks/chunkedentity.cpp b/src/3d/chunks/chunkedentity.cpp
@@ -1,10 +1,10 @@
+#include <QVector4D>
 #include "chunkedentity.h"
-
 #include "chunkboundsentity.h"
 #include "chunklist.h"
 #include "chunkloader.h"
 #include "chunknode.h"
-
+#include "utils.h"
 
 static float screenSpaceError( float epsilon, float distance, float screenSize, float fov )
 {
@@ -42,43 +42,6 @@ static float screenSpaceError( ChunkNode *node, const SceneState &state )
   return sse;
 }
 
-
-#include <QVector4D>
-
-//! coarse box vs frustum test for culling.
-//! corners of oriented box are transformed to clip space and new axis-aligned box is created for intersection test
-static bool isInFrustum( const AABB &bbox, const QMatrix4x4 &viewProjectionMatrix )
-{
-  float xmin, ymin, zmin, xmax, ymax, zmax;
-  for ( int i = 0; i < 8; ++i )
-  {
-    QVector4D p( ( ( i >> 0 ) & 1 ) ? bbox.xMin : bbox.xMax,
-                 ( ( i >> 1 ) & 1 ) ? bbox.yMin : bbox.yMax,
-                 ( ( i >> 2 ) & 1 ) ? bbox.zMin : bbox.zMax, 1 );
-    QVector4D pc = viewProjectionMatrix * p;
-    pc /= pc.w();
-    float x = pc.x(), y = pc.y(), z = pc.z();
-
-    if ( i == 0 )
-    {
-      xmin = xmax = x;
-      ymin = ymax = y;
-      zmin = zmax = z;
-    }
-    else
-    {
-      if ( x < xmin ) xmin = x;
-      if ( x > xmax ) xmax = x;
-      if ( y < ymin ) ymin = y;
-      if ( y > ymax ) ymax = y;
-      if ( z < zmin ) zmin = z;
-      if ( z > zmax ) zmax = z;
-    }
-  }
-  return AABB( -1, -1, -1, 1, 1, 1 ).intersects( AABB( xmin, ymin, zmin, xmax, ymax, zmax ) );
-}
-
-
 ChunkedEntity::ChunkedEntity( const AABB &rootBbox, float rootError, float tau, int maxLevel, ChunkLoaderFactory *loaderFactory, Qt3DCore::QNode *parent )
   : Qt3DCore::QEntity( parent )
   , needsUpdate( false )
@@ -237,8 +200,7 @@ void ChunkedEntity::updateNodes( const QList<ChunkNode *> &nodes, ChunkQueueJobF
 
 void ChunkedEntity::update( ChunkNode *node, const SceneState &state )
 {
-  // TODO: fix and re-enable frustum culling
-  if ( 0 && !isInFrustum( node->bbox, state.viewProjectionMatrix ) )
+  if (Utils::isCullable(node->bbox, state.viewProjectionMatrix ) )
   {
     ++frustumCulled;
     return;

diff --git a/src/3d/utils.cpp b/src/3d/utils.cpp
@@ -140,3 +140,52 @@ QMatrix4x4 Utils::stringToMatrix4x4( const QString &str )
     d[i] = elems[i].toFloat();
   return m;
 }
+
+//! copied from https://searchcode.com/codesearch/view/35195518/
+//! qt3d /src/threed/painting/qglpainter.cpp
+//! no changes in the code
+static inline uint outcode(const QVector4D &v)
+{
+    // For a discussion of outcodes see pg 388 Dunn & Parberry.
+    // For why you can't just test if the point is in a bounding box
+    // consider the case where a view frustum with view-size 1.5 x 1.5
+    // is tested against a 2x2 box which encloses the near-plane, while
+    // all the points in the box are outside the frustum.
+    // TODO: optimise this with assembler - according to D&P this can
+    // be done in one line of assembler on some platforms
+    uint code = 0;
+    if (v.x() < -v.w()) code |= 0x01;
+    if (v.x() > v.w())  code |= 0x02;
+    if (v.y() < -v.w()) code |= 0x04;
+    if (v.y() > v.w())  code |= 0x08;
+    if (v.z() < -v.w()) code |= 0x10;
+    if (v.z() > v.w())  code |= 0x20;
+    return code;
+}
+
+
+//! coarse box vs frustum test for culling.
+//! corners of oriented box are transformed to clip space
+//! and there is a test that all points are on the wrong side of the same plane
+//! see http://www.lighthouse3d.com/tutorials/view-frustum-culling/geometric-approach-testing-boxes/
+//!
+//! should be equivalent to https://searchcode.com/codesearch/view/35195518/
+//! qt3d /src/threed/painting/qglpainter.cpp
+//! bool QGLPainter::isCullable(const QBox3D& box) const
+bool Utils::isCullable( const AABB &bbox, const QMatrix4x4 &viewProjectionMatrix )
+{
+  uint out = 0xff;
+
+  for ( int i = 0; i < 8; ++i )
+  {
+    QVector4D p( ( ( i >> 0 ) & 1 ) ? bbox.xMin : bbox.xMax,
+                 ( ( i >> 1 ) & 1 ) ? bbox.yMin : bbox.yMax,
+                 ( ( i >> 2 ) & 1 ) ? bbox.zMin : bbox.zMax, 1 );
+    QVector4D pc = viewProjectionMatrix * p;
+
+    // if the logical AND of all the outcodes is non-zero then the BB is
+    // definitely outside the view frustum.
+    out = out & outcode(pc);
+  }
+  return out;
+}
diff --git a/src/3d/utils.h b/src/3d/utils.h
@@ -5,7 +5,7 @@ class QgsLineString;
 class QgsPolygonV2;
 
 #include "map3d.h"
-
+#include "aabb.h"
 
 //! how to handle altitude of vector features
 enum AltitudeClamping
@@ -45,6 +45,12 @@ class _3D_EXPORT Utils
 
     static QString matrix4x4toString( const QMatrix4x4 &m );
     static QMatrix4x4 stringToMatrix4x4( const QString &str );
+
+    /**
+        Returns true if bbox is completely outside the current viewing volume.
+        This is used to perform object culling checks.
+    */
+    static bool isCullable(const AABB &bbox, const QMatrix4x4 &viewProjectionMatrix );
 };
 
 #endif // UTILS_H