Как компьютеры рисуют странные формы: метаболы, marching squares, электрические поля

Пару месяцев назад я наткнулся на очень красивые анимации. В основе этих анимаций лежат несколько простых окружностей, но выделяет их то, насколько органично они сливаются друг с другом. Мне стало любопытно, как это работает, и моё исследование оказалось гораздо интереснее, чем я ожидал. Выяснилось, что соединяющиеся друг с другом круглые объекты называются метаболами (metaballs) и с ними связано множество математических и вычислительных понятий. Если вы в чём-то похожи на меня, то посмотрев на эти анимации, вы бы сразу задались вопросом, как подойти к решению такой задачи. Допустим, нам поручили разобраться с тем, как генерировать метаболы. Как сформулировать эту задачу? Что означает возможность органичного слияния окружностей? Как компьютер рендерит нечто подобное на экране? Всё это очень сложные вопросы.

В этой статье мы совершим путешествие и узнаем, как люди решают эту задачу. Базовый алгоритм, играющий неотъемлемую роль в генерации таких анимаций, называется marching squares. Он используется во многих сферах графики, а также медицинской визуализации. Но каким бы полезным ни был алгоритм, самым важным в нашем путешествии будет то, насколько изящен этот подход при решении подобной задачи. Есть истинная красота в том, что мы берём расплывчатую задачу и преобразуем её в конкретный решаемый вид. Главная цель этой статьи — дать вам ощущение радости при исследовании смены точек зрения, превращающих подобные сложные задачи в решаемые.

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

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

Неудивительно, что эти функции очень похожи. Обе эти функции являются примерами неявных функций. У нас есть некая функция, зависящая от x и y, а результатом этой функции является некое постоянное значение. Это отличается от других функций, в которых есть одна переменная, явно заданная как функция от другой. Очень часто с определением неявной функции просто легче работать, как и в случае с кругами и эллипсами. Вернёмся к метаболам: мы знаем, что если в случае этих конкретных кадров мы сможем получить соответствующие параметры кругов или эллипсов, то получим полное определение фигуры, которую нам нужно отрендерить. Возникает естественный вопрос: возможно, другие кадры тоже имеют некую загадочную неявную функцию, которую можно определить. Хоть мы и не можем этого доказать, интуитивно нам понятно, что для этих фигур должна быть какая-то неявная функция, похожая на функции окружности и эллипса. И может быть, эти неявные функции метаболов имеют свойства, позволяющие нам рендерить их, но в этих допущениях много неопределённости. Настало время снова взглянуть на задачу под другим углом.

Вероятно, многие из вас знают методику решения задач, основной идеей которой является решение более простой версии задачи. Существует ещё одна контринтуитивная техника: иногда разумно усложнить задачу. На данном этапе мы пытаемся разобраться, как рендерить кадры анимации, в которой некоторые кадры являются неявными функциями, определяющими форму круга или эллипса, а другие могут быть неявными функциями, рендерящими объединённые вариации фигур. Есть надежда, что некоторые из идей о том, как мы рендерим круги и эллипсы, помогут нам разобраться, как рендерить другие непонятные кадры. Но всё это отдельные случаи более масштабного вопроса: сможем ли мы найти способ рендеринга любой неявной функции вида . Кажется, что этот вопрос может оказаться намного сложнее, но это именно тот вопрос, на который нам нужно ответить, чтобы продвинуться в решении исходной задачи. Итак, давайте сыграем в игру. Допустим, у нас есть какая-то загадочная функция, получающая точку в 2D-пространстве и возвращающая значение функции в этой точке. Наша задача — найти все точки в пространстве, равные определённому значению в нашем примере. Например, допустим, нам нужно найти все точки, равные 1. Как подойти к решению этой задачи? Легче всего просто сэмплировать точки случайным образом, и если мы окажемся в пределах порогового значения от нашего значения, можно будет сказать, что мы нашли нужную точку. Но проблема здесь в том, что даже при достаточно большом пороговом значений вероятность оказаться близко с нужной точкой крайне низка. То есть это не настоящее решение задачи. Если немного подумать, то можно попробовать упростить ситуацию, сведя всё к двум случаям: каждая сэмплируемая точка или больше, или меньше целевого значения. Мы можем обозначить эти случаи цветами. Точки меньше 1 будут синими, а точки больше 1 будут зелёными. Давайте теперь выполним сэмплирование и посмотрим, что произойдёт.

Сэмплировав 1000 точек, мы почти ничего не увидим:

Но если сэмплировать 10000, то, возможно, станет что-то понятно.

После увеличения количества сэмлируемых точек до 20000 разница между двумя случаями начинает создавать чёткий контур.

Добавим несколько целевых точек, чтобы картина была понятна.

Я буду называть целевые точки контуром нашей неявной функции. Наша главная задача — найти контур при значении 1. У меня есть и более тайные мотивы — я всегда пытался найти способ вставить в свои материалы Бэтмена, и мне наконец-то это удалось.

Некоторым из вас может быть знакома функция Бэтмена, которую я нашёл в одном из постов на StackExchange. Забавно, что она является примером неявной функции (довольно некрасивой, если честно, зато результат её хорош).

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

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

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

Третий случай интересен — допустим, наша функция в одной точек имеет значение меньше 1, а в другой — больше 1. О чём это нам говорит? Значит, что теперь контур, на котором все точки равны 1, находится где-то между этими двумя точками. И на самом деле мы теоретически можем найти по крайней мере одну целевую точку. Мы можем многократно разделять отрезок с любым количеством шагов. Чем больше шагов, тем выше точность. По сути, это двоичный поиск по вещественным числам и основа простейших алгоритмов поиска корней.

Небольшое примечание: мы предполагаем, что точки больше целевого значения находятся внутри контура, а точки меньше целевого значения — снаружи. Этим предположением мы будем пользоваться до конца статьи, но стоит заметить, что это всего лишь условность, и в некоторых источниках всё будет наоборот. Но на самом деле это неважно, потому что главное, чтобы точки были равны целевому значению.

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

Существует пара ключевых случаев. Если все сэмплируемые точки ячейки меньше 1, то мы знаем, что эта конкретная ячейка находится снаружи контура. Когда все точки больше 1, то ячейка должна находиться внутри контура. В обоих этих случаях мы не можем создать аппроксимацию того, где находится контур. Но если хотя бы одна точка больше 1 и одна точка меньше 1, то мы получим некую информацию. Допустим, левая верхняя сэмплируемая точка находится внутри контура, а все остальные — снаружи. Что из этого следует? Что мы теперь точно знаем, что контур должен проходить через эту ячейку и можем проделать описанное выше упражнение. Одна точка находится внутри, а другая снаружи, поэтому при помощи поиска корней можно найти точку на контуре.

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

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

В целом идея заключается в том, что при уменьшении таких сеток линии, используемые для аппроксимации контура внутри ячейки становятся более точными. Мы рассмотрели два случая того, как контур может проходить через ячейку. Теперь давайте рассмотрим все остальные случаи. Всего существует 16 случаев, так как точка квадрата находится или внутри, или снаружи контура. Здесь хорошо будет проверить наше понимание и посмотреть, сможем ли мы нарисовать аппроксимацию контура по ячейке для каждого из этих случаев. Мы уже видели, как это работает для четырёх случаев. Не будем обращать внимания на то, где именно точки находятся на грани, это будет зависеть от неявной функции. Помните, что в зависимости от значений неявной функции в углах ячейки конечные точки контура могут быть в любом месте соответствующей грани. Чтобы упростить отрисовку, предположим, что контур просто проходит через середину соответствующих граней. Теперь давайте разберём оставшиеся случаи. Несмотря на то, что осталось 12 случаев, многие из них симметричны. Давайте их упорядочим. Два случая, когда все точки внутри или снаружи контура, по сути, аналогичны, так как линия контура не проходит через ячейку. Далее у нас есть квадраты, где внутри сетки. Следующая группа — где точки одной грани каждого квадрата находятся внутри контура, а точки другой грани — снаружи. Есть два случая, когда точки внутри контура находятся в противоположных углах. Наконец, есть случаи, когда внутри контура только одна точка.

На практике простейшим способом реализации этой логики является таблица поиска (lookup table), содержащая эти данные. Хочу кратко упомянуть пограничные случаи, которые нужно учитывать в некоторых областях применения.

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

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

Допустим, у меня есть ячейка со следующими сэмплированными из нашей неявной функции значениями. Если левый верхний угол ячейки имеет значение 1,5 а правый верхний угол — значение 0, то вместо выполнения поиска корней между этими точками для нахождения точной координаты (x, y), мы можем просто аппроксимировать её и предположить, что контур пересекает грань на трети пути между этими двумя точками. Мы можем повторить тот же процесс с нижней гранью, где ожидается, что контур пересечёт грань примерно на трёх четвертых пути между двумя точками. Когда у нас есть грань квадрата, одна точка которой находится внутри контура, а другая снаружи, то мы можем воспользоваться парой ключевых идей для приблизительного вычисления точки между ними. Во-первых, мы всегда будем сразу знать или значение x, или значение y. Помните, что наша точка контура между этими двумя сэмплированными точками всегда будет или на вертикальной, или на горизонтальной прямой, поэтому есть только одна неизвестная координата. Далее нам нужно сделать важное предположение: что значения функции будут линейно меняться от одной точки до другой. Это позволяет нам определить другую координату при помощи алгебраических вычислений. Эти вычисления представляют собой распространённую в компьютерной графике методику под названием «линейная интерполяция». В большинстве областей применения она гораздо быстрее чем поиск корней.

Эта аппроксимация достаточно хороша, чтобы сделать её предпочтительным способом расчёта. Давайте вставим найденное нами в алгоритм, который формально называется marching squares. Сделаем задачу более формальной: у нас есть некая неявная функция и нам нужно получить аппроксимированный контур функции, при котором все точки контура были бы равны некому конкретному значению. Подобные виды контуров также называют изолиниями («iso contours»).

Marching squares — это алгоритм, предназначенный для определения изолиний неявных функций. Но как бы сложно это ни звучало, им мы, по сути, задаём разрешение сетки и проходим квадратом по этой сетке. У большинства квадратов все точки будут находиться или внутри, или снаружи контура. В таком случае мы просто переходим к следующему квадрату. Однако интересные нам квадраты будут одними из оставшихся случаев, когда контур проходит через квадрат. Когда мы сталкиваемся с одним из таких случаев, можно найти точки пересечения на гранях при помощи линейной интерполяции и получить локальную аппроксимацию того, как контур проходит через ячейку. Когда разрешение низко, наш контур не будет выглядеть достаточно точным, но при увеличении разрешения контур улучшается. Это и есть фундаментальная идея, лежащая в основе marching squares. В целом это очень изящный алгоритм. Очевидно, что чем выше разрешение сетки, выбранное нами для выполнения marching squares, тем дольше будет генерироваться контур, поэтому всегда приходится идти на компромисс между точностью и скоростью. Но есть и другое свойство marching squares, которое делает этот алгоритм очень привлекательным для графических приложений. В computer science есть понятие, которое всегда мне казалось довольно забавным. Мы называем алгоритм чрезвычайно параллельным (embarrassingly parallel), если его легко можно превратить в независимые параллельные задачи.

Marching squares является примером такого алгоритма. Вот как это работает: проще всего можно понять параллельную версию marching squares, представив, что для вычислений в каждой ячейке сетки определённого разрешения я дал вам отдельный компьютер. Смысл в том, что мы можем обрабатывать каждую ячейку независимо от всех остальных ячеек. На практике нам нужна возможность обеспечить каждому компьютеру простой способ вычисления скалярного значения функции в каждом углу соответствующей ячейки. Это можно реализовать хранением общей для всех компьютеров карты точек скалярных значений функции, предназначенной только для чтения. Тогда после того, как компьютер обработает отдельный случай для каждой ячейки, он сможет записать информацию о геометрии в общую для всех компьютеров область памяти. После того, как все компьютеры закончат нужную операцию, мы можем использовать информацию для рендеринга всего контура. Почти все приложения, требующие определённого уровня производительности алгоритма marching squares, используют параллельную версию. Давайте сделаем шаг назад и посмотрим на картину того, чего мы уже добились. Помните, что мы начали наше путешествие с вопроса о том, как можно рендерить метаболы. Мы считали, что метаболы — это просто определённый вид неявной функции, поэтому пошли по пути попытки решения более сложной задачи — рендеринга контура любой неявной функции. И это привело нас к алгоритму marching squares. Теперь, когда мы решили более сложную задачу, остался вопрос: как применить marching squares к генерации метаболов?

Если бы у нас была неявная функция метаболов, то это было бы достаточно просто. Но какова неявная функция метабола? Здесь я бы мог просто заспойлерить ответ, но существует невероятная связь, о которой я бы хотел рассказать вам. Она показывает, почему неявная функция метаболов задаётся именно так. Это будет очень интересно, я обещаю.

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

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

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

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

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

Прежде чем мы закончим с метаболами, я бы хотел сделать краткое примечание: хотя истинная неявная функция метабола задаётся как функция обратного расстояния, на практике никто не пользуется этой функцией, потому что у неё есть некоторые неудачные свойства, из-за которых работа с ней становится неудобной. Работающие с графикой люди обычно предпочитают использовать полиномиальную аппроксимацию этой функции, которая, по сути, даёт тот же результат. Причины этого объяснять довольно сложно, поэтому я не хотел бы в это вдаваться, но в конце статьи я укажу ссылки на дополнительные источники. Те же принципы применимы и к трёхмерным функциям. Для рендеринга трёхмерной неявной функции можно использовать marching cubes. Если вы разобрались в marching squares, то поймёте, что marching cubes является естественным расширением алгоритма до 3D-пространств. Мы разделяем пространство на 3D-сетку и проходим кубом через это пространство. Ключевое отличие заключается в том. что теперь мы используем точки, сэмплированные в углах куба, и определяем аппроксимации треугольников, локально описывающих пространство. Применив этот принцип ко всему пространству, мы получим группу треугольников, образующих меш, который можно использовать для описания 3D-объекта.

Marching cubes — это очень мощный алгоритм, и если вы хотите посмотреть на примеры его применения, то крайне рекомендую посмотреть это видео Себастьяна Лага, оно просто потрясающее. Теперь вы достаточно хорошо понимаете вычисления и алгоритмы, лежащие в основе анимаций метаболов. Это было очень нестандартное знакомство с marching squares, неявными функциями и метаболами, но я считаю, что это хороший способ изучения концепций. Краткая личная история: когда я учился в колледже, то немного познакомился с marching squares и marching cubes на одном из курсов по графике. Это классическая история — я узнал о теме на лекции, когда нам показывали примеры, демонстрирующие концепцию. Мы выполнили несколько домашних заданий по теме, а позже сдали экзамен, и я, как и большинство людей, практически всё забыл. Вернувшись к своим конспектам курса я осознал, что никогда на самом деле не понимал, насколько красивы и изящны эти идеи. Всё это я говорю для того, чтобы донести, насколько я был потрясён, когда случайно наткнулся на тему метаболов и мои отношения с этой концепцией оказались совершенно другими. Мне настолько интересно было разбираться в том, как это работает, что я даже реализовал систему в рамках моей статьи. И я думаю, что такой способ изучения, когда моя цель заключалась в создании чего-то на основе знаний, оказался намного более значимым, чем выслушивание стандартной лекции. Это очень важный вывод — ключевым фактором в изучении новых идей и понятий, особенно в мире computer science — это эксперименты, которые нужно проводить при малейшей возможности. В computer science есть так много идей, которые можно развить, и самое важное, что вы можете получить от этой статьи — ощущение, что время, которое вы уделяете на самостоятельное исследование этих идей, может быть достаточно полезным.

Справочные источники

http://jamie-wong.com/2014/08/19/metaballs-and-marching-squares/ — источник вдохновения для создания основы моей статьи, отличное введение в метаболы и их рендеринг при помощи marching squares.

geisswerks.com/ryan/BLOBS/blobs.html — отличный ресурс по реализации метаболов и физических основах неявных функций

https://www.researchgate.net/publication/202232897_Marching_Cubes_A_High_Resolution_3D_Surface_Construction_Algorithm — научная статья, в которой впервые была описана техника marching cubes

https://www.youtube.com/watch?v=M3iI2l0ltbE&ab_channel=SebastianLague — видео Себастьяна Лага о marching cubes

https://www.youtube.com/watch?v=SDS5gLSiLg0&t=978s&ab_channel=PapersWeLove — отличная лекция Кейси Муратори о marching cubes

https://courses.lumenlearning.com/physics/chapter/19-4-equipotential-lines/ — физические основы эквипотенциальных линий и электрических полей.

https://github.com/nipunramk/Reducible/tree/master/2021/MarchingSquares — репозиторий с кодом, который использовался для генерации анимаций для статьи.