add ray march instancing (copies) with row offsets

instancing uses real evaluated copies of the mesh instead of domain
repetition. useful for hiding artifacts as an alternative to quilez's
corrective term, which generally converges more slowly.

1 files changed, 105 insertions, 102 deletions

diff --git a/ray_marching.cginc b/ray_marching.cginc
index 9cb8dd0..daba713 100644
--- a/ray_marching.cginc
+++ b/ray_marching.cginc
@@ -48,27 +48,30 @@ float map(float3 p) {
 #if defined(_RAY_MARCHING_HEX_GRID)
 float domain_repeat_hex_grid(inout float3 p) {
   const float gridCount = max(_Ray_Marching_Hex_Grid_Count, 1.0f);
-  const float halfCount = gridCount * 0.5f;
-  const float3 count = float3(halfCount, halfCount, halfCount);
-  const float3 period = 1.0f / count;
+  const float invGridCount = 1.0f / gridCount;
   const float3 hex = cart_to_hex(p.xy);
+  const float3 scaledHex = hex * gridCount;
   // Cell ID.
-  const float3 id = round_hex(hex / period);
+  const float3 id = round_hex(scaledHex);
   // Coordinates within the current cell.
-  const float3 local = hex - period * id;
-  float3 candidate = p;
-  candidate.xy = hex_to_cart(local);
-  float d = map(candidate);
-  float3 bestPos = candidate;
-
-#if defined(_RAY_MARCHING_CORRECT_REPETITION)
+  const float3 local = (scaledHex - id) * invGridCount;
   const float3 cubeId = float3(id.y, id.z, -id.y - id.z);
   const float limit = max((gridCount - 1.0f) * 0.5f, 0.0f);
   const float3 cubeLimit = float3(limit, limit, limit);
-  if (any(abs(cubeId) > cubeLimit)) {
-    p = float3(1e9, 1e9, 1e9);
-    return 1e9;
+
+  float3 bestPos = p;
+  float d = 1e9;
+  if (!any(abs(cubeId) > cubeLimit)) {
+    float3 pp = p;
+    pp.xy = hex_to_cart(local);
+    const float d_cur = map(pp);
+    if (d_cur < d) {
+      d = d_cur;
+      bestPos = pp;
+    }
   }
+
+#if defined(_RAY_MARCHING_CORRECT_REPETITION)
   const float3 cubeOffsets[6] = {
       float3( 1.0f, -1.0f,  0.0f),
       float3( 1.0f,  0.0f, -1.0f),
@@ -78,81 +81,17 @@ float domain_repeat_hex_grid(inout float3 p) {
       float3( 0.0f, -1.0f,  1.0f),
   };
 
-  float neighborDistSq[4] = { 1e9, 1e9, 1e9, 1e9 };
-  float3 neighborIds[4] = {
-      float3(0.0f, 0.0f, 0.0f),
-      float3(0.0f, 0.0f, 0.0f),
-      float3(0.0f, 0.0f, 0.0f),
-      float3(0.0f, 0.0f, 0.0f)};
-  float2 neighborLoc[4] = {
-      float2(0.0f, 0.0f),
-      float2(0.0f, 0.0f),
-      float2(0.0f, 0.0f),
-      float2(0.0f, 0.0f)};
-
-  [unroll]
   for (int idx = 0; idx < 6; ++idx) {
     const float3 cube = cubeId + cubeOffsets[idx];
-    const float3 rid = float3(cube.x + cube.y, cube.x, cube.y);
 
     if (any(abs(cube) > cubeLimit)) {
       continue;
     }
 
-    const float2 localXY = hex_to_cart(hex - period * rid);
-    const float distSq = dot(localXY, localXY);
-
-    if (distSq >= neighborDistSq[3]) {
-      continue;
-    }
-
-    neighborDistSq[3] = distSq;
-    neighborIds[3] = rid;
-    neighborLoc[3] = localXY;
-
-    if (neighborDistSq[3] < neighborDistSq[2]) {
-      const float tmpDist = neighborDistSq[2];
-      const float3 tmpId = neighborIds[2];
-      const float2 tmpLoc = neighborLoc[2];
-      neighborDistSq[2] = neighborDistSq[3];
-      neighborIds[2] = neighborIds[3];
-      neighborLoc[2] = neighborLoc[3];
-      neighborDistSq[3] = tmpDist;
-      neighborIds[3] = tmpId;
-      neighborLoc[3] = tmpLoc;
-    }
-    if (neighborDistSq[2] < neighborDistSq[1]) {
-      const float tmpDist = neighborDistSq[1];
-      const float3 tmpId = neighborIds[1];
-      const float2 tmpLoc = neighborLoc[1];
-      neighborDistSq[1] = neighborDistSq[2];
-      neighborIds[1] = neighborIds[2];
-      neighborLoc[1] = neighborLoc[2];
-      neighborDistSq[2] = tmpDist;
-      neighborIds[2] = tmpId;
-      neighborLoc[2] = tmpLoc;
-    }
-    if (neighborDistSq[1] < neighborDistSq[0]) {
-      const float tmpDist = neighborDistSq[0];
-      const float3 tmpId = neighborIds[0];
-      const float2 tmpLoc = neighborLoc[0];
-      neighborDistSq[0] = neighborDistSq[1];
-      neighborIds[0] = neighborIds[1];
-      neighborLoc[0] = neighborLoc[1];
-      neighborDistSq[1] = tmpDist;
-      neighborIds[1] = tmpId;
-      neighborLoc[1] = tmpLoc;
-    }
-  }
-
-  [unroll]
-  for (int idx = 0; idx < 4; ++idx) {
-    if (neighborDistSq[idx] >= 1e9) {
-      continue;
-    }
-
+    const float3 rid = float3(cube.x + cube.y, cube.x, cube.y);
+    const float3 neighbourHex = (scaledHex - rid) * invGridCount;
     float3 neighbour = p;
-    neighbour.xy = neighborLoc[idx];
+    neighbour.xy = hex_to_cart(neighbourHex);
     const float d_cur = map(neighbour);
     if (d_cur < d) {
       d = d_cur;
@@ -170,9 +109,9 @@ float domain_repeat(inout float3 p) {
   float d;
 #if defined(_RAY_MARCHING_CART_GRID)
   {
-    float3 count = float3(_Ray_Marching_Cart_Grid_Count_X, _Ray_Marching_Cart_Grid_Count_Y, _Ray_Marching_Cart_Grid_Count_Z);
-    float3 period = 1.0f / count;
-    period *= 2;
+    const float3 count = float3(_Ray_Marching_Cart_Grid_Count_X, _Ray_Marching_Cart_Grid_Count_Y, _Ray_Marching_Cart_Grid_Count_Z);
+    const float3 span = float3(_Ray_Marching_Cart_Grid_Span_X, _Ray_Marching_Cart_Grid_Span_Y, _Ray_Marching_Cart_Grid_Span_Z);
+    const float3 period = span / count;
     float3 half_period = period*0.5f;
     float3 which = floor((p + half_period) / period);
     if (any(abs(which) > count/2)) {
@@ -190,27 +129,13 @@ float domain_repeat(inout float3 p) {
   return d;
 }
 
-void ray_march(inout v2f i) {
 #if defined(_RAY_MARCHING)
-  float3 ro, rd;
-  GetRoRd(i, ro, rd);
-
-#if defined(_VERTEX_DEFORMATION)
-  // TODO optimize, we don't need to pass in `dummy`.
-  {
-    float3 dummy = 0;
-    float3 tmp_pos = ro;
-    undeform_normal(tmp_pos, dummy, rd);
-    rd = normalize(rd);
-  }
-#endif
-
+bool get_one_hit(float3 ro, float3 rd, out float3 hitPos, out float hitD) {
   const float kMinDist = _Ray_Marching_Min_Dist;
   const float kMaxDist = _Ray_Marching_Max_Dist;
   const uint kMaxIter = _Ray_Marching_Max_Iter;
   float d_cur;
   float d_acc = 0;
-  float3 hit_pos;
   for (uint ii = 0; ii < kMaxIter; ++ii) {
     float3 p = ro + rd * d_acc;
 
@@ -222,15 +147,93 @@ void ray_march(inout v2f i) {
 
     d_acc += d_cur;
     if (abs(d_cur) < kMinDist) {
-      hit_pos = p;
-      break;
+      hitPos = p;
+      hitD = d_acc;
+      return true;
     }
     if (d_acc > kMaxDist) {
       break;
     }
   }
 
-  if (abs(d_cur) >= kMinDist) {
+  return false;
+}
+
+bool get_hit(float3 ro, float3 rd, out float3 hitPos, out float hitD) {
+#if defined(_RAY_MARCHING_CART_INSTANCING)
+  const float3 span = float3(
+      _Ray_Marching_Cart_Instancing_Span_X,
+      _Ray_Marching_Cart_Instancing_Span_Y,
+      _Ray_Marching_Cart_Instancing_Span_Z) * 2.0f;
+  const float3 count = float3(
+      _Ray_Marching_Cart_Instancing_Count_X,
+      _Ray_Marching_Cart_Instancing_Count_Y,
+      _Ray_Marching_Cart_Instancing_Count_Z);
+  const float3 count_minus_1 = count - 1.0f;
+  const float3 offset = span / count;
+  const float3 midpoint = offset * count_minus_1 * 0.5f;
+#if defined(_RAY_MARCHING_CART_INSTANCING_OFFSETS)
+  const float x_every_y = _Ray_Marching_Cart_Instancing_Offsets_X_Every_Y;
+  const float x_every_z = _Ray_Marching_Cart_Instancing_Offsets_X_Every_Z;
+  const float y_every_x = _Ray_Marching_Cart_Instancing_Offsets_Y_Every_X;
+  const float y_every_z = _Ray_Marching_Cart_Instancing_Offsets_Y_Every_Z;
+  const float z_every_x = _Ray_Marching_Cart_Instancing_Offsets_Z_Every_X;
+  const float z_every_y = _Ray_Marching_Cart_Instancing_Offsets_Z_Every_Y;
+  const float3 max_offset = float3(
+    count_minus_1.y * x_every_y + count_minus_1.z * x_every_z,
+    count_minus_1.x * y_every_x + count_minus_1.z * y_every_z,
+    count_minus_1.x * z_every_x + count_minus_1.y * z_every_y
+  );
+  const float3 offset_midpoint = max_offset * 0.5f;
+#endif
+
+  hitD = 1e9;
+  for (uint xi = 0; xi < count.x; ++xi)
+  for (uint yi = 0; yi < count.y; ++yi)
+  for (uint zi = 0; zi < count.z; ++zi) {
+    float3 hitPos_tmp;
+    float hitD_tmp;
+    float3 cur_pos = ro + offset * float3(xi, yi, zi) - midpoint;
+#if defined(_RAY_MARCHING_CART_INSTANCING_OFFSETS)
+    const float3 cur_offset = float3(
+        x_every_y * yi + x_every_z * zi,
+        y_every_x * xi + y_every_z * zi,
+        z_every_x * xi + z_every_y * yi);
+    cur_pos += cur_offset - offset_midpoint;
+#endif
+    if (!get_one_hit(cur_pos, rd, hitPos_tmp, hitD_tmp)) {
+      continue;
+    }
+    if (hitD_tmp < hitD) {
+      hitPos = hitPos_tmp;
+      hitD = hitD_tmp;
+    }
+  }
+  return hitD != 1e9;
+#else
+  return get_one_hit(ro, rd, hitPos, hitD);
+#endif
+}
+#endif  // _RAY_MARCHING
+
+void ray_march(inout v2f i) {
+#if defined(_RAY_MARCHING)
+  float3 ro, rd;
+  GetRoRd(i, ro, rd);
+
+#if defined(_VERTEX_DEFORMATION)
+  // TODO optimize, we don't need to pass in `dummy`.
+  {
+    float3 dummy = 0;
+    float3 tmp_pos = ro;
+    undeform_normal(tmp_pos, dummy, rd);
+    rd = normalize(rd);
+  }
+#endif
+
+  float3 hit_pos;
+  float hit_d;
+  if (!get_hit(ro, rd, hit_pos, hit_d)) {
     discard;
   }