// ============================================================================
// ISLANDS — does the shell still cost the empty ground between buildings?
//
// dc_level_shell::build takes the AABB of EVERY brush and allocates one dense
// grid over it, so its cost is set by how far apart things are rather than by
// how much geometry there is. Scattered buildings — the ordinary shape of a
// large map — are therefore the pathological case, and they arrive long before
// a genuinely large single level does.
//
// Two identical sealed huts, 29848 triangles either way. The `flat` column is
// what that cost before build_islands existed; it is kept as the control,
// because a speedup with nothing to be faster THAN is not a measurement.
//
// The parity half lives in tests/test_level_shell.cpp's dump: on a CONNECTED
// level islands must be byte-identical to flat, or every acceptance number in
// docs/level-mesh-implementation.md §6.2 is invalidated by the change.
//
// Build: g++ -O2 -std=c++17 -I libdc/include -o /tmp/shell_islands \
// tests/test_shell_islands.cpp libdc/src/dc_csg4.cpp \
// libdc/src/dc_level_shell.cpp
// ============================================================================
#include "dc_level_shell.h"
#include <cstdio>
#include <vector>
#include <chrono>
#include <cmath>
static void box(std::vector<ConvexPlane>& p, float x0,float y0,float z0,float x1,float y1,float z1){
p = {{-1,0,0,-x0},{1,0,0,x1},{0,-1,0,-y0},{0,1,0,y1},{0,0,-1,-z0},{0,0,1,z1}};
}
// A sealed 10x6x10 hut: six slabs.
static void hut(std::vector<std::vector<ConvexPlane>>& store, float ox, float oz) {
const float t = 0.5f;
float x0=ox, x1=ox+10, z0=oz, z1=oz+10, y0=0, y1=6;
std::vector<std::vector<float>> parts = {
{x0,y0,z0,x1,y0+t,z1}, {x0,y1-t,z0,x1,y1,z1},
{x0,y0+t,z0,x0+t,y1-t,z1}, {x1-t,y0+t,z0,x1,y1-t,z1},
{x0+t,y0+t,z0,x1-t,y1-t,z0+t}, {x0+t,y0+t,z1-t,x1-t,y1-t,z1},
};
for (auto& q : parts) { store.emplace_back(); box(store.back(), q[0],q[1],q[2],q[3],q[4],q[5]); }
}
static int failures = 0;
static void run(const char* label, float sx, float sz) {
std::vector<std::vector<ConvexPlane>> store;
hut(store, 0, 0);
hut(store, sx, sz);
std::vector<CSG4Brush> bs(store.size());
for (size_t i=0;i<store.size();i++){
bs[i].planes = store[i].data();
bs[i].plane_count = (uint32_t)store[i].size();
bs[i].id = (uint32_t)i;
}
dc_csg4::compute_bounds(bs);
dc_level_shell::ShellMesh a, b2;
auto t0 = std::chrono::high_resolution_clock::now();
dc_level_shell::build(bs, a);
auto t1 = std::chrono::high_resolution_clock::now();
int islands = 0;
dc_level_shell::build_islands(bs, b2, dc_level_shell::DEFAULT_CELL,
dc_level_shell::DEFAULT_CLAMP_CELLS,
dc_level_shell::DEFAULT_MERGE, &islands);
auto t2 = std::chrono::high_resolution_clock::now();
double ms_flat = std::chrono::duration<double,std::milli>(t1-t0).count();
double ms_isl = std::chrono::duration<double,std::milli>(t2-t1).count();
printf("%-22s flat %8.1f ms (%9lld cells) islands %7.1f ms (%d) speedup %6.1fx tris %d/%d sealed %d/%d\n",
label, ms_flat, (long long)a.grid[0]*a.grid[1]*a.grid[2],
ms_isl, islands, ms_flat / (ms_isl > 0.01 ? ms_isl : 0.01),
a.triangle_count(), b2.triangle_count(),
(int)a.sealed(), (int)b2.sealed());
// WHAT IS ASSERTED DEPENDS ON THE ISLAND COUNT, and getting that wrong was my
// first attempt at this test.
//
// ONE island: the buffers must be BYTE-IDENTICAL. Same brushes, same single
// grid, so any difference at all is the clustering having changed the answer —
// and every acceptance number in §6.2 rests on that not happening. Proved on
// the real START.MAP, which is one connected building.
//
// TWO islands: byte-parity is NOT expected and demanding it is a bug in the
// test. Each island grids over ITS OWN extent, so its lattice origin is its own
// bounds minus two cells rather than the bounds of everything — a different
// PHASE, and vertices are emitted per island rather than in one sweep. The
// surface is equivalent, not identical, and it differs by less than the
// half-cell fringe the header already documents. So the invariants are the
// ones that carry meaning: the same triangles, the same seal, and a volume that
// agrees to within a fraction of a percent.
if (islands == 1) {
if (a.vertices != b2.vertices || a.indices != b2.indices) {
printf(" ** FAIL: one island, but the buffers differ\n"); failures++;
}
} else {
if (a.triangle_count() != b2.triangle_count()) {
printf(" ** FAIL: triangle count %d vs %d\n", a.triangle_count(), b2.triangle_count());
failures++;
}
const double dv = (a.volume > 0.0) ? std::fabs(a.volume - b2.volume) / a.volume : 0.0;
if (dv > 0.01) {
printf(" ** FAIL: volume %.1f vs %.1f (%.2f%%)\n", a.volume, b2.volume, dv * 100.0);
failures++;
}
}
if (a.sealed() != b2.sealed()) { printf(" ** FAIL: sealed() disagrees\n"); failures++; }
// Adjacent huts are ONE island; separated ones are two. Getting this backwards
// is the whole feature failing quietly — one island means no speedup, and
// splitting a connected building means grids that overlap and redo each other.
const int want = (sx > 40 || sz > 40) ? 2 : 1;
if (islands != want) {
printf(" ** FAIL: expected %d island(s), got %d\n", want, islands); failures++;
}
}
int main(){
printf("two sealed 10x6x10 huts, cell 0.25 m — cost vs how far apart they are\n\n");
printf("-- scattered along ONE axis --\n");
run("adjacent (12 m)", 12, 0);
run("200 m apart", 200, 0);
run("1 km apart", 1000, 0);
printf("\n-- scattered along TWO axes (the real map case) --\n");
run("100 m in X and Z", 100, 100);
run("200 m in X and Z", 200, 200);
run("400 m in X and Z", 400, 400);
printf("\n%s (%d failure%s)\n", failures ? "FAILED" : "PASSED", failures,
failures == 1 ? "" : "s");
return failures ? 1 : 0;
}