WIP BSP Tree for 3D Layer Sorting

cc/output/bsp_controller.h

Index: cc/output/bsp_controller.h
diff --git a/cc/output/bsp_controller.h b/cc/output/bsp_controller.h
new file mode 100644
index 0000000000000000000000000000000000000000..63235498d8e10194baad8fc6efb1d9b54a344c17
--- /dev/null
+++ b/cc/output/bsp_controller.h
@@ -0,0 +1,47 @@
+// Copyright 2013 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef CC_OUTPUT_BSP_CONTROLLER_H_
+#define CC_OUTPUT_BSP_CONTROLLER_H_
+
+#include "cc/output/bsp_compare_result.h"
+#include "cc/quads/draw_polygon.h"
+
+namespace cc {
+
+enum ViewCompareResult { IN_FRONT, BEHIND };

[Ian Vollick, 2014/07/16 20:54:32]

If we treat the camera plane as a splitting plane, can we use bsp compare result
rather than yet another enum? (There are 3, very similar enums in this patch. It
would be nice to have 1).

[troyhildebrandt, 2014/07/18 21:48:25]

Done.

+
+// Specialization of the BSP Controller abstract class that deals specifically
+// with DrawPolygons
+class BspController {
+ public:
+  BspController(float compare_thresh, float split_thresh)

[Ian Vollick, 2014/07/16 20:54:32]

Could they be static constants in the cc file rather than parameters?

[troyhildebrandt, 2014/07/18 21:48:25]

Done.

+      : compare_threshold_(compare_thresh), split_threshold_(split_thresh) {}
+
+  // Returns whether or not nodeA is on one or the other side of nodeB,
+  // coplanar, or whether it crosses nodeB's plane and needs to be split
+  BspCompareResult GetNodePositionRelative(const DrawPolygon& node_a,

[Ian Vollick, 2014/07/16 20:54:32]

Perhaps this could be static if the two thresholds weren't params?

[troyhildebrandt, 2014/07/18 21:48:25]

Done.

+                                           const DrawPolygon& node_b) const;
+  // Returns whether or not our viewer is in front of or behind the plane
+  // defined by this polygon/node
+  ViewCompareResult GetCameraPositionRelative(const DrawPolygon& node) const;
+  bool SplitPolygon(scoped_ptr<DrawPolygon> polygon,
+                    const DrawPolygon& splitter,
+                    scoped_ptr<DrawPolygon>* front,
+                    scoped_ptr<DrawPolygon>* back) const;

[Ian Vollick, 2014/07/16 20:54:32]

Ditto.

[troyhildebrandt, 2014/07/18 21:48:25]

Done.

+
+  // This heuristic uses the surface area of the polygon to determine whether
+  // or not a polygon is a good splitter. The idea is that if a polygon is
+  // larger, it is more likely to cross the planes of many other polygons,
+  // so using it as a splitter instead avoids many unnecessary splits.

[Ian Vollick, 2014/07/16 20:54:32]

Is this a common heuristic?

[troyhildebrandt, 2014/07/18 21:48:25]

I'm not certain if it is, it probably wouldn't hurt to make it a little more
intelligent to further improve performance.

+  virtual float SplitWeight(const DrawPolygon& polygon);
+
+ private:
+  float compare_threshold_;
+  float split_threshold_;
+};
+
+}  // namespace cc
+
+#endif  // CC_OUTPUT_BSP_CONTROLLER_H_