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

47

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

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

Грант
источник
1
В некоторой степени связанный, NVidia NV1 использовал квадратичное наложение текстур (которое использует четырехугольники) вместо треугольников / многоугольников. Это был не большой успех, если не сказать больше. См. En.wikipedia.org/wiki/NV1 .
Мак
5
@Macke: квадратичный, как в «квадратном уравнении», а не квадратичный, как в «четырехугольнике». Он не использует квадраты, а скорее квадратичную кривую, определенную 9 точками. stason.org/TULARC/pc/3d-graphics-cards-faq/...
9
+1 за ваш вопрос, но большой -1 вашему профессору. Это базовый материал, который он должен был знать так же хорошо, как и свою тыльную сторону, и признак того, что он немного не в курсе событий последних 15 с лишним лет.
Максимус Минимус
1
Ну, в моей защите профессоров, он не на стороне разработчика игр, он скорее аниматор / модельер. Он знал, что он конвертируется в трис, но не знал математической причины, по которой нужно делать рендеринг. Но да, он, вероятно, должен был знать.
Грант

Ответы:

56

Нижняя строка - это треугольник Rasterization, который позволяет компьютерам отображать объекты на экране. Хотя другие говорят это чаще, чем я:

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

Акцент мой. Источник: http://www.devmaster.net/articles/software-rendering/part3.php

Nate
источник
2
Потрясающие! Это имеет большой смысл, когда вы думаете об этом. Спасибо за ответ!
Грант
1
В OpenGL ES, в рамках усилий по упрощению API, квады и полигоны даже не поддерживаются. Поэтому практическая причина использования треугольников в том, что у вас нет другого выбора. Но причина, по которой оптимизированный API, такой как ES, избегает других примитивных типов, объясняется причинами, изложенными в этом и других ответах.
Suboptimus
5
+1 Потому что это ответ, который я могу смело использовать в качестве ссылки, когда кто-то спросит меня то же самое, на мои закладки. Только скажу, что я всегда думал, что причина в том, что треугольники - это маленький возможный примитив, потому что с неточной арифметикой с плавающей точкой, трис - единственный безопасный многоугольник, который вы можете гарантировать, чтобы быть плоским во всех случаях, с квадратами, которые вы не можете гарантировать, что они будут будь плоским все время. Программное обеспечение для моделирования, вероятно, отображает объекты в виде квадратов или n-гонов для удобства разработчика, но применяет преобразование / рендеринг разделительных полигонов в виде двух или более треугольников.
Hatoru Hansou
56

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

Четыре или более точек могут не находиться в одной плоскости, но три точки всегда есть (игнорируя вырожденные случаи). Это имеет интересное свойство: скалярные значения линейно изменяются по поверхности треугольника. Даже когда треугольник проецируется на экран, скалярные значения все равно линейно изменяются относительно x '/ z и y' / z.

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

tl; dr: треугольники - самый простой примитив, поэтому алгоритмы, работающие с треугольниками, могут быть сильно оптимизированы.

ggambett
источник
11
+1. Я думаю, что тот факт, что треугольник всегда плоский, является одной из главных причин. Неплоские многоугольники делают вещи намного сложнее.
Буммзак
2
+1. Я думаю, что треугольники, являющиеся единственным полигоном, который вы можете гарантировать, чтобы быть плоским, являются основной технической причиной для создания apis и оборудования, которое требует треугольников. Программное обеспечение для моделирования, вероятно, отображает сетки в виде четырехугольников как удобство для моделиста.
Hatoru Hansou
1
Хорошая неплоская аналогия, которую я использую ... Трехногий табурет может стоять на земле только в одном направлении, его ноги похожи на углы треугольника. Но четвероногий стул может стоять на земле двумя путями и колебаться от одного положения к другому, если одна нога короче других.
ChrisC
Я любопытный; Как возможно, чтобы треугольник всегда имел точки на одной плоскости? Как вы на самом деле нарисовать сферу тогда? По крайней мере, одна точка должна быть переведена на другую плоскость, в противном случае вы получите плоскую поверхность.
rataplan
@newbiez Три вершины всегда определяют одну плоскость. Сфера состоит из разных треугольников; два смежных треугольника, представляющие участок поверхности сферы, имеют две общие вершины, но они не находятся на одной плоскости. Это изображение может прояснить ситуацию: cse.csusb.edu/tongyu/courses/cs420/images/icos.jpg
ggambett
8

Три точки (треугольник) ВСЕГДА определяют плоскую плоскость. Другими словами, учитывая любые три точки, вы всегда можете создать плоскую плоскость, которая может прорезать все три точки. Однако то же самое не всегда верно для четырех пунктов. Вы можете иметь четыре точки на плоскости, но вы также можете иметь четыре точки, которые не на плоскости.

Тим Холт
источник
2
На самом деле 4 случайных точки, скорее всего, не находятся на плоскости, поэтому вам все равно придется триангулировать.
ChrisF
Это верно только в том случае, если точки не совпадают.
Нотлеш
1
Даже если точки совпадают, они копланарны на бесконечном количестве плоскостей.
3Dave
Быть копланарным не «ВСЕГДА определять плоскую плоскость» .
Сам Хочевар
6

Это не "игровые движки", которые делают это - все программное обеспечение 3D, которое вы используете, делает это. Это просто не говорит вам об этом, и ваш профессор кажется недостаточно квалифицированным, если он этого не знает. Они существуют в памяти компьютера, даже если программное обеспечение скрывает их от вас. Все 3D-программы имеют опцию, которая делает треугольники видимыми. У них также будет опция, которая разбивает их на редактируемые края, так что вы можете играть с ними. Но они всегда были там с самого начала, и наивно для вашего профессора преподавать этот предмет и все еще удивляться «для чего нужны треугольники».

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

Domarius
источник
3

Треугольник - это самый простой примитив, который можно описать изолированно, потому что он имеет три точки, меньше, чем те, которые не описывают поверхность в 3D.

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

Поэтому первая компьютерная система, которая преуспела в рендеринге «любой поверхности вообще», естественным образом сделала это путем независимого рендеринга многих треугольников.

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

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

Вот почему в 1980-х годах фильмы приняли «четырехугольник», который является неправильным, потому что он относится к двумерной сетке вершин в трехмерном пространстве, а не к изолированному четырехугольнику.

Такого же перехода от треугольников к «квадратам» еще не произошло в сфере интерактивных развлечений, но, скорее всего, это произойдет довольно скоро и по тем же причинам, что и в кинобизнесе.

bmcnett
источник
2

Есть только один способ триангуляции треугольника по сравнению с 'n - 2' способами для n-стороннего многоугольника. Таким образом, треугольники в конечном счете являются наименее двусмысленным способом определения многогранной формы. Кроме того, как указывали другие авторы, существует множество способов ускорить растеризацию треугольника (а не квадрата или выше) (константа z является одной из моих любимых). Кроме того, проще оптимизировать тесты пересечения лучей и треугольников, чем тесты пересечений лучей и произвольных многоугольников. Фактически, многие операции над n-сторонними полигонами выигрывают от наличия триангулированного представления. Это не означает, что n-сторонние представления многоугольников являются «плохими» - они очень полезны, но в конечном итоге вы захотите работать с треугольниками для многих операций с сетками.

Лютер
источник
2

Пока треугольник определяется тремя неколинейными вершинами (читай: ни один из углов не является точным числом Pi), вершины определяют уникальную плоскость.

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

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

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

Какой смысл работать с квадроциклами?

Если вам нужен квад, соедините два треугольника.

3Dave
источник
2

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

Поэтому остающаяся проблема заключается в эффективности представительства. - вы можете легко представить четырехугольник с двумя треугольниками и без каких-либо дополнительных вершин, если вы используете полосу треугольника (3 вершины для 1-го треугольника, затем дополнительный вершина для 2-го треугольника). С другой стороны, если вы пытаетесь изобразить треугольник с квадратом, вам нужно использовать 4 вершины и иметь вырожденную, идентичную другой. Это не идеально с точки зрения эффективности.

Kylotan
источник