Warum konvertieren Game Engines Modelle in Dreiecke, anstatt Quads zu verwenden?

47

Ich habe mit Maya für Animationen und mehr filmorientierte Projekte gearbeitet, aber ich konzentriere mich auch auf meine Studien zur Entwicklung von Videospielen. Wie auch immer, ich habe mit einem meiner Professoren gesprochen und wir konnten nicht herausfinden, warum alle (mir bekannten) Spiele-Engines in Dreiecke konvertiert werden.

Weiß zufällig jemand, warum Game-Engines in Dreiecke umgewandelt werden, anstatt die Modelle als vierseitige Polygone zu belassen? Was sind auch die Vor- und Nachteile (falls vorhanden), wenn Sie dies tun?

Gewähren
quelle
1
Das NVidia NV1 verwendete in gewisser Weise eine quadratische Texturabbildung (die Quads verwendet) anstelle von Dreiecken / Polygonen. Es war kein großer Erfolg, um es gelinde auszudrücken. Siehe en.wikipedia.org/wiki/NV1 .
Macke
5
@ Macke: Quadratisch wie in "quadratische Gleichung", nicht quadratisch wie in "viereckig". Es werden keine Quads verwendet, sondern eine quadratische Kurve, die durch 9 Punkte definiert wird. stason.org/TULARC/pc/3d-graphics-cards-faq/…
9
+1 für deine Frage aber ein großes -1 für deinen Professor. Dies sind grundlegende Dinge, die er wissen sollte und die er selbst kennt, und ein Zeichen dafür, dass er mit den Entwicklungen der letzten 15 Jahre ein wenig nicht vertraut ist.
Maximus Minimus
1
Nun, in der Verteidigung meines Professors ist er kein Entwickler, sondern eher ein Animator / Modeler. Er wusste, dass es zu Tris konvertiert wurde, wusste aber nicht, warum es gerendert werden sollte. Aber ja, er hätte es wahrscheinlich wissen müssen.
Grant

Antworten:

56

Die unterste Zeile ist Dreieck-Rasterisierung. Auf diese Weise rendern Computer Objekte auf dem Bildschirm. Obwohl andere es elquenter sagen als ich:

Alle 3D-Objekte, die wir auf dem Computerbildschirm sehen, bestehen aus winzigen geometrischen Objekten, die oft als Primitive bezeichnet werden. Vierecke, Dreiecke, n-Gone usw. sind Beispiele für Grundelemente. Wir werden uns hauptsächlich aus einem Grund auf Dreiecke konzentrieren: Jedes Objekt kann in Dreiecke unterteilt werden, aber ein Dreieck kann nur in Dreiecke unterteilt werden. Aus diesem Grund ist das Zeichnen von Dreiecken viel einfacher als das Zeichnen von Polygonen höherer Ordnung. weniger Dinge zu erledigen. Aus diesem Grund werden diese Dreiecke in der Computergrafik so häufig verwendet.

Betonung meiner. Quelle: http://www.devmaster.net/articles/software-rendering/part3.php

Nate
quelle
2
Genial! Das macht sehr viel Sinn, wenn Sie darüber nachdenken. Danke für die Antwort!
Grant
1
In OpenGL ES werden Quads und Polygone im Rahmen der Vereinfachung der API nicht einmal unterstützt. Ein praktischer Grund für die Verwendung von Dreiecken ist, dass Sie keine andere Wahl haben. Der Grund, warum eine optimierte API wie ES andere primitive Typen vermeidet, liegt in den in dieser und anderen Antworten genannten Gründen.
Suboptimus
5
+1 Weil es eine Antwort ist, die ich ohne Bedenken als Referenz verwenden kann, wenn mich jemand auf meine Lesezeichen hin das Gleiche fragt. Sagen Sie nur, ich habe immer gedacht, dass der Grund, warum Dreiecke das kleinste mögliche Grundelement sind, darin besteht, dass mit der Ungenauigkeit der Gleitkomma-Arithmetik Tris das einzige sichere Polygon ist, für das Sie garantieren können, dass es in allen Fällen planar ist Sei die ganze Zeit planar. Modellierungssoftware zeigt dem Modellierer Objekte wahrscheinlich als Quads oder N-Gons an, wendet jedoch Transformationen / Render-Teilungspolygone als zwei oder mehr Dreiecke an.
Hatoru Hansou
56

Dreiecke haben viele Eigenschaften, die das Zeichnen erleichtern und damit beschleunigen.

Vier oder mehr Punkte befinden sich möglicherweise nicht auf derselben Ebene, drei Punkte jedoch immer (degenerierte Fälle werden ignoriert). Dies hat die interessante Eigenschaft, dass Skalarwerte linear über die Oberfläche des Dreiecks variieren. Selbst wenn das Dreieck auf den Bildschirm projiziert wird, variieren die Skalarwerte linear in Bezug auf x '/ z und y' / z.

Dies bedeutet wiederum, dass die meisten, wenn nicht alle zum Schattieren, Texturieren und Tiefenfiltern eines Dreiecks erforderlichen Elemente mithilfe einer linearen Interpolation berechnet werden können, die mit spezialisierter Hardware äußerst schnell ausgeführt werden kann.

tl; dr: Dreiecke sind das einfachste Grundelement, sodass Algorithmen für Dreiecke stark optimiert werden können.

ggambett
quelle
11
+1. Ich denke, die Tatsache, dass ein Dreieck immer eben ist, ist einer der Hauptgründe. Nichtplanare Polygone machen Dinge viel komplizierter.
Mistzack
2
+1. Ich denke, Dreiecke sind das einzige Polygon, von dem Sie garantieren können, dass es eben ist. Dies ist der wichtigste technische Grund für die Herstellung von APIs und Hardware, für die Dreiecke erforderlich sind. Die Modellierungssoftware zeigt dem Modellierer wahrscheinlich Netze als Quads an.
Hatoru Hansou
1
Eine schöne nichtplanare Analogie, die ich benutze ... Ein dreibeiniger Hocker kann nur in einer Richtung auf dem Boden stehen, wobei seine Füße wie die Ecken eines Dreiecks sind. Ein vierbeiniger Hocker kann jedoch in zwei Richtungen auf dem Boden stehen und von einer Position zur anderen wackeln, wenn ein Bein kürzer als das andere ist.
ChrisC
Ich bin neugierig; Wie ist es möglich, dass ein Dreieck immer auf der gleichen Ebene liegt? Wie zeichnet man dann eigentlich eine Kugel? Mindestens einer der Punkte muss auf einer anderen Ebene verschoben werden, sonst erhalten Sie eine flache Oberfläche.
Rataplan
@newbiez Drei Eckpunkte definieren immer eine einzelne Ebene. Eine Kugel besteht aus verschiedenen Dreiecken. Zwei benachbarte Dreiecke, die einen Fleck auf der Oberfläche der Kugel darstellen, teilen sich zwei Scheitelpunkte, befinden sich jedoch nicht in derselben Ebene. Dieses Bild kann die Sache klarer machen: cse.csusb.edu/tongyu/courses/cs420/images/icos.jpg
ggambett
8

Drei Punkte (ein Dreieck) definieren IMMER eine flache Ebene. Mit anderen Worten, wenn Sie drei beliebige Punkte haben, können Sie immer eine flache Ebene erstellen, die alle drei Punkte durchschneiden kann. Dies gilt jedoch nicht immer für vier Punkte. Sie können alle vier Punkte in einer Ebene haben, aber Sie können auch vier Punkte haben, die sich nicht in einer Ebene befinden.

Tim Holt
quelle
2
Tatsächlich befinden sich 4 zufällige Punkte eher nicht in einer Ebene, sodass Sie ohnehin triangulieren müssen.
ChrisF
Dies gilt nur, wenn die Punkte nicht übereinstimmen.
notlesh
1
Selbst wenn die Punkte zusammenfallen, sind sie auf einer unendlichen Anzahl von Ebenen koplanar.
3Dave
Koplanar zu sein bedeutet nicht, "IMMER eine flache Ebene zu definieren" .
Sam Hocevar
6

Es sind nicht "Game Engines", die dies tun - die gesamte 3D-Software, die Sie verwenden, tut dies. Es sagt Ihnen einfach nichts darüber und Ihr Professor scheint ziemlich unterqualifiziert zu sein, wenn er das nicht weiß. Sie befinden sich im Arbeitsspeicher des Computers, auch wenn die Software sie vor Ihnen verbirgt. Alle 3D-Programme haben eine Option, mit der die Dreiecke sichtbar werden. Sie haben auch eine Option, die sie in bearbeitbare Kanten aufteilt, sodass Sie mit ihnen spielen können. Aber sie waren immer anfangs da und es ist naiv für Ihren Professor, dieses Fach zu unterrichten und sich immer noch zu fragen, "wofür Dreiecke sind".

Ein Dreieck ist die einzige Möglichkeit, Verts anzuordnen und eine flache Oberfläche zu gewährleisten. Wenn Sie ein Quad haben, können Sie die Verts so anordnen, dass sie sich biegen müssen. Aber es besteht bereits aus Dreiecken und es sind diese Dreiecke, die das Biegen ermöglichen.

Domarius
quelle
3

Ein Dreieck ist das einfachste Grundelement, das isoliert beschrieben werden kann, da es drei Punkte hat, weniger als eine Oberfläche in 3D.

Da ein Dreieck isoliert betrachtet werden kann, ist es möglich, ein Stück Code oder Silizium herzustellen, das in der Lage ist, nur ein einziges Dreieck zu rendern, das über die Kraft der Wiederholung überhaupt eine Oberfläche rendern kann.

Daher gelang es dem ersten Computersystem, "überhaupt irgendeine Oberfläche" zu rendern, indem es viele Dreiecke unabhängig voneinander renderte.

Wenn man sich Dreiecke und Quads als "primitive" (dh als vollständig isolierte Teile der Geometrie ohne Kontext) vorstellt, ist das Dreieck das primitivere und neigt daher zum "Gewinnen".

Sobald jedoch Computer mit Unterhaltungsqualität in den 1980er Jahren ein bestimmtes Niveau an Raffinesse überschritten, wurde die Einfachheit, "Primitive" isoliert zu betrachten, weniger wichtig. Wenn Grafiken in Massenproduktion hergestellt werden sollen, begünstigen Skaleneffekte die Verarbeitung von Gruppen verwandter Eckpunkte, ebenso wie die gleichzeitige Montage von hundert nahezu identischen Autos.

Aus diesem Grund haben die Filme in den 1980er Jahren das "Quad" übernommen, was eine falsche Bezeichnung ist, da es sich um ein 2D-Gitter von Eckpunkten im 3D-Raum und nicht um ein isoliertes Viereck handelt.

Dieselbe Verlagerung von Dreiecken zu "Quads" hat im Bereich der interaktiven Unterhaltung noch nicht stattgefunden, aber es ist wahrscheinlich, dass dies ziemlich bald und aus den gleichen Gründen wie im Filmgeschäft der Fall ist.

bmcnett
quelle
2

Es gibt nur einen Weg, ein Dreieck zu triangulieren, gegenüber 'n - 2' Wegen für ein n-seitiges Polygon. Dreiecke sind also letztendlich die am wenigsten mehrdeutige Art, eine polyedrische Form zu definieren. Wie andere Poster bereits angedeutet haben, gibt es auch viele Möglichkeiten, die Dreiecksrasterung (anstelle von Quad oder höher) zu beschleunigen (Konstante z ist einer meiner Favoriten). Außerdem ist es einfacher, Tests für Schnittpunkte von Strahlendreiecken zu optimieren als Tests für strahlendirektive Polygonschnittpunkte. Tatsächlich profitieren viele Operationen an n-seitigen Polygonen davon, eine triangulierte Darstellung zur Hand zu haben. Das heißt nicht, dass n-seitige Polygondarstellungen "schlecht" sind - sie sind sehr nützlich, aber letztendlich möchten Sie für viele Netzoperationen mit Dreiecken arbeiten.

Luther
quelle
2

Solange das Dreieck durch drei nicht-kolineare Eckpunkte definiert ist (sprich: keiner der Winkel ist genau Pi), definieren die Eckpunkte eine eindeutige Ebene.

Ein Quad ist natürlich durch vier Eckpunkte definiert. Es ist durchaus möglich, dass diese Eckpunkte nicht koplanar sind. In diesem Fall besteht Ihr Quad tatsächlich aus zwei durch eine Diagonale getrennten Dreiecken. Das sind zwei Ebenen, zwei Sätze von Oberflächennormalen usw.

Jedes verfügbare Modellierungswerkzeug, jeder Algorithmus für Texturierung, Beleuchtung usw. setzt voraus, dass ein Modell aus ebenen Segmenten besteht, und jede Formel, die wir haben (Kreuzprodukte für die normale Berechnung sind die ersten, die wir haben), verwendet den absoluten Mindesteingabedatensatz - drei Scheitelpunkte definieren eine Ebene, und die Ebene ist das, was wir brauchen, um all die ausgefallenen Dinge zu erledigen.

Sie könnten sicherlich eine Engine für die Arbeit mit Quads schreiben, aber Sie würden den vierten Eckpunkt in fast jedem Fall ignorieren, außer wenn Sie (häufig) sicherstellen müssten, dass er mit den anderen drei, die das Quad definieren, koplanar ist. Und die logischste Lösung für den Fall, dass es nicht koplanar ist, wäre, das Quad in zwei Dreiecke zu teilen. Warum also nicht gleich anfangen?

Was um alles in der Welt wäre der Sinn, mit Quads zu arbeiten?

Wenn Sie ein Quad wollen, setzen Sie zwei Dreiecke zusammen.

3Dave
quelle
2

Wenn wir davon ausgehen, dass es kein Problem ist, 4 Punkte koplanar zu machen (das ist, wie die anderen bereits betont haben, aber ich denke schon), dann finden Sie das Rendern eines willkürlichen Trapezes (so sieht ein Viereck normalerweise aus) Wenn es in einen Bildschirmbereich umgewandelt wird, unterscheidet es sich nicht wesentlich vom Rendern eines Dreiecks. Tatsächlich funktioniert es ziemlich genau so, wenn Sie das Ausschneiden ausführen, da dies zusätzliche Scheitelpunkte einführen kann. (Zumindest in einem Softwaremodell - Hardware verfügt möglicherweise über eine einfachere Brute-Force-Methode zum Abschneiden.)

Das verbleibende Problem ist daher die Darstellungseffizienz. - Sie können problemlos ein Quad mit 2 Dreiecken und ohne zusätzliche Eckpunkte darstellen, wenn Sie einen Dreiecksstreifen verwenden (3 Eckpunkte für das 1. Dreieck, dann ein zusätzliches Eckpunkt für das 2. Dreieck). Wenn Sie dagegen versuchen, ein Dreieck mit einem Vierer darzustellen, müssen Sie 4 Scheitelpunkte verwenden und einen entarteten Scheitelpunkt haben, der mit einem anderen identisch ist. Dies ist im Hinblick auf die Effizienz nicht ideal.

Kylotan
quelle