diff options
author | Sven Göthel <[email protected]> | 2024-10-09 16:02:48 +0200 |
---|---|---|
committer | Sven Göthel <[email protected]> | 2024-10-09 16:02:48 +0200 |
commit | 59825c2855ca69043eee282ba71a7d197bd2376f (patch) | |
tree | 5324e4cf81578d4041371387b373362fb7292941 | |
parent | cc9537ed29a895b465b11eec1de4d6212ff6470e (diff) |
Signed-off-by: Sven Göthel <[email protected]>
-rw-r--r-- | include/jau/math/geom/aabbox2f.hpp | 50 | ||||
-rw-r--r-- | include/jau/math/geom/aabbox3f.hpp | 49 | ||||
-rw-r--r-- | test/test_int_math_perf01.cpp | 156 | ||||
-rw-r--r-- | test/test_math_float_perf01.cpp | 191 |
4 files changed, 393 insertions, 53 deletions
diff --git a/include/jau/math/geom/aabbox2f.hpp b/include/jau/math/geom/aabbox2f.hpp index 392e22e..6d7e0a0 100644 --- a/include/jau/math/geom/aabbox2f.hpp +++ b/include/jau/math/geom/aabbox2f.hpp @@ -1,25 +1,12 @@ /* * Author: Sven Gothel <[email protected]> - * Copyright (c) 2022-2024 Gothel Software e.K. + * Copyright Gothel Software e.K. * - * Permission is hereby granted, free of charge, to any person obtaining - * a copy of this software and associated documentation files (the - * "Software"), to deal in the Software without restriction, including - * without limitation the rights to use, copy, modify, merge, publish, - * distribute, sublicense, and/or sell copies of the Software, and to - * permit persons to whom the Software is furnished to do so, subject to - * the following conditions: + * SPDX-License-Identifier: MIT * - * The above copyright notice and this permission notice shall be - * included in all copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, - * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF - * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND - * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE - * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION - * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION - * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. + * This Source Code Form is subject to the terms of the MIT License + * If a copy of the MIT was not distributed with this file, + * you can obtain one at https://opensource.org/license/mit/. */ #ifndef JAU_AABBOX2F_HPP_ #define JAU_AABBOX2F_HPP_ @@ -151,8 +138,8 @@ namespace jau::math::geom { * @return true if {x, y} belongs to (low.x, high.x) and y belong to (low.y, high.y) */ bool contains(const float x, const float y) const noexcept { - return !( x<bl.x || x>tr.x || - y<bl.y || y>tr.y ); + return bl.x<=x && x<=tr.x && + bl.y<=y && y<=tr.y; } /** @@ -162,10 +149,18 @@ namespace jau::math::geom { bool contains(const Point2f& p) const noexcept { return contains(p.x, p.y); } bool intersects(const AABBox2f& o) const noexcept { - return !( tr.x < o.bl.x || - tr.y < o.bl.y || - bl.x > o.tr.x || - bl.y > o.tr.y ); + /** + * Traditional boolean equation leads to multiple branches, + * using max/min approach allowing for branch-less optimizations. + * + return !( tr.x < o.bl.x || + tr.y < o.bl.y || + bl.x > o.tr.x || + bl.y > o.tr.y ); + */ + const Point2f lo = max(bl, o.bl); + const Point2f hi = min(tr, o.tr); + return lo.x <= hi.x && lo.y <= hi.y; } #if 0 @@ -177,6 +172,13 @@ namespace jau::math::geom { } #endif + /** Returns whether this aabbox2f fully contains given aabbox2f. */ + bool contains(const AABBox2f& o) const noexcept { + return tr.x >= o.tr.x && + tr.y >= o.tr.y && + bl.x <= o.bl.x && + bl.y <= o.bl.y; + } std::string toString() const noexcept { return "aabb[bl " + bl.toString() + ", tr " + tr.toString() + diff --git a/include/jau/math/geom/aabbox3f.hpp b/include/jau/math/geom/aabbox3f.hpp index e827e23..08bdf37 100644 --- a/include/jau/math/geom/aabbox3f.hpp +++ b/include/jau/math/geom/aabbox3f.hpp @@ -1,25 +1,12 @@ /* * Author: Sven Gothel <[email protected]> - * Copyright (c) 2022-2024 Gothel Software e.K. + * Copyright Gothel Software e.K. * - * Permission is hereby granted, free of charge, to any person obtaining - * a copy of this software and associated documentation files (the - * "Software"), to deal in the Software without restriction, including - * without limitation the rights to use, copy, modify, merge, publish, - * distribute, sublicense, and/or sell copies of the Software, and to - * permit persons to whom the Software is furnished to do so, subject to - * the following conditions: + * SPDX-License-Identifier: MIT * - * The above copyright notice and this permission notice shall be - * included in all copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, - * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF - * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND - * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE - * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION - * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION - * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. + * This Source Code Form is subject to the terms of the MIT License + * If a copy of the MIT was not distributed with this file, + * you can obtain one at https://opensource.org/license/mit/. */ #ifndef JAU_AABBOX3F_HPP_ #define JAU_AABBOX3F_HPP_ @@ -375,9 +362,9 @@ namespace jau::math::geom { * @return true if {x, y, z} belongs to {low, high} */ bool contains(const float x, const float y, const float z) const noexcept { - return !( x<m_lo.x || x>m_hi.x || - y<m_lo.y || y>m_hi.y || - z<m_lo.z || z>m_hi.z ); + return m_lo.x<=x && x<=m_hi.x && + m_lo.y<=y && y<=m_hi.y && + m_lo.z<=z && z<=m_hi.z; } /** @@ -388,12 +375,20 @@ namespace jau::math::geom { /** Returns whether this aabbox3f intersects (partially contains) given aabbox3f. */ bool intersects(const AABBox3f& o) const noexcept { - return !( m_hi.x < o.m_lo.x || - m_hi.y < o.m_lo.y || - m_hi.z < o.m_lo.z || - m_lo.x > o.m_hi.x || - m_lo.y > o.m_hi.y || - m_lo.z > o.m_hi.z ); + /** + * Traditional boolean equation leads to multiple branches, + * using max/min approach allowing for branch-less optimizations. + * + return !( m_hi.x < o.m_lo.x || + m_hi.y < o.m_lo.y || + m_hi.z < o.m_lo.z || + m_lo.x > o.m_hi.x || + m_lo.y > o.m_hi.y || + m_lo.z > o.m_hi.z ); + */ + const Point3f lo = max(m_lo, o.m_lo); + const Point3f hi = min(m_hi, o.m_hi); + return lo.x <= hi.x && lo.y <= hi.y && lo.z <= hi.z; } /** Returns whether this aabbox3f fully contains given aabbox3f. */ diff --git a/test/test_int_math_perf01.cpp b/test/test_int_math_perf01.cpp index 1ffb315..b2bf88b 100644 --- a/test/test_int_math_perf01.cpp +++ b/test/test_int_math_perf01.cpp @@ -21,14 +21,13 @@ * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ -#include <thread> #include <cassert> -#include <cinttypes> #include <cstring> #include <jau/test/catch2_ext.hpp> #include <jau/int_math.hpp> +#include <jau/math/vec2i.hpp> using namespace jau; using namespace jau::int_literals; @@ -90,3 +89,156 @@ TEST_CASE( "Int Math Bench 03a", "[ct_min][ct_max][benchmark][arithmetic][math]" REQUIRE( INT32_MIN+1== jau::ct_max( INT32_MIN+1, INT32_MIN ) ); }; } + +using namespace jau::math; + +struct AABBox { + Point2i lo, hi; + + bool __attribute__ ((noinline)) + intersects1a(const AABBox& o) const + { + return hi.x >= o.lo.x && + hi.y >= o.lo.y && + lo.x <= o.hi.x && + lo.y <= o.hi.y; + } + bool __attribute__ ((noinline)) + intersects1b(const AABBox& o) const + { + return !( hi.x < o.lo.x || + hi.y < o.lo.y || + lo.x > o.hi.x || + lo.y > o.hi.y ); + } + bool __attribute__ ((noinline)) + intersects1c(const AABBox& o) const + { + const Point2i lo_ = max(lo, o.lo); + const Point2i hi_ = min(hi, o.hi); + return lo_.x <= hi_.x && lo_.y <= hi_.y; + } + + bool intersects2a(const AABBox& o) const + { + return hi.x >= o.lo.x && + hi.y >= o.lo.y && + lo.x <= o.hi.x && + lo.y <= o.hi.y; + } + bool intersects2b(const AABBox& o) const + { + return !( hi.x < o.lo.x || + hi.y < o.lo.y || + lo.x > o.hi.x || + lo.y > o.hi.y ); + } + bool intersects2c(const AABBox& o) const + { + const Point2i lo_ = max(lo, o.lo); + const Point2i hi_ = min(hi, o.hi); + return lo_.x <= hi_.x && lo_.y <= hi_.y; + } +}; + +std::ostream& operator<<(std::ostream& out, const AABBox& v) noexcept { + return out << "aabb[bl " << v.lo << ", tr " << v.hi << "]"; +} + +#include <random> + +TEST_CASE( "Int Math Bench 04a", "[intersect][benchmark][arithmetic][math]" ) { + std::mt19937 rng; + int32_t seed_val=0; + rng.seed(seed_val); + std::uniform_int_distribution<int32_t> rint(0,50); + + const int loops = catch_auto_run ? 1000 : 1000000; + size_t isect_count=0; + std::vector<AABBox> va, vb; + for(int i=0; i<loops; ++i) { + Point2i lo(rint(rng), rint(rng)); + Point2i hi(lo.x+rint(rng), lo.y+rint(rng)); + AABBox a { lo, hi }; + lo = Point2i(rint(rng), rint(rng)); + hi = Point2i(lo.x+rint(rng), lo.y+rint(rng)); + AABBox b { lo, hi }; + va.push_back(a); + vb.push_back(b); + bool i1a = a.intersects1a(b); + bool i1b = a.intersects1b(b); + bool i1c = a.intersects1c(b); + if( i1a ) { + ++isect_count; + } + // std::cout << "# " << i << std::endl; + // std::cout << "A: " << a << std::endl; + // std::cout << "B: " << b << ", i " << i1a << std::endl; + REQUIRE( i1a == i1b ); + REQUIRE( i1a == i1c ); + // std::cout << std::endl; + bool i2a = a.intersects2a(b); + bool i2b = a.intersects2b(b); + bool i2c = a.intersects2c(b); + REQUIRE( i1a == i2a ); + REQUIRE( i2a == i2b ); + REQUIRE( i2a == i2c ); + } + std::cout << "isect_count " << isect_count << "/" << va.size() << ", " << 100.0f*( (float)isect_count / (float)va.size() ) << "%" << std::endl; + + BENCHMARK("Intersect1a Benchmark") { + size_t r = 0; + for(size_t i = 0; i < va.size(); ++i) { + AABBox a = va[i]; + AABBox b = vb[i]; + r += a.intersects1a(b) ? 10 : 1; + } + return r; + }; + BENCHMARK("Intersect1b Benchmark") { + size_t r = 0; + for(size_t i = 0; i < va.size(); ++i) { + AABBox a = va[i]; + AABBox b = vb[i]; + r += a.intersects1b(b) ? 10 : 1; + } + return r; + }; + BENCHMARK("Intersect1c Benchmark") { + size_t r = 0; + for(size_t i = 0; i < va.size(); ++i) { + AABBox a = va[i]; + AABBox b = vb[i]; + r += a.intersects1c(b) ? 10 : 1; + } + return r; + }; + BENCHMARK("Intersect2a Benchmark") { + size_t r = 0; + for(size_t i = 0; i < va.size(); ++i) { + AABBox a = va[i]; + AABBox b = vb[i]; + r += a.intersects2a(b) ? 10 : 1; + } + return r; + }; + BENCHMARK("Intersect2b Benchmark") { + size_t r = 0; + for(size_t i = 0; i < va.size(); ++i) { + AABBox a = va[i]; + AABBox b = vb[i]; + r += a.intersects2b(b) ? 10 : 1; + } + return r; + }; + BENCHMARK("Intersect2c Benchmark") { + size_t r = 0; + for(size_t i = 0; i < va.size(); ++i) { + AABBox a = va[i]; + AABBox b = vb[i]; + r += a.intersects2c(b) ? 10 : 1; + } + return r; + }; +} + diff --git a/test/test_math_float_perf01.cpp b/test/test_math_float_perf01.cpp new file mode 100644 index 0000000..6e99674 --- /dev/null +++ b/test/test_math_float_perf01.cpp @@ -0,0 +1,191 @@ +/* + * Author: Sven Gothel <[email protected]> + * Copyright Gothel Software e.K. + * + * SPDX-License-Identifier: MIT + * + * This Source Code Form is subject to the terms of the MIT License + * If a copy of the MIT was not distributed with this file, + * you can obtain one at https://opensource.org/license/mit/. + */ +#include <cassert> +#include <cstring> + +#include <jau/math/geom/aabbox2f.hpp> +#include <jau/test/catch2_ext.hpp> + +#include <jau/math/vec2f.hpp> + +using namespace jau; +using namespace jau::int_literals; + +using namespace jau::math; +using namespace jau::math::geom; + +struct AABBox { + Point2f lo, hi; + + bool __attribute__ ((noinline)) + intersects1a(const AABBox& o) const + { + return hi.x >= o.lo.x && + hi.y >= o.lo.y && + lo.x <= o.hi.x && + lo.y <= o.hi.y; + } + bool __attribute__ ((noinline)) + intersects1b(const AABBox& o) const + { + return !( hi.x < o.lo.x || + hi.y < o.lo.y || + lo.x > o.hi.x || + lo.y > o.hi.y ); + } + bool __attribute__ ((noinline)) + intersects1c(const AABBox& o) const + { + const Point2f lo_ = max(lo, o.lo); + const Point2f hi_ = min(hi, o.hi); + return lo_.x <= hi_.x && lo_.y <= hi_.y; + } + + bool intersects2a(const AABBox& o) const + { + return hi.x >= o.lo.x && + hi.y >= o.lo.y && + lo.x <= o.hi.x && + lo.y <= o.hi.y; + } + bool intersects2b(const AABBox& o) const + { + return !( hi.x < o.lo.x || + hi.y < o.lo.y || + lo.x > o.hi.x || + lo.y > o.hi.y ); + } + bool intersects2c(const AABBox& o) const + { + const Point2f lo_ = max(lo, o.lo); + const Point2f hi_ = min(hi, o.hi); + return lo_.x <= hi_.x && lo_.y <= hi_.y; + } +}; + +std::ostream& operator<<(std::ostream& out, const AABBox& v) noexcept { + return out << "aabb[bl " << v.lo << ", tr " << v.hi << "]"; +} + +#include <random> + +TEST_CASE( "Float Math Bench 04a", "[intersect][benchmark][arithmetic][math]" ) { + std::mt19937 rng; + int32_t seed_val=0; + rng.seed(seed_val); + std::uniform_int_distribution<int32_t> rint(0,50); + + const int loops = catch_auto_run ? 1000 : 1000000; + size_t isect_count=0; + std::vector<AABBox2f> va0, vb0; + std::vector<AABBox> va, vb; + for(int i=0; i<loops; ++i) { + Point2f lo((float)rint(rng), (float)rint(rng)); + Point2f hi(lo.x+(float)rint(rng), lo.y+(float)rint(rng)); + AABBox a { lo, hi }; + AABBox2f a0 { lo, hi }; + lo = Point2f((float)rint(rng), (float)rint(rng)); + hi = Point2f(lo.x+(float)rint(rng), lo.y+(float)rint(rng)); + AABBox2f b0 { lo, hi }; + AABBox b { lo, hi }; + va0.push_back(a0); + vb0.push_back(b0); + va.push_back(a); + vb.push_back(b); + bool i0 = a0.intersects(b0); + bool i1a = a.intersects1a(b); + bool i1b = a.intersects1b(b); + bool i1c = a.intersects1c(b); + if( i1a ) { + ++isect_count; + } + // std::cout << "# " << i << std::endl; + // std::cout << "A: " << a << std::endl; + // std::cout << "B: " << b << ", i " << i1a << std::endl; + REQUIRE( i1a == i1b ); + REQUIRE( i1a == i1c ); + REQUIRE( i1a == i0 ); + // std::cout << std::endl; + bool i2a = a.intersects2a(b); + bool i2b = a.intersects2b(b); + bool i2c = a.intersects2c(b); + REQUIRE( i1a == i2a ); + REQUIRE( i2a == i2b ); + REQUIRE( i2a == i2c ); + REQUIRE( i2a == i0 ); + } + std::cout << "isect_count " << isect_count << "/" << va.size() << ", " << 100.0f*( (float)isect_count / (float)va.size() ) << "%" << std::endl; + + BENCHMARK("Intersect0 Benchmark") { + size_t r = 0; + for(size_t i = 0; i < va0.size(); ++i) { + AABBox2f a = va0[i]; + AABBox2f b = vb0[i]; + r += a.intersects(b) ? 10 : 1; + } + return r; + }; + BENCHMARK("Intersect1a Benchmark") { + size_t r = 0; + for(size_t i = 0; i < va.size(); ++i) { + AABBox a = va[i]; + AABBox b = vb[i]; + r += a.intersects1a(b) ? 10 : 1; + } + return r; + }; + BENCHMARK("Intersect1b Benchmark") { + size_t r = 0; + for(size_t i = 0; i < va.size(); ++i) { + AABBox a = va[i]; + AABBox b = vb[i]; + r += a.intersects1b(b) ? 10 : 1; + } + return r; + }; + BENCHMARK("Intersect1c Benchmark") { + size_t r = 0; + for(size_t i = 0; i < va.size(); ++i) { + AABBox a = va[i]; + AABBox b = vb[i]; + r += a.intersects1c(b) ? 10 : 1; + } + return r; + }; + BENCHMARK("Intersect2a Benchmark") { + size_t r = 0; + for(size_t i = 0; i < va.size(); ++i) { + AABBox a = va[i]; + AABBox b = vb[i]; + r += a.intersects2a(b) ? 10 : 1; + } + return r; + }; + BENCHMARK("Intersect2b Benchmark") { + size_t r = 0; + for(size_t i = 0; i < va.size(); ++i) { + AABBox a = va[i]; + AABBox b = vb[i]; + r += a.intersects2b(b) ? 10 : 1; + } + return r; + }; + BENCHMARK("Intersect2c Benchmark") { + size_t r = 0; + for(size_t i = 0; i < va.size(); ++i) { + AABBox a = va[i]; + AABBox b = vb[i]; + r += a.intersects2c(b) ? 10 : 1; + } + return r; + }; +} + |