Navmesh, lightmaps и lightprobes: реализация и использование в Playcanvas

Выбор Playcanvas

Для меня ведь программирование всегда было отдыхом и способом отвлечься от работы. Довольно естественно, что большинство моих разработок касается геймдева или близко к нему. Можно не спеша выбирать технологии, делать какие-то прототипы, присматриваться и однажды обнаружить, что всё, в чём разобрался, уже давно устарело. По факту наиболее интересными оказываются 3d-игры для браузера. Вот даже не знаю почему. Может быть потому что совсем не умею рисовать руками (поэтому 3d), и потому что браузерные игры кажутся очень доступными: бесплатно, на расстоянии в 1 клик, при должной сноровке можно растормошить на составляющие. Началось это ещё с тех пор, когда браузерные игры переживали расцвет. Так вот всё и не отпускает.

Не будем забывать про главную проблему всех бедных независимых разработчиков, которые никогда ничего не сделают - какой движок выбрать? И тут с самого начала не хотелось бы использовать Unity. Слишком уж он хорош. Это становится особенно заметным после того, как от него отказываешься. Хотелось бы ограничиться нативным игровым движком для браузера. Посмотрев несколько из них, решил остановиться на Playcanvas. Объём самого движка не очень большой (что-то около 1-го мегабайта в минифицированном виде), есть базовые возможности не только связанные с выводом графики, но и с другими задачами при разработке игр. Впрочем, есть и альтернативы, BabylonJS тот же самый, или Cocos.

Теперь о проблемах. В Playcanvas есть многое. Но ещё больше того, чего в нём нет, но что в общем-то нужно. Поэтому неизбежно надо часть модулей делать самостоятельно. В этой заметке я хотел бы рассказать про две таких темы. Первая тема - это построение и использование navmesh-ей. Вторая тема - создание и использование lightmap-ов и lightprob-ов. Это есть в Unity, этого нет в Playcanvas. Надо реализовывать. Обсудим немного теории по обеим темам, а также то, как всё это можно сделать внутри Playcanvas. Надеюсь, что эти рецепты и наработки подойдут и под любой другой движок. Playcanvas можно использовать в двух вида: как фрэймворк, создавая web-приложение с использованием любого инструментария web-разработки (WebPack там, TypeScript и прочее), а можно собирать сцены в браузерном редакторе. Редактор этот довольно простой, вот мы и будем его использовать.

Сразу дам ссылку на демо-проект. Это небольшое игровое приложение, в котором реализовано всё то, о чём пойдёт речь.

Navmesh

Навигационная сетка (традиционно используется англицизм navmesh) - это подход к отысканию кратчайшего расстояния между двумя точками в трёхмерной сцене. Тут есть две совершенно разные задачи: построить navmesh, и использовать его. Для построения часто используется алгоритм, реализованный в репозитории. Такое впечатление, что если какой-то игровой движок умеет запекать navmesh, то значит в него сделана интеграция из этого репозитория. Простейшую версию алгоритма я портировал на Python и AssemblyScript. Вот ссылка. Поэтому будем считать, что сам navmesh мы умеем строить и в любой момент можем получить его полигональное представление, то есть список вершин в трёхмерном пространстве и наборы индексов вершин, задающих полигоны.

Теперь задача - как найти путь между двумя точками на полигонах построенного navmesh-а. Рассмотрим простой пример. Сцена выглядит так

Запечённый navmesh так

Предлагается использовать подход, предложенный в репозитории. Суть такова. На этапе подготовки полигоны navmesh-а укладываются в BVH (Bounding Volume Hierarchy) и строится двойственный граф. Вершинами этого графа являются центры полигонов, и две вершины соединены ребром, если соответствующие им полигоны имеют общую сторону. Попутно ещё сохраняется всякая дополнительная информация о том, какой полигон по какой стороне с каким другим полигоном граничит.

Кратко опишем, как происходит поиск пути. Берём две точки

Находим в каких полигонах они содержатся. Это быстро делается с помощью BVH-а. Потом берём двойственные им вершины графа, после чего находим кратчайший между ними путь в графе с использованием банального A*.

Найденный путь задаёт коридор из полигонов в navmesh-е

Далее строится избыточный путь по вершинам рёбер смежности полигонов этого коридора

На последнем этапе этот путь упрощается отбрасыванием неэффективных участков

Описанный подход хорошо тем, что является довольно быстрым. А плох он тем, что в некоторых случаях выдаёт далеко не кратчайший путь. Вот как на этой картинке

Причина понятна. Когда в двойственном графе нашли кратчайший путь между центрами полигонов, он не обязан задавать коридор, содержащий кратчайший путь. Может быть наоборот, кратчайший путь проходит по коридору, который в двойственном графе не самый короткий. Но в целом, если сам navmesh построен аккуратно, то такой алгоритм даёт правдоподобный ответ. Годится.

Как использовать navmesh в редакторе Playcanvas

Небольшой игровой уровень имеет вот такую геометрию

Запечённый navmesh выглядит так

Теперь качаем по ссылке файлы navmesh.wasm и navmesh.js. Это wasm-модуль с описанным выше алгоритмом, реализованным на языке AssemblyScript, и JavaScript-обёртка для него. Закидываем оба файла в редактор Playcanvas-а. Вообще в этом редакторе есть встроенная возможность подключать wasm-модули, но только работает это для модулей, скомпилированных Emscripten-ом. А у нас скомпилировано из AssemblyScript. Поэтому придётся подключать вручную. Но это не сложно.

Проверяем, что в Script Loading Order наш файл navmesh.js стоит повыше

Создаём скрипт navmeshController.js и вешаем его на какой-нибудь объект в сцене. Создаём два атрибута

var NavmeshController = pc.createScript("navmeshController");
NavmeshController.attributes.add("wasm_asset", {type: "asset"});
NavmeshController.attributes.add("navmesh_asset", {type: "asset", assetType: "binary"});

Атрибут wasm_asset должен содержать ссылку на wasm-модуль. Атрибут navmesh_asset должен содержать ссылку на файл с описанием полигонального представления navmesh-а. Я использую бинарный формат, в который прямо как есть записаны три числовых массива: координаты вершин, индексы вершин полигонов и размеры полигонов (их число сторон). Можно эти данные писать и в текстовый формат (да даже в json). Особой разницы нет.

Надо немного подправить обёртку navmesh.js. Причина в том, что из редактора нельзя загружать JavaScript-овые модули. Поэтому просто комментируем кусок с экспортами в самом конце

...
  return adaptedExports;
}
/*export const {
  memory,
  create_graph,
  create_navmesh,
  graph_search,
  graph_to_bytes,
  graph_from_bytes,
  navmesh_get_groups_count,
  navmesh_search_path,
  navmesh_search_path_batch,
  navmesh_sample,
  navmesh_raycast,
  navmesh_intersect_boundary,
  navmesh_set_bvh_delta,
  navmesh_get_bvh_delta,
  navmesh_to_bytes,
  navmesh_from_bytes,
  create_rtree,
  rtree_insert_polygon,
  rtree_insert_point,
  rtree_insert_edge,
  rtree_search,
  rtree_insert_edges,
  rtree_find_intersection,
  rtree_to_bytes,
  rtree_from_bytes
} = await (async url => instantiate(
  await (async () => {
    try { return await globalThis.WebAssembly.compileStreaming(globalThis.fetch(url)); }
    catch { return globalThis.WebAssembly.compile(await (await import("node:fs/promises")).readFile(url)); }
  })(), {
  }
))(new URL("navmesh.wasm", import.meta.url));*/

Далее пишем метод инициализации в скрипте navmeshController. Он автоматически вызывается при старте

NavmeshController.prototype.initialize = function() {
    this.exports = null;
    this.navmesh = null;
};

Содержимое такое. Сначала надо прочитать данные из атрибута navmesh_asset и перевести их в числовой формат. Например так

const view = new DataView(this.navmesh_asset.resource);
const count = view.byteLength / 4;
let stage = 0;
let vertices = [];
let polygons = [];
let sizes = [];
for (let i = 0; i < count; i++) {
	let v_float = view.getFloat32(4*i);
	let v_int = view.getInt32(4*i);
	
	if (v_float == Infinity) {
		stage += 1;
	}
	else {
		if (stage == 0) {
			vertices.push(v_float);
		}
		else if (stage == 1) {
			polygons.push(v_int);
		}
		else if (stage == 2) {
			sizes.push(v_int);
		}
	}
}

В результате получаем три нужных массива: vertices, polygons и sizes. Далее подгружаем wasm-модуль

fetch(this.wasm_asset.getFileUrl())
	.then((response) => globalThis.WebAssembly.compileStreaming(response))
	.then((module) => instantiate(module))
	.then((inst) => this.init_navmesh(inst, vertices, polygons, sizes));

Тут используется команда instantiate(module) как раз из обёртки navmesh.js. Помимо этого надо ещё сделать метод init_navmesh

NavmeshController.prototype.init_navmesh = function(exports, vertices, polygons, sizes) {
    this.exports = exports;
    this.navmesh = this.exports.create_navmesh(vertices, polygons, sizes);
};

Вот и всё, this.exports содержит все функции из wasm-модуля, а this.navmesh - ссылка на построенный navmesh. Теперь каждый найдёт свой путь. Делается это просто

this.exports.navmesh_search_path(this.navmesh, start[0], start[1], start[2], end[0], end[1], end[2]);

Ещё пару слов про модуль navmesh.wasm

Вообще этот модуль содержит несколько вспомогательных конструкций, которые тоже оказываются полезными. При построении navmesh-а треугольники его триангуляции укладываются в отдельный BVH. Его можно использовать, чтобы найти точку на navmesh-е, ближайшую к данной. Полезно, когда мы куда-то кликаем и хотим понять, а попали ли вообще по какому-нибудь полигону или мимо кликнули. Для этого вызываем функцию this.exports.navmesh_sample(this.navmesh, x, y, z). Она всегда возвращает массив из четырёх элементов. Если последний равен 1, то значит первые три - это координаты ближайшей точки. Если 0, то кликнули мимо.

Ещё есть метод this.exports.navmesh_raycast(this.navmesh, origin_x, origin_y, origin_z, dir_x, dir_y, sir_z), который находит точку пересечения луча с navmesh-ем.

Ещё строится RTree для граничных рёбер. Его удобно использовать, чтобы проверить, не пересекается ли отрезок с границей navmesh-а. Ну и вообще там много всего, можно справку посмотреть.

Lightmap-ы

Тут почти не о чем говорить. Стандартный материал Playcanvas содержит слот для lightmap-ов. Вся сложность состоит в том, чтобы подготовить эти текстуры в 3d-редакторе. Потом их можно загрузить в редактор Playcanvs и назначить материалам.

Рассмотрим это вот на таком классическом примере

Это результат рендера в Cycles. Тут есть один источник направленного света, один источник внешнего окружения, статическая геометрия и шарик, он будет играть роль динамического объекта. Предлагается запекать в lightmap-у только непрямое освещение, а прямое вместе с тенями считать от источника в реальном времени.

Вот результат запекания. Получить такое можно в любом 3d-редакторе, хоть даже и в том же Blender-е

Тут стоит упомянуть такой нюанс. Сама lightmap-а не должна содержать в себе информации о диффузном компоненте поверхности. То есть запекаться должна как будто на белую поверхность. В Blender-е этого можно добиться отключив параметр Color в настройках запекания диффузного цвета

Связано это с тем, что в стандартном шэйдере в Playcanvas цвет lightmap-ы умножается на диффузный цвет. Ну и получается в итоге как надо.

Теперь импортируем статическую геометрию в редактор Playcanvas. Там создаём материалы и назначаем подготовленную lightmap-у в нужный слот

Скрин из окна редактора

Вид из камеры

Похоже?.. Похоже!

Lightmap-ы для игрового уровня

Наш игровой уровень состоит из двух больших модулей

Вот результат его рендера

Не смотря на то, что в уровне довольно много источников света (это вот такие оранжевые кружочки на скрине выше), влияние каждого из них по отдельности не очень заметно. Поэтому я решил только четыре источника оставить динамическими

В lightmap-ы запечено не только непрямое освещение, но и прямое от всех источников света, кроме четырёх выделенных. Получились вот такие lightmap-ы

Вот как выглядит сцена в редакторе с назначенными текстурами

Выглядит если и не один к одному с пререндером, то по крайней мере похоже. Хотя, конечно, косяки есть.

Вот этот пример прямо очень наглядно показывает, что одних только lightmap для освещения уровня не достаточно. Если добавить динамическую модель, то она будет практически не освещенной. Источников света ведь в реальности на уровне почти что и нет

И вот тут мы как раз и подходим к следующей технике - lightprob-ам, которые позволяют добавить статическое запечённое освещение к динамическим объектам.

Lightprob-ы

Что такое lightprob-ы? Это информация об освещённости в окрестности одной конкретной точки пространства. Для записи этой информации можно использовать разные техники. Самое простое - писать данные в текстуру. Например, можно представить, что в пространстве располагается маленькая сфера, и в текстуру запечена освещённость этой сферы. Минус такого подхода в том, что текстура - это слишком много данных. В подавляющем числе случаев эти данные избыточны.

Для оптимизации используется следующее наблюдение. Каждый канал запечённой текстуры (R, G и B) можно расценивать как дискретную функцию на сфере. Аргументом у этой функции являются сферические координаты, а значением - величина R-, G- или B-канала в соответствующем пикселе. Идея состоит в том, чтобы интерполировать эти дискретные функции какой-нибудь гладкой функцией с небольшим числом параметров. Метод такой интерполяции называется сферическими гармониками. Это что-то вроде разложения обычной функции в ряд Тейлора, но только не для функции на числовой прямой, а для функции на сфере. Так как карта освещённости в большинстве случаев не содержит резких переходов, то достаточно каждую из функций интерполировать лишь первыми несколькими слагаемыми. Обычно используют сферические гармоники порядков 1, 2 и 3. Они задаются в общей сумме девятью коэффициентами, и поэтому одна lightrob-а полностью описывается 30 числами: 3 числа - местоположение в пространстве, 9 чисел - каждый канал карты освещённости.

Это, значит, общая идея. Теперь детали. Весь код основан на вот этом репозитории. Я не буду объяснять математику, скрывающуюся за всеми вычислениями, она достаточно тривиальна. Помимо этого есть большое число литературы, в которой всё подробно объяснено (с формулами, интегралами и прочей наукообразной заумью). Например, можно посмотреть оригинальную статью Ravi Ramamoorthi and Pat Hanrahan, An Efficient Representation for Irradiance Environment Maps // SIGGRAPH, 2001, 497-500. Она легко гуглится, например вот: https://cseweb.ucsd.edu/~ravir/papers/envmap/

Итак, сначала сгенерируем набор равномерно распределённых шариков по navmesh-у нашего уровня

Нам нужно записать освещённость только в этих точках, так как в остальных местах динамический объект никогда не может появиться. Более того, наш уровень фактически двумерный, поэтому изменение освещённости по высоте нам тоже не нужно никак отслеживать.

Дальше банально запекаем освещение в lightmap-у. Можно даже особо за качеством не следить, подойдёт и небольшое число сэмплов при рендере

Дальше для каждого куска (прямоугольничка на текстуре) находим коэффициенты интерполирующих его сферических гармоник. Приведу просто код на c++

float x_to_phi(int x, int width) {
    return 2.0 * M_PI * (x + 0.5) / width;
}

float y_to_theta(int y, int height) {
    return M_PI * (y + 0.5) / height;
}

size_t get_index(int l, int m) {
    return l * (l + 1) + m;
}

void to_vector(float phi, float theta, float& x, float& y, float& z) {
    float r = sin(theta);
    x = r * cos(phi);
    y = r * sin(phi);
    z = cos(theta);
}

float clamp(float val, float min, float max) {
    if (val < min) { val = min; }
    if (val > max) { val = max; }
    return val;
}

void to_spherical(float x, float y, float z, float& phi, float& theta) {
    theta = acos(clamp(z, -1.0, 1.0));
    phi = atan2(y, x);
}

float hardcoded_sh_00(float x, float y, float z) {
    return 0.282095;
}

float hardcoded_sh_1n1(float x, float y, float z) {
    return -0.488603 * y;
}

float hardcoded_sh_10(float x, float, float z) {
    return 0.488603 * z;
}

float hardcoded_sh_1p1(float x, float y, float z) {
    return -0.488603 * x;
}

float hardcoded_sh_2n2(float x, float y, float z) {
    return 1.092548 * x * y;
}

float hardcoded_sh_2n1(float x, float y, float z) {
    return -1.092548 * y * z;
}

float hardcoded_sh_20(float x, float y, float z) {
    return 0.315392 * (-x * x - y * y + 2.0 * z * z);
}

float hardcoded_sh_2p1(float x, float y, float z) {
    return -1.092548 * x * z;
}

float hardcoded_sh_2p2(float x, float y, float z) {
    return 0.546274 * (x * x - y * y);
}

float eval_sh(int l, int m, float x, float y, float z) {
    switch (l) {
    case 0:
        return hardcoded_sh_00(x, y, z);
    case 1:
        switch (m) {
        case -1:
            return hardcoded_sh_1n1(x, y, z);
        case 0:
            return hardcoded_sh_10(x, y, z);
        case 1:
            return hardcoded_sh_1p1(x, y, z);
        }
    case 2:
        switch (m) {
        case -2:
            return hardcoded_sh_2n2(x, y, z);
        case -1:
            return hardcoded_sh_2n1(x, y, z);
        case 0:
            return hardcoded_sh_20(x, y, z);
        case 1:
            return hardcoded_sh_2p1(x, y, z);
        case 2:
            return hardcoded_sh_2p2(x, y, z);
        }
    }
    return 0.0;
}

float eval_sh(int l, int m, float phi, float theta) {
    float x, y, z;
    to_vector(phi, theta, x, y, z);
    return eval_sh(l, m, x, y, z);
}

float linear_to_srgb(float v) {
	if (v <= 0.0f) {
		return 0.0;
	}
	if (v >= 1.0f) {
		return v;
	}
	if (v <= 0.0031308f) {
		return  12.92f * v;
	}

	return (1.055f * pow(v, 1.0f / 2.4f)) - 0.055f;
}

std::vector<float> image_to_sh(const std::vector<float>& image_pixels, size_t width, size_t height, size_t channels, bool apply_srgb) {
    std::vector<float> to_return(3 * 9);

    float pixel_area = (2.0 * M_PI / width) * (M_PI / height);

    for (size_t y = 0; y < height; y++) {
        float theta = y_to_theta(y, height);
        float weight = pixel_area * sin(theta);

        for (size_t x = 0; x < width; x++) {
            float phi = x_to_phi(x, width);

            float r = image_pixels[channels * (y * width + x)];
            float g = image_pixels[channels * (y * width + x) + 1];
            float b = image_pixels[channels * (y * width + x) + 2];
            if (apply_srgb) {
                r = linear_to_srgb(r);
                g = linear_to_srgb(g);
                b = linear_to_srgb(b);
            }

            for (int l = 0; l <= 2; l++) {
                for (int m = -l; m <= l; m++) {
                    size_t i = get_index(l, m);
                    float sh = eval_sh(l, m, phi, theta);

                    // update the i-th coefficient
                    to_return[3 * i] += sh * weight * r;
                    to_return[3 * i + 1] += sh * weight * g;
                    to_return[3 * i + 2] += sh * weight * b;
                }
            }
        }
    }

    return to_return;
}

Функция, которая тут нужна - это image_to_sh. Она на вход принимает массив пикселей картинки, её размеры и true/false в зависимости от того, надо ли делать преобразование в sRGB или нет. Результатом работы является массив из 27 чисел, в котором коэффициенты для гармоник сгруппированы по их порядкам: сначала три числа (для R, G и B каналов), задающих первый коэффициент, потом ещё три числа для второго коэффициента и так далее.

Пример работы. Вот входная картинка размера 256x128

Получающийся массив коэффициентов, задающих сферические гармоники

[1.7648712396621704, 1.6993560791015625, 1.7052123546600342, 
 -0.5724795460700989, -0.4202347695827484, -0.1682588905096054, 
 0.4165051579475403, 0.4504852890968323, 0.5280810594558716, 
 -0.37911805510520935, -0.32987675070762634, -0.2012496143579483,
 0.10270054638385773, 0.11499594151973724, 0.09571883082389832, 
 -0.07035323977470398, -0.048954349011182785, -0.01829037256538868, 
 -0.1626722514629364, -0.13568037748336792, -0.09725187718868256, 
 -0.04176412150263786, -0.023417677730321884, 0.0016406839713454247, 
 -0.007291402202099562, -0.00979363452643156, 0.003937914036214352]

Теперь давайте в обратную сторону. У нас есть набор коэффициентов, как по ним вычислить освещённость, то есть получить исходную текстуру. Вот код

float eval_sh_sum(const std::vector<float>& sh_coefficients, int channel, float x, float y, float z) {
    float sum = 0.0f;
    for (int l = 0; l <= 2; l++) {
        for (int m = -l; m <= l; m++) {
            sum += eval_sh(l, m, x, y, z) * sh_coefficients[get_index(l, m) * 3 + channel];
        }
    }
    return sum;
}

std::vector<float> sh_to_image(const std::vector<float>& sh_coefficients, int width, int height) {
    std::vector<float> to_return(width * height * 3);  // return 3-channel image

    for (size_t y = 0; y < height; y++) {
        float theta = y_to_theta(y, height);
        for (size_t x = 0; x < width; x++) {
            float phi = x_to_phi(x, width);
            float dir_x, dir_y, dir_z;
            to_vector(phi, theta, dir_x, dir_y, dir_z);

            to_return[3 * (width * y + x)] = eval_sh_sum(sh_coefficients, 0, dir_x, dir_y, dir_z);
            to_return[3 * (width * y + x) + 1] = eval_sh_sum(sh_coefficients, 1, dir_x, dir_y, dir_z);
            to_return[3 * (width * y + x) + 2] = eval_sh_sum(sh_coefficients, 2, dir_x, dir_y, dir_z);
        }
    }

    return to_return;
}

Тут нужна функция sh_to_image. На вход она принимает массив из коэффициентов и размеры выходной текстуры. Результатом является массив пикселей получающейся текстуры.

Применяем эту функцию к полученным коэффициентам, получаем результат

Эффектно?.. Не то слово!

В общем, будем считать, что для каждой lightprob-ы мы получили набор коэффициентов и записали всё в файл, хотя бы даже в *.json. Закидываем этот файл в редактор Playcanvas, и перед нами встаёт другой вопрос - как всё это использовать?

Использование запечённых lightprob-ов в Playcanvas

По большому счёту надо писать свой шэйдер для динамических объектов, который бы учитывал данные из файла с lightprob-ами. Хорошо, что в Playcanvas есть технология, позволяющая локально менять (а значит и расширять) шэйдер стандартного материала. Называется эта технология chunk patching. Она не очень документирована, но есть достаточное число обсуждений на форуме, кое-чего получается посмотреть в документации и исходном коде. Поэтому разобраться можно.

Шэйдер стандартного материала - это так называемый uber shader. Он содержит много разных параметров, большинство из которых никогда вместе и не нужны. Во время старта приложения из кода шэйдера выбрасываются неиспользуемые куски, и в результате получается ровно тот материал, который нужен. Сам шэйдер состоит из большого числа чанков, как для вершинного кода, так и для фрагментного. Надо правильно подобрать чанк, в который интегрировать нужную нам функциональность.

Мы хотим, чтобы наш модифицированный шэйдер работал следующим образом. В самом начале строится триангуляция Делоне плоскости по местоположениям сгенерированных lightprob-ов. Далее каждый update в материал динамического объекта передаются три массива коэффициентов, задающих сферические гармоники. Их три, не потом что три канала, а потому что динамический объект находится в каком-то треугольнике триангуляции, и передать надо данные об освещённости в каждой из его вершин. Помимо этого передаются барицентрические координаты местоположения динамического объекта в треугольнике триангуляции. Эти координаты используются, чтобы правильно смешать освещённость из трёх вершин, и полученные значения должны быть добавлены к цвету фрагмента.

Будем модифицировать три чанка:

• startVS В него добавим нужные параметры

• endVS В нём будут происходить все вычисления

• emissivePS В нём будем добавлять посчитанный цвет

Создаём в редакторе файл шэйдера (это обычный текстовый файл) с именем startvs_sh_chunk. Копируем в него стандартное содержимое чанка startVS из исходного кода Playcanvas

void main(void) {
    gl_Position = getPosition();

Добавляем нужные нам параметры

varying vec3 sh_color;
uniform vec3 sh0_coefficients[9];
uniform vec3 sh1_coefficients[9];
uniform vec3 sh2_coefficients[9];
uniform vec3 baricenteric_coordinates;

void main(void) {
    gl_Position = getPosition();

Далее точно так же создаём текстовый файл шэйдера endvs_sh_chunk. Его стандартное содержимое пусто, поэтому пишем

vec3 n = vNormalW;

sh_color =
    (sh0_coefficients[0] * baricenteric_coordinates.x + sh1_coefficients[0] * baricenteric_coordinates.y + sh2_coefficients[0] * baricenteric_coordinates.z) * 0.282095 +
    (sh0_coefficients[1] * baricenteric_coordinates.x + sh1_coefficients[1] * baricenteric_coordinates.y + sh2_coefficients[1] * baricenteric_coordinates.z) * -0.488603 * n.z +
    (sh0_coefficients[2] * baricenteric_coordinates.x + sh1_coefficients[2] * baricenteric_coordinates.y + sh2_coefficients[2] * baricenteric_coordinates.z) * 0.488603 * n.y +
    (sh0_coefficients[3] * baricenteric_coordinates.x + sh1_coefficients[3] * baricenteric_coordinates.y + sh2_coefficients[3] * baricenteric_coordinates.z) * -0.488603 * n.x +
    (sh0_coefficients[4] * baricenteric_coordinates.x + sh1_coefficients[4] * baricenteric_coordinates.y + sh2_coefficients[4] * baricenteric_coordinates.z) * 1.092548 * n.x * n.z +
    (sh0_coefficients[5] * baricenteric_coordinates.x + sh1_coefficients[5] * baricenteric_coordinates.y + sh2_coefficients[5] * baricenteric_coordinates.z) * -1.092548 * n.z * n.y +
    (sh0_coefficients[6] * baricenteric_coordinates.x + sh1_coefficients[6] * baricenteric_coordinates.y + sh2_coefficients[6] * baricenteric_coordinates.z) * 0.315392 * (-n.x * n.x - n.z * n.z + 2.0 * n.y * n.y) +
    (sh0_coefficients[7] * baricenteric_coordinates.x + sh1_coefficients[7] * baricenteric_coordinates.y + sh2_coefficients[7] * baricenteric_coordinates.z) * -1.092548 * n.x * n.y +
    (sh0_coefficients[8] * baricenteric_coordinates.x + sh1_coefficients[8] * baricenteric_coordinates.y + sh2_coefficients[8] * baricenteric_coordinates.z) * 0.546274 * (n.x * n.x - n.z * n.z);

Последнее, файл emissive_sh_chunk. Стандартное содержимое

#ifdef MAPCOLOR
uniform vec3 material_emissive;
#endif

#ifdef MAPFLOAT
uniform float material_emissiveIntensity;
#endif

void getEmission() {
    dEmission = vec3(1.0);

    #ifdef MAPFLOAT
    dEmission *= material_emissiveIntensity;
    #endif

    #ifdef MAPCOLOR
    dEmission *= material_emissive;
    #endif

    #ifdef MAPTEXTURE
    dEmission *= $DECODE(texture2DBias($SAMPLER, $UV, textureBias)).$CH;
    #endif

    #ifdef MAPVERTEX
    dEmission *= gammaCorrectInput(saturate(vVertexColor.$VC));
    #endif
}

Модифицируем так

#ifdef MAPCOLOR
uniform vec3 material_emissive;
#endif

#ifdef MAPFLOAT
uniform float material_emissiveIntensity;
#endif

varying vec3 sh_color;

void getEmission() {
    dEmission = vec3(1.0);

    #ifdef MAPFLOAT
    dEmission *= material_emissiveIntensity;
    #endif

    #ifdef MAPCOLOR
    dEmission *= material_emissive;
    #endif

    #ifdef MAPTEXTURE
    dEmission *= $DECODE(texture2DBias($SAMPLER, $UV, textureBias)).$CH;
    #endif

    #ifdef MAPVERTEX
    dEmission *= gammaCorrectInput(saturate(vVertexColor.$VC));
    #endif

    dEmission += sh_color * dAlbedo;
}

Чанки готовы. Теперь их надо заменить в шэйдере материала динамического объекта.

Создаём скрипт probesController.js и вешаем его на какой-нибудь объект сцены. Добавляем атрибутов

var ProbesController = pc.createScript("probesController");
ProbesController.attributes.add("probes_data", {type: 'asset', assetType: 'json'})
ProbesController.attributes.add("emissive_chunk", {type: "asset", assetType: "shader"});
ProbesController.attributes.add("startvs_chunk", {type: "asset", assetType: "shader"});
ProbesController.attributes.add("endvs_chunk", {type: "asset", assetType: "shader"});

Содержимое атрибутов понятно. emissive_chunk, startvs_chunk и endvs_chunk - это ссылки на те текстовые файлы, что мы подготовили, а probes_data - это ссылка на *.json с данными lightprob-ов. На старте приложения нам надо сформировать триангуляцию Делоне и уложить её в BVH для быстрого поиска треугольников. Имеет смысл саму триангуляцию построить вообще заранее и записать её в файл *.json. Поэтому тут напишем только простейшую реализацию BVH

class Triangle {
    constructor(index, i0, i1, i2, positions) {
        this.index = index;
        // point indices
        this.i0 = i0;
        this.i1 = i1;
        this.i2 = i2;

        // point coordinates
        this.v0 = positions[i0];
        this.v1 = positions[i1];
        this.v2 = positions[i2];

        this.center = [(this.v0[0] + this.v1[0] + this.v2[0]) / 3.0, 
                       (this.v0[1] + this.v1[2] + this.v2[3]) / 3.0];
        this.aabb = [Math.min(this.v0[0], this.v1[0], this.v2[0]), 
                     Math.min(this.v0[1], this.v1[1], this.v2[1]),
                     Math.max(this.v0[0], this.v1[0], this.v2[0]), 
                     Math.max(this.v0[1], this.v1[1], this.v2[1])]
        
        // need for baricentric calculations
        this.det = (this.v0[0] - this.v2[0]) * (this.v1[1] - this.v2[1]) - 
                   (this.v1[0] - this.v2[0]) * (this.v0[1] - this.v2[1]);
    }

    get_center() { return this.center; }

    get_aabb() { return this.aabb; }

    get_i0() { return this.i0; }
    get_i1() { return this.i1; }
    get_i2() { return this.i2; }

    is_point_inside(x, y) {
        const as_x = x - this.v0[0];
        const as_y = y - this.v0[1];

        const s_ab = ((this.v1[0] - this.v0[0]) * as_y - (this.v1[1] - this.v0[1]) * as_x) > 0;

        if (((this.v2[0] - this.v0[0]) * as_y - (this.v2[1] - this.v0[1]) * as_x > 0) == s_ab) {
            return false;
        }
        if (((this.v2[0] - this.v1[0]) * (y - this.v1[1]) - (this.v2[1] - this.v1[1]) * (x - this.v1[0]) > 0) != s_ab) {
            return false;
        }
        return true;
    }

    // return 3-valued array [a, b, c] with a + b + c = 1
    get_baricentric(x, y) {
        const l1 = ((this.v1[1] - this.v2[1]) * (x - this.v2[0]) + 
                    (this.v2[0] - this.v1[0]) * (y - this.v2[1])) / this.det;
        const l2 = ((this.v2[1] - this.v0[1]) * (x - this.v2[0]) + 
                    (this.v0[0] - this.v2[0]) * (y - this.v2[1])) / this.det;
        return [l1, l2, 1.0 - l1 - l2];
    }
}

function union_aabbs(a1, a2) {
    return [Math.min(a1[0], a2[0]),
            Math.min(a1[1], a2[1]),
            Math.max(a1[2], a2[2]),
            Math.max(a1[3], a2[3])];
}

class BVHNode {
    constructor(triangles) {
        this.left = null;
        this.right = null;
        this.object = null;
        this.aabb = null;
        const objects_count = triangles.length;
        if (objects_count == 1) {
            this.object = triangles[0];
            this.aabb = this.object.get_aabb();
        } else {
            let median = [0.0, 0.0];
            let x_min = Number.MAX_VALUE;
            let y_min = Number.MAX_VALUE;
            let x_max = Number.MIN_VALUE;
            let y_max = Number.MIN_VALUE;

            for (let i = 0; i < objects_count; i++) {
                const t = triangles[i];
                const t_center = t.get_center();
                median[0] += t_center[0];
                median[1] += t_center[1];
                if (t_center[0] < x_min) { x_min = t_center[0]; }
                if (t_center[0] > x_max) { x_max = t_center[0]; }
                if (t_center[1] < y_min) { y_min = t_center[1]; }
                if (t_center[1] > y_max) { y_max = t_center[1]; }
            }
            median[0] = median[0] / objects_count;
            median[1] = median[1] / objects_count;

            const split_axis = (x_max - x_min) > (y_max - y_min) ? 0 : 1;
            const median_value = median[split_axis];

            let left_objects = [];
            let right_objects = [];
            for (let i = 0; i < objects_count; i++) {
                const t = triangles[i];
                const t_center = t.get_center();
                if (t_center[split_axis] < median_value) {
                    left_objects.push(t);
                } else {
                    right_objects.push(t);
                }
            }
            if (left_objects.length == 0) {
                left_objects.push(right_objects.pop());
            }else if (right_objects.length == 0) {
                right_objects.push(left_objects.pop());
            }

            this.left = new BVHNode(left_objects);
            this.right = new BVHNode(right_objects);

            this.aabb = union_aabbs(this.left.get_aabb(), this.right.get_aabb());
        }
    }

    get_aabb() {
        return this.aabb;
    }

    is_inside_aabb(x, y) {
        return this.aabb[0] < x && this.aabb[1] < y && this.aabb[2] > x && this.aabb[3] > y;
    }

    sample(x, y) {
        if (this.is_inside_aabb(x, y)) {
            if (this.object != null) {
                if (this.object.is_point_inside(x, y)) {
                    return this.object;
                } else {
                    return null;
                }
            } else {
                const left_sample = this.left.sample(x, y);
                const right_sample = this.right.sample(x, y);
                if (left_sample == null) {
                    return right_sample;
                } else {
                    if (right_sample == null) {
                        return left_sample;
                    }

                    const left_center = left_sample.get_center();
                    const right_center = right_sample.get_center();

                    const left_dist = (x - left_center[0]) * (x - left_center[0]) + 
                                      (y - left_center[1]) * (y - left_center[1]);
                    const right_dist = (x - right_center[0]) * (x - right_center[0]) + 
                                       (y - right_center[1]) * (y - right_center[1]);
                    
                    if (left_dist < right_dist) {
                        return left_sample;
                    } else {
                        return right_sample;
                    }
                }
            }
        } else {
            return null;
        }
    }
}

Вызываем построение BVH на старте приложения

ProbesController.prototype.initialize = function() {
    const probes_data = this.probes_data.resource;
    this.probes = probes_data.probes;
    const triangulation = probes_data.triangulation;
    const probes_positions = [];
    for (let index = 0; index < this.probes.length; index++) {
        const probe = this.probes[index];
        const coords = probe.coordinates
        probes_positions.push([coords[0], coords[2]]);
    }
    const triangles = [];
    const triangles_count = triangulation.length / 3;
    for (let i = 0; i < triangles_count; i++) {
        triangles.push(new Triangle(i,
                                    triangulation[3*i],
                                    triangulation[3*i + 1],
                                    triangulation[3*i + 2],
                                    probes_positions));
    }

    this.bvh = new BVHNode(triangles);
    this.entities = new Map();
};

Далее метод, который будет патчить шэйдер любого динамического объекта

ProbesController.prototype.add_entity = function(entity) {
    const e_render = entity.render;
    const inst_count = e_render.meshInstances.length;
    const materials = [];
    for (let i = 0; i < inst_count; i++) {
        const inst = e_render.meshInstances[i];
        const m = inst.material.clone();
        m.chunks.APIVersion = pc.CHUNKAPI_1_62;
        m.chunks.emissivePS = this.emissive_chunk.resource;
        m.chunks.startVS = this.startvs_chunk.resource;
        m.chunks.endVS = this.endvs_chunk.resource;

        m.update();
        materials.push(m);

        e_render.meshInstances[i].material = m;
    }

    const e_pos = entity.getPosition();
    const e_triangle = this.bvh.sample(e_pos.x, e_pos.z);
    
    this.entities.set(entity, {position: [e_pos.x, e_pos.y, e_pos.z],
                               triangle: e_triangle,
                               materials: materials});
    if (e_triangle != null) {
        const bc = e_triangle.get_baricentric(e_pos.x, e_pos.z);
        for (let i = 0; i < materials.length; i++) {
            const m = materials[i];
            m.setParameter("sh0_coefficients[0]", this.probes[e_triangle.get_i0()].sh);
            m.setParameter("sh1_coefficients[0]", this.probes[e_triangle.get_i1()].sh);
            m.setParameter("sh2_coefficients[0]", this.probes[e_triangle.get_i2()].sh);
            m.setParameter("baricenteric_coordinates", bc);
        }
    }
}

И последнее - метод update

ProbesController.prototype.update = function(dt) {
    for (const [entity, e_data] of this.entities) {
        const e_pos = entity.getPosition();
        const prev_pos = e_data.position;
        const delta = (e_pos.x - prev_pos[0]) * (e_pos.x - prev_pos[0]) + 
                      (e_pos.y - prev_pos[1]) * (e_pos.y - prev_pos[1]) + 
                      (e_pos.z - prev_pos[2]) * (e_pos.z - prev_pos[2]);
        if (delta > 0.001) {
            e_data.position[0] = e_pos.x;
            e_data.position[1] = e_pos.y;
            e_data.position[2] = e_pos.z;

            const e_triangle = this.bvh.sample(e_pos.x, e_pos.z);
            e_data.triangle = e_triangle;

            if (e_triangle != null) {
                const bc = e_triangle.get_baricentric(e_pos.x, e_pos.z);
                const materials = e_data.materials;
                for (let i = 0; i < materials.length; i++) {
                    const m = materials[i];
                    m.setParameter("sh0_coefficients[0]", this.probes[e_triangle.get_i0()].sh);
                    m.setParameter("sh1_coefficients[0]", this.probes[e_triangle.get_i1()].sh);
                    m.setParameter("sh2_coefficients[0]", this.probes[e_triangle.get_i2()].sh);
                    m.setParameter("baricenteric_coordinates", bc);
                }
            }
        }
    }
};

Теперь, если мы хотим, чтобы динамический объект освещался lightprob-ами, то при его создании его надо передать в метод add_entity нашего контроллера. И всё.

Ну, какава красота...

Ссылки

• https://playcanvas.com - сайт движка, https://github.com/playcanvas/engine - его гитхаб

• https://playcanvas.com/project/1169594/overview/small-dungeon - ещё раз демонстрационный проект

• https://github.com/recastnavigation/recastnavigation - каноничная реализация функции запекания navmesh-ей

• https://github.com/Tugcga/Path-Finder - ещё раз моя реализация navmesh-ей на Python и AssemblyScript

• https://github.com/donmccurdy/three-pathfinding - отсюда взят подход к поиску путей на navmesh-ах

• https://github.com/google/spherical-harmonics - гитхаб с исходниками для вычисления сферических гармоник, там же есть небольшой список литературы