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

    Многие в общих чертах представляют, как работает обратная лучевая трассировка: через каждый пиксель окна вывода алгоритм пропускает луч и вычисляет, с какими объектами сцены он пересекается и как в результате данный пиксель должен быть освещён. Алгоритм по сути требует, чтобы у нас была функция, которая для каждой позиции возвращает цвет точки. Разумеется, тот же подход можно применять не только для трёхмерной графики: любое изображение можно растеризовать таким образом, если у нас есть подходящая функция. Рассмотрим для примера, как с помощью такого подхода решить задачу визуализации диаграмм разложения на простые множители, о которой написал 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 быстрее для первой сотни, но дальше моя начинает выигрывать (для честности я тоже не кэшировал значения синусов и косинусов). Использованный мной подход позволяет упростить и ускорить визуализацию многих нетривиальных вещей. Особенно он полезен при рендеринге фракталов. Заметьте также, что при моём подходе очень легко добавить неограниченный зум в любой области рисунка.
    Поделиться публикацией
    Похожие публикации
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама
    Комментарии 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
                              Я бы радовался пасхалке в виде моноскромной монохромной девушки.

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