// Copyright (C) 2017 Benjamin Kehlet // // This file is part of DOLFIN. // // DOLFIN is free software: you can redistribute it and/or modify // it under the terms of the GNU Lesser General Public License as published by // the Free Software Foundation, either version 3 of the License, or // (at your option) any later version. // // DOLFIN is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU Lesser General Public License for more details. // // You should have received a copy of the GNU Lesser General Public License // along with DOLFIN. If not, see . // // Unit tests for convex triangulation #include #include #include #include using namespace dolfin; namespace { bool pure_triangular(const std::vector>& triangulation, std::size_t dim) { for (const std::vector& tri : triangulation) { if (tri.size() != dim+1) return false; } return true; } bool has_degenerate(const std::vector>& triangulation, std::size_t dim) { for (const std::vector& tri : triangulation) { if (orient3d(tri[0], tri[1], tri[2], tri[3]) == 0) return true; } return false; } bool triangulation_selfintersects(const std::vector>& triangulation, std::size_t dim) { for (std::size_t i = 0; i < triangulation.size(); i++) { const auto& t1 = triangulation[i]; for (std::size_t j = i+1; j < triangulation.size(); j++) { const auto& t2 = triangulation[j]; // Count number of shared vertices std::size_t shared_vertices = 0; std::set t1_shared; std::set t2_shared; for (std::size_t v1 = 0; v1 < dim+1; v1++) { for (std::size_t v2 = 0; v2 < dim+1; v2++) { if (t1[v1] == t2[v2]) { shared_vertices++; t1_shared.insert(v1); t2_shared.insert(v2); } } } if (dim == 3) { if (shared_vertices == 0 && CollisionPredicates::collides_tetrahedron_tetrahedron_3d(t1[0], t1[1], t1[2], t1[3], t2[0], t2[1], t2[2], t2[3])) { return true; } else if (shared_vertices > 0) { for (std::size_t a = 0; a < dim+1; a++) { // None of the non-shared vertices should collide with the other tet if (t1_shared.count(a) == 0 && CollisionPredicates::collides_tetrahedron_point_3d(t2[0], t2[1], t2[2], t2[3], t1[a])) { return true; } if (t2_shared.count(a) == 0 && CollisionPredicates::collides_tetrahedron_point_3d(t1[0], t1[1], t1[2], t1[3], t2[a])) { return true; } } } } else if(dim == 2) { if (shared_vertices == 0 && CollisionPredicates::collides_triangle_triangle_2d(t1[0], t1[1], t1[2], t2[0], t2[1], t2[2])) { return true; } } } } return false; } //----------------------------------------------------------------------------- double triangulation_volume(const std::vector>& triangulation) { double vol = 0; for (const std::vector& tri : triangulation) { const Point& x0 = tri[0]; const Point& x1 = tri[1]; const Point& x2 = tri[2]; const Point& x3 = tri[3]; // Formula for volume from http://mathworld.wolfram.com const double v = (x0[0]*(x1[1]*x2[2] + x3[1]*x1[2] + x2[1]*x3[2] - x2[1]*x1[2] - x1[1]*x3[2] - x3[1]*x2[2]) - x1[0]*(x0[1]*x2[2] + x3[1]*x0[2] + x2[1]*x3[2] - x2[1]*x0[2] - x0[1]*x3[2] - x3[1]*x2[2]) + x2[0]*(x0[1]*x1[2] + x3[1]*x0[2] + x1[1]*x3[2] - x1[1]*x0[2] - x0[1]*x3[2] - x3[1]*x1[2]) - x3[0]*(x0[1]*x1[2] + x1[1]*x2[2] + x2[1]*x0[2] - x1[1]*x0[2] - x2[1]*x1[2] - x0[1]*x2[2])); vol += std::abs(v); } return vol/6; } } //----------------------------------------------------------------------------- TEST_CASE("Convex triangulation test") { SECTION("test trivial case]") { std::vector input = {{Point(0,0,0), Point(0,0,1), Point(0,1,0), Point(1,0,0)}}; std::vector> tri = ConvexTriangulation::triangulate_graham_scan_3d(input); std::size_t expected_size = 1; CHECK(tri.size() == expected_size); CHECK(triangulation_volume(tri) == Approx(1.0/6.0)); } SECTION("test trivial case 2") { std::vector input = {{Point(0,0,0), Point(0,0,1), Point(0,1,0), Point(0,1,1), Point(1,0,0), Point(1,0,1), Point(1,1,0), Point(1,1,1)}}; std::vector> tri = ConvexTriangulation::triangulate_graham_scan_3d(input); CHECK(pure_triangular(tri, 3)); CHECK_FALSE(has_degenerate(tri, 3)); CHECK_FALSE(triangulation_selfintersects(tri, 3)); CHECK(triangulation_volume(tri) == Approx(1.0)); } SECTION("test coplanar points") { std::vector input { Point(0, 0, 0), Point(0, 0, 1), Point(0, 1, 0), Point(0, 1, 1), Point(1, 0, 0), Point(1, 0, 1), Point(1, 1, 0), Point(1, 1, 1), Point(0.1, 0.1, 0)}; std::vector> tri = ConvexTriangulation::triangulate_graham_scan_3d(input); CHECK(pure_triangular(tri, 3)); CHECK_FALSE(has_degenerate(tri, 3)); CHECK_FALSE(triangulation_selfintersects(tri, 3)); CHECK(triangulation_volume(tri) == Approx(1.0)); } SECTION("test coplanar colinear points]") { std::vector input { Point(0, 0, 0), Point(0, 0, 1), Point(0, 1, 0), Point(0, 1, 1), Point(1, 0, 0), Point(1, 0, 1), Point(1, 1, 0), Point(1, 1, 1), Point(0, 0.1, 0)}; std::vector> tri = ConvexTriangulation::triangulate_graham_scan_3d(input); CHECK(pure_triangular(tri, 3)); CHECK_FALSE(has_degenerate(tri, 3)); CHECK_FALSE(triangulation_selfintersects(tri, 3)); CHECK(triangulation_volume(tri) == Approx(1.0)); } SECTION("test failing case") { std::vector input { Point(0.7, 0.6, 0.1), Point(0.7, 0.6, 0.5), Point(0.1, 0.1, 0.1), Point(0.8333333333333333, 0.8333333333333333, 0), Point(0.1, 0.15, 0.1), Point(0.1, 0.45, 0.1), Point(0.16, 0.15, 0.1), Point(0.61, 0.525, 0.1), Point(0.46, 0.6, 0.100000000000000006) }; std::vector> tri = ConvexTriangulation::triangulate_graham_scan_3d(input); CHECK(pure_triangular(tri, 3)); CHECK_FALSE(has_degenerate(tri, 3)); CHECK_FALSE(triangulation_selfintersects(tri, 3)); } SECTION("test failing case 2") { std::vector input { Point(0.7, 0.6, 0.5), Point(0.7, 0.1, 0.1), Point(0.8, 0, 0), Point (0.1, 0.1, 0.1), Point(0.16, 0.1, 0.1), Point(0.592, 0.1, 0.1), Point (0.16, 0.1, 0.14), Point (0.52, 0.1, 0.38), Point (0.7, 0.1, 0.38)}; std::vector> tri = ConvexTriangulation::triangulate_graham_scan_3d(input); CHECK(pure_triangular(tri, 3)); CHECK_FALSE(has_degenerate(tri, 3)); CHECK_FALSE(triangulation_selfintersects(tri, 3)); } SECTION("test failing case 3") { std::vector input { Point (0.495926, 0.512037, 0.144444), Point (0.376482, 0.519121, 0.284321), Point (0.386541, 0.599783, 0.0609262), Point (0.388086, 0.60059, 0.0607155), Point (0.7, 0.6, 0.5), Point (0.504965, 0.504965, 0.0447775), Point (0.833333, 0.833333, 0)}; std::vector> tri = ConvexTriangulation::triangulate_graham_scan_3d(input); CHECK(pure_triangular(tri, 3)); CHECK_FALSE(has_degenerate(tri, 3)); CHECK_FALSE(triangulation_selfintersects(tri, 3)); } } //-----------------------------------------------------------------------------