...

суббота, 5 сентября 2015 г.

[Перевод] Строим real-time веб-приложения с RethinkDB

От переводчика: Совсем недавно узнал про эту довольно интересную базу данных и как раз наткнулся на свежую статью. На Хабре нет почти ни слова о RethinkDB, в связи с чем было решено сделать этот перевод. Добро пожаловать под кат!

image

База данных RethinkDB упрощает разработку веб-приложений, рассчитанных на обновления в режиме реального времени.
RethinkDB — это open source база данных для real-time приложений. Она располагает встроенной системой уведомления об изменениях, которая беспрерывно транслирует обновления для вашего приложения. Вместо постоянного запрашивания новых данных, позвольте базе данных самой отправлять вам последние изменения. Возможность «подписываться» на потоковые обновления может сильно упростить архитектуру вашего приложения и работу с клиентами, поддерживающими постоянный коннект к вашей серверной части.

RethinkDB является безсхемным хранилищем JSON документов, но также поддерживает и некоторые особенности реляционных БД. RethinkDB также поддерживает кластеризацию, что делает её очень удобной в расширении. Вы можете настроить шардинг и копирование через встроенный веб-интерфейс. Последняя версия RethinkDB также включает в себя автоматический «fail-over» для кластеров с тремя и более серверами. (прим. переводчика: подразумевается возможность продолжения работы с БД в случае падения одного из серверов.)

Язык запросов в RethinkDB, который называется ReQL, нативно встраивается в код на том языке, на которым вы пишите своё приложение. Если, например, вы кодите на Python, то при написании запросов к БД будете использовать обычный для Python синтаксис. Каждый запрос составляется из функций, который разработчик собирает в цепочку, чтобы точно описать необходимую операцию.

Несколько слов о ReQL
RethinkDB содержит в себе таблицы, в которых хранятся традиционные JSON документы. Структура самих JSON объектов может иметь глубокую вложенность. Каждый документ в RethinkDB имеет свой основной ключ (primary key) — свойство «id» с уникальным для таблицы-родителя значением. Ссылаясь на primary key в своём запросе вы можете получить конкретный документ.

Написание ReQL запросов в приложении довольно похоже на использование API конструктора SQL запросов. Ниже, на языке JavaScript, представлен простой пример ReQL запроса для определения количества уникальных фамилий в таблице users:

r.table("users").pluck("last_name").distinct().count()


В ReQL запросе каждая функция цепочки работает с данными, полученными из предыдущей функции. Если быть точным, то порядок выполнения данного запроса таков:
  • table запрашивает определнную таблицу в базе данных
  • pluck достаёт определенное свойство (или несколько свойств) из каждой записи
  • disctinct убирает повторяющиеся значения, оставляя только по одному уникальному
  • count подсчитывает и возвращает количество полученных элементов

Традиционные CRUD операции также просты. ReQL включает в себя функцию insert, которую можно использовать для добавления новых JSON документов в таблицу:
r.table("fellowship").insert([
   { name: "Frodo", species: "hobbit" },
   { name: "Sam", species: "hobbit" },
   { name: "Merry", species: "hobbit" },
   { name: "Pippin", species: "hobbit" },
   { name: "Gandalf", species: "istar" },
   { name: "Legolas", species: "elf" },
   { name: "Gimili", species: "dwarf" },
   { name: "Aragorn", species: "human" },
   { name: "Boromir", species: "human" }
])


Функция filter достаёт документы, которые соответствуют определённым параметрам:
r.table("fellowship").filter({species: "hobbit"})


Вы можете добавлять в цепочку такие функции как update или delete, чтобы выполнить определенные операции над документами, возвращенными из filter:
r.table("fellowship").filter({species: "hobbit"}).update({species: "halfling"})


ReQL включает более 100 функций, которые можно комбинировать для достижения необходимого результата. Есть функции для управления потоками, изменения документов, агрегации, записи и т.д. Также существуют функции, «заточенные» под выполнение стандартных операций со строками, числами, метками времени и геопространственными координатами.

Существует даже команда http, которую можно использовать для получения данных из сторонних Web API. В следующем примере показано как можно использовать http для получения постов с Reddit:

r.http("http://ift.tt/1NUKWhz")("data")("children")("data").orderBy(r.desc("score")).limit(5).pluck("score", "title", "url")


После того как посты получены, они сортируются по очкам и затем отображаются определённые свойства лучшей пятёрки постов. Используя ReQL «на полную мощность», разработчики могут выполнять действительно сложные манипуляции с данными.

Как работает ReQL

RethinkDB client libraries (далее «драйвера») отвечают за интеграцию ReQL в тот язык программирования, на котором ведется разработка приложения. Драйвера внедряют функции для всевозможных запросов, поддерживаемых базой данных. ReQL выражения расцениваются как структурированные объекты, которые похожи на абстрактное синтаксическое дерево. Но для того чтобы выполнить запрос, драйвера переводят эти объекты запроса в специальный формат "RethinkDB's JSON wire protocol format", в котором затем передаются в базу данных.

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

В следующем примере показано как выполнить запрос в RethinkDB из-под Node.js с установленным драйвером ReQL для JavaScript. Этот запрос достаёт всех хафлингов (halflings) из таблицы fellowship и отображает их в консоли:

var r = require("rethinkdb");

r.connect().then(function(conn) {
return r.table("fellowship")
         .filter({species: "halfling"}).run(conn)
   .finally(function() { conn.close(); });
})
.then(function(cursor) {
return cursor.toArray();
})
.then(function(output) {
console.log("Query output:", output);
})


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

Метод connect устанавливает соединение, который затем используется функцией run. для выполнения запроса. Сам по себе запрос возвращает курсор, который является чем-то вроде открытого окошка в содержимое базы. Курсоры поддерживают «ленивую выборку» (lazy fetching) и предлагают эффективные способы перебора больших объёмов данных. В примере выше я просто решил конвертировать содержимое курсора в массив, так как размер результата относительно мал.

Несмотря на то, что ReQL запросы пишутся в вашем приложении как обычный код, они выполняются на сервере БД и возвращают полученные результаты. Интеграция настолько бесшовна, что новички часто путаются в каком месте кода граница между их приложением и работой с БД.

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

function paginate(table, index, limit, last) {
   return (!last ? table : table
      .between(last, null, {leftBound: "open", index: index}))
   .orderBy({index: index}).limit(limit)
}


Еще одно примечательное преимущество ReQL в том, что он предлагает также работу и с привычным SQL и хорошо застрахован от обычных атак-инъекций. Вы с легкостью можете включать в свои запросы внешние данные не беспокоясь о необходимости рискованной конкатенации строк.

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

Создание real-time веб-приложений с помощью changefeeds

RethinkDB обладает встроенной системой уведомления об изменениях, которая значительно упрощает разработку приложений, работающих в режиме реального времени. Если вы вставите функцию changes в конец цепочки, то в качестве результата запроса будет запущен беспрерывный поток, отражающий все происходящие изменения. Такие потоки называются changefeeds (далее «ченджфид»).

Привычные нам запросы к БД хорошо подходят к традиционной веб-модели «запрос/ответ». Однако, постоянное опрашивание сервера не практично для real-time приложений, использующих постоянное подключение к серверу или потоковую передачу данных. Ченджфиды предоставляют альтернативу обычному опрашиванию, а именно возможность постоянной подачи обновленных результатов в приложение.

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

r.table("players").orderBy({index: r.desc("score")}).limit(5).changes()


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

Ченджфид отправляет не только новое значение записи, но и предыдущее, позволяя нам сравнивать результаты. Если какая-то из записей удаляется, то её новое значение будет равно null. Также как и для только появившейся, новой записи, старое значение будет равно null. Кстати, вы можете добавлять в цепочку другие операции после changes, если необходимы какие-то манипуляции с поступающими данными.

Когда вы выполняете запрос с командой changes, — будет возвращён курсор, который останется открытым навсегда (помните про окошко, да?). Курсор будет отображать новые изменения как только они становятся доступными. Ниже можно увидеть пример, показывающий как можно получать обновления из ченджфида в Node.js:

r.connect().then(function(conn) {
   return r.table("data").changes().run(conn);
})
.then(function(cursor) {
   cursor.each(function(err, item) {
         console.log(item);
   });
});


Работа курсора ченджфида выполняется в фоновом режиме, а значит ваше приложения не блокируется. В исконно асинхронных окружениях, таких как Node.js, вам вовсе не нужно принимать какие-то дополнительные меры для корректной работы. Если вы работаете с другими языками, то вероятно понадобится установка фреймворков для асинхронного кода, или же ручное внедрение потоков. Официальные RethinkDB драйвера для Python и Ruby поддерживают такие популярные и широко используемые фреймворки как Tornado и EventMachine.

На данный момент, команда changes работает с функциями get, between, filter, map, orderBy, min и max. Поддержка других видов запросов запланирована на будущее.

При создании real-time веб-приложения с помощью RethinkDB, можно использовать WebSockets для трансляции обновлений на front-end. А такие библиотеки как Socket.io удобны в использовании и упростят этот процесс.

Ченджфиды особенно полезны для приложений, рассчитанных на горизонтальное расширение. Когда вы распределяете нагрузку между несколькими экземплярами своего приложения, то обычно прибегаете к помощи дополнительных механизмов, таких как очереди сообщений или in-memory db, чтобы распространить обновления на все сервера. RethinkDB переносит этот функционал на уровень вашего приложения, уплощая его архитектуру и избавляя вас от необходимости использования дополнительной инфраструктуры. Каждый экземпляр приложения подключается непосредственно к БД для получения новых изменений. Как только обновления доступны, каждый сервер транслирует их соответствующим WebSocket клиентам.

В дополнение к real-time приложениям, ченджфиды могут значительно упростить внедрение мобильных push-уведомлений и другого подобного функционала. Ченджфиды представляют событийно-ориентированную модель взаимодействия с базой данных и эта модель во многих случаях оказывается полезной.

Масштабирование и управление кластером RethinkDB

RethinkDB является распределённой базой данных, нацеленной на кластеризацию и простое расширение. Чтобы добавить новый сервер к кластеру, достаточно просто запустить его из командной строки с опцией --join и указанием адреса уже существующего сервера. Если у вас в распоряжении кластер с несколькими серверами, вы можете настраивать шардинг и копирование индивидуально для каждой таблицы. Любые настройки и особенности, работающие на одном экземпляре БД будут работать в точности также и на кластере.

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

RethinkDB позволяет применять ReQL-подход для конфигурации кластера, который идеально подходит для тонкой настройки и автоматизации. ReQL включается в себя простую функцию reconfigure, которую можно привязать к таблице для установки настроек шардинга. Также кластер предоставляет большую часть внутренней информации о своём состоянии и настройках через набор специальных таблиц в RethinkDB. Вы можете делать запросы к системным таблицам, чтобы изменять настройки или получать информацию для мониторинга. Практически весь функционал, предоставляемый через веб-интерфейс, построен на ReQL API.

Вы даже можете использовать ченджфиды в связке с ReQL monitoring API, чтобы получать поток данных о сервере. Например, можно было бы создать свой инструмент для мониторинга, который прикрепляет ченджфид к системной таблице со статистикой и в режиме реального времени передаёт данные для построения графика нагрузки чтения/записи.

RethinkDB 2.1, вышедшая недавно, имеет встроенную поддержку автоматического fail-over'a. Новый функционал улучшает доступность кластеров и уменьшает риск падения сервера БД. Если основной (primary) сервер неисправен, то остальные, вторичные рабочие сервера «выбирают» новый primary, который будет выполнять эту роль до тех пор, пока неисправный сервер заработает или будет удалён из кластера.
Поломки железа, или перебои в работе сети теперь не влияют на доступность данных до тех пор, пока большая часть серверов находится онлайн.

Установка RethinkDB

RethinkDB работает под Linux и MacOS X. Версия для Windows находится в активной разработке и еще не доступна для загрузки. В документации RethinkDB детально описан процесс установки. Мы подготовили APT и Yum репозитории для пользователей Linux, а также установщик для OS X. Вы также можете установить RethinkDB с помощью Docker или скомпилировать исходный код с Github. Чтобы в этом разобраться, вам поможет наша 10-минутная инструкция.

Оригинал: ссылка

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

Как Webnames снимает с делегирования домены

Вчера случилось страшное в виде сообщения от WebNames "Домен opentown.org заблокирован вследствие нарушения правил регистрации и/или использования доменного имени"

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

Через 2 часа удалось получить от WebNames сканкопию письма из Лубянки, составлял которое либо шутник школьник, а не ФСБшник, либо в службу информационной безопасности ФСБ начали набирать школьников.
image

Первое, что бросилось в глаза, это гриф «конфиденциально», это что же получается, WebNames мне передал конфиденциальную информацию полученную от ФСБ? Но на деле всё проще, никакого грифа «конфиденциально» у ФСБ нет, есть разные уровни конфиденциальной информации от нелепого ДСП до «совсекретно», так что «гриф» по ходу дело изобретение школьника.

Второе, что насторожило — это печать, она там есть, но вот понять, печать ли это ФСБ или ООО «чижик-пыжик» не представляется возможным.

Вывод: если Ваш конкурент зарегистрирован на WebNames, можете состряпать такую вот бумажку, отправить горе-регистратору и на месяц забыть о конкуренте.

Но даже допустим это опус от ФСБ. Сама фраза "в действиях администраторов сайтов усматриваются признаки ст. 283 УК РФ" — это нечто. Кто не в курсе, это страшная статья «Разглашение государственной тайны», но судя по всему составлявший бумагу школьник не удосужился нагуглить содержимое этой статьи, иначе бы знал, что чтобы разгласить гостайну, надо сначала иметь доступ к гостайне, которого за редким исключением у вебмастеров нет… Более того, текст который был там опубликован по сети гуляет уже больше года и назвать его тайной язык не поворачивается. Но это лирика.

Повторно задаем вопрос техподдержке Webnames, какие всё таки правила мы нарушили с просьбой указать пункт правил, и в ответ получаем ссылку на правила регистрации доменных имен в зоне .RU и.РФ. Напоминаю, сняли с делегирования домен в зоне OPENTOWN.ORG

Попытки добиться от техподдержки ответа на вопрос, какое отношение правила зоны RU имеют к домены в зоне ORG пока не увенчались успехом, хотя еще есть надежда, что в штате компании есть хоть один юрист чей мозг не изуродован ЕГЭ.

Интереса ради изучаем эти правила, в частности п.5.5 по которому любого обладателя домена, как теперь выясняется не только в зонах RU и РФ, можно без суда и следствия поставить к стенке лишить домена.

5.5. Делегирование домена может быть прекращено регистратором на основании письменного решения
руководителя (заместителя руководителя или приравненного к нему должностного лица) органа,
осуществляющего оперативно-розыскную деятельность.

Формулировка не слишком точная, но по смыслу получается, что полковник должен подписать решение о признании материала противоправным и предъявить регистратору требование о снятии домена с делегирования.

В нашем же случае в письме есть лишь предположение и просьба, чем отличается предположение от решения, а главным образом просьба от требования, думаю объяснять никому не надо. Но по всей видимости для господина Шарикова любая просьба ФСБ это приказ.

Начали копать дальше, нашлось разъяснение по порядку применения п. 5.5 Правил.

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

  1. Краткое указание информации, которая, по мнению лица, вынесшего решение, размещена с нарушением действующего законодательства;
  2. Квалификация согласно УК РФ или КоАП РФ правонарушения, условия для совершения которого создаются действиями администратора доменного имени, по которым проходит проверка или возбуждено дело.
  3. Правовое основание использования полномочий по направлению подобного решения, ограничивающего права администратора (ссылка на норму закона и пункт Правил регистрации доменных имен)
  4. Указание на исчерпание разумных способов связи с администрацией ресурса, хостинг-провайдером, либо их отказ в удалении информации, в случаях, предусмотренных настоящими разъяснениями.
  5. Контактная информация, позволяющая администратору урегулировать претензии непосредственно с органом, вынесшим решение, без привлечения регистратора.

Правовым основанием в письме указаны все те же правила российских доменов, про то, что пытались связаться с администратором или хостером вообще в письме ни слова, и не пытались, ну и конечно же никакой контактной информации как связаться с ЦИБом нет… печаль…

Попытка выйти из «бана»

В письме, предположительно из ФСБ, черным по белому написана просьба "приостановить делегирование доменов до удаления статей", и казалось бы нет особой проблемы, ну случилось, что помножилась глупость ФСБшников на боязливость регистратора, удалили материал и забыли как недоразумение.

Не тут то было, господа!

Отправив в ООО «Регтайм» скан бумаги о том, что данный контент удален, получаем ответ, дескать плевать они в данном случае хотели на просьбу ФСБ, в частности на фразу "до удаления статей", и будут четко следовать букве закона, то есть отправят почтой письмо в ФСБ и вот когда ФСБ им ответит, что можно делегировать домен, тогда они его и вернут, либо если ФСБ забьет отвечать, то вернут через месяц…

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

Судиться с ООО «Регтайм» будем в любом случае, хотя нет надежды на большую компенсацию, поскольку домен на частном лице, а доходы от рекламы как у нормальных людей идут на счет в европейском банке, не говоря уже об очевидной упущенной выгоде и потерях в будущем. Но отсудить пусть даже 12 рублей придется, хотя бы ради того, чтобы сделав перевод решения суда отправить его в ICANN, которому при такой практике давно пора лишить аккредитации таких регистраторов как WebNames, у которых перенести домен сложнее чем получить гражданство США, и которые к тому же творят вот такие вещи…

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

Набор Yii2 Behavior для хранения деревьев в БД и их совместного использования


Привет, Хабр!

В одном своём проекте на Yii2 мне захотелось совместить Adjacency List и Nested Sets. Причём так, чтобы в случае отключения поведения Nested Sets, функционал оставался полностью работоспособен. Затем я понял, что Nested Sets мне не нужен, т. к. в базе всё равно приходилось хранить полный путь, поэтому на замену я решил применить Materialized Path. Имеющийся на GitHub Behavior (matperez/yii2-materialized-path) был недостаточно функционален, поэтому пришлось написать свой, а так как я недавно уже писал свои поведения для Adjacency List и Nested Intervals, я решил, почему бы не сделать набор таких поведений с единым API, и возможностью произвольно подключать их к модели одновременно, используя преимущество каждого.

Список поведений


Adjacency List


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

Самый простой вид связи, чаще всего для его реализации не подключают никаких поведений, а просто прописывают связи с родителем и детьми. Но стоит дополнить Adjacency List полем сортировки для узлов (insertBefore()/insertAfter()), то тут уже без готового поведения становится сложно. Да и получить всех предков/потомков одними связями сложновато уже.
Все эти проблемы решает поведение. Кроме того, у него есть некоторые фишки — он позволяет делать настраиваемое количество join-ов таблицы саму с собой для сокращения и ускорения запросов на получения предков/потомков.
Смотреть на GitHub

Materialized Path


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

Чем же мне не подошёл matperez/yii2-materialized-path, помимо необходимости единого API и отсутствия некоторых методов? В первую очередь тем, что обновление детей при изменении path у него идёт php-рекурсией, что порождает тучу запросов в базу, что очень плохо. В реализованном мною поведении это производится одним запросом, правда пришлось пожертвовать некоторой совместимостью с базами данных — требуется поддержка функций CONCAT() и LENGTH() (в большинстве БД они есть — mysql, pqsql, mssql). Ещё из преимуществ — в моём behavior предусмотрено два режима построения пути — по первичному ключу или по другому полю, причём не обязательно уникальному.
Смотреть на GitHub

Nested Sets


+ быстрые выборки предков, потомков, соседних и пустых узлов
+ моментально получение количества потомков в узле
+ не рекурсивное построение дерева
— очень медленные модификации дерева, особенно в начале больших баз (вставка одного элемента может запросто длиться более 30 секунд в большой базе)

Для Yii2 уже есть отличное расширение от Creocoder, но мне пришлось его переписать для поддержки единого API, о котором чуть ниже. Этот API даёт ряд преимуществ.
Смотреть на GitHub

Nested Intervals


+ быстрые выборки предков, потомков
+ не рекурсивное построение дерева
+ быстрая вставка при условии оптимизации параметров
— медленные перемещения узлов

Этот алгоритм не очень популярен, хотя он очень быстр при условии выбора правильных параметров. Более подробно о nested intervals можно почитать в этой статье.
Смотреть на GitHub

Единое API


Все перечисленные выше поведения имеют общее API, благодаря чему могут быть заменены без переписывания кода.
У API есть одно большое преимущество — двойственный доступ к связанным объектам через стандартный для Yii2 механизм Relations:
$parent = $model->getParent()->orderBy(['title' => SORT_DESC])->one(); // если вызвать связь методом, вернёт ActiveQuery
$title1 = $model->parent->title; // если вызвать свойством, вернёт сам объект
$title2 = $model->parent->title . ' (2)'; // повторный вызов НЕ генерирует второй запрос к базе


Есть и особенность — методы makeRoot(), prependTo(), appendTo(), insertBefore(), insertAfter() — не производят само действие, а лишь дают указание на его тип, поэтому после них надо не забыть выполнить save():
$node = new Node;
$node->title = 'root';
$node->makeRoot()->save();


Это сделано для того, чтобы не протаскивать за собой параметры save($runValidation = true, $attributeNames = null).

Trait для одновременного использования нескольких поведений


Behavior в Yii2 реализованы таким образом, что выполняется метод первого поведения, в котором он существует. Чтобы совместно использовать несколько поведений, надо вызвать модифицирующие дерево методы для каждого подключенного поведения, а для выбирающих из базы методов — наиболее быстрый. Для этого был написан Trait, который выполняет эти функции. Заодно это избавляет от необходимости указывать PhpDoc каждый раз.
Смотреть на GitHub

Пример:

use paulzi\adjacencylist\AdjacencyListBehavior;
use paulzi\nestedsets\NestedSetsBehavior;
use paulzi\autotree\AutoTreeTrait;

class Node extends \yii\db\ActiveRecord
{
    use AutoTreeTrait;
    
    public function behaviors() {
        return [
            ['class' => AdjacencyListBehavior::className()],
            ['class' => NestedSetsBehavior::className()],
        ];
    }
}


Теперь:
$node->parents;     // будет использовать nested sets
$node->parent;      // будет использовать adjacency list
$node->children;    // будет использовать adjacency list
$node->descendants; // будет использовать nested sets
$node->insertAfter($node2)->save() // выполнится для двух поведений сразу


Максимально эффективные сочетания:
Adjacency List + Materialized Path
Adjacency List + Nested Sets
Adjacency List + Nested Intervals

Сравение производительности


Из таблицы думаю видно, в чём преимущества и недостатки каждого из behavior:
Таблица производительности
                                                Запросов    DB время    Выполнение  Память

Тест 1. Заполнение 3 уровня по 12 детей
    Adjacency List                              5811        1,567 ms    9,591 ms    71.3 MB
    Nested Sets                                 7697        6,672 ms    25,019 ms   105.9 MB
    Nested Intervals amount=24                  5813        1,765 ms    10,442 ms   78.7 MB
    Nested Intervals amount=12 noPrepend noIns. 5813        1,750 ms    10,223 ms   78.7 MB
    Materialized Path (identity pr. key mode)   7696        3,169 ms    13,726 ms   92.5 MB
    Materialized Path (attribute mode)          5811        1,690 ms    9,504 ms    71.6 MB

Тест 2. Заполнение 6 уровня по 3 детей
    Adjacency List                              3642        982 ms      5,812 ms    44.5 MB
    Nested Sets                                 4736        5,447 ms    17,859 ms   65.0 MB
    Nested Intervals amount=10                  3644        1,275 ms    5,976 ms    48.9 MB
    Nested Intervals amount=3 noPrepend noIns.  3644        1,271 ms    5,993 ms    48.9 MB
    Materialized Path (identity pr. key mode)   4735        1,316 ms    6,920 ms    57.3 MB
    Materialized Path (attribute mode)          3642        1,129 ms    5,507 ms    44.6 MB

Тест 3. Вставка в начало <4% (20 в 19657 узлов)
    Adjacency List                              100         36 ms       190 ms      4.6 MB
    PaulZi                                      100         15,768 ms   16,712 ms   4.7 MB
    Nested Intervals                            82          21 ms       150 ms      4.7 MB
    Materialized Path (identity pr. key mode)   120         98 ms       355 ms      4.8 MB
    Materialized Path (attribute mode)          100         74 ms       334 ms      4.6 MB

Тест 4. Вставка в середину >46% <50% (20 в 19657 узлов)
    Adjacency List                              100         24 ms       150 ms      4.6 MB
    Nested Sets                                 100         8,212 ms    8,799 ms    4.7 MB
    Nested Intervals                            82          269 ms      593 ms      4.7 MB
    Materialized Path (identity pr. key mode)   120         35 ms       196 ms      4.9 MB
    Materialized Path (attribute mode)          100         287 ms      494 ms      4.6 MB

Тест 5. Вставка в конец >96% (20 в 19657 узлов)
    Adjacency List                              100         31 ms       214 ms      4.5 MB
    Nested Sets                                 100         487 ms      899 ms      4.7 MB
    Nested Intervals                            83          46 ms       187 ms      4.7 MB
    Materialized Path (identity pr. key mode)   120         34 ms       229 ms      4.8 MB
    Materialized Path (attribute mode)          100         470 ms      718 ms      4.6 MB

Тест 6. Удаление из начала <4% (20 из 19657 узлов)
    Adjacency List parentJoin=0 childrenJoin=0  60          169 ms      257 ms      3.8 MB
    Adjacency List parentJoin=3 childrenJoin=3  60          87 ms       162 ms      3.8 MB
    Nested Sets                                 100         16,480 ms   16,902 ms   4.7 MB
    Nested Intervals                            60          164 ms      250 ms      4.2 MB
    Materialized Path (identity pr. key mode)   60          87 ms       201 ms      4.0 MB
    Materialized Path (attribute mode)          60          122 ms      219 ms      4.0 MB

Тест 7. appendTo() в случайный узел (5 уровней, 1000 узлов)
    Adjacency List                              4001        1,062 ms    5,976 ms    46.1 MB
    Nested Sets                                 5003        5,428 ms    17,334 ms   64.8 MB
    Nested Intervals amount=10                  8497        23,301 ms   41,060 ms   120.7 MB
    Nested Intervals x64 amount=10              7092        11,330 ms   23,618 ms   97.5 MB
    Nested Intervals amount=200,25 noPrep noIns 4009        1,431 ms    6,490 ms    50.2 MB
    Nested Intervals x64 a=250,30 noPrep noIns  4003        1,421 ms    6,615 ms    50.0 MB
    Materialized Path (identity pr. key mode)   5003        1,621 ms    8,184 ms    57.8 MB
    Materialized Path (attribute mode)          4002        1,269 ms    6,169 ms    46.2 MB
    
Тест 8. Произвольная операция в случайный узел (5 уровней, 1000 узлов)
    Adjacency List                              4383        1,330 ms    6,147 ms    53.0 MB
    Nested Sets                                 5003        9,577 ms    24,334 ms   64.8 MB
    Nested Intervals amount=10                  7733        8,123 ms    24,031 ms   107.2 MB
    Nested Intervals x64 default amount=10      5663        3,761 ms    14,084 ms   75.6 MB
    Nested Intervals amount=200,25              4175        1,548 ms    7,223 ms    52.8 MB
    Nested Intervals x64 a=250,30 reserve=2     4003        1,541 ms    6,753 ms    50.0 MB
    Materialized Path (identity pr. key mode)   5392        3,211 ms    11,771 ms   65.0 MB
    Materialized Path (attribute mode)          4377        2,902 ms    10,132 ms   53.2 MB
    
Тест 9. Перемещение узлов в начале <4% (20 из 19657 узлов)
    Adjacency List                              112         39 ms       261 ms      4.5 MB
    Nested Sets                                 140         218 ms      566 ms      5.5 MB
    Nested Intervals                            160         180 ms      573 ms      6.0 MB
    Materialized Path (identity pr. key mode)   128         38 ms       307 ms      4.9 MB
    Materialized Path (attribute mode)          128         159 ms      495 ms      4.9 MB

Тест 10. Перемещение узлов из конца в начало <4% >96% (20 из 19657 узлов)
    Nested Sets                                 140         16,991 ms   17,845 ms   5.5 MB
    Nested Intervals                            160         16,972 ms   17,854 ms   6.0 MB
    Materialized Path (identity pr. key mode)   132         49 ms       319 ms      4.9 MB
    Materialized Path (attribute mode)          132         205 ms      502 ms      4.9 MB
    Adjacency List                              112         33 ms       217 ms      4.5 MB
    
Тест 11. Выбор всех узлов (19657 шт.)
    Adjacency List                              1           33 ms       890 ms      179.1 MB
    Nested Sets                                 1           40 ms       1,208 ms    215.2 MB
    Nested Intervals                            1           42 ms       1,247 ms    225.3 MB
    Materialized Path (identity pr. key mode)   1           46 ms       1,240 ms    209.0 MB
    Materialized Path (attribute mode)          1           44 ms       1,106 ms    209.0 MB
    
Тест 12. Выбор детей и потомков (для 819 узлов в середине дерева из 19657 узлов)
    Adjacency List parentJoin=0 childrenJoin=0  2562        720 ms      1,969 ms    36.9 MB
    Adjacency List parentJoin=3 childrenJoin=3  2461        704 ms      1,966 ms    35.3 MB
    Nested Sets                                 1641        522 ms      1,585 ms    25.0 MB
    Nested Intervals                            1641        579 ms      1,657 ms    25.0 MB
    Materialized Path (identity pr. key mode)   1641        569 ms      1,626 ms    23.4 MB
    Materialized Path (attribute mode)          1641        793 ms      6,552 ms    44.7 MB

Тест 13. Выборка родителей (для 819 узлов в середине дерева из 19657 узлов)
    Adjacency List parentJoin=0 childrenJoin=0  3180        948 ms      2,304 ms    51.2 MB
    Adjacency List parentJoin=3 childrenJoin=3  1641        486 ms      1,495 ms    30.8 MB
    Nested Sets                                 821         3,238 ms    3,979 ms    20.7 MB
    Nested Intervals                            821         3,292 ms    4,147 ms    22.0 MB
    Materialized Path (identity pr. key mode)   821         292 ms      902 ms      21.2 MB
    Materialized Path (attribute mode)          821         582 ms      4,574 ms    24.7 MB

Тест 14. Выборка соседних узлов (для 819 узлов в середине дерева из 19657 узлов)
    Adjacency List parentJoin=0 childrenJoin=0  1641        535 ms      1,442 ms    23.7 MB
    Adjacency List parentJoin=3 childrenJoin=3  1641        508 ms      1,421 ms    23.6 MB
    Nested Sets                                 1641        513 ms      1,428 ms    24.5 MB
    Nested Intervals                            1641        19,681 ms   21,326 ms   27.5 MB
    Materialized Path (identity pr. key mode)   1641        730 ms      1,695 ms    24.3 MB
    Materialized Path (attribute mode)          1641        1,892 ms    2,964 ms    24.3 MB

Тест 15. Выборка пустых узлов (для 819 узлов в середине дерева из 19657 узлов)
    Adjacency List parentJoin=0 childrenJoin=0  1833        568 ms      1,743 ms    32.6 MB
    Adjacency List parentJoin=3 childrenJoin=3  1732        556 ms      1,891 ms    31.3 MB
    Nested Sets                                 821         305 ms      908 ms      18.4 MB
    Nested Intervals                            821         10,450 ms   11,166 ms   18.8 MB
    Materialized Path (identity pr. key mode)   821         7,968 ms    8,434 ms    18.5 MB
    Materialized Path (attribute mode)          821         14,349 ms   19,105 ms   21.3 MB

Ссылки на GitHub


Adjacency List
Materialized Path
Nested Sets
Nested Intervals
Auto Tree Trait

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

Дайджест KolibriOS #9: летний урожай

сегодня в 00:05

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

Обозначения
— реализация новой программы, драйвера или библиотеки
— реализация чего-либо в рамках GSoC
— ссылка на загрузку

Общесистемные изменения (ядро, драйверы, библиотеки):


  • новый системный шрифт с возможностью пропорционального масштабирования
  • увеличена скорость и стабильность работы IDE дисков, и SATA в режиме IDE.
  • Возможность работы с любой из установленных сетевых карт (ранее использовалась первая обнаруженная сетевая карта)
  • console.obj: скролл мышью.
  • kmenu.obj: библиотека с реализацией главного и контекстного меню.

Изменения в прикладном ПО:


  • Eolite: изменение атрибутов как отдельного файла/каталога, так и группы выделенных; настраиваемый размер шрифта; прогресс бар в диалоге копирования; работа шоткартов на раскладках отличных от английской; двух панельный режим; запоминание размера и позиции окна; множественные исправления и оптимизации.
  • WebView: использование новых системных шрифтов; улучшенная поддержка некоторых тегов; оптимизация программы и исправление багов.
  • MouseCfg: проверка и настройка параметров мыши.
    Заголовок спойлера
    Программа позволяет проверить работоспособность мыши, настроить скорость и задержку курсора, а также является оболочкой для работы с программами madmouse (позволяет сделать края экрана сквозными, т.е. курсор при достижении одного края, перескакивает на противоположный) и mousemul (также эмулирует мышь при помощи клавиш NumPad), которые не имеют собственного интерфейса.



  • TmpDisk: отображения размера созданных дисков.
  • TextEdit: изменение тулбара и полноценное меню
  • TinyPad: исправление бага при работе с буфером обмена.
  • Calypte: читалка текстовых файлов.
    Заголовок спойлера
    Текущий функционал:
    — открытие текстовых документов в кодировке DOS
    — навигация с помощью клавиш PgDn, PgUp, Down, Up, Home, End
    — адаптация вывода под ширину окна

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



  • Calc: использование увеличенного шрифта для отображения чисел.
  • VNC Client:; поддержка ZRLE/TRLE, 32bpp, клавиатуры; исправление багов и рефакторинг

  • End (С-- версия): новый дизайн.
  • MTDBG: уменьшена перерисовка окна при старте программы.
  • TicTacToe: новая логическая игра, особенностью является то, что она написана на Oberon07
  • Maze: новая логическая игра, особенностью является то, что она написанна на Oberon07
  • ALMAZ: новая аркадная игра, аналог Lode Runner

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

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

Django 1.9 получит новый дизайн админки

image

Всем привет

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

Получилось как-то так:

image

Недолго думая и сдав с чистой совестью проект, я решил показать Django-сообществу свое творение. Pull Request в официальном репозитории Django вызвал бурное обсуждение, к которому присоединились core-девелоперы. В итоге было решено, что внешний вид действительно стоит обновить, но не ассоциировать интерфейс с «брендовым» сайтом Django, а сохранить прежнюю узнаваемую цветовую схему.

На сей раз я решил не спешить и проработать все возможные ситуации. Специально для этого в марте мною был создан апп django-flat-theme, благодаря которому удалось собрать фидбэк пользователей (апп установили даже на djangoproject.com) и улучшить первоначальные задумки.

К августу после продолжительной дискуссии в сообществе django-developers мой Pull Request с новой темой для админки был замерджен в мастер-ветку Django, а еще через некоторое время по многочисленным запросам пользователей старые GIF-иконки были заменены на SVG. Таким образом Django-админка впервые за 10 лет потерпит серьезные изменения.

image

Кстати говоря, переход на SVG-иконки тоже вызвал в коммьюнити большое обсуждение, результатом которого стал отказ от поддержки IE8 начиная с версии Django 1.9, из-за чего также решено было обновить jQuery c 1.11 до 2.1.4.

Новый внешний вид интерфейса админки, вероятно, затронет сторонние приложения. Однако хорошая новость в том, что изменения в плане кода коснулись только CSS-файлов (за исключением пары HTML-шаблонов, где пришлось поменять названия иконок). Если у вас есть свои приложения, советую посмотреть на них локально в новом виде. Сделать это можно двумя способами:

  • установить пакет django-flat-theme в свой проект
    pip install django-flat-theme
  • обновить Django из master-ветки
    pip install git+http://ift.tt/1Oj4B7V --upgrade

Не стесняйтесь сообщать о найденных в новом интерфейсе багах. Сделать это можно либо создав Issue в django-flat-theme, либо непосредственно в баг-трекере Django. Бета-версия Django 1.9 выйдет 19 октября, до этого момента еще останется возможность исправить найденные ошибки. Большое спасибо.

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

пятница, 4 сентября 2015 г.

Дополненная реальность на Qt


Сейчас дополненная реальность – это одно из самых интересных направлений. Поэтому я и взялся за ее изучение, а результатом этого стала собственная реализация кроссплатформенной безмаркерной дополненной реальности на Qt. Речь в этой статье пойдет о том, как это было реализовано (или же как это реализовать самому). Под катом можно найти демку и ссылку на проект на гитхабе.
Для работы дополненной реальности не требуется какие-либо маркеры, подойдет любая картинка. Нужно только выполнить инициализацию: направить камеру на точку на картинке, нажать кнопку старт и двинуть камеру вокруг выбранной точки.
Здесь можно скачать демки под Windows и Android (почему-то не работает на windows 10).

О проекте


Проект разделен на три части:
AR – здесь все что связано с дополненной реальностью. Все спрятано в пространство имен AR, ARSystem – главный объект системы, в котором и осуществляются все расчеты.
QScrollEngine – графический движок для Qt. Находится в пространстве имен — QScrollEngine. Есть отдельный проект на гитхабе.
App – собственно здесь описано приложение, использующее систему дополненной реальности и графический движок.
Все, что описано ниже основывается на проектах PTAM и SVO: Fast Semi-Direct Monocular Visual Odometry.
Входные данные

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

Общий алгоритм работы


Чаще всего для работы дополненной реальности используются какие-то маркеры помогающие определять положение камеры в пространстве. Это ограничивает ее использования, так как, во-первых, маркеры должны быть постоянно в кадре, а во-вторых, их необходимо сначала подготовить (распечатать). Однако есть альтернатива — техника structure from motion, в которой данные о положении камеры находятся только по перемещению точек изображения по кадрам видеопотока.
Работать сразу со всеми точками изображения сложновато (хотя и вполне возможно (DTAM)), но для работы на мобильных платформах нужно упрощать. Поэтому мы просто будем выделять отдельные «особые» точки на изображении и следить за их перемещениями. Находить «особые» точки можно разными способами. Я использовал FAST. Этот алгоритм имеет недостаток – он находит углы только заданного размера (9, 10 пикселей). Чтобы он находил точки разного масштаба, используется пирамида изображений. Вкратце, пирамида изображений – это набор изображений, где первое изображение (основание) – это исходное изображение, а изображения следующего уровня в два раза меньше. Находя особые точки на разных уровнях пирамиды, находим «особые» точи разного масштаба. А сама пирамида используется также в оптическом потоке для получения траекторий движений наших точек. Прочитать про него можно здесь и здесь.

Итак, у нас есть траектории движения точек и теперь по ним надо как-то определить положение камеры в пространстве. Для этого, как можно понять из приложения, вначале выполняется инициализация по двум кадрам, в которых камера направлена примерно на одну и ту же точку, только под разными углами. В этот момент происходит вычисление положения камеры в этих кадрах и положение «особых» точек. Далее, по известным трехмерным координатам точек можно уже вычислить положения камеры в каждом следующем кадре видеопотока. Для более стабильной работы добавляем новые точки в процесс слежения, составляя карту пространства, которое видит камера.

Преобразование в экранные координаты


Для начала разберемся с тем, как трехмерные координаты «особых» точек переходят в экранные. Для этого используем эту формулу (обозначим ее, как формула 1):

world[i] — это «особые» точки в мировых координатах. Чтобы не усложнять себе жизнь, предположим, что эти координаты не меняются на протяжении всего времени. До инициализации эти координаты не известны.
screen[i] — компоненты x и y — это координаты «особой» точки на изображении (их дает нам оптический поток), z — глубина относительно камеры. Все эти координаты уже будут своими на каждом кадре видеопотока.
mProj — матрица проекции размером 3 на 3 и имеет вид , здесь pf — фокальное расстояние камеры в пикселях, pc — оптический центр камеры также в пикселях (обычно примерно центр изображения). Понятно, что эта матрица должна формироваться под параметры камеры (ее угол обзора).
mWorld — матрица, описывающая трансформацию точек, размером 3 на 4 (т. е. из обычная мировая матрица из которой убрали последнюю строчку (0 0 0 1). В этой матрице заключена информация о перемещении и повороте камеры. И это то, что собственно мы в первую очередь ищем на каждом кадре.
В данном случае не учитывается дисторсия, но будем считать, что она почти не влияет, и ею можно пренебречь.

Мы можем упростить формулу, избавившись от матрицы mProj (в формуле 1):

.
Введем , которые считаем заранее. Тогда формула 1 упрощается до (пусть это будет формула 2).

Инициализация


Как уже говорилось, инициализация происходит по двум кадрам. Обозначим их как A и B. Значит у нас появятся матрицы и . Точки c[i] на кадрах A и B обозначим как cA[i] и cB[i]. Так как мы сами вольны выбирать начало координат, предположим, что камера в кадре A как раз там и находится, поэтому — это единичная матрица (только размером 3 на 4). А вот матрицу придется все-таки вычислять. И сделать это возможно при помощи точек, расположенных на одной плоскости. Для них будет справедлива следующая формула:
, где матрица H — это плоская гомография.
Перепишем выражение таким образом (убрав индекс i для наглядности):

А теперь перейдем к такому виду, избавившись от :

Представив матрицу H в виде вектора , можем представить эти уравнений в матричном виде:

.

Обозначим новую матрицу как M. Получим M * H’ = 0. Все это расписывалось только для одной точки, поэтому в матрице M только 2 строки. Для того, чтобы найти матрицу H', необходимо, чтобы в матрице M было количество строк больше либо равно количеству столбцов. Если имеем только четыре точки, то можно просто добавить еще одну строку из нулей, выйдет матрица размером 9 на 9. Далее при помощи сингулярного разложения находим вектор H’ (само собой он не должен быть нулевым). Вектор H’ – это, как мы помним, векторное представление матрицы H, так что у нас теперь есть эта матрица.
Но как говорилось выше, все это справедливо только для точек, расположенных на одной плоскости. А какие из них расположены, а какие нет, заранее мы не знаем, но может предположить с помощью метода Ransac таким образом:

  1. В цикле, с заранее заданным количеством итераций (скажем 500) выполняем следующие действия:
    • Случайным образом выбираем четыре пары точек кадров A и B.
    • Находим матрицу H.
    • Считаем сколько точек дают ошибку меньше заданного значения, т. е. пусть и тогда должно выполняться условие — .

  2. Выбираем H на той итерации, в которой получилось больше всего точек.

Матрицу H можно получить используя функцию из библиотеки OpenCV – cvFindHomography.

Из матрицы H теперь получим матрицу перехода положения от кадра A к кадру B и назовем ее mMotion.
Для начала выполняем сингулярное разложение матрицы H. Получаем три матрицы: . Введем заранее некоторые значения:
— в итоге должно быть равно ±1;

Массивы (ну или вектора), указывающие нужный знак:

А дальше уже можем получить 8 возможных вариантов mMotion:

;

, где R[i] – матрица поворота,
t[i] – вектор смещения.

И матрицы . Параметр i = 0, ..., 7, и соответственно получаем 8 вариантов матрицы mMotion.
Вообщем, мы имеем следующее соотношение: = mMotion[i] * , т. к. – это единичная матрица, то выходит = mMotion[i].
Осталось выбрать одну матрицу из 8ми mMotion[i]. Понятно, что если выпустить лучи из точек первого и второго кадра, то они должны пересекаться, причем перед камерой, как в первом, так и во втором случае. Значит, подсчитываем количество точек пересечения перед камерой в первом и во втором кадре используя получившиеся mMotion[i], и отбрасываем варианты, при которых количество точек будет меньшим. Оставив пару матриц в итоге, выбираем ту, которая дает меньше ошибок.
Итак, у нас есть матрицы и , теперь зная их можно найти мировые координаты точек по их проекциям.

Вычисление мировых координат точки по нескольким проекциям


Можно было бы воспользоваться методом наименьших квадратов, но на практике у меня лучше работал следующий способ:
Вернемся к формуле 2. Нам необходимо найти точку world, которую обозначим как a. Допустим у нас есть кадры, в которых известны матрицы mWorld (обозначим их как mW[0], mW[1], …) и известны координаты проекций точки a (возьмем сразу с[0], с[1], …).
И тогда имеем такую систему уравнений:

Но можно представить их в таком виде, избавившись от (подобно тому как делали ранее):

где s –любое число не равное нулю,
— система уравнений в матричном виде. T — известно, f — необходимо вычислить, чтобы найти a.
Решив данное уравнение с помощью сингулярного разложения (также как нашли H'), получим вектор f. И соответственно точка .

Вычисление положения камеры используя известные мировые координаты точек


Используется итеративный алгоритм. Начальное приближение – предыдущий результат определения. На каждой итерации:
  1. Ведем еще точки . В идеале точки c[i] должны быть равны точкам b[i], на так как текущее приближение mWorld — это лишь пока приближение (плюс еще другие ошибки вычислений), они будут различаться. Подсчитаем вектор ошибки таким образом: . Решаем систему уравнений методом наименьших квадратов:

    Найти необходимо шестимерный вектор — вектор експоненты.

  2. Находим матрицу cмещения из вектора : dT = exp_transformMatrix(mu).
    Код этой функции:
    TMatrix exp_transformMatrix(const TVector& mu)
    {
        //Вектор mu - 6-мерный вектор 
        TMatrix result(4, 4);//создаем матрицу 4 на 4
        static const float one_6th = 1.0f / 6.0f;
        static const float one_20th = 1.0f / 20.0f;
        TVector w = mu.slice(3, 3);//получаем последние 3 элемента вектора mu 
        TVector mu_3 = mu.slice(0, 3);//получаем первые 3 элемента вектора mu
        float theta_square = dot(w, w);//dot - скалярное произведение векторов
        float theta = std::sqrt(theta_square);
        float A, B;
    
        TVector crossVector = cross3(w,  mu.slice(3));//cross3 векторное произведение 2х 3х-мерных векторов
        if (theta_square < 1e-4) {
            A = 1.0f - one_6th * theta_square;
            B = 0.5f;
            result.setColumn(3, mu_3 + 0.5f * crossVector);//устанавливаем 4ый столбец матрицы
        } else {
            float C;
            if (theta_square < 1e-3) {
                C = one_6th * (1.0f - one_20th * theta_square);
                A = 1.0f - theta_square * C;
                B = 0.5f - 0.25f * one_6th * theta_square;
            } else {
                float inv_theta = 1.0f / theta;
                A = std::sin(theta) * inv_theta;
                B = (1.0f - std::cos(theta)) * (inv_theta * inv_theta);
                C = (1.0f - A) * (inv_theta * inv_theta);
            }
            result.setColumn(3, mu_3 + B * crossVector + C * cross3(w,  crossVector));
        }
        exp_rodrigues(result, w, A, B);
        result(3, 0) = 0.0f;
        result(3, 1) = 0.0f;
        result(3, 2) = 0.0f;
        result(3, 3) = 1.0f;
        return result;
    }
    
    void exp_rodrigues(TMatrix& result, const TVector& w, float A, float B)
    {   
        float wx2 = w(0) * w(0);
        float wy2 = w(1) * w(1);
        float wz2 = w(2) * w(2);
        result(0, 0) = 1.0f - B * (wy2 + wz2);
        result(1, 1) = 1.0f - B * (wx2 + wz2);
        result(2, 2) = 1.0f - B * (wx2 + wy2);
        float a, b;
        a = A * w(2);
        b = B * (w(0) * w(1));
        result(0, 1) = b - a;
        result(1, 0) = b + a;
        a = A * w(1);
        b = B * (w(0) * w(2));
        result(0, 2) = b + a;
        result(2, 0) = b - a;
        a = A * w(0);
        b = B * (w(1) * w(2));
        result(1, 2) = b - a;
        result(2, 1) = b + a;
    }
    
    

  3. Обновляем матрицу .

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

Бонус – трехмерная реконструкция


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

Ссылка на исходный код на github.

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.