Sign in to follow this  
Aph3x

C++ 'sparse matrix' implementation.

Recommended Posts

Hi all, I want to cache the results from various visibility ray traces between objects in my game world. WRT generality and speed, I reckoned it best to use a 2D matrix of bools for object_id vs object_id (i.e. set entry true if visible, else false.) The hard bit (there has to be one) is that there can be hundreds of objects in the world, so I thought a 'sparse matrix' would suit my purposes best here. So... my initial thoughts on implementing one are to have a stl map of maps. Any comments on suitability (space/time efficiency), other thoughts on sparse matrix implementations or thoughts on other solutions to the problem?

Share this post


Link to post
Share on other sites
I think when most people talk about sparse matrices, they have considerations involving algebraic operations that can be done with matrices like matrix multiplication. For your purpose, you just want to be able to quickly set entries and check if an entry in a boolean matrix is true or false.

Instead of a map of maps, you could also use a map of sets. If an element is present in the set then true, else false. Or a set or map of pairs, although this could result in more unnecessary comparisons. Continuing along that idea, for more efficiency, if there are only hundreds or thousands of objects...if there is some maximum value for object id, create a function that stores a pair of object ids into a unique integer for that pair, and store that integer in a set or hash_set. For example, if an object id is 16 bits, store the first id in the upper 16 bits of a 32 bit word and the second id in the lower 16 bits.

Share this post


Link to post
Share on other sites
For 'hundreds' (let's say 1024 for simplicity of calculation), just make a bool[1024*1024] and don't bother with sparseness. That's only 1MB, a drop in the ocean with modern RAM.

Share this post


Link to post
Share on other sites
There are a plethora of different approaches to caching visibility and ray-cast results, all with different performance profiles and memory/speed tradeoffs. What specifically are you trying to accomplish?

Share this post


Link to post
Share on other sites
@Bob: ah yes - should have mentioned - my Id's are unsigned int's... :o

@Jason: I'm interested in any other approaches. My ray casting binds 3 separate subsystems (heightmap/physics world primitives/per-poly collision system) so isn't the most efficient of operations. I was just hoping to prevent multiple raycasts betw the same objects per frame, and also take advantage of the fact that some rays could have acceptable latency. Another method I thought of was raycast scheduling, but that seems maybe too complex?

@Vorpy: yeah I thought the terminology may confuse ;) I was hoping for an O(1) set/read (tho maps dont give this). My IDs are current U32, but I could maybe limit them to 16 bits - have to think about it.

Share this post


Link to post
Share on other sites
On the top of my head: SparseLib++ - I read the corresponding paper a long time ago when I was working with Essbase (a multidimensional SGDB system; as you can imagine. my problem was about how such an engine was implemented).

I don't know much sparse matrix implementation out there, but google might help.

Share this post


Link to post
Share on other sites
Emmanuel: yeah saw that: it's an implementation for the 'other' (official?) meaning of 'sparse matrix' as Vorpy mentioned - one for linear algebra, rather than just value storage.
Ah well I think I'll go for a map of maps/sets as looking like the best solution.

Thanks all :)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this