Учусь программировать. Marching Cubes
ч.5 Учусь программировать. Первый 2Д редактор карты.
Уточнение: я специально не использую сложную терминологию, а описываю все простым челочеческим языком :). Почему я не привожу код ?
Как уже писал ранее в постах, народ очень скуп на такие вещи и ограничивается небольшими пинками, поэтому до всего приходится доходить самому. Оно даже лучше, мозги тренируются и начинают работать в нужном направлении все лучше. Я считаю этот подход наиболее правильным, тем более что исходного кода в интернете масса, но вот понять его, незная направления, бывает довольно тяжело. Здесь же я описываю именно направление и стены об которые я долбился.
В ч.3 Я уже описывал как пытался постичь алгоритм Марширующих кубов, но не хватило терпения и знаний. Алгоритм интересен тем, что позволяет на регулярной сетке строить сложные 3Д объекты, а если его довести до ума, то можно строить 3Д модели практически любых размеров. Для меня это второй шаг на пути создания полностью изменяемого мира.
Все сложное начинается с чего то более простого, поэтому для начала я решил попробовать изучить упрощенный вид алгоритма Marching Squares - это 2-х мерный вариант марширующих кубов. Снова погрузившись в изучение статей, я с удивлением обнаружил, что 2Д вариант у меня есть практически в готовом виде - это был тот самый тайлинг земли из 2Д редактора (из предыдущей темы). Те же 16 разных видов кусочков карты из которых автоматически подбирается нужный пазл, лишь с небольшими изменениями. Сказать что я был рад - не то слово. Как оказалось позже я все же немного ошибся, но об этом дальше.
Итак, проглядев свой код, а также почитав описания теперь уже для 3Д варианта я решил перенести свой 2Д тайлинг земли на 3-х мерную сетку. Я также отписывался на форуме и мне подсказали примерно следующее >>"Я разобравшись с тайлингом 2Д, перенес его с 3Д и только потом узнал, что это уже сделано 20 лет назад и называется marching cube..."
Дело казалось нехитрым, тем более, что я уже игрался с кубическими чанками и как построить сложные объекты из более мелких не было трудностью.
Зацепившись за какую то идею, я становлюсь слеп к остальным подсказкам и мне требуется какое то время чтобы по новому взглянуть на вещи. И я зацепился, за слова "Я разобравшись с тайлингом 2Д, перенес его с 3Д...", точнее даже за "перенес его в 3Д" и начал расширять свой 2Д алгоритм. Уточню, что изначальная версия моего автоподбора правильного пазла в 2Д была строк на 200, я прописывал каждый случай отдельно, чтобы не запутаться. Это рабочий, но неправильный и некрасивый подход.
Я примерно представлял сколько же должно получиться кода, если количество разных кусочков увеличилось в 16 раз, поэтому начал искать зависимости, чтобы как можно больше все упростить.
Поскольку 2Д алгоритм подбора правильного пазла у меня работал по принципу сравнения соседних уже стоящих кусочков, а их всего 8 (если взять квадрать и нарисовать вокруг него квадратики таких же размеров), как уже писал зацепившись за "перенес его в 3Д" я стал проводить те же вычисления для 26 соседних кубиков вокруг целевого, не обращая внимания на явные подсказки в текстах.
Я упрощал все насколько это возможно, пересмотрев тучу вариантов кода я не понимал, что за "изолинии" на которые ориентируются авторы. Но все варианты крутились именно вокруг этого термина.
Провозившись пару дней с кодом, у меня так и не получилось добиться идеально-правильной расстановки 3Д пазлов, каждый раз какой то кусочек не подходил, я даже пробовал делать рассчет не только для 26 кубиков вокруг изменяемого (1 ряд вокруг), но даже для 2 и 3 рядов, что сводило на нет скорость вычисления при больших или быстрых изменениях. Но зато я нашел некоторые зависимости и упростил те 200 строк 2Д варианта всего лишь до 8. Тоже неплохо :))).
Я прервался на денек, отдохнул, погулял, посмотрел киношки, вообщем развеялся. А затем немного переосмыслив и почитав доки свежим взглядом, наконец понял, что за "изолинии" описываются. Это и есть по сути та самая форма объекта, которая проходит по сетке и в зависимости от того какое ребро эта линия задевает выбирается и подставляется нужная фигурка из списка. Мой изначальный подход оказался в корне неверным - нужно было считать правильность подбора кусочка не по соседеним уже стоящим кубикам-деталькам, а по вершинам самой сетки по которой и выстраивается пазл. Так же авторы делали дополнительные расчеты исходя из того, какие вершины и ребра находятся внутри линии (внутри формы объекта), а какие снаружи.
Рисунок на примере Marching Squares
Кубическая ячейка предполагаемой сетки состоит из 8 вершин и 12 ребер, на основе которых к любому исходнику этого алгоритма прилагается таблица из 256 пазлов и 256 вариантов задетых ребер.
Поколдовав еще пару часов над кодом, я честно говоря до сих не понимаю, зачем нужна эта дополнительная таблица вариантов задетых ребер. Благополучно избавившись от нее, при этом значительно сократив расчеты, я добился того, что моя реализация алгоритма подстановки правильного пазла (без списка пазлов) получилась всего.... на 11 строчек кода.
Я 4 дня продолбился над тем чтобы получить идеально работающий алгоритм всего 11 строчек длиной :))). Кому интересно тема от 2010 года, которую я фактически присвоил в октябре 2014, когда решил победить алгоритм
Затем, еще пару дней я провозился, чтобы сделать более менее адекватную развертку текстуры, поскольку при обычном наложении текстуры, она искривлялась и растягивалась, и выглядело это по уродски. Если интересно, можно почитать вот эту тему Тема про развертку
и вот собственно результат того, что получилось.
Теперь при удобном случае можно будет браться за более сложный вариант получаения сложных 3Д поверхностей, но перед этим необходимо изучить еще пару алгоритмов, о которых я напишу чуть позже.
ч. 6 Учусь программировать. Алгоритм авторазметки или подсчет отдельных объектов на поле.
Уточнение: я специально не использую сложную терминологию, а описываю все простым челочеческим языком :). Почему я не привожу код ?
Как уже писал ранее в постах, народ очень скуп на такие вещи и ограничивается небольшими пинками, поэтому до всего приходится доходить самому. Оно даже лучше, мозги тренируются и начинают работать в нужном направлении все лучше. Я считаю этот подход наиболее правильным, тем более что исходного кода в интернете масса, но вот понять его, незная направления, бывает довольно тяжело. Здесь же я описываю именно направление и стены об которые я долбился.
В ч.3 Я уже описывал как пытался постичь алгоритм Марширующих кубов, но не хватило терпения и знаний. Алгоритм интересен тем, что позволяет на регулярной сетке строить сложные 3Д объекты, а если его довести до ума, то можно строить 3Д модели практически любых размеров. Для меня это второй шаг на пути создания полностью изменяемого мира.
Все сложное начинается с чего то более простого, поэтому для начала я решил попробовать изучить упрощенный вид алгоритма Marching Squares - это 2-х мерный вариант марширующих кубов. Снова погрузившись в изучение статей, я с удивлением обнаружил, что 2Д вариант у меня есть практически в готовом виде - это был тот самый тайлинг земли из 2Д редактора (из предыдущей темы). Те же 16 разных видов кусочков карты из которых автоматически подбирается нужный пазл, лишь с небольшими изменениями. Сказать что я был рад - не то слово. Как оказалось позже я все же немного ошибся, но об этом дальше.
Итак, проглядев свой код, а также почитав описания теперь уже для 3Д варианта я решил перенести свой 2Д тайлинг земли на 3-х мерную сетку. Я также отписывался на форуме и мне подсказали примерно следующее >>"Я разобравшись с тайлингом 2Д, перенес его с 3Д и только потом узнал, что это уже сделано 20 лет назад и называется marching cube..."
Дело казалось нехитрым, тем более, что я уже игрался с кубическими чанками и как построить сложные объекты из более мелких не было трудностью.
Зацепившись за какую то идею, я становлюсь слеп к остальным подсказкам и мне требуется какое то время чтобы по новому взглянуть на вещи. И я зацепился, за слова "Я разобравшись с тайлингом 2Д, перенес его с 3Д...", точнее даже за "перенес его в 3Д" и начал расширять свой 2Д алгоритм. Уточню, что изначальная версия моего автоподбора правильного пазла в 2Д была строк на 200, я прописывал каждый случай отдельно, чтобы не запутаться. Это рабочий, но неправильный и некрасивый подход.
Я примерно представлял сколько же должно получиться кода, если количество разных кусочков увеличилось в 16 раз, поэтому начал искать зависимости, чтобы как можно больше все упростить.
Поскольку 2Д алгоритм подбора правильного пазла у меня работал по принципу сравнения соседних уже стоящих кусочков, а их всего 8 (если взять квадрать и нарисовать вокруг него квадратики таких же размеров), как уже писал зацепившись за "перенес его в 3Д" я стал проводить те же вычисления для 26 соседних кубиков вокруг целевого, не обращая внимания на явные подсказки в текстах.
Я упрощал все насколько это возможно, пересмотрев тучу вариантов кода я не понимал, что за "изолинии" на которые ориентируются авторы. Но все варианты крутились именно вокруг этого термина.
Провозившись пару дней с кодом, у меня так и не получилось добиться идеально-правильной расстановки 3Д пазлов, каждый раз какой то кусочек не подходил, я даже пробовал делать рассчет не только для 26 кубиков вокруг изменяемого (1 ряд вокруг), но даже для 2 и 3 рядов, что сводило на нет скорость вычисления при больших или быстрых изменениях. Но зато я нашел некоторые зависимости и упростил те 200 строк 2Д варианта всего лишь до 8. Тоже неплохо :))).
Я прервался на денек, отдохнул, погулял, посмотрел киношки, вообщем развеялся. А затем немного переосмыслив и почитав доки свежим взглядом, наконец понял, что за "изолинии" описываются. Это и есть по сути та самая форма объекта, которая проходит по сетке и в зависимости от того какое ребро эта линия задевает выбирается и подставляется нужная фигурка из списка. Мой изначальный подход оказался в корне неверным - нужно было считать правильность подбора кусочка не по соседеним уже стоящим кубикам-деталькам, а по вершинам самой сетки по которой и выстраивается пазл. Так же авторы делали дополнительные расчеты исходя из того, какие вершины и ребра находятся внутри линии (внутри формы объекта), а какие снаружи.
Рисунок на примере Marching Squares
Кубическая ячейка предполагаемой сетки состоит из 8 вершин и 12 ребер, на основе которых к любому исходнику этого алгоритма прилагается таблица из 256 пазлов и 256 вариантов задетых ребер.
Поколдовав еще пару часов над кодом, я честно говоря до сих не понимаю, зачем нужна эта дополнительная таблица вариантов задетых ребер. Благополучно избавившись от нее, при этом значительно сократив расчеты, я добился того, что моя реализация алгоритма подстановки правильного пазла (без списка пазлов) получилась всего.... на 11 строчек кода.
Я 4 дня продолбился над тем чтобы получить идеально работающий алгоритм всего 11 строчек длиной :))). Кому интересно тема от 2010 года, которую я фактически присвоил в октябре 2014, когда решил победить алгоритм
Затем, еще пару дней я провозился, чтобы сделать более менее адекватную развертку текстуры, поскольку при обычном наложении текстуры, она искривлялась и растягивалась, и выглядело это по уродски. Если интересно, можно почитать вот эту тему Тема про развертку
и вот собственно результат того, что получилось.
Click to viewТеперь при удобном случае можно будет браться за более сложный вариант получаения сложных 3Д поверхностей, но перед этим необходимо изучить еще пару алгоритмов, о которых я напишу чуть позже.
ч. 6 Учусь программировать. Алгоритм авторазметки или подсчет отдельных объектов на поле.