Z-Ordering in Software richtig durchführen

Question

Ich rende 3D-Objekte auf einer 2D-Leinwand, indem ich alle notwendigen Berechnungen in der Software mache. Ich verwende keine Grafikbeschleunigung.

Anfangs waren alle Objekte Würfel von gleicher Größe, also konnte ich sie anhand ihrer Entfernung in Z von der Kamera sortieren und das würde sie richtig ordnen. Aber jetzt versuche ich Würfel unterschiedlicher Größe zu zeichnen. Das führt dazu, dass mein einfacher z-Ordnungsalgorithmus bei der perspektivischen Projektion versagt.

Ich schaute in Computergrafik Bücher und fand die verwendeten Techniken, sie empfehlen schließlich Pixel-basierten Vergleich von zwei Polygonen, um zu bestimmen, welche man vor anderen ist. Wahrscheinlich machen sie das in der Grafikkarte. Aber das scheint in Software sehr schwierig zu sein und ich denke, es wird langsam für den praktischen Gebrauch sein, selbst wenn ich es kann.

Gibt es einen einfachen Trick, dies in der Software zu tun? Irgendwelche Beispiele aus den frühen Tagen der 3D-Grafik, als Grafikkarten nicht verfügbar waren?

Obwohl dies generische 3D-Grafik Frage ist, wenn es hilft, mache ich dies auf HTML5 Canvas 2D API.

Answer 1

Wie bereits von @ybungalobill erwähnt, ist z-buffer der einfachste zu implementierende Algorithmus. Wenn Sie die Dreiecke/Polygone füllen, die Ihre Würfel bilden, interpolieren Sie die Z-Koordinate zwischen ihnen und speichern Sie sie pro Pixel. Wenn Sie später ein anderes Polygon füllen, das auf der gleichen X, Y-Koordinate rendert, überprüfen Sie, ob sein Z kleiner ist als das Z, das bereits im Puffer gespeichert ist. Vergessen Sie nicht, den Z-Puffer vor dem Neuzeichnen auf unendlich zu löschen. Pseudo-Code:

foreach (scanline in polygon) { 
    int length = scanline.right.x - scanline.left.x; 
    foreach (pixel in scanline) { 
    float t = (float)pixel.x/length; 
    float z = (1 - t) * scanline.left.z + t * scanline.right.z; // Interpolate the Z coordinate 
    if (z < zbuffer[scanline.y][pixel.x]) 
     drawPixel(pixel.x, scanline.y, polygon.color); // The pixel is closer, paint it 
    } 
} 

Ein überarbeiteter Ansatz von Z-Puffer, der durch nicht Zeichnung Pixel besser auf CPU ausführt, die Segmentpuffer genannt überschrieben werden würde, ist: http://www.gamedev.net/reference/articles/article668.asp

Ein weiterer Ansatz ist der Warnock Algorithmus. Es verwendet Rekursion, die es schwierig macht, auf GPUs zu verwenden, aber CPU sollte es gut machen, wenn Sie Ihren eigenen Stapel verwenden, um Stapelüberlauf zu vermeiden. Die Idee besteht darin, die Szene in vier Teile zu unterteilen und zu prüfen, ob nur ein Polygon das ganze Teil bedeckt. Wenn es nicht erneut aufgeteilt wird, bis die Bedingung erfüllt ist (im schlimmsten Fall wird es auf Pixelebene erreicht). Pseudo-Code:

void warnock(Rectangle rect) 
{ 
    float minZ = infinity; 
    foreach (polygon in polygons) { 
    if (rect is inside polygon) { 
     float z = interpolateZ(polygon, rect.x + rect.width/2, rect.y + rect.height/2); // Get Z coordinate at the centre of the rectangle 
     if (z < minZ) { // If there are more polygons in this rectangle, make sure the topmost one gets drawn last 
     fillRect(polygon.color); 
     minZ = z; 
     } 
    } else { 
     // Divide to 4 subrectangles 
     warnock(Rectangle(rect.x, rect.y, rect.width/2, rect.height/2)); // Top left 
     warnock(Rectangle(rect.x, rect.y + rect.height/2, rect.width/2, rect.height/2)); // Bottom left 
     warnock(Rectangle(rect.x + rect.width/2, rect.y, rect.width/2, rect.height/2)); // Bottom right 
     warnock(Rectangle(rect.x + rect.width/2, rect.y + rect.height/2, rect.width/2, rect.height/2)); // Top right 
    } 
    } 
} 

Der Algorithmus des Maler ist, was Sie mit Ihrem Würfel gemacht haben, der einzige Unterschied besteht darin, dass es die Polygone statt ganze Objekte sortiert. Selbst dann ist es schwierig, verschiedene Polygonüberschneidungen zu lösen, und ich persönlich würde es nicht für nicht-triviale Szenen verwenden.

Ein anderer Algorithmus, den Sie verwenden könnten, ist der Backface-Culling-Algorithmus. Dies funktioniert nur für konvexe Objekte, die sich nicht überlappen.Der Algorithmus berechnet die Normale jedes Polygons, und wenn es in die Richtung von der Kamera zeigt, wird es entfernt.

Raycasting ist eine weitere Möglichkeit, die Sichtbarkeit pro Pixel zu bestimmen. Es ist jedoch ziemlich CPU-intensiv. Die Grundidee besteht darin, für jedes Pixel des Bildschirms zu prüfen, welches Polygon es schneidet (welches Polygon von dem vom aktuellen Pixel geworfenen Strahl getroffen wird). Der Ursprung der Strahlen ist die Augenposition. Pseudocode:

foreach (pixel in screen) { 
    float minZ = infinity; // Can be zfar from the perspective projection 
    Color pixelColor = backgroundColor; 
    foreach (polygon in projectedPolygons) { 
    if (polygon contains Point(pixel.x, pixel.y)) { 
     float z = interpolateZ(polygon, pixel.x, pixel.y); // Get the current Z for (x, y) and this polygon using bilinear interpolation 
     if (z < minZ) { 
     minZ = z; 
     pixelColor = polygon.color; 
     } 
    } 
    } 
} 

Answer 2

Richtig, heute verwenden Sie Z-Pufferung auf der GPU, um einen Tiefenvergleich pro Pixel durchzuführen. Sie können dies auch in der Software tun.

Die Sortiertechnik wird im Allgemeinen nicht funktionieren, siehe wikipedia. Sie können es jedoch verbessern, indem Sie Ihre Würfel in einzelne Flächen aufteilen und sie anstelle von Würfeln sortieren.

Eine allgemeinere Technik, die in vielen frühen Spielen (z. B. Doom) verwendet wurde, ist BSP trees. Sie werden nicht mit dynamischen Szenen arbeiten, da es teuer ist, sie zu erstellen. Sie lösen jedoch das Bestellproblem im Allgemeinen.

Answer 3

Was ich gefunden habe, ist ein festes Gitter kombiniert mit Warnock. Verteile den Bereich des Bildschirms des Modells umfasst (en) im Stumpfes in Zellen:

Dazu kann man einfach das Begrenzungsrechteck der Primitiven verwenden Sie einfügen. Diese Struktur kann ziemlich schnell aktualisiert werden, da Sie nur ganze Zahlen manipulieren müssen, um die Dinge von einer Zelle zur anderen zu bewegen. Um zu vermeiden, ständig Aufteilung und Daten Umschichtungen vorzunehmen, verwenden Sie einen Ansatz freie Liste:

nun jede Gitterzelle machen, wenn es „einfach genug“ (Warnock Kriterien). Wenn nicht, wenden Sie Warnock an.

Eine Rasterzelle ist "einfach genug", wenn das Rechteck für die Zelle vollständig in den Dreiecken enthalten ist, die Sie für diese Zelle rendern, z. und alle 4 Schnittpunkte für das Rechteck innerhalb eines gegebenen Dreiecks liegen vor allen anderen (haben den minimalen Tiefenwert) ... oder wenn die Zelle leer ist oder nur ein Primitiv hat.

Das gesagt, ich mache das nicht wirklich für Echtzeitanzeigezwecke. Es könnte ziemlich schwierig sein, dies in komplexen Netzen in Echtzeit effizient genug zu tun.

Ich mache hauptsächlich Dinge wie z. B. Marquee und Lasso, wählen Sie Scheitelpunkte/Kanten/Polygone in 3D-Software auf sehr dichten Gittern aus, wo wir nicht unklare Primitive durch Approximation mit einer festen Pixelauflösung verpassen wollen. In diesem Fall könnte der Benutzer weit weg von einem Netz herauszoomen und wir möchten nicht, dass unsere Lasso und Auswahlmöglichkeiten eine ganze Reihe von Subpixel-Primitiven verpassen, so dass die Verwendung des auflösungsunabhängigen Warnocks hier rekursiv ist Wenden Sie den Algorithmus so tief an, wie Sie benötigen, bis Sie das Ergebnis "einfach genug" erhalten, das ein Rechteck sein könnte, das viel kleiner als ein Pixel ist. Es könnte auch nützlich sein für Antialiasing mit einigermaßen effizienter Unterabtastung (da es keine Unterabtastung durchführt, wenn beispielsweise ein Pixel eine vollständige Abdeckung aufweist). Ich habe das nie für Rasterisierungskontexte verwendet.

Raytracing macht auch Spaß wegen all der Möglichkeiten, die es bis hin zu indirekter Beleuchtung, Ätzmittel, DOF usw. eröffnet, obwohl es sehr rechenintensiv ist, wie Karel betont. Das heißt, ich habe mit einem guten BVH herausgefunden, dass ich in der heutigen Zeit mit ziemlich hoher Auflösung in Echtzeit Raytracing machen kann, wenn ich nur hauptsächlich direktes Licht mache.

Hier ist ein kleines Beispiel, das ich aus Raytracing einer Million Dreiecksnetz in Echtzeit auf der CPU ausgegraben, die ich von einigen Jahren gepeitscht habe. Das war auf meinem i3 und bei 1600x1200 Pixel. Es hat nur einen Tag gedauert, um es zu programmieren. Die GIF herabgestuft wirklich die Qualität und Bildrate (ursprünglich über ~ 120 FPS), aber hoffentlich bekommen Sie die Idee:

Der größte Nachteil für mich mit Echtzeit-Raytracing auf CPU (sowie GPU) ist eigentlich nicht der Rasterungsteil.Während ich Grundmaterialien und Beleuchtung in Echtzeit ziemlich einfach mit einem i3 rendern konnte (und dies war nicht einmal optimierter Code, nur einige grundlegende SIMD und parallele Schleifen in C), wäre es viel schwieriger, wenn dieses Million Dreiecksnetz alle deformiert würde Rahmen. Dann müsste ich in der Lage sein, den BVH zu aktualisieren, der über eine Million Dreiecke mit über 100 FPS speichert, von denen ich nicht weiß, wie ich schnell genug vorgehen soll.

Das heißt, es gibt eine Software, die tatsächlich Millionen von Polygonen rasterisiert, die Daten in Echtzeit verformen. Es heißt ZBrush:

Ich habe keine Ahnung, wie sie es aber verwalten. Sie können LOD oder Voxelize super schnell verwenden, während Benutzer es mit einem Pinsel oder etwas deformieren; Für mich ist das nicht wirklich wichtig, da Sie die Dinge auf der Ebene pro Vertex, pro Polygon-Ebene steuern können, lassen Sie Drahtmodelle sehen und lassen Sie polygonale Netze beim Laden und Speichern eingeben und ausgeben. Wie auch immer, es hat den Effekt, Millionen von Polygonen Daten zu verarbeiten (es gelang sogar, Netze zu rippen und zu verformen, die vor 17 Jahren über 20 Millionen Polygone spannen, was beispiellos ist; Benutzer, um die Ergebnisse zu formen und die Dinge irgendwie auf einer Vertex-Ebene zu steuern, während interaktive Bildraten beibehalten werden, ohne die GPU für die Rasterung zu verwenden. Sie haben eine Art Voodoo-Programmierung, so weit ich es sehe, aber ich könnte einen Finger tauschen, um herauszufinden, wie sie das machen.