10 октября 2012 в 18:03

Визуализация характеристической функции

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

Моя реализация здесь. На картинке изображено 10! = 3628800, хотя всех деталей, разумеется, не видно.

В данной задаче, как и во многих других, цвет бинаризованный: или чёрный, или белый. Соответственно, нам нужна функция вида function check(x,y), которая возвращает логическое значение, говорящее нам, следует ли закрасить данную точку. Математики бы сказали, что check(x,y) — характеристическая функция множества точек на плоскости (в математике такая функция обычно возвращает 1 или 0). Если эта функция задана, алгоритм рисования на HTML5 Canvas будет достаточно прост:
function trace(canvas) {
  var ctx = canvas.getContext("2d");
  var w = canvas.width;
  var h = canvas.height;
  var img = ctx.createImageData(w, h);
  for(var x=0; x<w; x++)
    for(var y=0; y<h; y++)
      if(check(x,y)) img.data[(y*w+x)*4+3]=255;
  ctx.putImageData(img, 0, 0);
}

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

Пусть мы хотим изобразить, к примеру, круг с центром (50, 50) и радиусом 50. Функция check(x,y) будет выглядеть так:
function check(x,y) {
  return (x-50)*(x-50)+(y-50)*(y-50)<50*50;
}
Сумма квадратов расстояний от центра меньше квадрата радиуса. Получим такую картинку:

Разумеется, для круга проще и дешевле воспользоваться библиотечной функцией. Кроме того, наш круг получился угловатым. Чтобы с этим немного побороться, воспользуемся субпиксельным рендерингом: разделим пиксель на n×n более маленьких, прогоним check для каждого из них и установим прозрачность пропорционально количеству успешных проверок:
function trace(canvas) {
  var ctx = canvas.getContext("2d");
  var w = canvas.width;
  var h = canvas.height;
  var img = ctx.createImageData(w, h);
  var n = 2;
  for(var x=0; x<w; x++)
    for(var y=0; y<h; y++)
    {
      var k=0;
      for(var xx=0; xx<n; xx++)
        for(var yy=0; yy<n; yy++)
          if(check(x+xx/n, y+yy/n)) k++;
      if(k) img.data[(y*w+x)*4+3]=255*k/n/n;
    }
  ctx.putImageData(img, 0, 0);
}

Результат получается такой:

Уже вполне красиво. Кому мало, можно увеличить значение n (разумеется, считать будет медленнее).

Вернёмся к исходной задаче. По сути дела нам нужно написать характеристическую функцию для диаграммы разложения числа на простые множители. Я немного поменяю прототип функции, чтобы передать все нужные параметры задачи и воспользоваться рекурсией. Функция check будет принимать аргументы (factors, n, x, y, r), где x и y координаты точки относительно центра окружности, r — радиус окружности, factors — массив простых множителей, где двойки уже объединены в четвёрки, как это делал helarqjsc, а n — элемент массива, с которого нам нужно начинать рассмотрение. Тогда функция check будет выглядеть примерно так:
— Если расстояние от центра до текущей точки больше радиуса, точка точно не подходит — вернём false;
— Если n указывает на конец массива, значит мы добрались до конца и надо просто рисовать закрашенный кружок — вернём true;
— Иначе вычислим радиус окружности следующего порядка (r1);
— Если расстояние от центра до текущей точки меньше радиуса за вычетом диаметра новой окружности (2*r1), то точка попадает внутрь кольца — вернём false;
— Вычислим сектор, в который попадает точка (серым цветом на картинке);
— Вызовем саму себя с тем же factors, на единицу большим n, новым радиусом r1 и значениями x и y, откорректированными в соответствии с центром новой окружности.

Вот, собственно, и всё. Готовое приложение на JS вы можете видеть здесь (требуется поддержка canvas в браузере, никаких fallback для IE 6-8 нету). Я использовал функции helarqjsc для разложения на простые множители, а рендеринг полностью мой. Картинки у меня немного другие, потому что радиусы окружностей и расположение секторов я вычислял по-другому. Можно заметить, что скорость отрисовки практически не зависит от вводимого числа. Хотя реализация helarqjsc быстрее для первой сотни, но дальше моя начинает выигрывать (для честности я тоже не кэшировал значения синусов и косинусов). Использованный мной подход позволяет упростить и ускорить визуализацию многих нетривиальных вещей. Особенно он полезен при рендеринге фракталов. Заметьте также, что при моём подходе очень легко добавить неограниченный зум в любой области рисунка.
Тагир Валеев @lany
карма
482,2
рейтинг 11,0
Программист
Похожие публикации
Самое читаемое Разработка

Комментарии (19)

  • +2
    То, что вы описали в начала — обратная трассировка лучей. То, что вы описали далее — не трассировка лучей вовсе. Трассировка лучей оперирует лучами, поверхностями и их свойствами, у вас из этого нет ничего. И подход этот был зачат до трассировки лучей…

    Впрочем, как его не называй, а реализация хорошая. Спасибо, было крайне интересно почитать.
    • 0
      Да, ассоциация, может, не самая удачная, но мне пришла в голову именно такая :-)
    • +1
      Возможно, такое название будет удачнее.
    • +1
      Это трассировка. Только она происходит в не совсем привычном пространстве (z-координата дискретна, и траектория состоит из довольно странных точек).

      Думаю, что вместо того, чтобы считать секторы и центр нужной окружности, достаточно было бы вычислить что-то вроде

      z[n+1]=(pow(z[n], factors[n]) — 1) * b, где b — какое-то число, большее 1, а z[0]=x+i*y.

      Если z[N] будет меньше 1 по модулю — закрашиваем. И никаких синусов и косинусов.
      • 0
        Нет, плохо получилось :(
      • 0
        А это уже алгебраические фракталы напоминает. Я понимаю аналогию с обратной трассировкой лучей (z-координата константа, а траектория не непрерывна), но если мы назовем этот подход трассировкой лучей, нам придется обозвать трассировкой и это:
        for (int y = 0; y < height; y++)
          for (int x = 0; x < width; x++)
              drawPixel(x, y, abs(cos(x * y / 10000) * 255)); 
        
  • НЛО прилетело и опубликовало эту надпись здесь
  • 0
    Число 1 не работает :)
    • 0
      и 6 некрасиво смотрится. в оригинале лучше
      • +1
        Дело в том, что у меня двойки всегда отрисовывались вертикально, и чтобы [2,2] не создавало линию, я объединял их в [4]. Результат был таким же, как в оригинале.
        Здесь же двойки рисуются горизонтально, поэтому и выглядит иначе, хотя на мой взгляд это мелочи.
        Спасибо автору. Статья отличная, скорость работы потрясающая :)
        • 0
          Мой код кажется чуть логичнее, так как я никакое число не обрабатываю специально при рендеринге (двойки в четвёрки склеены заранее). У вас же для двоек отдельная ветка в отрисовке. Конечно, несложно и у меня добавить аналогичную ветку.

          Спасибо за отзыв!
    • 0
      С 1 была бага в стыренной мной функции факторизации: она должна возвращать пустой массив, а не [1]. Да, чужой код тоже надо тестировать. Пофиксал.
  • 0
    А вот такой Web мне нравится!
  • 0
    Попробовал 31415926=8263 * 1901 * 2, а фигура — круг.
    Идеальный мир!
    • НЛО прилетело и опубликовало эту надпись здесь
    • –2
      Чем более многогранна личность, тем ближе она к круглому идиоту
  • 0
    Добавьте исключительный случай в нуле?
    • 0
      По идее задача для нуля не определена: она имеет смысл только для натуральных чисел. Если хотите, можно выдавать сообщение, что входные данные некорректны :-)
      • 0
        Я бы радовался пасхалке в виде моноскромной монохромной девушки.

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