19.07.2019

1

Teil 7: 3D-Spiele7a: Virtuelle Welten

Erstes 3D-Spiel

● Monster-Maze(Sinclair ZX81)

● ZX Spectrum “Dersagenhafte Schatz des Minotaurus”

Malcolm Evans

Historie

● Elite (C64), erstes3D-Weltraumspiel

● DOOM

▪ “Quasi-3D-Spiel”

▪ Nur vertikaleWände

▪ 2D-Leveldesign

● John Carmack(ab 2013 Oculus)

● John Romero(bis 1996)

(To win the game you must kill me, John Romero)

Painters Algorithm(DOOM)

● Optimierung durch Binary Space Partitioning

Painters Algorithm(DOOM)

● Optimierung durch Binary Space Partitioning

19.07.2019

2

Historie II

● 1992: Alone in the dark(halbgerenderteSzenen)

● Tomb Raider

Spiele-Engine

● Darstellung der 3D-Objekte

● Animation der 3D-Objekte

● Spielablaufsteuerung (Skripte)

● Physikalisches Verhalten (fallende Objekte)

● Spielinhalt meist in speziellen Dateiformaten(nicht Teil der Engine)

▪ Z.B. DOOM (WAD-Dateien)

▪ Ggf. Herausgabe von Tools zum Selbstdesign (Mod)

Beispiel

● SCUMM (Lukas Arts)Script Creation Utility for Maniac Mansion

● SCUMM-VM (Virtuelle Maschine zum Spielen von Lukas Arts Adventures)

▪ (keine Verletzung des Copyrights, Original wird benötigt)

Beispiele

● Quake-Engine

● OGRE

● CryEngine

● Unity

● Gamebryo (Creation Engine)

● …

Modding Tools

● Wird von Spielehersteller angeboten

● Wirtschaftlicher Hintergrund:

▪ Spiel attraktiver machen

▪ Erweiterungen werden kostenlos (!) durchPrivatpersonen bereitgestellt

▪ Erhöht die Lebenszeit des Spieles

„Mods (modifications) of a computer game can be made by a person who has legally acquired a licensed copy of the game and exclusively for the purpose of its use on the hardware belonging to the person performing the modification or persons to whom the modification was given on non-commercial basis (such as freely over the Internet).

This means that the person who makes a mod for a computer game can use this modification exclusively on non-commercial basis.

The author of the mod retains authorship and exclusive rights on the mod. However, the resources used for development of the given mod belong to another person. As such, the mod does not wholly belong to the author of the modification, who does not have full control over it (such as for commercial use).“

Statement on Tesnexus

19.07.2019

3

Objekte

● World-Objekte und Charaktere (Menschen, Tiere, Monster)

● Basisobjekt

● Meshes (near, far, Inventar, ….)

● Eigenschaften der Instanz (Scale, Position, etc…)

● Scripte

● AI (bei Charakter)

● Inhalt (z.B. bei Kisten)

● …

Gollum‘s Kiste

ScriptName RiddleChestScript

Short controlvar

Short button

Begin OnActivate

If ( controlvar == 0 )

MessageBox "Voiceless it cries, wingless flutters, toothless

bites, mouthless mutters. What is it?",

"Bat", "Old woman", "Wind", "Wraith"

Set controlvar to 1

ElseIf ( controlvar > 1 )

Activate

EndIf

End

Begin GameMode

If ( controlvar == 1 )

Set button to GetButtonPressed

If ( button == -1 )

Return

ElseIf ( button == 2)

MessageBox "Your answer was correct."

Activate

Set controlvar to 2

Else

MessageBox "Your answer was wrong."

Set controlvar to -1

EndIf

EndIf

End

Script

Story

Referenzen

19.07.2019

4

Patches Middleware

● Fertige Engines (z.B. Gamebryo)

● Speedtree

● Havok / NVidia GameWorks

● Facegen

Speedtree

● Wind

● Dimming(Baumkrone)

● Sanftes Einblenden der Billboards für entfernte Bäume

Havok-Physics2015 von Microsoft gekauft

Havok-ClothesNVidia HairWorks

19.07.2019

5

NVidia HairWorks Facegen

© Ingo Fröhlich

Virtuelle Welten Virtuelle Welten

Aufbau des Meshes

● Direct-X: Basierend auf Triangles

Triangle-Setup

● Sammlung der Vertices-Liste

▪ Koordinaten: x,y,z

● Jeder Vertex kann zu beliebig vielen Triangles gehören

● Ein Triangle:

▪ Einfachste mögliche Fläche

▪ Immer planar

▪ Einfache Interpolationen

19.07.2019

6

Tri-Strips

● OpenGL-Standard

● Speicher-platz

Problem der Verdeckungen

● Starre Reihenfolge wieim Painters Algorithm

● Erlaubt keine Drehungim Raum

z-Buffer

● Brute-force-Algorithmus

● Geht jedes Triangle Zeile für Zeile durch und vergleicht den Abstand (z) mit dem z-Buffer

z-Buffer

● Falls Triangle-Pixel näher, wird z-Buffer-Pixel ersetzt

Texturierung

● Generell:

● Texel -> Pixel

● Texturen (u,v)-Koordinaten

● Vertizes haben (x,y,z) und (u,v)

● Punkte in Triangle-Fläche (x‘,y‘,z‘) wird in (u‘,v‘) umgerechnet-> lineare Transformation

Mesh-Objekte

Kleid vonwww.tesnexus.com/downloads/file.php?id=20232

19.07.2019

7

Body-Texture

© Ingo Fröhlich

Body-Texture

● Texture als(u,v)-Ebene

Texturen-Sampling

● Point-Sampling:

▪ Macht bei der Maxifikation aus den Texeln grobe Blöcke

● Bilineare Filterung:

▪ Interpolation von 4 Texeln(2 aufeinanderfolgende lineare Interpolationen)

● Theorem von Nyquist

▪ Informationsdichte darf nicht größer sein als Abtastdichte

MIP-Maps

● Multum In Parvo

● dds Dateiformat

19.07.2019

8

Trilineares Filtern

● Behebt harte Übergänge zwischen den LOD-Stufen

Vergleich

Anisotrope Filter

● Berücksichtigt Entfernung und Verkippung

Kantenglättung(Anti-Aliasing, AA)

● Verhindert Treppeneffekt an den Objektkante

● SSAA, Super-Sampling AA

▪ Full-Scene Super-Sampling

▪ Komplettes Bild wird in höherer Auflösung berechnet

● MSAA, Multi-Sampling AA

▪ Wie SS, aber nur Mischwert

Shading

● Schattierung: Beleuchtung des Objektes, abhängig vom Winkel der Beleuchtungsquelle + Normalenvektor

● Flat-Shading: Nehmen den Normalenvektor des Triangles

19.07.2019

9

Smooth Shading

● Normalenvektoren an den Vertizesunterschiedlich

▪ Gouraud-Shading: Interpolation von Farben

▪ Phong-Shading: Interpolation der Normalenvektoren

Phong-Shading

Smooth Shading

● Normalenvektoren an den Vertizesunterschiedlich

▪ Gouraud-Shading: Interpolation von Farben

▪ Phong-Shading: Interpolation der Normalenvektoren

Normal-Maps

● Bump-Map (Höhe)

● Normal-Map: Normalenvektorals RGB-Wert

Tesselation

● DirectX11 bzw. OpenGL 4.0

● Zerlegung in viele kleine Triangles per Displacement Map

Schatten

● Vergleich von z-Buffer (Tiefe) mit Schattenkonus

● Setzen eines Flags im „Stencil Buffer“

19.07.2019

10

Level Of Detail (LOD) Level Of Detail (LOD)

Terrain ModelsTerrain Models Terrain Models

Digitale Elektronik (SS 2010)

Die Kunst liegt in der Optimierung der

Vertices(Adaptive Gitter)

19.07.2019

11

Irregular mesh Delaunay-Triangulation

● Gebräuchliches Verfahren, um Punkte im N-dimensionalen Raum (auch N>3) zu triangulieren

▪ Bedingung: im Umkreis eines Triangles darf kein weiterer Punkt vorhanden sein

▪ Erzeugt möglichst stumpfe Dreiecke

▪ Erzeugt komplette Hülle

● Source Code (C): http://paulbourke.net/papers/triangulate/

● Wissenschaftliche Anwendung: QHULL (bis 128 Dimensionen)

Triangulate

Efficient Triangulation Algorithm Suitable for Terrain Modelling

or

An Algorithm for Interpolating Irregularly-Spaced Data

with Applications in Terrain Modelling

Written by Paul Bourke

Presented at Pan Pacific Computer Conference, Beijing, China.

January 1989

Abstract

A discussion of a method that has been used with success in terrain modelling to

estimate the height at any point on the land surface from irregularly distributed samples.

The special requirements of terrain modelling are discussed as well as a detailed

description of the algorithm and an example of its application.

Teil 7: 3D-Spiele7b: GPUs (Grafikkarten)

Historie

● Erste 2D-Beschleunigung:

● Windows 3.0, Zeichnen von Linien, Scrollen von Text

● VESA BIOS extensions (VBE, Framebuffer)

ET-4000 von Tseng Labs (für den 486)

Vesa Local Bus

● 40 MHz Taktrate, synchron

● Z.B. Einsatz mit dem DX2-80 von AMD

19.07.2019

12

PCI-Bus

● PCI-Bus (asynchron)

● Video7, S3, ATI, Cirrus, Diamond und Matrox

Matrox Millenium

Nvidia

● NV1, erster 3D-Beschleuniger

● Keine Triangles, sondern Splines (Bezier-Kurven)

VooDoo von 3dfx (1996)

● 3d-Beschleuniger ohne 2d-Funktionen

● Erste Beschleunigerkarte für den Massenmarkt

● Ca. 370DM

● Benutzt Triangles als Beschreibung

Riva 128 (Nvidia)

● Auch: NV3

▪ 16-Bit Frame- bzw. Z-Buffer

▪ Höhere Auflösung als VGA (VooDoo)

AGP (Accelerated Graphics Port)

● 1997 vorgestellt

● „Spezieller“ PCI-Slot (PCI 2.1 mit 66MHz)

● DIME=„Direct Memory Execution“

19.07.2019

13

Nvidia Geforce 256

● Transform & Lighting

▪ (T&L)

OpenGL

● API (applicationprocess interface), versteckt die eigentliche Hardware, bzw. Treiber

● Offen, z.B. auch für Linux

● Gegründet 1992

▪ 3dlabs, Apple, ATI, IBM, Intel, Nvidia, Microsoft (2003 ausgeschieden)

DirectX

● Verschiedene Komponenten, u.a. Direct3D

● API um Szene aufzusetzen

▪ Vertizes

▪ Triangles

▪ Texturen

Geforce3 (2001)

● Pixel- und Vertexshader auf einem Chip

● DirectX 8.0

● Shaderfrei programmierbar

Shader Pipeline

● T&L wird zum Vertex Shader

http://www.lighthouse3d.com/opengl/glsl/

DirectX 8

● Programmierbare Shader für realistische Wasserdarstellung

▪ Z.B. Morrowind (2002)

● ATI Radeon 8500 (DirectX 8.1)

19.07.2019

14

Shader-Programmierung

● DirectX: HLSL

● OpenGL: GLSL

● Nvidia: Cg

Shader-Programmierung mit HLSL(ab DirectX 9.0)

sampler2D g_samSrcColor;

float4 MyShader( float2 Tex :

TEXCOORD0 ) : COLOR0

{

float4 Color;

Color =

tex2D( g_samSrcColor, Tex.xy);

return Color;

}

technique PostProcess

{

pass p1

{

VertexShader = null;

PixelShader =

compile ps_2_0 MyShader();

}

}

Color.r = 1;

Color.rgb = 1;

Color.rb = 1;

Color = 1;

Tex.x = 0

Tex.x = 1

http://www.facewound.com/tutorials/shader1/

Color = tex2D( g_samSrcColor,

Tex.xy)*3;

Color = tex2D(

g_samSrcColor, Tex.xy);

Color.r = Color.r*2;

Color = tex2D( g_samSrcColor, Tex.xy);

Color.r = Color.r*sin(Tex.y*100)*2;

Color.g = Color.g*cos(Tex.y*200)*2;

Color.b = Color.b*sin(Tex.y*300)*2;

Tex.y = Tex.y +

(sin(Tex.x*200)*0.01);

Color = tex2D( g_samSrcColor,

Tex.xy);

Color = tex2D( g_samSrcColor, Tex.xy);

Color += tex2D( g_samSrcColor,

Tex.xy+0.001);

Color += tex2D( g_samSrcColor,

Tex.xy+0.002);

Color += tex2D( g_samSrcColor,

Tex.xy+0.003);

Color = Color / 4;

Color.a = 1.0f;

Color = tex2D( g_samSrcColor, Tex.xy);

Color.rgb = (Color.r+Color.g+Color.b)/3.0f;

if (Color.r<0.2 || Color.r>0.8) Color.r = 0.0f; else Color.r

= 1.0f;

if (Color.g<0.2 || Color.g>0.8) Color.g = 0.0f; else Color.g

= 1.0f;

if (Color.b<0.2 || Color.b>0.8) Color.b = 0.0f; else Color.b

= 1.0f;

Update Morrowind Water Shader (2008)

19.07.2019

15

DirectX 10 (Vista)

● Shader-Model 4.0

● GT200 Grafikchip (GTX280)

▪ 1,4 Milliarden Transistoren

▪ 280 Streamprozessoren

Unified Shader

GT200

● 10 Thread Processing Cluster

▪ Je 3x8 Stream-prozessoren

Raster Operator

Raster Operators (ROPs) handle several chores near the end of the ofthe pixel pipeline. ROPs handle anti-aliasing, Z and color compression, andthe actual writing of the pixel to theoutput buffer.

Thread Processing Cluster

Die von NVIDIA vorgestellte CUDA-Architektur (Compute Unified Device Architecture) macht Gebrauch von massenhaft ablaufgesteuerten Threads, wodurch die zur Verfügung stehenden Ressourcen effizient genutzt werden können. Der hohe Grad der Parallelisierung spiegelt sich auch im Hardware-Design einer solchen GPU wieder: Die GPU GT200, die z.B. in der Grafikkarte NVIDIA GeForce GTX 280 zum Einsatz kommt, besteht aus einem Thread-Verteiler, L2-Cache, mehreren Raster Operation Processor (ROP) sowie aus 10 Thread Processing Clustern (TPC). Ein TPC besteht aus 3 x 8 Stream-Prozessoren mit jeweils eigenem Speicher, gemeinsam genutzten Textur-Einheiten sowie einer Steuereinheit für den gesamten TPC. Aufaddiert besteht ein GT200-Kern also aus 240 Stream-Prozessoren, die zu je 24 Kernen 10 TPC bilden

Grafikkarten/chip-Hersteller

● S3: Bis in die 90er führender Hersteller von Grafikchips

▪ Grafiksparte später von Via übernommen

● 3dfx: 1994 mit Risikokapital gegründet

▪ Spätere Rechtsstreitigkeiten zwischen Nvidia und 3dfx

▪ 3dfx 2000 von Nvidia aufgekauft

● 3dlabs: 1994 gegründet, 2002 von Creative Labs gekauft

19.07.2019

16

Grafikkarten/chip-Hersteller

● Nvidia:

▪ 1993 gegründet

▪ 2008 Übernahme von Ageia (PhysX)

● Matrox:

▪ Familienfirma seit 1976 aus Kanada

▪ Heute nur noch im Firmenbereich (Medizin) tätig

● ATI:

▪ 1985 mit 300.000US$ Startkapital gegründet.

▪ Z.B. VGA-Wonder

▪ 2006 für 5,4Milliaren US$ von AMD gekauft

GPGPU(General Purpose

Computing on Graphics

Processors)

● Fermi-Architektur

Fermi-ArchitekturOpenCL

● Offener Standard für (wissenschaftliche) parallele Berechnungen (nicht nur auf Grafikkarten)

● 2 Bestandteile:

▪ Code, der auf der GPU läuft (repräsentiert durch Kernel)

▪ Code der auf dem Host läuft, und welcher die Kernel aufruft

Addition von Vektoren (klassisches C)

void vector_add_cpu (const float* src_a,

const float* src_b,

float* res,

const int num)

{

for (int i = 0; i < num; i++)

res[i] = src_a[i] + src_b[i];

}

Quelle:http://opencl.codeplex.com/wikipage?title=OpenCL%20Tutorials%20-%201

OpenCL-Kernel

__kernel void vector_add_gpu

(__global const float* src_a,

__global const float* src_b,

__global float* res,

const int num)

{

const int idx = get_global_id(0);

if (idx < num)

res[idx] = src_a[idx] + src_b[idx];

}

Single Instruction, Multiple Data (SIMD)

19.07.2019

17

Globaler und lokaler Speicher

__global

www.khronos.org/developers/library/overview/opencl_overview.pdf

Beschreibung des Kontextes

cl_int error = 0; // Used to handle error codes

cl_platform_id platform;

cl_context context;

cl_command_queue queue;

cl_device_id device;

// Platform

error = oclGetPlatformID(&platform);

if (error != CL_SUCCESS) {

cout << "Error getting platform id: " << errorMessage(error) << endl;

exit(error);

}

// Device

error = clGetDeviceIDs(platform, CL_DEVICE_TYPE_GPU, 1, &device, NULL);

if (err != CL_SUCCESS) {

cout << "Error getting device ids: " << errorMessage(error) << endl;

exit(error);

}

// Context

context = clCreateContext(0, 1, &device, NULL, NULL, &error);

if (error != CL_SUCCESS) {

cout << "Error creating context: " << errorMessage(error) << endl;

exit(error);

}

// Command-queue

queue = clCreateCommandQueue(context, device, 0, &error);

if (error != CL_SUCCESS) {

cout << "Error creating command queue: " << errorMessage(error) << endl;

exit(error);

}

Buffer zur Kommunikation mit dem Host

const int size = 1234567

float* src_a_h = new float[size];

float* src_b_h = new float[size];

float* res_h = new float[size];

// Initialize both vectors

for (int i = 0; i < size; i++) {

src_a_h = src_b_h = (float) i;

}

const int mem_size = sizeof(float)*size;

// Allocates a buffer of size mem_size and copies mem_size

bytes from src_a_h

cl_mem src_a_d = clCreateBuffer(context, CL_MEM_READ_ONLY |

CL_MEM_COPY_HOST_PTR, mem_size, src_a_h,

&error);

cl_mem src_b_d = clCreateBuffer(context, CL_MEM_READ_ONLY |

CL_MEM_COPY_HOST_PTR, mem_size, src_b_h,

&error);

cl_mem res_d = clCreateBuffer(context, CL_MEM_WRITE_ONLY,

mem_size, NULL, &error);

// Creates the program

size_t src_size = 0;

const char* path = shrFindFilePath("vector_add_gpu.cl",

NULL);

const char* source = oclLoadProgSource(path, "",

&src_size);

cl_program program = clCreateProgramWithSource(context, 1,

&source, &src_size, &error);

assert(error == CL_SUCCESS);

// Builds the program

error = clBuildProgram(program, 1, &device, 0, 0, 0);

assert(error == CL_SUCCESS);

// Extracting the kernel

cl_kernel vector_add_kernel =

clCreateKernel(program, "vector_add_gpu", &error);

„main()“

19.07.2019

18

Buffer als Argumente setzen

clSetKernelArg(vector_add_k, 0, sizeof(cl_mem),

&src_a_d);

clSetKernelArg(vector_add_k, 1, sizeof(cl_mem),

&src_b_d);

clSetKernelArg(vector_add_k, 2, sizeof(cl_mem),

&res_d);

clSetKernelArg(vector_add_k, 3, sizeof(size_t), &size);

clEnqueueNDRangeKernel(queue, vector_add_k, 1, 0, 512,

0, 0, 0, 0);

float* check = new float[size];

clEnqueueReadBuffer(queue, res_d, CL_TRUE, 0, mem_size,

check, 0, 0, 0);

Bsp: PhysX

● Bewegungen, Rauch, Flüssigkeiten (SmoothedParticle Hydrodynamics), Explosionen

Exkurs: Hydrodynamic-Anwendungenin der Physik

(in diesem Bsp. Ohne GPU)

www.aip.de/People/MSteinmetz/Movies.html