Builds a higher (less detailed) LOD of Minecraft style terrain by coalescing the most occurring then most prominent voxels.

gistfile1.c

typedef struct v3_octree_lod {
  unsigned level;
  v3_voxel_t voxels[0];
} v3_octree_lod_t;

V3_API void v3_octree_lod_coalesce(
  const v3_octree_lod_t *coalesee,
  v3_octree_lod_t *coalesed,
  const v3_voxel_t *(*select)(const v3_voxel_t *V, const size_t V_n))
{
  v3_assert(debug, coalesee != NULL);
  v3_assert(debug, coalesed != NULL);
  v3_assert(debug, select != NULL);
  v3_assert(debug, coalesee->level > coalesed->level);
  v3_assert(debug, (coalesee->level - coalesed->level) == 1);
  /* By storing voxels in Morton-order only linear iteration is required. */
  const unsigned C_src_dim = v3_powi(2, coalesee->level);
  const unsigned C_src_volume = C_src_dim * C_src_dim * C_src_dim;
  const unsigned C_dst_dim = v3_powi(2, coalesed->level);
  const unsigned C_dst_volume = C_dst_dim * C_dst_dim * C_dst_dim;
  unsigned C_src_iter, C_dst_iter;
  for (C_src_iter=0,C_dst_iter=0; C_src_iter<C_src_volume; C_src_iter+=C_dst_volume,C_dst_iter+=1)
    v3_voxel_copy(select(&coalesee->voxels[C_src_iter], C_dst_volume), &coalesed->voxels[C_dst_iter]);
  v3_assert(debug, C_src_iter == C_src_volume);
  v3_assert(debug, C_dst_iter == C_dst_volume);
}

/* This is how V^3 would be used for LODing Minecraft style terrain: */

typedef uint32_t v3_voxel_t;

typedef struct {
  const v3_voxel_t *v;
  size_t o;
} v3_voxel_occurance_t;

V3_INLINE v3_voxel_occurance_t v3_voxel_occurance(const v3_voxel_t *v, size_t o) {
  v3_voxel_occurance_t vo;
  vo.v = v;
  vo.o = o;
  return vo;
}

/* (S)elect the (M)ost (P)rominent (V)oxel. */
V3_INLINE const v3_voxel_t *smpv(const v3_voxel_t V3_RESTRICT *l, const v3_voxel_t V3_RESTRICT *r) {
  /* TODO(mtwilliams): Use a prominence table. */
  return ((*l > *r) ? l : r);
}

/*
** This (p)urely and (r)ecursively (s)elects the (m)ost (o)ccuring, (t)hen the
** (m)ost (p)rominent (v)oxel via an implicit fold.  You can think of it as a
** tweaked version of this:
**
**   def encode[A](list: List[A]): List[(A,Int)] =
**   list.foldLeft(List[(A,Int)]()){ (r,c) =>
**       r match {
**         case (value, count) :: tail =>
**           if (value == c) (c, count+1) :: tail
**           else            (c, 1) :: r
**         case Nil =>
**           (c, 1) :: r
**       }
**   }.reverse
**
** If that isn't enough, below is a pseduocode version that should clarify the
** otherwise terse and cryptic implemenation that follows:
**
**   prsmotmpv(L, R[n], occurrences = 1):
**     if L == R[0]:
**       return prsmotmpv(L, R[1..n], occurrences + 1)
**     else:
**       l = prsmotmpv(L, R[1..n], occurrences)
**       r = prsmotmpv(R[0], R[1..n])
**       if l occurs more often than r:
**         return l
**       else if r occurs more often than l:
**         return r
**       else if l is more prominent than r:
**         return l
**       else
**         return r
**
**/

v3_voxel_occurance_t prsmotmpv(const v3_voxel_t V3_RESTRICT *L, const v3_voxel_t V3_RESTRICT *R, size_t R_n, size_t o) {
  if (v3_unlikely(R_n == 0))
    return v3_voxel_occurance(L, o);
  if (*L == *R[0])
    return prsmotmpv(L, &R[1], R_n-1, o+1);
  const v3_voxel_occurance l = prsmotmpv(L, &R[1], R_n-1, o);
  const v3_voxel_occurance r = prsmotmpv(R[0], &R[1], R_n-1, 0);
  return ((l.o > r.o) ? l : ((r.o > l.o) ? r : smpv(l.v, r.v)));
}

const v3_voxel_t *select_most_prominent(const v3_voxel_t *V, const size_t V_n) {
  /* OPTIMIZATION(mtwilliams): Make a copy of `V` with `alloca`. Use `rsmotmpv`
    instead of `prsmotmpv`, which marks any L==R[0] matches via the highest bit
    in `v3_voxel_t` and early outs when it encounters an already matched match. */
  /* OPTIMIZATION(mtwilliams): If faster, a qsort and one-line for-loop can be
    used. */
  return prsmotmpv(&V[0] &V[1], V_n-1).v;
}