Game Dev Algorithms

A static bounding-sphere hierarchy won't help, but a dynamic one will. =
Check
out John Radcliffe's demo - it's an excellent illustration of dynamic
bounding-sphere hierarchies.

Tom Forsyth - Muckyfoot bloke.

What's he up to now (and in the past)?
http://www.muckyfoot.com/startopia/camgal.html


> -----Original Message-----
> From: David Lam [mailto:dlam@...]
> Sent: 25 April 2001 09:32
> To: 'gdalgorithms-list@...'
> Subject: RE: [Algorithms] Sphere - sphere collision
>=20
>=20
> Are your spheres all moving independently? If so then bounding sphere
> hierachy wont help you. You need sorted coordinate list or=20
> spatial hashing
> scheme. I have never seen these being describe by themselves.=20
> I found them
> mention in I-collide (Lin-Canny) and Impulse (Mirtich) paper,=20
> use in their
> collision detection scheme as a way to reduce body to body checks.
>=20
> David Lam
> Reflections
>=20
> -----Original Message-----
> From: Joakim Eriksson [mailto:jme@...]
> Sent: 24 April 2001 17:10
> To: gdalgorithms-list@...
> Subject: SV: [Algorithms] Sphere - sphere collision
>=20
>=20
>=20
> I'm allready using the fast 'non square root' sphere - sphere=20
> test and it did quite a lot. The problem is that doing the worst=20
> possible thing you can do. That is doing (n^2 - n)/2 such tests
> per frame. So what I need information about is that=20
> 'bounding sphere hierachy' thing.
> In other words something that makes sure I do as few of these tests
> as possible.
> So any reference that describe that would be nice.
>=20
>=20
> -----Ursprungligt meddelande-----
> Fr=E5n: Conor Stokes [mailto:cstokes@...]
> Skickat: den 24 april 2001 17:52
> Till: gdalgorithms-list@...
> =C4mne: Re: [Algorithms] Sphere - sphere collision
>=20
>=20
> > I'm playing around a bit with collision detection and I'm=20
> on a problem
> > where I have a
> > lot of spheres and want to let all spheres be able to collide with
> each
> > other.
> > So the question is how to this in a very fast way.
> >
> > I know and have read about the normal OBB and AABB and a bunch of
> other
> > techniques for doing this but I haven't found any specific way to =
do
> > this for simple
> > spheres.
> >
> > BTW. The spheres does have variating radii.
>=20
> Probably with spheres, some sort of bounding sphere hierachy would be
> best
> and could be constructed so it only changed slightly with an error
> metric
> frame to frame. That way you aso only need one collision test.
>=20
> Testing if 2 spheres collide is fairly easy. And you can do it with =
no
> square roots.
>=20
> Here is simple code for it:
>=20
> bool Sphere::Collide(Sphere* against) {
>     Vector3d* diff;
>=20
>     // Difference vector between the centres of the 2 sphere.
>     diff->Difference(Origin(),against->Origin());
>=20
>     // checks if the distance between the centre of the 2 spheres
> squared is
>     // less than the sum of the radii squared.
>=20
>     return ( diff->DotProduct(diff) <  (radius() *=20
> against->radius()) *
> (radius() * against->radius()));
> }
>=20
> Conor Stokes

Apology for speaking too early. I was thinking of other similar algorithm. I
must say I haven't seen John's algorithm before. I was just shown his demo
by someone here who never deletes his email :).

It looks interesting. I suppose the only way to compare its performance is
to look at the algorithm on paper. Sounds like I have to wait for GPG II.

David Lam
Reflections

-----Original Message-----
From: Tom Hubina [mailto:tomh@...]
Sent: 25 April 2001 10:04
To: gdalgorithms-list@...
Subject: RE: [Algorithms] Sphere - sphere collision


At 01:32 AM 4/25/2001, you wrote:
>Are your spheres all moving independently? If so then bounding sphere
>hierachy wont help you.

Actually .. that's what John's thing is all about. A dynamically updated 
hierarchical sphere tree with limits on processing time too (for those of 
us who care that things get done within a certain time frame). A rather 
cool little algo that seems pretty straightforward to implement. There are 
some numbers in there for the heuristics for figuring out when to push a 
sphere back up to the top, and when things are "close enough" to be in the 
same branch and when you need to split stuff off that will need to be 
fiddled with when you try to implement it yourself. At least until the full 
details of the algo have been made available :)

I like the Game Gems authors, but the Draconian agreement you have to sign 
with the publisher prevented me from putting stuff in the first volume .. 
nothing like giving the people who buy the book more rights to the article 
than the author who wrote the dang thing .. sigh. If there wasn't such 
great stuff in there I'd probably boycott :)

Tom


_______________________________________________
GDAlgorithms-list mailing list
GDAlgorithms-list@...
http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
-Virus scanned and cleared ok

Hey, can you forward me the message? I deleted it a while back... :(

MSN

-----Original Message-----
From: Sam McGrath [mailto:sammy@...]
Sent: Tuesday, April 24, 2001 3:31 PM
To: gdalgorithms-list@...
Subject: Re: [Algorithms] Sphere - sphere collision


Yes, the demo was done by John Ratcliff and the thread was "Pack my
spheres
up your frustum".  I have the thread archived on my computer if it can't
be
found online (as well as the attached demo file), so email me, whoever
wants
it.

-Sam

----- Original Message -----
From: "Thatcher Ulrich" <tu@...>
To: <gdalgorithms-list@...>
Sent: Tuesday, April 24, 2001 9:36 AM
Subject: Re: [Algorithms] Sphere - sphere collision


>
> On Tue, 24 Apr 2001, Daniel Renkel wrote:
>
> > wasn't the demo application (2d bouding sphere hierarchies) done by
> > thatcher ulrich ? (blind guess :-)
>
> Nope.  IIRC it was John Ratcliff and it was pretty fun to watch.
>
> If you have GPGems, there's some simple loose quadtree demo code on
the CD
> that shows something vaguely similar, but not as fun to look at.
>
> -Thatcher
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDAlgorithms-list@...
> http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>


_______________________________________________
GDAlgorithms-list mailing list
GDAlgorithms-list@...
http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list

Whoops, that wasn't supposed to go to the list... urgh....

-----Original Message-----
From: Mat Noguchi=20
Sent: Wednesday, April 25, 2001 9:13 AM
To: gdalgorithms-list@...
Subject: RE: [Algorithms] Sphere - sphere collision


Hey, can you forward me the message? I deleted it a while back... :(

MSN

-----Original Message-----
From: Sam McGrath [mailto:sammy@...]
Sent: Tuesday, April 24, 2001 3:31 PM
To: gdalgorithms-list@...
Subject: Re: [Algorithms] Sphere - sphere collision


Yes, the demo was done by John Ratcliff and the thread was "Pack my
spheres
up your frustum".  I have the thread archived on my computer if it can't
be
found online (as well as the attached demo file), so email me, whoever
wants
it.

-Sam

----- Original Message -----
From: "Thatcher Ulrich" <tu@...>
To: <gdalgorithms-list@...>
Sent: Tuesday, April 24, 2001 9:36 AM
Subject: Re: [Algorithms] Sphere - sphere collision


>
> On Tue, 24 Apr 2001, Daniel Renkel wrote:
>
> > wasn't the demo application (2d bouding sphere hierarchies) done by
> > thatcher ulrich ? (blind guess :-)
>
> Nope.  IIRC it was John Ratcliff and it was pretty fun to watch.
>
> If you have GPGems, there's some simple loose quadtree demo code on
the CD
> that shows something vaguely similar, but not as fun to look at.
>
> -Thatcher
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDAlgorithms-list@...
> http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>


_______________________________________________
GDAlgorithms-list mailing list
GDAlgorithms-list@...
http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list

_______________________________________________
GDAlgorithms-list mailing list
GDAlgorithms-list@...
http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list

this is just a general question and maybe it has been answered before, but i
havent read anything in the past months so im asking now. what is the best
way to do culling on moving objects like players or monsters or whatever? i
know several possibilities for static geometry like quadtrees, octrees,
scene graphs etc. but can i use those efficiently for moving objects? i
would always have to update the trees and that doesnt look good for me...
so how is it done normally? just test _all_ the single objects by their
bounding boxes/spheres? might not be so bad when i have only 50 moving
objects in my game...? but what other approaches to the problem are there?

thanx in advance

Turn your precomputed scene graph trees into spatial nodes.
Insert and delete moving objects to the node, not to the branch. As in if
objects move a lot, they themselves should not become a bisecting plane or
sorting criteria of other static and dynamic geometry. Or your graph or tree
would change very often.

Moving objects from node to node is not such a big deal, if traversal of
your tree is pretty fast.

Corrinne Yu

----- Original Message -----
From: "David Zaadstra" <mythomania@...>
To: <gdalgorithms-list@...>
Sent: Wednesday, April 25, 2001 12:03 PM
Subject: [Algorithms] visibility culling for moving objects


> this is just a general question and maybe it has been answered before, but
i
> havent read anything in the past months so im asking now. what is the best
> way to do culling on moving objects like players or monsters or whatever?
i
> know several possibilities for static geometry like quadtrees, octrees,
> scene graphs etc. but can i use those efficiently for moving objects? i
> would always have to update the trees and that doesnt look good for me...
> so how is it done normally? just test _all_ the single objects by their
> bounding boxes/spheres? might not be so bad when i have only 50 moving
> objects in my game...? but what other approaches to the problem are there?
>
> thanx in advance
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDAlgorithms-list@...
> http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>

yeah, that sounds sensible ;-)
any other methods? i dont believe that _everyone_ uses scene graphs....

----- Original Message -----
From: "Corrinne Yu" <corrinney@...>
To: <gdalgorithms-list@...>
Sent: Wednesday, April 25, 2001 8:06 PM
Subject: Re: [Algorithms] visibility culling for moving objects


> Turn your precomputed scene graph trees into spatial nodes.
> Insert and delete moving objects to the node, not to the branch. As in if
> objects move a lot, they themselves should not become a bisecting plane or
> sorting criteria of other static and dynamic geometry. Or your graph or
tree
> would change very often.
>
> Moving objects from node to node is not such a big deal, if traversal of
> your tree is pretty fast.
>
> Corrinne Yu
>
> ----- Original Message -----
> From: "David Zaadstra" <mythomania@...>
> To: <gdalgorithms-list@...>
> Sent: Wednesday, April 25, 2001 12:03 PM
> Subject: [Algorithms] visibility culling for moving objects
>
>
> > this is just a general question and maybe it has been answered before,
but
> i
> > havent read anything in the past months so im asking now. what is the
best
> > way to do culling on moving objects like players or monsters or
whatever?
> i
> > know several possibilities for static geometry like quadtrees, octrees,
> > scene graphs etc. but can i use those efficiently for moving objects? i
> > would always have to update the trees and that doesnt look good for
me...
> > so how is it done normally? just test _all_ the single objects by their
> > bounding boxes/spheres? might not be so bad when i have only 50 moving
> > objects in my game...? but what other approaches to the problem are
there?
> >
> > thanx in advance
> >
> >
> > _______________________________________________
> > GDAlgorithms-list mailing list
> > GDAlgorithms-list@...
> > http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> >
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDAlgorithms-list@...
> http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>

How many moving objects do you have? I find it simpler (and faster)
to keep moving objects totally out of the tree, and just loop through
all of them. I do a quick bounding sphere test for the first level
cull, then if that passes, I do a bounding sphere test on the components
of the model.

Jaimi


-----Original Message-----
From: gdalgorithms-list-admin@...
[mailto:gdalgorithms-list-admin@... Behalf Of David
Zaadstra
Sent: Wednesday, April 25, 2001 1:01 PM
To: gdalgorithms-list@...
Subject: Re: [Algorithms] visibility culling for moving objects


yeah, that sounds sensible ;-)
any other methods? i dont believe that _everyone_ uses scene graphs....

----- Original Message -----
From: "Corrinne Yu" <corrinney@...>
To: <gdalgorithms-list@...>
Sent: Wednesday, April 25, 2001 8:06 PM
Subject: Re: [Algorithms] visibility culling for moving objects


> Turn your precomputed scene graph trees into spatial nodes.
> Insert and delete moving objects to the node, not to the branch. As in if
> objects move a lot, they themselves should not become a bisecting plane or
> sorting criteria of other static and dynamic geometry. Or your graph or
tree
> would change very often.
>
> Moving objects from node to node is not such a big deal, if traversal of
> your tree is pretty fast.
>
> Corrinne Yu
>
> ----- Original Message -----
> From: "David Zaadstra" <mythomania@...>
> To: <gdalgorithms-list@...>
> Sent: Wednesday, April 25, 2001 12:03 PM
> Subject: [Algorithms] visibility culling for moving objects
>
>
> > this is just a general question and maybe it has been answered before,
but
> i
> > havent read anything in the past months so im asking now. what is the
best
> > way to do culling on moving objects like players or monsters or
whatever?
> i
> > know several possibilities for static geometry like quadtrees, octrees,
> > scene graphs etc. but can i use those efficiently for moving objects? i
> > would always have to update the trees and that doesnt look good for
me...
> > so how is it done normally? just test _all_ the single objects by their
> > bounding boxes/spheres? might not be so bad when i have only 50 moving
> > objects in my game...? but what other approaches to the problem are
there?
> >
> > thanx in advance
> >
> >
> > _______________________________________________
> > GDAlgorithms-list mailing list
> > GDAlgorithms-list@...
> > http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> >
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDAlgorithms-list@...
> http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>


_______________________________________________
GDAlgorithms-list mailing list
GDAlgorithms-list@...
http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list

i think we wont have that much moving objects...
say 100
would it make much difference?
or: how much objects does it take to make a real difference?

----- Original Message -----
From: "Jaimi McEntire" <jaimi@...>
To: <gdalgorithms-list@...>
Sent: Wednesday, April 25, 2001 8:47 PM
Subject: RE: [Algorithms] visibility culling for moving objects


> How many moving objects do you have? I find it simpler (and faster)
> to keep moving objects totally out of the tree, and just loop through
> all of them. I do a quick bounding sphere test for the first level
> cull, then if that passes, I do a bounding sphere test on the components
> of the model.
>
> Jaimi
>
>
> -----Original Message-----
> From: gdalgorithms-list-admin@...
> [mailto:gdalgorithms-list-admin@... Behalf Of David
> Zaadstra
> Sent: Wednesday, April 25, 2001 1:01 PM
> To: gdalgorithms-list@...
> Subject: Re: [Algorithms] visibility culling for moving objects
>
>
> yeah, that sounds sensible ;-)
> any other methods? i dont believe that _everyone_ uses scene graphs....
>
> ----- Original Message -----
> From: "Corrinne Yu" <corrinney@...>
> To: <gdalgorithms-list@...>
> Sent: Wednesday, April 25, 2001 8:06 PM
> Subject: Re: [Algorithms] visibility culling for moving objects
>
>
> > Turn your precomputed scene graph trees into spatial nodes.
> > Insert and delete moving objects to the node, not to the branch. As in
if
> > objects move a lot, they themselves should not become a bisecting plane
or
> > sorting criteria of other static and dynamic geometry. Or your graph or
> tree
> > would change very often.
> >
> > Moving objects from node to node is not such a big deal, if traversal of
> > your tree is pretty fast.
> >
> > Corrinne Yu
> >
> > ----- Original Message -----
> > From: "David Zaadstra" <mythomania@...>
> > To: <gdalgorithms-list@...>
> > Sent: Wednesday, April 25, 2001 12:03 PM
> > Subject: [Algorithms] visibility culling for moving objects
> >
> >
> > > this is just a general question and maybe it has been answered before,
> but
> > i
> > > havent read anything in the past months so im asking now. what is the
> best
> > > way to do culling on moving objects like players or monsters or
> whatever?
> > i
> > > know several possibilities for static geometry like quadtrees,
octrees,
> > > scene graphs etc. but can i use those efficiently for moving objects?
i
> > > would always have to update the trees and that doesnt look good for
> me...
> > > so how is it done normally? just test _all_ the single objects by
their
> > > bounding boxes/spheres? might not be so bad when i have only 50 moving
> > > objects in my game...? but what other approaches to the problem are
> there?
> > >
> > > thanx in advance
> > >
> > >
> > > _______________________________________________
> > > GDAlgorithms-list mailing list
> > > GDAlgorithms-list@...
> > > http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> > >
> >
> >
> > _______________________________________________
> > GDAlgorithms-list mailing list
> > GDAlgorithms-list@...
> > http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> >
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDAlgorithms-list@...
> http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDAlgorithms-list@...
> http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>

just thought a bit...
for my current purposes (landscape) a simple method would be to give every
quad in the quadtree a linked list and add/remove objects as necessary.
should be fairly quick and i don't have to test every object.
nevertheless i am/was interested what other ways there are.
thanx for the replies so far..

----- Original Message -----
From: "Jaimi McEntire" <jaimi@...>
To: <gdalgorithms-list@...>
Sent: Wednesday, April 25, 2001 8:47 PM
Subject: RE: [Algorithms] visibility culling for moving objects


> How many moving objects do you have? I find it simpler (and faster)
> to keep moving objects totally out of the tree, and just loop through
> all of them. I do a quick bounding sphere test for the first level
> cull, then if that passes, I do a bounding sphere test on the components
> of the model.
>
> Jaimi
>
>
> -----Original Message-----
> From: gdalgorithms-list-admin@...
> [mailto:gdalgorithms-list-admin@... Behalf Of David
> Zaadstra
> Sent: Wednesday, April 25, 2001 1:01 PM
> To: gdalgorithms-list@...
> Subject: Re: [Algorithms] visibility culling for moving objects
>
>
> yeah, that sounds sensible ;-)
> any other methods? i dont believe that _everyone_ uses scene graphs....
>
> ----- Original Message -----
> From: "Corrinne Yu" <corrinney@...>
> To: <gdalgorithms-list@...>
> Sent: Wednesday, April 25, 2001 8:06 PM
> Subject: Re: [Algorithms] visibility culling for moving objects
>
>
> > Turn your precomputed scene graph trees into spatial nodes.
> > Insert and delete moving objects to the node, not to the branch. As in
if
> > objects move a lot, they themselves should not become a bisecting plane
or
> > sorting criteria of other static and dynamic geometry. Or your graph or
> tree
> > would change very often.
> >
> > Moving objects from node to node is not such a big deal, if traversal of
> > your tree is pretty fast.
> >
> > Corrinne Yu
> >
> > ----- Original Message -----
> > From: "David Zaadstra" <mythomania@...>
> > To: <gdalgorithms-list@...>
> > Sent: Wednesday, April 25, 2001 12:03 PM
> > Subject: [Algorithms] visibility culling for moving objects
> >
> >
> > > this is just a general question and maybe it has been answered before,
> but
> > i
> > > havent read anything in the past months so im asking now. what is the
> best
> > > way to do culling on moving objects like players or monsters or
> whatever?
> > i
> > > know several possibilities for static geometry like quadtrees,
octrees,
> > > scene graphs etc. but can i use those efficiently for moving objects?
i
> > > would always have to update the trees and that doesnt look good for
> me...
> > > so how is it done normally? just test _all_ the single objects by
their
> > > bounding boxes/spheres? might not be so bad when i have only 50 moving
> > > objects in my game...? but what other approaches to the problem are
> there?
> > >
> > > thanx in advance
> > >
> > >
> > > _______________________________________________
> > > GDAlgorithms-list mailing list
> > > GDAlgorithms-list@...
> > > http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> > >
> >
> >
> > _______________________________________________
> > GDAlgorithms-list mailing list
> > GDAlgorithms-list@...
> > http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> >
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDAlgorithms-list@...
> http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDAlgorithms-list@...
> http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>

I think for a few hundred, the time is so negligible that you shouldn't
worry about it.

>> how much objects does it take to make a real difference?

Depends (bad answer, I know). Best idea is to just test it. Code it the
simplest way to start with, and then only optimize it if you need to.

-----Original Message-----
From: gdalgorithms-list-admin@...
[mailto:gdalgorithms-list-admin@... Behalf Of David
Zaadstra
Sent: Wednesday, April 25, 2001 2:01 PM
To: gdalgorithms-list@...
Subject: Re: [Algorithms] visibility culling for moving objects


i think we wont have that much moving objects...
say 100
would it make much difference?
or: how much objects does it take to make a real difference?

----- Original Message -----
From: "Jaimi McEntire" <jaimi@...>
To: <gdalgorithms-list@...>
Sent: Wednesday, April 25, 2001 8:47 PM
Subject: RE: [Algorithms] visibility culling for moving objects


> How many moving objects do you have? I find it simpler (and faster)
> to keep moving objects totally out of the tree, and just loop through
> all of them. I do a quick bounding sphere test for the first level
> cull, then if that passes, I do a bounding sphere test on the components
> of the model.
>
> Jaimi
>
>
> -----Original Message-----
> From: gdalgorithms-list-admin@...
> [mailto:gdalgorithms-list-admin@... Behalf Of David
> Zaadstra
> Sent: Wednesday, April 25, 2001 1:01 PM
> To: gdalgorithms-list@...
> Subject: Re: [Algorithms] visibility culling for moving objects
>
>
> yeah, that sounds sensible ;-)
> any other methods? i dont believe that _everyone_ uses scene graphs....
>
> ----- Original Message -----
> From: "Corrinne Yu" <corrinney@...>
> To: <gdalgorithms-list@...>
> Sent: Wednesday, April 25, 2001 8:06 PM
> Subject: Re: [Algorithms] visibility culling for moving objects
>
>
> > Turn your precomputed scene graph trees into spatial nodes.
> > Insert and delete moving objects to the node, not to the branch. As in
if
> > objects move a lot, they themselves should not become a bisecting plane
or
> > sorting criteria of other static and dynamic geometry. Or your graph or
> tree
> > would change very often.
> >
> > Moving objects from node to node is not such a big deal, if traversal of
> > your tree is pretty fast.
> >
> > Corrinne Yu
> >
> > ----- Original Message -----
> > From: "David Zaadstra" <mythomania@...>
> > To: <gdalgorithms-list@...>
> > Sent: Wednesday, April 25, 2001 12:03 PM
> > Subject: [Algorithms] visibility culling for moving objects
> >
> >
> > > this is just a general question and maybe it has been answered before,
> but
> > i
> > > havent read anything in the past months so im asking now. what is the
> best
> > > way to do culling on moving objects like players or monsters or
> whatever?
> > i
> > > know several possibilities for static geometry like quadtrees,
octrees,
> > > scene graphs etc. but can i use those efficiently for moving objects?
i
> > > would always have to update the trees and that doesnt look good for
> me...
> > > so how is it done normally? just test _all_ the single objects by
their
> > > bounding boxes/spheres? might not be so bad when i have only 50 moving
> > > objects in my game...? but what other approaches to the problem are
> there?
> > >
> > > thanx in advance
> > >
> > >
> > > _______________________________________________
> > > GDAlgorithms-list mailing list
> > > GDAlgorithms-list@...
> > > http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> > >
> >
> >
> > _______________________________________________
> > GDAlgorithms-list mailing list
> > GDAlgorithms-list@...
> > http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> >
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDAlgorithms-list@...
> http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDAlgorithms-list@...
> http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>


_______________________________________________
GDAlgorithms-list mailing list
GDAlgorithms-list@...
http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list

well ... david,

i do believe that most people under estimate the coutn of objects ..

if you want to check if all (expensive to render) alpha blended
plasma-gun shots are visible. and the 7 multiplayers are firing many
shots. 100 is a pretty small count.

for a /good old/ RTS an average of 50 "slower and thus longer staying"
objects and up to 200 "faster moving and thus shorter visible" objects
seems to be low. on a /good old/ FPS for sure, the lower average will
only be about 1/10.

do a search in the archives (-: if you'r lucky enoguh to have archived
all mails :-) for the "pack my spheres up your frustrum" thread [the one
with john ratcliff's demo, we talked about right now].

i think simply sorting your "faster" objects in a "few level" quadtree
and checking them against one "side" of your frsutrum [sort for the
axis, x<0, x>0,  ...] and you get a pretty fast and usefull basic "early
out".

hope that helps,
    Daniel 'SirLeto' Renkel [ D.Renkel@... ]


----- Original Message -----
From: "David Zaadstra" <mythomania@...>
To: <gdalgorithms-list@...>
Sent: Wednesday, April 25, 2001 9:00 PM
Subject: Re: [Algorithms] visibility culling for moving objects


> i think we wont have that much moving objects...
> say 100
> would it make much difference?
> or: how much objects does it take to make a real difference?
>
> ----- Original Message -----
> From: "Jaimi McEntire" <jaimi@...>
> To: <gdalgorithms-list@...>
> Sent: Wednesday, April 25, 2001 8:47 PM
> Subject: RE: [Algorithms] visibility culling for moving objects
>
>
> > How many moving objects do you have? I find it simpler (and faster)
> > to keep moving objects totally out of the tree, and just loop
through
> > all of them. I do a quick bounding sphere test for the first level
> > cull, then if that passes, I do a bounding sphere test on the
components
> > of the model.
> >
> > Jaimi
> >
> >
> > -----Original Message-----
> > From: gdalgorithms-list-admin@...
> > [mailto:gdalgorithms-list-admin@... Behalf Of
David
> > Zaadstra
> > Sent: Wednesday, April 25, 2001 1:01 PM
> > To: gdalgorithms-list@...
> > Subject: Re: [Algorithms] visibility culling for moving objects
> >
> >
> > yeah, that sounds sensible ;-)
> > any other methods? i dont believe that _everyone_ uses scene
graphs....
> >
> > ----- Original Message -----
> > From: "Corrinne Yu" <corrinney@...>
> > To: <gdalgorithms-list@...>
> > Sent: Wednesday, April 25, 2001 8:06 PM
> > Subject: Re: [Algorithms] visibility culling for moving objects
> >
> >
> > > Turn your precomputed scene graph trees into spatial nodes.
> > > Insert and delete moving objects to the node, not to the branch.
As in
> if
> > > objects move a lot, they themselves should not become a bisecting
plane
> or
> > > sorting criteria of other static and dynamic geometry. Or your
graph or
> > tree
> > > would change very often.
> > >
> > > Moving objects from node to node is not such a big deal, if
traversal of
> > > your tree is pretty fast.
> > >
> > > Corrinne Yu
> > >
> > > ----- Original Message -----
> > > From: "David Zaadstra" <mythomania@...>
> > > To: <gdalgorithms-list@...>
> > > Sent: Wednesday, April 25, 2001 12:03 PM
> > > Subject: [Algorithms] visibility culling for moving objects
> > >
> > >
> > > > this is just a general question and maybe it has been answered
before,
> > but
> > > i
> > > > havent read anything in the past months so im asking now. what
is the
> > best
> > > > way to do culling on moving objects like players or monsters or
> > whatever?
> > > i
> > > > know several possibilities for static geometry like quadtrees,
> octrees,
> > > > scene graphs etc. but can i use those efficiently for moving
objects?
> i
> > > > would always have to update the trees and that doesnt look good
for
> > me...
> > > > so how is it done normally? just test _all_ the single objects
by
> their
> > > > bounding boxes/spheres? might not be so bad when i have only 50
moving
> > > > objects in my game...? but what other approaches to the problem
are
> > there?
> > > >
> > > > thanx in advance
> > > >
> > > >
> > > > _______________________________________________
> > > > GDAlgorithms-list mailing list
> > > > GDAlgorithms-list@...
> > > > http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> > > >
> > >
> > >
> > > _______________________________________________
> > > GDAlgorithms-list mailing list
> > > GDAlgorithms-list@...
> > > http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> > >
> >
> >
> > _______________________________________________
> > GDAlgorithms-list mailing list
> > GDAlgorithms-list@...
> > http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> >
> >
> > _______________________________________________
> > GDAlgorithms-list mailing list
> > GDAlgorithms-list@...
> > http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> >
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDAlgorithms-list@...
> http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>

Tom,

-- I don't use scene graphs either, but David Z. wrote in his question that
he is already using scene graph or quad tree or oct tree already.
-- Tom., the "concept" of precomputed nodes (in the case of quads and octs
are axial aligned boxes), and inserting and deleting dynamic objects, is:
-- 1. applicable to quad and octrees
-- 2. very popularly used, and usually works fine enough

Corrinne Yu


----- Original Message -----
From: "Tom Forsyth" <tomf@...>
To: <gdalgorithms-list@...>
Sent: Wednesday, April 25, 2001 1:47 PM
Subject: RE: [Algorithms] visibility culling for moving objects


> IMHO, very few people use scene graphs. Very overrated.
>
> For boring old frustum culling, quad/octrees and so on work just fine.
>
> For fairly constrained worlds, portals and PVS works well.
>
> Didn't we just have this discussion, but w.r.t to collision?
>
>
> Tom Forsyth - Muckyfoot bloke.
>
> What's he up to now (and in the past)?
> http://www.muckyfoot.com/startopia/camgal.html
>
>
> > -----Original Message-----
> > From: David Zaadstra [mailto:mythomania@...]
> > Sent: 25 April 2001 19:01
> > To: gdalgorithms-list@...
> > Subject: Re: [Algorithms] visibility culling for moving objects
> >
> >
> > yeah, that sounds sensible ;-)
> > any other methods? i dont believe that _everyone_ uses scene
> > graphs....
> >
> > ----- Original Message -----
> > From: "Corrinne Yu" <corrinney@...>
> > To: <gdalgorithms-list@...>
> > Sent: Wednesday, April 25, 2001 8:06 PM
> > Subject: Re: [Algorithms] visibility culling for moving objects
> >
> >
> > > Turn your precomputed scene graph trees into spatial nodes.
> > > Insert and delete moving objects to the node, not to the
> > branch. As in if
> > > objects move a lot, they themselves should not become a
> > bisecting plane or
> > > sorting criteria of other static and dynamic geometry. Or
> > your graph or
> > tree
> > > would change very often.
> > >
> > > Moving objects from node to node is not such a big deal, if
> > traversal of
> > > your tree is pretty fast.
> > >
> > > Corrinne Yu
> > >
> > > ----- Original Message -----
> > > From: "David Zaadstra" <mythomania@...>
> > > To: <gdalgorithms-list@...>
> > > Sent: Wednesday, April 25, 2001 12:03 PM
> > > Subject: [Algorithms] visibility culling for moving objects
> > >
> > >
> > > > this is just a general question and maybe it has been
> > answered before,
> > but
> > > i
> > > > havent read anything in the past months so im asking now.
> > what is the
> > best
> > > > way to do culling on moving objects like players or monsters or
> > whatever?
> > > i
> > > > know several possibilities for static geometry like
> > quadtrees, octrees,
> > > > scene graphs etc. but can i use those efficiently for
> > moving objects? i
> > > > would always have to update the trees and that doesnt
> > look good for
> > me...
> > > > so how is it done normally? just test _all_ the single
> > objects by their
> > > > bounding boxes/spheres? might not be so bad when i have
> > only 50 moving
> > > > objects in my game...? but what other approaches to the
> > problem are
> > there?
> > > >
> > > > thanx in advance
> > > >
> > > >
> > > > _______________________________________________
> > > > GDAlgorithms-list mailing list
> > > > GDAlgorithms-list@...
> > > > http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> > > >
> > >
> > >
> > > _______________________________________________
> > > GDAlgorithms-list mailing list
> > > GDAlgorithms-list@...
> > > http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> > >
> >
> >
> > _______________________________________________
> > GDAlgorithms-list mailing list
> > GDAlgorithms-list@...
> > http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> >
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDAlgorithms-list@...
> http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>

I think we might mean different things by "scene graph". I definately
believe in things like quadtrees, hierarchial bounding volumes, PVS systems,
sector maps, portals, etc. But those are "just"
visbility/collision/navigation graphs (and usually a different one for each
role).

In my mind having a "scene graph" implies that you are putting everything
such as meshes, render states, transform matrices, textures, etc, into one
big unified hierarchial graph. And IMHO that's overkill and doesn't win you
much. But we've had this semi-religious discussion before, so let's not go
into that. :-)

However, apologies if I'm mis-using the term "scene-graph". As you can tell
I have found the concepts unappealing and unnecessary, so I haven't actually
looked into the details very much.


Tom Forsyth - Muckyfoot bloke.

What's he up to now (and in the past)?
http://www.muckyfoot.com/startopia/camgal.html


> -----Original Message-----
> From: Corrinne Yu [mailto:corrinney@...]
> Sent: 25 April 2001 20:22
> To: gdalgorithms-list@...
> Subject: Re: [Algorithms] visibility culling for moving objects
> 
> 
> Tom,
> 
> -- I don't use scene graphs either, but David Z. wrote in his 
> question that
> he is already using scene graph or quad tree or oct tree already.
> -- Tom., the "concept" of precomputed nodes (in the case of 
> quads and octs
> are axial aligned boxes), and inserting and deleting dynamic 
> objects, is:
> -- 1. applicable to quad and octrees
> -- 2. very popularly used, and usually works fine enough
> 
> Corrinne Yu
> 
> 
> ----- Original Message -----
> From: "Tom Forsyth" <tomf@...>
> To: <gdalgorithms-list@...>
> Sent: Wednesday, April 25, 2001 1:47 PM
> Subject: RE: [Algorithms] visibility culling for moving objects
> 
> 
> > IMHO, very few people use scene graphs. Very overrated.
> >
> > For boring old frustum culling, quad/octrees and so on work 
> just fine.
> >
> > For fairly constrained worlds, portals and PVS works well.
> >
> > Didn't we just have this discussion, but w.r.t to collision?
> >
> >
> > Tom Forsyth - Muckyfoot bloke.
> >
> > What's he up to now (and in the past)?
> > http://www.muckyfoot.com/startopia/camgal.html
> >
> >
> > > -----Original Message-----
> > > From: David Zaadstra [mailto:mythomania@...]
> > > Sent: 25 April 2001 19:01
> > > To: gdalgorithms-list@...
> > > Subject: Re: [Algorithms] visibility culling for moving objects
> > >
> > >
> > > yeah, that sounds sensible ;-)
> > > any other methods? i dont believe that _everyone_ uses scene
> > > graphs....
> > >
> > > ----- Original Message -----
> > > From: "Corrinne Yu" <corrinney@...>
> > > To: <gdalgorithms-list@...>
> > > Sent: Wednesday, April 25, 2001 8:06 PM
> > > Subject: Re: [Algorithms] visibility culling for moving objects
> > >
> > >
> > > > Turn your precomputed scene graph trees into spatial nodes.
> > > > Insert and delete moving objects to the node, not to the
> > > branch. As in if
> > > > objects move a lot, they themselves should not become a
> > > bisecting plane or
> > > > sorting criteria of other static and dynamic geometry. Or
> > > your graph or
> > > tree
> > > > would change very often.
> > > >
> > > > Moving objects from node to node is not such a big deal, if
> > > traversal of
> > > > your tree is pretty fast.
> > > >
> > > > Corrinne Yu
> > > >
> > > > ----- Original Message -----
> > > > From: "David Zaadstra" <mythomania@...>
> > > > To: <gdalgorithms-list@...>
> > > > Sent: Wednesday, April 25, 2001 12:03 PM
> > > > Subject: [Algorithms] visibility culling for moving objects
> > > >
> > > >
> > > > > this is just a general question and maybe it has been
> > > answered before,
> > > but
> > > > i
> > > > > havent read anything in the past months so im asking now.
> > > what is the
> > > best
> > > > > way to do culling on moving objects like players or 
> monsters or
> > > whatever?
> > > > i
> > > > > know several possibilities for static geometry like
> > > quadtrees, octrees,
> > > > > scene graphs etc. but can i use those efficiently for
> > > moving objects? i
> > > > > would always have to update the trees and that doesnt
> > > look good for
> > > me...
> > > > > so how is it done normally? just test _all_ the single
> > > objects by their
> > > > > bounding boxes/spheres? might not be so bad when i have
> > > only 50 moving
> > > > > objects in my game...? but what other approaches to the
> > > problem are
> > > there?
> > > > >
> > > > > thanx in advance
> > > > >
> > > > >
> > > > > _______________________________________________
> > > > > GDAlgorithms-list mailing list
> > > > > GDAlgorithms-list@...
> > > > > http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> > > > >
> > > >
> > > >
> > > > _______________________________________________
> > > > GDAlgorithms-list mailing list
> > > > GDAlgorithms-list@...
> > > > http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> > > >
> > >
> > >
> > > _______________________________________________
> > > GDAlgorithms-list mailing list
> > > GDAlgorithms-list@...
> > > http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> > >
> >
> > _______________________________________________
> > GDAlgorithms-list mailing list
> > GDAlgorithms-list@...
> > http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> >
> 
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDAlgorithms-list@...
> http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>

----- Original Message -----
From: "Robert Dibley" <RDibley@...>
To: <gdalgorithms-list@...>
Sent: Wednesday, April 25, 2001 1:18 PM
Subject: RE: [Algorithms] Pairs game algorithm...


> Why not reverse the process and fill the board - so you can put your first
> two anywhere at random on an empty board.  Then choose only pairs that can
> work.  At the end you might fail because the last pair are unmatchable,
but
> then you can go a few moves back and try a different approach.  If you
> manage to fill it you know it is solvable.
> Perhaps add in some logic on the filling in side that prevents you from
> leaving a single unconnected hole as well, to reduce the chances of
failure.
> Seems easy enough :-)

Yeah, my way of thinking was similar - but going with moves back and forward
can
put me into infitite loop.. (there is another contraint: I'm aiming on VERY
slow processor -
actually it is set-top-box application ;) and I even haven't good rnd()
routine.. :)) I was thinking
also about picking moves in some semi-random manner, to achieve both
randomness and
lack of holes, but any ideas which I've got resulted in too simple boards -
almost obvious ;)
However you suggested me interesting idea - try to avoid generating holes
which have odd
number of fields.. if I'll manage to do that rest will be easy.. but I'm
wondering about speed of
that algorithm.. currently on my box
for( i=0;i<64;i++ )
{
    for( j=0;j<64;j++ )
    {
        array[ (i<<6) + j ] = 0;
    }
}

take 4 (four!) seconds...

and
for( i=0;i<4096;i++ )
{
    array[ i ] = 0;
}

two seconds... so you see, that too complex algos might result in almost
endless
board generating :))

Best regards from
Kamil Burzynski
ADB Poland, LTD.
 - -
"God, root, what's the difference?"

> for( i=0;i<64;i++ )
> {
>     for( j=0;j<64;j++ )
>     {
>         array[ (i<<6) + j ] = 0;
>     }
> }
> 
> take 4 (four!) seconds...

Eeek !

Erm, I think my old BBC micro could beat that by several orders of magnitude
- what have they given you, a processor where the clock speed is in KHz
rather than MHz ?

If it takes that long you'd surely be better just generating a series of
random games using a simple algorithm and a seed, on a PC, and then store a
list of games which work.  Then use the same algo and one of those seeds to
generate your levels.  That way you could have perhaps 1000 levels stored in
2K :-)

Plus, if you do this, then you don't need to flush the table, so the
generation speed should be about twice as fast.

Best of luck with it anyway :-)

----- Original Message -----
From: "Robert Dibley" <RDibley@...>
To: <gdalgorithms-list@...>
Sent: Wednesday, April 25, 2001 3:44 PM
Subject: RE: [Algorithms] Pairs game algorithm...


> Eeek !
>
> Erm, I think my old BBC micro could beat that by several orders of
magnitude
> - what have they given you, a processor where the clock speed is in KHz
> rather than MHz ?

Yes, there are Mhz.. even 50 of them :) This cpu is able to decode
fullscreen mpeg+mp3
at one time.. but the trick is that I'm writing OpenTV application, and
OpenTV is interpreted
language.. and that interpreter is damned slow :)

> If it takes that long you'd surely be better just generating a series of
> random games using a simple algorithm and a seed, on a PC, and then store
a
> list of games which work.  Then use the same algo and one of those seeds
to
> generate your levels.  That way you could have perhaps 1000 levels stored
in
> 2K :-)

Heh, too simple to be obvious, why I didn't got it myself? :)

> Plus, if you do this, then you don't need to flush the table, so the
> generation speed should be about twice as fast.

Yeah, this approach can be optimized quite impresively :)

> Best of luck with it anyway :-)

Thx :)

Best regards from
Kamil Burzynski
ADB Poland, LTD.
 - -
"God, root, what's the difference?"

I think you can combine solvable x*y board with a solvable x*b board so you
get a 2x*(y+b) board and it will still be solvable.  I haven't proved this
yet.  If this is the case, you can take Rob's idea further by choosing 4 of
the 1000 possible boards and placing them together.  This will increase the
combinations of games.

However, thinking about it, it may not be possible.  If the x*y board is
placed to the left of the x*b board and the x*b board requires a left edge
to be solvable, the x*y board's position makes it unsolvable.  Oo-er.

Just thinking out loud,

Matt Davies
Programmer
Confounding Factor Ltd.
mattd@...
 http://www.confounding-factor.com



----- Original Message -----
From: "Robert Dibley" <RDibley@...>
Newsgroups: programming.algorithms
To: <gdalgorithms-list@...>
Sent: Wednesday, April 25, 2001 2:44 PM
Subject: RE: [Algorithms] Pairs game algorithm...


> > for( i=0;i<64;i++ )
> > {
> >     for( j=0;j<64;j++ )
> >     {
> >         array[ (i<<6) + j ] = 0;
> >     }
> > }
> >
> > take 4 (four!) seconds...
>
> Eeek !
>
> Erm, I think my old BBC micro could beat that by several orders of
magnitude
> - what have they given you, a processor where the clock speed is in KHz
> rather than MHz ?
>
> If it takes that long you'd surely be better just generating a series of
> random games using a simple algorithm and a seed, on a PC, and then store
a
> list of games which work.  Then use the same algo and one of those seeds
to
> generate your levels.  That way you could have perhaps 1000 levels stored
in
> 2K :-)
>
> Plus, if you do this, then you don't need to flush the table, so the
> generation speed should be about twice as fast.
>
> Best of luck with it anyway :-)
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDAlgorithms-list@...
> http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list

----- Original Message -----
From: "Matt Davies" <mattd@...>
To: <gdalgorithms-list@...>
Sent: Wednesday, April 25, 2001 4:32 PM
Subject: Re: [Algorithms] Pairs game algorithm...


> I think you can combine solvable x*y board with a solvable x*b board so
you
> get a 2x*(y+b) board and it will still be solvable.  I haven't proved this
> yet.  If this is the case, you can take Rob's idea further by choosing 4
of
> the 1000 possible boards and placing them together.  This will increase
the
> combinations of games.
>
> However, thinking about it, it may not be possible.  If the x*y board is
> placed to the left of the x*b board and the x*b board requires a left edge
> to be solvable, the x*y board's position makes it unsolvable.  Oo-er.

This is possible to generate such board - if cards will be picked in some
not-so-random
order from both boards, but even with that whole board will have general
rule to solve it..
so once user learn that (s)he should pick on card from left and one from
right game will be much easier..

Best regards from
Kamil Burzynski
ADB Poland, LTD.
 - -
"God, root, what's the difference?"