Немного о тетраэдальных сетках. Разбиение границы. Минусы тетраэдальной сетки.

Фактически, этот пост - продолжение этого.
Остановились мы на том, что построили тетраэдальную сетку из кубической. Следующая стадия - построить разбиение границы. Главная проблема в том, что разбиение границы должно быть согласованно с разбиением самой области - то есть, если у нас есть треугольник на границе, то этот треугольник полностью принадлежит одному из тетраэдров. Естественно есть множество способов сделать это. Простейший - берём прямоугольник разбиваем его на 4 треугольника (по 3 вершины разными способами), далее пробегаем по всем тетраэдрам и проверяем каждый тетраэдр на наличие этого треугольника. Проблема очевидна - на больших сетках это будет занимать гигантское количество времени.
Теперь если подумать о более рациональных способах, то можно сделать так: хранить отдельно параллелепипеды, находящиеся у границы сетки. Тогда сначала можно будет сделать разбиение внутренних, а затем внешних вместе с границей - тогда пробегать по тетраэдрам не придётся вообще(ну даже если придётся, то для каждого всего по 6 тетраэдрам, а не по всем, что есть - уже существенный плюс). Ну либо наоборот, порядок не важен.

Приведённые мой алгоритмы удобны в плане построения сеток для тестовых задач, либо для задач где надо сравнить решения на кубической и тетраэдальной сетки, однако построение "чисто" тераэдальной сетки даёт бóльшие возможности. С другой стороны это создаёт проблемы. Одна из главной проблема - это нормали. В вычислении нормалей проблем нет - векторное произведение сторон треугольника даст нам эту нормаль, главная проблема в определении ориентации нормали - её направления. Если с параллелепипедами всё просто - нормали для каждого параллелепипеда одинаковые(например, совпадают с координатными ортами), то для тетраэдров они могут быть направлены как угодно. И, если требуется ориентация нормали(что обычно так и есть), то надо для каждого тетраэдра разворачивать все нормали как надо, например, по направлению из тетраэдра, либо как-то хитро нумеровать сетку чтобы нормали расположились как надо. И то и другое требуют каких-никаких затрат.
Ещё один минус связан с размером тетраэдров в том или ином направлении(а возможно во всех сразу). Заключается в том, что при автоматическом построении сетки могут получаться очень маленькие тетраэдры. В зависимости от целей построения сетки это может не играть роли, а может быть минусом. Для графики, например, при аппроксимации некоторой модели тетраэдрами для отрисовки если маленький тетраэдр получается где-то внутри области, то это может не играть роли вообще. Для вычислительных задач это более важный критерий и может влиять на качество всего решения в целом.

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

Немного о тетраэдальный сетках. Алгоритмы построения.

С начала кратко, о чём будет пост: о построение тетраэдальных сеток (сеток, элементы которых - тетраэдры), получение этих сеток из сеток на треугольных призмах и параллелепипедальных сеток (далее буду называть их кубическими -  это короче и проще выговаривать и читать).
Теперь то, что привело меня к этому: для курсового проекта требовалось строить тетраэдальные сетки, причём большие (в итоге получилось 132651 узлов и 750000 тетраэдров), что руками делать не очень быстро. Есть различные методы построения, но я выбрал достаточно простой (форма области была не важна) - строится кубическая сетка, затем она разбивается на тетраэдры. И столкнулся с некоторыми проблемами - так, как я сначала  разбивал сетку - она получала не комфорной, ну и первом делом я полез в гугл и, что самое печально я не нашёл того, чего искал. Возможно я конечно плохо искал, но всё равно. Поэтому путь это будет хотя бы тут.
Ну чтож, а теперь начнём с краткого обзора алгоритмов построения тетраэдальных сеток(и соответсвено треугольных, если смотреть двухмерное разбиение).
1. Алгоритм исчерпывания
Выходные данные: граничный фронт (множество треугольников - разбиение границы области)
Принцип работы алгоритма достаточно простой и понятный, берём треугольник из фронта, откладываем по нормали к нему точку на определённую длину, если нет пересечений с тетраэдрами то добавляем тетраэдр в разбиение, если есть пытаемся модифицировать его(переносим точку) и добавляем в разбиение. Исходный треугольник удаляем из фронта, полученные(из тетраэдра) добавляем в него. Заканчиваем когда больше не можем строить тетраэдры.
Плюсы  и минусы: явным минусом является необходимость начального фронта - его тоже ещё надо построить, а так же нахождение оптимальной для задачи стратегии выбора шага по нормали и модификации  тетраэдров. Плюсам является то, что не важна геометрия области.

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

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

4. Построение из кубической сетки или сетки на треугольных призмах
Выходные данные: кубическая сетка или сетка на треугольных призмах
Принцип работы алгоритма: всё просто и понятно разбиваем исходные элементы на тетраэдры так, чтобы получилась комфорная сетка.
Плюсы и минусы: требование таких сеток большим минусом не является, особенно для кубической сетки - её строить легко, поэтому здесь метод даже выигрывает. Главным минусом является минус исходных сеток, по сравнению и "чисто тетраэдальными" сетками - тетраэдрами можно хорошо аппроксимировать более геометрически сложные области, чем параллелипипедами или призмами.

Конечно это далеко не все алгоритмы. Плюс есть алгоритмы, позволяющие улучшить качество тетраэдальных сеток, но их я рассматривать не буду. Перейду сразу к тому: как правильно разбить треугольную призму на тетраэдры, а потом как разбить куб.
 Пусть есть вот такая призма(не все невидимые линии правильно показаны, точнее показа правильно только одна из трёх, но не суть).

 Из неё получаются следующие три тетраэдра: (2, 4, 5, 6), (1, 2, 3, 6) и (1, 2, 4, 6).
Теперь перейдём к параллелепипедам: по суть мы разбиваем один параллелепипед на две призмы, а эти призмы на тетраэдры. Главная проблема - это правильная локальная нумерация призм друг по отношению к другу. Возьмём эту призму и добавим к ней ещё два узла, тем самым получим парллелепипед:

На кривости рисунка из-за копипаста обращать внимание не будем. Если взять симметричную нумерацию(7->2, 8->5), как с делал изначально сетка получится не комфорная, что в некоторых(даже думаю в большинстве) случаев будет проблемой. Правильно же локальную нумерацию во второй(левой) призме ввести следующим образом(глоб. -> лок.): 3 -> 1, 1 -> 2, 7 -> 3, 6 -> 4, 4 -> 5, 8 -> 6. И тогда, используя предыдущее разбиение мы получим наши заветные 6 тетраэдров: (2, 4, 5, 6), (1, 2, 3, 6), (1, 2, 4, 6), (1, 6, 4, 8), (3, 1, 7 8) и (3, 1, 6, 8).

Саму сетку мы разбили, однако осталось ещё одна проблема - разбиение границ. Об этом расскажу в следующий раз, а то пост и так получился каким-то длинным.

Аппаратная мощность - не всё для скорости работы программы

Люди, далёкие от программирования и вычислительной техники, часто считают, что скорость работы программы полностью определяется аппаратной мощностью вычислительной системы. Не так давно я пытался доказывать, что некоторые задачи нельзя быстро решить просто по тому, что не придумали хорошего алгоритма решения этих задач (я сейчас про класс NP). Однако мне кажется, что я не был убедителен. В искупление этого записал видео, где сравниваются две разных структуры и соответствующие им алгоритмы разработки. Так что если кому-то придётся объяснять нечто подобное можете сослаться на это видео.
Исходный код используемой в видео программы.
Само видео:

Выбор юнитов для стратегий. Теоретическая часть для реализации.

После прочтения статьи про выбор объектов в OpenGL, мне особенно понравился метод выбора, используя буфер цвета. Идея метода заключается в следующем: каждом объекту, который может быть выбран присваивается уникальный id и уникальный цвет(на самом деле достаточно только цвета), затем все эти объекты помещаются в некоторую структуры данных. При попытки выделить объект, строится двумерная проекция картинки. Строить надо лишь объекты, которые можно выделить и строить их надо без текстур, однотонные с указанным цветом. Затем считывается цвет пикселя под курсором мышки и ищется объект соответствующего цвета. Затем он и становится выделенным объектом.
За идентификатор рационально использовать сам объект, если такое возможно(например, если все объекты, которые могут быть выделены предоставляют собой потомков некоторого класса, то можно использовать механизм позднего связывания).
Явный минус такого алгоритма - он позволяет выделить только одного юнита. Если больше не надо использовать стоит именно его, если же надо выделить более одного, то алгоритм можно расширить. Я могу предложить два способа, как это сделать, они похожи, отличия у них, правда, небольшие.
Нам понадобится ещё одна структура данных, где мы будет хранить выделенных юнитов. Оба способа заключается в обходе выделанного прямоугольника, считывании пикселей, поиске фигур в буфере цвета(первая структура данных) и помещение их в буфер выделения(вторая структура данных). Отличите простое: в первом случае я предлагаю сделать обработку буфера выделения так, чтобы в нём не возникало коллизий(если юнит уже есть, то его не добавлять). Второй способ заключается в том, чтобы если юнит попадет в буфер выделения, то он удаляется из буфера цвета. Главный минус первого способа - каждый раз при добавлении в буфер выделения необходимо проверять все уже выделенные фигуры, главный минус второго способа - каждый раз при выделении необходимо заново строить буфер цвета(или "перекидывать" из буфера выделения обратно).
Следующий вопрос, не менее важный, это - как выбрать эти структуры данных. Начну с конца. Буфер выделения, выбирать лучше исходя из особенностей выделяемых объектов и самого выделения. Если выделить можно некоторое конечное количество фигур, то подойдёт ограниченный линейный список(реализованный с помощью массива, т.к. это позволяет производить прямой и обратный обход памяти, что даёт существенный выигрыш во времени), если можно выделять потенциально бесконечное множество объектов, то тут уже надо "смотреть на месте".
Для буфера цвета строить общую теорию проще, т.к. его вид его элементов и назначение сразу определенно. Буду рассматривать ситуацию, когда идентификатор включен в буфер. Назначение буфера цвета - это хранение всех объектов, которые могут быть выделены, а так же возможность поиска в нём. Из необходимости поиска и будем исходить. В статье, ссылку на которую я дал вышел, в виде буфера цвета используется статический массив и линейный поиск(просматриваются подряд все элементы массива). При небольшом количество объектов это, пожалуй лучшее решение. Причина всё та же - возможность прямого и обратного обхода памяти. Однако когда количество элементов превышает уже, где-то 256 это не очень удобно, т.к. время обхода будет компенсировать выигрыш.

Проблема в построении структуры данных для поиска, в данном случае, заключается в том, что величина, по которой мы ведём поиск - векторная, состоящая из минимум трёх компонент: (r, g, b). Однако, задачу можно очень просто свести к задачи поиска по скалярной величине. Множество значений каждой из переменных ограниченно, и можно построить отображение из множества цветов во множество натуральных чисел следующим образом:

 Пожалуй, это самый просто способ решения. Построив такое отображение, мы можем искать вместо цвета, простое чисто. В силу ограниченности отображения, у него существует обратное, которая находится достаточно легко(одна из учебных задач - разить число на части), числа в разрядах 0-2 будут означать красную составляющию цвета, 3-5 - зелёную и 6-8 - синюю. Теперь, для буфера цвета, в качестве структуры данных можно использовать бинарное дерево поиска. Поиск в такой структуре один из самых быстрых(собственно, для этого она и предназначена) и кодированние/декодированние цвета тоже занимает мало количество времени. Минус использования дерева поиска - это удаление элемента из дерева может привести к перестройке всего дерева, поэтому второй, из предложенных мной, способов реализации выделения большого числа юнитов не подходит.

В общем, это достаточный теоретический минимум, чтобы реализовать выделение юнитов. Особенно это полезно в играх-стратегиях. Однако применение возможно и в других областях, например, взаимодействие пользователя с некоторыми предметами, посредством мышки(например некоторая физическая система и её элементы можно двигать, щёлкая на них мышкой).