part1 | part2

2. Implementation
This section describes how planets3D is written and how the implicit surface code is implemented within it.
planets3D is written in C++ and uses OpenGL and Glut. It is therefore platform independent. It has been tested on a Microsoft Windows and SGI Irix system . planets3D is based on an old 2D game that followed exactly the same rules. planets3D is a two player game and is turned based. Each player takes their turn to angle her ship and fire, trying to hit the other player's ship with their projectile. Inbetween the two ships are a variable number of planets which exert gravity on the fired projectile causing it to curve as it passes through space. This is where the challenge lies as the player must judge the curved path needed to hit the other player's ship. If the player hits the other player then they win that game and the program raises the player's score by one and resets the world. The planet positions and size are set randomly every time the world is reset. If the projectile goes too far away from the world origin or the projectile has been active for too long then the current player's turn ends.
If the projectile hits a planet then a crater/dent/hole is put into the planet. Holes can be subsequently added to any planet so that tunnels can eventually form. Whole sections of planets can be blown away (see figure 8). This adds interest to the game as a player could win by creating shots that pass through and loop round numerous planets.


Figure 8: In this screenshot from planets3D player 1 has blown considerable chunks from the Earth.

If a planet is hit then the vertex list for that planet needs to be updated. Therefore polygonization of the new implicit function is required. First the program adds a new sphere to the planet list. Each planet starts as one positive sphere. Every time it is hit a negative sphere (representing a hole) is added to the list. These holes can be made bigger or smaller depending on the force of the impact. The program then calls the Bloomenthal polygonizer [6] passing to it the planet to polygonize and the size of the cubes which are used to break down the surface. A larger cubesize means a less detailed planet and a faster redraw time. The Bloomenthal code then recreates the vertex list for that planet which can be subsequently drawn on the next frame. This polygonization process takes about a second depending on the speed of the processor being used.
The rest of the game engine is fairly simple with an idle function waiting for key presses and then calling a draw function which redraws the world. If the player fires a projectile the program calls the fired function which redraws the progress of the projectile until one of the conditions discussed previously is met and the function exits.
Collision detection between the projectile and the planets is calculated by taking the projectiles current position and its position on the previous frame and plotting a line between these two points. This line is then broken down a predefined number of times. These new points are then tested against the planet. If a point is found to be outside the main positive sphere of the planet then the program knows that the projectile has not hit the planet for that point. If the point is found to be inside the main positive sphere of the planet and inside any of the negative hole spheres of the planet then the program knows that the projectile has not hit the planet for that point. If the point is found to be inside the main positive sphere and outside all the negative hole spheres of the planet then the program knows that the projectile has hit that planet. A new hole sphere should then be added to the planet list and the planet repolygonized. A more accurate method of calculating intersections (and thefore collisions) with implicit surfaces is presented in [8].

2.1 Texturing of Implicits

Exstensive research into the texturing of implicit surfaces is presented in [9]. It involves the implicit object being broken down into patches which can be interactively textured. Further work is presented in [10].
The planets in planets3D are textured using the following method. As the the surface is polygonized the program takes the current point to be tested and calculates its surface co-ordinates. The vertical spherical co-ordinate can vary between 0 and 180 degrees and the horizontal spherical co-ordinate can vary between 0 and 360 degrees. These are converted to values between 0 and 1 and stored alongside the vertex's Cartesian co-ordinates. They then become the UV co-ordinates which are used by OpenGL to access the texture. The values are calculated by:

vertical co-ord = arctan(z/x)/(2*PI)

horizontal co-ord = arcsin(y/radius)/PI + 0.5

where x,y,z are the co-ordinates of the point to be tested and radius is the radius of the planet.
There is one known bug with this method, associated with the way OpenGL interpolates texture co-ordinates. An example planet polygon has horizontal texture co-ordinates of 0.4, 0.41 and 0.45. This polygon would be textured with the correct, small part of the texture. However, say we had a polygon of three vertecies with horizontal texture co-ordinates of 0.1, 0.2 and 0.9 (see figure 9). All the polygons running down one side of the planet have texture co-ordinates equivalent to the second example polygon. This is due to the nature of the maths and the values returned by arcsin and arctan. When OpenGL draws that polygon it interpolates the texture co-ordinates all the way across the texture instead of over one edge and into the following tile of the texture. When drawn the planet has the entire texture compressed into a thin strip running down one of its sides. This can be fixed by adding 1.0 to the low horizontal texture co-ordinates of any face found to have both high AND low texture co-ordinates. This shifts the low co-ordinates into the following texture tile. OpenGL then interpolates over the correct small area across two texture tiles.


Figure 9: OpenGl interpolates these three co-ordinates all the way across the texture even though they are only one face wide. They should be interpolated in the other direction, i.e. into the adjacent tile.

planets3D then takes the texturing one step further allowing for the inside of the planet to be coloured differently to the outside (see figure 10). This is done by dedicating a small strip at the bottom of the texure file to a desired colour(molten orange in the case of planets3D). The program works out if the point to be tested is on the surface or inside the surface. If it is on the surface the points vertical texture co-ordinate is bound between 0.1 and 1.0 thus excluding the inside colour strip. If the point is found to be inside the surface its vertical co-ordinate is bound to between 0.0 and 0.1 thus excluding the planet surface part of the texture.


Figure 10: An example of a textured planet in planets3D. Note that the inside is textured differently to the outside.

3. Implications of Deformation in Games

One thing that appears guarenteed concerning computers in the near future is that they will get faster. Assuming we had a computer of considerable processing power what would the ideal game world look, or indeed, feel like. What if the game environment was built from voxels, each one representing a molecule or even an atom. In this game world the player could shoot holes in anything (if a future human has any desire to shoot holes in things at all). Liquids could be built from voxels. However methods would be needed to contol all these voxels in some mathematical, logical and realistic manner. This is not an easy undertaking. Also memory presents a problem to the all-for-voxels method. At least one bit of storage will be needed to represent each voxel. If we had a universe made of voxels then we would need as many voxels as there are atoms in the real universe and consquently the entire real universe would be taken up representing the computer game world.
Our future game world could be like game worlds of today and built entirely from polygons, albeit in much higher detail. Objects could be deformed using polygon CSG methods like in "Red Faction". But polygons are not suited to modelling liquids or plants. As yet, nobody has produced a convincing polygonal tree within a game environment due to the large number of polygons needed to model a convincing tree. This isn't to say it would be impossibe, we are discussing a future computer with considerably more power, but its just not the best way of making a tree.
What about making a future game world from implicit surfaces? We would need new modelling tools (Maya and Max would need adapting) that could allow the artist to produce implicit surface environments. However with implicit surfaces we could put holes easily in anything. Also soft objects could be fairly easily simulated. However the problem with implicit surfaces is that the are not suited to producing clamped, flat surfaces like walls.
The ideal gaming environment of the future should use all three methods. Buildings and artificial objects could be built from polygons and deformable with polygon CSG operations. Plants could be made of voxels, wether these were massive oak trees or vast fields of grass. They could be modelled procedually, using fractal geometry. Soft, curved objects and possibly water would be made from implicit surfaces, allowing them to blob and flow through the game world.
This environment excludes the possibility of an as yet univented alternative (an alternative that will probably be invented). Games of today all too often fall into the trap of trying to mimic one aspect of reality. They should be artistically pulling the player into a new way of thinking and seeing. The physical properties of the game world may be one important part of this. The choice of modelling technique could define these properties. A game wall is normally two triangles because the wall is static. What if that wall had the possibility of changing its natural state. For example it could flow away, or bend and twist. The game player needs her point-of-view turning upside down and inside out before game worlds become real worlds with no rules.

4. Future Developments

Currently planets3D is a turned based game, the main consideration for this being that a small amount of time is needed to repolygonize the implicit surfaces. This takes place during the turn switching phase. However through experimenting with the various detail options within the game it is possible to get the polygonization process to run unnoticabally fast (real-time) especially on a high end processor. The implications for this are important. In terms of planets3D the game could be developed to run in real-time allowing for a faster, more arcade-like game where the players are continuously trying to shoot each other.
The fact that the polygonization can run in real time (albeit at low detail levels at present) means that it is possible for games, on a wider scale, to use implicit surfaces for visualization. How could this polygonization process be speeded up though? One method is presented in [5] and involves only polygonizing the part of the implicit surface that has changed. For a game like planets3D this would allow it to run faster but may not be ideal as each planet's polygon list will steadily get longer. However for a first person game like "Red Faction" this would be ideal.
One interesting improvement to the polygonization process would be to add an adaptive cube size. The polygons are calculated using a specified size of cube but what if this cube size could be changed dynamically by the polygonizer. The program could look at the density functions and determine wether a high or low detail level was needed. It could then chage the cube size for that part of the surface appropriately.
There are many other, smaller, improvements that could be made to planets3D to make the game more fun to play. Some of these include; rotating planets, power ups (eg laser sight), networked game play allowing two players to be on different computers, more than two players per game, split screen mode allowing a panel for each player and many other simpler graphical improvements.

5. Conclusion

As a finished game, planets3D (see figure 11) is fun to play and successfully uses implicit surfaces to allow the deformation of planets in space.
From the research presented in this report it can be seen that the scope exists for real time deformation in games. It is already being used by games like "Red Faction". This report has shown that implicit surfaces are a viable option for deformation in a simple game like planets3D. For a more complex game they are suited more to the sculpting, animation and deformation of soft, malleable objects.
However for implicit surfaces to be a viable real-time option, some development is needed to speed up the polygonization process.
There is a great deal of room for creative development in computer games and it is hoped that the game player of the future finds her gaming world a little more interactive than those of today.


Figure 11: planets3D finished.

6. Acknowledgements

Rob Edwards (Tutor)
Peter Comninos (Tutor)
Ian Stephenson
John Haddon
Michael Bonnington
Ben Morgan
James Fletcher

References

[1] Claudio Montani and Roberto Scopigno. Spheres-to-Voxels Conversion. Graphics Gems. Consiglio Nazionale delle Ricerche, Pisa, Italy.

[2] Hongsheng Chen and Shiaofen Fang. A Volumetric Approach to Interactive CSG Modelling and Rendering. Department of Computer and Information Science, Indiana University, Purdue University, Indianapolis.

[3] Prof. Peter Comninos. Notes on the Anima II System. 3D Computer Animation. National Centre for Computer Animation. Bournemouth University, Bournemouth, UK.

[4] Eric Ferley, Marie-Paule Cani and Jean-Dominique Gascuel. Pratical Volumetric Sculpting. iMAGIS a joint research project of CNRS/INRIA/UJF/INPG. iMAGIS-GRAVIR/IMAG, BP 53, 38041 Grenoble cedex 9 France.
www-imagis.imag.fr/Membres/Marie-Paule.Gascuel

[5] E. Ferley, Marie-Paule Cani and Jean-Dominique Gascuel. Virtual Sculpture. EUROGRAPHICS '99. iMAGIS/GRAVIR-IMAG, 220 rue de la chimie BP53, 38041 Grenoble Codex 9, France.
www-imagis.imag.fr/Membres/Marie-Paule.Gascuel

[6] Jules Bloomenthal. An Implicit Surface Polygonizer. Visual Information Technologies, George Mason Technologies, Fairfax, VA 22030-4444. jbloom@beauty.gmu.edu

[7] James Fletcher. Fletchercallin Ltd. Manchester, UK. fletch@fletchercallin.co.uk.

[8] Tom Duff. Interval Arithmetic and Recursive Subdivision for Implicit Functions and Constructive Solid Geometry. AT&T Bell Laboratories, 600 Mountain Avenue, Murray Hill, New Jersey, 07974.

[9] Hans Kohling Pedersen. Decorating Implicit Surfaces. Department of Computer Science, University of North Carolina at Chapel Hill. The author can be reached at Center for Integrated Systems, Stanford University, Stanford, CA 94305-4070. hkp@daimi.aau.dk

[10] Fabrice Neyret and Marie-Paule Cani. Pattern-Based Texturing Revisited. iMAGIS/GRAVIR-IMAG. www-imagis.imag.fr/TEXTURES/



part1 | part2