Как заполнить треугольник прямоугольниками (5 видео)

Прямоугольник в треугольнике

Казалось бы — самый простой случай: в треугольник вписан прямоугольник. Но почему-то нигде не приводятся общие формулы! Только частные численные задачи. Если же рассматривать задачу в общем виде, то появится нечто очень красивое и неожиданное. В основе лежит параметр А, который я бы назвал Параметром Герона. Придумать подобные компактные тождества немыслимо, а произвести расчёты по формулам — раз плюнуть.

Из выражения для длины прямоугольника L, что синей рамочке на рисунке, методом дифференциального исчисления легко находятся уже габариты прямоугольника с наибольшей площадью. Высота такого оптимального элемента Н равна половине высоты треугольника (то есть перпендикуляра, опущенного с вершины В на основание АС). Длина L равна половине основания, то есть b/2. Отсюда ясно, что площадь наибольшего треугольника, вписанного в треугольник, равна половине площади исходного треугольника АВС. Геометрически построение прямоугольника наибольшей площади элементарное: строится средняя линия треугольника (она параллельна стороне АС) и из точек пересечения с боковыми сторонами опускаются вниз перпендикуляры. Это в геометрии давно известно, но из моих формул всё чётко и наглядно выводится.

Формулы я самостоятельно получил еще в седьмом классе и они часто выручали как при решении примеров, так и в строительстве. Каждый уважающий себя интеллектуал должен содержимое рисунка твёрдо знать! Наряду с числами Марсенна, Марсела, теоремами Экобара, Менелая, Виета, распределениями Гаусса, Релея, Гумбеля, Александрова. И ещё многое из всего в математике — величайшей науке всех цивилизаций.

Содержание

Краткий курс компьютерной графики: пишем упрощённый OpenGL своими руками, статья 2 из 6
Улучшение кода
Official translation (with a bit of polishing) is available here.
Update:
Рисуем заполненный треугольник
Рисуем модель
Плоская тонировка
Прямоугольный треугольник
📸 Видео

Видео:Все про прямоугольный треугольник. Решаем задачи | Математика | TutorOnlineСкачать

Краткий курс компьютерной графики: пишем упрощённый OpenGL своими руками, статья 2 из 6

Улучшение кода

Official translation (with a bit of polishing) is available here.

Update:

Внимание, статья 4в даёт новую, более простую версию растеризатора.

Давайте знакомиться, это я.

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

В прошлый раз мы нарисовали проволочную сетку трёхмерной модели, в этот раз мы зальём полигоны. Точнее, треугольники, так как OpenGL практически любой полигон триангулирует, поэтому ни к чему разбирать сложный случай. Напоминаю, что этот цикл статей создан для самостоятельного программирования. Время, которое я здесь привожу — это не время чтения моего кода. Это время написания вашего кода с нуля. Мой код здесь только для того, чтобы сравнить ваш (рабочий) код с моим. Я совсем не являюсь хорошим программистом, поэтому ваш код может быть существенно лучше моего. Любая критика приветствуется, любым вопросам рад.

Пожалуйста, если вы следуете этому туториалу и пишете свой код, выкладывайте его на github.com/code.google.com и им подобные и давайте ссылки в комментариях! Это может хорошо помочь как и вам (другие люди могут чего посоветовать), так и будущим читателям.

Видео:Площадь треугольника. Как найти площадь треугольника?Скачать

Рисуем заполненный треугольник

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

В самом начале давайте рассмотрим вот такой псевдокод:

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

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

Почему я люблю этот код? Да потому, что, увидев такое, совсем новичок в программировании его воспримет с энтузиазмом, человек, немного знакомый с программированием, только самодовольно хмыкнет, мол, вот идиот писал. А эксперт в программировании компьютерной графики просто пожмёт плечами, мол, ну да, так оно и работает в реальной жизни. Массивно-параллельные вычисления в тысячах маленьких графических процессоров (я говорю про обычные потребительские компьютеры) творят чудеса. Но мы будем писать код под центральный процессор, поэтому этот метод использовать не будем. Да и какая разница, как оно там в кремнии, нашей абстракции вполне хватит для понимания принципа работы.

Окей, начальная заглушка будет выглядеть следующим образом:

Как обычно, на гитхабе доступен отпечаток кода. В этом коде всё просто: я даю три треугольника для начальной отладки вашего кода; если внутри функции triangle просто сделать вызов line(), то получим контур треугольника. Как нарисовать заполненный треугольник?

Хороший метод отрисовки треугольника должен обладать следующими свойствами:

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

Требований можно добавлять гораздо больше, но мы довольствуемся этими тремя.

Традиционно используется line sweeping (заметание отрезком?):

Сортируем вершины треугольника по их y-координате
Растеризуем параллельно левую и правую границы треугольника
Отрисовываем горзонтальный отрезок между левой и правой точкой границы

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

Как рисую я? Ещё раз, если у вас есть лучший метод, то я его с огромным удовольствием возьму на вооружение. Давайте предположим, что у нас есть три точки треугольника, t0,t1,t2, они отсортированы по возрастанию y-координаты.
Тогда граница А будет между t0 и t2, граница Б будет между t0 и t1, а затем между t1 и t2.

Здесь у нас граница А нарисована красным, а граница Б зелёным.

Граница Б, к сожалению, составная. Давайте отрисуем нижнюю половину треугольника, разрезав его по горизонтали в точке излома границы Б.

Заметьте, что в этот раз у меня получились разрывные отрезки. В отличие от прошлого раза (где мы рисовали прямые) я не заморочился поворотом изображения на 90°. Почему? Это оказывается не всем очевидным моментом. Просто если мы соединим горизонтальными линиями соответствующие пары точек, то пробелы пропадут:

Теперь осталось отрисовать вторую половину треугольника. Это можно сделать, добавив второй цикл:

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

Отпечаток кода для отрисовки 2d треугольников.

Видео:Геометрия 7 класс (Урок№25 - Прямоугольные треугольники.)Скачать

Рисуем модель

Мы умеем уже отрисовывать модель с пустыми треугольниками, давайте их зальём случайным цветом, это поможет нам проверить, насколько хорошо мы закодировали заполнение треугольников. Вот код.

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

Видео:Построение высоты в тупоугольном и прямоугольном треугольниках. 7 класс.Скачать

Плоская тонировка

Давайте теперь убирать эти клоунские цвета и освещать нашу модель.
Капитан Очевидность: «При одной и той же итенсивности света полигон освещён максимально ярко, если свет ему перпендикулярен».

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

Но ведь скалярное произведение может быть отрицательным, что это означает? Это означает, что свет падает позади полигона. Если модель хорошая (обычно не наша забота, а 3д моделеров), то мы просто можем этот треугольник не рисовать. Это позволяет быстро убрать часть невидимых треугольников. В англоязычной литературе называется Back-face culling.

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

Обратите внимание, внутренняя полость рта нарисовалась поверх губ. Ну а что, такое быстрое отсечение невидимых треугольников убирает всё ненужное только для выпуклых моделей. Эти огрехи мы уберём в следующий раз, закодировав z-buffer.

Видео:КАК ИЗМЕРИТЬ УГЛЫ ТРЕУГОЛЬНИКА ТРАНСПОРТИРОМ? Примеры | МАТЕМАТИКА 5 классСкачать

Прямоугольный треугольник

Прямоугольный треугольник – треугольник, в котором один угол прямой (то есть равен 90˚).

Сторона, противоположная прямому углу, называется гипотенузой прямоугольного треугольника.

Стороны, прилежащие к прямому углу, называются катетами .

Признаки равенства прямоугольных треугольников

Если катеты одного прямоугольного треугольника соответственно равны катетам другого прямоугольного треугольника, то такие треугольники равны ( по двум катетам ).

Если катет и прилежащий к нему острый угол одного прямоугольного треугольника соответственно равны катету и прилежащему к нему острому углу другого прямоугольного треугольника, то такие треугольники равны ( по катету и острому углу ).

Если гипотенуза и острый угол одного прямоугольного треугольника соответственно равны гипотенузе и острому углу другого прямоугольного треугольника, то такие треугольники равны ( по гипотенузе и острому углу ).

Если гипотенуза и катет одного прямоугольного треугольника равны гипотенузе и катету другого прямоугольного треугольника, то такие треугольники равны ( по гипотенузе и катету ).