Bounding Volume Hierarchies

I've been working with the Polyworld code and I've added additional input and output neurons to the critter neural networks for communication input and output. I've also written a simple function so that each critter gets communication from the closest critter.

The problem is that this function is quite costly. Each critter needs to check with all the other critters to determine the closest critter. I looked around for a bit and found that a possible approach is to implement a bounding volume hierarchy (BVH).

I can either implement my own BVH or find an existing one.

The following books on Google Books describe how to implement a BVH.

• Game Physics Engine Development by Ian Millington
  
  Simulating physics helps cutting-edge games distinguish themselves by making virtual objects behave as we expect them to in the real world.Physics enginesare the software programs that run these simulations. Building an engine is difficult, however. There are a large number of new developers (and hobbyists) coming into this market who need help through this complex process. Current introductory books are inadequate; they don't bring enough real-world programming experience to the task. There is a need for an introductory book on game physics with solid coding guidance but which limits the math content.
  
  Ian Millington brings his extensive professional programming experience to this problem. He has developed games since 1987, has studied AI and mathematics at the PhD level, and founded Mindlathe Ltd., a company that designed and built commercial physics engines.
  
  Physics Engine Development carefully describes each step in the creation of a robust, usable physics engine. It introduces the mathematical concepts in a clear and simple manner, keeping to high school level topics and building a physics code library as it goes. Each new concept is explained in diagrams and code to make sure that even the most novice of game programmers understands. The companion CD-ROM includes the source code for a complete physics engine of commercial quality.
  
  This book will serve as a introduction to more mathematically advanced books on game physics, such as Dave Eberly's Game Physics. * Uses only high school algebra * Shows how to build a complete system based on professional principles * CD-ROM with C++ source code for a full commercial-quality physics engine
  
  
• Real-time Rendering by Tomas Möller, Tomas Akenine-Moller, Eric Haines
  
  Real-Time Rendering, 2nd Edition comes three years after the release of the first. In that time, computer graphics hardware has evolved at a rapid rate. It is more than ten times faster and the functionality has increased significantly in a wide range of areas. Reflecting these changes, this second edition is almost 900 pages - 75% larger than the first edition. All chapters have been updated, and new chapters added on spline and subdivision surfaces, advanced shading theory and techniques, and non-photorealistic and image-based rendering. As with the first edition, this new book is a blend of solid theory and practical advice, useful for students, professionals and hobbyists alike.

I really like Millington's book because I can follow the maths.

The other choices I have are to use existing libraries. If I write my own BVH, the complexity is low but the possibility of error is high. If I use an existing library, then it's the other way around. There's a few libraries available such as

• Ogre
  
  It's not a complete game engine (no sound, networking, or physics). It's strictly an open-source graphics engine. It provides and easy-to-use high level API. It's written in C++ but has bindings for other languages, and it deploys on Windows, Linux, or MacOS.
  
  ...
  
  Scene Management – determining what should be drawn and when. The default scene manager uses a bounding volume hierarchy. Octree and terrain scene managers are also provided. You can also create custom scene managers is the default ones won't suit your needs. For most projects, the default ones will work.
  
  
• Open Scene Graph
  
  OpenSceneGraph is an open source high performance 3D graphics toolkit, used by application developers in fields such as visual simulation, computer games, virtual reality, scientific visualization and modelling.
  
  The toolkit is written in standard C++ using OpenGL, and runs on a variety of operating systems including Microsoft Windows, Mac OS X, Linux, IRIX, Solaris and FreeBSD.
  
  
• Open SG
  
  OpenSG is a scene graph system to create realtime graphics programs, e.g. for virtual reality applications. It is developed following Open Source principles, LGPL licensed, and can be used freely. It runs on Microsoft Windows, Linux, Solaris and Mac OS X and is based on OpenGL.
  
  Its main features are advanced multithreading and clustering support (with sort-first and sort-last rendering, amongst other techniques), although it is perfectly usable in a single-threaded single-system application as well.

I think it may be one of those cases of choosing something and taking the plunge.