我实际上有2个问题。1）我看到这些数千个体素的渲染，但使用八叉树我仍然只能在屏幕上获得大约 500 个体素。
import warnings,sys
sys.setrecursionlimit(50000)
class storedItem():
def __init__(self,coord,data):
self.coord = coord
self.data = data
self.node = None
def remove(self):
self.node.children.remove(self)
self.node = None
class Node():
def __init__(self,parent,lower,upper):
self.parent = parent
self.children = []
self.lowerbound = lower
self.upperbound = upper
self.setVolume()
def setVolume(self):
dx = self.upperbound[0] - self.lowerbound[0]
dy = self.upperbound[1] - self.lowerbound[1]
dz = self.upperbound[2] - self.lowerbound[2]
self.volume = dx*dy*dz
def inbound(self,coord):
if self.lowerbound[0] <= coord[0] and self.lowerbound[1] <= coord[1] and self.lowerbound[2] <= coord[2]:
if self.upperbound[0] >= coord[0] and self.upperbound[1] >= coord[1] and self.upperbound[2] >= coord[2]:
return True
return False
def returnValueOrChildnode(self,coord):
if not self.inbound(coord):
return self.parent
for child in self.children:
if child.__class__ == Node:
if child.inbound(coord):
return child
elif child.__class__ == storedItem:
if child.coord == coord:
return child
return None
def deleteOrReturnChildNode(self,coord):
if not self.inbound(coord):
return self.parent
for child in self.children:
if child.__class__ == Node:
if child.inbound(coord):
return child
elif child.__class__ == storedItem:
if child.coord == coord:
self.children.remove(child)
del(child)
return True
return None
def insertStoredItem(self,item):
if len(self.children) < 8:
self.children.append(item)
item.node = self
return True
if len(self.children) == 8:
for child in self.children:
if child.__class__ == Node:
if child.inbound(item.coord):
return child.insertStoredItem(item)
elif item.coord == child.coord:
warnings.warn('Already an item at this location, replacing it')
self.children.remove(child)
self.children.append(item)
self.breakupIntoChildren()
self.insertStoredItem(item)
def breakupIntoChildren(self):
#if self.volume == 8:
# raise Exception("Node full. Cannot add to this node")
nodes = []
delta = (self.upperbound[0] - self.lowerbound[0] +1)/2
x1,x2,x3 = (self.lowerbound[0],self.lowerbound[0]+delta -1,self.upperbound[0])
y1,y2,y3 = (self.lowerbound[1],self.lowerbound[1]+delta -1,self.upperbound[1])
z1,z2,z3 = (self.lowerbound[2],self.lowerbound[2]+delta -1,self.upperbound[2])
nodes.append(Node(self,(x1,y1,z1),(x2,y2,z2)))
nodes.append(Node(self,(x2 + 1,y1,z1),(x3,y2,z2)))
nodes.append(Node(self,(x1,y1,z2 +1),(x2,y2,z3)))
nodes.append(Node(self,(x2 + 1,y1,z2 + 1),(x3,y2,z3)))
nodes.append(Node(self,(x1,y2 + 1,z1),(x2,y3,z2)))
nodes.append(Node(self,(x2 + 1,y2 + 1,z1),(x3,y3,z2)))
nodes.append(Node(self,(x1,y2 + 1,z2 + 1),(x2,y3,z3)))
nodes.append(Node(self,(x2 + 1,y2 + 1,z2 + 1),(x3,y3,z3)))
while self.children:
child = self.children[0]
for node in nodes:
if node.inbound(child.coord):
node.insertStoredItem(child)
self.children.remove(child)
self.children = nodes
class Octree():
def __init__(self,size,maxsearch=1000):
if size % 2:
raise Exception("Size must be multiple of 2")
self.root = Node(None, (0,0,0),(size,size,size))
self.size = size
self.maxsearch=maxsearch
def search(self,coord):
searching = True
node = self.root
count = 0
while searching:
result = node.returnValueOrChildnode(coord)
if result is None:
searching = False
elif result.__class__ == storedItem:
result = result.data
searching = False
elif result.__class__ == Node:
node = result
count += 1
if count > self.maxsearch: #just incase something goes wrong
searching=False
result = None
raise Exception("Max Search depth limit reached")
return result
def insert(self,coord,data):
if not self.root.inbound(coord):
print coord, self.size, self.root.upperbound, self.root.lowerbound
raise Exception("Coordinate outside scope of octree")
item = storedItem(coord,data)
self.root.insertStoredItem(item)
def remove(self,coord):
searching = True
node = self.root
count = 0
while searching:
result = node.deleteOrReturnChildNode(coord)
if result is True:
searching = False
return True
elif result is None:
searching = False
elif result.__class__ == Node:
node = result
count += 1
if count > self.maxsearch: #just incase something goes wrong
searching=False
result = None
raise Exception("Max Search depth limit reached")
return result
def trace(frame, event, arg):
print "%s, %s:%d" % (event, frame.f_code.co_filename, frame.f_lineno)
return trace
这就是我一直在使用的八叉树代码。我从一个网站上得到的，这很整洁。它非常适合移除内部的立方体。虽然它只是一个空心盒子，这很奇怪。虽然它确实大大提高了FPS。对于渲染立方体，我使用这个小类。
class Cube(object):
def __init__(self, position, color,tree):
self.position = position
self.x = position[0]
self.y = position[1]
self.z = position[2]
self.color = color
self.tree = tree
num_faces = 6
vertices = [ (0.0, 0.0, 1.0),
(1.0, 0.0, 1.0),
(1.0, 1.0, 1.0),
(0.0, 1.0, 1.0),
(0.0, 0.0, 0.0),
(1.0, 0.0, 0.0),
(1.0, 1.0, 0.0),
(0.0, 1.0, 0.0) ]
normals = [ (0.0, 0.0, +1.0), # front
(0.0, 0.0, -1.0), # back
(+1.0, 0.0, 0.0), # right
(-1.0, 0.0, 0.0), # left
(0.0, +1.0, 0.0), # top
(0.0, -1.0, 0.0) ] # bottom
vertex_indices = [ (0, 1, 2, 3), # front
(4, 5, 6, 7), # back
(1, 5, 6, 2), # right
(0, 4, 7, 3), # left
(3, 2, 6, 7), # top
(0, 1, 5, 4) ] # bottom
def render(self):
glColor( self.color )
# Adjust all the vertices so that the cube is at self.position
vertices = [tuple(Vector3(v) + self.position) for v in self.vertices]
# Draw all 6 faces of the cube
glBegin(GL_QUADS)
for face_no in xrange(self.num_faces):
glNormal3dv( self.normals[face_no] )
v1, v2, v3, v4 = self.vertex_indices[face_no]
glVertex( vertices[v1] )
glVertex( vertices[v2] )
glVertex( vertices[v3] )
glVertex( vertices[v4] )
glEnd()
def getneighbors(self):
x = self.x
y = self.y
z = self.z
return ((x,y,z+1),(x+1,y,z),(x,y+1,z),(x-1,y,z),(x,y-1,z),(x,y,z-1))
def checkneighbors(self):
if not self.tree:
return True
positions = self.getneighbors()
for pos in positions:
result = self.tree.search(pos)
if not result:
return True
return False
使用此代码，我可以获得大约 30FPS。我认为屏幕上大约有 62,210 个方格。我通常得到大约 30-40 FPS（这还不错。）