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