Отсечение невидимых граней при построении объемных объектов в "Живой математике"

Здравствуйте, уважаемые мои читатели! Хочу поделиться с вами тем, чему научилась сама, а именно - как добиться, чтобы при построении объемных моделей в "Живой математике" (или "Живой геометрии", как ее еще называют), грани, которые экранируются объектом, не прорисовывались бы. То есть, если модель повернута  гранью к нам, то видно было бы элементы, принадлежащие этой грани (отрезки и точки), но при повороте объекта и экранировании самим объектом этой грани (то есть грань - позади) - эти отрезки и точки исчезали бы.

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

Алгоритм, о котором я хочу рассказать, называется алгоритмом Робертса. Хочу сразу заметить, что в машинной графике я - чайник, не моя это область. Просто удалось разобрать простейшую задачу, которая изначально не была для меня простейшей, и для ее решения потребовалась неделя. Поэтому решила сберечь неделю времени для вас. Специалистам - на форумы 3D - программистов, здесь - объяснение для обычных людей, простым языком, для таких же "чайников", как я.

Алгоритм создания невидимости основан на следующем: представим себе объект и наблюдателя, который на него смотрит из какой-то точки пространства, находящейся, разумеется, вне этого объекта. Нужно оговорить, что объект должен быть "выпуклым", то есть плоскости, которым принадлежат грани, не должны разрезать объект. В этом случае алгоритм работает хорошо, в противном случае необходимо применять дополнительные условия или другие способы отсечения. Основан алгоритм на следующем факте: если между нормалью к грани объекта и линией наблюдения угол острый, то грань видна, а если тупой - то нет. На рисунках представлена зеленым линия наблюдения, красным - нормали, которые составляют острый угол с линией наблюдения, а фиолетовые нормали на соседнем рисунке составляют тупой угол с линией наблюдателя, поэтому эти грани - не видно. У острых углов, как известно, косинус положительный, а у тупых - отрицательный. Поэтому основывать и расчет, и построение будем именно на этом факте.

Итак, делать будем следующее: рассчитаем вектора нормалей ко всем граням. Нормалей к плоскости всегда две, нам нужна та, что глядит "наружу", из объекта, а не "внутрь". Зададимся линией наблюдения, и определим знак косинуса угла между нормалями и линией наблюдения. На основании этих сведений сформируем коэффициенты видимости-невидимости, и создадим гомотетии вершин объекта с указанными коэффициентами. Эти точки существуют только при определенном положении объекта, и, если их соединить отрезками, то отрезки будут исчезать при исчезновении соответствующих точек, и появляться обратно при повороте объекта и появлении данных гомотетий.

Ну а теперь - к делу. Расписываю все подробно, так, как мне хотелось бы, чтобы объяснили мне, когда я только начала вникать в эту проблему.

1. Определяем количество граней объекта. Для правильной пирамиды их 4, для параллелепипеда - 6.

2. Рассчитываем нормали к граням (по количеству граней, понятно). Это будут нормали, определенные в  вершине многоугольника, а найдем мы их путем расчета векторного произведения прилежащих ребер. Здесь важно не ошибиться с направлением нормали, как ранее сказано, она должна обязательно смотреть "наружу", из объекта. Как же этого достичь? Тут поможет правило буравчика, известное в физике и электротехнике (для тех, кто его помнит), или следующие способы:

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

Правило правой руки для векторного произведения:

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

Иначе говоря, нужно охватить наш объект ладонью так, чтобы грань, к которой строится нормаль, была бы сверху. Тогда один из векторов будет параллелен указательному пальцу, а второй - большому. Например:

Тогда векторное произведение векторов будет записано так:

Это и есть искомая нормаль. В этой записи:

Здесь  - единичные вектора выбранного базиса.

То есть, нам понадобятся координаты трех вершин этой грани по осям  и  -

, а значит, нужно их определить.

Если мы выполняем расчет для параллелепипеда, то придется рассчитать последние суммы (ну или разности) для каждой грани  - то есть 6 раз. Проделав это, будем иметь 6 нормалей.

3. Теперь подошло время для выбора места для нас с вами, как наблюдателей - то есть точки наблюдения. Вот тут у меня возникли трудности. В одних источниках рекомендуется точка, располагающаяся на оси , причем то на положительной полуоси, то - на отрицательной. А другие рекомендуют точку с координатами (1, 1, 1). Эта точка мне кажется более правильной, если мы хотим видеть три грани параллелепипеда одновременно. Итак, выбираем точку (1, 1, 1). Вектор, изображающий это направление - тоже (1, 1, 1).

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

- здесь в числителе не просто произведение, а скалярное произведение векторов.

Или:

Как видно, в знаменателе - заведомо положительное число, поэтому считать его вообще не нужно, на знак оно не повлияет.

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

. Если знак положительный - грань видна, если отрицательный - грань не видна. Введем величину: , тогда эта величина равна 1, когда грань видна, а если не видна, то для такой грани  . В этих формулах: sgn - операция определения знака. Возвращает 1, если знак положителен, и (-1) - если знак отрицателен.

5. Ну вот, мы уже приближаемся к сути - то есть к вычислению коэффициентов видимости - невидимости ребер. Первый вопрос - а сколько их должно быть, этих коэффициентов? Ответ такой: их число равно удвоенному числу ребер. Тогда для параллелепипеда это , а для тетраэдра -  , для правильной призмы с пятиугольником в основании - 30, с шестиугольником в основании - 36 и т.д. Половина из них - коэффициенты видимости, вторая половина - коэффициенты невидимости. Коэффициент видимости может быть равен 1(тогда элемент видно), или неопределен (тогда не видно), и аналогично коэффициент невидимости - может быть равен 1 или не определен. Зачем, спросите вы, нам тогда нужны и коэффициенты видимости, и невидимости? Пусть просто исчезает невидимое, и все! Но нам-то нужно, чтобы невидимое прорисовывалось бы, но только тоненько, пунктиром... А чтобы существовал отрезок, даже тоненький - нужно, чтобы существовали его предки - точки. Иными словами, если грань лицевая (видимая в данный момент), то все вершины существуют, и отрезки (ребра) между ними - тоже, и нарисованы они жирно. Но стоит нам повернуть объект так, чтобы эта грань стала нелицевой, задней - и точки-вершины должны исчезнуть, но вместо них появляются другие точки (в тех же местах!), и отрезок, их соединяющий - но уже пунктирный.

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

и  невидимости:

Понятно, что, если две смежные грани невидимы, то и ребро между ними невидимо тоже. Тогда получим корень из (-1), и коэффициент видимости не определен, а коэффициент невидимости равен 1 - то, что нам и нужно. Если хотя бы одна из двух смежных граней видна - то коэффициент видимости равен 1, и ребро видно, при этом коэффициент невидимости неопределен.

6. Теперь, собственно, надо приступать к рисованию ребер. Ребро - отрезок, соединяющий точки - вершины. У нас, если объект уже построен, то вершины он уже имеет. Но нам-то понадобятся другие точки для наших то видимых, то невидимых ребер. Давайте обходить объект в каком-то одном направлении, например, против часовой стрелки. Начинаем с точки А. Отмечаем точку D как центр гомотетии, и в вершине А создаем новую точку с коэффициентом гомотетии invisible - A'. Соединяем D и А' тонким отрезком, или пунктиром. Потом создаем вторую гомотетию точки А, но уже с коэффициентом visible - А", и эту точку соединим с точкой D толстым, лицевым, отрезком. Только смотрите внимательно, какие точки вы соединяете. Если несколько точек находятся в одном месте, надо пощелкать мышью, чтобы выбрать нужную точку. Так, обходя верхнее основание объекта, проводим тонкий и толстый отрезки для всех ребер. Аналогично делаем для нижнего основания, а затем и для боковых ребер. И ура - все получилось!

Предлагаю посмотреть построение в видеоуроке: