aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorSven Göthel <[email protected]>2024-10-09 16:02:48 +0200
committerSven Göthel <[email protected]>2024-10-09 16:02:48 +0200
commit59825c2855ca69043eee282ba71a7d197bd2376f (patch)
tree5324e4cf81578d4041371387b373362fb7292941
parentcc9537ed29a895b465b11eec1de4d6212ff6470e (diff)
aabbox[23]f::intersects: Use possible branchless min/max approach, add perf-testHEADmaster
Signed-off-by: Sven Göthel <[email protected]>
-rw-r--r--include/jau/math/geom/aabbox2f.hpp50
-rw-r--r--include/jau/math/geom/aabbox3f.hpp49
-rw-r--r--test/test_int_math_perf01.cpp156
-rw-r--r--test/test_math_float_perf01.cpp191
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;
+ };
+}
+