скачать книгу бесплатно
Построение графика такой функции во многом схоже с построением функции, заданной явно. Более того, явное задание функции может быть сведено к параметрическому, а именно:
y = f (x) => X=t, Y=f (t)
Обратное преобразование от параметрического к явному не всегда возможно. В целом, как уже было сказано, построение графика такой функции не несет в себе принципиально иного подхода. Немного изменятся лишь функции конвертации значений из обычной системы в экранную.
Как видим в формуле для X (преобразование по оси Y не претерпело изменений), величины A и B заменены на Xmin и Xmax соответственно.
Выбор N
График может занимать маленькую часть на экране монитора или весь экран, но в любом случае мы хотим чтобы он был гладким и приятным для восприятия. Возникает вопрос: сколько требуется точек, чтобы график выглядел хорошо? Вообще число точек должно быть пропорционально длине графика. Исходя из этого, можно предложить следующий метод. Изначально мы берем довольно много точек в обычной системе координат, например, 10000. Далее конвертируем эти точки в экранную систему, а затем формируем новую коллекцию точек по следующему алгоритму – добавляем первую точку, а следующую точку добавляем с условием, что она отстает от предыдущей не менее, чем на 4 (например) пикселя. Получившуюся коллекцию соединяем линией. При таком подходе мы обеспечиваем приемлемый вид графика вне зависимости от того, сколько места он занимает на экране.
Оптимизация построения
Следуя вышеизложенному алгоритму, можно построить график, где точки, по которым мы его строим, следуют друг за другом с равномерным шагом. Однако часто такой подход не является оптимальным с точки зрения производительности. Например, известно, что в окрестности нуля функции y=sin (x) и y=x ведут себя почти одинаково. То есть синус очень похож на прямую, а прямую можно построить всего по двум точкам. Идея оптимизации состоит в том, чтобы там, где график близок к прямой, можно удалить лишние точки без потери качества. Далее мы разберем простой алгоритм, который на основе кривизны графика сможет уменьшать количество точек для построения.
Пусть точки p1 и p2 уже принадлежат списку точек, по которым строится график в экранной системе координат. Точку p3 включаем в этот список, только если ее отклонение от прямой, задаваемой точками p1 и p2, больше некоторой величины d.
рис. 1.7
Определить расстояние от точки p3 (x3, y3) до прямой определяемой точками p1 (x1, y1) и p2 (x2, y2) можно по следующей формуле:
Такая простая модификация алгоритма построения позволяет уменьшить количество точек без потери качества отображения. Мы используем участки графика, где он близок к прямой, и на этих участках удаляем избыточные для построения точки.
На рисунке 1.8 мы видим график, построенный с равномерным шагом (без оптимизации).
рис. 1.8
Число точек здесь равно 134. Сами точки отмечены квадратиками. Ниже представлен график той же функции, но к которому была применена вышеописанная процедура. График нисколько не потерял в качестве, а между тем число точек сократилось до 47.
рис. 1.9
Построение разрывных функций
Формулы, конвертирующие координаты точки из обычной системы координат в компьютерную, содержат минимальное и максимальное значения, которые достигает функция на отрезке. Для непрерывных функций эти величины обязательно существуют. Для разрывных функций это выполняется не всегда. По причине того, что минимум и максимум для разрывных функций могут не достигаться, использовать формулы, приведенные выше, нельзя.
Существует несколько типов разрывов функций. В данном разделе мы рассмотрим вариант построения графика разрывной функции с разрывом типа «скачок через бесконечность». Такой разрыв называется разрывом второго рода. Например, функция y=1/x на отрезке [-1, 1] как раз претерпевает такой разрыв в точке 0.
Чтобы научиться строить графики функций, имеющих разрыв, давайте попробуем понять поведение функции в окрестности точки разрыва. Как видно из рисунка ниже, при приближении к точке разрыва начинается быстрый рост приращения функции, при этом шаг по X остается фиксированным:
y
– y
<y
– y
<y
– y
<y
– y
и т. д.
Такое поведение функции указывает на то, что мы предположительно подошли к точке разрыва.
рис. 1.10
Необходимо вырезать из области определения точки разрыва вместе с некоторой окрестностью. После этого график функции распадается на две или более непрерывных кривых, заданных на участках, где точки разрыва отсутствуют. На каждом таком участке максимум и минимум будут достигнуты. Затем среди этих максимумов и минимумов нужно найти самое большое и самое маленькое значение и использовать их в качестве Ymax и Ymin, которые присутствуют в формуле для конвертации. Таким образом, мы снова сможем использовать формулы для конвертации точек из обычной системы в компьютерную.
Быстрый рост приращения функции в окрестности точки разрыва типа «скачок через бесконечность» является необходимым условием разрыва, но не достаточным. Можно привести пример функции, когда значение приращения будет сколь угодно велико, но тем не менее функция может оставаться непрерывной. Данный подход построения разрывного графика не является универсальным и подходит только для некоторых функций. Наиболее правильным было бы проанализировать аналитическое уравнение функции и найти, например, точки, где знаменатель обращается в ноль. Такие точки всегда являются точками разрыва, но не всегда относятся к типу «скачок через бесконечность».
Интерполяция
Иногда нам известны лишь значения функции в некоторых точках. При этом аналитическое выражение функции неизвестно, получить его крайне трудно или вообще невозможно. Задача интерполяции ставится как задача восстановления значений функции внутри области определения. Основная идея здесь состоит в том, чтобы имея конечный набор значений, построить по нему аналитическое выражение таким образом, чтобы оно выдавало значения близкие к уже имеющимся.
Делать это можно разными способами. В данной части урока мы рассмотрим два способа интерполяции – многочлен Лагранжа и линейный тренд.
Многочлен Лагранжа
Пусть имеется набор из N-значений функции (Xi, Yi), i=1… N. При этом сама функция нам неизвестна. Обладая этим набором мы хотели бы вычислять значение функции при любом значении X. Будем искать аналитическое выражение для искомой функции в виде многочлена степени N-1.
Подставив значение каждой точки (Xi, Yi) в эту формулу, мы получим систему из N-уравнений относительно коэффициентов многочлена. Можно доказать, что если все Xi различны между собой, данная система всегда имеет единственное решение. Всегда существует многочлен, проходящий через каждую заданную точку. Получившуюся формулу можно использовать для вычислений значений в промежуточных точках. Недостатком этого подхода является то, что нужно решать линейную систему и если точек много, это может потребовать значительных вычислительных ресурсов.
Французский математик Жозеф Луи Лагранж (1736—1813 г.г.) предложил следующую формулу для интерполяционного полинома:
Используя данную формулу, мы можем вычислять значение многочлена, проходящего через заданный набор точек, не зная самих коэффициентов многочлена!
Пример: Пусть даны следующий три точки (1, 1), (4, 2), (8, 5). Тогда, согласно формуле Лагранжа, значения многочлена, проходящего через эти точки, можно вычислять по формуле:
Линейный тренд
В случае интерполяции набора точек многочленом мы получаем аналитическое выражение, с помощью которого можно получать значения в промежуточных точках, причем в самих исходных точках у нас будет полное совпадение. Иногда исходные значения меняются по некоторому линейному закону, но в силу погрешностей измерений и влияния других вероятностных факторов, они не лежат на одной прямой. Можно сказать, что данные линейны, но в них присутствует некоторый «шум». В этом случае нет смысла добиваться точного совпадения значений интерполяционной формулы и исходных данных. Гораздо важнее уловить сам линейный закон. Эту задачу решает линейный тренд. Не стремясь пройти через какую-либо исходную точку, линейный тренд стремится соответствовать самому закону, по которому эти точки получены.
Пусть имеется набор из N-точек (Xi, Yi), i=1..N. Будем искать интерполяционную формулу в виде y=a?x+b. При этом потребуем, чтобы сумма квадратов разностей между исходным значением и аппроксимированным была минимальна.
рис. 1.11
Имея набор исходных точек, нам нужно найти неизвестные коэффициенты a и b. Запишем условие о минимальности суммы квадратов между исходными значениями и аппроксимированными в виде:
Получение a и b незатруднительно само по себе, но требует некоторых знаний из дифференциального исчисления. Опуская некоторые выкладки, можно показать, что a и b являются решениями следующей системы линейных уравнений:
где
Данный метод построения линейного тренда по заданному набору точек носит название метода наименьших квадратов. Этот метод можно использовать не только для того, чтобы вычислять значение в промежуточных точках (задача интерполяции), но и за пределами минимального и максимального значений по X (задача экстраполяции). Метод наименьших квадратов позволяет предсказывать новое значение y по x, имея исходный набор точек. Этот метод также лежит в основе линейных моделей машинного обучения.
Заключение
На этом наш первый урок завершен. Рекомендуем ознакомиться с дополнительными материалы, которые можно скачать по ссылке https://gitverse.ru/dmitrypavlov74/DMBook. В папке L1 вы найдете два проекта: первый Chart2D посвящен построению графиков, второй Interpolation2D – интерполяционным методам.
Урок 2. 3D моделирование
Цифровые модели в пространстве
Введение
Создание компьютерных игр и CAD-систем невозможно без глубокого понимания того, как устроены трехмерные цифровые модели, как они создаются, трансформируются и освещаются. Все это (создание, трансформирование и освещение трехмерных объектов) мы подробно разберем в этом уроке. Также мы научимся строить поверхности, накладывать текстуры на объекты, рисовать тени и моделировать туман.
3D-моделирование
Цифровое 3D-моделирование – это процесс создания трехмерного представления объекта путем манипулирования ребрами и вершинами в моделируемом трехмерном пространстве. Вы наверняка видели результаты трехмерного моделирования в фильмах, анимациях и видеоиграх, которые наполнены фантастическими существами и структурами.
3D-моделирование используется в самых разных областях, включая инженерию, архитектуру, развлечения, кино, спецэффекты, разработку игр и коммерческую рекламу.
Сама тема 3D-моделирования необычайно интересна и очень востребована в современном мире. В IT-индустрии существует даже профессия 3D-дизайнера (например, 2D-дизайнеров не существует). Справедливости ради нужно отметить, что к разработчику 3D-систем предъявляются повышенные требования в области математики. Наш второй урок направлен как раз на то, чтобы читатель научился понимать основные этапы, связанные с работой в 3D-моделировании. Хочется сразу успокоить читателя: в математическом аппарате, необходимом для работы с 3D-моделями, нет ничего сложного, хотя знаний здесь понадобится больше, чем при построении графиков.
Преобразование точек в трехмерном пространстве
Поскольку трехмерные модели так или иначе задаются набором точек, чтобы изменять положение и размер объекта в пространстве, достаточно уметь изменять положение точки. Мы рассмотрим следующую группу преобразований: поворот, масштабирование и параллельный перенос. Именно к этим трем действиям и сводится трансформация трехмерной модели. Существует унифицированный подход к этим преобразованиям, а именно все эти операции можно свести к умножению матрицы на вектор. Для преобразования точек в трехмерном пространстве используются матрицы порядка 4x4.
рис. 2.1
Вращение
Далее для каждого преобразования укажем матрицу, которая ему соответствует. Сначала рассмотрим матрицы, которые соответствуют вращению.
Поворот вокруг оси Х:
Поворот вокруг оси Y:
Поворот вокруг оси Z:
? – угол поворота, заданный в радианах. Поворот осуществляется против часовой стрелки, если смотреть навстречу оси.
Мы рассмотрели матрицы поворота точки вокруг координатных осей. Также на практике может потребоваться повернуть точку вокруг произвольной оси. Пусть ось вращения задана единичным вектором v (x, y, z). Тогда матрица поворота вокруг этого вектора имеет вид:
Масштабирование
Матрица масштабирования (изменения размеров объекта с сохранением подобия) имеет вид:
Где с – это коэффициент масштабирования. Если коэффициент с> 1, то точка удаляется от начала координат, если 0 <с <1, то приближается. Если же с <0, то происходит зеркальное отражение точки относительно начала координат. С помощью масштабирования можно управлять размером модели, увеличивая или уменьшая его.
Параллельный перенос
Матрица, соответствующая параллельному переносу точки на вектор с координатами (a, b, c), имеет вид:
Для вращения и масштабирования можно было бы использовать матрицы порядка 3x3, но параллельный перенос уже не может быть описан как матричное преобразование в пространстве этой размерности – для этого требуются матрицы размерности на единицу больше. Использование матриц 4x4, прежде всего, дает нам возможность унифицировать подход к преобразованиям в пространстве – все трансформации модели всегда сводятся к умножению матрицы на вектор. Сами по себе матричные преобразования просты и во многих прикладных библиотеках хорошо оптимизированы. Чтобы иметь возможность умножать матрицу 4x4 на трехмерный вектор, к вектору добавляют формальную четвертую координату w, равную 1: (x, y, z) -> (x, y, z, 1).
Поскольку наши рассуждения привязаны к конкретному языку программирования, то отметим, что в среде NET уже реализован необходимый функционал для работы с объектами в трехмерном пространстве. В частности, пространство имен System.Numerics содержит матрицы и векторы различных размерностей, а также разнообразные методы для работы с ними. Листинг ниже демонстрирует поворот точки с координатами (1, 0, 2) на угол в 90 градусов. В результате мы получаем точку с координатами (1, -2, 0).
Перспективные преобразования
Перспективные преобразования обеспечивают отображение пространственных моделей на какой-либо поверхности в соответствии с теми, кажущимися сокращениями их размеров, изменениями очертаний и форм, которые наблюдаются в природе. Использование перспективных преобразований делает отображение моделей на экране более реалистичным. Близкие объекты кажутся большими, а далекие маленькими, дорога сужается к горизонту и т. п (рис. 2.2).
рис. 2.2
Смысл перспективных преобразований представлен на рисунках ниже. Пусть нам необходимо отобразить на экране треугольник ABC. Если проекция не используется (рис. 2.3), то берутся обычные ортогональные проекции точек этого треугольника на плоскость проектирования (как правило, это плоскость Z=0),
рис. 2.3
При использовании проекции (рис. 2.4), образ точки на плоскость проектирования получается как точка пересечения луча, выходящего из центра проекции, проходящего через исходную точку и плоскости проекции.
рис. 2.4
Если мы отображаем точку (x, y, z) без использования проективных преобразований, то, по сути, мы просто игнорируем третью координату. При использовании перспективы координата z будет влиять на координаты x и y.
Существует несколько типов проекций. Рассмотрим одноточечную проекцию как пример наиболее простого перспективного преобразования. Нашей задачей будет вычислить новые координаты точки для отображения с учетом перспективы. Для примера рассмотрим плоскость XOZ и вычислим координату X с учетом перспективного преобразования.
рис. 2.5
Воспользовавшись подобием треугольников (Z
, Pr
, 0) и (Z
, P, P
) и выразив значение для Pr
получаем:
Аналогичные рассуждения можно провести и в плоскости YOZ. Таким образом, если центр проекции находится в точке (0, 0, -Zc), то новые координаты точки с учетом перспективного преобразования можно вычислить по формуле ниже.
x’, y’ – координаты точки с учетом перспективы; x, y, z – исходные координаты точки.
При одноточечной проекции учитывается только Z-координата. При удалении точки по оси Z от центра проекции его координаты по X и Y будут стремиться к нулю.
Перспективные преобразования, в отличии от, например, вращения и масштабирования, являются мнимыми, они не влияют на форму и положение предметов, а являются лишь кажущимися. Это означает, например, что если к 3D-модели перед отображением были применены перспективные преобразования, то после отображения они должны быть отменены.
Посмотрите, как выглядит цифровая модель куба в приложении Advanced3DModels (см. дополнительные материалы) с применением одноточечной проекции:
рис. 2.6
Полигональные модели
