DRW: Add intersection and shape libraries for GLSL

These are meant to provide easy shape and AABB operation for culling.

They are currently incomplete but can be extended as one see fits.

The `common_debug_shape_lib.glsl` contains helper to draw thoses shapes.

5 files changed, 729 insertions, 0 deletions

diff --git a/source/blender/draw/intern/shaders/common_aabb_lib.glsl b/source/blender/draw/intern/shaders/common_aabb_lib.glsl
new file mode 100644
index 00000000000..b5f664a6779
--- /dev/null
+++ b/source/blender/draw/intern/shaders/common_aabb_lib.glsl
@@ -0,0 +1,59 @@
+
+#pragma BLENDER_REQUIRE(common_shape_lib.glsl)
+
+/* ---------------------------------------------------------------------- */
+/** \name Axis Aligned Bound Box
+ * \{ */
+
+struct AABB {
+  vec3 min, max;
+};
+
+AABB aabb_init_min_max()
+{
+  AABB aabb;
+  aabb.min = vec3(1.0e30);
+  aabb.max = vec3(-1.0e30);
+  return aabb;
+}
+
+void aabb_merge(inout AABB aabb, vec3 v)
+{
+  aabb.min = min(aabb.min, v);
+  aabb.max = max(aabb.max, v);
+}
+
+/**
+ * Return true if there is any intersection.
+ */
+bool aabb_intersect(AABB a, AABB b)
+{
+  return all(greaterThanEqual(min(a.max, b.max), max(a.min, b.min)));
+}
+
+/**
+ * Compute intersect intersection volume of \a a and \a b.
+ * Return true if the resulting volume is not empty.
+ */
+bool aabb_clip(AABB a, AABB b, out AABB c)
+{
+  c.min = max(a.min, b.min);
+  c.max = min(a.max, b.max);
+  return all(greaterThanEqual(c.max, c.min));
+}
+
+Box aabb_to_box(AABB aabb)
+{
+  Box box;
+  box.corners[0] = aabb.min;
+  box.corners[1] = vec3(aabb.max.x, aabb.min.y, aabb.min.z);
+  box.corners[2] = vec3(aabb.max.x, aabb.max.y, aabb.min.z);
+  box.corners[3] = vec3(aabb.min.x, aabb.max.y, aabb.min.z);
+  box.corners[4] = vec3(aabb.min.x, aabb.min.y, aabb.max.z);
+  box.corners[5] = vec3(aabb.max.x, aabb.min.y, aabb.max.z);
+  box.corners[6] = aabb.max;
+  box.corners[7] = vec3(aabb.min.x, aabb.max.y, aabb.max.z);
+  return box;
+}
+
+/** \} */
diff --git a/source/blender/draw/intern/shaders/common_debug_shape_lib.glsl b/source/blender/draw/intern/shaders/common_debug_shape_lib.glsl
new file mode 100644
index 00000000000..538c55ce544
--- /dev/null
+++ b/source/blender/draw/intern/shaders/common_debug_shape_lib.glsl
@@ -0,0 +1,57 @@
+
+/**
+ * Debug drawing of shapes.
+ */
+
+#pragma BLENDER_REQUIRE(common_debug_draw_lib.glsl)
+#pragma BLENDER_REQUIRE(common_shape_lib.glsl)
+
+void drw_debug(Box shape, vec4 color)
+{
+  drw_debug_quad(shape.corners[0], shape.corners[1], shape.corners[2], shape.corners[3], color);
+  drw_debug_line(shape.corners[0], shape.corners[4], color);
+  drw_debug_line(shape.corners[1], shape.corners[5], color);
+  drw_debug_line(shape.corners[2], shape.corners[6], color);
+  drw_debug_line(shape.corners[3], shape.corners[7], color);
+  drw_debug_quad(shape.corners[4], shape.corners[5], shape.corners[6], shape.corners[7], color);
+}
+void drw_debug(Box shape)
+{
+  drw_debug(shape, drw_debug_default_color);
+}
+
+void drw_debug(Frustum shape, vec4 color)
+{
+  drw_debug_quad(shape.corners[0], shape.corners[1], shape.corners[2], shape.corners[3], color);
+  drw_debug_line(shape.corners[0], shape.corners[4], color);
+  drw_debug_line(shape.corners[1], shape.corners[5], color);
+  drw_debug_line(shape.corners[2], shape.corners[6], color);
+  drw_debug_line(shape.corners[3], shape.corners[7], color);
+  drw_debug_quad(shape.corners[4], shape.corners[5], shape.corners[6], shape.corners[7], color);
+}
+void drw_debug(Frustum shape)
+{
+  drw_debug(shape, drw_debug_default_color);
+}
+
+void drw_debug(Pyramid shape, vec4 color)
+{
+  drw_debug_line(shape.corners[0], shape.corners[1], color);
+  drw_debug_line(shape.corners[0], shape.corners[2], color);
+  drw_debug_line(shape.corners[0], shape.corners[3], color);
+  drw_debug_line(shape.corners[0], shape.corners[4], color);
+  drw_debug_quad(shape.corners[1], shape.corners[2], shape.corners[3], shape.corners[4], color);
+}
+void drw_debug(Pyramid shape)
+{
+  drw_debug(shape, drw_debug_default_color);
+}
+
+void drw_debug(Sphere shape, vec4 color)
+{
+  drw_debug_sphere(shape.center, shape.radius, color);
+}
+void drw_debug(Sphere shape)
+{
+  drw_debug(shape, drw_debug_default_color);
+}
diff --git a/source/blender/draw/intern/shaders/common_intersect_lib.glsl b/source/blender/draw/intern/shaders/common_intersect_lib.glsl
new file mode 100644
index 00000000000..708d361029a
--- /dev/null
+++ b/source/blender/draw/intern/shaders/common_intersect_lib.glsl
@@ -0,0 +1,399 @@
+
+/**
+ * Intersection library used for culling.
+ * Results are meant to be conservative.
+ */
+
+#pragma BLENDER_REQUIRE(common_view_lib.glsl)
+#pragma BLENDER_REQUIRE(common_math_geom_lib.glsl)
+#pragma BLENDER_REQUIRE(common_shape_lib.glsl)
+
+/* ---------------------------------------------------------------------- */
+/** \name Plane extraction functions.
+ * \{ */
+
+/** \a v1 and \a v2 are vectors on the plane. \a p is a point on the plane. */
+vec4 isect_plane_setup(vec3 p, vec3 v1, vec3 v2)
+{
+  vec3 normal_to_plane = normalize(cross(v1, v2));
+  return vec4(normal_to_plane, -dot(normal_to_plane, p));
+}
+
+struct IsectPyramid {
+  vec3 corners[5];
+  vec4 planes[5];
+};
+
+IsectPyramid isect_data_setup(Pyramid shape)
+{
+  vec3 A1 = shape.corners[1] - shape.corners[0];
+  vec3 A2 = shape.corners[2] - shape.corners[0];
+  vec3 A3 = shape.corners[3] - shape.corners[0];
+  vec3 A4 = shape.corners[4] - shape.corners[0];
+  vec3 S4 = shape.corners[4] - shape.corners[1];
+  vec3 S2 = shape.corners[2] - shape.corners[1];
+
+  IsectPyramid data;
+  data.planes[0] = isect_plane_setup(shape.corners[0], A2, A1);
+  data.planes[1] = isect_plane_setup(shape.corners[0], A3, A2);
+  data.planes[2] = isect_plane_setup(shape.corners[0], A4, A3);
+  data.planes[3] = isect_plane_setup(shape.corners[0], A1, A4);
+  data.planes[4] = isect_plane_setup(shape.corners[1], S2, S4);
+  for (int i = 0; i < 5; i++) {
+    data.corners[i] = shape.corners[i];
+  }
+  return data;
+}
+
+struct IsectBox {
+  vec3 corners[8];
+  vec4 planes[6];
+};
+
+IsectBox isect_data_setup(Box shape)
+{
+  vec3 A1 = shape.corners[1] - shape.corners[0];
+  vec3 A3 = shape.corners[3] - shape.corners[0];
+  vec3 A4 = shape.corners[4] - shape.corners[0];
+
+  IsectBox data;
+  data.planes[0] = isect_plane_setup(shape.corners[0], A3, A1);
+  data.planes[1] = isect_plane_setup(shape.corners[0], A4, A3);
+  data.planes[2] = isect_plane_setup(shape.corners[0], A1, A4);
+  /* Assumes that the box is actually a box! */
+  data.planes[3] = vec4(-data.planes[0].xyz, -dot(-data.planes[0].xyz, shape.corners[6]));
+  data.planes[4] = vec4(-data.planes[1].xyz, -dot(-data.planes[1].xyz, shape.corners[6]));
+  data.planes[5] = vec4(-data.planes[2].xyz, -dot(-data.planes[2].xyz, shape.corners[6]));
+  for (int i = 0; i < 8; i++) {
+    data.corners[i] = shape.corners[i];
+  }
+  return data;
+}
+
+struct IsectFrustum {
+  vec3 corners[8];
+  vec4 planes[6];
+};
+
+IsectFrustum isect_data_setup(Frustum shape)
+{
+  vec3 A1 = shape.corners[1] - shape.corners[0];
+  vec3 A3 = shape.corners[3] - shape.corners[0];
+  vec3 A4 = shape.corners[4] - shape.corners[0];
+  vec3 B5 = shape.corners[5] - shape.corners[6];
+  vec3 B7 = shape.corners[7] - shape.corners[6];
+  vec3 B2 = shape.corners[2] - shape.corners[6];
+
+  IsectFrustum data;
+  data.planes[0] = isect_plane_setup(shape.corners[0], A3, A1);
+  data.planes[1] = isect_plane_setup(shape.corners[0], A4, A3);
+  data.planes[2] = isect_plane_setup(shape.corners[0], A1, A4);
+  data.planes[3] = isect_plane_setup(shape.corners[6], B7, B5);
+  data.planes[4] = isect_plane_setup(shape.corners[6], B5, B2);
+  data.planes[5] = isect_plane_setup(shape.corners[6], B2, B7);
+  for (int i = 0; i < 8; i++) {
+    data.corners[i] = shape.corners[i];
+  }
+  return data;
+}
+
+/** \} */
+
+/* ---------------------------------------------------------------------- */
+/** \name View Intersection functions.
+ * \{ */
+
+bool intersect_view(Pyramid pyramid)
+{
+  bool intersects = true;
+
+  /* Do Pyramid vertices vs Frustum planes. */
+  for (int p = 0; p < 6; ++p) {
+    bool is_any_vertex_on_positive_side = false;
+    for (int v = 0; v < 5; ++v) {
+      float test = dot(drw_view.frustum_planes[p], vec4(pyramid.corners[v], 1.0));
+      if (test > 0.0) {
+        is_any_vertex_on_positive_side = true;
+        break;
+      }
+    }
+    bool all_vertex_on_negative_side = !is_any_vertex_on_positive_side;
+    if (all_vertex_on_negative_side) {
+      intersects = false;
+      break;
+    }
+  }
+
+  if (!intersects) {
+    return intersects;
+  }
+
+  /* Now do Frustum vertices vs Pyramid planes. */
+  IsectPyramid i_pyramid = isect_data_setup(pyramid);
+  for (int p = 0; p < 5; ++p) {
+    bool is_any_vertex_on_positive_side = false;
+    for (int v = 0; v < 8; ++v) {
+      float test = dot(i_pyramid.planes[p], vec4(drw_view.frustum_corners[v].xyz, 1.0));
+      if (test > 0.0) {
+        is_any_vertex_on_positive_side = true;
+        break;
+      }
+    }
+    bool all_vertex_on_negative_side = !is_any_vertex_on_positive_side;
+    if (all_vertex_on_negative_side) {
+      intersects = false;
+      break;
+    }
+  }
+  return intersects;
+}
+
+bool intersect_view(Box box)
+{
+  bool intersects = true;
+
+  /* Do Box vertices vs Frustum planes. */
+  for (int p = 0; p < 6; ++p) {
+    bool is_any_vertex_on_positive_side = false;
+    for (int v = 0; v < 8; ++v) {
+      float test = dot(drw_view.frustum_planes[p], vec4(box.corners[v], 1.0));
+      if (test > 0.0) {
+        is_any_vertex_on_positive_side = true;
+        break;
+      }
+    }
+    bool all_vertex_on_negative_side = !is_any_vertex_on_positive_side;
+    if (all_vertex_on_negative_side) {
+      intersects = false;
+      break;
+    }
+  }
+
+  if (!intersects) {
+    return intersects;
+  }
+
+  /* Now do Frustum vertices vs Box planes. */
+  IsectBox i_box = isect_data_setup(box);
+  for (int p = 0; p < 6; ++p) {
+    bool is_any_vertex_on_positive_side = false;
+    for (int v = 0; v < 8; ++v) {
+      float test = dot(i_box.planes[p], vec4(drw_view.frustum_corners[v].xyz, 1.0));
+      if (test > 0.0) {
+        is_any_vertex_on_positive_side = true;
+        break;
+      }
+    }
+    bool all_vertex_on_negative_side = !is_any_vertex_on_positive_side;
+    if (all_vertex_on_negative_side) {
+      intersects = false;
+      break;
+    }
+  }
+
+  return intersects;
+}
+
+bool intersect_view(Sphere sphere)
+{
+  bool intersects = true;
+
+  for (int p = 0; p < 6 && intersects; ++p) {
+    float dist_to_plane = dot(drw_view.frustum_planes[p], vec4(sphere.center, 1.0));
+    if (dist_to_plane < -sphere.radius) {
+      intersects = false;
+    }
+  }
+  /* TODO reject false positive. */
+  return intersects;
+}
+
+/** \} */
+
+/* ---------------------------------------------------------------------- */
+/** \name Shape vs. Shape Intersection functions.
+ * \{ */
+
+bool intersect(IsectPyramid i_pyramid, Box box)
+{
+  bool intersects = true;
+
+  /* Do Box vertices vs Pyramid planes. */
+  for (int p = 0; p < 5; ++p) {
+    bool is_any_vertex_on_positive_side = false;
+    for (int v = 0; v < 8; ++v) {
+      float test = dot(i_pyramid.planes[p], vec4(box.corners[v], 1.0));
+      if (test > 0.0) {
+        is_any_vertex_on_positive_side = true;
+        break;
+      }
+    }
+    bool all_vertex_on_negative_side = !is_any_vertex_on_positive_side;
+    if (all_vertex_on_negative_side) {
+      intersects = false;
+      break;
+    }
+  }
+
+  if (!intersects) {
+    return intersects;
+  }
+
+  /* Now do Pyramid vertices vs Box planes. */
+  IsectBox i_box = isect_data_setup(box);
+  for (int p = 0; p < 6; ++p) {
+    bool is_any_vertex_on_positive_side = false;
+    for (int v = 0; v < 5; ++v) {
+      float test = dot(i_box.planes[p], vec4(i_pyramid.corners[v], 1.0));
+      if (test > 0.0) {
+        is_any_vertex_on_positive_side = true;
+        break;
+      }
+    }
+    bool all_vertex_on_negative_side = !is_any_vertex_on_positive_side;
+    if (all_vertex_on_negative_side) {
+      intersects = false;
+      break;
+    }
+  }
+  return intersects;
+}
+
+bool intersect(IsectFrustum i_frustum, Pyramid pyramid)
+{
+  bool intersects = true;
+
+  /* Do Pyramid vertices vs Frustum planes. */
+  for (int p = 0; p < 6; ++p) {
+    bool is_any_vertex_on_positive_side = false;
+    for (int v = 0; v < 5; ++v) {
+      float test = dot(i_frustum.planes[p], vec4(pyramid.corners[v], 1.0));
+      if (test > 0.0) {
+        is_any_vertex_on_positive_side = true;
+        break;
+      }
+    }
+    bool all_vertex_on_negative_side = !is_any_vertex_on_positive_side;
+    if (all_vertex_on_negative_side) {
+      intersects = false;
+      break;
+    }
+  }
+
+  if (!intersects) {
+    return intersects;
+  }
+
+  /* Now do Frustum vertices vs Pyramid planes. */
+  IsectPyramid i_pyramid = isect_data_setup(pyramid);
+  for (int p = 0; p < 5; ++p) {
+    bool is_any_vertex_on_positive_side = false;
+    for (int v = 0; v < 8; ++v) {
+      float test = dot(i_pyramid.planes[p], vec4(i_frustum.corners[v].xyz, 1.0));
+      if (test > 0.0) {
+        is_any_vertex_on_positive_side = true;
+        break;
+      }
+    }
+    bool all_vertex_on_negative_side = !is_any_vertex_on_positive_side;
+    if (all_vertex_on_negative_side) {
+      intersects = false;
+      break;
+    }
+  }
+  return intersects;
+}
+
+bool intersect(IsectFrustum i_frustum, Box box)
+{
+  bool intersects = true;
+
+  /* Do Box vertices vs Frustum planes. */
+  for (int p = 0; p < 6; ++p) {
+    bool is_any_vertex_on_positive_side = false;
+    for (int v = 0; v < 8; ++v) {
+      float test = dot(i_frustum.planes[p], vec4(box.corners[v], 1.0));
+      if (test > 0.0) {
+        is_any_vertex_on_positive_side = true;
+        break;
+      }
+    }
+    bool all_vertex_on_negative_side = !is_any_vertex_on_positive_side;
+    if (all_vertex_on_negative_side) {
+      intersects = false;
+      break;
+    }
+  }
+
+  if (!intersects) {
+    return intersects;
+  }
+
+  /* Now do Frustum vertices vs Box planes. */
+  IsectBox i_box = isect_data_setup(box);
+  for (int p = 0; p < 6; ++p) {
+    bool is_any_vertex_on_positive_side = false;
+    for (int v = 0; v < 8; ++v) {
+      float test = dot(i_box.planes[p], vec4(i_frustum.corners[v].xyz, 1.0));
+      if (test > 0.0) {
+        is_any_vertex_on_positive_side = true;
+        break;
+      }
+    }
+    bool all_vertex_on_negative_side = !is_any_vertex_on_positive_side;
+    if (all_vertex_on_negative_side) {
+      intersects = false;
+      break;
+    }
+  }
+
+  return intersects;
+}
+
+bool intersect(IsectFrustum i_frustum, Sphere sphere)
+{
+  bool intersects = true;
+
+  for (int p = 0; p < 8; ++p) {
+    float dist_to_plane = dot(i_frustum.planes[p], vec4(sphere.center, 1.0));
+    if (dist_to_plane < -sphere.radius) {
+      intersects = false;
+      break;
+    }
+  }
+  return intersects;
+}
+
+bool intersect(Cone cone, Sphere sphere)
+{
+  /**
+   * Following "Improve Tile-based Light Culling with Spherical-sliced Cone"
+   * by Eric Zhang
+   * https://lxjk.github.io/2018/03/25/Improve-Tile-based-Light-Culling-with-Spherical-sliced-Cone.html
+   */
+  float sphere_distance = length(sphere.center);
+  float sphere_distance_rcp = safe_rcp(sphere_distance);
+  float sphere_sin = saturate(sphere.radius * sphere_distance_rcp);
+  float sphere_cos = sqrt(1.0 - sphere_sin * sphere_sin);
+  float cone_aperture_sin = sqrt(1.0 - cone.angle_cos * cone.angle_cos);
+
+  float cone_sphere_center_cos = dot(sphere.center * sphere_distance_rcp, cone.direction);
+  /* cos(A+B) = cos(A) * cos(B) - sin(A) * sin(B). */
+  float cone_sphere_angle_sum_cos = (sphere.radius > sphere_distance) ?
+                                        -1.0 :
+                                        (cone.angle_cos * sphere_cos -
+                                         cone_aperture_sin * sphere_sin);
+  /* Comparing cosines instead of angles since we are interested
+   * only in the monotonic region [0 .. M_PI / 2]. This saves costly acos() calls. */
+  bool intersects = (cone_sphere_center_cos >= cone_sphere_angle_sum_cos);
+
+  return intersects;
+}
+
+bool intersect(Circle circle_a, Circle circle_b)
+{
+  return distance_squared(circle_a.center, circle_b.center) <
+         sqr(circle_a.radius + circle_b.radius);
+}
+
+/** \} */
diff --git a/source/blender/draw/intern/shaders/common_math_geom_lib.glsl b/source/blender/draw/intern/shaders/common_math_geom_lib.glsl
index cb2da9d35bf..71460c39285 100644
--- a/source/blender/draw/intern/shaders/common_math_geom_lib.glsl
+++ b/source/blender/draw/intern/shaders/common_math_geom_lib.glsl
@@ -5,6 +5,18 @@
 /** \name Math intersection & projection functions.
  * \{ */
 
+vec4 plane_from_quad(vec3 v0, vec3 v1, vec3 v2, vec3 v3)
+{
+  vec3 nor = normalize(cross(v2 - v1, v0 - v1) + cross(v0 - v3, v2 - v3));
+  return vec4(nor, -dot(nor, v2));
+}
+
+vec4 plane_from_tri(vec3 v0, vec3 v1, vec3 v2)
+{
+  vec3 nor = normalize(cross(v2 - v1, v0 - v1));
+  return vec4(nor, -dot(nor, v2));
+}
+
 float point_plane_projection_dist(vec3 line_origin, vec3 plane_origin, vec3 plane_normal)
 {
   return dot(plane_normal, plane_origin - line_origin);
diff --git a/source/blender/draw/intern/shaders/common_shape_lib.glsl b/source/blender/draw/intern/shaders/common_shape_lib.glsl
new file mode 100644
index 00000000000..f2c8bf0faaf
--- /dev/null
+++ b/source/blender/draw/intern/shaders/common_shape_lib.glsl
@@ -0,0 +1,202 @@
+
+#pragma BLENDER_REQUIRE(common_math_geom_lib.glsl)
+
+/**
+ * Geometric shape structures.
+ * Some constructors might seems redundant but are here to make the API cleaner and
+ * allow for more than one constructor per type.
+ */
+
+/* ---------------------------------------------------------------------- */
+/** \name Circle
+ * \{ */
+
+struct Circle {
+  vec2 center;
+  float radius;
+};
+
+Circle shape_circle(vec2 center, float radius)
+{
+  return Circle(center, radius);
+}
+
+/** \} */
+
+/* ---------------------------------------------------------------------- */
+/** \name Sphere
+ * \{ */
+
+struct Sphere {
+  vec3 center;
+  float radius;
+};
+
+Sphere shape_sphere(vec3 center, float radius)
+{
+  return Sphere(center, radius);
+}
+
+/** \} */
+
+/* ---------------------------------------------------------------------- */
+/** \name Box
+ * \{ */
+
+struct Box {
+  vec3 corners[8];
+};
+
+/* Construct box from 4 basis points. */
+Box shape_box(vec3 v000, vec3 v100, vec3 v010, vec3 v001)
+{
+  v100 -= v000;
+  v010 -= v000;
+  v001 -= v000;
+  Box box;
+  box.corners[0] = v000;
+  box.corners[1] = v000 + v100;
+  box.corners[2] = v000 + v010 + v100;
+  box.corners[3] = v000 + v010;
+  box.corners[4] = box.corners[0] + v001;
+  box.corners[5] = box.corners[1] + v001;
+  box.corners[6] = box.corners[2] + v001;
+  box.corners[7] = box.corners[3] + v001;
+  return box;
+}
+
+/** \} */
+
+/* ---------------------------------------------------------------------- */
+/** \name Square Pyramid
+ * \{ */
+
+struct Pyramid {
+  /* Apex is the first. Base vertices are in clockwise order from front view. */
+  vec3 corners[5];
+};
+
+/**
+ * Regular Square Pyramid (can be oblique).
+ * Use this corner order.
+ * (Top-Down View of the pyramid)
+ * <pre>
+ *
+ * Y
+ * |
+ * |
+ * .-----X
+ *
+ *  4-----------3
+ *  | \       / |
+ *  |   \   /   |
+ *  |     0     |
+ *  |   /   \   |
+ *  | /       \ |
+ *  1-----------2
+ * </pre>
+ * base_corner_00 is vertex 1
+ * base_corner_01 is vertex 2
+ * base_corner_10 is vertex 4
+ */
+Pyramid shape_pyramid(vec3 apex, vec3 base_corner_00, vec3 base_corner_01, vec3 base_corner_10)
+{
+  Pyramid pyramid;
+  pyramid.corners[0] = apex;
+  pyramid.corners[1] = base_corner_00;
+  pyramid.corners[2] = base_corner_01;
+  pyramid.corners[3] = base_corner_10 + (base_corner_01 - base_corner_00);
+  pyramid.corners[4] = base_corner_10;
+  return pyramid;
+}
+
+/**
+ * Regular Square Pyramid.
+ * <pre>
+ *
+ * Y
+ * |
+ * |
+ * .-----X
+ *
+ *  4-----Y-----3
+ *  | \   |   / |
+ *  |   \ | /   |
+ *  |     0-----X
+ *  |   /   \   |
+ *  | /       \ |
+ *  1-----------2
+ * </pre>
+ * base_center_pos_x is vector from base center to X
+ * base_center_pos_y is vector from base center to Y
+ */
+Pyramid shape_pyramid_non_oblique(vec3 apex,
+                                  vec3 base_center,
+                                  vec3 base_center_pos_x,
+                                  vec3 base_center_pos_y)
+{
+  Pyramid pyramid;
+  pyramid.corners[0] = apex;
+  pyramid.corners[1] = base_center - base_center_pos_x - base_center_pos_y;
+  pyramid.corners[2] = base_center + base_center_pos_x - base_center_pos_y;
+  pyramid.corners[3] = base_center + base_center_pos_x + base_center_pos_y;
+  pyramid.corners[4] = base_center - base_center_pos_x + base_center_pos_y;
+  return pyramid;
+}
+
+/** \} */
+
+/* ---------------------------------------------------------------------- */
+/** \name Frustum
+ * \{ */
+
+struct Frustum {
+  vec3 corners[8];
+};
+
+/**
+ * Use this corner order.
+ * <pre>
+ *
+ * Z  Y
+ * | /
+ * |/
+ * .-----X
+ *     2----------6
+ *    /|         /|
+ *   / |        / |
+ *  1----------5  |
+ *  |  |       |  |
+ *  |  3-------|--7
+ *  | /        | /
+ *  |/         |/
+ *  0----------4
+ * </pre>
+ */
+Frustum shape_frustum(vec3 corners[8])
+{
+  Frustum frustum;
+  for (int i = 0; i < 8; i++) {
+    frustum.corners[i] = corners[i];
+  }
+  return frustum;
+}
+
+/** \} */
+
+/* ---------------------------------------------------------------------- */
+/** \name Cone
+ * \{ */
+
+/* Cone at orign with no height. */
+struct Cone {
+  vec3 direction;
+  float angle_cos;
+};
+
+Cone shape_cone(vec3 direction, float angle_cosine)
+{
+  return Cone(direction, angle_cosine);
+}
+
+/** \} */