REAL is computer graphics project expanding on both a class project originally used to display the Martian landscape, and an independent study of the OpenGL graphics application programming interface. The presentation will be on the problem of terrain performance in computer games, and efficiently generating terrain across a wide number of different computer configurations. The large number of vertexes used in three dimensional gaming terrains makes it necessary to find efficient algorithms to sort, hold, and find any vertex at any time.
The brute force method of terrain generation generates the vertexes during the programs execution, and holds them in memory to be displayed. When a frame is displayed using the brute force method all the vertexes, lines, and polygons in the entire frame are displayed, even those not visible by the viewer. The code for the brute force method is simple, straight forward, and can be very fast for smaller applications.
Oct-tree terrain generation uses a tree data structure to hold the vertexes of the terrain. Unlike the brute force method the Oct-tree loads all the points from an outside source. The oct-tree stores the points in a hierarchy of nodes, dividing the vertexes by a predetermined equation. Frames drawn using an oct-tree data structure display only the vertexes required by the user, making the processing time for the frame decrease, and the complexity Big O (log n). The code for the oct-tree method is far more complex and requires many more steps, but necessary for larger applications.
Linn Neilson, ’05 Mt. Vernon , IA
Major: Computer Science
Sponsor: Tony deLaubenfels