Введение в курс. 5 алгоритмов для задачи Vertex Cover

Линейные ядра для Vertex Cover, Color Coding для $k$-пути

Алгоритмы для задач о Гамильтоновом пути и ориентированном $k$-пути

Алгоритм для $k$-пути в неориентированных графах

Алгоритмы для NP-трудных задач

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

Введение

- Локальные ключевые точки и дескрипторы
- Требования к инвариантности ключевых точек и дескрипторов к преобразованиям изображений 
- Разбор деталей реализации алгоритма SIFT

Детектор SIFT

- Оптимизации скорости подсчета расстояния между парой дескрипторов
- SIFT: Сокращение размерности, бинаризация
- Бинарные дескрипторы
- Оптимизации поиска ближайших соседей между парой кадров
- Hardware оптимизации на GPU
- Approximate Nearest Neighbors, Flann, проклятие размерности
- Оптимизации количества пар сопоставляемых кадров
- Преселекции по порядку кадров, по GPS привязке, по грубым матчам

Сопоставление ключевых точек, оптимизации по скорости

- Виды ошибочных сопоставлений, шумы и честные false positives
- Ratio test: фильтрация false positives
- Left-right check, cluster filtering
- Фильтрация очень шумных матчей с помощью GMS matcher

Сопоставление ключевых точек, оптимизации по качеству

- Сложные примеры матчинга
- История learned дескрипторов, LIFT, HyNet, Superpoint, ALIKED
- Learned матчеры, SuperGlue, LightGlue
- Learned sfm: Mast3r, DepthAnything3

Learned дескрипторы и матчеры

- Однородные координаты
- Поиск гомографии по матчам
- Склейка фотографий в панораму по гомографии

Однородные координаты, гомография, панорама

- Pinhole camera, Brown distortion model
- Fisheye & spherical cameras
- Rolling shutter

Модели камеры

- Эпиполярная геометрия
- Фундаментальная матрица
- Триангуляция, резекция

Structure from Motion

Фотограмметрия: трехмерная реконструкция

На первой лекции курса обсудим:
- какой уровень C++ и знания алгоритмов ожидается от студентов
- в общих чертах архитектуру CPU чтобы было с чем дальше сравнивать GPU
- Instruction Level Parallelism, Branch Prediction, Cache Lines, Simultaneous Multithreading, Hyper-Threading
- обсудим как работает эксплуатация уязвимостей Meltdown/Spectre
- обсудим SIMD, SSE, AVX intrinsics на примере фрактала Мандельброта
- посмотрим на историю видеокарт и как они пришли от графических задач GPU к задачам вычислений общего назначения GPGPU
- введение в OpenCL API и взглянем на первое домашнее задание на [https://github.com/GPGPUCourse](https://github.com/GPGPUCourse)

Архитектура CPU, история GPU и GPGPU, введение в OpenCL API

- Архитектура GPU (на контрасте с CPU)
- Модель массового параллелизма
- code divergence, coalesced memory access
- latency hiding, occupancy, registers pressure/spilling
- Speed of Light (SoL) анализ, профилировщики
- Синтаксис кернелов на OpenCL, CUDA, Vulkan

Архитектура GPU, модель массового параллелизма

- Напоминание ментальной модели
- Local Memory, barrier, bank conflicts
- Суммирование чисел, reduction

Локальная память, суммирование массива

- Транспонирование через local memory (bank conflicts)
- Умножение матриц через local memory
- Tensor Cores, WMMA
- Оптимизации fp8 DeepSeek
- Умножение матриц Методом Штрассена и Виноградова

Транспонирование и умножение матриц

- Битовая арифметика
- Префиксная сумма (Scan)
- Как отлаживать
- OpenCL/CUDA самописный эмулятор

Префиксные суммы, scan, битовая арифметика

- Результаты соревнования по умножению матриц
- Bitonic sort (битоническая сортировка)
- Radix sort (поразрядная сортировка)
- Как отлаживать

Bitonic sort, radix sort

- Merge sort на GPU (merge path)
- Coarse to Fine схема оптимизаций
- Patch Match алгоритм ретуширования фотографий и построения карт глубины, оптимизация под видеокарты
- Look Up Tables (LUT): поиск соседей в октодереве, маршировка кубов для реконструкции поверхности

Merge sort, Coarse-to-Fine схема, Patch Match, Look Up Tables

- Разреженные матрицы
 - COO, CSR, CSC
 - ELL, DIA, HYB
 - Система Непересекающихся Множеств (СНМ, Disjoint Set)

Разреженные матрицы, Системы Непересекающихся Множеств

- Ray Tracing, Bounded Volume Hierarchy, AABB
 - Z curve, Morton code
 - Linear BVH (LBVH), H-PLOC
 - Как читать научные статьи

Real-time построение BVH для Ray Tracing

- Signed Distance Functions
- shadertoy.com
- Ray marching
- Применения в физических симуляциях, глобальном освещении и навигации роботов

Signed Distance Functions

- Вершинный и фрагментный шейдеры
- Растеризация в OpenGL/Vulkan
- Алгоритм Брезенхэма
- Проект Larrabee
- Проект cudaraster

Программная растеризация

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

Представьте: gamedev-команда Babazaki разрабатывает игру. 3D-моделлеры создали ПОТРЯСАЮЩИЙ воображение мир: скалы, пещеры, замки, ЦИКЛОПИЧЕСКИХ РАЗМЕРОВ ДЕРЕВО.

Разработчики загрузили это на видеокарту, попытались отрисовать, видеокарта отрисовала 1 FPS и произошел отвал GPU-чипа. Заменили видеокарту - ситуация повторилась. Так сделали 10 раз - игра показала КРАЙНЕ стабильное поведение. Выбросив 11 видеокарт, РАЗРАБОТЧИКИ ЧТО-ТО ЗАПОДОЗРИЛИ, сказали 3D-моделлерам, что современные технологии не могут отрисовать мир из более чем тысячи треугольников. 3D-моделлеры пригорюнились: «Но так мы ничего красивого не создадим... Это будет посредственная игра!»

И шли споры... шли долго... до 2021 года... Как вдруг в переговорку вошел он, Brian Karis, и приободрил он моделлеров, и заговорщицки подмигнул разработчикам, и молвил: «Не дело это идти на компромиссы! Но и FPS хороший нужен! Вы мне высокополигональную геометрию, а я вам - высокий FPS! Мена? Мена!» И пошло, и поехало! И вынул он из-за пазухи конверт, на конверте было написано Unreal Engine 5, а внутри конверта был Nanite!

Обсудим как работает Nanite:
 - виртуальные текстуры
 - кластеризация графов
 - иерархичный Z buffer (Z test)
 - репроекция кадров в VR
 - deferred rendering
 - софтварный растеризатор для ускорения (т.к. реализация в видеодрайверах - СУБОПТИМАЛЬНА, можно лучше)
 - упрощение геометрии алгоритмом QSlim (схлопывание ребер)
 - и чем же Nanite принципиально отличается от упрощения геометрии и объектов разного LOD (level of details)

Пререквизиты (можно послушать в первых 15 минутах последней лекции [ссылка](https://www.youtube.com/@ComputerScienceSpace)):
 - что такое растеризация
 - что такое вершинные и фрагментные шейдеры

Контакты

Адрес

Открытое
Computer Science
Объединение

Мероприятия

КомандаПроекта

Контакты

Адрес

ОткрытоеComputer ScienceОбъединение

Мероприятия

КомандаПроекта

Открытое
Computer Science
Объединение