I am looking for documentation that explains the different kinds of (well the major ones anyway) 2D space partitioning algorithms & data structures.
Any pointers besides 'Google it and sift through hundreds of papers'. A book perhaps?
\$\begingroup\$
\$\endgroup\$
2
-
\$\begingroup\$ Do you have any specific algorithms and data structures you are interested in? What kind of game are you making? \$\endgroup\$– NoobsArePeople2Commented Dec 28, 2011 at 23:18
-
\$\begingroup\$ I simply wanted to digest the main ones and understand the strengths and trade-offs. I am not making a game, but know that this is the right place to ask this question :) \$\endgroup\$– r1xCommented Dec 28, 2011 at 23:38
Add a comment
|
1 Answer
\$\begingroup\$
\$\endgroup\$
3
I've got this sort of info spread over many books on my bibliography, but I'm currently away from them. But from what I could gather up from memory and browsing through the table of contents online, I recall the following books:
3D Math Primer for Graphics and Game Development 1st Edition or Mathematics for 3D Game Programming & Computer Graphics
or 
Chapter 16 (Visibility Determination) of 3D Math Primer for Graphics and Game Development 1st Edition (strangely the authors seem to have removed this section from the second edition of the book) covers the most common techniques (i.e. grid system, quadtree and octree, bsp trees, portal occlusion). The book is really good, although perhaps not the best of its kind.
I've seen Mathematics for 3D Game Programming & Computer Graphics being mentioned very often, but unfortunately haven't gotten my hands on it yet. From the table of contents, it seems to cover space partitioning algorithms too. Not sure how they compare against each other.
Naturally, the focus of these books is on the math. And although the title says 3D, they are also quite relevant for 2D programming.
Real-time Rendering 3rd Edition
Chapter 14 (Acceleration Algorithms) of Real-time Rendering also covers most of these topics, and this is actually my favorite general graphics programming book ever. Very comprehensive but I don't recall how much it covered this particular subject.
The focus of this book is on the graphics theory, but it covers such a large amount of topics that I could hardly find a better recommendation for anyone interested in the field.
Game Programming Gems
The previous books were mostly theoretical though. For more specific and practical advice, I've read several articles on the subject scattered throughout the Game Programming Gems series. Some that come to mind:
- Octree Construction - Game Programming Gems 1
- Loose Octrees - Game Programming Gems 1
- Sphere Trees for Fast Visibility Culling, Ray Tracing, and Range Searching - Game Programming Gems 2
- A High-Performance Tile-based Line-of-Sight and Search System - Game Programming Gems 2
- Sphere Trees for Speedy BSPs - Game Programming Gems 5
- Spatial Partitioning Using an Adaptive Binary Tree - Game Programming Gems 6
- BSP Techniques - Game Programming Gems 6
answered Dec 28, 2011 at 23:17
-
\$\begingroup\$ Theory is actually what I'm after. Hopefully explanations that involve linear algebra & discrete geometry. \$\endgroup\$– r1xCommented Dec 28, 2011 at 23:51
-
\$\begingroup\$ Then I believe one of the math books might be the better choice, although you might be disappointed at how little coverage there really is (at least I remember it being rather simple). \$\endgroup\$ Commented Dec 29, 2011 at 4:22
-
\$\begingroup\$ Therefore you might benefit from combining that with some practical (and more advanced) examples too. \$\endgroup\$ Commented Dec 29, 2011 at 4:29