Thread: RE: [Algorithms] good way of storing a lot of collision data
Brought to you by:
vexxed72
From: Tom F. <to...@mu...> - 2002-12-23 15:35:35
|
That sounds terrible. By request do you mean "find me all the objects in this bounding volume"? Roughly how many objects are going to be returned by each request? A standard octree request should be easily fast enough to do a few thousand queries returning a few hundred objects each _unless_: (a) your octree doesn't store any "I'm completely empty" node flags. Without these, you're going all the way down to each leaf every time. No point in having an octree if you're doing this! (b) you are actually checking data inside the objects during a query. Don't do this - checking even a single bit inside the object means the whole cache line gets pulled in, which is almost as expensive as reading the entire object. (c) something else. If your world is massive, then your octree may have a very tall structure (i.e. lots of "mipmap" levels), so each request may be going through quite a lot of nodes at the top. You can chop the top off the structure and remove some of these tests by not having a full octree, but having a regular grid at some level, and then each grid square uses an octree off that. So you can very quickly get to the grid square using simple bit shifting arithmetic, and then go down through the octree. For the example of a planet-sized object, you might have a pre-allocated grid where each cell is 100km x 100km, rather than store a full octree all the way up to one octree for the whole planet. However, this is a much smaller optimisation than the sorts of orders-of-magnitude stuff you need. Tom Forsyth - Muckyfoot bloke and Microsoft MVP. This email is the product of your deranged imagination, and does not in any way imply existence of the author. > -----Original Message----- > From: Richard Fabian [mailto:alg...@th...] > Sent: 23 December 2002 15:06 > To: gda...@li... > Subject: [Algorithms] good way of storing a lot of collision data > > > I've used tight octrees and now an Axis aligned binary space > partition, > I basically want something that runs fast, and returns a list > of things > to try and collide against... > > both the algorithms I tried are too slow... I want about a thousand > requests every 60th of a frame, and I'm getting about 100 with the > current methods on my 850 PIII, and this is meant to be a PS2 > engine! :( > > anyway, can people chuck me some buzzwords that I can investigate... > > I've already stuck loose octrees on the list... what do you people use > to store your collision datas? > > fabs(); > Animation, dynamics and collision programmer Broadsword > Interactive ltd. > > (aka Richard Fabian) > > > > ------------------------------------------------------- > This sf.net email is sponsored by:ThinkGeek > Welcome to geek heaven. > http://thinkgeek.com/sf > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > |
From: Tom F. <to...@mu...> - 2002-12-23 16:27:57
|
> From: Richard Fabian [mailto:alg...@th...] > [snip] > > (a) your octree doesn't store any "I'm completely empty" node > > flags. Without > > these, you're going all the way down to each leaf every time. > > No point in > > having an octree if you're doing this! > > pointers to children... if( NULL )... Oh, right - dynamically allocated octree. Gotcha. Yeah, that should be fine. > > (b) you are actually checking data inside the objects during > > a query. Don't > > do this - checking even a single bit inside the object means > > the whole cache > > line gets pulled in, which is almost as expensive as reading > > the entire > > object. > > the only data in an octree node is the list of IDs of objects > and their > associated bounding boxes... OK. > > (c) something else. > > yeah, I think so... > > > If your world is massive, then your octree may have a very > > tall structure > > seems to have 16 levels at the highest :( Not extreme, but it might help to chop the top off. > > (i.e. lots of "mipmap" levels), so each request may be going > > through quite a > > lot of nodes at the top. You can chop the top off the > > structure and remove > > some of these tests by not having a full octree, but having a > > regular grid > > at some level, and then each grid square uses an octree off > > that. So you can > > very quickly get to the grid square using simple bit shifting > > arithmetic, > > and then go down through the octree. > > ... hmmm, lumping it up... might work... > > One thing I did notice, and have attacked: there are leads of object > that sit on high nodes because they straddle middle planes. this > caused MASSIVE slowdown early in development, and I got around it by > sending the object into all the child nodes that it touched... > > I got a great speed up, but has caused the octree to be a little large > :( In that case you definately want "loose octrees". They're pretty simple to implement - you just modify where you insert items in your existing octree, and how you query volumes. And then you don't need to replicate entries (which burns memory) or put things too high in the tree (which returns too many objects to the query). Tom Forsyth - Muckyfoot bloke and Microsoft MVP. This email is the product of your deranged imagination, and does not in any way imply existence of the author. |
From: Richard F. <alg...@th...> - 2002-12-24 13:05:08
|
> -----Original Message----- > From: gda...@li... > [mailto:gda...@li...] On > Behalf Of Tom Forsyth > Sent: 23 December 2002 16:27 > To: gda...@li... > Subject: RE: [Algorithms] good way of storing a lot of collision data > > > > If your world is massive, then your octree may have a very > > > tall structure > > > > seems to have 16 levels at the highest :( > > Not extreme, but it might help to chop the top off. do you think it might be to do with the fact that I am making a tree from 68000 AABBs? (hmm 68000, is there some mysterious lynchesque-motorola style thingy here?) > > One thing I did notice, and have attacked: there are leads of object > > that sit on high nodes because they straddle middle planes. this > > caused MASSIVE slowdown early in development, and I got around it by > > sending the object into all the child nodes that it touched... > > > > I got a great speed up, but has caused the octree to be a > little large > > :( > > In that case you definately want "loose octrees". They're > pretty simple to > implement - you just modify where you insert items in your > existing octree, > and how you query volumes. And then you don't need to > replicate entries > (which burns memory) or put things too high in the tree > (which returns too > many objects to the query). implemented loose octrees, and they seem to be a bit slower than my tight octrees... may try and add my axial exlusion code to this and see if its any faster :S is it okay if I post my looseoctree.h for you to peruse? |
From: Scott Le G. <va...@sh...> - 2002-12-23 22:21:10
|
This is as good a time as any to chime in: has anyone compared the efficacy of using octrees versus sweep and prune / recursive dimensional clustering sorts of approaches. I'm at the decision stage for a collision handler of my own, and I currently rely on the latter. There is a great deal of temporal coherence (space shooter), but a huge playfield (objects 100 feet in diameter interacting with capitol ships several miles long) in an unbounded arena (well bounded by floating point precision and time constraints in that you lose if you fly off too far and let things go to pieces). Scott |
From: Pierre T. <p.t...@wa...> - 2002-12-24 05:16:19
|
> This is as good a time as any to chime in: has anyone compared the efficacy > of using octrees versus sweep and prune / recursive dimensional clustering > sorts of approaches. I did with loose octrees. (I assume we can safely discard normal octrees, since they're not very useful for dynamic objects anyway. I also assume our objects are dynamic, else no need for a sweep-and-prune). Then as far as we're speaking about that query : "find all pairs of overlapping objects" ...loose octrees are slower. (I'm not the only one that came to that conclusion, in case you wonder). On the other hand (and that's why they're still useful), you can re-use loose octrees for all other queries (from VFC to ray-casts to whatever), while the SAP algorithm only answers the query above (AFAIK). So in the end and as often, it depends on your actual needs :) As far as I'm concerned, I use both. Some rough SAP notes just in case : http://www.codercorner.com/SweepAndPrune.htm RDC is not worth it IMHO. Unless I'm missing something it has nothing to offer compared to the original SAP algorithm (I really think the author just didn't know about SAP, it's never mentioned in the article while it's exactly the same, except it prunes all lists at the same time instead of recursively). Pierre ...ok and now let's print those wavelet papers to have something to read in the train :) |
From: Richard F. <alg...@th...> - 2002-12-23 16:02:10
|
> That sounds terrible. I know... :( > By request do you mean "find me all the objects in this > bounding volume"? yeah, bounding box currently... (shape + vel) > Roughly how many objects are going to be returned by each request? A 2 - 10 > standard octree request should be easily fast enough to do a > few thousand > queries returning a few hundred objects each _unless_: yeah, s'what I thought... (I'm probaly shit :) ) > (a) your octree doesn't store any "I'm completely empty" node > flags. Without > these, you're going all the way down to each leaf every time. > No point in > having an octree if you're doing this! pointers to children... if( NULL )... > (b) you are actually checking data inside the objects during > a query. Don't > do this - checking even a single bit inside the object means > the whole cache > line gets pulled in, which is almost as expensive as reading > the entire > object. the only data in an octree node is the list of IDs of objects and their associated bounding boxes... > (c) something else. yeah, I think so... > If your world is massive, then your octree may have a very > tall structure seems to have 16 levels at the highest :( > (i.e. lots of "mipmap" levels), so each request may be going > through quite a > lot of nodes at the top. You can chop the top off the > structure and remove > some of these tests by not having a full octree, but having a > regular grid > at some level, and then each grid square uses an octree off > that. So you can > very quickly get to the grid square using simple bit shifting > arithmetic, > and then go down through the octree. ... hmmm, lumping it up... might work... One thing I did notice, and have attacked: there are leads of object that sit on high nodes because they straddle middle planes. this caused MASSIVE slowdown early in development, and I got around it by sending the object into all the child nodes that it touched... I got a great speed up, but has caused the octree to be a little large :( |