Real-Time Massive Model Rendering

Jean-Daniel Nahmias

Supervised by Anthony Steed

Computer Science Department, University College London

Gower Street, London WC1E 6BT, UK

j.nahmias@cs.ucl.ac.uk

Master’s Thesis

Msc Vision, Imaging, & Virtual Environments

September 2002

Real-Time Massive Model Rendering

Jean-Daniel Nahmias

Supervised by Anthony Steed

Computer Science Department, University College London

Gower Street, London WC1E 6BT, UK

j.nahmias@cs.ucl.ac.uk

Master’s Thesis

Msc Vision, Imaging, & Virtual Environments

September 2002

Abstract

This report discussed various techniques to speed up rendering of large and complex virtual environments. It explores algorithms such as Hierarchical Spatial Subdivision as well as Occlusion Culling. The report analyses these algorithms as well as investigates ways of implementing them using recent consumer level Graphics Processing Units.

Disclaimer

This report is submitted as part requirement for the MSc Degree in Vision Imaging and Virtual Environments at University College London. It is substantially the result of my own work except where explicitly indicated in the text. The report may be freely copied and distributed provided the source is explicitly acknowledged.

1 Introduction_ 5

1.1 Organisation_ 7

2 Background Work_ 8

2.1 Visibility Determination_ 9

2.1.1 View Frustum Culling_ 12

2.1.2 Spatial Coherence 13

2.1.3 Temporal Coherence 17

2.1.4 Occlusion Culling_ 17

2.2 Level of Detail 20

2.2.1 Progressive Meshes [8] 22

2.3 Impostors 24

2.3.1 Per-Object Image Warping with Layered Impostors [5] 24

Figure 13 Example of remaining gap artefacts 26

3 Development Life Cycles 27

3.1 Requirements Analysis 28

3.1.1 Application Feature Set 28

3.1.2 Rendering Feature Set 28

4 Design_ 30

4.1 Code Base Design_ 31

4.1.1 Scene Graph_ 32

4.1.2 3DS Max Plugin_ 36

4.1.3 Application Code 39

4.2 Algorithmic Design_ 40

4.2.1 1^st Pipeline 41

4.2.2 2^nd Pipeline 42

4.2.3 3^rd Pipeline 42

4.2.4 4^th Pipeline 43

4.2.5 5^th Pipeline 45

5 Implementation_ 47

5.1 Choice of Language_ 47

5.2 OpenGL Issues & Getting the most out of the GPU_ 48

5.3 Oct-Tree Implementation Details 49

5.4 Other details addressed after testing_ 50

6 Testing and Evaluation_ 52

6.1 Testing_ 52

6.2 Evaluation_ 54

6.2.1 Windows Timing Functions 54

6.2.2 Evaluating the Rendering Pipeline 57

6.2.3 Finding Bottlenecks 58

7 Results 60

7.1 Benchmark System_ 60

7.2 Tuning Pipeline 3-5 by Balancing Oct-Tree_ 61

7.3 Tuning Pipeline 5 with Temporal Coherence_ 64

7.4 Rendering Pipeline Comparisons 66

8 Conclusion and Further Work_ 68

1 Introduction

There are various fields including Computer Aided Design and Scientific Visualization that require the interactive display of large and complex 3D virtual environments. There is a very strong motivation for the performance of the display of these systems to be high (i.e. Real-Time). The performance of display systems is usually measured in frames per second. This is the total number of images that are sent to the display in one second and is a g