UPD: схема заменена на вариант с контейнерами из С++11, соавторы — в комментариях ниже

Привет всем. Я уже однажды писал про Distance Field и приводил реализацию «эвристическим» кодом, дающую неплохую скорость: «Честный glow и скорость».

Зачем он нужен?

DField можно применять:

• Для значительного повышения качества шрифтов
• Для эффектов например горения контура. Один из эффектов я приводил в своей предыдущей статье
• Для эффекта «metaballs» но в 2д и для любых сложных шейпов. (возможно я когда-нибудь приведу пример реализации этого эффекта)
• А в данный момент DField мне нужен для качественного сглаживания углов и удаления мелких деталей.

И если в первых двух случаях мы можем заранее вычислить DField, то для других эффектов нам нужно просчитывать его в реальном времени.
В статье будет рассмотрен наиболее популярный, я бы сказал классический Chamfer distance (CDA) с кучей картинок, объясняющих принцип его работы, а так же рассмотрен двухпроходный алгоритм на GPU.
Оба алгоритма реализованы в демонстрационных программах на FPC.

Не так давно было опубликовано интереснейшее исследование «A Large-Scale Study of Flash Memory Failures in the Field” за авторством Qiang Wu и Sanjev Kumar из Facebook, а также Justin Meza и Onur Mutlu из Университета Карнеги-Меллон. Ниже основные выводы из статьи с небольшими комментариями.

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

Авторами была собрана обширная статистика за четыре года эксплуатации флэш-накопителей в дата-центрах Facebook.

Как многие наверняка знают, Facebook долгое время была лучшим (и основным) клиентом компании Fusuion-IO (сейчас куплена SANdisk), которая одной из первых начала выпускать PCI-e флэш-накопители.


В результате проведенного анализа собранных данных, был сделан ряд интересных выводов:

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

Что такое LLVM?

LLVM — это по-настоящему удобный для разборки и сборки «ранний» компилятор для таких традиционных языков программирования, как C и C++.

LLVM настолько хорош, что считается «больше, чем просто компилятором» (это динамический компилятор, он работает с языками, не относящимися к семейству C, он представляет собой новый формат доставки для App Store и т. д. и т. п.). Все перечисленное верно, но для нашей статьи важно лишь приведенное выше определение.

LLVM имеет несколько ключевых отличий от других компиляторов:

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

Как вы, возможно, знаете в мире Windows для рисования графики часто используется DirectX. В последних версиях (10, 11.x) библиотека серьёзно шагнула вперёд и именно на них построены движки многих современных игр. Кроме того, DirectX используется не только в играх — сам интерфейс ОС Windows тоже с непомню-какой версии (Vista?) рисуется через него, да и казалось-бы не сильно связанные с графикой программы, желая увеличить производительность и плавность зума\скрола переходят на последние версии DirectX. Так некоторое время назад на DirectX11 перешел рендер Google Chrome (вроде бы с версии 36).

Когда-то во времена Windows 95 и Pentium II была такая шутка, что чем медленнее компьютер — тем лучше можно понять работу операционной системы — невооруженным глазом видно в каком порядке прорисовываются элементы окон, обрабатываются события. Сегодня для подобных целей относительно DirectX есть отдельные инструменты — графические отладчики, позволяющие понять, как именно рисуется каждый пиксель каждого кадра, какие операции выполняет движок DirectX, какие ресурсы он использует, насколько быстро и правильно всё работает. Один из таких инструментов — RenderDoc от компании Crytek мы сегодня и рассмотрим. А в качестве примера разберём уже упомянутый выше новый рендер Google Chrome.

Если невежество – это благословление, значит ли это, что высокий IQ приравнивается к страданию? В массовом представлении это так и есть – гениев обычно представляют, как людей, страдающих от страхов, неудовлетворённости и одиночества. Вспомните Вирджинию Вулф, Алана Тьюринга и Лизу Симпсон – одинокие звёзды, изолированные в своей яркости. По словам Хемингуэя: «Счастье у умных людей – самое редкое явление из всех, что я знаю».

Вопрос вроде бы затрагивает не так много людей – но если разобраться в нём, то оказывается, что он влечёт сложные последствия для многих людей. Система образования направлена в основном на улучшение академических знаний. Хотя ограничения системы IQ известны, это всё ещё основной способ измерения когнитивных способностей, и мы тратим кучу денег на тренировки мозга, стараясь улучшить эти показатели. Но что, если поиск гения – это бесполезное дело?

Первые шаги в поисках ответа на этот вопрос сделали ещё 100 лет назад, в эпоху джаза. В то время инновационный тест на IQ набирал популярность, после того, как оправдал себя в вербовочных центрах Первой Мировой. В 1926 году психолог Льюис Терман решил использовать его для проверки группы одарённых детей. Собрав сливки учащихся с калифорнийских школ, он отобрал 1500 учеников с IQ не менее 140. 80 из них имели IQ более 170. Их назвали «Термитами», и истории их жизней изучают по сей день.

Конечно, многие Термиты достигли богатства и успеха. Например, Джесс Оппенгеймер, написавший классический ситком 50-х «I Love Lucy». В те времена, когда его крутили на CBS, средняя зарплата у Термитов вдвое превышала среднюю зарплату тогдашних «белых воротничков». Но не все люди из этой группы оправдали ожидания – многие занялись более скромным делом, стали полицейскими, моряками и машинистками. Поэтому Терман заключил, что «интеллект и достижения очень слабо коррелируют». Их выдающийся ум не гарантировал им личного счастья. Количество разводов, алкоголизма и самоубийств в их среде совпадало со средними уровнями.

Речь сегодня пойдёт о генерации изображений с картой расстояний (Signed Distance Field). Данный вид изображений примечателен тем, что фактически позволяет получить «векторную» графику на видеоускорителе, причём даром. Одной из первых данный метод растеризации предложила компания Valve в игре Team Fortress 2 для масштабируемых декалей в 2007 году, но до сих пор он не пользуется особой популярностью, хотя позволяет рендерить прекрасного качества шрифты, используя текстуру всего 256х256 точек. Данный метод прекрасно подходит для современных экранов высокой чёткости и позволяет серьёзно сэкономить на текстурах в играх, он не требователен к железу и прекрасно работает на смартфонах.



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

Как же создавать такие изображения? Очень просто, ImageMagick позволяет сделать это одной командой:

convert in.png -filter Jinc -resize 400% -threshold 30% \( +clone -negate -morphology Distance Euclidean -level 50%,-50% \) -morphology Distance Euclidean -compose Plus -composite -level 45%,55% -resize 25% out.png

На этом можно было бы поставить точку, но так полноценного топика не получится. Что ж, под катом — описание быстрого алгоритма расчёта SDF, пример на C++ и немного шейдеров для OpenGL.

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

В посте на своем блоге «gdal_translate и gdalwarp для перепроицирования изображений» описывался процесс получения картинок под разные проекции с помощью утилит GDAL. Полученные изображения я использовал как подложки для карт в примерах проекта dbCartajs. Позже, работая над портированием канвасной версии своего планетария на WebGL, описанной в статье «Звездное небо на WebGL с использованием Three.js» на Хабре, у меня возникла мысль со временем перенести не только глобус, но и плоские на карты на WebGL, используя вместо фона текстуры. То есть для создания карты обойтись только использованием браузера и JavaScript без использования серверных компонентов.

24 июня 2015 разработчики Telegram открыли платформу для создания ботов. Новость кого-то обошла стороной Хабр, однако многие уже начали разрабатывать викторины. При этом мало где указаны хоть какие-то примеры работающих ботов.

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

Что же всё-таки можно нарисовать с помощью всего двух треугольников? Квадрат? Фрактал? Полёт сквозь мегатонной мощности взрыв в центре города? Есть ли предел безумию, где заканчивается реальность и начинается явь? Как правильно ухаживать за лучами, чем их кормить и обо что отражать вы узнаете во внезапном продолжении цикла статей про демомейкинг!

Перевод поста Ed Pegg Jr."Biggest Little Polyhedron—New Solutions in Combinatorial Geometry".
Скачать файл, содержащий текст статьи, интерактивные модели многогранников и код, приведенный в статье, можно здесь.
Выражаю огромную благодарность Кириллу Гузенко за помощь в переводе.

---

Во многих областях математики ответом будет единица 1. Возведение неотрицательного числа в квадрат, которое больше или меньше единицы, даст большее или меньшее число соответственно. Иногда для того, чтобы определить, является ли что-то «большим», необходимо выяснить, больше ли единицы наибольший размер этого объекта. К примеру, гигантский гексагон Сатурна с длиной стороны в 13,800 км можно было-бы отнести к большим. «Малый многоугольник» — это тот, у которого максимальное расстояние между вершинами равно единице. В 1975 году Рон Грэм открыл наибольший малый шестиугольник, который, как показано ниже, имеет большую площадь, чем у правильного шестиугольника. Красные диагонали имеют единичную длину. Все остальные (непроведённые) диагонали имеют меньшую длину.

Представляю публичную базу геопозиций телефонных вышек и Wi-Fi роутеров. Мне понадобилась стабильная и безлимитная база для приложения Android, в котором нужна была точная геолокация из всех доступных источников (GPS, Wi-Fi, Mobile). Пришлось создать базу данных положений сотовых вышек и Wi-Fi. Всех заинтересовавшихся прошу под кат.

Сегодня Google Chrome является самым популярным браузером среди веб разработчиков. С быстрым, шести недельным, циклом релизов и мощным набором постоянно расширяющихся инструментов разработчика, превратившим браузер в инструмент, который вы обязаны иметь. Большинство из вас, вероятно, знакомы со многими его функциями, такими как «живое» редактирование CSS, используя консоль и отладчик. В этой статье мы с вами рассмотрим 15 захватывающих советов и хитростей, которые позволят улучшить вашу производительность еще больше.

Доброго времени суток, уважаемые хабравчане. За последнее время я увидел несколько интересных и полезных инструментов/библиотек/событий, которыми хочу поделиться с Хабром.

NativeScript

Открытый фреймворк для создания мобильных приложений под iOS, Android и Windows Phone основанный на NodeJS. И весь цимус в том, что это не очередная кроссплатформенная оболочка над WebView (аля PhoneGap), NativeScript со слов разработчиков обеспечивает на JavaScript такие же возможности, какие обеспечивают нативные Objective-C, Java или .NET.

Также хочу упомянуть о NW.js, который до появления IO.js назывался Node-Webkit. Проект по такому же принципу позволяет писать десктопные приложения под Windows, Mac и Linux с помощью веб-технологий. Более того микроконтроллеры, умные дома, интернет вещей, Oculus Rift, Nest выпускают API на JS. Вспоминая все эти новости, хочется сказать, что JavaScript все чаще и чаще представляется как унифицированное средство для кроссплатформенной разработки.

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

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

Дано:

• общее количество статей 140 000;
• количество спама: примерно 16%;
• количество не чётких дубликатов: примерно 63%;

Задача: избавиться от спама и дубликатов, а так же не допустить их дальнейшего появления.

При написании серьезных проектов перед JavaScript программистами встает выбор: пожертвовать качеством кода и писать классы руками, или же пожертвовать скоростью и использовать систему классов. А если использовать систему, то какую выбрать?

В статье рассмотрена система автора, которая не уступает по скорости классам, написанным «от руки» (другими словами — одна из самых быстрых в мире). Но при этом классы имеют приятную структуру в стиле Си.

Системы классов

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

Каждый из этих велосипедов отличается своим набором возможностей, своим стилем программирования и своим падением скорости. Так, например, создание класса MooTools примерно в 90 раз медленнее, чем создание класса, написанного от руки. Зачем тогда нужны все эти системы?

Введение

Добро пожаловать в третью часть серии статей «Изучаем React». Сегодня мы будем изучать, как устроена архитектура Facebook Flux, и как использовать ее в своих проектах.

Как говорят, с годами планета уменьшается. Лет 500 назад на неизвестных территориях карты писали «здесь живут драконы». Лет 200 назад на планете ещё существовали белые пятна.

Теперь же у нас есть GPS, интернет и Google Maps, и планета уже не кажется такой большой.

Хорошо бы и адрес также можно было уменьшить. Вместо «страна, регион, город, улица, дом» и вместо длинных цепочек цифр-координат — что-нибудь типа короткого url.

Есть такая возможность — это замена координатам и адресам под названием Mapcode. К примеру, адрес телецентра на Королёва, 12 — JC.B4J. Адрес ГУМ — JF.XG.

И так далее.

Все началось с данного топика на сайте gamedev.ru. Топикстартер предложил найти сортировку, которая обладает следующими свойствами:

1. Время выполнения — гарантированные O(nlogn).
2. Использование O(1) дополнительной памяти.
3. Применимость для сортировки данных в односвязных списках (но не ограничиваясь ими).

Оговорки на все три ограничения:

1. Гарантированные O(nlogn) означают, что, например, среднее время быстрой сортировки не подходит — должно получаться O(nlogn) для любых, даже самых худших входных данных.
2. Рекурсию использовать нельзя, поскольку она подразумевает O(logn) памяти на хранение стека рекурсивных вызовов.
3. Произвольного доступа к элементам сортируемого массива нет, мы можем двигаться итератором от любого элемента только к соседнему (за O(1)), причем только в одном направлении (вперед по списку). Модифицировать сам список (перевешивать указатели на следующие элементы) нельзя.

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

Под катом можно узнать, что в итоге получилось у нас.

Challenge. Прежде чем заглядывать под кат, предлагаю сначала самостоятельно подумать над алгоритмом. Если придумается что-то круче нашего варианта — напишите в комментариях.