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

Я достаточно долгое время использовал sublime (около 4 лет) в качестве основной среды разработки, но в последнее время кое-что изменилось: я освоил слепой 9-ти пальцевый метод печати. В тот момент я начал понимать людей, которым неудобно тянуться к мышке или стрелочкам. Убирать пальцы с «домашних» позиций стало неестественно и непродуктивно. Тогда я включил vintage. Проблема, вроде бы, стала неактуальна, но чего-то не хватало. Не помню, что заставило меня пересесть за vim, но мне всегда нравилось, как в нем выделяются фигурные скобки (MatchParen) и как выглядит курсор :). Vim я пробовал и до этого, когда правил конфиги на сервере, правда, вся «магия» ограничивалась переходом в режим вставки и успешным сохранением/выходом из редактора.

Содержание основного курса

• Статья 1: алгоритм Брезенхэма
• Статья 2: растеризация треугольника + отсечение задних граней
• Статья 3: Удаление невидимых поверхностей: z-буфер
• Статья 4: Необходимая геометрия: фестиваль матриц
  
  • 4а: Построение перспективного искажения
  • 4б: двигаем камеру и что из этого следует
  • 4в: новый растеризатор и коррекция перспективных искажений
• Статья 5: Пишем шейдеры под нашу библиотеку
• Статья 6: Чуть больше, чем просто шейдер: просчёт теней

Улучшение кода

• Статья 3.1: Настала пора рефакторинга
• Статья 3.14: Красивый класс матриц

---

Official translation (with a bit of polishing) is available here.

---

Пришла пора веселья, давайте для начала смотреть размер текущего кода:

• geometry.cpp+.h — 218 строк
• model.cpp+.h — 139 строк
• our_gl.cpp+.h — 102 строки
• main.cpp — 66 строк

Итого 525 строк. Ровно то, что я обещал в самом начале курса. И заметьте, что отрисовкой мы занимаемся только в our_gl и main, а это всего 168 строк, и нигде мы не вызывали сторонних библиотек, вся отрисовка сделана нами с нуля!
Я напоминаю, что мой код нужен только для финального сравнения с вашим работающим кодом! По-хорошему, вы всё должны написать с нуля, если следуете этому циклу статей. Очень прошу, делайте самые безумные шейдеры и выкладывайте в комментарии картинки!!!

Оглавление (на данный момент)

Часть 1. Описание, операции, применения.
Часть 2. Ценная информация в дереве и множественные операции с ней.
Часть 3. Декартово дерево по неявному ключу.
To be continued...

Очень сильное колдунство

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

Вспомним-ка еще раз структуру дерамиды. В ней есть ключ x, по которому дерамида есть дерево поиска, случайный ключ y, по которому дерамида есть куча, а также, возможно, какая-то пользовательская информация с (cost). Давайте совершим невозможное и рассмотрим дерамиду… без ключей x. То есть у нас будет дерево, в котором ключа x нет вообще, а ключи y — случайные. Соответственно, зачем оно нужно — вообще непонятно :)

На самом деле расценивать такую структуру стоит как декартово дерево, в котором ключи x все так же где-то имеются, но нам их не сообщили. Однако клянутся, что для них, как полагается, выполняется условие двоичного дерева поиска. Тогда можно представить, что эти неизвестные иксы суть числа от 0 до N-1 и неявно расставить их по структуре дерева:

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

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