A fast 2D and 3D game engine — TypeScript SDK, C++/WebAssembly core, visual editor. Ship one project to web, desktop, WeChat MiniGames, playable ads, and native Android / iOS.
TypeScript 2d-game-engine3d3d-game-engineandroidcppecsgame-editorgame-enginegamedeviostypescriptwebassemblywebglwebgpuwechat-minigame
// SPDX-License-Identifier: Apache-2.0
// SPDX-FileCopyrightText: Copyright (c) 2024-present ESEngine Team
/**
* @file The glyph SDF generator skips the sites of its distance transform that
* cannot change a byte of the result. These hold it, byte for byte, against
* the transform with no shortcuts, on shapes that exercise each skip.
*/
#define DOCTEST_CONFIG_IMPLEMENT_WITH_MAIN
#include "doctest.h"
#include "esengine/text/SdfGenerator.hpp"
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
using esengine::u8;
using esengine::text::sdfFromAlpha;
namespace {
constexpr float kInf = 1e20f;
/** The plain Felzenszwalb–Huttenlocher transform: every site enters the envelope. */
void plain1d(const float* f, float* d, int* v, float* z, int n) {
int k = 0;
v[0] = 0;
z[0] = -kInf;
z[1] = kInf;
for (int q = 1; q < n; ++q) {
float s;
while (true) {
const int p = v[k];
s = (f[q] + float(q) * q - (f[p] + float(p) * p)) / (2.0f * (q - p));
if (s > z[k]) break;
--k;
}
++k;
v[k] = q;
z[k] = s;
z[k + 1] = kInf;
}
k = 0;
for (int q = 0; q < n; ++q) {
while (z[k + 1] < float(q)) ++k;
const float dx = float(q - v[k]);
d[q] = dx * dx + f[v[k]];
}
}
void plain2d(std::vector<float>& g, int w, int h) {
const int m = std::max(w, h);
std::vector<float> f(m), d(m), z(m + 1);
std::vector<int> v(m);
for (int x = 0; x < w; ++x) {
for (int y = 0; y < h; ++y) f[y] = g[size_t(y) * w + x];
plain1d(f.data(), d.data(), v.data(), z.data(), h);
for (int y = 0; y < h; ++y) g[size_t(y) * w + x] = d[y];
}
for (int y = 0; y < h; ++y) {
plain1d(&g[size_t(y) * w], d.data(), v.data(), z.data(), w);
std::copy_n(d.data(), w, &g[size_t(y) * w]);
}
}
std::vector<u8> plainSdf(const std::vector<u8>& alpha, int w, int h, float spread) {
const size_t n = size_t(w) * h;
std::vector<float> outer(n), inner(n);
for (size_t i = 0; i < n; ++i) {
const float a = alpha[i] / 255.0f;
if (a >= 1.0f) { outer[i] = 0; inner[i] = kInf; }
else if (a <= 0.0f) { outer[i] = kInf; inner[i] = 0; }
else {
const float dOut = std::max(0.0f, 0.5f - a), dIn = std::max(0.0f, a - 0.5f);
outer[i] = dOut * dOut;
inner[i] = dIn * dIn;
}
}
plain2d(outer, w, h);
plain2d(inner, w, h);
const float scale = spread > 0 ? 127.0f / spread : 127.0f;
std::vector<u8> out(n);
for (size_t i = 0; i < n; ++i) {
// Clamped before it is rounded: a grid with no exterior reads about 1e10 here, past a 32-bit long.
const long b = std::lround(std::clamp(128.0f + (std::sqrt(inner[i]) - std::sqrt(outer[i])) * scale, -1.0f, 256.0f));
out[i] = (u8)std::clamp(b, 0L, 255L);
}
return out;
}
void holdAgainstPlain(const std::vector<u8>& alpha, int w, int h, float spread) {
std::vector<u8> out(alpha.size(), 77);
sdfFromAlpha(alpha.data(), out.data(), (esengine::u32)w, (esengine::u32)h, spread);
const std::vector<u8> want = plainSdf(alpha, w, h, spread);
int worst = 0;
for (size_t i = 0; i < out.size(); ++i) worst = std::max(worst, std::abs(int(out[i]) - int(want[i])));
CHECK(worst == 0);
}
/** Antialiased disc: every edge direction, partial texels all round. */
void disc(std::vector<u8>& a, int w, int h, float cx, float cy, float r) {
for (int y = 0; y < h; ++y) for (int x = 0; x < w; ++x) {
const float d = std::hypot(x + 0.5f - cx, y + 0.5f - cy) - r;
const float c = std::clamp(0.5f - d, 0.0f, 1.0f);
a[size_t(y) * w + x] = std::max(a[size_t(y) * w + x], (u8)std::lround(c * 255));
}
}
} // namespace
TEST_CASE("every skip gives the plain transform's bytes") {
const int w = 120, h = 96;
const size_t n = size_t(w) * h;
SUBCASE("nothing: every line has no site in one field") {
holdAgainstPlain(std::vector<u8>(n, 0), w, h, 12.0f);
}
SUBCASE("everything covered") {
holdAgainstPlain(std::vector<u8>(n, 255), w, h, 12.0f);
}
SUBCASE("a single partial texel") {
std::vector<u8> a(n, 0);
a[size_t(40) * w + 60] = 90;
holdAgainstPlain(a, w, h, 12.0f);
}
SUBCASE("hard-edged bars: long runs of zeros in both fields") {
std::vector<u8> a(n, 0);
for (int y = 10; y < 22; ++y) for (int x = 8; x < 110; ++x) a[size_t(y) * w + x] = 255;
for (int y = 40; y < 90; ++y) for (int x = 50; x < 54; ++x) a[size_t(y) * w + x] = 255;
holdAgainstPlain(a, w, h, 12.0f);
}
SUBCASE("ink touching every border") {
std::vector<u8> a(n, 0);
for (int x = 0; x < w; ++x) { a[x] = 255; a[size_t(h - 1) * w + x] = 255; }
for (int y = 0; y < h; ++y) { a[size_t(y) * w] = 200; a[size_t(y) * w + w - 1] = 40; }
holdAgainstPlain(a, w, h, 12.0f);
}
SUBCASE("antialiased discs, near and far apart past the spread") {
std::vector<u8> a(n, 0);
disc(a, w, h, 20, 20, 12);
disc(a, w, h, 95, 70, 18);
disc(a, w, h, 30, 80, 3);
holdAgainstPlain(a, w, h, 12.0f);
holdAgainstPlain(a, w, h, 3.0f);
holdAgainstPlain(a, w, h, 40.0f);
}
SUBCASE("noise: partial texels everywhere") {
std::vector<u8> a(n);
unsigned seed = 12345;
for (size_t i = 0; i < n; ++i) {
seed = seed * 1103515245u + 12345u;
a[i] = (seed >> 16) & 7 ? 0 : (u8)((seed >> 8) & 255);
}
holdAgainstPlain(a, w, h, 12.0f);
}
SUBCASE("no spread") {
std::vector<u8> a(n, 0);
disc(a, w, h, 60, 48, 20);
holdAgainstPlain(a, w, h, 0.0f);
}
}
TEST_CASE("sizes in turn share the kept scratch without leaking between them") {
std::vector<u8> big(size_t(200) * 200, 0);
disc(big, 200, 200, 100, 100, 60);
holdAgainstPlain(big, 200, 200, 12.0f);
std::vector<u8> small(size_t(16) * 24, 0);
disc(small, 16, 24, 8, 12, 5);
holdAgainstPlain(small, 16, 24, 4.0f);
holdAgainstPlain(big, 200, 200, 12.0f);
// Past what is kept: the scratch is dropped, and the next call has to come back with its own.
std::vector<u8> huge(size_t(1100) * 1000, 0);
disc(huge, 1100, 1000, 500, 500, 300);
holdAgainstPlain(huge, 1100, 1000, 8.0f);
holdAgainstPlain(small, 16, 24, 4.0f);
}