From 271dadee1b91a8e9c65d2c1d3317d403bc832956 Mon Sep 17 00:00:00 2001
From: ggetz <ggetz881@gmail.com>
Date: Fri, 3 Nov 2017 13:57:46 -0400
Subject: [PATCH] Tileset traversal with clipping planes

---
 Apps/Sandcastle/gallery/Clipping Planes.html  | 34 +++++++++++-------
 Source/Core/CullingVolume.js                  | 18 ++++++++--
 Source/Core/Plane.js                          | 35 +++++++++++++++++--
 Source/Scene/Cesium3DTile.js                  | 32 +++++++++++++++--
 Source/Scene/Model.js                         | 14 ++++----
 Source/Scene/PointCloud3DTileContent.js       | 15 ++++----
 .../Shaders/Builtin/Functions/clipPlanes.glsl |  2 +-
 7 files changed, 117 insertions(+), 33 deletions(-)

diff --git a/Apps/Sandcastle/gallery/Clipping Planes.html b/Apps/Sandcastle/gallery/Clipping Planes.html
index 5637666be68..627206ed45f 100644
--- a/Apps/Sandcastle/gallery/Clipping Planes.html	
+++ b/Apps/Sandcastle/gallery/Clipping Planes.html	
@@ -44,25 +44,26 @@
     <tr>
         <td>x</td>
         <td>
-            <input type="range" min="-100" max="100" step="1" data-bind="value: xOffset, valueUpdate: 'input'">
+            <input type="range" min="-150" max="150" step="1" data-bind="value: xOffset, valueUpdate: 'input'">
             <input type="text" size="2" data-bind="value: xOffset">
         </td>
     </tr>
     <tr>
         <td>y</td>
         <td>
-            <input type="range" min="-100" max="100" step="1" data-bind="value: yOffset, valueUpdate: 'input'">
+            <input type="range" min="-150" max="150" step="1" data-bind="value: yOffset, valueUpdate: 'input'">
             <input type="text" size="2" data-bind="value: yOffset">
         </td>
     </tr>
     <tr>
         <td>z</td>
         <td>
-            <input type="range" min="-100" max="100" step="1" data-bind="value: zOffset, valueUpdate: 'input'">
+            <input type="range" min="-150" max="150" step="1" data-bind="value: zOffset, valueUpdate: 'input'">
             <input type="text" size="2" data-bind="value: zOffset">
         </td>
     </tr>
     </tbody></table>
+    <input type="checkbox" value="false" data-bind="checked: debugBoundingVolumesEnabled, valueUpdate: 'input'"> Show debug <code>boundingVolume</code>
 </div>
 
 <script id="cesium_sandcastle_script">
@@ -77,10 +78,20 @@
     new Cesium.Plane(new Cesium.Cartesian3(0, 0, 1), 100.0)
 ];
 
-function loadTileset (url) {
+var viewModel = {
+    exampleType : 'BIM',
+    exampleTypes : ['BIM', 'Model', 'Point Cloud'],
+    xOffset : 0.0,
+    yOffset: 100.0,
+    zOffset: 100.0,
+    debugBoundingVolumesEnabled: false
+};
+
+var tileset;
+function loadTileset (url, offeset) {
     reset();
 
-    var tileset = viewer.scene.primitives.add(new Cesium.Cesium3DTileset({
+    tileset = viewer.scene.primitives.add(new Cesium.Cesium3DTileset({
         url : url
     }));
 
@@ -92,6 +103,7 @@
         throw(error);
     });
 
+    tileset.debugShowBoundingVolume = viewModel.debugBoundingVolumesEnabled;
     tileset.clippingPlanes = defaultClippingPlanes;
     return tileset.clippingPlanes;
 }
@@ -131,14 +143,6 @@
 var clippingPlanes = loadTileset(bimUrl);
 
 // Track and create the bindings for the view model
-
-var viewModel = {
-    exampleType : 'BIM',
-    exampleTypes : ['BIM', 'Model', 'Point Cloud'],
-    xOffset : 0.0,
-    yOffset: 100.0,
-    zOffset: 100.0
-};
 var toolbar = document.getElementById('toolbar');
 Cesium.knockout.track(viewModel);
 Cesium.knockout.applyBindings(viewModel, toolbar);
@@ -155,6 +159,10 @@
     clippingPlanes[2].distance = parseFloat(newValue);
 });
 
+Cesium.knockout.getObservable(viewModel, 'debugBoundingVolumesEnabled').subscribe(function(newValue) {
+    tileset.debugShowBoundingVolume = newValue;
+});
+
 Cesium.knockout.getObservable(viewModel, 'exampleType').subscribe(
     function(newValue) {
         if (newValue === 'BIM') {
diff --git a/Source/Core/CullingVolume.js b/Source/Core/CullingVolume.js
index 084406b7672..02578ae0b65 100644
--- a/Source/Core/CullingVolume.js
+++ b/Source/Core/CullingVolume.js
@@ -111,15 +111,22 @@ define([
      * Determines whether a bounding volume intersects the culling volume.
      *
      * @param {Object} boundingVolume The bounding volume whose intersection with the culling volume is to be tested.
+     * @param {Function} [checkClipped] A function which takes the boundingVolume as a parameter, that if supplied,
+     *                                  will check to see if the tile has been entirely clipped by any tileset
+     *                                  clippingPlane.
      * @returns {Intersect}  Intersect.OUTSIDE, Intersect.INTERSECTING, or Intersect.INSIDE.
      */
-    CullingVolume.prototype.computeVisibility = function(boundingVolume) {
+    CullingVolume.prototype.computeVisibility = function(boundingVolume, checkClipped) {
         //>>includeStart('debug', pragmas.debug);
         if (!defined(boundingVolume)) {
             throw new DeveloperError('boundingVolume is required.');
         }
         //>>includeEnd('debug');
 
+        if (defined(checkClipped) && checkClipped(boundingVolume)) {
+            return Intersect.OUTSIDE;
+        }
+
         var planes = this.planes;
         var intersecting = false;
         for (var k = 0, len = planes.length; k < len; ++k) {
@@ -142,11 +149,14 @@ define([
      *                                 volume, such that if (planeMask & (1 << planeIndex) === 0), for k < 31, then
      *                                 the parent (and therefore this) volume is completely inside plane[planeIndex]
      *                                 and that plane check can be skipped.
+     * @param {Function} [checkClipped] A function which takes the boundingVolume as a parameter, that if supplied,
+     *                                  will check to see if the tile has been entirely clipped by any tileset
+     *                                  clippingPlane.
      * @returns {Number} A plane mask as described above (which can be applied to this boundingVolume's children).
      *
      * @private
      */
-    CullingVolume.prototype.computeVisibilityWithPlaneMask = function(boundingVolume, parentPlaneMask) {
+    CullingVolume.prototype.computeVisibilityWithPlaneMask = function(boundingVolume, parentPlaneMask, checkClipped) {
         //>>includeStart('debug', pragmas.debug);
         if (!defined(boundingVolume)) {
             throw new DeveloperError('boundingVolume is required.');
@@ -161,6 +171,10 @@ define([
             return parentPlaneMask;
         }
 
+        if (defined(checkClipped) && checkClipped(boundingVolume)) {
+            return CullingVolume.MASK_OUTSIDE;
+        }
+
         // Start with MASK_INSIDE (all zeros) so that after the loop, the return value can be compared with MASK_INSIDE.
         // (Because if there are fewer than 31 planes, the upper bits wont be changed.)
         var mask = CullingVolume.MASK_INSIDE;
diff --git a/Source/Core/Plane.js b/Source/Core/Plane.js
index f52eea521e1..c8193f27448 100644
--- a/Source/Core/Plane.js
+++ b/Source/Core/Plane.js
@@ -3,13 +3,16 @@ define([
         './defined',
         './DeveloperError',
         './freezeObject',
-        './Math'
+        './Math',
+        './Matrix4'
     ], function(
         Cartesian3,
         defined,
         DeveloperError,
         freezeObject,
-        CesiumMath) {
+        CesiumMath,
+        Matrix4
+) {
     'use strict';
 
     /**
@@ -166,6 +169,34 @@ define([
         return Cartesian3.dot(plane.normal, point) + plane.distance;
     };
 
+    var scratchPosition = new Cartesian3();
+    /**
+     * Transforms the plane by the given transformation matrix.
+     *
+     * @param {Plane} plane The plane.
+     * @param {Matrix4} transform The transformation matrix.
+     * @param {Plane} [result] The object into which to store the result.
+     * @returns {Plane} The plane transformed by the given transformation matrix.
+     */
+    Plane.transformPlane = function(plane, transform, result) {
+        //>>includeStart('debug', pragmas.debug);
+        if (!defined(plane)) {
+            throw new DeveloperError('plane is required.');
+        }
+        if (!defined(transform)) {
+            throw new DeveloperError('transform is required.');
+        }
+        //>>includeEnd('debug');
+
+        Matrix4.multiplyByPointAsVector(transform, plane.normal, scratchNormal);
+        Cartesian3.normalize(scratchNormal, scratchNormal);
+
+        Cartesian3.multiplyByScalar(plane.normal, plane.distance, scratchPosition);
+        Matrix4.multiplyByPoint(transform, scratchPosition, scratchPosition);
+
+        return Plane.fromPointNormal(scratchPosition, scratchNormal, result);
+    };
+
     /**
      * A constant initialized to the XY plane passing through the origin, with normal in positive Z.
      *
diff --git a/Source/Scene/Cesium3DTile.js b/Source/Scene/Cesium3DTile.js
index 825bc5ad6af..aa93d7ae962 100644
--- a/Source/Scene/Cesium3DTile.js
+++ b/Source/Scene/Cesium3DTile.js
@@ -14,6 +14,7 @@ define([
         '../Core/loadArrayBuffer',
         '../Core/Matrix3',
         '../Core/Matrix4',
+        '../Core/Plane',
         '../Core/Rectangle',
         '../Core/Request',
         '../Core/RequestScheduler',
@@ -47,6 +48,7 @@ define([
         loadArrayBuffer,
         Matrix3,
         Matrix4,
+        Plane,
         Rectangle,
         Request,
         RequestScheduler,
@@ -323,6 +325,7 @@ define([
         this._debugViewerRequestVolume = undefined;
         this._debugColor = Color.fromRandom({ alpha : 1.0 });
         this._debugColorizeTiles = false;
+        this._debugClipped = false;
 
         this._commandsLength = 0;
 
@@ -735,6 +738,28 @@ define([
         return frameState.mode !== SceneMode.SCENE3D ? tile._contentBoundingVolume2D : tile._contentBoundingVolume;
     }
 
+
+    var scratchPlane = new Plane(Cartesian3.UNIT_X, 0.0);
+    function getCheckClippedFunction (tile) {
+        return function (boundingVolume) {
+            tile._debugClipped = false;
+
+            var planes = tile._tileset.clippingPlanes;
+            var length = planes.length;
+            for (var i = 0; i < length; ++i) {
+                var plane = planes[i];
+                Plane.transformPlane(plane, tile._tileset._root.computedTransform, scratchPlane);
+                if (boundingVolume.intersectPlane(scratchPlane) === Intersect.INSIDE) {
+                    tile._debugClipped = true;
+                    return true;
+                }
+            }
+
+            return false;
+        };
+    }
+
+
     /**
      * Determines whether the tile's bounding volume intersects the culling volume.
      *
@@ -747,7 +772,8 @@ define([
     Cesium3DTile.prototype.visibility = function(frameState, parentVisibilityPlaneMask) {
         var cullingVolume = frameState.cullingVolume;
         var boundingVolume = getBoundingVolume(this, frameState);
-        return cullingVolume.computeVisibilityWithPlaneMask(boundingVolume, parentVisibilityPlaneMask);
+
+        return cullingVolume.computeVisibilityWithPlaneMask(boundingVolume, parentVisibilityPlaneMask, getCheckClippedFunction(this));
     };
 
     /**
@@ -770,7 +796,7 @@ define([
         // tile's (not the content's) bounding volume intersects the culling volume?
         var cullingVolume = frameState.cullingVolume;
         var boundingVolume = getContentBoundingVolume(this, frameState);
-        return cullingVolume.computeVisibility(boundingVolume);
+        return cullingVolume.computeVisibility(boundingVolume, getCheckClippedFunction(this));
     };
 
     /**
@@ -940,7 +966,7 @@ define([
         var showVolume = tileset.debugShowBoundingVolume || (tileset.debugShowContentBoundingVolume && !hasContentBoundingVolume);
         if (showVolume) {
             if (!defined(tile._debugBoundingVolume)) {
-                var color = tile._finalResolution ? (hasContentBoundingVolume ? Color.WHITE : Color.RED) : Color.YELLOW;
+                var color = tile._finalResolution ? (hasContentBoundingVolume ? (tile._debugClipped ? Color.CYAN : Color.WHITE) : Color.RED) : Color.YELLOW;
                 tile._debugBoundingVolume = tile._boundingVolume.createDebugVolume(color);
             }
             tile._debugBoundingVolume.update(frameState);
diff --git a/Source/Scene/Model.js b/Source/Scene/Model.js
index 455b64046be..3654432cce2 100644
--- a/Source/Scene/Model.js
+++ b/Source/Scene/Model.js
@@ -31,6 +31,7 @@ define([
         '../Core/Matrix3',
         '../Core/Matrix4',
         '../Core/PixelFormat',
+        '../Core/Plane',
         '../Core/PrimitiveType',
         '../Core/Quaternion',
         '../Core/Queue',
@@ -108,6 +109,7 @@ define([
         Matrix3,
         Matrix4,
         PixelFormat,
+        Plane,
         PrimitiveType,
         Quaternion,
         Queue,
@@ -3312,7 +3314,7 @@ define([
         };
     }
 
-    var scratchCartesian = new Cartesian3();
+    var scratchPlane = new Plane(Cartesian3.UNIT_X, 0.0);
     var scratchMatrix = new Matrix4();
 
     function createClippingPlanesFunction(model, context) {
@@ -3327,11 +3329,11 @@ define([
             for (var i = 0; i < length; ++i) {
                 var plane = planes[i];
                 var packedPlane = packedPlanes[i];
-                Matrix4.multiplyByPointAsVector(scratchMatrix, plane.normal, packedPlane);
-                Cartesian3.normalize(packedPlane, packedPlane);
-                Cartesian3.multiplyByScalar(plane.normal, plane.distance, scratchCartesian);
-                Matrix4.multiplyByPoint(scratchMatrix, scratchCartesian, scratchCartesian);
-                packedPlane.w = Cartesian3.dot(packedPlane, scratchCartesian);
+
+                Plane.transformPlane(plane, scratchMatrix, scratchPlane);
+
+                Cartesian3.clone(scratchPlane.normal, packedPlane);
+                packedPlane.w = scratchPlane.distance;
             }
             return packedPlanes;
         };
diff --git a/Source/Scene/PointCloud3DTileContent.js b/Source/Scene/PointCloud3DTileContent.js
index 4280deb069a..d8cb531dc0f 100644
--- a/Source/Scene/PointCloud3DTileContent.js
+++ b/Source/Scene/PointCloud3DTileContent.js
@@ -15,6 +15,7 @@ define([
         '../Core/Matrix3',
         '../Core/Matrix4',
         '../Core/oneTimeWarning',
+        '../Core/Plane',
         '../Core/PrimitiveType',
         '../Core/RuntimeError',
         '../Core/Transforms',
@@ -50,6 +51,7 @@ define([
         Matrix3,
         Matrix4,
         oneTimeWarning,
+        Plane,
         PrimitiveType,
         RuntimeError,
         Transforms,
@@ -514,8 +516,8 @@ define([
             }
         }
 
-        var scratchCartesian = new Cartesian3();
-
+        var scratchPlane = new Plane(Cartesian3.UNIT_X, 0.0);
+        var scratchMatrix = new Matrix4();
         var uniformMap = {
             u_pointSizeAndTilesetTime : function() {
                 scratchPointSizeAndTilesetTime.x = content._pointSize;
@@ -539,10 +541,11 @@ define([
                     var plane = planes[i];
                     var packedPlane = packedPlanes[i];
 
-                    Matrix3.multiplyByVector(context.uniformState.normal, plane.normal, packedPlane);
-                    Cartesian3.multiplyByScalar(plane.normal, plane.distance, scratchCartesian);
-                    Matrix4.multiplyByPoint(context.uniformState.modelView3D, scratchCartesian, scratchCartesian);
-                    packedPlane.w = Cartesian3.dot(packedPlane, scratchCartesian);
+                    Matrix4.multiply(context.uniformState.view3D, content._modelMatrix, scratchMatrix);
+                    Plane.transformPlane(plane, scratchMatrix, scratchPlane);
+
+                    Cartesian3.clone(scratchPlane.normal, packedPlane);
+                    packedPlane.w = scratchPlane.distance;
                 }
                 return packedPlanes;
             }
diff --git a/Source/Shaders/Builtin/Functions/clipPlanes.glsl b/Source/Shaders/Builtin/Functions/clipPlanes.glsl
index 086f505d3ef..419990f1748 100644
--- a/Source/Shaders/Builtin/Functions/clipPlanes.glsl
+++ b/Source/Shaders/Builtin/Functions/clipPlanes.glsl
@@ -24,7 +24,7 @@ void czm_clipPlanes (vec4[czm_maxClippingPlanes] clippingPlanes, int clippingPla
             }
 
             clipNormal = clippingPlanes[i].xyz;
-            clipPosition = clippingPlanes[i].w * clipNormal;
+            clipPosition = -clippingPlanes[i].w * clipNormal;
             clipped = clipped || (dot(clipNormal, (position.xyz - clipPosition)) > czm_epsilon7);
         }