habrahabr

Космология и квантовые флуктуации в браузере

  • суббота, 21 сентября 2019 г. в 00:27:36
https://habr.com/ru/post/467959/
  • JavaScript
  • Графические оболочки
  • Математика
  • Физика


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


Результат

Постановка задачи


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



Конечный автомат


Поведение подобных систем удобно описывать переходами между их состояниями, — т.е. конечным автоматом $\delta: S \rightarrow S$, где $\delta$ — функция перехода между состояниями, отображающая множество состояний в себя.


В нашем случае диаграмма состояний выглядит так:





При реализации функцию перехода удобно сделать событийно-зависимой. Это станет видно в дальнейшем. Точно так же удобно иметь возможность подписываться на изменение состояния автомата.


type State = string | number;

type Transition<States = State> = {
  to: States,
  where: (event: Event) => Array<boolean>,
};

type Scheme<States = State> = {
  [key: States]: Array<Transition<States>>
};

interface FSM<States = State> {
  constructor(state: States, scheme: Scheme<States>): void;
  // Returns true if the scheme had a transition, false otherwise
  get isActive(): boolean;
  // Dispatch event and try to do transition
  dispatch(event: Event): void;
  // subscribe on state change
  on(state: States, cb: (event: Event) => any): FSM<States>;
  // remove subscriber
  removeListener(state: States, cb: (event: Event) => any): void;
};

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


Геометрии


Если вопрос с перемещением холста настолько очевиден, что не будем на нем останавливаться, то растяжение стоит рассмотреть подробнее. Прежде всего, потребуем, чтобы растяжение оставляло неподвижным одну единственную точку — курсор мыши. Также должно выполняться условие обратимости, т.е. обратная последовательность пользовательских действий должна приводить холст в исходное положение. Какая геометрия для этого подходит? Мы будем рассматривать некоторую группу точечных преобразований плоскости в себя $\mathbb{R}^2\rightarrow\mathbb{R}^2$, которая в общем случае выражается введением новых переменных $x', y'$, заданных как функции старых:


$x' = \varphi(x, y)\\y' = \psi(x, y)$


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


Современное понимание геометрии отличается от понимания древних. Согласно Ф. Клейну, — геометрия изучает инварианты относительно некоторых групп преобразований. Так, в группе движений $D$ инвариантом является расстояние между двумя точками $d((x_{1},y_{1}),((x_{2},y_{2}))=\sqrt{(x_{1} - x_{2})^2+(y_{1} - y_{2})^2}$. В нее входят параллельные переносы $T_{(x,y)}$ на вектор $(x, y)$, вращения $R_{\phi}$ относительно начала координат на угол $\phi$ и отражения $M_{l}$ относительно некоторой прямой $l$. Такие движения называются элементарными. Композиция двух движений принадлежит нашей группе и иногда сводится к элементарным. Так, например, два последовательных зеркальных отражения относительно прямых $l$ и $n$ дадут поворот вокруг некоторого центра на некоторый угол (проверьте сами):

$M_{l} \circ M_{n} = T_{(-a,-b)} \circ R_{\alpha} \circ T_{(a,b)}$


Наверняка вы уже догадались, что такая группа движений $D$ образует евклидову геометрию. Однако, растяжения сохраняют не расстояние между двумя точками, а их отношения. Поэтому группа движений хоть и должна включаться в нашу схему, но лишь на правах подгруппы.


Геометрия, которая нам подходит, основана на группе растяжений $P$, к которой, помимо вышеуказанных движений, добавляется гомотетия $S_{k}$ на коэффициент $k$.


Ну и последнее. В группе обязательно должен присутствовать обратный элемент. А потому существует нейтральный $e$ (или единичный), который ничего не меняет. Например

$S_{k} \circ S_{k}^{-1}=e$


означает сначала растяжение в $k$ раз, а затем в $1/k$.

Теперь мы можем описать растяжение, оставляющие неподвижным точку курсора мыши, на теоретико-групповом языке:


$(x, y) \rightarrow (x,y)( T_{(-clientX, -clientY)} \circ S_{k} \circ T_{(clientX, clientY)})$


Примечание 1

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


$\forall(x,y) \in \mathbb{R}^2 \neq 0 \Rightarrow T_{(-x, -y)} \circ S_{k} \circ T_{(x, y)}) \neq S_{k} \circ T_{(-x, -y)} \circ T_{(x, y)})$



Выразим движения $T_{(x,y)}$ и $S_{k}$ и их композицию как функции вектора в коде


type Scalar = number;
type Vec = [number, number];

type Action<A = Vec | Scalar> = (z: Vec) => (v: A)  => Vec;

// Translate
const T: Action<Vec> = (z: Vec) => (d: Vec): Vec => [
  z[0] + d[0],
  z[1] + d[1]
];
// Scale
const S: Action<Scalar> = (z: Vec) => (k: Scalar): Vec => [
  z[0] * k,
  z[1] * k
];

const compose = (z: Vec) => (...actions: Array<(z: Vec) => Vec>) =>
	actions.reduce((z, g) => g(z), z);

Боль 1

Весьма странно, что в JavaScript отсутствует перегрузка операторов. Казалось бы, при таком повсеместном использовании векторной и растровой графики куда удобнее работать с векторами или комплексными числами в «классической» форме. Понятия действия сменили бы арифметические операции. Так, например, поворот вокруг некоторого вектора $a$ на угол $\phi$ выражался бы тривиальным способом:


$T_{-a} \circ R_{\phi} \circ T_{a} \Leftrightarrow z \rightarrow (z-a) e^{i \phi}+a$


К сожалению, JS не следует развитию замечательной пифагорейской идеи «Мир есть число» в отличии, хотя бы, от Python.



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


Космология холста. Модулярная решётка


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


Поскольку решётка периодическая, удобно взять на вооружение модулярную алгебру. Таким образом, будем действовать группой $P$ ещё и на тор $T^2=S^1\times S^1$. Поскольку экран монитора не непрерывная плоскость, а целочисленная решётка $\mathbb{Z}^2$ (пренебрежём сейчас тем, что она конечна), то действие группы $P$ надо рассматривать на целочисленном торе $\mathbb{Z}_{p}^2$, где $p$ — размер ребра квадрата $p \times p$:





Таким образом, раз и навсегда фиксировав наш тор возле начала координат, будем производить все дальнейшие вычисления на нём. Затем размножим его, используя стандартные методы библиотеки canvas. Вот, как выглядит перемещение на один пиксель:





Очевидно, что стандартная операция взятия модуля x % p нам не подходит, поскольку переводит отрицательные значения аргумента в отрицательные, а на целочисленном торе таковых нет. Напишем свою функцию $x \mod p$:



const mod = (x, p) =>
      x >= 0 ? Math.round(x) % p : p + Math.round(x) % p;

Теперь вернёмся к машине конечных состояний и


определим её
Класс FSM удобно наследовать от EventEmitter, который предоставит нам возможность подписки.
class FSM<States> extends EventEmitter {
      static get TRANSITION() { return '__transition__'; }
      state: States;
      scheme: Scheme<States>;
      constructor(state: States, scheme: Scheme<States>) {
        super();
        this.state = state;
        this.scheme = scheme;
        this.on(FSM.TRANSITION, event => this.emit(this.state, event));
      }
      get isActive(): boolean {
        return typeof(this.scheme[this.state]) === 'object';
      }      
      dispatch(event: Event) {
        if (this.isActive) {
          const transition = this.scheme[this.state].find(({ where }) =>
            where(event).every(domen => domen)
          );
          if (transition) {
            this.state = transition.to;
            this.emit(FSM.TRANSITION, event);
          }
        }
      }
    }


Далее, определим схему переходов, создадим холст и


все проинициализируем.
canvas = document.getElementById('canvas');
    ctx = canvas.getContext('2d');

    // Create a pattern, offscreen
    patternCanvas = document.createElement('canvas');
    patternContext = patternCanvas.getContext('2d');
    
    type States = 
      | 'idle'
      | 'pressed'
      | 'dragging'
      | 'zooming';

    const scheme: Scheme<States> = {
      'idle': [
        { to: 'pressed', where: event => [event.type === 'mousedown'] },
        { to: 'zooming', where: event => [event.type === 'wheel'] },
      ],
      'pressed': [
        { to: 'moving', where: event => [event.type === 'mousemove'] },
        { to: 'idle', where: event => [event.type === 'mouseup'] },
      ],
      'moving': [
        { to: 'moving', where: event => [event.type === 'mousemove'] },
        { to: 'idle', where: event => [event.type === 'mouseup'] },
      ],
      'zooming': [
        { to: 'zooming', where: event => [event.type === 'wheel'] },
        { to: 'pressed', where: event => [event.type === 'mousedown'] },
        { to: 'idle', where: event => [true] },
      ],
    };

    const fsm: FSM<States> = new FSM('idle', scheme);
    const dispatch = fsm.dispatch.bind(fsm);


Затем следует определить функцию отрисовки, задать необходимые начальные значения и подписаться на изменение состояний. Рассмотрим наиболее интересную часть кода:


      fsm.on('zooming', (event: WheelEvent) => {
        // next scale factor
        const nk = g >= 1
          ? round(k + Math.sign(event.wheelDeltaY) * h * g / 1e2, 1e2)
          : round(k + Math.sign(event.wheelDeltaY) * h * g / 1e2, 1e12);
        // gain
        g = 2 ** Math.trunc(Math.log2(nk));
        if (g < min || g > max) return;

        vec = compose(vec)(
          T([-event.clientX, -event.clientY]),
          S(nk / k),
          T([event.clientX, event.clientY])
        );

        size = base * nk;
        patternCanvas.width = Math.round(size / g);
        patternCanvas.height = Math.round(size / g);

        xyMod = [
          mod(vec[0], patternCanvas.width),
          mod(vec[1], patternCanvas.height)
        ];

        k = nk;

        main();
      });

Во-первых, мы производим расширение не на коэффициент k, а на некоторое отношение nk / k. Это связано с тем, что m-шаг нашего отображения при фиксированной точке $(a,b)$ выражается как


$x_{m} = (x_{m-1}-a)k_{m-1}^*+a \\ y_{m} = (y_{m-1}-b)k_{m-1}^*+b $


или, относительно начальных значений $x_{1}, y_{1}$


$x_{m}=(x_{1}-a)\prod_{i=1}^{m-1} k_{i}^* + a \\ y_{m}=(y_{1}-b)\prod_{i=1}^{m-1} k_{i}^* + b$


Очевидно, что произведение $\prod_{i=1}^{m-1} k_{i}^*$ есть нелинейная функция от шага итерации и либо очень быстро сходится к нулю, либо убегает на бесконечность при небольших начальных отклонениях.


Введём переменную g, которая есть мера удвоения нашего полотна. Очевидно, она принимает постоянное значение на некотором отрезке. Для достижения линейности $k_{i}^*$ воспользуемся однородной подстановкой


$k_{i+1}^*=\frac{k_{i+1}}{k_{i}}, k_{1}=1$


Тогда все члены в произведении, кроме первого и последнего, сократятся:


$\prod_{i=1}^{m-1} k_{i}^*=\prod_{i=1}^{m-1} \frac{k_{i}}{k_{i-1}}=\frac{k_{2}}{1} \frac{k_{3}}{k_{2}}... \frac{k_{m-2}}{k_{m-3}} \frac{k_{m-1}}{k_{m-2}}=k_{m-1}$


Далее, фазовый скачок g уменьшает скорость расширения таким образом, что вновь разворачивающаяся перед нами фрактальная структура всегда движется линейно. Таким образом, мы получаем аппроксимированную вариацию степенного закона Хаббла расширения Вселенной.


Осталось разобраться с пределами точности нашей модели.


Квантовые флуктуцации. Поле 2-адических чисел


Осмысление процесса измерения привело к понятию действительного числа. Принцип неопределённости Гейзенберга указывает на его пределы. Современный компьютер работает не действительными числами, а с машинными словами, длина которых определяется разрядностью процессора. Машинные слова образуют поле 2-адических чисел $\mathbb{Q_{2}}$ и обозначаются как $\mathbb{F_{2}^{n}}$, где $n$ — длина слова. Процесс измерения в этом случае заменяется процессом вычисления и связан с неархимедовой метрикой:


$\forall n \in \mathbb{Z}, z \in \mathbb{F_{2}^{n}}: n \cdot z < 2^n$


Таким образом наша модель имеет предел вычислений. Ограничения описаны в стандарте IEEE_754. Начиная с некоторого момента наш базовый размер выйдет за предел точности и операция взятия модуля начнёт порождать погрешности, напоминающие псевдо-случайные последовательности. В этом просто убедиться, удалив строку


if (g < min || g > max) return;

Окончательный предел в нашем случае вычисляется полуэмпирическим методом, поскольку мы работаем с несколькими параметрами.


Заключение


Таким образом, кажущиеся на первый взгляд далёкими, теории соединяются на холсте в браузере. Понятия действия, измерения и вычисления тесно связаны друг с другом. Вопрос их объединения до сих пор не разрешен.


Результат

P.S.
Было ясно, что исходный код получится маленьким, поэтому я вёл разработку в обыкновенном index.html. По ходу написании статьи, я добавил типизацию, которую тестировал в TypeScript playground.