| // Copyright 2014 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. |
| |
| #include "cc/output/bsp_tree.h" |
| |
| #include <stddef.h> |
| |
| #include <deque> |
| #include <memory> |
| |
| #include "base/macros.h" |
| #include "cc/output/bsp_walk_action.h" |
| #include "cc/quads/draw_polygon.h" |
| #include "testing/gtest/include/gtest/gtest.h" |
| |
| namespace cc { |
| namespace { |
| |
| #define EXPECT_SORTED_LISTS_EQ(polygon_list, compare_list) \ |
| do { \ |
| EXPECT_EQ(polygon_list.size(), compare_list.size()); \ |
| for (unsigned int i = 0; i < polygon_list.size(); i++) { \ |
| EXPECT_EQ(polygon_list[i]->order_index(), compare_list[i]); \ |
| } \ |
| } while (false); |
| |
| #define INT_VECTOR_FROM_ARRAY(array) \ |
| std::vector<int>(array, array + arraysize(array)) |
| |
| #define CREATE_DRAW_POLYGON(vertex_vector, normal, polygon_id) \ |
| new DrawPolygon(NULL, vertex_vector, normal, polygon_id) |
| |
| class BspTreeTest { |
| public: |
| static void RunTest(std::deque<std::unique_ptr<DrawPolygon>>* test_polygons, |
| const std::vector<int>& compare_list) { |
| BspTree bsp_tree(test_polygons); |
| |
| std::vector<DrawPolygon*> sorted_list; |
| BspWalkActionToVector action_handler(&sorted_list); |
| bsp_tree.TraverseWithActionHandler(&action_handler); |
| |
| EXPECT_SORTED_LISTS_EQ(sorted_list, compare_list); |
| EXPECT_TRUE(VerifySidedness(bsp_tree.root())); |
| } |
| |
| static BspCompareResult SideCompare(const DrawPolygon& a, |
| const DrawPolygon& b) { |
| const float split_threshold = 0.05f; |
| bool pos = false; |
| bool neg = false; |
| for (const auto& pt : a.points()) { |
| float dist = b.SignedPointDistance(pt); |
| neg |= dist < -split_threshold; |
| pos |= dist > split_threshold; |
| } |
| if (pos && neg) |
| return BSP_SPLIT; |
| if (neg) |
| return BSP_BACK; |
| if (pos) |
| return BSP_FRONT; |
| double dot = gfx::DotProduct(a.normal(), b.normal()); |
| if ((dot >= 0.0f && a.order_index() >= b.order_index()) || |
| (dot <= 0.0f && a.order_index() <= b.order_index())) { |
| // The sign of the dot product of the normals along with document order |
| // determine which side it goes on, the vertices are ambiguous. |
| return BSP_COPLANAR_BACK; |
| } |
| return BSP_COPLANAR_FRONT; |
| } |
| |
| static bool VerifySidedness(const std::unique_ptr<BspNode>& node) { |
| // We check if both the front and back child nodes have geometry that is |
| // completely on the expected side of the current node. |
| bool front_ok = true; |
| bool back_ok = true; |
| if (node->back_child) { |
| // Make sure the back child lies entirely behind this node. |
| BspCompareResult result = |
| SideCompare(*(node->back_child->node_data), *(node->node_data)); |
| if (result != BSP_BACK) { |
| return false; |
| } |
| back_ok = VerifySidedness(node->back_child); |
| } |
| // Make sure the front child lies entirely in front of this node. |
| if (node->front_child) { |
| BspCompareResult result = |
| SideCompare(*(node->front_child->node_data), *(node->node_data)); |
| if (result != BSP_FRONT) { |
| return false; |
| } |
| front_ok = VerifySidedness(node->front_child); |
| } |
| if (!back_ok || !front_ok) { |
| return false; |
| } |
| |
| // Now we need to make sure our coplanar geometry is all actually coplanar. |
| for (size_t i = 0; i < node->coplanars_front.size(); i++) { |
| BspCompareResult result = |
| SideCompare(*(node->coplanars_front[i]), *(node->node_data)); |
| if (result != BSP_COPLANAR_FRONT) { |
| return false; |
| } |
| } |
| for (size_t i = 0; i < node->coplanars_back.size(); i++) { |
| BspCompareResult result = |
| SideCompare(*(node->coplanars_back[i]), *(node->node_data)); |
| if (result != BSP_COPLANAR_BACK) { |
| return false; |
| } |
| } |
| return true; |
| } |
| }; |
| |
| // Simple standing quads all parallel with each other, causing no splits. |
| TEST(BspTreeTest, NoSplit) { |
| std::vector<gfx::Point3F> vertices_a; |
| vertices_a.push_back(gfx::Point3F(0.0f, 10.0f, 0.0f)); |
| vertices_a.push_back(gfx::Point3F(0.0f, 0.0f, 0.0f)); |
| vertices_a.push_back(gfx::Point3F(10.0f, 0.0f, 0.0f)); |
| vertices_a.push_back(gfx::Point3F(10.0f, 10.0f, 0.0f)); |
| std::vector<gfx::Point3F> vertices_b; |
| vertices_b.push_back(gfx::Point3F(0.0f, 10.0f, -5.0f)); |
| vertices_b.push_back(gfx::Point3F(0.0f, 0.0f, -5.0f)); |
| vertices_b.push_back(gfx::Point3F(10.0f, 0.0f, -5.0f)); |
| vertices_b.push_back(gfx::Point3F(10.0f, 10.0f, -5.0f)); |
| std::vector<gfx::Point3F> vertices_c; |
| vertices_c.push_back(gfx::Point3F(0.0f, 10.0f, 5.0f)); |
| vertices_c.push_back(gfx::Point3F(0.0f, 0.0f, 5.0f)); |
| vertices_c.push_back(gfx::Point3F(10.0f, 0.0f, 5.0f)); |
| vertices_c.push_back(gfx::Point3F(10.0f, 10.0f, 5.0f)); |
| |
| std::unique_ptr<DrawPolygon> polygon_a( |
| CREATE_DRAW_POLYGON(vertices_a, gfx::Vector3dF(0.0f, 0.0f, 1.0f), 0)); |
| std::unique_ptr<DrawPolygon> polygon_b( |
| CREATE_DRAW_POLYGON(vertices_b, gfx::Vector3dF(0.0f, 0.0f, 1.0f), 1)); |
| std::unique_ptr<DrawPolygon> polygon_c( |
| CREATE_DRAW_POLYGON(vertices_c, gfx::Vector3dF(0.0f, 0.0f, 1.0f), 2)); |
| |
| std::deque<std::unique_ptr<DrawPolygon>> polygon_list; |
| polygon_list.push_back(std::move(polygon_a)); |
| polygon_list.push_back(std::move(polygon_b)); |
| polygon_list.push_back(std::move(polygon_c)); |
| |
| int compare_ids[] = {1, 0, 2}; |
| std::vector<int> compare_list = INT_VECTOR_FROM_ARRAY(compare_ids); |
| BspTreeTest::RunTest(&polygon_list, compare_list); |
| } |
| |
| // Basic two polygon split, can be viewed as a + from above. |
| TEST(BspTreeTest, BasicSplit) { |
| std::vector<gfx::Point3F> vertices_a; |
| vertices_a.push_back(gfx::Point3F(-5.0f, -5.0f, 0.0f)); |
| vertices_a.push_back(gfx::Point3F(-5.0f, 5.0f, 0.0f)); |
| vertices_a.push_back(gfx::Point3F(5.0f, 5.0f, 0.0f)); |
| vertices_a.push_back(gfx::Point3F(5.0f, -5.0f, 0.0f)); |
| std::vector<gfx::Point3F> vertices_b; |
| vertices_b.push_back(gfx::Point3F(0.0f, -5.0f, -5.0f)); |
| vertices_b.push_back(gfx::Point3F(0.0f, 5.0f, -5.0f)); |
| vertices_b.push_back(gfx::Point3F(0.0f, 5.0f, 5.0f)); |
| vertices_b.push_back(gfx::Point3F(0.0f, -5.0f, 5.0f)); |
| |
| std::unique_ptr<DrawPolygon> polygon_a( |
| CREATE_DRAW_POLYGON(vertices_a, gfx::Vector3dF(0.0f, 0.0f, 1.0f), 0)); |
| std::unique_ptr<DrawPolygon> polygon_b( |
| CREATE_DRAW_POLYGON(vertices_b, gfx::Vector3dF(-1.0f, 0.0f, 0.0f), 1)); |
| |
| std::deque<std::unique_ptr<DrawPolygon>> polygon_list; |
| polygon_list.push_back(std::move(polygon_a)); |
| polygon_list.push_back(std::move(polygon_b)); |
| |
| int compare_ids[] = {1, 0, 1}; |
| std::vector<int> compare_list = INT_VECTOR_FROM_ARRAY(compare_ids); |
| BspTreeTest::RunTest(&polygon_list, compare_list); |
| } |
| |
| // Same as above with the second quad offset so it doesn't intersect. One quad |
| // should be very clearly on one side of the other, and no splitting should |
| // occur. |
| TEST(BspTreeTest, QuadOffset) { |
| std::vector<gfx::Point3F> vertices_a; |
| vertices_a.push_back(gfx::Point3F(-5.0f, -5.0f, 0.0f)); |
| vertices_a.push_back(gfx::Point3F(-5.0f, 5.0f, 0.0f)); |
| vertices_a.push_back(gfx::Point3F(5.0f, 5.0f, 0.0f)); |
| vertices_a.push_back(gfx::Point3F(5.0f, -5.0f, 0.0f)); |
| std::vector<gfx::Point3F> vertices_b; |
| vertices_b.push_back(gfx::Point3F(0.0f, 5.0f, -15.0f)); |
| vertices_b.push_back(gfx::Point3F(0.0f, -5.0f, -15.0f)); |
| vertices_b.push_back(gfx::Point3F(0.0f, -5.0f, -10.0f)); |
| vertices_b.push_back(gfx::Point3F(0.0f, 5.0f, -10.0f)); |
| |
| std::unique_ptr<DrawPolygon> polygon_a( |
| CREATE_DRAW_POLYGON(vertices_a, gfx::Vector3dF(0.0f, 0.0f, 1.0f), 0)); |
| std::unique_ptr<DrawPolygon> polygon_b( |
| CREATE_DRAW_POLYGON(vertices_b, gfx::Vector3dF(-1.0f, 0.0f, 0.0f), 1)); |
| |
| std::deque<std::unique_ptr<DrawPolygon>> polygon_list; |
| polygon_list.push_back(std::move(polygon_a)); |
| polygon_list.push_back(std::move(polygon_b)); |
| |
| int compare_ids[] = {1, 0}; |
| std::vector<int> compare_list = INT_VECTOR_FROM_ARRAY(compare_ids); |
| BspTreeTest::RunTest(&polygon_list, compare_list); |
| } |
| |
| // Same as above, but this time we change the order in which the quads are |
| // inserted into the tree, causing one to actually cross the plane of the other |
| // and cause a split. |
| TEST(BspTreeTest, QuadOffsetSplit) { |
| std::vector<gfx::Point3F> vertices_a; |
| vertices_a.push_back(gfx::Point3F(-5.0f, -5.0f, 0.0f)); |
| vertices_a.push_back(gfx::Point3F(-5.0f, 5.0f, 0.0f)); |
| vertices_a.push_back(gfx::Point3F(5.0f, 5.0f, 0.0f)); |
| vertices_a.push_back(gfx::Point3F(5.0f, -5.0f, 0.0f)); |
| std::vector<gfx::Point3F> vertices_b; |
| vertices_b.push_back(gfx::Point3F(0.0f, -5.0f, -15.0f)); |
| vertices_b.push_back(gfx::Point3F(0.0f, 5.0f, -15.0f)); |
| vertices_b.push_back(gfx::Point3F(0.0f, 5.0f, -10.0f)); |
| vertices_b.push_back(gfx::Point3F(0.0f, -5.0f, -10.0f)); |
| |
| std::unique_ptr<DrawPolygon> polygon_a( |
| CREATE_DRAW_POLYGON(vertices_a, gfx::Vector3dF(0.0f, 0.0f, 1.0f), 0)); |
| std::unique_ptr<DrawPolygon> polygon_b( |
| CREATE_DRAW_POLYGON(vertices_b, gfx::Vector3dF(-1.0f, 0.0f, 0.0f), 1)); |
| |
| std::deque<std::unique_ptr<DrawPolygon>> polygon_list; |
| polygon_list.push_back(std::move(polygon_b)); |
| polygon_list.push_back(std::move(polygon_a)); |
| |
| int compare_ids[] = {0, 1, 0}; |
| std::vector<int> compare_list = INT_VECTOR_FROM_ARRAY(compare_ids); |
| BspTreeTest::RunTest(&polygon_list, compare_list); |
| } |
| |
| // In addition to what can be viewed as a + from above, another piece of |
| // geometry is inserted to cut these pieces right in the middle, viewed as |
| // a quad from overhead. |
| TEST(BspTreeTest, ThreeWaySplit) { |
| std::vector<gfx::Point3F> vertices_a; |
| vertices_a.push_back(gfx::Point3F(-5.0f, -5.0f, 0.0f)); |
| vertices_a.push_back(gfx::Point3F(-5.0f, 5.0f, 0.0f)); |
| vertices_a.push_back(gfx::Point3F(5.0f, 5.0f, 0.0f)); |
| vertices_a.push_back(gfx::Point3F(5.0f, -5.0f, 0.0f)); |
| std::vector<gfx::Point3F> vertices_b; |
| vertices_b.push_back(gfx::Point3F(0.0f, -5.0f, -5.0f)); |
| vertices_b.push_back(gfx::Point3F(0.0f, 5.0f, -5.0f)); |
| vertices_b.push_back(gfx::Point3F(0.0f, 5.0f, 5.0f)); |
| vertices_b.push_back(gfx::Point3F(0.0f, -5.0f, 5.0f)); |
| std::vector<gfx::Point3F> vertices_c; |
| vertices_c.push_back(gfx::Point3F(-5.0f, 0.0f, -5.0f)); |
| vertices_c.push_back(gfx::Point3F(-5.0f, 0.0f, 5.0f)); |
| vertices_c.push_back(gfx::Point3F(5.0f, 0.0f, 5.0f)); |
| vertices_c.push_back(gfx::Point3F(5.0f, 0.0f, -5.0f)); |
| |
| std::unique_ptr<DrawPolygon> polygon_a( |
| CREATE_DRAW_POLYGON(vertices_a, gfx::Vector3dF(0.0f, 0.0f, 1.0f), 0)); |
| std::unique_ptr<DrawPolygon> polygon_b( |
| CREATE_DRAW_POLYGON(vertices_b, gfx::Vector3dF(-1.0f, 0.0f, 0.0f), 1)); |
| std::unique_ptr<DrawPolygon> polygon_c( |
| CREATE_DRAW_POLYGON(vertices_c, gfx::Vector3dF(0.0f, 1.0f, 0.0f), 2)); |
| |
| std::deque<std::unique_ptr<DrawPolygon>> polygon_list; |
| polygon_list.push_back(std::move(polygon_a)); |
| polygon_list.push_back(std::move(polygon_b)); |
| polygon_list.push_back(std::move(polygon_c)); |
| |
| int compare_ids[] = {2, 1, 2, 0, 2, 1, 2}; |
| std::vector<int> compare_list = INT_VECTOR_FROM_ARRAY(compare_ids); |
| BspTreeTest::RunTest(&polygon_list, compare_list); |
| } |
| |
| // This test checks whether coplanar geometry, when inserted into the tree in |
| // order, comes back in the same order as it should. |
| TEST(BspTreeTest, Coplanar) { |
| std::vector<gfx::Point3F> vertices_a; |
| vertices_a.push_back(gfx::Point3F(-5.0f, -5.0f, 0.0f)); |
| vertices_a.push_back(gfx::Point3F(-5.0f, 5.0f, 0.0f)); |
| vertices_a.push_back(gfx::Point3F(5.0f, 5.0f, 0.0f)); |
| vertices_a.push_back(gfx::Point3F(5.0f, -5.0f, 0.0f)); |
| std::vector<gfx::Point3F> vertices_b; |
| vertices_b.push_back(gfx::Point3F(-4.0f, -4.0f, 0.0f)); |
| vertices_b.push_back(gfx::Point3F(-4.0f, 4.0f, 0.0f)); |
| vertices_b.push_back(gfx::Point3F(4.0f, 4.0f, 0.0f)); |
| vertices_b.push_back(gfx::Point3F(4.0f, -4.0f, 0.0f)); |
| std::vector<gfx::Point3F> vertices_c; |
| vertices_c.push_back(gfx::Point3F(-3.0f, -3.0f, 0.0f)); |
| vertices_c.push_back(gfx::Point3F(-3.0f, 3.0f, 0.0f)); |
| vertices_c.push_back(gfx::Point3F(3.0f, 3.0f, 0.0f)); |
| vertices_c.push_back(gfx::Point3F(3.0f, -3.0f, 0.0f)); |
| |
| std::unique_ptr<DrawPolygon> polygon_a( |
| CREATE_DRAW_POLYGON(vertices_a, gfx::Vector3dF(0.0f, 0.0f, 1.0f), 0)); |
| std::unique_ptr<DrawPolygon> polygon_b( |
| CREATE_DRAW_POLYGON(vertices_b, gfx::Vector3dF(0.0f, 0.0f, 1.0f), 1)); |
| std::unique_ptr<DrawPolygon> polygon_c( |
| CREATE_DRAW_POLYGON(vertices_c, gfx::Vector3dF(0.0f, 0.0f, 1.0f), 2)); |
| |
| std::unique_ptr<DrawPolygon> polygon_d = polygon_a->CreateCopy(); |
| std::unique_ptr<DrawPolygon> polygon_e = polygon_b->CreateCopy(); |
| std::unique_ptr<DrawPolygon> polygon_f = polygon_c->CreateCopy(); |
| |
| { |
| std::deque<std::unique_ptr<DrawPolygon>> polygon_list; |
| polygon_list.push_back(std::move(polygon_a)); |
| polygon_list.push_back(std::move(polygon_b)); |
| polygon_list.push_back(std::move(polygon_c)); |
| |
| int compare_ids[] = {0, 1, 2}; |
| std::vector<int> compare_list = INT_VECTOR_FROM_ARRAY(compare_ids); |
| BspTreeTest::RunTest(&polygon_list, compare_list); |
| } |
| |
| // Now check a different order and ensure we get that back as well |
| { |
| std::deque<std::unique_ptr<DrawPolygon>> polygon_list; |
| polygon_list.push_back(std::move(polygon_f)); |
| polygon_list.push_back(std::move(polygon_d)); |
| polygon_list.push_back(std::move(polygon_e)); |
| |
| int compare_ids[] = {0, 1, 2}; |
| std::vector<int> compare_list = INT_VECTOR_FROM_ARRAY(compare_ids); |
| BspTreeTest::RunTest(&polygon_list, compare_list); |
| } |
| } |
| |
| // A bunch of coplanar geometry should end up sharing a single node, and |
| // result in the final piece of geometry splitting into just two pieces on |
| // either side of the shared plane. |
| TEST(BspTreeTest, CoplanarSplit) { |
| std::vector<gfx::Point3F> vertices_a; |
| vertices_a.push_back(gfx::Point3F(-5.0f, -5.0f, 0.0f)); |
| vertices_a.push_back(gfx::Point3F(-5.0f, 5.0f, 0.0f)); |
| vertices_a.push_back(gfx::Point3F(5.0f, 5.0f, 0.0f)); |
| vertices_a.push_back(gfx::Point3F(5.0f, -5.0f, 0.0f)); |
| std::vector<gfx::Point3F> vertices_b; |
| vertices_b.push_back(gfx::Point3F(-4.0f, -4.0f, 0.0f)); |
| vertices_b.push_back(gfx::Point3F(-4.0f, 4.0f, 0.0f)); |
| vertices_b.push_back(gfx::Point3F(4.0f, 4.0f, 0.0f)); |
| vertices_b.push_back(gfx::Point3F(4.0f, -4.0f, 0.0f)); |
| std::vector<gfx::Point3F> vertices_c; |
| vertices_c.push_back(gfx::Point3F(-3.0f, -3.0f, 0.0f)); |
| vertices_c.push_back(gfx::Point3F(-3.0f, 3.0f, 0.0f)); |
| vertices_c.push_back(gfx::Point3F(3.0f, 3.0f, 0.0f)); |
| vertices_c.push_back(gfx::Point3F(3.0f, -3.0f, 0.0f)); |
| std::vector<gfx::Point3F> vertices_d; |
| vertices_d.push_back(gfx::Point3F(0.0f, -15.0f, -15.0f)); |
| vertices_d.push_back(gfx::Point3F(0.0f, 15.0f, -15.0f)); |
| vertices_d.push_back(gfx::Point3F(0.0f, 15.0f, 15.0f)); |
| vertices_d.push_back(gfx::Point3F(0.0f, -15.0f, 15.0f)); |
| |
| std::unique_ptr<DrawPolygon> polygon_a( |
| CREATE_DRAW_POLYGON(vertices_a, gfx::Vector3dF(0.0f, 0.0f, 1.0f), 0)); |
| std::unique_ptr<DrawPolygon> polygon_b( |
| CREATE_DRAW_POLYGON(vertices_b, gfx::Vector3dF(0.0f, 0.0f, 1.0f), 1)); |
| std::unique_ptr<DrawPolygon> polygon_c( |
| CREATE_DRAW_POLYGON(vertices_c, gfx::Vector3dF(0.0f, 0.0f, 1.0f), 2)); |
| std::unique_ptr<DrawPolygon> polygon_d( |
| CREATE_DRAW_POLYGON(vertices_d, gfx::Vector3dF(-1.0f, 0.0f, 0.0f), 3)); |
| |
| std::deque<std::unique_ptr<DrawPolygon>> polygon_list; |
| polygon_list.push_back(std::move(polygon_a)); |
| polygon_list.push_back(std::move(polygon_b)); |
| polygon_list.push_back(std::move(polygon_c)); |
| polygon_list.push_back(std::move(polygon_d)); |
| |
| int compare_ids[] = {3, 0, 1, 2, 3}; |
| std::vector<int> compare_list = INT_VECTOR_FROM_ARRAY(compare_ids); |
| BspTreeTest::RunTest(&polygon_list, compare_list); |
| } |
| |
| } // namespace |
| } // namespace cc |