Scaling Worlds: A project for CSC 570R - 3D Data Acquisition and enhancement
by Spencer Roberts
Dr. Z. Wood, Winter 2006
Background
I was inspired by several games I have played as well as google earth to try to make a dynamic system that would allow a character to transition from space to the surface of a planet completely realistically without any loading. The problem with typical techniques for drawing spheres is that stacks around the equator tend to be significantly larger than those around the polls as you can see in the image below. A general solution would require all the faces to be approximately the same size. Also worlds are huge the entire world obviously cannot have terrain and textures loaded into memory and drawn at the same time. A general solutions requires a means to transition between zones of interest on the planet model. Since I started out with such a huge concept, I decided to one-up myself and make the system general to not only include planets but any astronomically large object and contain a general scheme for dynamically deciding when to scale these objects up to a larger size.
Goals
The Algorithm
The basic design for the system was an exorcize in object oriented design. I Developed two interfaces, drawable and scaleable. Naturally drawables can be drawn and scaleables can be scaled. The main code does not need to know what it is drawing or where it is only responsible for maintaining the clipping plane (explained in results section) and scaling scaleables when appropriate. Scaleables have a method called "getSQDist" which gets the squared distance to the scaleable from the current camera position. The main code maintains a priority queue of squared distances with pointers to scaleables and a list of scaleables in the scene. Each display tick, the program goes through the list of scaleables and draws them. Drawing a scaleable has the effect of drawing all drawables that would represent that scaleable at that time step. For example, a planet is expressed as a sphere when you are far away and as you approach it breaks into what I call 'grids.' Each of these grids are then drawn individually. Every time the user moves the camera something might need to be scaled. The main program checks the distance that the user has traveled against the smallest squared distance in the scales priority queue. The program scales all objects until the smallest distance on the priority queue is greater than the distance traveled and then updates the distance traveled and does some housekeeping to keep the priority queue consistent.
The next challenge was to create a decent sphere approximation using grids. I decided to take a cube and subdivide each face and push the resulting vertices onto the sphere by centering the cube about the origin and normalizing the points. This created the nice shape you see in the figure below.
Results
After spending two full days of programming chasing what I thought was a bug in my code, I realized the obvious problem that my scheme had. There is no way to consistently assign neighbors on a cube so that this->up->down == this for all faces. This broke one of my major assumptions and ruined my original plan for terrain height map and texture generation as well as transition from zone to zone. In the face of that catastrophic failure, I focused on simply making a per-zone texture and height map generation. As you can see in the images at the top of this page, I still have not gotten the bugs out of the texture generating method.
I wrote a lot of code to recursively subdivide the planet down to some threshold and I built the texture and height map generation on these ideas. The intention was to compute the height map and textures for the planet down to a resolution of about 4 times and then write that granularity out to disk and load sections below the second as the user passed over them. If I use a terrain width of 8, the second subdivision of the planet had more than 24,000 faces. The third subdivision would theoretically have 1,570,000 faces but my computer runs out of memory before it can ever build that many. What that means is all of my recursive subdivision code is effectively worthless since I already had the second subdivision calculated.
On the plus side, the method for scaling the planet using the scales priority queue worked very well, and consistently scales the planet up and down and only calls the scale method when the planet approaches the range at which it will need to be scaled.
I added two other features to support actually viewing the objects. First the clipping plane is partially dependent on the distance to the nearest scaleable and maxes out at the radius of the nearest scaleable. The clipping plane is at 1 to 20 miles until you approach a planet so that you are less than 10 miles from the surface, at this point it scales the clipping plane exponentially back to the radius of the object. Since the clipping plane is closer to the viewer than to the planet (which may be more than 100,000 miles away) I need to draw the planet so that it is still visible. I do this by placing the planet on the clipping plane and increasing its radius as it approaches. This gives the appearance of the planet approaching when in fact, it is simply getting larger. The second feature was to limit the speed of the viewer to a proportion to the distance to the nearest scaleable. This makes it theoretically impossible to fly through a planet.
I wasted a lot of coding effort on this project debugging problems that turned out to be fundamental flaws in my design and then failing to incorporate code from other projects and being forced to re-invent the wheel (sometimes a lop-sided wheel...). I tried for a unique project without using research in the field to guide me and I found the project was more than could do in a quarter. I am going to continue to work on the project and see what I come up with in the near future.
The source code and windows compiled binary are located here.
Controls
The controls on this application are relatively simple but sometimes finicky.