Цифровое моделирование на C#

Посвящается моей семье: моей жене Наталье, моим сыновьям Тимофею, Павлу и дочери Любови.

Моделирование – это процесс замены реального объекта его двойником с целью последующего изучения. Можно ли изучать непосредственно сам объект? Иногда можно, но даже в этих случаях мы часто, сами того не подозревая, переходим от объекта к модели. Например, перед нами стоит задача вычислить площадь стола. Для решения задачи мы подменяем стол его моделью – прямоугольником. А как вычислить площадь прямоугольника, мы хорошо знаем еще из школьного курса геометрии. В этом примере реальный объект – стол, мы заменили его абстрактной моделью – прямоугольником. Прямоугольник, как и стол, обладает свойствами, которые необходимы для решения нашей задачи: шириной и длиной. То есть модель всегда в некотором смысле похожа на реальный объект. Она должна обладать теми свойствами объекта, которые мы собираемся изучать или использовать.

С другой стороны, если мы захотим узнать, насколько прочен наш стол, наша модель (прямоугольник) становится бесполезной. Таким образом, модель всегда отражает лишь часть свойств реального объекта. Примеры, которые мы рассмотрели выше, конечно, очень просты. В реальных задачах выбор модели для изучения и ее создание, будь то изготовление копии на токарном станке или цифрового двойника на компьютере, может быть делом нетривиальным. И все-таки моделирование – это то, что упрощает, формализует процесс изучения окружающего мира, способствует эффективности и точности работы в различных отраслях. Благодаря моделированию можно изучать взаимодействие различных частей системы, анализировать их поведение и делать прогнозы. Моделирование помогает выявлять потенциально слабые места в системе, оптимизировать ее работу и принимать более взвешенные решения.

Благодаря всестороннему вхождению информационных технологий в нашу жизнь моделирование вышло на принципиально новый уровень. Экспоненциальное развитие вычислительных мощностей и постоянное совершенствование алгоритмов привели к возможности создания нового типа моделирования – компьютерного (цифрового). Цифровое моделирование – это процесс создания и использования виртуальных моделей для анализа, оптимизации различных систем и процессов, а также предсказания их поведения в ситуациях, связанных с реальной эксплуатацией. Цифровое моделирование позволяет создавать виртуальные модели объектов и систем, а затем использовать их для тестирования различных сценариев и принимать решения на основе полученных результатов. Цифровое моделирование дает возможность понять, как будет работать та или иная система еще до того, как эта система будет создана. С помощью этого подхода можно проводить краш-тесты автомобилей, реконструировать военные сражения, разрабатывать крыло самолета – и этот список ограничивается лишь нашей фантазией. Круг областей, где могут использоваться цифровые модели, очень широк – это медицина, биология, транспорт, логистика, строительство, финансы и т. д. Кроме практических сфер и бизнеса цифровое моделирование может использоваться в естественных науках, например, в физике, чтобы заменить дорогостоящий эксперимент виртуальным.

Необходимые знания и навыки

Читателю для понимания материала необходимо следующее:

– базовые знания математики: большая часть теоретического материала этой книги не подразумевает знаний, выходящих за рамки школьной программы, однако для понимания некоторых глав следует знать о векторах, матрицах, умножении матриц, стандартных математических функциях, производной и интеграле. Если в процессе чтения та или иная теоретическая часть будет вам непонятна в силу пробелов в знаниях, то при первом чтении ее можно пропустить без ущерба для общего понимания;

– для работы с программами, которые поставляются вместе с этой книгой, желательно иметь начальный опыт программирования на C#: необходимо уметь пользоваться средой разработки, иметь представление о типах данных в. NET, классах, интерфейсах, коллекциях; уметь использовать операторы ветвления и циклы.

Как устроена эта книга

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

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

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

Миссия

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

Дополнительные материалы

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

Книга поможет вам в создании ваших собственных проектов, поэтому вы можете использовать код из дополнительных материалов как вам угодно. Если при копировании кода вы сделаете ссылку на это издание, я буду вам очень признателен.

Программы можно скачать по ссылке:

https://gitverse.ru/dmitrypavlov74/DMBook

или воспользуйтесь QR-кодом для перехода на сайт:

По ссылке ниже (кроме исходников) вы сможете скачать и скомпилированные примеры:

https://disk.yandex.ru/d/33V3WI3A3mjyTA

Обратная связь

Написание книги – дело непростое. Даже если книга успешно продается, понять, насколько она была полезна читателю, очень сложно, поэтому я буду благодарен за любую обратную связь. Вы можете писать мне на адрес электронной почты [email protected]. Я стараюсь оперативно отвечать на поступающие вопросы. Это касается не только самой книги, но и дополнительных материалов.

Об авторе

Павлов Дмитрий является большим энтузиастом языка C#. Работал в таких компаниях, как «Danfoss», «Intel». Сейчас трудится в компании «Ридан», где курирует центр технических компетенций в области теплофизического моделирования. По образованию математик, кроме этого, получил дополнительное образование в области машинного обучения. В свободное время ведет свое сообщество в социальной сети «ВКонтакте» https://vk.ru/digitalmodelsru, где занимается популяризацией программирования и математики. В настоящее время проживает в Нижнем Новгороде.

QR-код для перехода в сообщество:

Построения на плоскости

Введение

Большую часть информации об окружающем мире человек получает от органов зрения. Часто визуальный анализ данных может быть намного эффективнее, чем разглядывание длинных колонок чисел. Рассматривая таблицу чисел (рис 1.1), не сразу удастся понять, с какими данными мы имеем дело. Но взглянув на кривую, построенную по этим данным, мы легко угадаем знакомую нам еще со школы параболу.

рис. 1.1

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

На этом уроке мы разберем одну из «вечных» задач – построение графиков функций. Мы научимся строить графики в декартовой и полярной системах координат, оптимизировать процедуру их построения; разберем особенности построения разрывных функций. Также мы узнаем, что такое интерполяция и разберем несколько ее видов.

Системы координат

Прежде, чем перейти к алгоритмам построения графиков, вкратце приведем некоторые сведения о координатных системах. В любой системе координат на плоскости точка задается парой значений (a, b). Каждая такая пара однозначно определяет место точки на плоскости. Обратное, вообще говоря, выполняется не всегда.

Декартова система координат

В декартовой системе координат, как правило, пары обозначаются (x, y), хотя это и не принципиально. Смысл значения x – это проекция точки на ось OX, y – это проекция на ось OY.

рис. 1.2

Полярная система координат

В полярной системе координат точки будем обозначать парой (r, t). Где r – это расстояние от точки О, называемой полюсом, а t – угол между горизонтальным лучом, исходящим из полюса, направленным вправо, и радиусом-вектором, указывающим на точку (рис. 1.3).

рис. 1.3

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

– в астрономических наблюдениях;

– в фотографии – используют фильтр, переводящий координаты точек из прямоугольной системы в полярную, создавая сферический эффект снимка;

– в биржевых графиках – необычный формат на основе полярных координат предложил в 1990-е годы российский математик Владимир Иванович Елисеев;

– во взаимосвязи градусов и времени (в году 365 дней, в окружности – 360 градусов);

– в медицине – компьютерная томография сердца изображается в полярной системе координат;

– в системах безопасности при идентификации по радужной оболочке глаза.

Способы задания функций

Функции, заданные следующим образом y = f (x), называются заданными явно. Здесь y явно зависит от переменной x, а f определяет некоторое правило, по которому, взяв переменную x, можно получить y. При этом переменная x называется независимой переменной, а y зависимой. Или говорят, что y является функцией x.

Например: y = 2x + sin2x.

Функция может быть задана следующим образом:

x = X (t)

y = Y (t)

Здесь x и y являются функциями независимой переменной t. Такой способ задания функций называется параметрическим. Например, следующая пара функций определяет окружность радиусом 1:

x=cos (t)

y=sin (t)

Построение графика в декартовой системе координат

Для определенности мы начнем с построения графика функции, заданной явно в декартовой системе. Сформулируем шаги, необходимые для построения:

– Получить список точек в обычной системе координат.

– Получить список точек в компьютерной системе координат, преобразовав точки из обычной системы.

– Соединить получившиеся точки линией.

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

Код достаточно простой, но поскольку мы с вами находимся в начале пути, немного комментариев к нему не будут лишними. Во-первых, в коде присутствуют границы отрезка, на котором мы собираемся строим наш график – это A и B. Во-вторых, сама функция f (x) задана локально и в нашем случае это y=x². От исходной функции требуется, чтобы она была определена при всех значениях внутри заданного отрезка. Очевидно, что наша функция этому условию удовлетворяет. Далее, N – это число точек для построения. На самом деле выбор этого значения – сама по себе весьма интересная задача. От выбора числа N зависит, как будет выглядеть наш график. Понятно, что нет смысла брать слишком много точек, поскольку разрешение экрана конечно. С другой стороны, точек не может быть мало, иначе график будет угловатым и не будет отображать истинное поведение функции. Обратите внимание на формулу для вычисления X [i]. При i=0, X [i] =A, а при i=N-1 (максимальной значение i в цикле), мы получаем X [i] =B. Поскольку формула для X [i] линейна относительно i, значит в массиве X будут лежать значения от A до B с равномерным шагом.

Согласно шагу 2, необходимо преобразовать данные из обычной системы координат в компьютерную. Экран монитора тоже представляет из себя декартову систему координат, с той лишь разницей, что ось Y здесь направлена вниз. Определим несколько величин:

[A, B] – отрезок, на котором задана исходная функция.

Ymax – максимальное значение функции на отрезке.

Ymin – минимальное значение функции на отрезке.

(X_win_min, Y_win_min) – левый верхний угол на экране монитора.

(X_win_max, Y_win_min) – правый верхний угол на экране монитора.

(X_win_min, Y_win_max) – левый нижний угол на экране монитора.

(X_win_max, Y_win_max) – правый нижний угол на экране монитора.

рис. 1.4

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

В данных формулах (X, Y) – это координаты точки в обычной системе координат, а (Xwin, Ywin) – координаты на экране монитора. Обратите внимание, что формулы не симметричны относительно осей X и Y. Как уже было упомянуто, это связано с тем, что компьютерная система координат устроена так, что ось Y направлена вниз, в то время, как в обычной системе эта ось направлена вверх. Данные формулы универсальны – используя их, можно вписать график любой функции в любой прямоугольник на экране. Тем не менее, все-таки есть очевидные ограничения на их использование. Во-первых, Ymax и Ymin должны достигаться на отрезке [A, B]. Существуют функции, которые не имеют максимума или минимума на заданном отрезке. Например, гипербола y=1/x не имеет ни того, ни другого на отрезке [-1, 1]. Ниже мы разберем как строить графики таких функций. Во-вторых, Ymax и Ymin должны быть различны, иначе в знаменателе мы получим ноль. Этот случай, впрочем, разрешается элементарно. Если у нас Ymax равен Ymin, то мы имеем дело с функцией y=const и в этом случае ее графиком будет просто горизонтальная линия.

Определим две функции, с помощью которых мы будем производить конвертацию.

Сама конвертация выглядит так, как показано на листинге ниже. В данном коде мы воспользовались функционалом, который предоставляет нам System.Linq для поиска минимального и максимального значений в массиве Y, а также для самой конвертации.

В переменных Xwin и Ywin теперь у нас лежит коллекция координат точек, которые мы соединим линией.

Построение графика в полярной системе координат

Для построения графика функции, заданной в полярной системе координат, мы сначала научимся конвертировать значения функции в декартову систему. Итак, пусть есть пара значений в полярной системе координат (r, t), давайте получим для нее соответствие в декартовой системе. Как видно из иллюстрации ниже, координата по оси OX равна произведению длины радиуса вектора r на косинус угла t, а по оси Y, соответственно, это произведение r на синус t.

рис. 1.6

Таким образом получаем: x=r⋅cos (t), y=r⋅sin (t);

Сами формулы перехода достаточно просты. А поскольку мы теперь умеем переводить полярные координаты в декартовы, то можем считать, что мы успешно свели задачу к предыдущей.

Построение графика функции, заданной параметрически

Построение графика такой функции во многом схоже с построением функции, заданной явно. Более того, явное задание функции может быть сведено к параметрическому, а именно:

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 – интерполяционным методам.

Цифровые модели в пространстве

Введение

Создание компьютерных игр и 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_c, Pr_x, 0) и (Z_c, P, P_z) и выразив значение для Pr_x, получаем:

Аналогичные рассуждения можно провести и в плоскости YOZ. Таким образом, если центр проекции находится в точке (0, 0, -Zc), то новые координаты точки с учетом перспективного преобразования можно вычислить по формуле ниже.

x’, y’ – координаты точки с учетом перспективы; x, y, z – исходные координаты точки.

При одноточечной проекции учитывается только Z-координата. При удалении точки по оси Z от центра проекции его координаты по X и Y будут стремиться к нулю.

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

Посмотрите, как выглядит цифровая модель куба в приложении Advanced3DModels (см. дополнительные материалы) с применением одноточечной проекции:

рис. 2.6

Полигональные модели

Полигональное моделирование – это разновидность трехмерного моделирования. Модель при этом задается набором точек. Если три точки заданы в качестве вершин и соединены ребрами, то они формируют треугольник (полигон), который имеет цвет или текстуру. Совокупность таких треугольников позволяет смоделировать практически любой объект. Недостаток полигонального моделирования состоит в том, что сами треугольники должны иметь очень маленький размер, иначе объект будет иметь огранённый вид. Это означает, что если для модели на сцене предполагается увеличение, ее необходимо моделировать с большим количеством полигонов, даже несмотря на то, что большинство из них будут лишними при удалении от объекта. Тем не менее, для простого моделирования такой подход считается вполне приемлемым.

Реалистичное освещение полигональных моделей

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

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

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

Прежде, чем начать изучение методов освещения, кратко коснемся самих источников света. Все источники света разделим на два типа: прожекторы и точечные источники. Прожектором называется источник света, лучи которого параллельны друг другу. Точечный источник – это источник света, который испускает световые лучи во все стороны.

рис. 2.7

Лучи-прожекторы параллельны друг другу (рис. 2.7)

рис. 2.8

Точечный источник излучает свет во все стороны (рис. 2.8)

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

рис. 2.9

Модель Фонга

Одной из наиболее часто используемых моделей освещения является модель освещения Фонга. Она состоит из трех составляющих: фоновой (ambient, англ.), диффузной (diffuse, англ.) и зеркальной (specular, англ.). Цвет в конкретной выбранной точке треугольника зависит от этих трех составляющих освещения. Далее разберем каждую составляющую в отдельности.

Фоновая составляющая

Пусть X – исходный цвет треугольника, а A – константа, лежащая между 0 и 1, которая характеризует фоновое освещение. Тогда фоновая составляющая F равна:

F = A ⋅ X

Тот факт, что константа A лежит между 0 и 1, означает, что исходное значение цвета X будет уменьшено. Вообще, значение параметра А для всех объектов, не излучающих свет самостоятельно, как то всевозможные лампочки или флуоресцентные материалы, равно 0. Значение фоновой составляющей не зависит от наличия источников света и характеризует самостоятельное свечение объекта.

Диффузная составляющая

Диффузное освещение имитирует воздействие на объект направленного источника света. Это наиболее визуально значимый компонент модели освещения. Чем меньше угол между нормалью (нормалью называется ненулевой вектор перпендикулярный плоскости треугольника) к треугольнику и вектором, направленным на источник света, тем большую яркость ему придает диффузная составляющая.

рис. 2.10

Расчет диффузной составляющей происходит согласно формуле ниже:

D = d ⋅ X ⋅ (1 + cos (α)) / 2

D – диффузная составляющая.

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

X – исходный цвет поверхности треугольника.

α – угол между вектором нормали к поверхности и вектором, исходящим из вершины треугольника и направленным на источник света.

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

Зеркальная составляющая

Зеркальная составляющая имитирует яркое пятно света (блик), которое появляется на блестящих объектах. Расчет зеркальных бликов, как и в случае диффузного освещения, основан на векторе направления источника света и нормали к поверхности объекта, но помимо этого в вычислениях учитывается позиция наблюдателя, то есть направление, в котором наблюдатель смотрит на фрагмент.

рис. 2.11

(1) – вектор, исходящий из вершины треугольника и направленный на источник света.

(2) – вектор нормали к плоскости треугольника.

(3) – отраженный от поверхности луч света.

(4) – вектор, исходящий из вершины треугольника и направленный на наблюдателя.

α – угол между вектором нормали и вектором, направленным на источник света.

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

Зеркальную составляющую освещения можно вычислить по следующей формуле:

S – зеркальная составляющая.

a – параметр, характеризующий яркость светового блика.

b – параметр, характеризующий размер светового блика на поверхности. Чем больше b, тем меньше блик.

x = 1-cos (β)

β – угол между отраженным лучом света и вектором, направленным на наблюдателя. Этот угол должен варьироваться в пределах от 0 до 90 градусов. Если угол больше, чем 90 градусов, это означает, что поверхность не освещается лучами от источника света или наблюдатель не может видеть данную поверхность. В этом случае зеркальная составляющая равна 0.

Если мы построим график функции, с помощью которой вычисляется зеркальная составляющая, то мы получим примерно такой график (рис. 2.12) (в зависимости от параметров a и b вид графика может немного меняться).

рис. 2.12

Эта функция достигает своего максимума при x=0, то есть когда отраженный луч и вектор, направленный на наблюдателя, сонаправлены. Значение самих параметров a и b полностью зависит от свойств материала поверхности. Например, для металла значение a будет больше, чем для дерева.

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

Формула Фонга

Общее значение освещенности является суммой трех составляющих освещения:

Освещенность = Фоновая + ∑ Диффузная + ∑ Зеркальная

Суммирование идет по всем источникам света, присутствующим на сцене.

Способы освещения

Мы выяснили, как вычислять цвет в произвольной точке треугольника. Но нам необходимо закрасить весь треугольник. Чтобы это сделать, существует несколько вариантов. Первый вариант самый простой (и, соответственно, самый быстрый) – нужно вычислить цвет в произвольной точке (например, в вершине) и закрасить этим цветом весь треугольник. Второй чуть сложнее – это вычислить цвет в трех вершинах треугольника, усреднить эти значения и закрасить этим усредненным значением весь треугольник. И, наконец, третий способ – вычислить цвет в трех вершинах, а для закраски внутренних точек треугольника использовать линейную интерполяцию между вершинами треугольника (метод Гуро). Этот метод позволяет устранить дискретность изменения интенсивности, также он является наиболее ресурсоемким из трех перечисленных, но именно он дает самую качественную картину из описанных выше методов.

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

Существует еще один подход к освещению как полигональных, так и других типов моделей. Если мы умеем вычислять значение цвета для произвольной точки объекта, то можно рассчитать освещенность для каждой точки модели. Это, так называемый, метод попиксельного освещения. Понятно, что он является наиболее ресурсоемким из всех. Этот метод может применяться в областях, где скорость расчета освещенности не так важна по сравнению с качеством – например, в мультипликации, где картинки подготавливаются заранее и не так важно, как долго отрисовывался конкретный кадр.

В качестве практической вставки посмотрим, как закрасить треугольник в соответствии с методом Гуро. В графической библиотеке GDI+ присутствует необходимый функционал, чтобы линейно интерполировать цвета между тремя вершинами. (см. листинг ниже)

Моделирование тумана

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

В этой части урока мы научимся моделировать присутствие тумана на сцене. Мы смоделируем туман, который равномерно скрывает объекты в направлении глубины сцены. Действие такого тумана легко объяснить следующими словами: чем ближе к нам объект, тем более четко мы его видим и тем меньшее значение оказывает туман на цвета объекта, и наоборот, чем дальше объект, тем менее четко мы его видим и тем большее значение оказывает туман (его цвет) на то, каким мы видим объект. Можно сказать, что корректирующее действие тумана является функцией расстояния от наблюдателя до объекта.

Рассмотрим формулу, с помощью которой можно вычислять цвет 3D-модели в условиях тумана:

X_F – цвет 3D-модели с учетом тумана.

F – цвет тумана (в природе, как правило, это белый цвет, но можно использовать и другие цвета).

R – расстояние от наблюдателя до объекта.

X – исходный цвет объекта, вычисленный например, по методу Фонга.

d – параметр тумана (плотность).

Как работает эта формула? Если R=0, то есть объект находится перед наблюдателем, тогда X_F равно исходному цвету объекта. Если же устремить R в бесконечность, X_F устремится к цвету тумана. Не стоит рассматривать эту формулу как некоторую каноническую и единственно правильную. Она является искусственно сконструированной и хорошо показала себя на практике (см. дополнительные материалы). В данной формуле выражение R² может быть заменено на любую другую монотонно-возрастающую функцию, зависящую от R. При этом туман будет как-то по-другому «растворять» объект.

Отображение 3D-модели

Поскольку мы определили трехмерную модель как совокупность полигонов (треугольников), то отображение модели сводится к отображению этой совокупности. Как отобразить эту совокупность чтобы модель выглядела корректно? Существует несколько подходов к решению этой задачи. Мы изложим один из наиболее простых методов. Итак, чтобы наша 3D-модель выглядела правдоподобно, нам нужно проделать следующее: необходимо отсортировать наши треугольники по оси Z в порядке удаленности от наблюдателя. В качестве Z-координаты можно взять минимум по Z для всех трех вершин. То есть отображаться треугольники должны по мере приближения к наблюдателю – от самых дальних к ближним. Этот подход называется алгоритмом художника. Он очень прост, нагляден и легко реализуем. Но он также имеет ряд недостатков. Например, алгоритм не позволяет получить корректную картину в случае взаимно перекрывающихся треугольников. В этом случае следует разбивать конфликтный треугольник на несколько меньших. Второй проблемой является то, что система прорисовывает области, которые впоследствии будут перекрыты, на что тратятся лишние вычислительные ресурсы.

Особый случай представляет из себя ситуация, когда на сцене присутствует только одна 3D-модель и она является выпуклым многогранником (например, кубом), в этом случае сортировка не требуется. Достаточно просто отобразить видимые треугольники. Однако мы пока не выясняли, как определить, видим треугольник наблюдателю или нет. Давайте сформулируем простой критерий видимости треугольника для наблюдателя: треугольник виден наблюдателю в том и только в том случае, если угол между его нормалью и вектором на наблюдателя лежит в пределах от 0 до 90 градусов (является острым). Это условие может быть сформулировано по другому – треугольник виден наблюдателю в случае, если скалярное произведение вектора нормали и вектора, направленного на наблюдателя, больше нуля. Если для определенности предположить, что вектор на наблюдателя имеет следующие координаты (0, 0, -1), то условие видимости треугольника принимает очень простой вид: треугольник виден наблюдателю тогда и только тогда, когда Z-координата его вектора нормали меньше нуля.