Pull to refresh
19
0
Andrei Konshyn @konshyn

Render Engineer

Send message

Диаграмма Вороного и её применения

Reading time25 min
Views121K
Доброго всем времени суток, уважаемые посетители сайта Хабрахабр. В данной статье я бы хотел рассказать вам о том, что такое диаграмма Вороного (изображена на картинке ниже), о различных алгоритмах её построения (за , — пересечение полуплоскостей, — алгоритм Форчуна) и некоторых тонкостях реализации (на языке C++).



Также будет рассмотрено много интересных применений диаграммы и несколько любопытных фактов о ней. Будет интересно!
Читать дальше →
Total votes 92: ↑89 and ↓3+86
Comments49

Математические расчёты, стоящие за феноменом роллинг-шаттера

Reading time4 min
Views22K
image

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

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

Первый пропеллер совершает 1/10 оборота во время экспозиции:

image


Подписывайтесь на каналы:
@Ontol — самые интересные тексты/видео всех времен и народов, влияющие на картину мира
@META LEARNING — где я делюсь своими самыми полезными находками про образование и роль ИТ/игр в образовании (а так же мыслями на эту тему Антона Макаренко, Сеймура Пейперта, Пола Грэма, Джозефа Ликлайдера, Алана Кея)

Total votes 68: ↑63 and ↓5+81
Comments48

Нефтянка для инженеров, программистов, математиков и широких масс трудящихся, часть 4

Reading time10 min
Views10K
image

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

Сегодня мы расскажем о том, зачем нужны модели месторождений, и как их строить. Модель – это план действий, который обязательно должен быть, а кроме этого – предполагаемый и ожидаемый результат этих действий.

Читать дальше →
Total votes 24: ↑24 and ↓0+24
Comments4

Вейвлет деревья

Reading time10 min
Views6.5K
Succinct data structures свежее веяние в алгоритмистике. В русскоязычной школе материала мало, нет даже устоявшегося перевода. Будем восполнять этот пробел. На правах первопроходцев терминологию будем вводить налету. Пусть, скажем, компактные структуры данных. На Хабре уже появилась хорошая ознакомительная статья.

Под катом развитие темы с описанием пары новых(такое вы не найдете у Кнута) трюков структур, примеры применения и реализация на языке Go.

Итак — вейвлет дерево

Читать дальше →
Total votes 14: ↑12 and ↓2+13
Comments6

Пора обновить ваш монитор

Reading time16 min
Views175K

Иллюстрация: Юлия Прокопова

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

Поэтому я оптимизирую настройки, чтобы показывать действительно, действительно хорошие буквы. Для этого необходим хороший монитор. Не просто нужен, а ОБЯЗАТЕЛЕН. А под «хорошим» я имею в виду настолько хороший, насколько это возможно. Это мои мысли, основанные на моём собственном опыте того, какие мониторы лучше подходят для программирования.
Читать дальше →
Total votes 142: ↑109 and ↓33+115
Comments991

Анатомия RAM

Reading time14 min
Views105K
image

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

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

Зачем же ты, RAM-ео?


Процессорам требуется очень быстро получать доступ к данным и командам, чтобы программы выполнялись мгновенно. Кроме того, им нужно, чтобы при произвольных или неожиданных запросах не очень страдала скорость. Именно поэтому для компьютера так важно ОЗУ (RAM, сокращение от random-access memory — память с произвольным доступом).

Существует два основных типа RAM: статическая и динамическая, или сокращённо SRAM и DRAM.

Мы будем рассматривать только DRAM, потому что SRAM используется только внутри процессоров, таких как CPU или GPU. Так где же находится DRAM в наших компьютерах и как она работает?
Читать дальше →
Total votes 26: ↑25 and ↓1+33
Comments31

Деловая переписка на английском языке: фразы и советы

Reading time18 min
Views604K
Елена Соловьева, менеджер проектов в компании Лаборатория Касперского, специально для блога Нетологии поделилась советами о том, как вести деловую переписку с иностранными коллегами и партнерами на английском языке. Статья участвует в конкурсе.

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

Задача становится сложнее, если вы общаетесь на неродном английском языке с представителями других культур. В статье я поделюсь, на что в этом случае обратить внимание, как избежать ошибок и достичь взаимопонимания с иностранными коллегами и партнерами.
Читать дальше →
Total votes 104: ↑100 and ↓4+96
Comments80

Реверс-инжиниринг микропроцессора Intel 8086

Reading time6 min
Views26K
В июне 1978 года был представлен один из самых влиятельных чипов в полупроводниковой индустрии – Intel 8086. Он положил начало архитектуре х86, которая до сих пор доминирует сегодня в настольных и серверных вычислениях. Давайте заглянем вглубь чипа и разберём внутреннее строение и архитектурные особенности этого микропроцессора.

image

На фото ниже изображён кристалл процессора Intel 8086. На фото виден металлический слой чипа, скрывающий кремний под ним. По краям матрицы расположены тонкие провода, обеспечивающие соединение между площадками на чипе и внешними контактами. Силовые и заземляющие площадки имеют по два соединительных провода для поддержания более высокого тока. Микросхема была очень сложной для своего времени и содержала 29 тысяч транзисторов. Обратите внимание на маркировку кристалла в самом низу – на ней указан логотип Intel, модель процессора и год изготовления микросхемы.

image
Кристалл процессора Intel 8086

image

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

image

Читать дальше →
Total votes 43: ↑43 and ↓0+43
Comments185

Как писать на ассемблере в 2018 году

Reading time13 min
Views321K


Статья посвящена языку ассемблер с учетом актуальных реалий. Представлены преимущества и отличия от ЯВУ, произведено небольшое сравнение компиляторов, скрупулёзно собрано значительное количество лучшей тематической литературы.
Читать дальше →
Total votes 117: ↑102 and ↓15+87
Comments167

Нефтянка для инженеров, программистов, математиков и широких масс трудящихся, часть 3

Reading time12 min
Views16K
image

Сегодня мы расскажем о том, кто куда мигрирует в нефтяной отрасли, о том, что происходит с месторождением при добыче, и о том, как вода, нефть и газ взаимодействуют. Это третья часть из серии статей для будущих математиков-программистов, которым предстоит решать задачи, связанные с моделированием нефтедобычи и разработкой инженерного ПО в области сопровождения нефтедобычи. В книжках всё расписано гораздо подробнее, зато здесь о нефтянке рассказывают программисты и для программистов.
Читать дальше →
Total votes 23: ↑23 and ↓0+23
Comments4

Повышаем эффективность распределения точек на сфере

Reading time9 min
Views7.2K
Наложение решётки Фибоначчи (она же золотая спираль или сфера Фибоначчи) на поверхность сферы — чрезвычайно быстрый и эффективный приближенный метод равномерного распределения точек на сфере. Я продемонстрирую, как небольшие изменения, внесённые в каноническую реализацию, могут привести к значительным улучшениям показателей ближайших соседей.


Рисунок 1. Небольшая модификация канонической решётки Фибоначчи может привести к улучшению расстояния упаковки (максимального расстояния между ближайшими соседями) на 8,3%.
Читать дальше →
Total votes 21: ↑21 and ↓0+21
Comments7

Симуляция гидравлической эрозии

Reading time7 min
Views3.8K

Гидравлическая эрозия — это процесс постепенного преображения водой рельеф. В основном она вызывается осадками, но на неё также влияют разбивающиеся о побережье волны океана, а также течения рек. На рисунке 1 показаны масштабные эффекты, которые может оказать небольшой поток на окружающие его скалы. При создании реалистичных окружений необходимо учитывать влияние эрозии. Я уже экспериментировал с процедурной генерацией при создании сцен для послойного рендеринга вокселей и для демонстрации кубического шума. Такие рельефы очень просты и в них не учитывается влияние эрозии. Следовательно, им не хватает деталей, из-за чего они при близком рассмотрении кажутся нереалистичными.


Рисунок 1: небольшой водопад.

В этой статье я подробно расскажу о простом и быстром способе аппроксимации эффектов гидравлической эрозии.
Читать дальше →
Total votes 12: ↑12 and ↓0+12
Comments0

Алгоритм быстрого и простого объёмного рендеринга

Reading time9 min
Views14K

Недавно я написал небольшой ShaderToy, выполняющий простой объёмный рендеринг, а затем решил опубликовать пост с объяснением его работы. Сам интерактивный ShaderToy можно посмотреть здесь. Если вы читаете с телефона или ноутбука, то рекомендую посмотреть эту быструю версию. Я включил в пост фрагменты кода, которые помогут вам понять работу ShaderToy на высоком уровне, но в них есть не все подробности. Если вы хотите разобраться глубже, то рекомендую сверяться с кодом ShaderToy.

У моего ShaderToy были три основные задачи:

  1. Выполнение в реальном времени
  2. Простота
  3. Физическая корректность (… или типа того)

Я начну с этой сцены с кодом-заготовкой. Не буду вдаваться в подробности реализации, потому что она не очень интересна, но вкратце расскажу, с чего мы начинаем:

  1. Трассировка лучей непрозрачных объектов. Все объекты являются примитивами с простыми пересечениями с лучами (1 плоскость и 3 сферы)
  2. Для вычисления освещения используется затенение по Фонгу, а в трёх сферических источниках света применется настраиваемый коэффициент затухания света. Лучи теней не требуются, потому что мы освещаем только плоскость.

Вот как это выглядит:

ShaderToy screenshot
Читать дальше →
Total votes 52: ↑52 and ↓0+52
Comments6

Анатомия KD-Деревьев

Reading time14 min
Views48K
image

Эта статья полностью посвящена KD-Деревьям: я описываю тонкости построения KD-Деревьев, тонкости реализации функций поиска 'ближнего' в KD-Дереве, а также возможные 'подводные камни', которые возникают в процессе решения тех или иных подзадач алгоритма. Дабы не запутывать читателя терминологией(плоскость, гипер-плоскость и т.п), да и вообще для удобства, полагается что основное действо разворачивается в трехмерном пространстве. Однако же, где нужно я отмечаю, что мы работаем в пространстве другой размерности. По моему мнению статья будет полезна как программистам, так и всем тем, кто заинтересован в изучении алгоритмов: кто-то найдет для себя что-то новое, а кто-то просто повторит материал и возможно, в комментариях дополнит статью. В любом случае, прошу всех под кат.
Читать дальше →
Total votes 32: ↑32 and ↓0+32
Comments11

Алгоритм сортировки Timsort

Reading time6 min
Views151K
Timsort, в отличии от всяких там «пузырьков» и «вставок», штука относительно новая — изобретен был в 2002 году Тимом Петерсом (в честь него и назван). С тех пор он уже стал стандартным алгоритмом сортировки в Python, OpenJDK 7 и Android JDK 1.5. А чтобы понять почему — достаточно взглянуть на вот эту табличку из Википедии.



Среди, на первый взгляд, огромного выбора в таблице есть всего 7 адекватных алгоритмов (со сложностью O(n logn) в среднем и худшем случае), среди которых только 2 могут похвастаться стабильностью и сложностью O(n) в лучшем случае. Один из этих двух — это давно и хорошо всем известная «Сортировка с помощью двоичного дерева». А вот второй как-раз таки Timsort.

Алгоритм построен на той идее, что в реальном мире сортируемый массив данных часто содержат в себе упорядоченные (не важно, по возрастанию или по убыванию) подмассивы. Это и вправду часто так. На таких данных Timsort рвёт в клочья все остальные алгоритмы.
Читать дальше →
Total votes 293: ↑286 and ↓7+279
Comments63

Делить на ноль — это норма. Часть 1

Reading time9 min
Views220K
Часть 1. Вобще-то уже все поделили до нас!
Часть 2. Истина где-то рядом

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


Читать дальше →
Total votes 106: ↑98 and ↓8+90
Comments102

Имитация рисования от руки на примере RoughJS

Reading time8 min
Views11K
RoughJS это маленькая (<9 КБ) графическая библиотека JavaScript, позволяющая рисовать в эскизном, рукописном стиле. Она позволяет рисовать на <canvas> и с помощью SVG. В этом посте я хочу ответить на самый популярный вопрос о RoughJS: как это работает?


Немного истории


Очарованный изображениями рукописных графиков, схем и эскизов, я, как истинный нерд, задался вопросом: можно ли создавать такие рисунки с помощью кода, как можно точнее имитировать рисунок от руки, в то же время сохранив возможность программной реализации? Я решил сосредоточиться на примитивах — линиях, многоугольниках, эллипсах и кривых, чтобы создать целую библиотеку 2D-графики. На её основе можно создавать библиотеки и графики для рисования графиков и схем.

Вкратце изучив вопрос, я нашёл статью Джо Вуда и его коллег под названием Sketchy rendering for information visualization. Описанные в ней техники стали основой библиотеки, особенно в рисовании линий и эллипсов.

В 2017 году я написал первую версию библиотеки, которая работала только на Canvas. Решив задачу, я потерял к ней интерес. Год спустя я много работал с SVG, и решил адаптировать RoughJS для работы с SVG. Также я изменил структуру API, сделав её более простой, и сосредоточился на простых векторных графических примитивах. Я рассказал о версии 2.0 на Hacker News и внезапно она обрела огромную популярность. В 2018 году это был второй по популярности пост ShowHN.
Читать дальше →
Total votes 46: ↑46 and ↓0+46
Comments4

Секреты синхронизации электромагнитных полей Земли и живого организма

Reading time12 min
Views75K


Организм человека это очень сложный механизм, работа которого зависит не только от целостности деталей, но и от воздействия внешних факторов. Мы частенько слышим формулировки «метеочувствительность», «суставы болят на погоду», «хандра во время дождя» и т.д. На первый взгляд все это кажется не особо научным, однако никогда не стоит отклонять нестандартные варианты объяснения чего-либо. Связь между работой системы и средой, ее окружающей, так или иначе есть всегда. Вопрос в том, как она проявляется и как это доказать. Сегодня мы с вами познакомимся с исследованием, в котором ученые из университета Тель-Авива впервые выявили доказательства связи между активностью электрического поля живого организма и электрического поля окружающей среды. Как именно проявляется связь электрических полей, зачем она нужна и откуда появилась? Об этом мы узнаем из доклада ученых. Поехали.
Total votes 23: ↑21 and ↓2+29
Comments26

Библиотека ttf2mesh — преобразование TrueType шрифтов в сетку

Reading time11 min
Views6.9K

Многим известна проблема трёхмерной графики — отсутствие легковесных кроссплатформенных решений в вопросе вывода текста.


Большинство реализаций позволяет использовать выбранный шрифт в виде текстуры. Публикуемая библиотека ttf2mesh реализует другой способ — она преобразует векторные символы TrueType шрифта в сеточные объекты. Это позволяет выводить текст в виде набора треугольников.


image


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

Читать дальше →
Total votes 34: ↑34 and ↓0+34
Comments15

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

Reading time12 min
Views222K


Знаете что общего между ситуацией с уничтожением антенн сотовой связи и последней лентой Тарантино «Однажды в Голливуде»? Они оба делят людей на два противоположных лагеря.
Читать дальше →
Total votes 244: ↑216 and ↓28+244
Comments340

Information

Rating
Does not participate
Date of birth
Registered
Activity