Оптимизация 3D моделей на Javascript

Все кто работал с конструктивной сплошной геометрией (CSG), создавал свой воксельный движок или использовал готовые модели, сталкивался с проблемой оптимизации треугольников. Число и расположение треугольников у моделей может быть не оптимальным. Конечно, если дизайнер нарисовал для вас лично модель, его можно попросить её исправить. Но как быть, если модель процедурная, и дизайнер не может исправлять каждую процедурную деталь? Нам придется делать это автоматически.

Для примера, возьмем одну деталь, из процедурного генератора стадий созданного на Javascript:

webgl-procedural-part-solid

webgl-procedural-part-wired

Как мы видим, модель с очень большим числом треугольников, которые не влияют на геометрические параметры модели. Есть уже много готовых решений и библиотек по оптимизации моделей, но ни одна не делает работу так как это нужно нам. Тем более нам нужно выполнить быстро и качественно, без деформации текстурной сетки и конечной модели.

Прежде чем приступить к созданию модуля оптимизации моделей, мною были опробованы десятки готовых библиотек и разные готовые решения, но ни одно не дало даже близко нужного результата. После того как убедился, что готового решения нет, приступил к созданию собственного.

Решение с виду было простым, но мне, это лишь казалось. В результате целый месяц ушел на реализацию.

Так как же оно работает? Разберемся с этапами: объединяем все треугольники по группам в зависимости от текстуры и текстурной сетки. Мы получим группы где у нас содержатся треугольники только с одной текстурой и текстурной сеткой у которой при удалении вершин не изменится общая картина.

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

Преобразовать полигоны в треугольники задача не самая простая, обратный путь сложнее. Преобразовать можно при помощи готовых библиотек, но тут нас ждет одно большое разочарование. Готовые библиотеки такие как earcut, libtess и несколько других, умудряются так криво расположить треугольники, что даже в редакторе сложно исправить дефекты.

После десятка зарисовок на листке бумаге, мною было принято решение использовать Триангуляцию Делоне (созданная еще в 1934 году советским математиком Борисом Николаевичем Делоне), но всё далеко не так просто. Триангуляцию Делоне в чистом виде применить не получится. Хоть количество и расположение треугольников будет всегда оптимальным:

delaunay-triangulation

В теории всё хорошо, а в реальности у нас сразу же возникает проблема, треугольники идут не в тех местах:

triangulation-edgeКрасным обозначено ожидаемое разбиение относительно нашей структуры. Но нас ждал сюрприз в этом месте, треугольники шли пересекая конечную структуру. Для этого пришлось модернизировать метод, задача свелась к перестраиванию треугольников которые пересекают наше ребро. После преобразований получился следующий результат:

triangulation-edge-fixed

Теперь треугольники в нужной последовательности, с оптимальным заполнением полигона. На этом можно было остановиться.

Но это далеко не всё, так как реализация Javascript в браузерах не самая быстрая. А расчеты физики на CPU через Javascript слишком чувствительны к числу треугольников, было применено дополнительное преобразование:

triangulation-mesh-minimize

На изображении показана начальная деталь и она же после преобразований, из полигона мы получили 6 треугольников, отлично расположенных, а после конечного преобразования их уже 4, что и требовалось. Конечно, это изменит модель и в ней будут заметны микро трещины, но так же такое преобразование позволяет дополнительно сократить модель еще на 5-10%.

А вот и конечный результат, после всех преобразований, теперь наша модель выглядит так:

webgl-procedural-mesh-optimized

Оригинальная модель содержала 4148 треугольников, после преобразования в полигоны и с удалением лишних вершин: 1174 треугольника, с применением последней оптимизации мы получили 994 треугольника.

Итог: мы сократили модель с 4148 треугольников до 994.

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

Аппарат «Юнона» вышел на орбиту Юпитера

juno

Космический аппарат «Юнона», задача которого — исследование Юпитера, успешно зашел на орбиту этой планеты, сообщило НАСА.

Аппарат успешно выполнил 35-минутный маневр, во время которого он снизил скорость и оказался под воздействием гравитационных сил Юпитера.

Во время этого маневра командный центр мог обмениваться с аппаратом только простыми сигналами, так как главная антенна зонда в этот момент направлена не на Землю. Во время маневра зонд летел на автопилоте, и вмешательство операторов на Земле фактически не требовалось.

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

juno_probe_gfx2_russian

Редактор моделей для различных форм жизни

При создании большого проекта Dreams Gate, постоянно нужны модели и не только зданий и сооружений, но и различных форм жизни. Это могут быть различные животные, рыбы, гуманоиды, фантастичные пришельцы, динозавры и даже роботы. Но рисовать их в стандартных редакторах Blender / 3D Max / Maya и других очень сложно, долго, а в итоге они будут занимать слишком много места (даже в сжатом виде модель одного человека получилась 43кб при 60 тыс треугольников и 1 текстуре 1024х1024 без анимации). Конечно процедурные модели экономят место, но в этом случае создание игры займет слишком много времени.
Стояла задача найти либо создать простой редактор основанный на создании и редактировании костей с последующей анимацией.
Прежде чем приступить к созданию собственного редактора, были изучены основные современные редакторы в поисках готового решения. И оно было найдено ZSpheres в Zbrush, но как всегда, то что требовалось больше всего было не в том виде, а так же для каждого желающего нарисовать модель, потребовалась бы отдельная копия программы. Было принято решение разработать редактор в удобном для работы виде с возможностью сохранения моделей на сайте и в проект Dreams Gate. Изначально редактор не планировалось делать публичным, но после нескольких тестов, всё же решение было принято открыть доступ всем.

Предстоит проделать очень много работы прежде чем редактор перейдет в состояние готового продукта, но бета тестирование уже началось.

Сайт редактора www.modeler.ml

Примеры моделей:

Простейшая модель гуманоида

Для фанатов игры Half-Life модель Bullsquid

Короткие url (mysql + php)

В интернете, множество сайтов, где используются короткие ссылки. Например youtube, tinyurl и подобные. Ссылка вида: http://www.youtube.com/watch?v=N98cpA5hdI0 куда приятнее чем было бы http://www.youtube.com/watch?v=23450928230945820532. Так же использование коротких ссылок необходимо если мы не хотим чтобы наш сайт легко парсили.
Очень часто начинающие программисты пытаются создать ссылки подобного вида на своих сайтах. Но делают это совсем странным способом, обычно создают строку со случайной последовательностью, проверяют есть ли уже подобная в базе данных, если есть создают новую и опять проверяют. Это очень дорогой подход и в базе данных у нас каша из набора символов. Не спорю, это тоже решение, очень даже верное, но не оптимальное. Обычно приходят к такому решению начитавшись форумов, сайтов с ответами или через поиск в том же гугл.
Оптимальное решение: использовать mysql в привычном виде, создать поле id типа int \ bigint, и использовать auto_increment для данного поля. Многие думают, что вдруг индекс будет огромным и выйдет за пределы, это напрасные опасения. Если логика программы верная, просто не получится дойти до границ int/bigint.

Но как же появятся короткие ссылки?
Использовать base62 с небольшим изменением, например мы хотим ссылку вида XXXXX, для этого достаточно прибавить произвольное значение к вашему id из базы данных.

class BaseConv {
  private static $base = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ';
  public static function Base10($value, $b = 62) {
    if (!preg_match("/^[a-zA-Z0-9]+$/", $value)) return -1;
    $limit = strlen($value);
    $result = strpos(static::$base, $value[0]);
    for($i = 1; $i < $limit; $i++) {
      $result = $b * $result + strpos(static::$base, $value[$i]);
    }
    return $result;
  }
  public static function BaseX($value, $b = 62) {
    $r = $value  % $b;
    $result = static::$base[$r];
    $q = floor($value / $b);
    while ($q) {
      $r = $q % $b;
      $q = floor($q / $b);
      $result = static::$base[$r].$result;
    }
    return $result;
  }
}

function idToUrl($id) {
  return BaseConv::BaseX(100000000000 + $id);
}

function idFromUrl($id) {
  return BaseConv::Base10($id)-100000000000;
}

Этот простой код поможет в ваших начинаниях. А если хочется чтобы каждая ссылка была из уникального набора символов, достаточно перемешать биты по маске и изменить порядок в базовом наборе символов.
Дальше простор для вашей фантазии.

Полезные инструменты для повседневной работы

Работая над проектами и заказами скапливается гора информации, куча пометок, набросков. И всё это теряется на и так переполненном рабочем столе. Не так давно мне один знакомый (из весьма знаменитой компании) посоветовал опробовать сервис Trello. Изначально я отнеся скептически, ведь уже был опыт работы с разными системами в том числе и багтрекерными. Но он настоял, чтобы я попробовал. В итоге делюсь с вами положительными впечатлениями от двух недель работы с системой.

Сама система это просто стикеры, которые можно лепить на доску, их можно двигать, менять, кидать в корзину, объединять в группы. Так же можно ставить на них метки, добавлять списки и вычеркивать из них завершенные задачи. В общем это оказался уникальный и удобный инструмент. Который поможет в любых задачах где требуется строгий график и последовательность работы. Так же он позволяет работать командам над своими творческими творениями. График развития моих проектов теперь стал аккуратным и стало видно как и куда развивается каждый проект.

Рекомендую: Сайт trello.com

Полет над планетой

webgl-planet-big

Проснувшись утром и выглянув в окно, приходят мысли: какой волшебный вид из моего окна. Реальность, в компьютерном мире, далека от совершенства, но прогресс не стоит на месте. Каждый день, мы становимся наблюдателями, как рождаются десятки новых технологий, появляются тысячи строк кода. Это приближает нас к созданию полноценного виртуального мира.
Но сегодня, хочется поделиться с Вами, полетом над планетой. Работа над созданием качественных планет велась не один год и новая версия планет требовала определенного подхода к созданию. Были испробованы различные методы. От создание сферы из треугольников, до трассировки лучей. Но только с появлением современных видеокарт, стало доступно создание качественных планет при помощи трассировки лучами.

Так как, у нас браузерная игра и ограниченные возможности, было потрачено не мало времени и сил для получения качественного вида поверхности планет. При этом все создается без использования текстур и без использования треугольников (только два треугольника для трассировки и отображения). Поверхность планеты + атмосфера + облака, всё создается на лету, каждый кадр. Для создания облаков использовались формулы движения жидкостей.
При этом fps 60 и более на современной видеокарте.

Список современных видеокарт: Videocard Benchmark, если ваша карта от 5000 баллов и выше, то всё будет летать.

На пути к звездам!

webgl-proceduralplanet-2

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

Продолжая серию рассказов о создании, хочется рассказать про планеты. А точнее, про изменения метода вывода, теперь, трассировкой лучей будут выводиться планеты и их поверхность на экран. Это самый медленный способ вывода графики на экран и видеокарты с трудом справляются, но перед открывающимися преимуществами, готов рискнуть и пойти на это. JavaScript по своей природе медленный, делать на нем генерацию кусков планеты оказалось очень накладно (даже через 1-2 кадра на сектор). Проведя несколько тестов, сравнив скорость работы с привычным выводом на экран, было принято решение по модернизации движка.

И вот результат:

1 2 3 6