Билинейная фильтрация на JavaScript
141 #javascript,#интерактив,#линейная интерполяция,#математика

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

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

(далее…)

Почему Thread.sleep() — это прошлый век
727 #многопоточность

Допустим, есть задача: создать поток, который скачивает что-то из интернета, а из основного потока ему валятся задания. Стандартный путь реализации такой:

class DownloadThread extends Thread {
    public interface Listener {
        void onImageLoaded(Image image);
    }
 
    private String reqUrl_ = null;
    private final Listener listener_;
    private boolean isFinished_ = false;
 
    DownloadThread(Listener listener) {
        listener_ = listener;
    }
 
    public void imageRequest(String url) {
        synchronized (this) {
            // Запрос на загрузку изображения
            reqUrl_ = url;
        }
    }
 
    @Override
    public void run() {
        while (!isFinished_)
            String url = null;
 
            synchronized (this) {
                // Проверка: есть ли запрос?
                if (null != reqUrl_) {
                    url = reqUrl_;
                    reqUrl_ = null;
                }
            }
 
            if (null != url) {
                // Запрос есть, загружаем изображение
                Image image = download(url);
                listener_.onImageLoaded(image);
            }
 
            try {
                // Поспим одну милисекунду, чтоб не грузить CPU
                sleep(1);
            }
            catch (InterruptedException e) {
                isFinished_ = true;
                break;
            }
        }
    }
 
    public void stopThread() {
        isFinished_ = true;
    }
}

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

Рассмотрим пример номер два:

class DownloadThread extends Thread {
    public interface Listener {
        void onImageLoaded(Image image);
    }
 
    private String reqUrl_ = null;
    private final Listener listener_;
    private boolean isFinished_ = false;
 
    DownloadThread(Listener listener) {
        listener_ = listener;
    }
 
    public void imageRequest(String url) {
        synchronized (this) {
            // Запрос на загрузку изображения
            reqUrl_ = url;
            // Уведомляем поток, что есть задание
            notify();
        }
    }
 
    @Override
    public void run() {
        while (!isFinished_)
            String url = null;
 
            synchronized (this) {
                if (isFinished_) {
                    break;
                }
                // Проверка: есть ли запрос?
                if (null != reqUrl_) {
                    url = reqUrl_;
                    reqUrl_ = null;
                }
                else {
                    try {
                        // Ждем вызова notify
                        wait();
                    }
                    catch (InterruptedException e) {
                        isFinished_ = true;
                        break;
                    }
                }
            }
 
            if (null != url) {
                // Запрос есть, загружаем изображение
                Image image = download(url);
                listener_.onImageLoaded(image);
            }
        }
    }
 
 
    public void stopThread() {
        synchronized (this) {
            isFinished_ = true;
            notify();
        }
    }
 
}

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

Обратите внимание, что метод stopThread() слегка изменился. Ввиду того, что поток не выйдет из состояния wait() без вызова notify().

UPD: По совету друзей исправил метод run() для корректного завершения потока.

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

P.S. Кстати, в C/C++ для тех же целей можно использовать pthread_cond_wait() и pthread_cond_signal()

Извлекаем вектор и угол из матрицы поворота
1K #python,#вектор,#математика,#матрица

В продолжение темы кватерниона…

Итак, есть матрица 4×4, где три оси ортогональны друг другу (по-нашенски, по-деревенски — это означает, что три оси перпендикулярны каждая с каждой, представьте оси прямоугольной системы координат, так вот это оно и есть).

Выглядит матрица вот так:

M=\begin{bmatrix}A&E&I&M\\B&F&J&N\\C&G&K&O\\D&H&L&P\end{bmatrix}

В ней, как я уже рассказывал, «живут» три вектора ABC (ось X), EFG (ось Y), IJK (ось Z). Также есть три смещения вдоль XYZ — это M, N и O соответственно.

Для того, чтобы извлечь вектор и угол из этой матрицы я использую вот такую конструкцию (псевдокод):

def getAngleAxis(m):
    xx = m[A]
    yy = m[F]
    zz = m[K]
 
    # Сумма элементов главной диагонали
    traceR = xx + yy + zz
 
    # Угол поворота
    theta = acos((traceR - 1) * 0.5)
 
    # Упростим вычисление каждого элемента вектора
    omegaPreCalc = 1.0 / (2 * sin(theta))
 
    # Вычисляем вектор
    w.x = omegaPreCalc * (m[J] - m[G])
    w.y = omegaPreCalc * (m[C] - m[I])
    w.z = omegaPreCalc * (m[E] - m[B])
 
    # Получаем угол поворота и ось, 
    # относительно которой был поворот
    return (theta, w)

Мне довелось применять этот метод на матрице, где вектора ABC, EFG и IJK нормализованы. Масштаб хранится отдельно. Если вы храните масштаб внутри матрицы, то перед применением формулы надо нормализовать вектора ABC, EFG и IJK).

Убираем резкие перепады входных данных
18 #python,#линейная интерполяция,#математика

И снова в эфире наша рубрика: «Банальности программирования в массы»…

В этот раз хочу поделиться с народом штукой под названием «Low-pass filter».

«Ну что ты, в самом деле, опять про то, что все уже давным-давно знают» — скажут опытные программисты. «А вот ничего подобного» — отвечу им, лично я узнал об этом совсем недавно. И очень жалею, что не знал этого раньше.

Итак, вот функция для сглаживания входных данных:

def filter(a, b, dt, RC):
    t = dt / (RC + dt)
    return a + t * (b - a)

где a — текущее значение переменной, b — следующее значение, dt — время в миллисекундах между кадрами, RC — некий коэффициент (чем больше значение, тем больше сглаживание).

Соответственно, если вам надо сгладить какое-то значение (например, позицию камеры по Y в зависимости от позиции Y главного героя), то можно применить эту функцию следующим образом (значение RC подбирается опытным путем):

def update(dt):
    camPosY = filter(camPosY, heroPosY, dt, 0.85)

Кстати, тут используется линейная интерполяция, которая вкратце описана в этой заметке: «Линейная интерполяция и кривая Безье».

Расстояние между точками, маленькая хитрость
48 #математика

Расстояние между точками считается довольно просто. Допустим, у нас есть две точки (x1, y1, z1) и (x2, y2, z2), тогда расстояние L между ними считается так:

    \begin{equation*} L=\sqrt{(x_1-x_2)^2 + (y_1-y_2)^2 + (z_1-z_2)^2} \end{equation*}

Если вам нужно определить меньше это расстояние или больше какого-то константного значения C, то вам нет нужны извлекать корень (довольно «дорогая» для процессора операция). Просто сравниваете значение L^2 со значением C^2.

Формула расстояния в таком случае примет вид:

    \begin{equation*} L^2=(x_1-x_2)^2 + (y_1-y_2)^2 + (z_1-z_2)^2 \end{equation*}

Если у вас двумерное пространство — отбросьте координату z.

Блог Евгения Жирнова