How do people render so many voxels at once?

Question

I have actually 2 questions. 1) I see these renders of thousands of voxels, yet using an octree I can still get only about 500 voxels on the screen.

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

Thats the octree code I've been using. I got it off a website, which was pretty neat. It works great for removing the cubes on the inside. Though it makes it just a hollow box, which is pretty weird. Though it does drastically improve the FPS. For rendering cubes I use this little class.

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

I can get about 30FPS with this code. I think there is about 62,210 squares on the screen. I get usually around 30-40 FPS (which isn't bad.)

Answer 1

The first thing I would say is: Don't use objects to represent cubes. It sounds like the right thing to do, but I don't think iterating through millions of objects and executing methods on each of those is going to perform too greatly on python.

I would recommend using 3d Numpy arrays to store this (voxel[x][y][z] = color). That's would be an improvement in memory consumption. You can more information here

After you do that and rewrite your algorithms to use an array instead of many objects, the next thing you need to realize is that you don't need to render every voxel you have. You only need to render those that are visible. That means pushing much less polygons to the GPU.

Think about it... if you have a cube of 10x10x10 voxels, right now you are writing 6000 quads. If you grow the cube to be of 100x100x100 voxels you will be writing 6000000 quads. This gets quickly out of control.

You only need to push those voxels that are going to be visible to the user. In the 10x10x10 voxels case you only need to push the "outer" ones. That's 486 voxels (9x9x6), which means 2916 quads if you write every face of each of the voxels. And for the 100x100x100 case you only need 58806 voxels (99x99x6), that's 352836 quads (that's 6% the number of quads you wrote on the first case). The rest of the voxels are hidden behind the outer ones.

Optimizations don't end here, really. But I think these small optimizations will allow you to render many more voxels than you are currently rendering. There are many more advanced optimizations, you could read here if you want to learn more about it.