[Contrib] [Labor] [Nummer 3]    DER WACKELPUDDING-ALGORITHMUS

DER WACKELPUDDING-ALGORITHMUS Ein neues Verfahren zur Abbildung einer eingeschränkten Klasse von Nachspeisen von Paul S. Heckbert, PIXAR Inc. Ray Tracing [a] hat sich in den vergangenen Jahren als der weitreichendste Algorithmus zur Bildsynthese etabliert [10]. Forscher haben Verfahren zur Schnittpunktberechnung von Strahlen für eine Anzahl von Flächen-Primitives [b] erarbeitet. Zu diesen gehören Schachbretter [Whitted 80]; Chromkugeln [Whitted 80]; Glaskugeln [Whitted 80]; Roboter- Arme [Barr 82]; blaue abstrakte Dinge [Hanrahan 82]; weitere Glaskugeln [Watterberg 83]; Mandrills [Watterberg 83]; weitere Mandrills [Sweeney 83]; grüne fraktale Hügel [Kajiya 83]; noch mehr Glaskugeln [SEDIC 83]; unterseeische Blubberdinger [Kaw 83]; mehr Chromkugeln [Heckbert 83]; Wasserbälle [Porter 84]; und noch mehr Glaskugeln [Kajiya 86]. Bedauerlicherweise hat noch niemand irgendwelche Nahrungsmittel vermittels Ray Tracing dargestellt. Die realistischsten Nahrungsmittel sind auf Blinn's klassischen Orangen- und Erdbeer-Bildern zu sehen, welche aber durch einen Scanline-Algorithmus erzeugt wurden [2]. Das "Dessert Realism Project" bei Pixar [c] hat sich dieses Problems angenommen. Dieser Artikel präsentiert neue Ray Tracing- Verfahren zur Darstellung einer bestimmten Klasse von Nachspeisen, im speziellen von Jell-O-Brand Gelatine [eine Art Götterspeise; Anm.d.Ü.]. Wir glauben, daß diese Methode sich auch auf andere Gelatine-Marken und möglicherweise auch auf Pudding anwenden läßt. Die Form von Jell-O Um einen statischen Jell-O zu modellieren, benutzen wir eine neue Synthese-Technik, in der Attribute durch die Verwendung abstrakter, objektorientierter Klassen, die wir "Zutaten" nennen, einzeln hinzugefügt werden. Die Attribute von Zutaten werden im Rahmen eines Preprozess-Durchgangs kombiniert, um die gewünschte Zusammensetzung von Materialeigenschaften (Konsistenz, Geschmack, Dehnbarkeit, Temperaturbeständigkeit, Brechungsindex, etc.) zu erreichen. Wir verwenden eine orthogonale RLS-Basis ([R]aspberry, [L]ime, [S]trawberry; Himbeeren, Limonen, Erdbeeren; s. Abbildung), von der ausgehend jede Art von Jell-O synthetisiert werden kann [9]. Die Zutaten werden über ein großes 3D-Gitter verteilt, und zwar unter Anwendung von vektorisiertem SIMD-Parallel Processing in einer systolischen Array-Architektur [d], die wir "Jell-O Engine" nennen. Wir können unterschiedliche Gitterpunkte gleichzeitig berechnen. Frei geformten Flächen sind Begrenzungsbedingungen auferlegt, um die Jell-O-Form zu kontrollieren; die Zutaten werden unter Verwendung von "relaxation"- und "annealing"-Gitteralgorithmen gemischt, bis die Matrix erstarrt und "eßfertig" ist. Die Dynamik von Jell-O Frühere Forscher haben beobachtet, daß Jell-O unter bestimmten Bedingungen "wobbelt" [8]. Es ist uns möglich, diese spezielle und komplexe Jell-O Dynamik unter Verwendung spatialer Deformationen [1] und einiger anderer haariger Berechungsverfahren zu simulieren. Aus früheren Forschungen mit Rendering-Systemen [a] haben wir gelernt, daß eine gute Dosis zusätzlicher partieller Differentialgleichungen nützlich ist, um den Papier-Ergebnissen eindrucksvoller Formeln zu entsprechen. Daher haben wir die Schrödinger'sche Wellengleichung für das Jell-O-Feld J aufgelöst: 2 2m Delta J + -- (E - V)J = 0 . h Transformation in ein sphärisches Koordinatensystem: delta J 1 delta J 1 delta J Delta J = xi ------- + xi - ----------- + xi ------------ --------- x delta r y r delta Theta z r sin Theta delta Psi 2 1 delta ( delta J ) 1 delta Delta J = --- ------- ( 2 ------- ) + ------------ ----------- --> 2 ( r ) 2 r delta r ( delta r ) r sin Theta delta Theta 2 ( delta J ) 1 delta J --> ( sin Theta ----------- ) + ------------- ---------- . ( ) 2 2 2 ( delta Theta ) r sin Theta delta Psi Fuller gibt eine kurze und erhellende Erklärung der obigen Auszüge: "Die 'erzeugte' Achtheit als die systembegrenzende Anzahl der Kern-Einmaligkeit selbstregenerativen symmetrischen Wachstums kann auf das Konto der fundamentalen Oktave einmaliger, interpermutativer ganzzahliger Effekte gehen, die als plus Eins, plus Zwei, plus Drei, plus Vier respektive minus Vier, minus Drei, minus Zwei und minus Eins identifiziert sind und die ganzen Zahlen Fünf, Sechs, Sieben und Acht charakterisieren." [3] Mit anderen Worten: Eine erste Annäherung lautet J = 0 . (Die Jell-O-Gleichung) Die Jell-O Strahlenschnittberechnung Die Jell-O Strahlenschnittberechnungen erfordern die Lösung integraler Gleichungen und die Simulation von Markov-Ketten [6], weshalb sie nicht effizient gerechnet werden können. Wir haben ermittelt, daß die Lösungen linearzeitlich reduzierbar sind auf das Problem des 'reisenden Kaufmanns' [e], in dem n der Anzahl von Jell-O Molekülen entspricht, weshalb wir davon ausgehen, daß das Ray Tracing von Jell-O nur auf Supercomputern praktizierbar ist [5]. Gerätschaften Eine Testlauf wurde auf einer VAX 11/780 unter UNIX ausgeführt. Um ein Bild unter Verwendung der vollen "Jell-O Engine Simulation" zu erzeugen, ist nach unserer Einschätzung 1 CPU-Äon Cray-Rechenzeit und eine Menge harter Arbeit erforderlich. Wir führten bis zur Fertigstellung dieses Artikels verschiedene vereinfachende Approximationen durch. Als eine erste Annäherung modellierten wir einen Gelatine- Würfel, gesteuert von einer Jell-O Gleichung erster Ordnung, mit bedacht gewählten Flächen-Eigenschaften (Farben = (0, 255, 0). Das Frontispiz für den Artikel wurde mit diesem Modell erzeugt. Wir arbeiten an der Ausführung einer kompletten Jell-O Engine in LISP-"Geschmäckern". In Kürze werden wir mit der Berechnung eines 100 x 100-Bilds einer Schale Limonen-Jell-O unter Verwendung eines Zimmers voller Amigas beginnen [4]. Bis das Bild zur SIGGRAPH fertig sein wird, sind noch einige Stündchen rumzubringen. Schlußfolgerungen Jell-O läßt sich abbilden, wie auch eine Anzahl anderer ähnlicher Objekte einschließlich Mandrills, Glaskugeln und Teekannen. Die Möglichkeiten der Komposition und Animation sind nur durch unsere Vorstellungskraft beschränkt (persönliche Aussage von Lance Williams, 1980). Die "Dessert Food Division" versucht, die hier beschriebene Methode in Hinsicht auf andere Gelatine-Marken zu verallgemeinen. Zukünftige Forschungen werden sich mit der Entwicklung von Algorithmen für das Ray Tracing von Pudding und anderen Nachspeisen beschäftigen. Ein weiteres fälliges Problem ist die Einbeziehung von Früchten in Jell-O, genauer gesagt: frischer Ananas und Kiwifrüchte. Jell-O ist - visuell ansprechend - futuristisch - hydrodynamisch gebunden - geschmackvoll - läßt sich mit anderen Objekten verbinden Danksagung: Dank an Paul Haeberli für Hinweise zu diesen Forschungen und an H. B. Siegel für maßgebliche Beobachtungen. Dem SIGGRAPH Technical Committee gebührt Dank für die Einsicht, "daß es immer Platz für Jell-O geben muß". Referenzen: [1] Barr, A. H. Ray tracing deformed surfaces, SIGGRAPH 86 Proc. 20. 4 (Aug. 1986), 287-296. [2] Blinn, J. F. Computer display of curved Surfaces. Ph. D. thesis. Computer Science Dept., univ. of Utah, Salt Lake City, 1978. [3] Fuller, R. B., Synergetics. MacMillan, New York, 1975, p. 125. [4] Graham, E. Graphic scene simulations. Amiga World (May- June 1987), 18-95. [5] Haeberli, P. and Heckbert, P. A Jell-O calculus, ACM Trans. Graph. (special issue on ray tracing moist surfaces). Submitted 1872. To be published. [6] Kaijya, J. T., The rendering equation. SIGGRAPH 86 Proc. 20, 4 (Aug. 1986), 143-150. [7] Plastock, R. A. and Kalley, G. Schaum's Outline of Computer Graphics. McGraw-Hill, New York, 1986. [8] Sales, S. The Soupy Sales Show, 1966. [9] Weller, T. Science Made Stupid, Houghton Mifflin, Boston, Mass., 1985. [10] Whitted, T. An improved illumination model for shaded display, Commun. ACM 23, 6 (June 1980), 343-349 Erläuterungen für Nicht-Fachleute: [a] Ray Tracing (Strahlenrückverfolgung) ermöglicht ein Höchstmaß an Realismus bei der Erzeugung synthetischer dreidimensionaler Szenarios und ihrer zweidimensionalen Abbildungen. Der Verlauf, den Lichtstrahlen gewöhnlich auf dem Weg ins Auge nehmen, wird bei diesem Verfahren umgekehrt. Ausgehend von einem "Augpunkt" tasten Vektor- Strahlen ein innerhalb eines dreidimensionalen Koordinatensystems mathematisch beschriebenes Szenario ab. Der Bildschirm wird als Ebene angesehen, den die Vektorstrahlen auf dem Abtastweg zwischen dem Augpunkt und den Objekten der Szene schneiden. Hat ein Vektorstrahl eine bestimmte Grenzbedingung erreicht, z.B. 'matte Oberfläche' oder 'Himmel', wird der Farbwert für das entsprechende Pixel am Bildschirm ausgegeben. Anschließend wird der Vektorstrahl durch das nächste Pixel vorwärtsgerechnet. An 'spiegelnden' Oberflächen wird der Strahl so lange umgelenkt, bis eine Grenzbedingung erreicht ist. An 'transparenten' Oberflächen wie Glas oder Wasser wird der Strahl, entsprechend einem zugeordneten Brechungsindex, in zwei Strahlen (reflektierter und gebrochener) geteilt, die jeweils weiter verfolgt werden, bis eine Grenzbedingung erreicht ist. Zusätzliche Vektor-Fühler für Lichtquellen und Schattenbereiche verfeinern den Raumeindruck in der Abbildung. Im Gegensatz zu 'Rendering'-Algorithmen, in denen Objekte facettenartig aus Flächenstücken zusammengesetzt und schattiert werden, erfordern Ray Tracing-Algorithmen einen hohen Aufwand an Rechenzeit. [b] Als Primitives bezeichnet man geometrische Grundelemente wie Kugel, Würfel, Prisma, Pyramide, Kreisring u.ä., die sich durch einfache Formeln beschreiben lassen und aus denen sich nach dem LEGO-Prinzip komplexe Objekte zusammensetzen lassen. [c] Pixar ist eine auf Computergrafik spezialisierte Division der Lucasfilm Corp. (San Rafael, CA), in der mächtige Grafik-Hardware (Pixar Image Computer) und Software entwickelt und produziert wird. Pixar- Animationen wie "Luxo jr.", "Tin Toy" oder "Red's Dream" gehören zu den Meilensteinen der Computergrafik. [d] Eine Art pulsierende, dreidimensionale Matrix. [e] Ein kniffliges Problem der Kombinatorik, bei dem es die jeweils kürzeste Route eines Kaufmanns für eine Reise durch verschiedene Städte zu finden gilt. Mit zunehmender Anzahl der Städte (n) wächst die Anzahl an Kombinationsmöglichkeiten rasch ins Gigantische. Quelle: Communications of the ACM, Vol. 31; Reprint aus ACM Computer Graphics, Vol. 21, Juli 87. Originaltitel: Ray Tracing Jell-O Brand Gelatin Übersetzung: Peter Glaser, LABOR

[Contrib] [Labor] [Nummer 3]    DER WACKELPUDDING-ALGORITHMUS