GTC-CVS: GTC: Re: gtc & Settlers: Upcoming SEUL-ANNOUNCE mailing (fwd)

[Game ToolChest dev account <gtc@seul.org>]

Introduction to GTC
===================

GTC (Game ToolChest) is an LGPL'd library for doing a bunch of things that are 
useful to 3d games. There's a 3d library (in progress), it sits on top of 
OpenGL. (In SGIspeak, that's a "visual simulation" library.) Currently it 
doesn't have very many features but I've started putting in some fancy collision 
detection. There's also a networking library, which is supposed to simplify the 
packing of data and communication. The socket API of Unix is good and simple so 
there isn't all that much to do but it still does some useful work. There is a 
code generator which will take a struct and produce streaming code for it, the 
streaming code will either encode to a platform neutral format or, if both 
endpoints of the communication link are binary compatible, send the binary data 
as is.

Goals
=====

I want to make a poweful and flexible game/vis sim library. I do not believe 
that these things need to be rewritten every year. I think that if they had done 
the X-Wing 3d library properly in the first place, they'd still be using it 
today (with some modifications).

In addition, I want the library to be as usable as possible. I want a simple 
API, I don't want to hide the underlying APIs (OpenGL, X11). I would like to 
provide bindings for many languages. I want a small memory footprint, efficient 
code, portable code. For these reasons, I am using C for the implementation. I 
was a C++ priest for a long time so my decision to not use C++ is a very 
educated one.

I want to provide functionality, not just another way of doing things you could 
already do. This means collision detection, projected shadows, complicated 
objects (such as smoothly changing LOD meshes, subdivision meshes, fractal 
meshes, deformable meshes, etc...)

I want to make it very easy, even completely transparent, to make a networked 
game. I hope to achieve this by writing a single client and having a server 
framework which will let you program your game while practically ignoring the 
network.

I refuse to write any code which already exists, is orthogonal to my library and 
is well implemented. If the code already exists but is not orthogonal, an 
integration effort should be made. If integration is impossible, we should check 
whether some sort of cooperation is possible between the two libraries. Only as 
a last resort should it be reimplemented. Of course, this only applies to 
significant code bases; if there is some small overlap between GTC and some 
other library, that's ok.

Finally, I would very much enjoy to have a way to very quickly prototype games. 
This would be done using some higher level language (Scheme, Python, whatever) 
with the approprate bindings to GTC and perhaps a simplification layer to take 
care of all stupid little details that need to be taken care of. Ideally, a 
space shooter would become 20 lines of Python code (or whichever language) and 
perhaps even children can start making their own games (again).

Status
======

Currently I am working on integrating the networking code and the gfx code. 
There's a simple data structure for holding generic gfx objects. Then, I make a 
world by having a list of those objects, along with a 4x4 matrix for position 
and orientation. The collision detection works with this data structure and can 
report collisions between these generic gfx object. I am now writing code to 
stream the state of these gfx objects in the world and a client program 
de-stream and display them. I plan to have this completed by July 19.

Included is a demo shooter where you fly in a space armada of ducks (that's the 
only mesh I had available) and you can shoot them. As soon as the networking 
code is integrated with the gfx code (should be July 19), I will release v0.2 of 
the library with a networked version of the space shooter.

After this is done, I have to go back to the gfx and complete the 
implementation.

Todo
====

* Textures, colors, materials; I do none of that, my space ducks are all gray. 
This is fairly easy but needs to be done.

* Mesh loading. This is hard for me, I have no modeller.

* Skeleton animation. We had started doing this but I put it on the back burner 
until some of the features I find more important start working. For skeleton 
animation there will be the additional problem of finding a modeller/animation 
program and reading its output.

* Collision detection (pruning). Currently the only collision detection 
implemented is a step which takes N axis aligned bounding boxes and checks all 
pairs for collision. It uses an algorithm that tries to prune away some of the 
checks -- there are N(N-1)/2 pairs which is O(N^2). The algorithm tries to be 
"output sensitive"; if there are few collisions, it runs faster. The algorithm 
uses no preprocessing and does not use coherence, I did this to make it as 
simple to use as possible. For N<200, the algorithm seems to do worse than the 
naive comparison of all pairs. For N>1000, my algorithm does much better than 
comparing all pairs. Unfortunately, it may be that it is still too slow so I 
will have to investigate other algorithms. Alas, all the other algorithms I know 
of use frame to frame coherence, which I was hoping to avoid.

* Collision detection (mesh to mesh): I haven't started working on this. I have 
chosen to use a Hierarchical Bounding Volume (HBV) algorithm. The reason is, 
they are fast, easy to implement and often can be used for other purposes than 
collision detection. Of the popular algorithms (Sphere trees, AABB trees, OBB 
trees and Swept Sphere Volume trees), I am leaning towards AABB trees. The 
reasons are, they are easy to implement and it seems to me it is probably easy 
to generate the AABB tree in real-time. The reason I want to generate the HBV in 
real time is for simplicity, but also for flexibility. I want to be able to use 
this collision detection algorithm on, say, fractal terrain. Generating all the 
triangles and creating the (huge) bounding tree would be absurd (I think) and 
would be hard to modify in real-time. It is much more realistic to generate the 
nodes of the bounding volume as required by the collision detection algorithm. I 
intend to include an option for generating the tree ahead of time for those data 
structure that permit it (eg, a simple mesh which will not get deformed).

* Reducing the bandwidth required by the generic client. Instead of sending 16 
floats for the matrix and a 32 bit int for the resource id, I could send 3 12 
bit fixed point numbers for the orientation (eg, quaternions), 3 16 bit values 
for the position (or variable size encoding) and a few more bits for resource 
id. This would make it perhaps 12 bytes per object in the world per frame of 
animation, which is still big. Then, objects which behave predictably 
(orientation not changing, position moving some constant amount each time 
interval), can be removed from the stream (a bit somewhere tells you if the 
object is in the stream). At that point, I hope the bandwidth requirement will 
be low enough to make interesting games. All this is good because it can be done 
without any help from the actual game code, the library will take care of 
everything. A next step which would probably greatly improve the bandwidth usage 
would be to ask the game code to tag which objects need to be updated for each 
client. However this is less transparent so I'll implement it last. My bandwidth 
goal is to take the least amount of bandwidth that can easily and transparently 
be achieved without taking away genericity. I believe that doing this will be 
enough to play on some of the faster modems (maybe 56Kbps but surely on 
ADSL/cable). I have no intention to do any of the predictive lag stuff they 
tried to do in Quake (ordinary modems can induce a latency of one fifth of a 
second, which is hardly acceptable for action games -- tough luck).

* API documentation. It is not stable enough yet to be worth documenting but 
eventually this will need to be done. At the moment, the API documentation is 
the source code. There is some preliminary documentation in the doc subdirectory 
but some of it is much out of date (eg the skeleton documentation).

Further down the road
=====================

Once the above is done, we should look into making those language bindings. A 
weak attempt was made early on to make guile bindings, and more recently Quentin 
started looking at xcode (a C-like language interpreter). Python, Perl, C++ 
would all be useful. However, before any work on bindings can start, we should 
stabilize the basic API some more, else the effort is wasted. Probably one of 
the most useful bindings would be a CORBA binding; presumably then in a far 
future high tech civilization this would give us automatic bindings to popular 
scripting languages?

Once we start putting in the real features, such as fractal meshes or 
subdivision surfaces, we will be in a dire need for a super duper modeller. We 
might have to make our own at that point. Hopefully this will be made easier 
because of the library. Unfortunately, modellers have their own set of hard 
problems they need to solve so it's not at all certain this will ever happen.

Help needed
===========

We need more coders. There are two main coders on this project (Quentin Merigot 
and I) but Quentin is away until the middle of August. If you think you can 
contribute to any aspect of the library, please contact me (see below for 
contact information). Here is a list of things which we may need. (The reason 
there's nothing in the gtc-dev mailing list right now is, well, I'm the only 
coder who's active right now.)

* We should be educated about CORBA. It may be that CORBA is useless to us now 
but it wouldn't hurt to check and make sure.

* Gfx. If you have a nifty idea for gfx stuff that could be implemented in a 
library, we want it.

* Mesh loading. Need that.

* Content. We need to have some objects to work with. I think that it's pretty 
clear from my demo (flying ducks!?) that I didn't have a spaceship mesh. We 
don't need much in that aspect right now but it would be good if we had a 
contact who could occasionally provide us with meshes to test our stuff with.

* Streaming video/audio. There are lots of patents here so we need to be 
careful. My field of study is harmonic analysis so I have some idea as to how I 
would compress video (or still pictures) but I don't know if that's patented. 
For the sound, I basically know the general idea of MP3 but that's patented too. 
I do not know if there are any patent-free alternatives for both these problems. 
If it weren't for patents, we could just use the already existing free MP3 
decoders and mpeg_play.

Contact
=======

You can reach my by e-mail. Please also check out the GTC home page.

Sebastien Loisel
loisel@math.mcgill.ca
sbastien@eng.sun.com
http://gtc.seul.org/

*************************************************************
To unsubscribe, send an e-mail to majordomo@gtc.seul.org with
unsubscribe gtc-cvs       in the body. http://gtc.seul.org/