Rendu 3D temps réel

Patrick Reuterpreuter@labri.fr

Pour DESS Ingénierie de l'Image

DESS Informatique Multimedia

Patrick ReuterVersion 1.2 2/10/2002

1-1 Préface - Interaction

Scène Image

Utilisateur

projection

Interaction:commence à 5 fps« temps réel » >12 fpsplus de difference >72 fps

fps: frames per second (taux de rafraîchissement)

interaction

1-2 Préface - Applications

ModélisationAnimationEnvironnements virtuelsJeux vidéo…

Graphics hardware: double tous les 6 mois

mais: scènes complexes demandent accéleration

1-3 Préface - Littérature

Tomas Möller, Eric Haines

« Real-Time Rendering »

www.realtimerendering.comISBN 1-568816-101-2

[Haines99]

Le processus du rendu d’une scène à l’écran

- caméra virtuel- objets 3D- textures image 2D à

l’écran- sources de lumière- interacteurs- …

2 The Graphics Rendering Pipeline

2 The Graphics Rendering Pipeline

ApplicationStage

GeometryStage

RasterizerStage

Bottleneck stage (Stage critique) détermine le fps final

Stages gérées par des unités différents

2-1 The Graphics Rendering Pipeline

- gère les interacteurs (clavier, souri, …)

- gère la détection des collisions

- gère les animations

- gère la physique de la scène (force feedback, déformations, vélocités, …)

- …

ApplicationStage

GeometryStage

RasterizerStage

(CPU operations)

2-2 The Graphics Rendering Pipeline

Model & ViewTransform

Lighting &Shading

Projection Clipping ScreenMapping

du Model Space pour ajouter 3D -> 2D (les objets en ajuster le champ

-> World Space du réalisme (projection or- dehors du champ de vue à la taille

-> Eye Space tographique ou de vue sont de la fenêtre

(Muliplications perspectivique) supprimés)

des matrices 4x4)

(per-vertex operations), consiste de 5 phases séquentielles:

ApplicationStage

GeometryStage

RasterizerStage

2-3 The Graphics Rendering Pipeline

- mettre les bonnes couleurs aux pixels

- utilisation des textures

- Z – buffering

- double – buffering

(per-pixel operations)

ApplicationStage

GeometryStage

RasterizerStage

3-1 Optimisation - Overview

ApplicationStage

GeometryStage

RasterizerStage

Bottleneck stage (Stage critique) détermine le fps final

Optimisation:

1) Identifier le Bottleneck stage2) réduire le temps d’exécution du

Bottleneck 3) mais aussi: charger les autres stages

avec plus de travail pour une qualité supérieure du

rendu

3-2 Optimisation – Identifier le bottleneck

- pas par simple benchmark du temps d’affichage :

mesure le temps d’exécution de tous les 3 stages

les 3 stages doivent être testés séparément

ApplicationStage

3-2-1 Optimisation – Identifier le bottleneck

- le CPU workload est 100% ? Bottleneck

- en OpenGL:

remplacer les commandes glNormal3 et glVertex3 par glColor3

plus de travail pour Geometry Stage et Rasterizer Stage:

pas de changement de fps bottleneck

tester le (CPU)

GeometryStage

3-2-2 Optimisation – Identifier le bottleneck

- éteindre la lumière: plus de performance? bottleneck

- augmenter la lumière: même performance? not bottleneck

- (ou tester les 2 autres stages)

tester le (plus difficile, parce queseulement la lumière n’affecteque le Geometry Stage)

RasterizerStage

3-2-3 Optimisation – Identifier le bottleneck

- diminuer la taille de la fenêtre:

plus de performance? bottleneck

-éteindre les textures, le brouillard, z-buffering, blending, …:

plus de performance? bottleneck

tester le

3-3 Optimisation du Bottleneck

Optimiser le temps d’exécution du bottleneck stage

- Application Stage

- Geometry Stage

- Rasterizer Stage

ApplicationStage

ApplicationStage

ApplicationStage

3-3-1 Optimisation du Application stage

- optimisation du code

- optimisation de la gestion de mémoire (allocation, cache, …)

- utilisation de plusieurs processeurs

- détection des collisions intelligente (hierarchy, bounding volumes (volumes englobantes), …)

- …

ApplicationStage

GeometryStage

GeometryStage

3-3-2 Optimisation du Geometry stage

- transformation: regrouper les transformations

(le moins de multiplications des matrices 4x4 possible)

- vertices (sommets) connectés

(Triangle Fans, Triangle Strips, Quad Strips)

3-3-2 Optimisation du Geometry stage OpenGL Triangle Fans

Rappel: GeometryStage dépend des

per-vertex operations

à la place de:GL_TRIANGLES0-1-2, 0-2-3, 0-3-4,0-3-4, 0-5-6(15 vertices)

transférer GL_TRIANGLE_FAN 0-1-2-3-4-5-6

(7 vertices)

3-3-2 Optimisation du Geometry stage OpenGL Triangle Strips

à la place de GL_TRIANGLES (8 * 3 = 24 vertices)0-1-2, 1-3-2, 2-3-4, 3-5-4, 4-5-6, 5-7-6, 6-7-8, 7-9-8

transférer GL_TRIANGLE_STRIP (2 + 8 = 10 vertices)0-1-2-3-4-5-6-7-8-9

3-3-2 Optimisation du Geometry stage OpenGL Triangle Strips

pour triangles connectés: réduire de 3n vertices jusqu’à n+2 vertices !

Mais: Trouver la meilleure configuration est un problème NP complet (bijection sur problème du voyageur de commerce)

Automatisation: SGI Performer et Optimizer, Algorithme STRIPE

3-3-2 Optimisation du Geometry Stage The STRIPE algorithm [Evans et al., 1996]

1.) Phase globale: Identifier les patchs quadrilaterales

2.) Phase locale: prendre le triangle avec degré minimum, continuer avec le triangle du degré minimum, etc.

ApplicationStage

GeometryStage

GeometryStage

3-3-2 Optimisation du Geometry stage (avec perte)

Simplification (Représentations Level of Detail)

(LOD, niveaux de détails)

réduire le nombre de polygones (triangles)

1.) pour les terrains: construire un terrain en LOD à partir des cartes d’élévations, p.ex. [Duchaineau et al. 1997, Hoppe98, Lindstrom et Pascucci 2001, Lindstrom et al. 1996]

2.) pour les objets fermés: simplification du maillage

3-3-2 Optimisation du Geometry stage (avec perte) - Simplification du maillage

Méthode la plus commune: Edge collapse, p.ex. [Eck et al. 95, Garland et Heckbert 98, Hoppe 96, Melax 98]

Application consécutive de cette méthode: Représentation en multirésolution du maillage, choisir le bon niveaux de détail en fonction du point de vue

3-3-2 Optimisation du Geometry stage (avec perte) - Exemple de simplification du maillage

Remarque: La sélection du niveau de détails se passe dans le Application Stage, mais elle est peu coûteuse

ApplicationStage

RasterizerStage

RasterizerStage

3-3-3 Optimisation du Rasterizer stage

- OpenGL backface culling

- éteindre z – Buffering où possible

- …

- diminuer la taille de la fenêtre (avec perte)

3-4 Optimisation générale

- le moindre précision possible (float à la place de double, …)

- éteindre les options non utilisées (brouillard, blending, …)

- minimiser les changements d’état OpenGL (trier par couleur, textures, triangles,

quadrilaterales, …)

-OpenGL: utiliser les display lists

- …

ApplicationStage

4 Equilibrer le Graphics Rendering Pipeline

GeometryStage

RasterizerStage

ApplicationStage

RasterizerStage

ApplicationStage

GeometryStage

30 ms 50 ms 30 msmieux:

40 ms 40 ms 40 ms

4 Equilibrer - Culling techniques

Point

de vue

View frustum cullingView frustum culling

Backface cullingBackface culling

Occlusion cullingOcclusion culling

ViewFrustum

4-1 Equilibrer – du Geometry Stage a l’ Application Stage

ApplicationStage

GeometryStage

GeometryStage

ApplicationStage

RasterizerRasterizerStageStage

RasterizerRasterizerStageStage

4-1-1 Equilibrer – Hierarchical View Frustum Culling

Par exemple: basé sur des spheres englobantes(bounding spheres)

4-1-1 Equilibrer – Hierarchical View Frustum

Culling

intersection

intersectionintersection

dehors

dedans

dedans dedans dedansintersection

Point de vue

View frustum test dans chaque noeud

4-1-2 Equilibrer – Hierarchical Backface

Culling

- Regroupement (Clustering) des polygones suivant

- proximité dans l’espace euclidienne- proximité dans l’espace des normales

- Performance du culling dans chaque noeud

par exemple [Kumar et al. 1996]

4-2 Equilibrer – du Geometry Stage et Rasterizer Stage a l’Application

Stage

ApplicationStage

GeometryStage

GeometryStage

ApplicationStage

RasterizerStage

RasterizerStage

4-2-1 Equilibrer – Occlusion culling

Le teapot lila n’est pas visible

Algorithmes les plus connus:

- Hierarchical visibility algorithm (pyramide Z-buffer) [Greene et al. 1993]

-HOM (Hierachical occlusion maps)

[Zhang et al. 1997]

A

D

H

FCB

E

G

H

B C D F G

EA

4-2-2 Equilibrer – Portal culling

A

D

H

FCB

E

G

H

B C D F G

EA

4-2-2 Equilibrer – Portal culling

A

D

H

FCB

E

G

H

B C D F G

EA

4-2-2 Equilibrer – Portal culling

A

D

H

FCB

E

G

H

B C D F G

EA

4-2-2 Equilibrer – Portal culling

A

D

H

FCB

E

G

H

B C D F G

EA

4-2-2 Equilibrer – Portal culling

A

D

H

FCB

E

G

4-2-2 Equilibrer – Portal culling

par exemple [Luebke et Georges 1995, Teller et Sequin1991]

4-3 Equilibrer – du Geometry Stage au Rasterizer Stage

RasterizerStage

GeometryStage

GeometryStage

RasterizerStage

ApplicationApplicationStageStage

ApplicationApplicationStageStage

4-3-1 Equilibrer – Appearance Preserving

Simplification

- Utilisation du Bump Mapping pour preserver les normales

Bump Mapping:

Multipass Rendering

Bump Map

Texture Map

4-3-1 Equilibrer – Appearance Preserving

Simplification

Objet originalImage de normales

Bump Mapping :

4-3-1 Equilibrer – Appearance Preserving

Simplification

Appearance Preserving Simplification [Cohen et al. 1998, Cignoni et al. 1998]

1.) Créer un maillage simplifié2.) Créer un Bump Map pour chaque face

1.) 2.)

4-3-1 Equilibrer – Appearance Preserving

Simplification

Amelioration: Silhouette Clipping [Sander et al. 2000]

-Utiliser le OpenGL Stencil Buffer pour ameliorer la silhouette

Autre possibilite: utiliser Displacement Mapping

5 Conclusions

- Séparation du Graphics Rendering pipeline en 3 Stages conceptuels

- Optimisation de chacun de ces Stages

- Équilibree des Stages

- autres techniques de rendu (Rendu basé Image)

- Discussion

6 Nouvelles techniques de rendu

- Apparition du “Rendu Basé Image” (Image Based Rendering)

- Description de la Scène par la Fonction plenoptique P

[McMillan et Bishop 1995]

- vue p de la Scene de chaque point (Vx, Vy, Vz) dans une direction (, ) au temps t

p = P(, , Vx, Vy, Vz, t)

Rendu Basé Image: Essai de reconstruire la fonction plenoptique P

6 Nouvelles techniques de renduRendu Basé ImageComment reconstruire la fonction plenoptique?

- p. ex.: entraîner avec des vues à l’entrée

après créer des nouvelles images pour autres (, , Vx, Vy, Vz, t)

6 Nouvelles techniques de rendu

Polygonal MeshesTexture MappingImpostorsPoint Rendering

(Surfels)Light Field RenderingLumigraphPlenoptic Function

GEOMETRY-BASED

RENDERING

IMAGE-BASED

RENDERING

6 Nouvelles techniques de rendu

Point Rendering (Surfels)- Modèles complexes: >> polygones, écran toujours pareil

projection:

mais:

projection

Plus de necessité de prendre des polygones

6 Nouvelles techniques de rendu

Point Rendering (Surfels)

Littérature: p. ex. [Pfister et al. 2000,Rusinkiewicz et Levoy 2000]

6 Nouvelles techniques de rendu

Point Rendering (Surfels)

106.795 Surfels 62143 Surfels 4544 Surfels

Level-of-Details

- Niveaux de détails gérés par un arbre BSP

6 Nouvelles techniques de rendu

Point Rendering (Surfels)

- Problèmes: remplissage des trous

- Solutions: boucher les trous en espace image (2D) ou espace objet (3D)

reconstruction de la surface (Surfaces paramétriques, surfaces implicites, Radial basis functions …)

6 Nouvelles techniques de rendu

Point Rendering (Surfels)

7 Definitions

Environnementvirtuel

Utilisateur

Immersion

Interaction

Realité virtuelle:

Synthèsed’image

Interacteurs

…

Son

Applications: - Géomarketing- Prototypage- Virtual design- Simulateurs- …

7 Définitions

Synthèsed’image

Modélisation Visualization

RenduTechniques d’Illumination

Rendu parPoints

……Rendu parPolygons

Raytracing RadiositéRendu basé

Image