Discussion:
[CsMain] Huge Worlds
(too old to reply)
Jorrit Tyberghein
2005-06-16 06:20:56 UTC
Permalink
Lately many people seem to be interested in developing a game with
Crystal Space that has a huge world. Typically this is done for MMORPG
games. PlaneShift is currently the game with the biggest online world
and they solved this issue by having loading pauses whenever a new
area needs to be loaded and they also make sure that different regions
are connected through small portals. i.e. no large outside plains that
are different regions.

However, this may not be a suitable solution for everyone. It would be
ideal if you could really have a really big world that never shows a
loading screen but which still has sufficient detail everywhere. To
accomplish that I think that we basically need to work on two issues
in Crystal Space:

1. Support for paging terrain engine. The current terrain engine can
support relatively big landscapes but if you really want a HUGE
landscape then it will not work nicely. Solutions like trying to solve
this with different sectors and different landscape meshes that need
to connect at the borders are hacky at best and have several
disadvantages: hard to connect landscapes without seams, overhead of
having many portals, hard to manage, big memory requirements for every
landscape mesh, ... Much better would be if the terrain engine itself
supported paging so that it can swap in/out parts of the terrain as
needed. Crystal Space has a memory mapping facility. Perhaps this can
be used for that?

2. Support for streaming of objects. The current map loading system in
CS is good and flexible but it is not really suitable for fast input
of objects. I wonder if we shouldn't have some kind of fast
intermediate format that is specifically designed for very fast
loading and can also be done in the background (thread).

I would like to discuss these two things as I feel they are important
for the future of CS. First we need to discuss what exactly needs to
be done to make this work. And finally we need to find someone who can
help implement this.

Greetings,
--
Project Manager of Crystal Space (http://www.crystalspace3d.org)
and CEL (http://cel.sf.net)
Philipp Aumayr
2005-06-16 07:11:56 UTC
Permalink
Hi Jorrit!

Maybe this "intermediate" format for streaming would work hand-in-hand with the vertex/color/abritrary data stream database thing (Marten's plans) that's been ghosting around for some time ?
Greets from Austria,
Phil

On Thu, 16 Jun 2005 10:19:55 +0200
Post by Jorrit Tyberghein
Lately many people seem to be interested in developing a game with
Crystal Space that has a huge world. Typically this is done for MMORPG
games. PlaneShift is currently the game with the biggest online world
and they solved this issue by having loading pauses whenever a new
area needs to be loaded and they also make sure that different regions
are connected through small portals. i.e. no large outside plains that
are different regions.
However, this may not be a suitable solution for everyone. It would be
ideal if you could really have a really big world that never shows a
loading screen but which still has sufficient detail everywhere. To
accomplish that I think that we basically need to work on two issues
1. Support for paging terrain engine. The current terrain engine can
support relatively big landscapes but if you really want a HUGE
landscape then it will not work nicely. Solutions like trying to solve
this with different sectors and different landscape meshes that need
to connect at the borders are hacky at best and have several
disadvantages: hard to connect landscapes without seams, overhead of
having many portals, hard to manage, big memory requirements for every
landscape mesh, ... Much better would be if the terrain engine itself
supported paging so that it can swap in/out parts of the terrain as
needed. Crystal Space has a memory mapping facility. Perhaps this can
be used for that?
2. Support for streaming of objects. The current map loading system in
CS is good and flexible but it is not really suitable for fast input
of objects. I wonder if we shouldn't have some kind of fast
intermediate format that is specifically designed for very fast
loading and can also be done in the background (thread).
I would like to discuss these two things as I feel they are important
for the future of CS. First we need to discuss what exactly needs to
be done to make this work. And finally we need to find someone who can
help implement this.
Greetings,
--
Project Manager of Crystal Space (http://www.crystalspace3d.org)
and CEL (http://cel.sf.net)
-------------------------------------------------------
SF.Net email is sponsored by: Discover Easy Linux Migration Strategies
from IBM. Find simple to follow Roadmaps, straightforward articles,
informative Webcasts and more! Get everything you need to get up to
speed, fast. http://ads.osdn.com/?ad_idt77&alloc_id492&op=click
_______________________________________________
Crystal-main mailing list
https://lists.sourceforge.net/lists/listinfo/crystal-main
res
2005-06-16 09:09:16 UTC
Permalink
Post by Jorrit Tyberghein
1. Support for paging terrain engine. The current terrain engine can
support relatively big landscapes but if you really want a HUGE
landscape then it will not work nicely. Solutions like trying to solve
this with different sectors and different landscape meshes that need
to connect at the borders are hacky at best and have several
disadvantages: hard to connect landscapes without seams, overhead of
having many portals, hard to manage, big memory requirements for every
landscape mesh, ... Much better would be if the terrain engine itself
supported paging so that it can swap in/out parts of the terrain as
needed. Crystal Space has a memory mapping facility. Perhaps this can
be used for that?
I recall the olde "terrbig" did that (but as we know that terrain was eventually
scrapped).

Memory mapping is probably the way to go. But swapped in/out should not only be
geometry data, but also texture data (like splat maps, base maps).
Post by Jorrit Tyberghein
2. Support for streaming of objects. The current map loading system in
CS is good and flexible but it is not really suitable for fast input
of objects. I wonder if we shouldn't have some kind of fast
intermediate format that is specifically designed for very fast
loading and can also be done in the background (thread).
I think we can split the data needed to load a mesh object/factory in two parts:
"administrative" (flags, materials and such stuff) and "geometry" (vertex
coordinates, triangles, you get the idea). I think the administrative data is
usually very small and could thus stay stored in documents (XML or binary),
while the geometry is best stored as raw as possible - think float[] dumped to a
disk. If any relatively time-consuming processing is done beforehand, the only
processing at load time needed would be endianness conversion (if the endian
happens to be different).

Sidebar: considering that (afaik) the major target processors for CS (x86,
PowerPC) and probably a good deal of other platforms use IEEE floats, it would
probably be more performant to not encode floats using csFloatToLong() -
obviously, as all that bit fiddling and float construction is saved. Of course
platforms w/o IEEE floats need conversion - I'd think the cost would be the same
as the current csLongToFloat(), just that only a fraction of the platforms would
have to pay it.

-f.r.
Peter Amstutz
2005-06-16 15:19:58 UTC
Permalink
Post by Jorrit Tyberghein
2. Support for streaming of objects. The current map loading system in
CS is good and flexible but it is not really suitable for fast input
of objects. I wonder if we shouldn't have some kind of fast
intermediate format that is specifically designed for very fast
loading and can also be done in the background (thread).
I'm extremely interested in CS being able to support background loading.
Currently, the csvosa3dl plugin handles the downloading of objects in
separate thread(s), but has to synchronize with the CS engine to actually
load/create CS meshes from the downloaded data. Certain elements of the
loading process for these models (such as computing vertex normals or LoD
levels) can get quite expensive, which causes a very noticible pause in
the CS runloop. Ideally it should be possible for a loader to set up
nearly all the data in the engine in a background thread, and then
synchronize with the main CS thread only for the last step of actually
adding the object to the scene.

What I'd like to see would be a code audit to determine what aspects of
the engine could be made threadsafe without having a negative impact on
performance, focusing on how to support arbitrary background loading of
meshes and textures. Then developers could have some guidelines as to how
to write multithreaded applications which use Crystal Space.

[ Peter Amstutz ][ ***@interreality.org ][ ***@anteon.com ]
[Lead Programmer][Interreality Project][Virtual Reality for the Internet]
[ VOS: Next Generation Internet Communication][ http://interreality.org ]
[ http://interreality.org/~tetron ][ pgpkey: pgpkeys.mit.edu 18C21DF7 ]
Jorrit Tyberghein
2005-06-16 17:41:10 UTC
Permalink
Post by Peter Amstutz
What I'd like to see would be a code audit to determine what aspects of
the engine could be made threadsafe without having a negative impact on
performance, focusing on how to support arbitrary background loading of
meshes and textures. Then developers could have some guidelines as to how
to write multithreaded applications which use Crystal Space.
This has actually been discussed in the past. The conclusion was that
it was not needed to make the engine thread-safe. What is needed is
that there are thread-safe methods in the engine to create empty
object wrappers. Like iMeshWrapper, iMaterialWrapper, .... These empty
wrapper objects are not linked to any engine list (as that would
require making those lists thread-safe and that's probably not a good
idea). Instead the loader would call those methods to create thos
classes and manage them on its own. In the seperate thread the loader
would call the mesh object loaders (or texture loaders) and finally
when everything is loaded the loader thread would finish and the main
engine thread would take all loaded meshes/textures/... from the
loader and add them to the right engine lists.

With this technique the following things must be made thread-safe:
- Simple methods in engine to create empty wrappers.
- The mesh object loaders must be made thread-safe.
- Image loaders must be made thread-safe.
- Perhaps the renderer texture manager too? Not sure.

Greetings,
--
Project Manager of Crystal Space (http://www.crystalspace3d.org)
and CEL (http://cel.sf.net)
Peter Amstutz
2005-06-17 01:13:42 UTC
Permalink
Post by Jorrit Tyberghein
This has actually been discussed in the past. The conclusion was that
it was not needed to make the engine thread-safe. What is needed is
that there are thread-safe methods in the engine to create empty
object wrappers. Like iMeshWrapper, iMaterialWrapper, .... These empty
wrapper objects are not linked to any engine list (as that would
require making those lists thread-safe and that's probably not a good
idea). Instead the loader would call those methods to create thos
classes and manage them on its own. In the seperate thread the loader
would call the mesh object loaders (or texture loaders) and finally
when everything is loaded the loader thread would finish and the main
engine thread would take all loaded meshes/textures/... from the
loader and add them to the right engine lists.
This is pretty much what I had in mind -- disconnecting the object
construction from the rendering parts of the engine, so the object isn't
added to the rendering lists in the engine until it has been fully
constructed and immediately ready to render on the next frame. I wonder
if there could still some threadsafety considerations, though -- what if
an object under construction needs to refer to some elements already
present in the engine, such as existing loaded textures and materials?
Someone needs to go through the relevant object construction code to
ensure that it doesn't touch or link into more subtle things in the engine
that could be changing in the middle of rendering.
Post by Jorrit Tyberghein
- Simple methods in engine to create empty wrappers.
Perhaps these could go into a "not ready" list so the engine still has
them available, and then the user can call a method that says "activate
this object" at which point it would move it over to the real rendering
list when the rendering thread starts the next frame.
Post by Jorrit Tyberghein
- The mesh object loaders must be made thread-safe.
The crossbuilder stuff (for importing MD2, 3DS etc) needs to be checked
over as well.
Post by Jorrit Tyberghein
- Image loaders must be made thread-safe.
- Perhaps the renderer texture manager too? Not sure.
The textures are only actually downloaded to the video card on an
as-needed basis, correct? So the background loader would mostly only be
responsible for decompressing the image from the file. Placing it in
texture memory would always happen in the renderer thread.

In any event, if we do go to a mixed model of partially-threadsafe code
we're going to have to make sure it is well documented what threads are
and are not permitted to do.

[ Peter Amstutz ][ ***@interreality.org ][ ***@anteon.com ]
[Lead Programmer][Interreality Project][Virtual Reality for the Internet]
[ VOS: Next Generation Internet Communication][ http://interreality.org ]
[ http://interreality.org/~tetron ][ pgpkey: pgpkeys.mit.edu 18C21DF7 ]
res
2005-06-17 05:34:27 UTC
Permalink
Post by Peter Amstutz
The crossbuilder stuff (for importing MD2, 3DS etc) needs to be checked
over as well.
Slightly off-topic but: maybe realize model importing through loader plugins
instead the crossbuilder.
Post by Peter Amstutz
Post by Jorrit Tyberghein
- Image loaders must be made thread-safe.
- Perhaps the renderer texture manager too? Not sure.
The textures are only actually downloaded to the video card on an
as-needed basis, correct? So the background loader would mostly only be
responsible for decompressing the image from the file. Placing it in
texture memory would always happen in the renderer thread.
If you look at PNG, JPG or TGA loading, you can notice that those loaders
actually use a 2nd thread for decompression.
Post by Peter Amstutz
In any event, if we do go to a mixed model of partially-threadsafe code
we're going to have to make sure it is well documented what threads are
and are not permitted to do.
Hm... maybe worthwhile to think of some good error-detection helpers... would be
nice if there were "thread-safety assertions" or so.

-f.r.
Jorrit Tyberghein
2005-06-17 05:37:13 UTC
Permalink
Post by res
Post by Peter Amstutz
The crossbuilder stuff (for importing MD2, 3DS etc) needs to be checked
over as well.
Slightly off-topic but: maybe realize model importing through loader plugins
instead the crossbuilder.
I agree with that. I think the crossbuilder should be removed and
replaced with normal loader plugins (using the binary plugin
mechanism). The crossbuilder is an ugly creature.
Post by res
If you look at PNG, JPG or TGA loading, you can notice that those loaders
actually use a 2nd thread for decompression.
Yes, but at some point you need to register a texture for the renderer
too which does mipmap generation and other stuff.

Greetings,
--
Project Manager of Crystal Space (http://www.crystalspace3d.org)
and CEL (http://cel.sf.net)
Andrew Mann
2005-06-20 14:01:59 UTC
Permalink
Post by Jorrit Tyberghein
Post by res
Post by Peter Amstutz
The crossbuilder stuff (for importing MD2, 3DS etc) needs to be checked
over as well.
Slightly off-topic but: maybe realize model importing through loader plugins
instead the crossbuilder.
I agree with that. I think the crossbuilder should be removed and
replaced with normal loader plugins (using the binary plugin
mechanism). The crossbuilder is an ugly creature.
Post by res
If you look at PNG, JPG or TGA loading, you can notice that those loaders
actually use a 2nd thread for decompression.
Yes, but at some point you need to register a texture for the renderer
too which does mipmap generation and other stuff.
Greetings,
Have you thought about a situation where a background loaded object
references an object already in the engine (say a texture), and the
referenced object is then unloaded before the background object
completes initialization? The SCF reference counting isn't threadsafe,
and to make it that way would probably incur some hefty penalties with
the amount of smart pointer usage.

In a somewhat related matter, before any mutexes are added, a critical
section implementation should be considered. Under linux pthreads this
would be the same as a mutex, but under windows critical sections are
much faster, although they don't work with conditions (and some other
operations) so they aren't directly interchangable.

Rhad/Andrew
res
2005-06-20 16:24:49 UTC
Permalink
Post by Andrew Mann
Have you thought about a situation where a background loaded object
references an object already in the engine (say a texture), and the
referenced object is then unloaded before the background object
completes initialization?
Hm... at some point, the object needs to be queried from the engine. Only this
would need to be thread-safe. If it increments the refcount, the object should
also be safe from deletion.
Post by Andrew Mann
The SCF reference counting isn't threadsafe,
and to make it that way would probably incur some hefty penalties with
the amount of smart pointer usage.
True... that probably means that the loader thread would have to be rather
careful to not change the refcount of used objects in some unsynchronized way.

-f.r.
Andreas Grosam
2005-06-20 17:08:12 UTC
Permalink
Post by res
Post by Andrew Mann
Have you thought about a situation where a background loaded
object
references an object already in the engine (say a texture), and the
referenced object is then unloaded before the background object
completes initialization?
Hm... at some point, the object needs to be queried from the engine. Only this
would need to be thread-safe. If it increments the refcount, the object should
also be safe from deletion.
Post by Andrew Mann
The SCF reference counting isn't threadsafe,
and to make it that way would probably incur some hefty penalties with
the amount of smart pointer usage.
True... that probably means that the loader thread would have to be rather
careful to not change the refcount of used objects in some
unsynchronized way.
IMO, making the change of the ref-counter thread safe isn't a big a
penalty.
When you use a well implemented pthread mutex on a modern system, it
adds a few opcodes (if it gets the mutex).
If you use your handcrafted CPU and board dependent atomic counter, you
can only reduce it to 50% of the number of instructions - and finally
it is propbaby not thread safe in all circumstances, anyway ;-)
In general, the guys creating the system know how to optimize it and
make it really work - so you can trust them.

If I remember right, there is a performance test for the boost shared
pointer somewhere (which uses thread safe optimized ref-counter in its
next implementation). This might give you some real numbers.
Sorry you need to google for it.

Of course, the access to the object itself isn't thread safe, yet. You
need to ensure this somehow, too.


Well, besides this, i think that in order to improve performance you
need to take a birds eye view - instead of looking at the atoms. For
instance, the desing of the world data might be much more important.
There are implementations which increase detail with increasing length
of data. Means, this is ideal cache coherence and ideal data locality.
(e.g.: "Totaly Ordered Mesh").

This also means, you just load the amount of data with the sufficient
resolution. Thus, you can view far distant and many objects without
loading a huge amount of data.

Maybe there are even "cache oblivious" access structures which LOD
increases which the length of data. Then, you need not care about the
source of the data - it is automatically well optimized for all levels
of hierachy memory (1. level cache, 2. level cache, RAM, disk,
internet).
You should consider to partition your world data, too.

Then you can analyze your motion of the point of view. With this data
you can estimate the next positions and thus you can prefetch and
pre-process the corresponding world data.


Regards
Andreas
Post by res
-f.r.
Jorrit Tyberghein
2005-06-20 17:13:40 UTC
Permalink
Post by Andreas Grosam
IMO, making the change of the ref-counter thread safe isn't a big a
penalty.
When you use a well implemented pthread mutex on a modern system, it
adds a few opcodes (if it gets the mutex).
Don't forget that ref counting is crucial in CS and is done a lot. So
even a few opcodes matter here. Selectively enabling thread-safe ref
counting is perhaps an option but not thread-safe ref counting in
general. That would be too much.

Greetings,
--
Project Manager of Crystal Space (http://www.crystalspace3d.org)
and CEL (http://cel.sf.net)
Andreas Grosam
2005-06-20 19:44:56 UTC
Permalink
Post by Jorrit Tyberghein
Post by Andreas Grosam
IMO, making the change of the ref-counter thread safe isn't a big a
penalty.
When you use a well implemented pthread mutex on a modern system, it
adds a few opcodes (if it gets the mutex).
Don't forget that ref counting is crucial in CS and is done a lot. So
even a few opcodes matter here. Selectively enabling thread-safe ref
counting is perhaps an option but not thread-safe ref counting in
general. That would be too much.
We should add a pthread mutex in the current code where the ref-counter
will be changed and then we can run a benchmark to compare the values.
This is only a few lines of code.
I bet it is less than 1%. ;-)


Regards
Andreas
Post by Jorrit Tyberghein
Greetings,
--
Project Manager of Crystal Space (http://www.crystalspace3d.org)
and CEL (http://cel.sf.net)
-------------------------------------------------------
SF.Net email is sponsored by: Discover Easy Linux Migration Strategies
from IBM. Find simple to follow Roadmaps, straightforward articles,
informative Webcasts and more! Get everything you need to get up to
speed, fast. http://ads.osdn.com/?ad_idt77&alloc_id492&op=click
_______________________________________________
Crystal-main mailing list
https://lists.sourceforge.net/lists/listinfo/crystal-main
res
2005-06-20 19:50:53 UTC
Permalink
Post by Andreas Grosam
We should add a pthread mutex in the current code where the ref-counter
will be changed and then we can run a benchmark to compare the values.
This is only a few lines of code.
I bet it is less than 1%. ;-)
Go ahead.

Also consider that other mutex implementations may be less performant than
pthreads. But once you uploaded the benchmark code/necessary diff somewhere this
can be easily checked.

-f.r.
Andrew Mann
2005-06-21 16:23:39 UTC
Permalink
Post by Andreas Grosam
Post by res
Post by Andrew Mann
Have you thought about a situation where a background loaded object
references an object already in the engine (say a texture), and the
referenced object is then unloaded before the background object
completes initialization?
Hm... at some point, the object needs to be queried from the engine. Only this
would need to be thread-safe. If it increments the refcount, the object should
also be safe from deletion.
Post by Andrew Mann
The SCF reference counting isn't threadsafe,
and to make it that way would probably incur some hefty penalties with
the amount of smart pointer usage.
True... that probably means that the loader thread would have to be rather
careful to not change the refcount of used objects in some
unsynchronized way.
IMO, making the change of the ref-counter thread safe isn't a big a
penalty.
When you use a well implemented pthread mutex on a modern system, it
adds a few opcodes (if it gets the mutex).
I'm not sure if this is true on Windows. Windows isn't a monolithic
design, and kernel operations require a context switch or two. Mutexes
are system wide and involve a kernel operation (and the associated
context switching) to lock or unlock. Windows critical sections seem to
be about the same thing as a pthread mutex, except they are process
specific and can't be used with conditions - the latter means you can't
just change CsMutex on Windows to use critical sections. Any place you
drop a CsMutex now that you can get away with a windows critical section
will cause some performance hit.
At one point a planeshift map was taking about 5 minutes to load and
parse under windows while the same map took about 30 seconds under
linux. It turned out that this was due to frequent memory allocations
in the XML parsing. Specifically, the MS libc was aquiring a mutex for
each memory allocation or deallocation. When the mutex was held through
the whole parsing process the Windows parse time dropped down to 30
seconds even though the same amount of memory allocs/deallocs were
performed.
Post by Andreas Grosam
If you use your handcrafted CPU and board dependent atomic counter, you
can only reduce it to 50% of the number of instructions - and finally
it is propbaby not thread safe in all circumstances, anyway ;-)
In general, the guys creating the system know how to optimize it and
make it really work - so you can trust them.
I think this is an architecture dependant thing, but I wouldn't suggest
taking on the burden of making a safe atomic refcount for every arch
anyway.
Post by Andreas Grosam
If I remember right, there is a performance test for the boost shared
pointer somewhere (which uses thread safe optimized ref-counter in its
next implementation). This might give you some real numbers.
Sorry you need to google for it.
Of course, the access to the object itself isn't thread safe, yet. You
need to ensure this somehow, too.
This probably isn't so hard for a loader thread. If you can build the
loading objects in the background thread without altering any data in
the main thread (except the presumed thread-safe refcount) then you
should be OK. The main thread wont know anything about the objects
being built by the loader thread until it's done with them.
Post by Andreas Grosam
Well, besides this, i think that in order to improve performance you
need to take a birds eye view - instead of looking at the atoms. For
instance, the desing of the world data might be much more important.
There are implementations which increase detail with increasing length
of data. Means, this is ideal cache coherence and ideal data locality.
(e.g.: "Totaly Ordered Mesh").
This also means, you just load the amount of data with the sufficient
resolution. Thus, you can view far distant and many objects without
loading a huge amount of data.
LOD is something to consider, but before that you need to figure out
where to load data from at all. In a two dimensional heightmap the data
may be ordered differently than a 3 dimensional map that extends in all
3 dimensions (space or flight sim for example).
Coordination is still required between "world" designers and the chosen
algorithm. A method that pre-loads objects 100 meters from you may be
fine for a cave-crawl, but do you want the slope of a mountain popping
in at 100 meters out of nowhere?
I think that the world level loading is much more important than the
atmoic design, but I think that it's important to a point where you as a
game/application developer will want to customize how this is done. I
dont think a general purpose solution should be locked in here. For
that reason I think that whatever default solution is put into CS will
be unoptimal for many situations.
On the other hand, I think that the syncronization between the
background loader and the engine needs to be solved in a universal manner.
Post by Andreas Grosam
Maybe there are even "cache oblivious" access structures which LOD
increases which the length of data. Then, you need not care about the
source of the data - it is automatically well optimized for all levels
of hierachy memory (1. level cache, 2. level cache, RAM, disk, internet).
You should consider to partition your world data, too.
Then you can analyze your motion of the point of view. With this data
you can estimate the next positions and thus you can prefetch and
pre-process the corresponding world data.
Regards
Andreas
We should add a pthread mutex in the current code where the
ref-counter >will be changed and then we can run a benchmark to
compare the values. This is only a few lines of code.
I bet it is less than 1%. ;-)
Be sure to run this test on Windows (both mingw and MSVC would be
interesting, but MSVC is where I'm most worried of a slowdown). I can
compile and run any test under MSVC 7.1, though I don't have an up to
date CS workspace right now.


Rhad/Andrew
Andreas Grosam
2005-06-21 19:36:26 UTC
Permalink
Post by Andrew Mann
Post by Andreas Grosam
Post by res
Post by Andrew Mann
Have you thought about a situation where a background loaded
object
references an object already in the engine (say a texture), and the
referenced object is then unloaded before the background object
completes initialization?
Hm... at some point, the object needs to be queried from the engine. Only this
would need to be thread-safe. If it increments the refcount, the object should
also be safe from deletion.
Post by Andrew Mann
The SCF reference counting isn't threadsafe,
and to make it that way would probably incur some hefty penalties with
the amount of smart pointer usage.
True... that probably means that the loader thread would have to be rather
careful to not change the refcount of used objects in some
unsynchronized way.
IMO, making the change of the ref-counter thread safe isn't a big a
penalty.
When you use a well implemented pthread mutex on a modern system, it
adds a few opcodes (if it gets the mutex).
I'm not sure if this is true on Windows. Windows isn't a monolithic
design, and kernel operations require a context switch or two.
Mutexes are system wide and involve a kernel operation (and the
associated context switching) to lock or unlock.
You can implement your own simple mutex with a variable of type long
and the InterlockedExchange()function. However, this is not a full
fledged mutex - but sufficient and fast (no context switch) for this
purpose.
You might also use CRITICAL_SECTION.

For Linux and GCC there are similar functions in <asm/atomic.h>
respectively <bits/atomicity.h>. For other UNIXs as well.
Post by Andrew Mann
Windows critical sections seem to be about the same thing as a pthread
mutex, except they are process specific and can't be used with
conditions
Important to note here is, that critical sections do not force a
context switch (when they succeed to aquire the mutex).
Post by Andrew Mann
- the latter means you can't just change CsMutex on Windows to use
critical sections. Any place you drop a CsMutex now that you can get
away with a windows critical section will cause some performance hit.
For the ref-counter you need only a "light-wight" mutex. So, you can
use a critical section.
Post by Andrew Mann
At one point a planeshift map was taking about 5 minutes to load and
parse under windows while the same map took about 30 seconds under
linux. It turned out that this was due to frequent memory allocations
in the XML parsing. Specifically, the MS libc was aquiring a mutex
for each memory allocation or deallocation. When the mutex was held
through the whole parsing process the Windows parse time dropped down
to 30 seconds even though the same amount of memory allocs/deallocs
were performed.
This shows, that on Windows the heap is poorly designed. On other
systems, you get process specific chunks of memory, and a process only
rarely allocates/frees system memory.
With a carfefully design the process heap is even thread safe without
affecting performance.
Of course, you could also implement your own memory allocation scheme.
Post by Andrew Mann
Post by Andreas Grosam
If you use your handcrafted CPU and board dependent atomic counter,
you can only reduce it to 50% of the number of instructions - and
finally it is propbaby not thread safe in all circumstances, anyway
;-)
In general, the guys creating the system know how to optimize it and
make it really work - so you can trust them.
I think this is an architecture dependant thing, but I wouldn't
suggest taking on the burden of making a safe atomic refcount for
every arch anyway.
I would strongly discourage this too, except you have a sound
understanding of the CPU, the memory architecture and you know what
memory barriers are for.

However, there are already implementations, see above.
You might take a look into boost light wight mutexes, too.
Post by Andrew Mann
Post by Andreas Grosam
If I remember right, there is a performance test for the boost shared
pointer somewhere (which uses thread safe optimized ref-counter in
its next implementation). This might give you some real numbers.
Sorry you need to google for it.
Of course, the access to the object itself isn't thread safe, yet.
You need to ensure this somehow, too.
This probably isn't so hard for a loader thread. If you can build
the loading objects in the background thread without altering any data
in the main thread (except the presumed thread-safe refcount) then you
should be OK. The main thread wont know anything about the objects
being built by the loader thread until it's done with them.
OK, but this implies a certain implementation of how and when the
loader constructs objects. And eventually, there needs to be at least
one shared object - e.g. a container of objects where the loader
inserts the objects. And the access to the container needs to be
synchronized, thus it requires a mutex.
On every access to the container - either from the loader thread or
from the main thread, its mutex must be aquired.
(If i get this right)
Post by Andrew Mann
Post by Andreas Grosam
Well, besides this, i think that in order to improve performance you
need to take a birds eye view - instead of looking at the atoms. For
instance, the desing of the world data might be much more important.
There are implementations which increase detail with increasing
length of data. Means, this is ideal cache coherence and ideal data
locality. (e.g.: "Totaly Ordered Mesh").
This also means, you just load the amount of data with the sufficient
resolution. Thus, you can view far distant and many objects without
loading a huge amount of data.
LOD is something to consider, but before that you need to figure out
where to load data from at all.
From a "world database"! :-)
Post by Andrew Mann
In a two dimensional heightmap the data may be ordered differently
than a 3 dimensional map that extends in all 3 dimensions (space or
flight sim for example).
Yes, there are many kinds of data in a world: terrain data, objects,
light sources, textures, shader programs, audio data, images, scripts,
etc.
Each type may require its own data access structure.
Post by Andrew Mann
Coordination is still required between "world" designers and the
chosen algorithm. A method that pre-loads objects 100 meters from you
may be fine for a cave-crawl, but do you want the slope of a mountain
popping in at 100 meters out of nowhere?
It should be clear that LOD is required. There are various algorithm
around, which deal with huge data sets (>>1 GBytes), perform view
frustum culling, texture mapping, deal with arbitrary shapes (objects)
and terrain data, etc., and also exploit modern graphics hardware.
Just to mention these for terrain data:
"BDAM - Batched Dynamic Adaptive Meshes for High Performance Terrain
Visualization.", at <http://www.crs4.it>,
or "Chunked LODS", at <http://tulrich.com/geekstuff/chunklod.html>
or "Geometry Clipmaps", ROAM, SOAR.


Please notice, that an algorithm might change, a hybrid might be used,
or an optimal algorithm might be chosen on the client, which takes care
of the hardware capabilities. Thus, a data structure which is optimal
for a specific tesselation/render algorithm might not be ideal.

We could use an intermediate format in the world database, which
requires to preprocess the data and convert them into the appropriate
data structure for the current algorithm used by the client.

Alternatively, a set of different data structures can be stored in the
database (ugly).

I guess, if preprocessing (for converting data structures) needs to be
done, this needs to be performed on the client side - and i fear this
is not optimal regarding load performance. Even more worse, off-line
optimization of data is difficult or impossible, too.
Thus, a genious data structure which suffices many algorithm would be
nice, unfortunately, I have no idea whether this is possible at all.
Post by Andrew Mann
I think that the world level loading is much more important than the
atmoic design, but I think that it's important to a point where you as
a game/application developer will want to customize how this is done.
I dont think a general purpose solution should be locked in here. For
that reason I think that whatever default solution is put into CS will
be unoptimal for many situations.
Yes, i agree - although i had gladly said "No, this isn't true!", *sigh*

So a world database needs to be flexible enough to provide for a
solution for the aformentioned requirements.
Post by Andrew Mann
On the other hand, I think that the syncronization between the
background loader and the engine needs to be solved in a universal manner.
So, you jump again to the atomic level? ;-)
Or, are you saying you want a more abstract level for a design?

Hm, objects (including terrains) might be streamed, might be
compressed, might have a certain view-independent LOD.
How can we access them?
For terrain data, see papers above.

For other objects, these might have many attributes, and any attribute
or any combination can be used as a key to query them.
Thus, a multi dimensional access structure which is also optimized for
range queries (say "region of interest"), would be appropriate.

However, firstly, i think we need a more elaborated data model for
world data. We need to know which kind of data it shall contain. Of
course, fine grained detail and most coarse level shall be supported -
this leads to a hierarchical approach.

The database should be flexibel and extensible, so that a world
desginer can add any kind of weird data types which will be used in a
game.

It should be also clear, that this is a distributed database with
transactions and so force ...
Ohps, now it might become complex ... ;-)
OK, "distributed" not necessarily.
Post by Andrew Mann
Post by Andreas Grosam
Maybe there are even "cache oblivious" access structures which LOD
increases which the length of data. Then, you need not care about the
source of the data - it is automatically well optimized for all
levels of hierachy memory (1. level cache, 2. level cache, RAM, disk,
internet).
You should consider to partition your world data, too.
Then you can analyze your motion of the point of view. With this data
you can estimate the next positions and thus you can prefetch and
pre-process the corresponding world data.
Regards
Andreas
We should add a pthread mutex in the current code where the
ref-counter >will be changed and then we can run a benchmark to
compare the values. This is only a few lines of code.
I bet it is less than 1%. ;-)
Be sure to run this test on Windows (both mingw and MSVC would be
interesting, but MSVC is where I'm most worried of a slowdown). I can
compile and run any test under MSVC 7.1, though I don't have an up to
date CS workspace right now.
Sorry, I don´t have a Windows box for testing. Even more worse, the
csbench test program crashes on my Mac without leaving any traces in
log files. It just freezes the system completely. But this is another
problem ...

Although, it would be interesting to see how well a Mac OS X pthread
mutex performs against an AtomicCounter used to assemble a light wight
mutex.

Regards
Andreas
Post by Andrew Mann
Rhad/Andrew
-------------------------------------------------------
SF.Net email is sponsored by: Discover Easy Linux Migration Strategies
from IBM. Find simple to follow Roadmaps, straightforward articles,
informative Webcasts and more! Get everything you need to get up to
speed, fast. http://ads.osdn.com/?ad_id=7477&alloc_id=16492&op=click
_______________________________________________
Crystal-main mailing list
https://lists.sourceforge.net/lists/listinfo/crystal-main
Andrew Mann
2005-06-21 21:12:18 UTC
Permalink
Post by Andrew Mann
Post by Andreas Grosam
Post by res
Post by Andrew Mann
Have you thought about a situation where a background loaded
object
references an object already in the engine (say a texture), and the
referenced object is then unloaded before the background object
completes initialization?
Hm... at some point, the object needs to be queried from the engine. Only this
would need to be thread-safe. If it increments the refcount, the object should
also be safe from deletion.
Post by Andrew Mann
The SCF reference counting isn't threadsafe,
and to make it that way would probably incur some hefty penalties with
the amount of smart pointer usage.
True... that probably means that the loader thread would have to be rather
careful to not change the refcount of used objects in some
unsynchronized way.
IMO, making the change of the ref-counter thread safe isn't a big a
penalty.
When you use a well implemented pthread mutex on a modern system, it
adds a few opcodes (if it gets the mutex).
I'm not sure if this is true on Windows. Windows isn't a
monolithic design, and kernel operations require a context switch or
two. Mutexes are system wide and involve a kernel operation (and the
associated context switching) to lock or unlock.
You can implement your own simple mutex with a variable of type long and
the InterlockedExchange()function. However, this is not a full fledged
mutex - but sufficient and fast (no context switch) for this purpose.
You might also use CRITICAL_SECTION.
For Linux and GCC there are similar functions in <asm/atomic.h>
respectively <bits/atomicity.h>. For other UNIXs as well.
Post by Andrew Mann
Windows critical sections seem to be about the same thing as a pthread
mutex, except they are process specific and can't be used with conditions
Important to note here is, that critical sections do not force a context
switch (when they succeed to aquire the mutex).
Post by Andrew Mann
- the latter means you can't just change CsMutex on Windows to use
critical sections. Any place you drop a CsMutex now that you can get
away with a windows critical section will cause some performance hit.
For the ref-counter you need only a "light-wight" mutex. So, you can use
a critical section.
Perhaps I should back up a bit. What I was trying to relay is that, if
mutexing is the protection that ends up being used, csMutex can't be
used, and a new construct should be created which will likely be the
implemented the same as a csMutex on linux, but will be different on
Windows.
This follows from: If mutexing is going to be used it will be used in
a platform independant way with a platform abstraction performed by a
class wrapper (as csMutex is now) - i.e. you wont put windows specific
code around the refcount, you'll use a csCriticalSection or some such.
The windows specific code would be hidden. The method used can't be
csMutex because csMutex is used by csCondition, and on windows that
relies on windows conditions which rely on the csMutex using a true
windows mutex, that would mean you'd have to use a windows mutex which
we've determined is slow.
So all that I'm saying is that if csMutex are dropped in now, they will
end up being pulled out and replaced later due to speed, so it's best to
consider the critical section early.
Post by Andrew Mann
At one point a planeshift map was taking about 5 minutes to load
and parse under windows while the same map took about 30 seconds under
linux. It turned out that this was due to frequent memory allocations
in the XML parsing. Specifically, the MS libc was aquiring a mutex
for each memory allocation or deallocation. When the mutex was held
through the whole parsing process the Windows parse time dropped down
to 30 seconds even though the same amount of memory allocs/deallocs
were performed.
This shows, that on Windows the heap is poorly designed. On other
systems, you get process specific chunks of memory, and a process only
rarely allocates/frees system memory.
With a carfefully design the process heap is even thread safe without
affecting performance.
Of course, you could also implement your own memory allocation scheme.
I wouldn't go that far. We're talking about a lot of memory here. I
don't know of any C libs that base their allocation size on time, most
will allocate/free system memory based on size requested, so if you
request and free a lot of memory quite often you will get memory from
the system quite often. The XML parser was really quite inefficient in
that, which is why Jorrit changed it.
Post by Andrew Mann
Post by Andreas Grosam
If you use your handcrafted CPU and board dependent atomic counter,
you can only reduce it to 50% of the number of instructions - and
finally it is propbaby not thread safe in all circumstances, anyway ;-)
In general, the guys creating the system know how to optimize it and
make it really work - so you can trust them.
I think this is an architecture dependant thing, but I wouldn't
suggest taking on the burden of making a safe atomic refcount for
every arch anyway.
I would strongly discourage this too, except you have a sound
understanding of the CPU, the memory architecture and you know what
memory barriers are for.
However, there are already implementations, see above.
You might take a look into boost light wight mutexes, too.
Post by Andrew Mann
Post by Andreas Grosam
If I remember right, there is a performance test for the boost shared
pointer somewhere (which uses thread safe optimized ref-counter in
its next implementation). This might give you some real numbers.
Sorry you need to google for it.
Of course, the access to the object itself isn't thread safe, yet.
You need to ensure this somehow, too.
This probably isn't so hard for a loader thread. If you can build
the loading objects in the background thread without altering any data
in the main thread (except the presumed thread-safe refcount) then you
should be OK. The main thread wont know anything about the objects
being built by the loader thread until it's done with them.
OK, but this implies a certain implementation of how and when the loader
constructs objects. And eventually, there needs to be at least one
shared object - e.g. a container of objects where the loader inserts the
objects. And the access to the container needs to be synchronized, thus
it requires a mutex.
On every access to the container - either from the loader thread or from
the main thread, its mutex must be aquired.
(If i get this right)
Right, a simple threadsafe queue is probably fine. When the loader is
done with an object it puts it into the queue. The main thread checks
the queue each pass - and maybe only processes one or a few waiting
objects (if any are waiting). A once per pass mutex lock is nothing,
and the loader thread will only hold the mutex for a few ops during a
queue insert.
Post by Andrew Mann
Post by Andreas Grosam
Well, besides this, i think that in order to improve performance you
need to take a birds eye view - instead of looking at the atoms. For
instance, the desing of the world data might be much more important.
There are implementations which increase detail with increasing
length of data. Means, this is ideal cache coherence and ideal data
locality. (e.g.: "Totaly Ordered Mesh").
This also means, you just load the amount of data with the sufficient
resolution. Thus, you can view far distant and many objects without
loading a huge amount of data.
LOD is something to consider, but before that you need to figure
out where to load data from at all.
Mårten Svanfeldt (dev)
2005-06-22 09:36:21 UTC
Permalink
Ok, as I think this thread have derailed a bit, so I will start fresh with my
thoughts ;)

First, I think some of these thougts are not only beneficial to people with huge
worlds but to everyone. IMO the current CS world files are good in the way they
are resonably easy to write but if you have a world (even though the extent
might be not so big) with 100k triangles/vertices it just take too much space
and time to load.

Random thougts on the subject ;)
- Separate "administrative" data from geometry data. Administrative data is in
my definition such as position, object relations, list of materials etc that CS
would need to know where to display the object and what other objects needs to
be loaded before/at the same time as this object. This data should/could be
stored in xml format.
Geometry data on the other hand (ie vertex and triangle information) should be
stored in a format that makes it as fast as possible to load and at least I
think this means a binary format. Sure you need to endian-convert on some (few)
platforms but still this is alot faster than the current text-processing
currently done.

- Give the user control over the background loading. Some people will be
satisfied with a thread "uncontrolled" in the background doing loading, others
want to be able to control that thread and I suspect there are people who want
total control over anything that happens. Therefor I think it is vital to give
maximum control over the loading process. (One idea is that you can disable any
background thread and instead tap into the "objects to be loaded queue"
yourself).

- Connect the loading to LOD. At first this sounds like a bad idea but I think
it might help to resolve one of the problems with dynamic loading, that your
data is not in memory when you first need to render it. By loading a lower
LOD-level of a high resolution model you speed up the loading and then later
when the full model is loaded you can change to a higher quality model. I think
it is sometimes better to have something to display even though it might be
lower quality. Of course this must also be controllable.


All for now. I think the thread should focus on the architectural and design
problems first instead of derailing into a discussion about thread-safty in
ref-counting ;)

-Mårten
Andrew Mann
2005-06-22 15:59:22 UTC
Permalink
Post by MÃ¥rten Svanfeldt (dev)
Ok, as I think this thread have derailed a bit, so I will start fresh with my
thoughts ;)
First, I think some of these thougts are not only beneficial to people with huge
worlds but to everyone. IMO the current CS world files are good in the way they
are resonably easy to write but if you have a world (even though the extent
might be not so big) with 100k triangles/vertices it just take too much space
and time to load.
Random thougts on the subject ;)
- Separate "administrative" data from geometry data. Administrative data is in
my definition such as position, object relations, list of materials etc that CS
would need to know where to display the object and what other objects needs to
be loaded before/at the same time as this object. This data should/could be
stored in xml format.
Geometry data on the other hand (ie vertex and triangle information) should be
stored in a format that makes it as fast as possible to load and at least I
think this means a binary format. Sure you need to endian-convert on some (few)
platforms but still this is alot faster than the current text-processing
currently done.
You may want to have an arbitrarily deep heirarchy even at the
administrative level. For example, if you segment your data with a BSP
tree, it would be nice to say "always keep the top 16 levels in memory".
The branches would contain unresolved references to other locations in
the data file. If you walk the tree and reach a reference to an
unloaded branch, you'd load in that branch (and maybe a few levels
deeper as an optimization). You'd also expire branches that haven't
been recently used from the memory cache. This tree would only need to
contain enough information to know how to walk the tree (visibility
information), and ultimately what object/world data to load once the the
walk is complete.
This may be able to be generalized such that loading a new world file
just adds a new unresolved branch to a global tree, and doesn't really
load anything until that branch is looked at for the first time.
Post by MÃ¥rten Svanfeldt (dev)
- Give the user control over the background loading. Some people will be
satisfied with a thread "uncontrolled" in the background doing loading, others
want to be able to control that thread and I suspect there are people who want
total control over anything that happens. Therefor I think it is vital to give
maximum control over the loading process. (One idea is that you can disable any
background thread and instead tap into the "objects to be loaded queue"
yourself).
As with everything a set of interfaces should be defined. CS should
have a reference implementation, but I doubt the reference
implementation will meet everyone's needs. Other plugins can/will be
developed I'm sure, but you need to start with 1.
Post by MÃ¥rten Svanfeldt (dev)
- Connect the loading to LOD. At first this sounds like a bad idea but I think
it might help to resolve one of the problems with dynamic loading, that your
data is not in memory when you first need to render it. By loading a lower
LOD-level of a high resolution model you speed up the loading and then later
when the full model is loaded you can change to a higher quality model. I think
it is sometimes better to have something to display even though it might be
lower quality. Of course this must also be controllable.
I think this is a detail that doesn't need to be resolved at a high
level. The high level system will notify a subsystem: "Hey, this area
is within the defined pre-load region. Go get it." The subsystem will
decide wether to load a LOD reduced, normal, whatever set of models. I
think the tricky part is figuring out what regions are now preloadable,
what regions are unloadable, or even 'what is a region?'. Is a region a
polygon? An object? A set of objects? (If so, what criteria for the set?)
Post by MÃ¥rten Svanfeldt (dev)
All for now. I think the thread should focus on the architectural and design
problems first instead of derailing into a discussion about thread-safty in
ref-counting ;)
Or binary/XML eh? :P

Rhad/Andrew
Post by MÃ¥rten Svanfeldt (dev)
-Mårten
-------------------------------------------------------
SF.Net email is sponsored by: Discover Easy Linux Migration Strategies
from IBM. Find simple to follow Roadmaps, straightforward articles,
informative Webcasts and more! Get everything you need to get up to
speed, fast. http://ads.osdn.com/?ad_idt77&alloc_id492&opÌk
_______________________________________________
Crystal-develop mailing list
https://lists.sourceforge.net/lists/listinfo/crystal-develop
Andreas Grosam
2005-06-22 21:09:30 UTC
Permalink
Post by MÃ¥rten Svanfeldt (dev)
Ok, as I think this thread have derailed a bit, so I will start fresh with my
thoughts ;)
We didn't discuss memory barriers so far ... ;-)
Post by MÃ¥rten Svanfeldt (dev)
First, I think some of these thougts are not only beneficial to people with huge
worlds but to everyone. IMO the current CS world files are good in the way they
are resonably easy to write but if you have a world (even though the extent
might be not so big) with 100k triangles/vertices it just take too much space
and time to load.
k, issue tracked.
Post by MÃ¥rten Svanfeldt (dev)
Random thougts on the subject ;)
- Separate "administrative" data from geometry data. Administrative data is in
my definition such as position, object relations, list of materials etc that CS
would need to know where to display the object and what other objects needs to
be loaded before/at the same time as this object. This data
should/could be
stored in xml format.
Could you/we elaborate on this, please:
1) what exactly are the data types which shall be stored in a world
database?
terrain data, terrain textures are the most obvious ones, but what else
...
terrain data are "height maps", either 2 or 3 dimensional.

2) which of them shall be stored in a multi resolution data structure
(LOD enabled)?
Post by MÃ¥rten Svanfeldt (dev)
Geometry data on the other hand (ie vertex and triangle information) should be
stored in a format that makes it as fast as possible to load and at least I
think this means a binary format.
of course, here we need speed. I also think about compression.
Post by MÃ¥rten Svanfeldt (dev)
Sure you need to endian-convert on some (few)
platforms but still this is alot faster than the current
text-processing
currently done.
Endian?? wrong thread!! ;-)
Post by MÃ¥rten Svanfeldt (dev)
- Give the user control over the background loading.
IMO no, ...
Post by MÃ¥rten Svanfeldt (dev)
Some people will be
satisfied with a thread "uncontrolled" in the background doing
loading, others
want to be able to control that thread and I suspect there are people who want
total control over anything that happens.
... hm, I don't think they want to control *this*, or do you consider
to control background tasks in your video or audio player on your PC?

But let them define other parameters:
minimum frame rate, max distortion error, region of interest,
priorities (importance map), etc.
Post by MÃ¥rten Svanfeldt (dev)
Therefor I think it is vital to give
maximum control over the loading process. (One idea is that you can disable any
background thread and instead tap into the "objects to be loaded queue"
yourself).
hm, why do you want to do this? It is an simulation! Means, when an
object enters the scene, it enters the scene - and you can't say "No,
stop, do not render this object!" You wouldn't have enough time to take
actions right in time anyway. The computer is typically much better in
such things. ;-)

But probably I do miss something, so could you please explain this in
more detail?
Post by MÃ¥rten Svanfeldt (dev)
- Connect the loading to LOD. At first this sounds like a bad idea
not at all!!
Post by MÃ¥rten Svanfeldt (dev)
but I think
it might help to resolve one of the problems with dynamic loading, that your
data is not in memory when you first need to render it. By loading a lower
LOD-level of a high resolution model you speed up the loading and then later
when the full model is loaded you can change to a higher quality model. I think
it is sometimes better to have something to display even though it might be
lower quality.
This is the idea.
Post by MÃ¥rten Svanfeldt (dev)
Of course this must also be controllable.
All for now. I think the thread should focus on the architectural and design
problems first instead of derailing into a discussion about
thread-safty in
ref-counting ;)
agreed
Post by MÃ¥rten Svanfeldt (dev)
-Mårten
Andreas
Post by MÃ¥rten Svanfeldt (dev)
-------------------------------------------------------
SF.Net email is sponsored by: Discover Easy Linux Migration Strategies
from IBM. Find simple to follow Roadmaps, straightforward articles,
informative Webcasts and more! Get everything you need to get up to
speed, fast. http://ads.osdn.com/?ad_idt77&alloc_id492&op=click
_______________________________________________
Crystal-main mailing list
https://lists.sourceforge.net/lists/listinfo/crystal-main
Mårten Svanfeldt (dev)
2005-06-23 06:54:34 UTC
Permalink
Post by Andreas Grosam
1) what exactly are the data types which shall be stored in a world
database?
terrain data, terrain textures are the most obvious ones, but what else
...
terrain data are "height maps", either 2 or 3 dimensional.
By world database you mean the binary storage (ie not the adminstrative data).
If so I say any vertex/triangle data for any mesh not only terrains but also
genmesh/thingmesh/cal3d.
Post by Andreas Grosam
2) which of them shall be stored in a multi resolution data structure
(LOD enabled)?
The exact format of the stored data IMO depends on the mesh, so the mesh is
responsible for parsing it's own data.
Post by Andreas Grosam
... hm, I don't think they want to control *this*, or do you consider
to control background tasks in your video or audio player on your PC?
No, but here is the difference between a regular application and a SDK. The user
of a regular application is generaly a clueless idiot, while the "user" of an
SDK is a programmer who generally should know what he does and might want to do
things the SDK coders have not pondered.
Post by Andreas Grosam
minimum frame rate, max distortion error, region of interest,
priorities (importance map), etc.
This is very hard or impossible to do good without having control of all things
that runs on the computer. In general this is not the case. For example our
(almost non-exisiting) project use CS with several other SDKs such as physics
and network libraries (not connected to CS) and as CS does not control those it
makes it very hard for CS to "load balance" the processor.
Post by Andreas Grosam
Post by MÃ¥rten Svanfeldt (dev)
Therefor I think it is vital to give
maximum control over the loading process. (One idea is that you can disable any
background thread and instead tap into the "objects to be loaded queue"
yourself).
hm, why do you want to do this? It is an simulation! Means, when an
object enters the scene, it enters the scene - and you can't say "No,
stop, do not render this object!" You wouldn't have enough time to take
actions right in time anyway. The computer is typically much better in
such things. ;-)
Yes you can :) One example is that you can hang on to a lower LOD-level or a
billboard longer than you should while waiting for the wanted data to load.
Also, delaying a mesh 1-5 frames when you run at 50 fps isn't noticable
really..
Post by Andreas Grosam
But probably I do miss something, so could you please explain this in
more detail?
I just know that some users (not all, but a few) want total control of what is
happening and when. If you work with someone who made a few games, especially
for console platforms (PS2/Xbox) there are two things they really want
1. All calls (function calls) should have estimatable cost (ie the time should
be possible to roughly estimate and/or limit).
2. All processes/calls should take about the same time every frame. You do not
want the draw one frame to take three times as long as the frame before just
because it have to wait for new meshes. Better make it wait for a few (the most
important maybe) meshes, then ignore the rest and take those next frame.


-Mårten
Andreas Grosam
2005-06-23 10:56:36 UTC
Permalink
On 23.06.2005, at 10:53, Mårten Svanfeldt (dev) wrote:

I would like to stick on the "world database" and elaborate more on
this:
Note that i intentionally do not consider anything what is currently
implemented in CS, just for the sake to have an open mind.

Since Jorrit anounced a new project, and since there are questions
regarding the Collision-Detection - i think the thoughts below could
be helpfull.
Post by MÃ¥rten Svanfeldt (dev)
Post by Andreas Grosam
1) what exactly are the data types which shall be stored in a world
database?
terrain data, terrain textures are the most obvious ones, but what else
...
terrain data are "height maps", either 2 or 3 dimensional.
By world database you mean the binary storage (ie not the
adminstrative data).
I would say, a "world database" is a container holding all objects
which exist in a world (game, simulation). At any time the objects
represent the current state of the world.

At a very basic level, a world is a set of objects - or more precisely,
it is a set of containers of objects. Since objects might itself be
again containers, it forms a hierarchical strucure.

Some examples of types are:
Terrain, Sound, Particel, Texture, Vegetation, Script, DynamicTexture,
DynamicTerrain, etc.

A certain object may be of multible types, or a composition or
aggregation.



The next step should be to define a topology or classification for the
world data. Any pointers or ideas are appreciated.

Note that a world is "dynamic" and its objects may be related to
others, might be active or passive, and form a complex dependency and
relationship. (So we might identify these roles: controller, owner,
parent, container, group, etc)



At least for terrain (hight maps, not including other terrain related
objects) we already identified these requirements:

Capable of representing objects based on spherical and planar height
fields (planetes, ground)
Able to handle huge amount of out-of-core world data (>> 1GByte).
Visualization in real-time
Support several tesselation/rendering algorithms, e.g. through plugins
Provide a flexible data format which can be easily and (fast, too)
converted to a format suitable for a certain tesselation/render
algorithm, otherwise is a "multi-format".
Allow for off-line preprocessing of the data for improving runtime
speed (may require "multi-format" terrain data)
Allow for collision-detection with non-terrain objects.
Allow for physical realism?? For terrain? (may require "multi-format"
data)
Allow for low dynamic modification of terrain data (changes are
infrequent and small == quasi constant)




[snip]

Andreas
Post by MÃ¥rten Svanfeldt (dev)
-Mårten
-------------------------------------------------------
SF.Net email is sponsored by: Discover Easy Linux Migration Strategies
from IBM. Find simple to follow Roadmaps, straightforward articles,
informative Webcasts and more! Get everything you need to get up to
speed, fast. http://ads.osdn.com/?ad_idt77&alloc_id492&op=click
_______________________________________________
Crystal-main mailing list
https://lists.sourceforge.net/lists/listinfo/crystal-main
Mårten Svanfeldt (dev)
2005-06-23 11:08:33 UTC
Permalink
Post by Andreas Grosam
I would like to stick on the "world database" and elaborate more on
Note that i intentionally do not consider anything what is currently
implemented in CS, just for the sake to have an open mind.
Of course none of this exists, if it did we didn't have to discuss it ;)
Post by Andreas Grosam
Since Jorrit anounced a new project, and since there are questions
regarding the Collision-Detection - i think the thoughts below could
be helpfull.
I don't see how this have anything to do with either;)
Post by Andreas Grosam
I would say, a "world database" is a container holding all objects
which exist in a world (game, simulation). At any time the objects
represent the current state of the world.
Ok, you include both the in memory (runtime) and on disk/network structures.
Post by Andreas Grosam
At a very basic level, a world is a set of objects - or more precisely,
it is a set of containers of objects. Since objects might itself be
again containers, it forms a hierarchical strucure.
Terrain, Sound, Particel, Texture, Vegetation, Script, DynamicTexture,
DynamicTerrain, etc.
I think you tend to forget the most important object in the 3d world.. a general
3d mesh :)
Post by Andreas Grosam
Note that a world is "dynamic" and its objects may be related to
others, might be active or passive, and form a complex dependency and
relationship. (So we might identify these roles: controller, owner,
parent, container, group, etc)
Remmeber that we're not after a total rewrite of the CS engine ;)
Post by Andreas Grosam
At least for terrain (hight maps, not including other terrain related
Most of this is of no use to this discussion but is internal to the terrain
Post by Andreas Grosam
Able to handle huge amount of out-of-core world data (>> 1GByte).
Provide a flexible data format which can be easily and (fast, too)
converted to a format suitable for a certain tesselation/render
algorithm, otherwise is a "multi-format".
(Comment, not sure that multiple formats are good.. that often lead to that
people use one and the other become unmaintained)
Post by Andreas Grosam
Allow for off-line preprocessing of the data for improving runtime
speed (may require "multi-format" terrain data)
Allow for low dynamic modification of terrain data (changes are
infrequent and small == quasi constant)
I still think the biggest problem have not been really touched..
1. How to determin what to load and when (without total rewrite :)
2. How to make that loading fast and painless ;) (ok, this is touched :)

-Mårten
Andreas Grosam
2005-06-23 14:08:06 UTC
Permalink
Post by MÃ¥rten Svanfeldt (dev)
Post by Andreas Grosam
I would like to stick on the "world database" and elaborate more on
Note that i intentionally do not consider anything what is currently
implemented in CS, just for the sake to have an open mind.
Of course none of this exists, if it did we didn't have to discuss it ;)
Post by Andreas Grosam
Since Jorrit anounced a new project, and since there are questions
regarding the Collision-Detection - i think the thoughts below could
be helpfull.
I don't see how this have anything to do with either;)
This project deals with creating game engines and creating worlds.
Since both need to store/access world data somehow, they are closely
related.
Post by MÃ¥rten Svanfeldt (dev)
Post by Andreas Grosam
I would say, a "world database" is a container holding all objects
which exist in a world (game, simulation). At any time the objects
represent the current state of the world.
Ok, you include both the in memory (runtime) and on disk/network structures.
Post by Andreas Grosam
At a very basic level, a world is a set of objects - or more
precisely,
it is a set of containers of objects. Since objects might itself be
again containers, it forms a hierarchical strucure.
Terrain, Sound, Particel, Texture, Vegetation, Script, DynamicTexture,
DynamicTerrain, etc.
I think you tend to forget the most important object in the 3d world.. a general
3d mesh :)
What do you mean with a general 3D mesh?

At this point, just think an instance of Terrain might provide this.
Then suppose there is a class "Model3D", which can be used to model
arbitrary manifolds, e.g. using voxels for generating meshes.
An instance of Terrain also may contain terrain related objects (say
buildings, brigdes, power-lines, vegetation, ect.). For its landscape,
it might use a height map (spherical or planar), or it might use a
Model3D - which enables to render arbitrary surfaces as landscape, not
only for planar surfaces, but also for caves, etc., etc.

Note, that an object need not to be stored as meshes in the database,
generating these meshes occurs in two processes: preprocess and runtime
process.
Post by MÃ¥rten Svanfeldt (dev)
Post by Andreas Grosam
Note that a world is "dynamic" and its objects may be related to
others, might be active or passive, and form a complex dependency and
relationship. (So we might identify these roles: controller, owner,
parent, container, group, etc)
Remmeber that we're not after a total rewrite of the CS engine ;)
Others suggested, that it would be sufficient to just let the engine
load several maps sequentially as needed, and just handle only one at
once. What you get with this approach is similar to PlaneShift.
But again others, complained, that exactly this is not sufficient.

If you want a flight / space simulator, a planetary view, a huge world,
a multi player game, more speed, and some more features, you need to
think about changes. There is no way to achieve all this in a perfect
manner without doing any changes - e.g. by just adding a new class or
so.

Fortunately, *here* we do *not* (yet) talk about implementing a perfect
solution - but here we should think about a well designed solution.
(thus, as i mentioned, i do not consider anything already part of CS).

Ok, and since i just noticed that the topic has been changed slightly,
we are talking about solutions of dynamically loading world data ;-)
Post by MÃ¥rten Svanfeldt (dev)
Post by Andreas Grosam
At least for terrain (hight maps, not including other terrain related
Most of this is of no use to this discussion but is internal to the terrain
Post by Andreas Grosam
Able to handle huge amount of out-of-core world data (>> 1GByte).
Provide a flexible data format which can be easily and (fast, too)
converted to a format suitable for a certain tesselation/render
algorithm, otherwise is a "multi-format".
(Comment, not sure that multiple formats are good.. that often lead to that
people use one and the other become unmaintained)
I think this is an automatic process:
There is only one base format. From this, the server preprocesses the
data for several tesselation/renderer algorithm - on the server side. A
client, caches the data on its local disk as it loads it from the
server. Whether the data will be compressed or not is a minor issue.
Of course, this requires that the server knows about the available
renderes.
A certain custom renderer might not get *its* prefered format. But this
is problem usually does not occure, since a complete game supports a
fixed set of known supported renderers.
Post by MÃ¥rten Svanfeldt (dev)
Post by Andreas Grosam
Allow for off-line preprocessing of the data for improving runtime
speed (may require "multi-format" terrain data)
Allow for low dynamic modification of terrain data (changes are
infrequent and small == quasi constant)
I still think the biggest problem have not been really touched..
1. How to determin what to load and when (without total rewrite :)
This is not yet discussed in detail in this thread - but i mentioned
already several algorithms.

Well, just to emphasize it again: we are now talking about how to
visualize huge terrain data in realtime.
This terrain data shall be based on a 2 dimensional height map.
A spherical coordiante system could be used also.
What we exclude for now: huge non-heigtfields, (voxels for instance).

The key to the solution to this problem is: "multi resolution data", or
"continous LOD".

There are several algorithms around, and tons of papers. For a few,
there is also open source available.

Promising papers:
"A Framework for Realtime Visualization with Adaptive Semiregular
Meshes"
"BDAM – Batched Dynamic Adaptive Meshes for High Performance Terrain
Visualization"
"Geometry Clipmaps: Terrain Rendering Using Nested Regular Grids"
"Direct Mesh: a Multiresolution Approach to Terrain Visualization"
"Rendering Massive Terrains Using Chunked Level of Detail Control"

to mention only a few.


There are also papers dealing with the problem of huge textures and
other hight maps or voxels or other concepts, too.

links and software:
<www.terralib.org/>
<http://tulrich.com/geekstuff/chunklod.html>
<www.gvu.gatech.edu/people/peter.lindstrom/software/soar/>
<www9.informatik.uni-erlangen.de/Persons/Roettger>
This site maps to various other sites: <www.vterrain.org>
<www.openscenegraph.org>
Post by MÃ¥rten Svanfeldt (dev)
2. How to make that loading fast and painless ;) (ok, this is touched :)
Of course, the algorithm alone is not yet sufficient. We may need to
consider database support, caching, compression, and many other
features mentioned above.

My suggestion is:
Create a framework, where it is possible to plug-in several algorithm.
The terrain data type should not be restricted to planar hight fields.
It could be anything.
The same for renderers: why not raytracing? There are already
raytracers available that render in realtime. (and why realtime,
anyway?)
So, i just want to emphasize on a general framework which does not
restrict too much.


Andreas
Post by MÃ¥rten Svanfeldt (dev)
-Mårten
-------------------------------------------------------
SF.Net email is sponsored by: Discover Easy Linux Migration Strategies
from IBM. Find simple to follow Roadmaps, straightforward articles,
informative Webcasts and more! Get everything you need to get up to
speed, fast. http://ads.osdn.com/?ad_idt77&alloc_id492&op=click
_______________________________________________
Crystal-main mailing list
https://lists.sourceforge.net/lists/listinfo/crystal-main
res
2005-06-23 14:41:48 UTC
Permalink
Post by Andreas Grosam
What do you mean with a general 3D mesh?
At this point, just think an instance of Terrain might provide this.
Then suppose there is a class "Model3D", which can be used to model
arbitrary manifolds, e.g. using voxels for generating meshes.
Uhm, at the risk of sounding offensive, but what do you know about 3D
graphics?
Practically everything what you see in a 3D game are triangles made out
of vertices (colloquially "meshes"). Guess what, not only they can be
used to model arbitrary manifolds (and are used for that), they're also
native to the graphics hardware. Everything else, be it terrain,
particles systems or characters produces triangles & vertices. Some more
specialized than others for certain tasks. But if you just don't want
anything special (say, a static object), using a "general mesh" (with
the basic idea of using raw triangles + vertices) is natural.

While voxels are certainly interesting, they're not viable for realtime
environments nowadays - not only would they need to be tesselated (ie a
mesh has to be generated), they are rather large in size, and last but
not least there isn't exactly an abundance of creation tools for voxel data.
Post by Andreas Grosam
Note, that an object need not to be stored as meshes in the database,
Does not make sense, as you now know that meshes are the native geometry
representation for 3D graphics.
Post by Andreas Grosam
generating these meshes occurs in two processes: preprocess and runtime
process.
Yes. And runtime processing should be minimized.
Post by Andreas Grosam
There is no way to achieve all this in a perfect
manner without doing any changes - e.g. by just adding a new class or so.
Sure, there will be changes. But the changes devised should be made with
the current engine in mind - to map things to existing functionality as
far as possible.
Post by Andreas Grosam
The key to the solution to this problem is: "multi resolution data", or
Guess what CS' terrain does.
I think that's the kind of thinking Marten wanted to address with "no
rewrite". We have a terrain mesh in CS already, and it does a good job -
there's not much reason to rewrite it. Instead, we should attempt to
retrofit it with whatever we deem necessary to fit into the new grand
scheme.
Post by Andreas Grosam
Of course, the algorithm alone is not yet sufficient. We may need to
consider database support, caching, compression, and many other features
mentioned above.
That sounds like something that should not go into CS. Stuff like DB
support and caching is something that needs to be done on a
per-application base. E.g. PlaneShift would ma need no caching - if they
continue to deliver all the content with the client, retrieving data is
just a matter of opening a file.
OTOH, VOS with it's ultra-dynamic environment may indeed employ some
caching scheme, which may itself again tied to specific properties of
their protocol/system.
Data delivery is highly application-specific. What CS should provide is
an interface were you just pass in a data buffer or stream or so; if a
client needs some elaborate caching scheme, it would be up to him.
Post by Andreas Grosam
Create a framework, where it is possible to plug-in several algorithm.
Incidentally, CS already kind of follows that idea.
Post by Andreas Grosam
The terrain data type should not be restricted to planar hight fields.
It could be anything.
In CS that would probably be a different mesh type.
Post by Andreas Grosam
The same for renderers: why not raytracing? There are already raytracers
available that render in realtime. (and why realtime, anyway?)
Realtime because CS is an SDK for realtime 3D graphics, with a focus on
games. If you want non-realtime rendering, use povray, blender, 3dsmax,
maya...

-f.r.
Andreas Grosam
2005-06-24 00:09:52 UTC
Permalink
Post by res
Post by Andreas Grosam
What do you mean with a general 3D mesh?
At this point, just think an instance of Terrain might provide this.
Then suppose there is a class "Model3D", which can be used to model
arbitrary manifolds, e.g. using voxels for generating meshes.
Uhm, at the risk of sounding offensive, but what do you know about 3D
graphics?
Hm, that's a good question. What do you know about 3D graphics?
But you don't want an answer anyway, so I, either ;-)
Post by res
Practically everything what you see in a 3D game are triangles made out
of vertices (colloquially "meshes").
Guess what, not only they can be
used to model arbitrary manifolds (and are used for that),
they're also native to the graphics hardware.
oh, really? Well, but arn't some sort of triangels better than others?
Post by res
Everything else, be it terrain,
particles systems or characters produces triangles & vertices. Some more
specialized than others for certain tasks. But if you just don't want
anything special (say, a static object), using a "general mesh" (with
the basic idea of using raw triangles + vertices) is natural.
Well, since i now know what meshes are, i would gladly have known what
"general" means exactly (*always* triangles?, regular?, etc.)
Means, requiers CS a certain format?
Post by res
While voxels are certainly interesting, they're not viable for realtime
environments nowadays -
FYI, there are demo games and techdemos running on a modern PC with
Post by res
30 fps.
not only would they need to be tesselated (ie a
mesh has to be generated),
they are rather large in size, and last but
not least there isn't exactly an abundance of creation tools for voxel data.
might be true.
But that doesn't mean, that voxels MUST not be used, and meshes are the
only kind of data.

Anyway, there are not only voxels, there are also fractal algorithm
which could be used for refinement.
These are not meshes nor are they vertices/triangles. I just didn't
want to restrict objects to be defined as mesh only.
Well, of course you can choose meshes only.
Post by res
Post by Andreas Grosam
Note, that an object need not to be stored as meshes in the database,
Does not make sense, as you now know that meshes are the native geometry
representation for 3D graphics.
Please, keep an open mind! ;-)
What about fractal algorithms? They draw vegetation, detailed terrain,
textures, what ever you can imagine.
K, they might be embedded in meshes, somehow.
Post by res
Post by Andreas Grosam
generating these meshes occurs in two processes: preprocess and runtime
process.
Yes. And runtime processing should be minimized.
Post by Andreas Grosam
There is no way to achieve all this in a perfect
manner without doing any changes - e.g. by just adding a new class or so.
Sure, there will be changes. But the changes devised should be made with
the current engine in mind - to map things to existing functionality as
far as possible.
It is not my intention to make changes, yet!
Post by res
Post by Andreas Grosam
The key to the solution to this problem is: "multi resolution data", or
Guess what CS' terrain does.
Sorry, i have too much information available for guessing.
Post by res
I think that's the kind of thinking Marten wanted to address with "no
rewrite". We have a terrain mesh in CS already, and it does a good job -
there's not much reason to rewrite it. Instead, we should attempt to
retrofit it with whatever we deem necessary to fit into the new grand
scheme.
OK, i see. You don't want a flexible and fast multi resolution data
strucure, and you are saying loading is currently fast enough. You also
feel comfortable with the concpet of portals, and that maps will be
loaded at once. You also don't need large terrains, for e.g. flight
simulations, or far distant views, nor "huge" worlds.
Instead, you want to extend the existing solution in order to achieve
what you deem is necessary and fits seamlessly into the existing
solution, for instance choosing a terrain grid, which patches will be
loaded depending on the view position.
Post by res
Post by Andreas Grosam
Of course, the algorithm alone is not yet sufficient. We may need to
consider database support, caching, compression, and many other features
mentioned above.
That sounds like something that should not go into CS. Stuff like DB
support and caching is something that needs to be done on a
per-application base.
Well, i disagree, but in this case, a world database - even a very
limited one, only dealing with terrian data - will not become part of
CS.
Post by res
E.g. PlaneShift would ma need no caching - if they
continue to deliver all the content with the client, retrieving data is
just a matter of opening a file.
OTOH, VOS with it's ultra-dynamic environment may indeed employ some
caching scheme, which may itself again tied to specific properties of
their protocol/system.
Data delivery is highly application-specific. What CS should provide is
an interface were you just pass in a data buffer or stream or so; if a
client needs some elaborate caching scheme, it would be up to him.
Post by Andreas Grosam
Create a framework, where it is possible to plug-in several algorithm.
Incidentally, CS already kind of follows that idea.
I didn't meant to define a plug-in architecture, merely an interface,
but - as you said - you don´t need different algorithms anyway. Hence
also no different preprocesses nor different kinds of data structures
for your meshes.
Post by res
Post by Andreas Grosam
The terrain data type should not be restricted to planar hight fields.
It could be anything.
In CS that would probably be a different mesh type.
Post by Andreas Grosam
The same for renderers: why not raytracing? There are already
raytracers
available that render in realtime. (and why realtime, anyway?)
Realtime because CS is an SDK for realtime 3D graphics, with a focus on
games. If you want non-realtime rendering, use povray, blender, 3dsmax,
maya...
Andreas
Post by res
-f.r.
res
2005-06-24 12:58:10 UTC
Permalink
Post by Andreas Grosam
oh, really? Well, but arn't some sort of triangels better than others?
All triangles are created equal.
Post by Andreas Grosam
Well, since i now know what meshes are, i would gladly have known what
"general" means exactly (*always* triangles?, regular?, etc.)
Means, requiers CS a certain format?
Well... always triangles - polygons would have to be triangulated
anyway. Not sure what you mean with regular. Generally, for just drawing
an object meshes usually don't need to be very restricted - can have
holes, can be concave... (however, certain algorithms, like the one for
shadow volumes, have such limiting requirements).
Post by Andreas Grosam
FYI, there are demo games and techdemos running on a modern PC with >30
fps.
I recall that there was some game using voxels... I forgot the name, but
I remember that at the time 3D acceleration was used quite commonly, yet
the use of voxels restricted the rendering to software and relatively
low screen resolutions (512x384 or so) which meant that it looked ugly.
Voxels may work, but in comparison they can currently probably not stand
up to mesh graphics in terms of quality.
Post by Andreas Grosam
might be true.
But that doesn't mean, that voxels MUST not be used, and meshes are the
only kind of data.
No. In fact, I recall that Anders played with voxels and made a mesh
plugin once. But for practical purposes, focus should be on triangle meshes.
Post by Andreas Grosam
Anyway, there are not only voxels, there are also fractal algorithm
which could be used for refinement.
AFAIK one common approach for refinement is to, below a certia
Post by Andreas Grosam
These are not meshes nor are they vertices/triangles. I just didn't want
to restrict objects to be defined as mesh only.
Well, of course you can choose meshes only.
I'm not opposed against alternative data storage. But in the context of
dynamic (un)loading of world elements, the best way to achieve "load
stuff fast" is to use meshes as far as sensible.
Post by Andreas Grosam
Please, keep an open mind! ;-)
What about fractal algorithms? They draw vegetation, detailed terrain,
textures, what ever you can imagine.
K, they might be embedded in meshes, somehow.
Well, I'd see it the other way round, for those specializations, meshes
are created dynamically from some "other" data, like, a heightmap for
terrain, or a "plant distribution" map for vegetation.
Vegetation is also a good example that "all objects stored as meshes" is
actually not the mean to all ends - for vegetation you would exactly not
want every tuft of grass, rather employ a nice scheme that generates
foliage geometry in an area just around the player. Particle systems are
other examples for dynamic meshes.

About generating data with fractal algorithms: as known, whole (small)
3D games have been fit into a size of 64k, thanks to extensive use of
algorithmically generated geometry and textures. However, in those
cases, you pay for size with a (relatively) long startup time, as all
those resources need to be generated first (and on every startup again).
Thus, for dynamic loading, fractal algorithms only have limited
applicability.
Post by Andreas Grosam
OK, i see. You don't want a flexible and fast multi resolution data
strucure, and you are saying loading is currently fast enough. You also
feel comfortable with the concpet of portals, and that maps will be
loaded at once. You also don't need large terrains, for e.g. flight
simulations, or far distant views, nor "huge" worlds.
No, I didn't say that. (But I do feel comfortable with portals and
sectors. They allow useful stuff like culling of invisible geometry on
the one, and "special effects" on the other. But as initially specified
by Jorrit, they're not useful in the "big landscape" scenario; but they
are in indoor scenarios.)
Post by Andreas Grosam
Instead, you want to extend the existing solution in order to achieve
what you deem is necessary and fits seamlessly into the existing
solution, for instance choosing a terrain grid, which patches will be
loaded depending on the view position.
If that works well, why not? I just think we should start with what we
have already. Writing some newer and fancier stuff can be done, but it
takes time and resources. I also think that we should keep openness in
mind - right now, you're free to implement any of those algorithms in CS
as a mesh object. So, if you would like to use some other terrain algo
with your world, the system should allow for that.
Post by Andreas Grosam
Well, i disagree, but in this case, a world database - even a very
limited one, only dealing with terrian data - will not become part of CS.
Well, there was also a misunderstanding on my side. With DB I associate
stuff like "MySQL" etc. But as you stated at another place, with DB you
roughly mean "map storage". In that sense, a simple XML world is a DB
already... What I wanted to say was: nothing fancy. Basic support, yes -
we don't want to deprive anyone of the possibility to just load a map file.

-f.r.

Jorrit Tyberghein
2005-06-23 15:55:02 UTC
Permalink
Post by Andreas Grosam
This project deals with creating game engines and creating worlds.
Since both need to store/access world data somehow, they are closely
related.
Actually not really. There will be no loading of data here as the data
is already in memory loaded by Blender itself. The CS/GameEngine will
simply use that data through internal API calls from Blender to CS (at
least that's the idea for the final product). Dynamic loading is not
an issue here at all.

Greetings,
--
Project Manager of Crystal Space (http://www.crystalspace3d.org)
and CEL (http://cel.crystalspace3d.org)
res
2005-06-23 14:47:21 UTC
Permalink
Post by MÃ¥rten Svanfeldt (dev)
I still think the biggest problem have not been really touched..
1. How to determin what to load and when (without total rewrite :)
Perhaps we can develop something by staring with the zone stuff in
CEL... afaik, there are sector sets stored somewhere, ie what sectors to
keep in memory when you are in a specific sector. When you change
sectors, sectors are accordingly loaded/unloaded.

A naive idea: split the world into a "3D grid". When you move about, you
change the cell, and thus the set of neighbouring cells change. You
would then load/unload objects in the changed cells...

-f.r.
Reed Hedges
2005-06-23 15:47:22 UTC
Permalink
A general comment for these discussions on world loading and large worlds, some
of us don't use the map/world file :) So don't let solutions be hidden away in the
world file parser/loader if it's possible to have them live in the engine or the
mesh object classes :)

Reed
Andreas Grosam
2005-06-16 23:54:40 UTC
Permalink
Post by Jorrit Tyberghein
Lately many people seem to be interested in developing a game with
Crystal Space that has a huge world.
This sounds like a geospatial data management.

What exactly are the requirements for such a feature?
fast zooming, fast motion?
Procedural geometry (e.g. automated vegation generation)?
An accompanying terrain editor?
Automatic generation of landform structures?
How well shall it scale? (what is "huge" in terms of amount of data)
How partitioned? (collection of volumes or tiles, grids)
Multiresolution Terrain Model (LOD)? (see indexing structures:
"LOD-quadtree", "direct mesh")
Distributed database?
details of spatial modelling? which type of data model? (spatial
enties, edges, nodes, volumns, etc.)

Andreas
Post by Jorrit Tyberghein
Typically this is done for MMORPG
games. PlaneShift is currently the game with the biggest online world
and they solved this issue by having loading pauses whenever a new
area needs to be loaded and they also make sure that different regions
are connected through small portals. i.e. no large outside plains that
are different regions.
However, this may not be a suitable solution for everyone. It would be
ideal if you could really have a really big world that never shows a
loading screen but which still has sufficient detail everywhere. To
accomplish that I think that we basically need to work on two issues
1. Support for paging terrain engine. The current terrain engine can
support relatively big landscapes but if you really want a HUGE
landscape then it will not work nicely. Solutions like trying to solve
this with different sectors and different landscape meshes that need
to connect at the borders are hacky at best and have several
disadvantages: hard to connect landscapes without seams, overhead of
having many portals, hard to manage, big memory requirements for every
landscape mesh, ... Much better would be if the terrain engine itself
supported paging so that it can swap in/out parts of the terrain as
needed. Crystal Space has a memory mapping facility. Perhaps this can
be used for that?
2. Support for streaming of objects. The current map loading system in
CS is good and flexible but it is not really suitable for fast input
of objects. I wonder if we shouldn't have some kind of fast
intermediate format that is specifically designed for very fast
loading and can also be done in the background (thread).
I would like to discuss these two things as I feel they are important
for the future of CS. First we need to discuss what exactly needs to
be done to make this work. And finally we need to find someone who can
help implement this.
Greetings,
--
Project Manager of Crystal Space (http://www.crystalspace3d.org)
and CEL (http://cel.sf.net)
-------------------------------------------------------
SF.Net email is sponsored by: Discover Easy Linux Migration Strategies
from IBM. Find simple to follow Roadmaps, straightforward articles,
informative Webcasts and more! Get everything you need to get up to
speed, fast. http://ads.osdn.com/?ad_idt77&alloc_id492&op=click
_______________________________________________
Crystal-main mailing list
https://lists.sourceforge.net/lists/listinfo/crystal-main
Chris Case
2005-06-17 01:17:21 UTC
Permalink
Something that would aid in this 'Huge World Support' quest would be good
documentation on LOD, and how to use it in your CS/CEL app... I've not seen
any really good documentation on the subject... and it would be nice.. plus
it's simplier than any engine changes ;) .

Just a wish, tis all.

--Chris
Post by Andreas Grosam
Post by Jorrit Tyberghein
Lately many people seem to be interested in developing a game with
Crystal Space that has a huge world.
This sounds like a geospatial data management.
What exactly are the requirements for such a feature?
fast zooming, fast motion?
Procedural geometry (e.g. automated vegation generation)?
An accompanying terrain editor?
Automatic generation of landform structures?
How well shall it scale? (what is "huge" in terms of amount of data)
How partitioned? (collection of volumes or tiles, grids)
"LOD-quadtree", "direct mesh")
Distributed database?
details of spatial modelling? which type of data model? (spatial
enties, edges, nodes, volumns, etc.)
Andreas
Post by Jorrit Tyberghein
Typically this is done for MMORPG
games. PlaneShift is currently the game with the biggest online world
and they solved this issue by having loading pauses whenever a new
area needs to be loaded and they also make sure that different regions
are connected through small portals. i.e. no large outside plains that
are different regions.
However, this may not be a suitable solution for everyone. It would be
ideal if you could really have a really big world that never shows a
loading screen but which still has sufficient detail everywhere. To
accomplish that I think that we basically need to work on two issues
1. Support for paging terrain engine. The current terrain engine can
support relatively big landscapes but if you really want a HUGE
landscape then it will not work nicely. Solutions like trying to solve
this with different sectors and different landscape meshes that need
to connect at the borders are hacky at best and have several
disadvantages: hard to connect landscapes without seams, overhead of
having many portals, hard to manage, big memory requirements for every
landscape mesh, ... Much better would be if the terrain engine itself
supported paging so that it can swap in/out parts of the terrain as
needed. Crystal Space has a memory mapping facility. Perhaps this can
be used for that?
2. Support for streaming of objects. The current map loading system in
CS is good and flexible but it is not really suitable for fast input
of objects. I wonder if we shouldn't have some kind of fast
intermediate format that is specifically designed for very fast
loading and can also be done in the background (thread).
I would like to discuss these two things as I feel they are important
for the future of CS. First we need to discuss what exactly needs to
be done to make this work. And finally we need to find someone who can
help implement this.
Greetings,
--
Project Manager of Crystal Space (http://www.crystalspace3d.org)
and CEL (http://cel.sf.net)
-------------------------------------------------------
SF.Net <http://SF.Net> email is sponsored by: Discover Easy Linux
Migration Strategies
Post by Jorrit Tyberghein
from IBM. Find simple to follow Roadmaps, straightforward articles,
informative Webcasts and more! Get everything you need to get up to
speed, fast. http://ads.osdn.com/?ad_idt77&alloc_id492&op=click
_______________________________________________
Crystal-main mailing list
https://lists.sourceforge.net/lists/listinfo/crystal-main
-------------------------------------------------------
SF.Net <http://SF.Net> email is sponsored by: Discover Easy Linux
Migration Strategies
from IBM. Find simple to follow Roadmaps, straightforward articles,
informative Webcasts and more! Get everything you need to get up to
speed, fast. http://ads.osdn.com/?ad_idt77&alloc_id492&opclick
_______________________________________________
Crystal-main mailing list
https://lists.sourceforge.net/lists/listinfo/crystal-main
?subjectunsubscribe
--
Christopher S. Case
SUNY Fredonia Co/Op Engineering
***@gmail.com
(716) 673 - 4396 (Dorm)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
"To err is human. To forgive, divine.
To fix mistakes, now that's an Engineer."
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Keith Fulton
2005-06-19 20:11:55 UTC
Permalink
Another problem implicit in these problems is defining a way to store the
metadata about all the objects so that the bg loader knows what it can load
and discard at each point in the game. Doing this efficiently seems like
the trickiest part (least well understood) part of this whole task.
Perhaps there must be a meta-map file which defines a kd-tree of zones
which has nodes which define what to load/unload.

I liked res' idea below about keeping administrative data separate from the
bulk data. Perhaps the admin data could be part of the meta-map, and
contain pointers to all the detailed raw streams of bulk. If all the
meshes in the huge world were loaded in skeletal form at the beginning,
then it would be easier for the bg loader to understand what is required to
be rehydrated or dehydrated as the player moves about the world...

I don't know much about this subject but I think the threading issues are
not as difficult as defining the overall scheme here.

Keith
Date: Thu, 16 Jun 2005 13:08:10 +0200
Subject: [CsMain] Re: [Crystal-develop] Huge Worlds
This is an OpenPGP/MIME signed message (RFC 2440 and 3156)
--------------enigCBCFE7E50C5D895DCBEFA6C8
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Post by Jorrit Tyberghein
1. Support for paging terrain engine. The current terrain engine can
support relatively big landscapes but if you really want a HUGE
landscape then it will not work nicely. Solutions like trying to solve
this with different sectors and different landscape meshes that need
to connect at the borders are hacky at best and have several
disadvantages: hard to connect landscapes without seams, overhead of
having many portals, hard to manage, big memory requirements for every
landscape mesh, ... Much better would be if the terrain engine itself
supported paging so that it can swap in/out parts of the terrain as
needed. Crystal Space has a memory mapping facility. Perhaps this can
be used for that?
I recall the olde "terrbig" did that (but as we know that terrain was
eventually
scrapped).
Memory mapping is probably the way to go. But swapped in/out should not
only be
geometry data, but also texture data (like splat maps, base maps).
Post by Jorrit Tyberghein
2. Support for streaming of objects. The current map loading system in
CS is good and flexible but it is not really suitable for fast input
of objects. I wonder if we shouldn't have some kind of fast
intermediate format that is specifically designed for very fast
loading and can also be done in the background (thread).
I think we can split the data needed to load a mesh object/factory in two
"administrative" (flags, materials and such stuff) and "geometry" (vertex
coordinates, triangles, you get the idea). I think the administrative data
is
usually very small and could thus stay stored in documents (XML or
binary),
while the geometry is best stored as raw as possible - think float[]
dumped to a
disk. If any relatively time-consuming processing is done beforehand, the
only
processing at load time needed would be endianness conversion (if the
endian
happens to be different).
Sidebar: considering that (afaik) the major target processors for CS (x86,
PowerPC) and probably a good deal of other platforms use IEEE floats, it
would
probably be more performant to not encode floats using csFloatToLong() -
obviously, as all that bit fiddling and float construction is saved. Of
course
platforms w/o IEEE floats need conversion - I'd think the cost would be
the same
as the current csLongToFloat(), just that only a fraction of the platforms
would
have to pay it.
-f.r.
--------------enigCBCFE7E50C5D895DCBEFA6C8
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: OpenPGP digital signature
Content-Disposition: attachment; filename="signature.asc"
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (MingW32)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
iD8DBQFCsV2eNCTzcE/07ewRAvZcAJ4jGQl8gswobgXy0dpNAZIyj0OKsACgof9I
7tn5dn5tCbEd/qe7CmGjHKQ=iJ4L
-----END PGP SIGNATURE-----
--------------enigCBCFE7E50C5D895DCBEFA6C8--
Peter Amstutz
2005-06-19 23:42:43 UTC
Permalink
Post by Keith Fulton
Another problem implicit in these problems is defining a way to store the
metadata about all the objects so that the bg loader knows what it can load
and discard at each point in the game. Doing this efficiently seems like
...
I don't know much about this subject but I think the threading issues are
not as difficult as defining the overall scheme here.
I agree that an overall design is needed, but I also think that different
application have different design requirements. The direction I'm coming
at this is in the context of VOS, which is going to be downloading world
data on the fly rather and not pulling it from a (relatively) fast-access
medium like a CD or hard disk. This also means you have less
foreknowledge or metadata about the size and shape of the world. So a
system in CS for background loading/preloading world data either needs to
be flexible enough to handle this, or at least the background loading
primitives need to be available so I can write my own code independent of
the CS loading system.

Hence my interest in the more immediate goals of being able to construct
objects in a background thread and push it into the engine with as little
delay in the rendering loop as possible.

[ Peter Amstutz ][ ***@interreality.org ][ ***@anteon.com ]
[Lead Programmer][Interreality Project][Virtual Reality for the Internet]
[ VOS: Next Generation Internet Communication][ http://interreality.org ]
[ http://interreality.org/~tetron ][ pgpkey: pgpkeys.mit.edu 18C21DF7 ]
Chris Case
2005-06-20 02:46:23 UTC
Permalink
I have to agree with this here, as my game is going to have most of the
world data on a server, not on the local computer (mmorpg games will most
likely all have the same requirement here.) I too would want this to be
flexible enough, or be able to write my own code for it.

--Chris
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
Post by Keith Fulton
Another problem implicit in these problems is defining a way to store
the
Post by Keith Fulton
metadata about all the objects so that the bg loader knows what it can
load
Post by Keith Fulton
and discard at each point in the game. Doing this efficiently seems like
...
I don't know much about this subject but I think the threading issues
are
Post by Keith Fulton
not as difficult as defining the overall scheme here.
I agree that an overall design is needed, but I also think that different
application have different design requirements. The direction I'm coming
at this is in the context of VOS, which is going to be downloading world
data on the fly rather and not pulling it from a (relatively) fast-access
medium like a CD or hard disk. This also means you have less
foreknowledge or metadata about the size and shape of the world. So a
system in CS for background loading/preloading world data either needs to
be flexible enough to handle this, or at least the background loading
primitives need to be available so I can write my own code independent of
the CS loading system.
Hence my interest in the more immediate goals of being able to construct
objects in a background thread and push it into the engine with as little
delay in the rendering loop as possible.
[Lead Programmer][Interreality Project][Virtual Reality for the Internet]
[ VOS: Next Generation Internet Communication][ http://interreality.org ]
[ http://interreality.org/~tetron ][ pgpkey: pgpkeys.mit.edu<http://pgpkeys.mit.edu>18C21DF7 ]
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.0 (GNU/Linux)
iD8DBQFCtiCfaeHUyhjCHfcRAhX4AKCe991+fvrBxN2S/2hKahzTMHyTiwCfTl3P
PyHVqN71T43WpB0pvNxlnsk=
=xSle
-----END PGP SIGNATURE-----
-------------------------------------------------------
SF.Net <http://SF.Net> email is sponsored by: Discover Easy Linux
Migration Strategies
from IBM. Find simple to follow Roadmaps, straightforward articles,
informative Webcasts and more! Get everything you need to get up to
speed, fast. http://ads.osdn.com/?ad_id=7477&alloc_id=16492&op=click
_______________________________________________
Crystal-main mailing list
https://lists.sourceforge.net/lists/listinfo/crystal-main
?subject=unsubscribe
--
Christopher S. Case
SUNY Fredonia Co/Op Engineering
***@gmail.com
(716) 673 - 4396 (Dorm)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
"To err is human. To forgive, divine.
To fix mistakes, now that's an Engineer."
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
res
2005-06-20 15:47:22 UTC
Permalink
Post by Peter Amstutz
The direction
I'm coming at this is in the context of VOS, which is going to be
downloading world data on the fly rather and not pulling it from a
(relatively) fast-access medium like a CD or hard disk. This also means
you have less foreknowledge or metadata about the size and shape of the
world.
Just some thoughts: In some respects "online" and "offline" storage are quite
similar. Even hard-disk or CDs are relatively fast, you still have an delay when
loading data to it; it is small, but still can cause hitches; hence I think both
disk and network access can be abstracted to a data source that you ask for some
resource and get it back some time later (disk access: e.g. use asynchronous
reads) - maybe just in milliseconds, maybe after seconds, but in both cases
you'll have to deal with inserting the new data into the engine (or updating
some meshes' geometry, or have the mesh check whether the geometry already arrived).

-f.r.
Juhana Sadeharju
2005-06-21 07:58:12 UTC
Permalink
What kind of terrain CS has now? I have found code for ChunkLOD:

http://tulrich.com/geekstuff/chunklod.html
http://www.vlad1.com/~vladimir/projects/osg/ CLOD as openscenegraph node
http://csp.sourceforge.net flight simulator with CLOD screenshots

Juhana
--
http://music.columbia.edu/mailman/listinfo/linux-graphics-dev
for developers of open source graphics software
Jorrit Tyberghein
2005-06-21 08:02:54 UTC
Permalink
Chunklod has been removed some time ago. Our current terrain engine is
the bruteblock one.

Greetings,
Post by Juhana Sadeharju
http://tulrich.com/geekstuff/chunklod.html
http://www.vlad1.com/~vladimir/projects/osg/ CLOD as openscenegraph node
http://csp.sourceforge.net flight simulator with CLOD screenshots
Juhana
--
http://music.columbia.edu/mailman/listinfo/linux-graphics-dev
for developers of open source graphics software
-------------------------------------------------------
SF.Net email is sponsored by: Discover Easy Linux Migration Strategies
from IBM. Find simple to follow Roadmaps, straightforward articles,
informative Webcasts and more! Get everything you need to get up to
speed, fast. http://ads.osdn.com/?ad_id=7477&alloc_id=16492&op=click
_______________________________________________
Crystal-main mailing list
https://lists.sourceforge.net/lists/listinfo/crystal-main
--
Project Manager of Crystal Space (http://www.crystalspace3d.org)
and CEL (http://cel.sf.net)
Juhana Sadeharju
2005-06-21 07:58:15 UTC
Permalink
About sharing data between the cells.

Is it still recommended to store all textures to one large
hardware texture? Or can the textures kept in their own hardware
textures?

If mipmaps of a texture need not be in one large hardware
texture for efficiency, the cells could share only the common
mipmap levels and save the hardware memory.

LODs would be shared in similar manner. Each LOD level could
be a separate file. This would work with progressive LODs as
well.

How the data should be named? The LOD and mipmap generation
routines should name the data they generate. E.g., if a LOD
generator receives "object", then LOD generator defines the
name "object-lodlevel3". Each cell which needs the level 3
of the LOD can now query the disk server with that name.

Juhana
--
http://music.columbia.edu/mailman/listinfo/linux-graphics-dev
for developers of open source graphics software
Juhana Sadeharju
2005-06-21 07:58:18 UTC
Permalink
For huge worlds, I would divide the scene to cells. The renderer
would need only the render data associated to the cell where the
player is. The size of cell could be 200x200 meters.

Within the cell the rendered data won't change in the memory.
The data could still hold progressive LODs, of course.
Or have entire terrain with all finest details held in memory.

In generating the data to a cell, the world need not be
considered to be celled. Only the pos and size of the cell to
which we generate the data may have use. If we do that, then
for each cell we need to go through all objects in the world.
So, it speeds up the generation if we utilize the cells.
E.g., if the next cell, between the cell and the object, has
approximated the object as an impostor, the cell may use
the same impostor.

A good way to generate the data could be to go through all the
objects and make LODs and impostors to the cells. No occlusion
culling would be needed but it would speed up the generation if
we would not have to generate viewdependent LODs and impostors
for each cell.

Going through the objects one-by-one would generate one impostor
per object. We could combine the impostors later by clustering
them and generating one impostor per cluster. But this could be
slow. It could be faster to, e.g, create a skybox for the cell
and render distant objects directly to the skybox.

In any case, with square cells we would have to keep at most
data of four cells in memory. The four cells likely would have
shared data.

Juhana
--
http://music.columbia.edu/mailman/listinfo/linux-graphics-dev
for developers of open source graphics software
Juhana Sadeharju
2005-06-21 07:58:21 UTC
Permalink
Post by Jorrit Tyberghein
Post by res
If you look at PNG, JPG or TGA loading, you can notice that those loaders
actually use a 2nd thread for decompression.
Yes, but at some point you need to register a texture for the renderer
too which does mipmap generation and other stuff.
What is this "renderer"? I understand that there is the renderer
which renders the scene real-time to the screen, but I don't
understand why it should perform mipmap generation in real-time.

Juhana
--
http://music.columbia.edu/mailman/listinfo/linux-graphics-dev
for developers of open source graphics software
Jorrit Tyberghein
2005-06-21 08:02:14 UTC
Permalink
Post by Juhana Sadeharju
What is this "renderer"? I understand that there is the renderer
which renders the scene real-time to the screen, but I don't
understand why it should perform mipmap generation in real-time.
Well, unless you use DDS images which have mipmaps included in the
image itself you need to generate mipmaps the first time a texture is
loaded.

Greetings,
--
Project Manager of Crystal Space (http://www.crystalspace3d.org)
and CEL (http://cel.sf.net)
Timothy Whitfield
2005-06-21 21:45:01 UTC
Permalink
I can already tell by the little I have read on this
topic I may be in over my head, but I would like to
point out the KISS method in looking at this change
and point out that perhaps so many changes aren't
needed to Crystal Space in order to provide the HUGE
WORLD solution.

As far as the terrain goes, I am currently looking at
the possibility of modifying the TerraFormer to be
able to use multiple heightmaps. Of course this makes
intertwining mesh objects with the terrain more
difficult, but I am waiting to see what is necessary
once I have a multiple terrain terraformer running in
order to facilitate merging it back into the central
world concept of Crystal Space.

As far as meshed worlds, it seems that Crystal Space
is almost already capable of having the map altered in
mid run. With the old renderer I was able to make a
sample where a button press would add on a few extra
sectors and set the necessary polygons to portals;
however the light map data for the new sectors was not
computed. Although I haven't yet tried to reimplement
that old test with the new renederer it would seem
that atleast the lightmap problem due to it being
precalculated now, is a thing of the past.

Heightmaps and meshes are neither difficult to load
quickly, and I would even say that it is possible they
need not even to be loaded in the background, but
rather at some other pause in processing.

This of course brings us to materials, textures and
other items consisting of longer load times. At this
point, it seems that for terrain for instance, there
are only so many different textures you would use for
the world in general, that although the terrain itself
was streaming in, the textures need not do the same.
I would imagine this true of large indoor worlds.

I am completely humbled by the discussion that is
going on in order to rectify Crystal Space's HUGE
WORLD accessibility; however, I do believe that the
answers to this can be found at a much less intense
level. Currently, the map loader will only load a
single map, if it were able to load another map while
the current one was in use and then snap them together
at the appropriate second while simultaneosly freeing
other now uneeded maps, we could essentially
accomplish the same goals. I think the fact that
Crystal Space maps are already divided into sectors to
keep the geometries organized in a way where it is
always easy to tell which of them are closest to the
camera, central point, etc.. makes this process easier
on Crystal Space than it could be to some "other"
engines who have no concept of polygon order short of
sorting.

Of course some of the methods I have proposed also add
restrictions on the world that could be created using
these techniques, but I think that most will find
hiding these "restrictions" under creative world
design more enjoyable than blatently stopping the user
for yet another pause period.

But as I said before, all of you seem to be well in
advance at this point of my understanding of this
creature; however, I plead that simple small changes
be considered as opposed to large redesigns that will
find Crystal Space wanting for these features for much
time to come.

Also, as I pointed out earlier, I will be playing with
the Terraformer and the Sampler if anyone has any
particular direction you would like to point me in.

Timothy Whitfield



____________________________________________________
Yahoo! Sports
Rekindle the Rivalries. Sign up for Fantasy Football
http://football.fantasysports.yahoo.com
Continue reading on narkive:
Loading...