This is an octree class, updated from the previous version to represent a true octree space. First create an octree with a world size. To add objects, use octree.InsertNode(rootNode, worldDivisionSize, parentNode, object)
to find the closest objects to a position, do result = myTree.findPosition(myTree.root, pos)

This code is public domain

# python Octree v.1
 
 # UPDATED:
 # Is now more like a true octree (ie: partitions space containing objects)
 
 # Important Points to remember:
 # The OctNode positions do not correspond to any object position
 # rather they are seperate containers which may contain objects
 # or other nodes.
 
 # An OctNode which which holds less objects than MAX_OBJECTS_PER_CUBE
 # is a LeafNode; it has no branches, but holds a list of objects contained within
 # its boundaries. The list of objects is held in the leafNode's 'data' property
 
 # If more objects are added to an OctNode, taking the object count over MAX_OBJECTS_PER_CUBE
 # Then the cube has to subdivide itself, and arrange its objects in the new child nodes.
 # The new octNode itself contains no objects, but its children should.
 
 # Psyco may well speed this script up considerably, but results seem to vary.
 
 # TODO: Add support for multi-threading for node insertion and/or searching
 
 #### Global Variables ####
 
 # This defines the maximum objects an LeafNode can hold, before it gets subdivided again.
 MAX_OBJECTS_PER_CUBE = 4
 
 # This dictionary is used by the findBranch function, to return the correct branch index
 DIRLOOKUP = {"3":0, "2":1, "-2":2, "-1":3, "1":4, "0":5, "-4":6, "-3":7}
 
 #### End Globals ####
 
 # Try importing psyco, in case it makes any speed difference
 # ( Speed increase seems to vary depending on system ).
 try:
     import psyco
     psyco.full()
 except:
     print "Could not import psyco, speed may suffer :)"
 
 class OctNode:
     # New Octnode Class, can be appended to as well i think
     def __init__(self, position, size, data):
         # OctNode Cubes have a position and size
         # position is related to, but not the same as the objects the node contains.
         self.position = position
         self.size = size
 
         # All OctNodes will be leaf nodes at first
         # Then subdivided later as more objects get added
         self.isLeafNode = True
 
         # store our object, typically this will be one, but maybe more
         self.data = data
        
         # might as well give it some emtpy branches while we are here.
         self.branches = [None, None, None, None, None, None, None, None]
 
         # The cube's bounding coordinates -- Not currently used
         self.ldb = (position[0] - (size / 2), position[1] - (size / 2), position[2] - (size / 2))
         self.ruf = (position[0] + (size / 2), position[1] + (size / 2), position[2] + (size / 2))
        
 
 class Octree:
     def __init__(self, worldSize):
         # Init the world bounding root cube
         # all world geometry is inside this
         # it will first be created as a leaf node (ie, without branches)
         # this is because it has no objects, which is less than MAX_OBJECTS_PER_CUBE
         # if we insert more objects into it than MAX_OBJECTS_PER_CUBE, then it will subdivide itself.
         self.root = self.addNode((0,0,0), worldSize, [])
         self.worldSize = worldSize
 
     def addNode(self, position, size, objects):
         # This creates the actual OctNode itself.
         return OctNode(position, size, objects)
 
     def insertNode(self, root, size, parent, objData):
         if root == None:
             # we're inserting a single object, so if we reach an empty node, insert it here
             # Our new node will be a leaf with one object, our object
             # More may be added later, or the node maybe subdivided if too many are added
             # Find the Real Geometric centre point of our new node:
             # Found from the position of the parent node supplied in the arguments
             pos = parent.position
             # offset is halfway across the size allocated for this node
             offset = size / 2
             # find out which direction we're heading in
             branch = self.findBranch(parent, objData.position)
             # new center = parent position + (branch direction * offset)
             newCenter = (0,0,0)
             if branch == 0:
                 # left down back
                 newCenter = (pos[0] - offset, pos[1] - offset, pos[2] - offset )
                
             elif branch == 1:
                 # left down forwards
                 newCenter = (pos[0] - offset, pos[1] - offset, pos[2] + offset )
                
             elif branch == 2:
                 # right down forwards
                 newCenter = (pos[0] + offset, pos[1] - offset, pos[2] + offset )
                
             elif branch == 3:
                 # right down back
                 newCenter = (pos[0] + offset, pos[1] - offset, pos[2] - offset )
 
             elif branch == 4:
                 # left up back
                 newCenter = (pos[0] - offset, pos[1] + offset, pos[2] - offset )
 
             elif branch == 5:
                 # left up forward
                 newCenter = (pos[0] - offset, pos[1] + offset, pos[2] + offset )
                
             elif branch == 6:
                 # right up forward
                 newCenter = (pos[0] + offset, pos[1] - offset, pos[2] - offset )
 
             elif branch == 7:
                 # right up back
                 newCenter = (pos[0] + offset, pos[1] + offset, pos[2] - offset )
             # Now we know the centre point of the new node
             # we already know the size as supplied by the parent node
             # So create a new node at this position in the tree
             # print "Adding Node of size: " + str(size / 2) + " at " + str(newCenter)
             return self.addNode(newCenter, size, [objData])
         
         #else: are we not at our position, but not at a leaf node either
         elif root.position != objData.position and root.isLeafNode == False:
            
             # we're in an octNode still, we need to traverse further
             branch = self.findBranch(root, objData.position)
             # Find the new scale we working with
             newSize = root.size / 2
             # Perform the same operation on the appropriate branch recursively
             root.branches[branch] = self.insertNode(root.branches[branch], newSize, root, objData)
         # else, is this node a leaf node with objects already in it?
         elif root.isLeafNode:
             # We've reached a leaf node. This has no branches yet, but does hold
             # some objects, at the moment, this has to be less objects than MAX_OBJECTS_PER_CUBE
             # otherwise this would not be a leafNode (elementary my dear watson).
             # if we add the node to this branch will we be over the limit?
             if len(root.data) < MAX_OBJECTS_PER_CUBE:
                 # No? then Add to the Node's list of objects and we're done
                 root.data.append(objData)
                 #return root
             elif len(root.data) == MAX_OBJECTS_PER_CUBE:
                 # Adding this object to this leaf takes us over the limit
                 # So we have to subdivide the leaf and redistribute the objects
                 # on the new children.
                 # Add the new object to pre-existing list
                 root.data.append(objData)
                 # copy the list
                 objList = root.data
                 # Clear this node's data
                 root.data = None
                 # Its not a leaf node anymore, Dave
                 root.isLeafNode = False
                 # It needs Branches now, Dave, 8 of them, one for each of my wives, Dave.
                 # root.branches = [None, None, None, None, None, None, None, None]
                 # Calculate the size of the new children
                 newSize = root.size / 2
                 # distribute the objects on the new tree
                 # print "Subdividing Node sized at: " + str(root.size) + " at " + str(root.position)
                 for ob in objList:
                     branch = self.findBranch(root, ob.position)
                     root.branches[branch] = self.insertNode(root.branches[branch], newSize, root, ob)
         return root
 
     def findPosition(self, root, position):
         # Basic collision lookup that finds the leaf node containing the specified position
         # Returns the child objects of the leaf, or None if the leaf is empty or none
         if root == None:
             return None
         elif root.isLeafNode:
             return root.data
         else:
             branch = self.findBranch(root, position)
             return self.findPosition(root.branches[branch], position)
            
 
     def findBranch(self, root, position):
         # helper function
         # returns an index corresponding to a branch
         # pointing in the direction we want to go
         vec1 = root.position
         vec2 = position
         result = 0
         # Equation created by adding nodes with known branch directions
         # into the tree, and comparing results.
         # See DIRLOOKUP above for the corresponding return values and branch indices
         for i in range(3):
             if vec1[i] <= vec2[i]:
                 result += (-4 / (i + 1) / 2)
             else:
                 result += (4 / (i + 1) / 2)
         result = DIRLOOKUP[str(result)]
         return result
 
 ## ---------------------------------------------------------------------------------------------------##
 
 
 if __name__ == "__main__":
 
     ### Object Insertion Test ###
     
     # So lets test the adding:
     import random
     import time
 
     #Dummy object class to test with
     class TestObject:
         def __init__(self, name, position):
             self.name = name
             self.position = position
 
     # Create a new octree, size of world
     myTree = Octree(15000.0000)
 
     # Number of objects we intend to add.
     NUM_TEST_OBJECTS = 200
 
     # Number of collisions we're going to test
     NUM_COLLISION_LOOKUPS = 200
 
     # Insert some random objects and time it
     Start = time.time()
     for x in range(NUM_TEST_OBJECTS):
         name = "Node__" + str(x)
         pos = (random.randrange(-4500.000, 4500.000), random.randrange(-4500.00, 4500.00), random.randrange(-4500.00, 4500.00))
         testOb = TestObject(name, pos)
         myTree.insertNode(myTree.root, 15000.000, myTree.root, testOb)
     End = time.time() - Start
 
     # print some results.
     print str(NUM_TEST_OBJECTS) + "-Node Tree Generated in " + str(End) + " Seconds"
     print "Tree Leaves contain a maximum of " + str(MAX_OBJECTS_PER_CUBE) + " objects each."
 
     ### Lookup Tests ###
 
     # Look up some random positions and time it
     Start = time.time()
     for x in range(NUM_COLLISION_LOOKUPS):
         pos = (random.randrange(-4500.000, 4500.000), random.randrange(-4500.00, 4500.00), random.randrange(-4500.00, 4500.00))
         result = myTree.findPosition(myTree.root, pos)
        
         ##################################################################################
         # This proves that results are being returned - but may result in a large printout
         # I'd just comment it out and trust me :)
         # print "Results for test at: " + str(pos)
         # if result != None:
         #    for i in result:
         #        print i.name, i.position,
         # print
         ##################################################################################
        
     End = time.time() - Start
 
     # print some results.
     print str(NUM_COLLISION_LOOKUPS) + " Collision Lookups performed in " + str(End) + " Seconds"
     print "Tree Leaves contain a maximum of " + str(MAX_OBJECTS_PER_CUBE) + " objects each."

<HR>
Creative Commons Copyright -- Some rights reserved.


THE WORK (AS DEFINED BELOW) IS PROVIDED UNDER THE TERMS OF THIS CREATIVE COMMONS PUBLIC LICENSE ("CCPL" OR "LICENSE"). THE WORK IS PROTECTED BY COPYRIGHT AND/OR OTHER APPLICABLE LAW. ANY USE OF THE WORK OTHER THAN AS AUTHORIZED UNDER THIS LICENSE OR COPYRIGHT LAW IS PROHIBITED.

BY EXERCISING ANY RIGHTS TO THE WORK PROVIDED HERE, YOU ACCEPT AND AGREE TO BE BOUND BY THE TERMS OF THIS LICENSE. THE LICENSOR GRANTS YOU THE RIGHTS CONTAINED HERE IN CONSIDERATION OF YOUR ACCEPTANCE OF SUCH TERMS AND CONDITIONS.

1. Definitions

  • "Collective Work" means a work, such as a periodical issue, anthology or encyclopedia, in which the Work in its entirety in unmodified form, along with a number of other contributions, constituting separate and independent works in themselves, are assembled into a collective whole. A work that constitutes a Collective Work will not be considered a Derivative Work (as defined below) for the purposes of this License.
  • "Derivative Work" means a work based upon the Work or upon the Work and other pre-existing works, such as a translation, musical arrangement, dramatization, fictionalization, motion picture version, sound recording, art reproduction, abridgment, condensation, or any other form in which the Work may be recast, transformed, or adapted, except that a work that constitutes a Collective Work will not be considered a Derivative Work for the purpose of this License. For the avoidance of doubt, where the Work is a musical composition or sound recording, the synchronization of the Work in timed-relation with a moving image ("synching") will be considered a Derivative Work for the purpose of this License.
  • "Licensor" means the individual or entity that offers the Work under the terms of this License.
  • "Original Author" means the individual or entity who created the Work.
  • "Work" means the copyrightable work of authorship offered under the terms of this License.
  • "You" means an individual or entity exercising rights under this License who has not previously violated the terms of this License with respect to the Work, or who has received express permission from the Licensor to exercise rights under this License despite a previous violation.
  • "License Elements" means the following high-level license attributes as selected by Licensor and indicated in the title of this License: Attribution, ShareAlike.

2. Fair Use Rights

Nothing in this license is intended to reduce, limit, or restrict any rights arising from fair use, first sale or other limitations on the exclusive rights of the copyright owner under copyright law or other applicable laws.

3. License Grant

Subject to the terms and conditions of this License, Licensor hereby grants You a worldwide, royalty-free, non-exclusive, perpetual (for the duration of the applicable copyright) license to exercise the rights in the Work as stated below:

  • to reproduce the Work, to incorporate the Work into one or more Collective Works, and to reproduce the Work as incorporated in the Collective Works;
  • to create and reproduce Derivative Works;
  • to distribute copies or phonorecords of, display publicly, perform publicly, and perform publicly by means of a digital audio transmission the Work including as incorporated in Collective Works;
  • to distribute copies or phonorecords of, display publicly, perform publicly, and perform publicly by means of a digital audio transmission Derivative Works.
  • For the avoidance of doubt, where the work is a musical composition:
    • Performance Royalties Under Blanket Licenses. Licensor waives the exclusive right to collect, whether individually or via a performance rights society (e.g. ASCAP, BMI, SESAC), royalties for the public performance or public digital performance (e.g. webcast) of the Work.
    • Mechanical Rights and Statutory Royalties. Licensor waives the exclusive right to collect, whether individually or via a music rights society or designated agent (e.g. Harry Fox Agency), royalties for any phonorecord You create from the Work ("cover version") and distribute, subject to the compulsory license created by 17 USC Section 115 of the US Copyright Act (or the equivalent in other jurisdictions).
    • Webcasting Rights and Statutory Royalties. For the avoidance of doubt, where the Work is a sound recording, Licensor waives the exclusive right to collect, whether individually or via a performance-rights society (e.g. SoundExchange), royalties for the public digital performance (e.g. webcast) of the Work, subject to the compulsory license created by 17 USC Section 114 of the US Copyright Act (or the equivalent in other jurisdictions).


The above rights may be exercised in all media and formats whether now known or hereafter devised. The above rights include the right to make such modifications as are technically necessary to exercise the rights in other media and formats. All rights not expressly granted by Licensor are hereby reserved.

4. Restrictions

The license granted in Section 3 above is expressly made subject to and limited by the following restrictions:

  • You may distribute, publicly display, publicly perform, or publicly digitally perform the Work only under the terms of this License, and You must include a copy of, or the Uniform Resource Identifier for, this License with every copy or phonorecord of the Work You distribute, publicly display, publicly perform, or publicly digitally perform. You may not offer or impose any terms on the Work that alter or restrict the terms of this License or the recipients' exercise of the rights granted hereunder. You may not sublicense the Work. You must keep intact all notices that refer to this License and to the disclaimer of warranties. You may not distribute, publicly display, publicly perform, or publicly digitally perform the Work with any technological measures that control access or use of the Work in a manner inconsistent with the terms of this License Agreement. The above applies to the Work as incorporated in a Collective Work, but this does not require the Collective Work apart from the Work itself to be made subject to the terms of this License. If You create a Collective Work, upon notice from any Licensor You must, to the extent practicable, remove from the Collective Work any credit as required by clause 4(c), as requested. If You create a Derivative Work, upon notice from any Licensor You must, to the extent practicable, remove from the Derivative Work any credit as required by clause 4(c), as requested.
  • You may distribute, publicly display, publicly perform, or publicly digitally perform a Derivative Work only under the terms of this License, a later version of this License with the same License Elements as this License, or a Creative Commons iCommons license that contains the same License Elements as this License (e.g. Attribution-ShareAlike 2.5 Japan). You must include a copy of, or the Uniform Resource Identifier for, this License or other license specified in the previous sentence with every copy or phonorecord of each Derivative Work You distribute, publicly display, publicly perform, or publicly digitally perform. You may not offer or impose any terms on the Derivative Works that alter or restrict the terms of this License or the recipients' exercise of the rights granted hereunder, and You must keep intact all notices that refer to this License and to the disclaimer of warranties. You may not distribute, publicly display, publicly perform, or publicly digitally perform the Derivative Work with any technological measures that control access or use of the Work in a manner inconsistent with the terms of this License Agreement. The above applies to the Derivative Work as incorporated in a Collective Work, but this does not require the Collective Work apart from the Derivative Work itself to be made subject to the terms of this License.
  • If you distribute, publicly display, publicly perform, or publicly digitally perform the Work or any Derivative Works or Collective Works, You must keep intact all copyright notices for the Work and provide, reasonable to the medium or means You are utilizing: (i) the name of the Original Author (or pseudonym, if applicable) if supplied, and/or (ii) if the Original Author and/or Licensor designate another party or parties (e.g. a sponsor institute, publishing entity, journal) for attribution in Licensor's copyright notice, terms of service or by other reasonable means, the name of such party or parties; the title of the Work if supplied; to the extent reasonably practicable, the Uniform Resource Identifier, if any, that Licensor specifies to be associated with the Work, unless such URI does not refer to the copyright notice or licensing information for the Work; and in the case of a Derivative Work, a credit identifying the use of the Work in the Derivative Work (e.g., "French translation of the Work by Original Author," or "Screenplay based on original Work by Original Author"). Such credit may be implemented in any reasonable manner; provided, however, that in the case of a Derivative Work or Collective Work, at a minimum such credit will appear where any other comparable authorship credit appears and in a manner at least as prominent as such other comparable authorship credit.

5. Representations, Warranties and Disclaimer

UNLESS OTHERWISE AGREED TO BY THE PARTIES IN WRITING, LICENSOR OFFERS THE WORK AS-IS AND MAKES NO REPRESENTATIONS OR WARRANTIES OF ANY KIND CONCERNING THE MATERIALS, EXPRESS, IMPLIED, STATUTORY OR OTHERWISE, INCLUDING, WITHOUT LIMITATION, WARRANTIES OF TITLE, MERCHANTIBILITY, FITNESS FOR A PARTICULAR PURPOSE, NONINFRINGEMENT, OR THE ABSENCE OF LATENT OR OTHER DEFECTS, ACCURACY, OR THE PRESENCE OF ABSENCE OF ERRORS, WHETHER OR NOT DISCOVERABLE. SOME JURISDICTIONS DO NOT ALLOW THE EXCLUSION OF IMPLIED WARRANTIES, SO SUCH EXCLUSION MAY NOT APPLY TO YOU.

6. Limitation on Liability.

EXCEPT TO THE EXTENT REQUIRED BY APPLICABLE LAW, IN NO EVENT WILL LICENSOR BE LIABLE TO YOU ON ANY LEGAL THEORY FOR ANY SPECIAL, INCIDENTAL, CONSEQUENTIAL, PUNITIVE OR EXEMPLARY DAMAGES ARISING OUT OF THIS LICENSE OR THE USE OF THE WORK, EVEN IF LICENSOR HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.

7. Termination

  • This License and the rights granted hereunder will terminate automatically upon any breach by You of the terms of this License. Individuals or entities who have received Derivative Works or Collective Works from You under this License, however, will not have their licenses terminated provided such individuals or entities remain in full compliance with those licenses. Sections 1, 2, 5, 6, 7, and 8 will survive any termination of this License.
  • Subject to the above terms and conditions, the license granted here is perpetual (for the duration of the applicable copyright in the Work). Notwithstanding the above, Licensor reserves the right to release the Work under different license terms or to stop distributing the Work at any time; provided, however that any such election will not serve to withdraw this License (or any other license that has been, or is required to be, granted under the terms of this License), and this License will continue in full force and effect unless terminated as stated above.

8. Miscellaneous

  • Each time You distribute or publicly digitally perform the Work or a Collective Work, the Licensor offers to the recipient a license to the Work on the same terms and conditions as the license granted to You under this License.
  • Each time You distribute or publicly digitally perform a Derivative Work, Licensor offers to the recipient a license to the original Work on the same terms and conditions as the license granted to You under this License.
  • If any provision of this License is invalid or unenforceable under applicable law, it shall not affect the validity or enforceability of the remainder of the terms of this License, and without further action by the parties to this agreement, such provision shall be reformed to the minimum extent necessary to make such provision valid and enforceable.
  • No term or provision of this License shall be deemed waived and no breach consented to unless such waiver or consent shall be in writing and signed by the party to be charged with such waiver or consent.
  • This License constitutes the entire agreement between the parties with respect to the Work licensed here. There are no understandings, agreements or representations with respect to the Work not specified here. Licensor shall not be bound by any additional provisions that may appear in any communication from You. This License may not be modified without the mutual written agreement of the Licensor and You.