1 /** 2 * Copyright: Copyright (C) 2018 Gabriel Gheorghe, All Rights Reserved 3 * Authors: $(Gabriel Gheorghe) 4 * License: $(LINK2 https://www.gnu.org/licenses/gpl-3.0.txt, GNU GENERAL PUBLIC LICENSE Version 3, 29 June 2007) 5 * Source: $(LINK2 https://github.com/GabyForceQ/LibertyEngine/blob/master/source/liberty/math/shapes.d, _shapes.d) 6 * Documentation: 7 * Coverage: 8 */ 9 module liberty.math.shapes; 10 import std.traits : isFloatingPoint; 11 import liberty.math.vector : Vector; 12 import liberty.math.box : Box; 13 /// 14 struct Segment(T, int N) if (N == 2 || N == 3) { 15 /// 16 alias PointType = Vector!(T, N); 17 /// 18 PointType a, b; 19 /// 20 static if (N == 3 && isFloatingPoint!T) { 21 /// 22 bool intersect(Plane!T plane, out PointType intersection, out T progress) pure nothrow const @safe @nogc { 23 import liberty.math.functions : abs; 24 import liberty.math.vector : dot; 25 PointType dir = b - a; 26 T dp = dot(plane.n, dir); 27 if (abs(dp) < T.epsilon) { 28 progress = T.infinity; 29 return false; 30 } 31 progress = -(dot(plane.n, a) - plane.d) / dp; 32 intersection = progress * dir + a; 33 return progress >= 0 && progress <= 1; 34 } 35 } 36 } 37 /// 38 alias Segment2I = Segment!(int, 2); 39 /// 40 alias Segment3I = Segment!(int, 3); 41 /// 42 alias Segment2F = Segment!(float, 2); 43 /// 44 alias Segment3F = Segment!(float, 3); 45 /// 46 alias Segment2D = Segment!(double, 2); 47 /// 48 alias Segment3D = Segment!(double, 3); 49 /// 50 struct Triangle(T, int N) if (N == 2 || N == 3) { 51 /// 52 alias PointType = Vector!(T, N); 53 /// 54 PointType a, b, c; 55 static if (N == 2) { 56 /// Returns area of a 2D triangle. 57 T area() pure nothrow const @safe @nogc { 58 import liberty.math.functions : abs; 59 return abs(signedArea()); 60 } 61 /// Returns signed area of a 2D triangle. 62 T signedArea() pure nothrow const @safe @nogc { 63 return ((b.x * a.y - a.x * b.y) + (c.x * b.y - b.x * c.y) + (a.x * c.y - c.x * a.y)) / 2; 64 } 65 } 66 static if (N == 3 && isFloatingPoint!T) { 67 /// Returns triangle normal. 68 Vector!(T, 3) computeNormal() pure nothrow const @safe @nogc { 69 import liberty.math.vector : cross; 70 return cross(b - a, c - a).normalized(); 71 } 72 } 73 } 74 /// 75 alias Triangle2I = Triangle!(int, 2); 76 /// 77 alias Triangle3I = Triangle!(int, 3); 78 /// 79 alias Triangle2F = Triangle!(float, 2); 80 /// 81 alias Triangle3F = Triangle!(float, 3); 82 /// 83 alias Triangle2D = Triangle!(double, 2); 84 /// 85 alias Triangle3D = Triangle!(double, 3); 86 /// 87 struct Sphere(T, int N) if (N == 2 || N == 3) { 88 /// 89 alias PointType = Vector!(T, N); 90 /// 91 PointType center; 92 /// 93 T radius; 94 /// 95 this(in PointType center_, T radius_) pure nothrow @safe @nogc { 96 center = center_; 97 radius = radius_; 98 } 99 /// 100 bool contains(in Sphere s) pure nothrow const @safe @nogc { 101 if (s.radius > radius) { 102 return false; 103 } 104 T innerRadius = radius - s.radius; 105 return squaredDistanceTo(s.center) < innerRadius * innerRadius; 106 } 107 /// 108 T squaredDistanceTo(PointType p) pure nothrow const @safe @nogc { 109 return center.squaredDistanceTo(p); 110 } 111 /// 112 bool intersects(Sphere s) pure nothrow const @safe @nogc { 113 T outerRadius = radius + s.radius; 114 return squaredDistanceTo(s.center) < outerRadius * outerRadius; 115 } 116 static if (isFloatingPoint!T) { 117 /// 118 T distanceTo(PointType p) pure nothrow const @safe @nogc { 119 return center.distanceTo(p); 120 } 121 static if(N == 2) { 122 /// Returns circle area. 123 T area() pure nothrow const @safe @nogc { 124 import liberty.math.functions : PI; 125 return PI * (radius * radius); 126 } 127 } 128 } 129 } 130 /// 131 alias Sphere2I = Sphere!(int, 2); 132 /// 133 alias Sphere3I = Sphere!(int, 3); 134 /// 135 alias Sphere2F = Sphere!(float, 2); 136 /// 137 alias Sphere3F = Sphere!(float, 3); 138 /// 139 alias Sphere2D = Sphere!(double, 2); 140 /// 141 alias Sphere3D = Sphere!(double, 3); 142 /// 143 struct Ray(T, int N) if (N == 2 || N == 3) { 144 /// 145 alias PointType = Vector!(T, N); 146 /// 147 PointType origin; 148 /// 149 PointType direction; 150 /// 151 PointType progress(T t) pure const nothrow 152 { 153 return origin + direction * t; 154 } 155 static if (N == 3 && isFloatingPoint!T) { 156 /// 157 bool intersect(Triangle!(T, 3) triangle, out T t, out T u, out T v) pure nothrow const @safe @nogc { 158 import liberty.math.functions : abs; 159 import liberty.math.vector : dot, cross; 160 PointType edge1 = triangle.b - triangle.a; 161 PointType edge2 = triangle.c - triangle.a; 162 PointType pvec = cross(direction, edge2); 163 T det = dot(edge1, pvec); 164 if (abs(det) < T.epsilon) { 165 return false; 166 } 167 T invDet = 1 / det; 168 PointType tvec = origin - triangle.a; 169 u = dot(tvec, pvec) * invDet; 170 if (u < 0 || u > 1) { 171 return false; 172 } 173 PointType qvec = cross(tvec, edge1); 174 v = dot(direction, qvec) * invDet; 175 if (v < 0.0 || u + v > 1.0) { 176 return false; 177 } 178 t = dot(edge2, qvec) * invDet; 179 return true; 180 } 181 /// 182 bool intersect(Plane!T plane, out PointType intersection, out T distance) pure nothrow const @safe @nogc { 183 import liberty.math.functions : abs; 184 import liberty.math.vector : dot; 185 T dp = dot(plane.n, direction); 186 if (abs(dp) < T.epsilon) { 187 distance = T.infinity; 188 return false; 189 } 190 distance = -(dot(plane.n, origin) - plane.d) / dp; 191 intersection = distance * direction + origin; 192 return distance >= 0; 193 } 194 } 195 } 196 /// 197 alias Ray2I = Ray!(int, 2); 198 /// 199 alias Ray3I = Ray!(int, 3); 200 /// 201 alias Ray2F = Ray!(float, 2); 202 /// 203 alias Ray3F = Ray!(float, 3); 204 /// 205 alias Ray2D = Ray!(double, 2); 206 /// 207 alias Ray3D = Ray!(double, 3); 208 /// 209 struct Plane(T) if (isFloatingPoint!T) { 210 /// 211 alias type = T; 212 /// 213 Vector!(T, 3) n; 214 /// 215 T d; 216 /// 217 this(Vector!(T, 4) abcd) pure nothrow @safe @nogc { 218 n = Vector!(T, 3)(abcd.x, abcd.y, abcd.z).normalized(); 219 d = abcd.w; 220 } 221 /// 222 this(Vector!(T, 3) origin, Vector!(T, 3) normal) pure nothrow @safe @nogc { 223 import liberty.math.vector : dot; 224 n = normal.normalized(); 225 d = -dot(origin, n); 226 } 227 /// 228 this(Vector!(T, 3) A, Vector!(T, 3) B, Vector!(T, 3) C) pure nothrow @safe @nogc { 229 import liberty.math.vector : cross; 230 this(C, cross(B - A, C - A)); 231 } 232 /// 233 ref Plane opAssign(Plane other) pure nothrow @safe @nogc { 234 n = other.n; 235 d = other.d; 236 return this; 237 } 238 /// 239 T signedDistanceTo(Vector!(T, 3) point) pure nothrow const @safe @nogc { 240 import liberty.math.vector : dot; 241 return dot(n, point) + d; 242 } 243 /// 244 T distanceTo(Vector!(T, 3) point) pure nothrow const @safe @nogc { 245 import liberty.math.functions : abs; 246 return abs(signedDistanceTo(point)); 247 } 248 /// 249 bool isFront(Vector!(T, 3) point) pure nothrow const @safe @nogc { 250 return signedDistanceTo(point) >= 0; 251 } 252 /// 253 bool isBack(Vector!(T, 3) point) pure nothrow const @safe @nogc { 254 return signedDistanceTo(point) < 0; 255 } 256 /// 257 bool isOn(Vector!(T, 3) point, T epsilon) pure nothrow const @safe @nogc { 258 T sd = signedDistanceTo(point); 259 return (-epsilon < sd) && (sd < epsilon); 260 } 261 } 262 /// 263 alias PlaneF = Plane!float; 264 /// 265 alias PlaneD = Plane!double; 266 /// 267 enum FrustumSide : ubyte { 268 /// 269 Left = 0x00, 270 /// 271 Right = 0x01, 272 /// 273 Top = 0x02, 274 /// 275 Bottom = 0x03, 276 /// 277 Near = 0x04, 278 /// 279 Far = 0x05 280 } 281 /// 282 enum FrustumScope : ubyte { 283 /// Object is outside the frustum. 284 Outside = 0x00, 285 /// Object intersects with the frustum. 286 Intersect = 0x01, 287 /// Object is inside the frustum. 288 Inside = 0x02 289 } 290 /// 291 struct Frustum(T) if (isFloatingPoint!T) { 292 /// 293 enum sideCount = 6; 294 /// 295 enum vertexCount = 8; 296 /// 297 alias type = T; 298 /// 299 Plane!T[6] planes; 300 /// Create a frustum from 6 planes. 301 this(Plane!T left, Plane!T right, Plane!T top, Plane!T bottom, Plane!T near, Plane!T far) pure nothrow @safe @nogc { 302 planes[FrustumSide.Left] = left; 303 planes[FrustumSide.Right] = right; 304 planes[FrustumSide.Top] = top; 305 planes[FrustumSide.Bottom] = bottom; 306 planes[FrustumSide.Near] = near; 307 planes[FrustumSide.Far] = far; 308 } 309 /// 310 bool contains(Vector!(T, 3) point) pure nothrow const @safe @nogc { 311 T distance = 0; 312 static foreach (i; 0..sideCount) { 313 distance = planes[i].signedDistanceTo(point); 314 if (distance < 0) { 315 return false; 316 } 317 } 318 return true; 319 } 320 /// 321 FrustumScope contains(Sphere!(T, 3) sphere) pure nothrow const @safe @nogc { 322 T distance = 0; 323 static foreach (i; 0..sideCount) { 324 distance = planes[i].signedDistanceTo(sphere.center); 325 if(distance < -sphere.radius) { 326 return FrustumScope.Outside; 327 } else if (distance < sphere.radius) { 328 return FrustumScope.Intersect; 329 } 330 } 331 return FrustumScope.Inside; 332 } 333 /// 334 int contains(Box!(T, 3) box) pure nothrow const @safe @nogc { 335 Vector!(T, 3)[8] corners; 336 int totalIn = 0; 337 T x, y, z; 338 static foreach (i; 0..2) { 339 static foreach (j; 0..2) { 340 static foreach (k; 0..2) { 341 x = i == 0 ? box.min.x : box.max.x; 342 y = j == 0 ? box.min.y : box.max.y; 343 z = k == 0 ? box.min.z : box.max.z; 344 corners[i * 4 + j * 2 + k] = Vector!(T, 3)(x, y, z); 345 } 346 } 347 } 348 int inCount = 0, ptIn = 0; 349 static foreach (p; 0..sideCount) { 350 inCount = vertexCount; 351 ptIn = 1; 352 static foreach (i; 0..vertexCount) { 353 if (planes[p].isBack(corners[i])) { 354 ptIn = 0; 355 inCount--; 356 } 357 } 358 if (inCount == 0) { 359 return FrustumScope.Outside; 360 } 361 totalIn += ptIn; 362 } 363 if(totalIn == sideCount) { 364 return FrustumScope.Inside; 365 } 366 return FrustumScope.Intersect; 367 } 368 } 369 /// 370 alias FrustumF = Frustum!float; 371 /// 372 alias FrustumD = Frustum!double; 373 /// 374 enum isSegment(T) = is(T : Segment!U, U...); 375 /// 376 enum isTriangle(T) = is(T : Triangle!U, U...); 377 /// 378 enum isSphere(T) = is(T : Sphere!U, U...); 379 /// 380 enum isRay(T) = is(T : Ray!U, U...); 381 /// 382 enum isPlane(T) = is(T : Plane!U, U); 383 /// 384 enum isFrustum(T) = is(T : Frustum!U, U); 385 /// 386 enum isSegment2D(T) = is(T : Segment!(U, 2), U); 387 /// 388 enum isTriangle2D(T) = is(T : Triangle!(U, 2), U); 389 /// 390 enum isSphere2D(T) = is(T : Sphere!(U, 2), U); 391 /// 392 enum isRay2D(T) = is(T : Ray!(U, 2), U); 393 /// 394 enum isSegment3D(T) = is(T : Segment!(U, 3), U); 395 /// 396 enum isTriangle3D(T) = is(T : Triangle!(U, 3), U); 397 /// 398 enum isSphere3D(T) = is(T : Sphere!(U, 3), U); 399 /// 400 enum isRay3D(T) = is(T : Ray!(U, 3), U); 401 /// 402 alias DimensionType(T : Segment!U, U...) = U[0]; 403 /// 404 alias DimensionType(T : Triangle!U, U...) = U[0]; 405 /// 406 alias DimensionType(T : Sphere!U, U...) = U[0]; 407 /// 408 alias DimensionType(T : Ray!U, U...) = U[0]; 409 // 410 alias DimensionType(T : Plane!U, U) = U; 411 /// 412 alias DimensionType(T : Frustum!U, U) = U; 413 /// 414 pure nothrow @safe @nogc unittest { 415 static assert (is(DimensionType!Segment2I == int)); 416 static assert (is(DimensionType!Triangle3F == float)); 417 static assert (is(DimensionType!Sphere2D == double)); 418 static assert (is(DimensionType!Ray3F == float)); 419 static assert (is(DimensionType!PlaneD == double)); 420 static assert (is(DimensionType!(Frustum!float) == float)); 421 }