Date of Last Revision

2021-09-09 06:55:11


Computer Science - Systems

Degree Name

Bachelor of Science in Computer Science

Date of Expected Graduation

Fall 2015


In video games today, world geometry is often represented as a polygon mesh. While this representation is able to represent terrain, it must be done so using an elevation grid. For each X and Z location, an elevation grid stores the height of the terrain at that location. This has a major drawback: it is unable to allow terrain with overhangs and caves, and is unable to allow for destructible terrain. In this project, an alternative technique using voxels is explored to overcome these limitations for a game engine. A voxel is the 3D equivalent of a pixel and allows for 3D model manipulation by adding and removing discrete units. Because voxel objects require O(n^3) memory to represent, a number of challenges must be overcome to allow efficient manipulation, including effective use of cache memory, minimization of polygon count, efficient communication between the CPU and GPU, efficient collision detection when brute force methods require O(n^6) collision checks, and deletion of triangles from fixed-size Vertex Buffer Objects. The purpose of this project is to investigate and create solutions for these problems and successfully implement a simple game engine in C++ that allows for destructible terrain and terrain generation from mathematical formulas.

Research Sponsor

Yingcai Xiao

First Reader

Zhong-Hui Duan

Second Reader

En Cheng



To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.