Источник: habrahabr
Antelle
В отличии от человеческого глаза, компьютер рендерит всю сцену в фокусе. И камера, и глаз же имеют ограниченную глубину резкости вследствие конечного диаметра апертуры зрачка или объектива. Для достижения большего фотореализма рекомендуется использовать эффект глубины резкости в изображениях, получаемых на компьютере. Кроме того, управление глубиной резкости помогает раскрыть художественный замысел автора, выделив важный по смыслу объект.
До сих пор задача изображения реалистичной глубины резкости в компьютерной графике полностью не решена. Существует множество решений, обладающих плюсами и минусами, применимых в разных случаях. Мы рассмотрим самые популярные на сегодняшний момент.
В оптике
Свет, преломляясь в линзе, формирует изображение на светочувствительном элементе: плёнка, матрица, сетчатка. Чтобы света в камеру проникло достаточное количество, входная апертура (диаметр светового пучка на входе в оптическую систему) должна быть достаточного размера. Лучи от одной точки в пространстве всегда сходятся ровно в одну точку за линзой, но эта точка не обязательно совпадает с выбранной картинной плоскостью (полскостью сенсора). Поэтому изображения имеют ограниченную глубину резкости - то есть, объекты будут тем более размытыми, чем больше разница расстояния от объекта до линзы и фокусного расстояния. В результате, точку, находящуюся на определённом расстоянии, мы увидим как размытое пятно: пятно рассеяния (Circle of Confusion, CoC). Радиус размытия вычисляется по определённому закону:
Определение диаметра размытия (более подробно см. в Википедии).
Методы, применяемые в рендерерах, используют модель камеры-пинхола (в которой входная апертура → 0, а следовательно, все объекты будут в фокусе). Симуляция апертуры конечного размера и, следовательно, глубины резкости, требует дополнительных усилий.
Точка в сцене проецируется на картинную плоскость в виде пятна рассеяния.
Общий обзор
Способы реализации глубины резкости можно разделить на две большие группы: методы пространства объектов (object space) и методы пространства изображения (image space).Методы пространства объектов работают с 3D-представлением объектов сцены и таким образом применяются во время рендера. Методы пространства изображения, также известные как методы постобработки (postprocess), оперируют с растровыми изображениями, полученными при помощи стандартной модели камеры-пинхола (полностью в фокусе). Для достижения эффекта глубины резкости эти методы размывают участки изображения, учитывая карту глубины (depth map). Вообще, методы пространства объектов способны выдать более физически точный результат и обладают меньшим числом артефактов, нежели методы пространства изображения, в то время как методы пространства изображения значительно быстрее.
Методы пространства объектов бывают основаны или на геометрической оптике, или на волновой оптике. В большинстве приложений используется геометрическая оптика, чего достаточно для достижения подавляющего большинства целей. Однако в расфокусированных изображениях не последнюю роль могут играть дифракция и интерференция; для их учёта и необходимо применять законы волновой оптики.
Методы пространства изображения можно разделить на применяемые к генерируемым изображениям и применяемые в цифровой фотографии. Традиционные техники постобработки требуют наличия карты глубины, в которой содержится информация об отдалённости точки изображения от камеры, но такую карту сложно получить для фотографий. Существует интересная техника световых полей, позволяющая выполнять размытие объектов не в фокусе без карты глубины. Недостаток технологии в том, что она требует специального оборудования, но получаемые изображения не имеют ограничения на сложность сцены.
Методы пространства объектов (object space approaches)
Распределённая трассировка лучей (distributed ray tracing)
Метод напрямую симулирует геометрическую оптику. Вместо трассировки одного луча на семпл (в оригинале - пиксель, но я счёл это неуместным, т.к. количество просчитанных лучей будет изменяться в зависимости от настроек AA и редко когда равняется одному пикселю), что симулирует камеру-пинхол, надо выбрать несколько лучей, чтобы получить аналог изображения, полученного на камеру с конечной апертурой. Лучи для каждого семпла исходят из одной точки на картинной плоскости, но направлены в разные участки линзы. После преломления линзой луч испускается в сцену.Из описания видно, что изображение формируется, учитывая физические законы оптики (исключая волновую). Поэтому изображения, полученные таким способом, довольно реалистичные и считаются "золотым стандартом", по которому можно проверять методы постобработки. Недостаток метода очевиден: для каждого семпла следует просчитать количество лучей, достаточное для получения качественного размытия, соответственно, время рендера увеличивается. Если требуется получить малую глубину резкости, потребуется увеличение времени рендера в сотни или тысячи раз. При использовании недостаточного числа дополнительных лучей в размытых областях появится шум.
Метод реализован в шейдере mia_lens_bokeh:
// параметры шейдера
struct depth_of_field {
miScalar focus_plane_distance;
miScalar blur_radius;
miInteger number_of_samples;
};
miBoolean depth_of_field (
miColor *result, miState *state, struct depth_of_field *params )
{
// получаем параметры
miScalar focus_plane_distance = *mi_eval_scalar(¶ms->focus_plane_distance);
miScalar blur_radius = *mi_eval_scalar(¶ms->blur_radius);
miUint number_of_samples = *mi_eval_integer(¶ms->number_of_samples);
miVector camera_origin, camera_direction, origin, direction, focus_point;
double samples[2], focus_plane_z;
int sample_number = 0;
miColor sum = {0,0,0,0}, single_trace;
// переводим в другую систему координат
miaux_to_camera_space(state, &camera_origin, &camera_direction);
// ищем точку пересечения
focus_plane_z = state->org.z - focus_plane_distance;
miaux_z_plane_intersect(&focus_point, &camera_origin, &camera_direction, focus_plane_z);
// считаем заданное количество семплов
while (mi_sample(samples, &sample_number, state, 2, &number_of_samples)) {
miaux_sample_point_within_radius(&origin, &camera_origin, samples[0], samples[1], blur_radius);
mi_vector_sub(&direction, &focus_point, &origin);
mi_vector_normalize(&direction);
miaux_from_camera_space(state, &origin, &direction);
mi_trace_eye(&single_trace, state, &origin, &direction);
miaux_add_color(&sum, &single_trace);
}
// нормализуем результат
miaux_divide_color(result, &sum, number_of_samples);
return miTRUE;
}
Результат применения шейдера (код взят из мануала mental ray, картинка оттуда же).
Реалистичные модели камеры (realistic camera models)
В предыдущем методе преломнелие в линзе рассчитывалось по одному закону. Однако же, это не всегда так. Объективы состоят из групп линз, обладающих разными свойствами:
Группы линз в объективе (картинка Pat Hanrahan).
Оптические спецификации объектива, предоставляемые производителями, корректно реализуются в виде математической модели. Модель включает в себя симуляцию групп линз и предоставляет также модель выходного отверстия (в пределах которого рендерер будет испускать лучи для одного семпла). Попадающие в выходное отверстие лучи просчитываются, учитывая оптические свойства групп линз, через которое они проходят.
Метод позволяет физически корректно симулировать как глубину резкости, так и искажения, вносимые линзой.
Объективы с разным фокусным расстоянием: с изменением фокусного расстояния и модели линзы меняется перспектива и могут появляться искажения (например, как на верхней картинке) - картинка Pat Hanrahan.
Пример шейдера, реализующего объектив-фишай:
struct fisheye {
miColor outside_color;
};
miBoolean fisheye (miColor *result, miState *state, struct fisheye *params )
{
miVector camera_direction;
miScalar center_x = state->camera->x_resolution / 2.0;
miScalar center_y = state->camera->y_resolution / 2.0;
miScalar radius = center_x < center_y ? center_x : center_y;
miScalar distance_from_center = miaux_distance(center_x, center_y, state->raster_x, state->raster_y);
if (distance_from_center < radius) {
mi_vector_to_camera(state, &camera_direction, &state->dir);
camera_direction.z *= miaux_fit(distance_from_center, 0, radius, 1, 0);
mi_vector_normalize(&camera_direction);
mi_vector_from_camera(state, &camera_direction, &camera_direction);
return mi_trace_eye(result, state, &state->org, &camera_direction);
} else {
*result = *mi_eval_color(¶ms->outside_color);
return miTRUE;
}
}
Результат применения шейдера (код взят из мануала mental ray, картинка оттуда же).
Буфер накопления (accumulation buffer)
Для достижения эффекта глубины резкости также можно использовать буфер накопления. Рендерится несколько кадров, после чего, усредняя их, мы получаем искомое изображение. Метод очень похож на распределённую трассировку лучей, но быстрее его, т.к. рендериг происходит при помощи аппаратных средств. Однако же, в первом методе мы можем адаптивно контролировать количество семплов и получить картинку приемлемого качества, используя меньше семплов. Метод применим только там, где можно отреднерить сцену аппаратно.Симуляция распространения волн (wawe propagation)
Все методы, рассмотренные выше, используют законы геометрической оптики, игнорируя дифракцию и интерференцию. Если в сцене есть несколько точечных источников, излучающих свет определённой длины волны, можно отследить распространение световых волн в пространстве. Картинная плоскость располагается на определённом расстоянии и для определения значения семпла учитывается вклад от всех волн, испускаемых источниками. Вычисления можно производить в частотном домене, используя преобразование Фурье.Разброс (splatting) [Krivanek]
При рендере сцена представляется не как набор геометрических примитивов с текстурами, а в виде набора точек. Точки разбрасываются по определённому закону, чаще всего по Гауссовскому. Для достижения большей скорости, при разбросе точек используется операция свёртки, учитывающая функцию размытия точки (point spread function, PSF). В случае размытия по Гауссу, параметром PSF является стандартное отклонение.Полученные точки хранятся в дереве и при выборе точки из размытой области поиск производится в определённом радиусе. Это позволяет просчитывать меньшее количество семплов в расфокусированных областях изображения.
Логично предположить, что довольно жёстким ограничением метода является возможность представления сцены в требуемом виде.
Изображение, полученное методом разброса. В размытых областях плотность семплирования меньше (картинка Jaroslav Krivanek).
Аналитическая видимость (analytical visibility) [Catmull]
Имея трёхмерную сцену, можно аналитически определить, какие объекты находятся вне фокуса. Для таких объектов берётся меньшее число семплов, в результате они выглядят размытыми. Метод позволяет получить точные изображения без шума, в отличие от распределённой трассировки лучей.Методы пространства изображения (image-space approaches)
Идеальный метод постобработки должен обладать следующими свойствами:
- Выбор функции разброса точки (point spread function, PSF)
Вид размытия зависит от PSF, определяющей, какое пятно рассеяния мы получим от одной точки. Так как в разных оптических системах данная характеристика будет разной, хороший метод должен позволять выбрать вид PSF.
Разные PSF позволяют получить разный характер размытия. - Попиксельный контроль над размытием
В каждой точке изображения размер и характер пятна рассеяния отличается. Обычно методы пост-обработки не позволяют изменять характер размытия в зависимости от положения точки. Это обусловлено ещё и тем, что часто в методах используются или сепарабельные фильтры, или преобразование Фурье, что делает подобный выбор затруднительным для реализации.
На первом изображении PSF одинаковая; на втором меняется, что более точно симулируетГелиос-44особенности некоторых линз. - Отсутствие артефактов нехватки интенсивности (intensity leakage artifacts)
Размытый объект на заднем плане никогда не заходит за границы объекта в фокусе. Однако примитивные линейные фильтры могут не учитывать этот факт; проявляемые в результате этой ошибки артефакты нехватки интенсивности уменьшают реалистичность изображения.
На изображении зелёная фигура в фокусе, следовательно, размытие объекта на заднем плане не должно распространяться на её. - Отсутствие артефактов, обусловленных ненепрервыной глубиной (depth discontinuity artifacts)
В реальности размытие объекта на переднем плане будет мягким, у объекта не будет видимого жёсткого контура. Часто фильтры размывают объект так, что он одновременно имеет и размытие, и силуэт, что неправильно. Такое поведение обусловлено особенностями сглаживания карты глубины, в результате чего на границе объекта глубина меняется ступенчато (и получается, что на краю объекта, как и за его пределами, пиксели смешанных цветов).
Результат применения разных фильтров. Из-за того, что изображение (beauty map) сглажено, а карта глубины (depth map) - нет, могут возникнуть подобные артефакты. - Корректная симуляция частичного пересечения объектов (partial occlusion)
В реальности у расфокусированных объектов на переднем плавно размытые границы, через которые видно объекты, находящиеся сзади. Этот эффект называется частичным пересечением, потому что задний объект только частично заблокирован передним. Эти видимые участки объекта на заднем плане мы бы не смогли увидеть, если бы мы смотрели через камеру-пинхол. Геометрическое объяснение эффекта см. на рисунке. Т.к. методы постобработки работают с изображениями, полученными на камеру-пинхол, симуляция частичного пересечения - сложная задача: цвет невидимых точек надо экстраполировать по имеющимся данным.
Частичное пересечение объектов (картинка Barsky). - Высокая производительность
Производительность фильтров, применяемых "напрямую" в пространстве изображения (имеется в виду самая простая реализация фильтра), падает с ростом радиуса размытия. Для больших радиусов процесс может длиться несколько минут. В идеале хочется, чтобы фильтр можно было применять в реальном времени, что не всегда возможно.
Линейная фильтрация (linear filtering) [Potmesil и Chakravarty]
Один из первых методов получения DoF на этапе постобработки. В зависимости от глубины точки (определяется по карте глубины) меняются параметры функции размытия (PSF). Чем больше радиус PSF, тем более низкая производительность фильтра. Фильтр можно выразить формулой:
где B - размытое изображение, psf - ядро фильтра, x и y - координаты в выходном изображении, S - исходное изображение, i и j - координаты во входном изображении.
PSF может в некотором смысле учитывать оптические эффекты, такие как дифракцию и интерференцию. Недостатки метода: нехватка интенсивности, ненепрерывная глубина.
Буфер распределения лучей (ray distribution buffer) [Shinya]
В методе предлагается учитывать видимость объектов, тем самым мы можем избавиться от нехватки интенсивности. Вместо создания размытого изображения, сначала для каждой точки создаётся буфер распределения лучей, исходящих из неё. В такой буфер входят возможные координаты, в какие может прийти свет от точки, с глубиной. После просчёта буферов распределения лучей для всех точек вычисляется среднее значение цвета. Метод работает с видимостью объектов достаточно корректно, но требует больше памяти и вычислений, в сравнении с линейной фильтрацией. Заметим, что набор карт, полученных методом RDB, называется световым полем (light field).Послойная глубина резкости (layered DoF) [Scofield]
Метод предназначен для частного случая расположения объектов: объекты должны быть параллельны картинной плоскости. Объекты делятся на слои, слои размывается по отдельности в частотном домене (используя быстрое преобразование Фурье). FFT позволяет использовать PSF больших радиусов без влияния на производительность. Метод не имеет недостатка нехватки интенсивности и работает очень быстро, но область его применения сильно ограничена.Пересечение и дискретизация (occlusion and discretization) [Barsky]
Ограничение, накладываемое предыдущим методом, очень строгое. Изображение делится на слои, таким образом глубина семплов изображения округляется до выбранной глубины ближайшего слоя. Полученное изображение будет иметь артефакты дискретизации в форме полос или жёстких границ по линиям пересечения слоёв. В данном методе проблема таких артефактов решается при помощи использования ID объектов, полученных методом нахождения границ (или по карте ObjectId). Если один объект принадлежит двум слоям, слои объединяются. Ещё одна проблема метода - частичное пересечение. Для размытия объектов на заднем плане используется аппроксимация по видимым семплам.
На верхнем изображении видны чёрные полосы - артефакты, происходящие от применения послойного размытия без использования ObjectId (картинка Barsky).
Размытие, учитывающее особенности глаза человека (vision-realistic rendering) [Kolb]
Глаз человека сложно описать в виде аналитической модели, состоящей из нескольких линз - как это можно сделать для объектива. В данном методе при помощи специального прибора, называемого wavefront aberrometer (я не решился это перевести) определяется набор PSF, соответствующих глазу человека. Далее используется размытие по слоям в соответствии с полученными PSF. Метод позволяет получать изображения, видимые людьми с заболеваниями зрения.
Изображение, учитывающее особенности глаза человека, больного кератоконусом (картинка Barsky).
Упорядочение по важности (importance ordering) [Fearing]
Метод работает аналогично механизму antialiasing-а рендереров: сначала формируется изображение с низким разрешением, после чего семплы, рядом с которыми изменение цвета превышает порог, обрабатываются на следующей итерации и для получения пикселя итогового изображения берётся больше семплов исходного изображения, и так далее. Таким образом, метод достигает лучшего качества за меньшее время.Гибридный перцептивный метод (perceptual hybrid method) [Mulder и van Lier]
Особенности восприятия изображения человеком таковы, что детали в центре более важны, чем детали по краям изображения. Центр изображения можно размыть более медленным и точным способом, в то время как для периферии используется быстрая аппроксимация размытия. Для быстрого размытия используется пирамида Гаусса, уровень размытия выбирается в зависимости от глубины пикселя; результат обладает артефактами.Повторяемая свёртка (repeated convolution) [Rokita]
Метод предназначен для быстрого применения в интерактивных приложениях. Работает на аппаратных устройствах, где можно эффективно реализовать операцию свёртки с ядром размера 3x3 пикселя. Свёртка выполняется несколько раз, тем самым достигается большая величина размытия. Производительность падает с ростом радиуса размытия. На PSF накладывается ограничение: она должна быть Гауссовской.Глубина резкости на GPU [Scheueremann and Tatarchuk]
Глубину резкости можно считать и на GPU. Один из методов преложили Scheueremann и Tatarchuk.Учитывая глубину пикселя, по законам оптики определяем величину пятна рассеяния, и в пределах пятна выбираем семплы, которые и формируют цвет пикселя в результате. В целях оптимизации памяти, в участках изображения, где CoC имеет большой радиус, берутся пиксели не входного изображения, а уменьшенного в несколько раз. Для уменьшения количества артефактов нехватки интенсивности, в расчёт берётся ещё и глубина пикселей. Метод обладает артефактам ненепрервыности глубины.
Интегральная матрица (summed area table) [Hensley]
В качестве альтернативы семплирования в пределах CoC, усреднённый цвет области пикселей изображения можно найти, используя интегральную матрицу (SAT). В данном случае скорость вычислений высока и не падает с увеличением радиуса размытия, к тому же нет необходимости в генерации изображения меньшего разрешения. Изначально метод предназначался для сглаживания текстур, но в дальнейшем был адаптирован и для глубины резкости, в том числе и на GPU. Метод обладает практически всеми видами артефактов.Метод пирамид (pyramidal method) [Kraus и Strengert]
Сцена разделяется на слои, в зависимости от глубины. Пиксели, находящиеся близко к границе слоёв, относятся не к ближайшему слою, а частично к нескольким слоям: таким образом исключаются артефакты дискретизации на границах слоёв. Затем экстраполируются значения пикселей, отсутствующих в слоях (тех, которые закрыты объектами на переднем плане). После этого каждый слой размывается методом пирамид, для исключения артефактов используется вес точки. Полученные слои смешиваются с учётом прозрачности слоёв. Метод быстрее послойных методов, использующих FFT, но накладывает ограничения на используемую PSF.
Изображение было размыто с использованием метода пирамид (картинка Magnus Strengert).
Сепарабельное размытие (separable blur) [Zhou]
Точно так же, как и в методах классического размытия, не учитывающего глубину (box blur, gaussian blur), в расчёте глубины резкости можно применять сепарабельные PSF. Сначала изображение размывается по горизонтали, затем по вертикали - в результате мы получаем скорость, зависимую не от площади пятна не резкости, а от его диаметра. Метод поддаётся реализации на GPU и может быть применён в реальном времени. Идея применения сепарабельных функций проиллюстрирована на рисунке:
При сепарабельном размытии производительность зависит не от площади PSF, а от её диаметра.
Стоит заметить, что в другой работе Barsky подчёркивает, что правильное размытие, учитывающее глубину, не может быть сепарабельным: при использовании этого метода в некоторых случаях возможны артефакты.
Симуляция рассеяния тепла (simulated heat diffusion) [Barsky, Kosloff, Bertalmio, Kass]
Рассеяние тепла - физический процесс, в котором тоже можно наблюдать размытие (хотя он и не связан с оптикой). Если в веществе-проводнике тепла температура распределена неравномерно, со временем мы будем наблюдать размытие. Дифференциальные уравнения, описывающие эффект такого размытия, можно использовать для симуляции глубины резкости. Даже для достаточно больших радиусов размытия метод может быть применён на GPU в реальном времени.
Карта position map, используемая вместо карты глубины в этом методе, содержит информацию о трёх измерениях точки, а не только о глубине (картинка Barsky).
Обобщённая и семантическая глубина резкости
До сих пор мы описывали методы, симулирующие глубину резкости так, как это происходит в природе. Однако размытие может быть и не таким, как мы привыкли его наблюдать. В компьютерной графике мы не ограничены физически реализуемыми моделями линз, поэтому область размытия может быть задана произвольно - например, мы можем выделить из толпы несколько человек. Метод можно реализовать как вариацию метода симуляции рассеяния тепла, используя в качестве карты размытия законы, отличные от физических.
Физически неправильное размытие (картинка Kosloff и Barsky)
Световые поля (light fields)
Световые поля изначально были описаны как метод, описывающий изображение сцены с разных точек, не зависящий от сложности сцены. Стандартный способ кодирования световых полей - двухплоскостная параметризация (two-plane parametrization). Выбираются две параллельные плоскости; каждый луч описывается точкой на обеих плоскостях. В результате получается четырёхмерная структура данных. С полученными данными можно производить манипуляции, такие как изменение плоскости фокусировки или глубины резкости.Можно сказать, что в камерах световое поле (между плоскостями линзы и матрицы) интегрируется естественным путём: мы не различаем, из какой точки линзы пришёл луч света. Однако если учитывать это, мы сможем интерактивно, имея описанную структуру данных, управлять глубиной резкости уже после снятия показаний сенсора.
Кроме того, мы можем сфокусироваться на разных участках изображения, применяя быстрое преобразование Фурье в четырёхмерном пространстве.
В изображениях, генерируемых на компьютере, легко получить данные светового поля, отрендерив сцену с разных ракурсов.
Существуют камеры (физические), способные записывать световые поля. Перед сенсором располагаются микролинзы, разделяющие свет, пришедший из разных направлений. Таким образом, в отличие от классической камеры, свет не суммируется в одной точке, а распределяется в зависимости от направления. По данным сенсора уже на этапе обработки можно выбрать объект в фокусе и размер размытия.
Световое поле: маленькая часть RAW-изображения с сенсора Lytro. Мы видим микролизны, расположенные перед матрицей.
Пятнистия (dappled) фотография
Способ, описанный выше, требует много точек матрицы для кодирования одного пикселя, следовательно, обладает низким разрешением. Действительно, разрешение этой камеры где-то 800 пикселей по большей стороне при матрице 11MPix. Проблема может быть решена использованием сенсоров с очень высоким разрешением (но это приведёт к удорожанию сенсоров и запредельно большому размеру структуры данных).Пятнистая фотография предлагает альтернативный способ получения светового поля, обходящий ограничение на размер матрицы. Вместо большого числа микролинз используется полупрозрачная маска, изменяющая свет по определённому закону. Применяя обратное преобразование Фурье, можно получить исходное световое поле.
Увеличение расфокусировки (defocus magnification)
Хорошо было бы уметь применять эффект глубины резкости и в "обычной" фотографии, без светового поля (где, в отличие от рендера, нет карты глубины). Данный метод предполагает определение размытия и его увеличение (в методе предполагается, что размытие в фотографии уже есть, но недостаточное - например, фотография сделана на мыльницу, где из-за размера матрицы невозможно достичь большого радиуса размытия). Чем больше размытие, уже присутствующее в изображении, тем ещё большее размытие будет применено дополнительно.Автофокус
При использовании глубины резкости в приложениях виртуальной реальности и видеоиграх, так же как и в фотографии, необходим автофокус, то есть задача определения глубины, пиксели на которой находятся в фокусе. В центре изображения выделяется область, семплы из этой области участвуют в определении глубины фокусировки. В расчёт берётся как средневзвешенное значение глубины, так и известная для изображаемых объектов присущая им важность (скажем, можно сфокусировать "взгляд" на одном их персонажей, но нельзя на деревянном ящике или стене) - это называется семантический вес объекта. Также необходимо учитывать процесс аккомодации взгляда (фокусировка меняется во времени плавно), для этого используется, например, low-pass фильтр.Заключение
Мы рассмотрели большинство из наиболее распространённых методов, применяемых для достижения эффекта глубины резкости в современной компьютерной графике. Некоторые из них работают с 3D-объектами, некоторые являются методами постобработки. Мы также описали основные характеристики, которым должны удовлетворять правильные методы.В настоящее время проблема эффективного достижения фотореалистичной глубины резкости до сих пор открыта. Кроме того, открыта и проблема воссоздания карты глубины по фотографии (определения расстояния до объекта).
Ссылки
От переводчика
Эту и остальные работы Brian A. Barsky (университет Беркли) можно почитать на его сайте. Везде, где встречаются какие-то термины и общеизвестные названия алгоритмов, я оставил их в скобках на английском, фамилии не переводил. Если где-то неправильно перевёл - пишите в личку, поправлю (я изучал всю терминологию на английском, поэтому могу ошибаться с переводом). В [квадратных скобках] после названий методов указаны имена работавших над ними. Ради наглядности и интереса я дополнил публикацию примерами и некоторыми картинками.Ссылки по теме