1 /** 2 inmath.aabb 3 4 Authors: David Herberth, Inochi2D Project 5 License: MIT 6 */ 7 module inmath.aabb; 8 9 private { 10 import inmath.linalg : Vector; 11 import inmath.math : almostEqual; 12 import inmath.util : TupleRange; 13 14 static import std.compiler; 15 } 16 17 18 /// Base template for all AABB-types. 19 /// Params: 20 /// type = all values get stored as this type 21 struct AABBT(type, uint dimension_ = 3) { 22 alias at = type; /// Holds the internal type of the AABB. 23 alias vec = Vector!(at, dimension_); /// Convenience alias to the corresponding vector type. 24 alias dimension = dimension_; 25 static assert(dimension > 0, "0 dimensional AABB don't exist."); 26 27 vec min = vec(cast(at)0.0); /// The minimum of the AABB (e.g. vec(0, 0, 0)). 28 vec max = vec(cast(at)0.0); /// The maximum of the AABB (e.g. vec(1, 1, 1)). 29 30 31 /// Gets a hash of this item 32 size_t toHash() const { return typeid(this).getHash(&this); } 33 34 @safe pure nothrow: 35 36 /// Constructs the AABB. 37 /// Params: 38 /// min = minimum of the AABB 39 /// max = maximum of the AABB 40 this(vec min, vec max) { 41 this.min = min; 42 this.max = max; 43 } 44 45 /// Constructs the AABB around N points (all points will be part of the AABB). 46 static AABBT fromPoints(vec[] points) { 47 AABBT res; 48 49 if(points.length == 0) { 50 return res; 51 } 52 53 res.min = points[0]; 54 res.max = points[0]; 55 foreach(v; points[1..$]) { 56 res.expand(v); 57 } 58 59 return res; 60 } 61 62 // Convenience function to get a dimension sized vector for unittests 63 version(unittest) 64 private static vec sizedVec(T)(T[] values){ 65 at[] ret; 66 foreach(i; 0..dimension) 67 ret ~= cast(at)values[i]; 68 return vec(ret); 69 } 70 71 unittest { 72 alias AABB = AABBT!(at, dimension); 73 74 AABB a = AABB(sizedVec([0.0, 1.0, 2.0, 3.0]), sizedVec([1.0, 2.0, 3.0, 4.0])); 75 assert(a.min == sizedVec([0.0, 1.0, 2.0, 3.0])); 76 assert(a.max == sizedVec([1.0, 2.0, 3.0, 4.0])); 77 78 a = AABB.fromPoints([ 79 sizedVec([1.0, 0.0, 1.0, 5.0]), 80 sizedVec([0.0, 2.0, 3.0, 3.0]), 81 sizedVec([1.0, 0.0, 4.0, 4.0])]); 82 assert(a.min == sizedVec([0.0, 0.0, 1.0, 3.0])); 83 assert(a.max == sizedVec([1.0, 2.0, 4.0, 5.0])); 84 85 a = AABB.fromPoints([sizedVec([1.0, 1.0, 1.0, 1.0]), sizedVec([2.0, 2.0, 2.0, 2.0])]); 86 assert(a.min == sizedVec([1.0, 1.0, 1.0, 1.0])); 87 assert(a.max == sizedVec([2.0, 2.0, 2.0, 2.0])); 88 } 89 90 /// Expands the AABB by another AABB. 91 void expand(AABBT b) { 92 foreach(i; TupleRange!(0, dimension)) { 93 if(min.vector[i] > b.min.vector[i]) min.vector[i] = b.min.vector[i]; 94 if(max.vector[i] < b.max.vector[i]) max.vector[i] = b.max.vector[i]; 95 } 96 } 97 98 /// Expands the AABB, so that $(I v) is part of the AABB. 99 void expand(vec v) { 100 foreach(i; TupleRange!(0, dimension)) { 101 if(min.vector[i] > v.vector[i]) min.vector[i] = v.vector[i]; 102 if(max.vector[i] < v.vector[i]) max.vector[i] = v.vector[i]; 103 } 104 } 105 106 unittest { 107 alias AABB = AABBT!(at, dimension); 108 109 AABB a = AABB(sizedVec([1.0, 1.0, 1.0, 1.0]), sizedVec([2.0, 4.0, 2.0, 4.0])); 110 AABB b = AABB(sizedVec([2.0, 1.0, 2.0, 1.0]), sizedVec([3.0, 3.0, 3.0, 3.0])); 111 112 AABB c; 113 c.expand(a); 114 c.expand(b); 115 assert(c.min == sizedVec([0.0, 0.0, 0.0, 0.0])); 116 assert(c.max == sizedVec([3.0, 4.0, 3.0, 4.0])); 117 118 c.expand(sizedVec([12.0, 2.0, 0.0, 1.0])); 119 assert(c.min == sizedVec([0.0, 0.0, 0.0, 0.0])); 120 assert(c.max == sizedVec([12.0, 4.0, 3.0, 4.0])); 121 } 122 123 /// Returns true if the AABBs intersect. 124 /// This also returns true if one AABB lies inside another. 125 bool intersects(AABBT box) const { 126 foreach(i; TupleRange!(0, dimension)) { 127 if(min.vector[i] >= box.max.vector[i] || max.vector[i] <= box.min.vector[i]) 128 return false; 129 } 130 return true; 131 } 132 133 unittest { 134 alias AABB = AABBT!(at, dimension); 135 136 assert(AABB(sizedVec([0.0, 0.0, 0.0, 0.0]), sizedVec([1.0, 1.0, 1.0, 1.0])).intersects( 137 AABB(sizedVec([0.5, 0.5, 0.5, 0.5]), sizedVec([3.0, 3.0, 3.0, 3.0])))); 138 139 assert(AABB(sizedVec([0.0, 0.0, 0.0, 0.0]), sizedVec([1.0, 1.0, 1.0, 1.0])).intersects( 140 AABB(sizedVec([0.5, 0.5, 0.5, 0.5]), sizedVec([1.7, 1.7, 1.7, 1.7])))); 141 142 assert(!AABB(sizedVec([0.0, 0.0, 0.0, 0.0]), sizedVec([1.0, 1.0, 1.0, 1.0])).intersects( 143 AABB(sizedVec([2.5, 2.5, 2.5, 2.5]), sizedVec([3.0, 3.0, 3.0, 3.0])))); 144 } 145 146 /// Returns the extent of the AABB (also sometimes called size). 147 @property vec extent() const { 148 return max - min; 149 } 150 151 /// Returns the half extent. 152 @property vec halfExtent() const { 153 return (max - min) / 2; 154 } 155 156 unittest { 157 alias AABB = AABBT!(at, dimension); 158 159 AABB a = AABB(sizedVec([0.0, 0.0, 0.0, 0.0]), sizedVec([10.0, 10.0, 10.0, 10.0])); 160 assert(a.extent == sizedVec([10.0, 10.0, 10.0, 10.0])); 161 assert(a.halfExtent == a.extent / 2); 162 163 AABB b = AABB(sizedVec([2.0, 2.0, 2.0, 2.0]), sizedVec([10.0, 10.0, 10.0, 10.0])); 164 assert(b.extent == sizedVec([8.0, 8.0, 8.0, 8.0])); 165 assert(b.halfExtent == b.extent / 2); 166 } 167 168 /// Returns the area of the AABB. 169 static if(dimension <= 3) { 170 @property real area() const { 171 vec e = extent; 172 173 static if(dimension == 1) { 174 return 0; 175 } else static if(dimension == 2) { 176 return e.x * e.y; 177 } else static if(dimension == 3) { 178 return 2.0 * (e.x * e.y + e.x * e.z + e.y * e.z); 179 } else { 180 static assert(dimension <= 3, "area() not supported for aabb of dimension > 3"); 181 } 182 } 183 184 unittest { 185 alias AABB = AABBT!(at, dimension); 186 AABB a = AABB(sizedVec([0.0, 0.0, 0.0, 0.0]), sizedVec([1.0, 1.0, 1.0, 1.0])); 187 switch (dimension) { 188 case 1: assert(a.area == 0); break; 189 case 2: assert(a.area == 1); break; 190 case 3: assert(a.area == 6); break; 191 default: assert(0); 192 } 193 194 195 AABB b = AABB(sizedVec([2.0, 2.0, 2.0, 2.0]), sizedVec([10.0, 10.0, 10.0, 10.0])); 196 switch (dimension) { 197 case 1: assert(b.area == 0); break; 198 case 2: assert(b.area == 64); break; 199 case 3: assert(b.area == 384); break; 200 default: assert(0); 201 } 202 203 AABB c = AABB(sizedVec([2.0, 4.0, 6.0, 6.0]), sizedVec([10.0, 10.0, 10.0, 10.0])); 204 switch (dimension) { 205 case 1: assert(c.area == 0); break; 206 case 2: assert(almostEqual(c.area, 48.0)); break; 207 case 3: assert(almostEqual(c.area, 208.0)); break; 208 default: assert(0); 209 } 210 } 211 212 } 213 214 /// Returns the center of the AABB. 215 @property vec center() const { 216 return (max + min) / 2; 217 } 218 219 unittest { 220 alias AABB = AABBT!(at, dimension); 221 222 AABB a = AABB(sizedVec([4.0, 4.0, 4.0, 4.0]), sizedVec([10.0, 10.0, 10.0, 10.0])); 223 assert(a.center == sizedVec([7.0, 7.0, 7.0, 7.0])); 224 } 225 226 /// Returns all vertices of the AABB, basically one vec per corner. 227 @property vec[] vertices() const { 228 vec[] res; 229 res.length = 2 ^^ dimension; 230 foreach(i; TupleRange!(0, 2^^dimension)) { 231 foreach(dim ; TupleRange!(0, dimension)) { 232 res[i].vector[dim] = (i & (1 << dim)) ? max.vector[dim] : min.vector[dim]; 233 } 234 } 235 return res; 236 } 237 238 static if(std.compiler.version_major > 2 || std.compiler.version_minor >= 69) unittest { 239 import std.algorithm.comparison : isPermutation; 240 alias AABB = AABBT!(at, dimension); 241 242 AABB a = AABB(sizedVec([1.0, 1.0, 1.0, 1.0]), sizedVec([2.0, 2.0, 2.0, 2.0])); 243 switch (dimension) { 244 case 1: assert(isPermutation(a.vertices, [ 245 sizedVec([1.0]), 246 sizedVec([2.0]), 247 ])); 248 break; 249 case 2: assert(isPermutation(a.vertices, [ 250 sizedVec([1.0, 1.0]), 251 sizedVec([1.0, 2.0]), 252 sizedVec([2.0, 1.0]), 253 sizedVec([2.0, 2.0]), 254 ])); 255 break; 256 case 3: assert(isPermutation(a.vertices, [ 257 sizedVec([1.0, 1.0, 1.0]), 258 sizedVec([1.0, 2.0, 1.0]), 259 sizedVec([2.0, 1.0, 1.0]), 260 sizedVec([2.0, 2.0, 1.0]), 261 sizedVec([1.0, 1.0, 2.0]), 262 sizedVec([1.0, 2.0, 2.0]), 263 sizedVec([2.0, 1.0, 2.0]), 264 sizedVec([2.0, 2.0, 2.0]), 265 ])); 266 break; 267 case 4: assert(isPermutation(a.vertices, [ 268 sizedVec([1.0, 1.0, 1.0, 1.0]), 269 sizedVec([1.0, 2.0, 1.0, 1.0]), 270 sizedVec([2.0, 1.0, 1.0, 1.0]), 271 sizedVec([2.0, 2.0, 1.0, 1.0]), 272 sizedVec([1.0, 1.0, 2.0, 1.0]), 273 sizedVec([1.0, 2.0, 2.0, 1.0]), 274 sizedVec([2.0, 1.0, 2.0, 1.0]), 275 sizedVec([2.0, 2.0, 2.0, 1.0]), 276 sizedVec([1.0, 1.0, 1.0, 2.0]), 277 sizedVec([1.0, 2.0, 1.0, 2.0]), 278 sizedVec([2.0, 1.0, 1.0, 2.0]), 279 sizedVec([2.0, 2.0, 1.0, 2.0]), 280 sizedVec([1.0, 1.0, 2.0, 2.0]), 281 sizedVec([1.0, 2.0, 2.0, 2.0]), 282 sizedVec([2.0, 1.0, 2.0, 2.0]), 283 sizedVec([2.0, 2.0, 2.0, 2.0]), 284 ])); 285 break; 286 default: assert(0); 287 } 288 } 289 290 bool opEquals(AABBT other) const { 291 return other.min == min && other.max == max; 292 } 293 294 unittest { 295 alias AABB = AABBT!(at, dimension); 296 assert(AABB(sizedVec([1.0, 12.0, 14.0, 16.0]), sizedVec([33.0, 222.0, 342.0, 1231.0])) == 297 AABB(sizedVec([1.0, 12.0, 14.0, 16.0]), sizedVec([33.0, 222.0, 342.0, 1231.0]))); 298 } 299 } 300 301 alias AABB3 = AABBT!(float, 3); 302 alias AABB2 = AABBT!(float, 2); 303 304 alias AABB = AABB3; 305 306 @("AABB") 307 unittest { 308 import inmath.util : TypeTuple; 309 alias Types = TypeTuple!(ubyte, byte, short, ushort, int, uint, float, double); 310 foreach(type; Types) 311 { 312 foreach(dim; TupleRange!(1, 5)) 313 { 314 { 315 alias aabbTestType = AABBT!(type,dim); 316 auto instance = AABBT!(type,dim)(); 317 } 318 } 319 } 320 }