Monster Black Hole – Pythius

Pythius makes Drum & Bass and is a friend of mine. So when he told me he was doing a new track and I could make the visuals I didn’t think twice about it!

The short version

The video was made using custom software and lots of programming! Generally 3D videos are made with programs that calculate the result, which can take minutes or even hours. This means that every time you change something you have to wait to see whether the result is more to your liking. With the custom software that we made, everything is instantly updated and we are looking at the end result at all time. This makes tweaking anything, from colors and shapes to animation, a breeze. It allows for much iteration as we want and turns the video creation process into an interactive playground.

The technique we use generates all the visuals with code, there are very few images and no 3D model files. Everything you see on the screen is visualized through maths. As a side effect of not using big 3D model files, the code that can generate the entire video is incredibly small. About 300 kilobytes, 10 thousand times smaller than the video file it produced!

The details

Technologies used are Python (software) Qt (interface) OpenGL (visual effects). The rendering uses Enhanced Sphere Tracing & physically based shading.

I talked about thetool development here and the rendering pipeline here in the past.
More information about advanced sphere tracing here. Which is an enhancement of this!

Screenshot dump

This is without the awesome after effects work from Lex Hoogendam, but a straight rip from the tool. Apologies that it’s not the same, but I hope it’ll make for some cool stills!

Monster-Black-Hole-4k_00704.jpg
Monster-Black-Hole-4k_01303.jpg
Monster-Black-Hole-4k_01633.jpg
Monster-Black-Hole-4k_02140.jpg
Monster-Black-Hole-4k_02200.jpg
Monster-Black-Hole-4k_02592.jpg
Monster-Black-Hole-4k_02776.jpg
Monster-Black-Hole-4k_02879.jpg
Monster-Black-Hole-4k_03078.jpg
Monster-Black-Hole-4k_03474.jpg
Monster-Black-Hole-4k_03911.jpg
Monster-Black-Hole-4k_04865.jpg
Monster-Black-Hole-4k_5225.jpg
Monster-Black-Hole-4k_05680.jpg
Monster-Black-Hole-4k_05933.jpg
Monster-Black-Hole-4k_06365.jpg
Monster-Black-Hole-4k_06388.jpg
Monster-Black-Hole-4k_07089.jpg
Monster-Black-Hole-4k_07285.jpg
Monster-Black-Hole-4k_07854.jpg

A* path finding using a game’s wiki

Navigate the result here!

I recently replayed Metroid Prime 2 (for GameCube) and got lost. A lot. This game features many interconnecting rooms, most of which exist in a dark and a light dimension with one-way or two-way portals. It took ages to figure out what item to collect when and where, so I did what anyone would do and coded a system to find the optimal path to finish the game!

The game works with rooms, basically every room has a bunch of doors, usually 2 complex rooms are connected by tunnels, this allows the game to close doors and stream the world very late (as we don’t have any view of unloaded areas to worry about). To start out I scraped this site (while saving every page loaded to disk as to not get banned for doing too many requests). Every link in that list goes to a page that describes what other places we can go from this place, as well as what upgrades can be found in this room. The connecting rooms are also formulated like “Room X (through red door)”, from which I can derive that a red door requires the missile launcher upgrade. So I can scrape limitations as well!

This allowed me to build a massive structure. Instead of making serialization work I just did code generation into a set of global dictionaries. That looks a bit like this:

# structure.py
class Or(object):
    def __init__(self, *args):
        self.options = args

    def __str__(self):
        return 'Or(\'%s\')' % '\', \''.join(self.options)

    def __eq__(self, other):
        for opt in self.options:
            if opt == other:
                return True
        return False


class Item(object):
    def __init__(self, name):
        self.name = name
        self.requirements = []


class Transition(object):
    def __init__(self, sourceRoom, targetRoom):
        self.sourceRoom, self.targetRoom, self.requirements = sourceRoom, targetRoom, []

    def deregister(self):
        self.sourceRoom.transitions.remove(self)


areas = ['Temple Grounds', 'Sky Temple Grounds', 'Great Temple', 'Sky Temple', 'Agon Wastes', 'Dark Agon Wastes', 'Torvus Bog', 'Dark Torvus Bog', 'Sanctuary Fortress', 'Ing Hive']


class Room(object):
    def __init__(self, name):
        self.name = name
        self.transitions = []
        self.items = []
        self.area = None

    def displayData(self):
        print '%s (%s)' % (self.name, self.area)
        print '\tConnects to:'
        for transition in self.transitions:
            print transition.targetRoom.name, transition.requirements
        print '\tItems:'
        for item in self.items:
            print item.name
from structure import *

# list items in the game
items = {
    'beam ammo expansion1': Item('Beam Ammo Expansion'),
    'beam ammo expansion2': Item('Beam Ammo Expansion'),
    'beam ammo expansion3': Item('Beam Ammo Expansion'),
    'beam ammo expansion4': Item('Beam Ammo Expansion'),
    'boost ball': Item('Boost Ball'),
# ... etcetera
}
# list rooms in the game
rooms = {
    ('transit station', 'Agon Wastes'): Room('Transit Station'),
    ('mining plaza', 'Agon Wastes'): Room('Mining Plaza'),
# ... etcetera
}

# denote room worlds and contents
rooms[('transit station', 'Sanctuary Fortress')].area = 'Sanctuary Fortress'
rooms[('transit station', 'Sanctuary Fortress')].items.append(items['power bomb expansion6'])
# ... etcetera

# connect rooms in the game
transitions = {
    (('transit station', 'Agon Wastes'), ('mining plaza', 'Agon Wastes')): Transition(rooms[('transit station', 'Agon Wastes')], rooms[('mining plaza', 'Agon Wastes')]),
# ... etcetera
}
# register the connections
rooms[('transit station', 'Agon Wastes')].transitions.append(transitions[(('transit station', 'Agon Wastes'), ('mining plaza', 'Agon Wastes'))])
# ... etcetera
# add inventory requirements to the connections
transitions[(('sacred path', 'Temple Grounds'), ('profane path', 'Sky Temple Grounds'))].requirements.append('Dark Beam')
# ... etcetera

After executing that code I would have every room in the game in memory, where every room has links to the objects they’re connected to, including constraints such as upgrade requirements to open the door between those rooms!

Now with all this information, I can start writing a navigation unit in the game world. My unit has a certain inventory of upgrades and a current location and it can figure out where it can and can’t go at this point. So I wrote an A* path finder but for every connection I only consider evaluating it if the requirements of going through that door are met by the inventory.

Putting the unit at the start of the game and telling it to grab the first upgrade works instantly like this! A bit of a harder extension was adding the possibility to realize the requirements for a transition and then finding the path to that requirement first. This also slowed the algorithm down by a lot, but it does allow me to say “start here, go to final boss” and the navigator will figure out what to do! I realized there’s 100! (factorial) options to gather the upgrades so stuck with the manual order input for now…

I wanted to add the desire to obtain all items in the game, to complete it with 100% of the upgrades, but didn’t get around to it.

Next up was visualization! I soon realized that to highlight rooms on the map the most time efficient way was to just bite the bullet for an evening and trace them…
I wrote this little tool where I can navigate the different maps and draw the polygons for each room. That then gets saved as JSON and got used by the visualizer.

And here’s the code!

import json
import os
from qt import *
from scrapeoutput import *


class PolygonView(QWidget):
    def __init__(self, owner):
        super(PolygonView, self).__init__()
        self._owner = owner
        self.roomPolygons = {}
        self.setFocusPolicy(Qt.StrongFocus)
        self._panStart = None
        self.background = None
        self._panX = 0
        self._panY = 0

    def mousePressEvent(self, event):
        if event.button() == Qt.MiddleButton:
            self._panStart = self._panX, self._panY, event.x(), event.y()
            return

    def mouseReleaseEvent(self, event):
        if self._panStart is not None:
            self._panStart = None
            return

    def mouseMoveEvent(self, event):
        if self._panStart is not None:
            self._panX = self._panStart[0] + (event.x() - self._panStart[2])
            self._panY = self._panStart[1] + (event.y() - self._panStart[3])
            self.repaint()
            return

    def paintBackground(self, painter):
        if self.background:
            painter.setOpacity(0.2)
            painter.drawImage(0, 0, self.background)
            painter.setOpacity(1.0)

    def findActivePolygon(self):
        key = self._owner.activeKey()
        if key is None:
            return
        points = self.roomPolygons.get(key, [])
        if not points:
            return None
        return points

    def drawPolygon(self, painter, points):
        solidWhite = QPen(Qt.white, 1, Qt.SolidLine)
        dottedWhite = QPen(Qt.white, 1, Qt.DotLine)
        for i in xrange(len(points)):
            painter.setPen(solidWhite)
            painter.setBrush(Qt.NoBrush)
            x, y = points[i].x(), points[i].y()
            if i == 0:
                painter.setBrush(Qt.white)
            painter.drawRect(QRectF(x - 2.5, y - 2.5, 5.0, 5.0))
            if i == len(points) - 1:
                painter.setPen(dottedWhite)
            painter.drawLine(points[i], points[(i + 1) % len(points)])

    def paint(self, painter):
        self.paintBackground(painter)
        painter.setRenderHint(QPainter.Antialiasing)
        points = self.findActivePolygon()
        if not points:
            return
        self.drawPolygon(painter, points)

    def paintEvent(self, event):
        painter = QPainter(self)
        painter.fillRect(QRect(0, 0, self.width(), self.height()), Qt.black)

        painter.translate(self._panX, self._panY)
        self.paint(painter)


def quadZoom(zoom, steps):
    # apply steps as multiplicative zoom to get a quadratic curve
    if steps < 0:
        return zoom * pow(1.000794567, steps)
    else:
        return zoom * pow(0.99912239, -steps)


class PolygonZoom(PolygonView):
    def __init__(self, owner):
        super(PolygonZoom, self).__init__(owner)
        self.zoom = 1.0
        self.state = 0

    def wheelEvent(self, event):
        oldUnits = (event.x() - self._panX) / self.zoom, (event.y() - self._panY) / self.zoom
        self.zoom = quadZoom(self.zoom, event.delta())
        newUnits = (event.x() - self._panX) / self.zoom, (event.y() - self._panY) / self.zoom
        deltaUnits = newUnits[0] - oldUnits[0], newUnits[1] - oldUnits[1]
        self._panX += deltaUnits[0] * self.zoom
        self._panY += deltaUnits[1] * self.zoom
        self.repaint()

    def drawPolygon(self, painter, points):
        if self.state == 0:
            painter.setPen(Qt.white)
        else:
            painter.setPen(QPen(QBrush(QColor(255, 180, 40)), 3.0))
        for i in xrange(len(points)):
            painter.drawLine(points[i], points[(i + 1) % len(points)])

    def paintEvent(self, event):
        painter = QPainter(self)
        painter.fillRect(QRect(0, 0, self.width(), self.height()), Qt.black)

        painter.translate(self._panX, self._panY)
        painter.scale(self.zoom, self.zoom)
        self.paint(painter)


class PolygonEdit(PolygonView):
    def __init__(self, owner):
        super(PolygonEdit, self).__init__(owner)
        self.__dragStart = None

    def __indexUnderMouse(self, polygon, pos):
        tolerance = 8
        for index, point in enumerate(polygon):
            delta = point - pos
            if abs(delta.x()) + abs(delta.y()) < tolerance:
                return index
        return None

    def mousePressEvent(self, event):
        if event.button() == Qt.MiddleButton:
            self._panStart = self._panX, self._panY, event.x(), event.y()
            return

        if event.button() != Qt.LeftButton:
            return

        key = self._owner.activeKey()
        if key is None:
            return

        polygon = self.roomPolygons.get(key, None)
        if polygon is None:
            return None

        localPos = event.pos() - QPoint(self._panX, self._panY)
        index = self.__indexUnderMouse(polygon, localPos)
        if index is None:
            return

        self.__dragStart = localPos, polygon, index, QPoint(polygon[index])

    def mouseReleaseEvent(self, event):
        if self._panStart is not None:
            self._panStart = None
            return

        if self.__dragStart is None:
            if event.modifiers() == Qt.ControlModifier:
                key = self._owner.activeKey()
                if key is None:
                    return
                polygon = self.roomPolygons.get(key, [])
                localPos = event.pos() - QPoint(self._panX, self._panY)
                polygon.append(localPos)
                self.roomPolygons[key] = polygon
                self.repaint()
                return

            if event.button() == Qt.RightButton:
                key = self._owner.activeKey()
                if key is None:
                    return
                polygon = self.roomPolygons.get(key, None)
                if polygon is None:
                    return
                localPos = event.pos() - QPoint(self._panX, self._panY)
                index = self.__indexUnderMouse(polygon, localPos)
                if index is None:
                    return
                polygon.pop(index)
                self.repaint()
                return

        self.__dragStart = None

    def mouseMoveEvent(self, event):
        if self._panStart is not None:
            self._panX = self._panStart[0] + (event.x() - self._panStart[2])
            self._panY = self._panStart[1] + (event.y() - self._panStart[3])
            self.repaint()
            return
        if self.__dragStart is None:
            return
        localPos = event.pos() - QPoint(self._panX, self._panY)
        delta = localPos - self.__dragStart[0]
        self.__dragStart[1][self.__dragStart[2]] = self.__dragStart[3] + delta
        self.repaint()

    def paint(self, painter):
        self.paintBackground(painter)
        painter.setRenderHint(QPainter.Antialiasing)
        activeKey = self._owner.activeKey()
        if not activeKey:
            return

        painter.setOpacity(0.2)
        for key in self.roomPolygons:
            if key[1] == activeKey[1] and key[0] != activeKey[0]:
                self.drawPolygon(painter, self.roomPolygons[key])
        painter.setOpacity(1.0)

        points = self.findActivePolygon()
        if not points:
            return
        self.drawPolygon(painter, points)


class App(QMainWindowState):
    def __init__(self):
        super(App, self).__init__(QSettings('ImageEditor'))

        self.__worldList = QListView()
        self.__roomList = QListView()
        self.__view = PolygonEdit(self)
        self.__worldList.setModel(QStandardItemModel())
        self.__roomList.setModel(QStandardItemModel())
        self._addDockWidget(self.__worldList, 'Worlds')
        self._addDockWidget(self.__roomList, 'Rooms')
        self._addDockWidget(self.__view, 'View')

        self.__activeRoom = None
        self.__activeWorld = None
        self.__worldRooms = {}
        worldList = self.__worldList.model()
        for key in rooms:
            world = key[1]
            if world not in self.__worldRooms:
                worldList.appendRow(QStandardItem(world))
                self.__worldRooms[world] = []
            self.__worldRooms[world].append(key[0])

        self.__worldList.selectionModel().selectionChanged.connect(self.onWorldSelected)
        self.__roomList.selectionModel().selectionChanged.connect(self.onRoomSelected)

        self.__menuBar = QMenuBar()
        self.setMenuBar(self.__menuBar)
        self.__fileMenu = self.__menuBar.addMenu('File')
        self.__fileMenu.addAction('Save').triggered.connect(self.__onSave)
        self.__fileMenu.addAction('Load').triggered.connect(self.__onLoad)
        self.__fileMenu.addAction('Export').triggered.connect(self.__onExport)

        if os.path.exists('autosave.json'):
            self.load('autosave.json')

    def closeEvent(self, event):
        self.save('autosave.json')

    def __onSave(self):
        filePath = QFileDialog.getSaveFileName(self, 'Save', os.path.dirname(os.path.normpath(__file__)), '*.json')
        if filePath is not None:
            self.save(filePath)

    def __onLoad(self):
        filePath = QFileDialog.getOpenFileName(self, 'Load', os.path.dirname(os.path.normpath(__file__)), '*.json')
        if filePath is not None:
            self.load(filePath)

    def __onExport(self):
        filePath = QFileDialog.getExistingDirectory(self, 'Export', os.path.dirname(os.path.normpath(__file__)))
        if filePath is not None:
            self.export(filePath)

    def export(self, filePath):
        for key, value in self.__view.roomPolygons.iteritems():
            minX = min(value, key=lambda p: p.x()).x()
            minY = min(value, key=lambda p: p.y()).y()
            maxX = max(value, key=lambda p: p.x()).x()
            maxY = max(value, key=lambda p: p.y()).y()
            dest = os.path.join(filePath, '__'.join((key[0], key[1], str(minX), str(minY))) + '.bmp')
            image = QImage(maxX - minX + 1, maxY - minY + 1, QImage.Format_ARGB32)
            image.fill(Qt.black)
            for i, point in enumerate(value):
                image.setPixel(point.x() - minX, point.y() - minY, qRgb(i, 0, 0))
            image.save(dest)

    def save(self, filePath):
        with open(filePath, 'w') as fh:
            result = []
            for key, value in self.__view.roomPolygons.iteritems():
                format = {}
                format['key'] = key
                format['value'] = [(point.x(), point.y()) for point in value]
                result.append(format)
            json.dump(result, fh)

    def load(self, filePath):
        with open(filePath) as fh:
            self.__view.roomPolygons.clear()
            format = json.load(fh)
            for item in format:
                key, value = item['key'], item['value']
                self.__view.roomPolygons[(str(key[0]), str(key[1]))] = [QPoint(*point) for point in value]

    def activeKey(self):
        key = self.__activeRoom, self.__activeWorld
        if None in key:
            return None
        return key

    def onWorldSelected(self, *args):
        idx = self.__worldList.selectionModel().currentIndex()
        roomList = self.__roomList.model()
        roomList.clear()
        if not idx.isValid():
            self.__activeWorld = None
            self.__view.background = None
            return
        item = self.__worldList.model().itemFromIndex(idx)
        self.__activeWorld = str(item.text())
        self.__view.background = QImage(self.__activeWorld + '.jpg')
        for room in self.__worldRooms[self.__activeWorld]:
            inst = QStandardItem(room)
            if (room.lower(), self.__activeWorld) in self.__view.roomPolygons:
                inst.setBackground(Qt.lightGray)
            roomList.appendRow(inst)

        self.onRoomSelected()

    def onRoomSelected(self, *args):
        idx = self.__roomList.selectionModel().currentIndex()
        if not idx.isValid():
            self.__activeRoom = None
            self.__view.repaint()
            return
        item = self.__roomList.model().itemFromIndex(idx)
        self.__activeRoom = str(item.text())
        self.__view.repaint()


if __name__ == '__main__':
    a = QApplication([])
    w = App()
    w.show()
    a.exec_()

Then for navigation I wrote a basic A* pathfinder. This is the most basic introduction I could find, I think I learned from this same site years ago!

import json
import itertools
from structure import *
from scrapeoutput import *


_cache = {}
def findItem(target):
    """ given an item name find what room it lives in (and cache it for speedier queries in the future). """
    room = _cache.get(target, None)
    if room:
        return room
    for key, room in rooms.iteritems():
        if target in room.items:
            _cache[target] = room
            return room


def canTransition(transition, inventory):
    """
    check if a path is blocked
    :type transition: Transition
    :type inventory: [str]
    :rtype: bool
    """
    for requirement in transition.requirements:
        if requirement not in inventory:
            return False
    return True


class AStarNode(object):
    """ simply points to a room and knows how to get there through the hierarchy system """
    def __init__(self, data, parent=None):
        self.data = data
        self.parent = parent

    def cost(self):
        """ assume navigating through a room always costs "1", so going through as little doors as possible is assumed to be the shortest path """
        if self.parent is not None:
            return 1 + self.parent.cost()
        return 1

    def __repr__(self):
        if self.parent is not None:
            return '%s (from %s)' % (self.data.name, self.parent.data.name)
        return self.data.name


def growAdjacentNodes(node, inventory, open, closed):
    """
    Update the open list:
    Get adjacent tiles from node.
    If in closed do not add.
    If in open update best score.
    Else add to open.

    :type node: AStarNode
    :type inventory: [str]
    :type open: [AStarNode]
    :type closed: [AStarNode]
    :rtype: [AStarNode]
    """
    for transition in node.data.transitions:
        if not canTransition(transition, inventory):
            continue

        isInClosedList = False
        for entry in closed:
            if entry.data == transition.targetRoom:
                isInClosedList = True
                break
        if isInClosedList:
            continue

        newNode = AStarNode(transition.targetRoom, node)
        cost = newNode.cost()
        for i, entry in enumerate(open):
            if entry.data == transition.targetRoom:
                if cost < entry.cost():
                    open[i] = newNode
                break
        else:
            open.append(newNode)


class AstarException(Exception): pass


def aStar(startRoom, destinationRoom, inventory):
    """ basic path finder """
    closed = [AStarNode(startRoom)]
    open = []
    growAdjacentNodes(closed[0], inventory, open, closed)
    destinationNode = None
    for i in xrange(10000):  # failsafe
        for entry in open:
            if entry.data == destinationRoom:
                destinationNode = entry
                break
        if destinationNode:
            break
        if not open:
            raise AstarException('Out of options searching %s. Closed list: \n%s' % (destinationRoom.name, '\n'.join(str(i) for i in closed)))
        best = min(open, key=lambda x: x.cost())
        open.remove(best)
        closed.append(best)
        growAdjacentNodes(best, inventory, open, closed)
    iter = destinationNode
    path = []
    while iter:
        path.insert(0, (iter.data.name, iter.data.area))
        iter = iter.parent
    return path


def shortestPath(startRoom, itemKey, ioInventory):
    """ utility to kick off the path finder and compile the results """
    target = items[itemKey]
    for requirement in target.requirements:
        if requirement not in ioInventory:
            raise AstarException()
    destinationRoom = findItem(target)
    if startRoom == destinationRoom:
        ioInventory.append(target.name)
        return ['Aquired: %s' % target.name], destinationRoom
    path = aStar(startRoom, destinationRoom, ioInventory)
    if not path:
        raise RuntimeError()
    ioInventory.append(target.name)
    return path[1:] + ['Aquired: %s' % target.name], destinationRoom


def shortestMultiPath(startRoom, orderlessItems, finalItem, ioInventory):
    """ utility to try out all ways to get the orderlessItems and returns the most optimal version
    finalItem is the next item to get, it is included because the most optimal route should also be close to the next destination to be truly optimal """
    results = []
    for option in itertools.permutations(orderlessItems):
        inv = ioInventory[:]
        totalPath = []
        cursor = startRoom
        for itemKey in option + (finalItem,):
            path, cursor = shortestPath(cursor, itemKey, inv)
            totalPath += path
        results.append((totalPath, cursor, inv))
    # get result with shortest path
    result = min(results, key=lambda r: len(r[0]))
    ioInventory += result[2][len(ioInventory):]
    return result[0], result[1]

With this we can navigate from item to item and record the whole play through. After doing this some amendmends were necessary to fix things missed by the wiki scrape, such as activating a switch in room A to move aside something in room B. I solved that by adding a "switch" item to the right room and inserting it into the ordered item list that the navigator will walk along. After I had the pathfinder working and showing the resulting path on a map with highlighting, I went on and exported that all to a webpage! I just added that inline in the startup code. This whole thing does the navigation, generates a webpage and then shows a Qt app in a surprisingly small amount of time.

Here is that visualizer code:

from image_editor import PolygonZoom
from qt import *


class App(QMainWindowState):
    def __init__(self):
        super(App, self).__init__(QSettings('Navigator'))
        self.view = PolygonZoom(self)
        self.timeline = QListView()
        model = QStandardItemModel()
        self.timeline.setModel(model)
        self.setCentralWidget(self.view)
        self._addDockWidget(self.timeline, 'Timeline', Qt.LeftDockWidgetArea)
        self.timeline.selectionModel().selectionChanged.connect(self.__onUpdate)
        self.__key = None

        with open('autosave.json') as fh:
            self.view.roomPolygons.clear()
            format = json.load(fh)
            for item in format:
                key, value = item['key'], item['value']
                self.view.roomPolygons[(str(key[0]), str(key[1]))] = [QPoint(*point) for point in value]

        # record playthrough
        inventory = []
        itemOrder = ('missile launcher', 'violet translator', 'morph ball bomb', 'amber translator', 'space jump boots', 'dark beam', 'light beam',
                     ('dark agon temple key 1', 'dark agon temple key 2', 'dark agon temple key 3', 'dark suit'), 'agon energy', 'agon energy delivery',
                     'super missile', 'emerald translator', 'boost ball', 'dark torvus temple key 1', 'seeker launcher',
                     'catacombs lock', 'gathering lock',
                     'gravity boost', 'grapple beam',
                     ('dark torvus temple key 2', 'dark torvus temple key 3', 'dark visor'), 'torvus energy', 'torvus energy delivery',
                     'spider ball', 'power bomb', 'echo visor', 'screw attack',
                     ('ing hive temple key 1', 'ing hive temple key 2', 'ing hive temple key 3', 'annihilator beam'), 'sanctuary energy', 'sanctuary energy delivery',
                     'light suit',
                     'sky temple key 1', 'sky temple key 2', 'sky temple key 3', 'sky temple key 4', 'sky temple key 5', 'sky temple key 6', 'sky temple key 7', 'sky temple key 8', 'sky temple key 9',
                     'temple energy',
                     'temple energy delivery',

                     'missile expansion17', 'beam ammo expansion3', 'power bomb expansion5', 'darkburst', 'missile expansion12'
                     )
        startRoom = rooms[('landing site', 'Temple Grounds')]

        inst = QStandardItem('Landing Site')
        inst.setData('Temple Grounds')
        model.appendRow(inst)

        for itemKey in itemOrder:
            try:
                if isinstance(itemKey, tuple):
                    path, startRoom = shortestMultiPath(startRoom, itemKey[:-1], itemKey[-1], inventory)
                else:
                    path, startRoom = shortestPath(startRoom, itemKey, inventory)
            except ValueError:
                print 'Error finding %s' % str(itemKey)
                raise
            if not path:
                raise RuntimeError()
            for room_area in path:
                if isinstance(room_area, tuple):
                    room, area = room_area
                else:
                    room, area = room_area, None
                inst = QStandardItem(room)
                if area:
                    inst.setData(area)
                model.appendRow(inst)

        worldPolygons = {}
        with open('index.html', 'w') as fh:
            fh.write('')
            fh.write('')
            fh.write('')
            fh.write('')
            fh.write('
') for i in xrange(model.rowCount()): data = str(model.item(i).data()) room = str(model.item(i).text()) if not room.lower().startswith('aquired'): worldPolygons[data] = worldPolygons.get(data, {}) try: worldPolygons[data][room] = self.view.roomPolygons[(room.lower(), data)] except: worldPolygons[data][room] = [] data = '' if not data else 'data="%s"' % data fh.write('
%s
' % (data, room)) fh.write('
') with open('polygons.js', 'w') as fh: fh.write('polygons = {') for world in worldPolygons: fh.write('"%s": {' % world) for room in worldPolygons[world]: if worldPolygons[world][room]: poly = '%s' % (', '.join(['[%s, %s]' % (pt.x(), pt.y()) for pt in worldPolygons[world][room]])) fh.write('"%s": [%s],' % (room, poly)) fh.write('},') fh.write('};') def activeKey(self): return self.__key def __onUpdate(self, *args): self.view.state = 0 idx = self.timeline.selectionModel().currentIndex() if idx.isValid(): item = self.timeline.model().itemFromIndex(idx) label = str(item.text().lower()) if label.startswith('aquired: '): item = self.timeline.model().item(idx.row() - 1) label = str(item.text().lower()) self.view.state = 1 world = str(item.data()) self.__key = label, world self.view.background = QImage(world + '.jpg') else: self.__key = None self.view.background = None self.view.repaint() if __name__ == '__main__': a = QApplication([]) w = App() w.show() a.exec_()

This is definitely one of the sillier things to do in your spare time 🙂
Navigate the result here!

Accelerating Maya -> PyOpenGL mesh IO

A few weeks back I posted about exporting a mesh from Maya and drawing it with Python.

Faster export

I recently got back to improving this a little. First I improved maya exporter performance by porting it to a C++ plugin.
I don’t want to go over all the details, because it is similar to the python version posted before and if I’m going to explain this code properly I’d have to do a tutorial series on the Maya API in the first place! So here’s a little dump of the visual studio project instead: plugin.vcxproj!

It is currently very basic and just exports all data it can find. I’m aware certain maya models can crash certain other functions in Maya’s MFnMesh (and related) class. E.g. empty UV sets, UV sets with UVs for only certain vertices/faces, geometry with holes crashing getTriangles, etc. It may be good to write a python layer that does some validation on the mesh as well as add flags to explicitly export (or ignore) certain attributes and UV/color sets.

Faster import

Next I used the python mmap (memory map) module to upload the mesh directly from disk to openGL without getting (and therefore boxing) the raw data in Python objects first. Previously I was loading binary to python, which requires python to cast the binary to a python object, which I then wrapped into a ctypes object, allocating and copying huge chunks of memory and constructing tons of python objects. With mmap I can just cast the file handle to a void* and hand it to glBufferData.

import os
import mmap
import ctypes
import contextlib


@contextlib.contextmanager
def memoryMap(fileDescriptor, sizeInBytes=0, offsetInBytes=0):
    if isinstance(fileDescriptor, basestring):
        fd = os.open(fileDescriptor, os.O_RDWR | os.O_BINARY)
        ownFd = True
    else:
        fd = fileDescriptor
        ownFd = False
    mfd = None
    try:
        mfd = mmap.mmap(fd, sizeInBytes, offset=offsetInBytes)
        yield MappedReader(mfd)
    finally:
        if mfd is not None:
            mfd.close()
        if ownFd:
            os.close(fd)


class MappedReader(object):
    def __init__(self, memoryMap):
        """Wrap a memory map into a stream that can stream through the file and map sections to ctypes."""
        self.__memoryMap = memoryMap
        self.__offset = 0

    def close(self):
        self.__memoryMap.close()

    def size(self):
        return self.__memoryMap.size()

    def seek(self, offset):
        assert offset >= 0 and offset < self.size(), 'Seek %s beyond file bounds [0, %s)' % (offset, self.size())
        self.__offset = offset

    def tell(self):
        return self.__offset

    def read(self, ctype):
        """
        Map a part of the file memory to a ctypes object (from_buffer, so ctype points directly to file memory).
        Object type is inferred from the given type.
        File cursor is moved to the next unread byte (seek = tell + sizeof(ctype)).
        """
        result = ctype.from_buffer(self.__memoryMap, self.__offset)
        self.__offset += ctypes.sizeof(result)
        return result

    def readValue(self, ctype):
        """
        Utility to read and directly return the data cast as a python value.
        """
        return self.read(ctype).value

The memoryMap context can take a file descriptor (acquired through os.open, different from the regular open) or file path.
It will then open the entire file as read-only binary and map it instead of reading it.
Last it returns a MappedReader object which is a little wrapper around the mmap object that assists in reading chunks as a certain ctype.
This way I can easily read some header data (previously I'd do this by reading n bytes and using struct.unpack) and then read the remainder (or a large chunk) of the file as a ctypes pointer.

This code is a refactor from what I did in the tutorial mentioned at the top, but using mmap instead! It is mostly identical.

def _loadMesh_v0(stream, vao, bufs):
    vertexCount = stream.readValue(ctypes.c_uint32)
    vertexSize = stream.readValue(ctypes.c_ubyte)

    indexCount = stream.readValue(ctypes.c_uint32)
    indexSize = stream.readValue(ctypes.c_ubyte)

    assert indexSize in indexTypeFromSize, 'Unknown element data type, element size must be one of %s' % indexTypeFromSize.keys()
    indexType = indexTypeFromSize[indexSize]

    drawMode = stream.readValue(ctypes.c_uint32)
    assert drawMode in (GL_LINES, GL_TRIANGLES), 'Unknown draw mode.'  # TODO: list all render types

    # gather layout
    numAttributes = stream.readValue(ctypes.c_ubyte)

    offset = 0
    layouts = [None] * numAttributes
    for i in xrange(numAttributes):
        location = stream.readValue(ctypes.c_ubyte)
        dimensions = stream.readValue(ctypes.c_ubyte)
        assert dimensions in (1, 2, 3, 4)
        dataType = stream.readValue(ctypes.c_uint32)
        assert dataType in attributeElementTypes, 'Invalid GLenum value for attribute element type.'
        layouts[i] = AttributeLayout(location, dimensions, dataType, offset)
        offset += dimensions * sizeOfType[dataType]

    assert offset == vertexSize, 'File says each chunk of vertex data is %s bytes, but attribute layout used up %s bytes' % (vertexSize, offset)

    # apply layout
    for layout in layouts:
        glVertexAttribPointer(layout.location, layout.dimensions, layout.dataType, GL_FALSE, vertexSize, ctypes.c_void_p(layout.offset))  # total offset is now stride
        glEnableVertexAttribArray(layout.location)

    raw = stream.read(ctypes.c_ubyte * (vertexSize * vertexCount))
    glBufferData(GL_ARRAY_BUFFER, vertexSize * vertexCount, raw, GL_STATIC_DRAW)

    raw = stream.read(ctypes.c_ubyte * (indexSize * indexCount))
    glBufferData(GL_ELEMENT_ARRAY_BUFFER, indexSize * indexCount, raw, GL_STATIC_DRAW)

    if stream.size() - stream.tell() > 0:
        raise RuntimeError('Error reading mesh file, more data in file after we were done reading.')
    
    return Mesh(vao, bufs, drawMode, indexCount, indexType)


def model(filePath):
    vao = glGenVertexArrays(1)
    glBindVertexArray(vao)
    bufs = glGenBuffers(2)
    glBindBuffer(GL_ARRAY_BUFFER, bufs[0])
    glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, bufs[1])
    with memoryMap(filePath) as stream:
        fileVersion = stream.readValue(ctypes.c_ubyte)
        if fileVersion == 0:
            return _loadMesh_v0(stream, vao, bufs)
        raise RuntimeError('Unknown mesh file version %s in %s' % (fileVersion, filePath))

Attribute editor in PyQt

I’ve been working on a particle editor, though that isn’t entirely done yet, I did create something interesting in the process. An attribute editor for arbitrary python objects.

This is where I’m at right now, I hope to get to work on this more and share details about the particles themselves once it is more complete.

On the right you see an editor for the following object:

class ParticleSettings(OrderedClass):
    def __init__(self):
        super(ParticleSettings, self).__init__()
        # emitter
        self.emitterType = Enum(('Sphere', 'Cone', 'Box'), 0)
        self.emitterSettings = Vec3([0.5, 0.5, 0.5])
        self.emitterIsVolume = True
        self.randomDirection = False
        # not curve based
        self.startSize = RandomFloat()
        self.startSpeed = RandomFloat()
        self.startRotation = RandomFloat()
        self.lifeTime = RandomFloat()
        # curve based on particle alive time / life time
        self.sizeOverTime = RandomChannelFloat()
        self.angularVelocity = RandomChannelFloat()
        self.velocityOverTime = RandomChannelVec3()

I’ve added some data types so I can visualize them better, but the attribute editing framework I wrote works off the bat on python’s basic types.
I’d like to break down how I got here, as I wrote a heap of code which still needs a heap of refactoring for it to be presentable, I’ll demonstrate creating a more basic example, which should be more useful because it isn’t cluttered with my edge cases.

Preparing edit widgets

First, I made some widgets to edit some basic data types. Because we want to generate and connect our widgets to data, it’d be nice if they all have the same interface to keep the rest of our code abstract. I went for the following interface:

class AEComponent(QObject):
    # Attribute editor widget editing a single value type. Note that UI interactions from the user should emit valueChanged.
    valueChanged = pyqtSignal(object)

    def __init__(self):
        # The constructor may accept additional arguments, e.g. default value or enum options
        self._value = None

    def value(self):
        # Return the internal value
        return self._value

    def setValue(self, value):
        # Set value should programatically adjust the internal value, without emitting a signal; used in case multiple set values may trigger or when a parent widget is already going to send a change event.
        self.blockSignals(True)
        self._value = value
        self.blockSignals(False)

    def editValue(self, value):
        # Set the value and emit a change event
        self._value = value
        self.valueChanged.emit(value)

Note that this is an example of the interface, not a base class. I will not actually use the code above, I’ll just subclass Qt widgets and make them behave the same.

The core data types I want to support are:

int QSpinBox
float QDoubleSpinBox
bool checkable QPushButton
str QLineEdit
object recurse into its propreties
dict recurse into its items
list recurse into its items

Because tuples & sets are not mutable it’d be hard to construct a widget that sets the entire tuple at once.
I do not intend to adjust the composition of lists, dicts and objects – so no element insertion / removal.

Int & double
QSpinBox already has a value and setValue, but the setValue emits a signal. Instead I’m adding an editValue that forwards to the super setValue and make setValue block the signals. I’ve also made it so I can construct versions that only support e.g. ctypes.c_char by adding a number of bits parameter that is used to infer limits. It’d be trivial to extend this to unsigned and size-limited variants. The LineEditSelected used is listed below at the QLineEdit, it just simply selects all text at the focus event.

class SpinBox(QSpinBox):
    """
    QSpinBox with right limits & that follows the AEComponent interface.
    """
    def __init__(self, value=0, bits=32):
        super(SpinBox, self).__init__()
        self.setMinimum(-2 ** (bits - 1))
        self.setMaximum(2 ** (bits - 1) - 1)
        self.setValue(value)
        self.setLineEdit(LineEditSelected())

    def setValue(self, value):
        self.blockSignals(True)
        super(SpinBox, self).setValue(value)
        self.blockSignals(False)

    def editValue(self, value):
        super(SpinBox, self).setValue(value)

Doubles are almost identical.

class DoubleSpinBox(QDoubleSpinBox):
    """
    QDoubleSpinBox with right limits & that follows the AEComponent interface.
    """
    def __init__(self, value=0.0):
        super(DoubleSpinBox, self).__init__()
        self.setMinimum(-float('inf'))
        self.setMaximum(float('inf'))
        self.setValue(value)
        self.setSingleStep(0.01)  # Depending on use case this can be very coarse.
        self.setLineEdit(LineEditSelected())

    def setValue(self, value):
        self.blockSignals(True)
        super(DoubleSpinBox, self).setValue(value)
        self.blockSignals(False)

    def editValue(self, value):
        super(DoubleSpinBox, self).setValue(value)

Booleans with icons
A few more interesting things to make this work based on a checkable QPushButton.
Manual value changed signal handling & keeping track of the icon to use.

class IconBoolEdit(QPushButton):
    """
    QPushButton with icons to act as a boolean (not tri-state) toggle.
    """
    valueChanged = pyqtSignal(bool)

    def __init__(self, *args):
        super(IconBoolEdit, self).__init__(*args)
        self.__icons = icons.get('Unchecked'), icons.get('Checked')  # Implement your own way to get icons!
        self.setIcon(self.__icons[0])
        self.setCheckable(True)
        self.clicked.connect(self.__updateIcons)
        self.clicked.connect(self.__emitValueChanged)

    def setIcons(self, off, on):
        self.__icons = off, on
        self.__updateIcons(self.isChecked())

    def __updateIcons(self, state):
        self.setIcon(self.__icons[int(state)] or QIcon())

    def __emitValueChanged(self, state):
        self.valueChanged.emit(state)

    def value(self):
        return self.isChecked()

    def setValue(self, state):
        self.setChecked(state)
        self.__updateIcons(state)

    def editValue(self, state):
        self.setChecked(state)
        self.__updateIcons(state)
        self.__emitValueChanged(state)

Strings
This is very similar to the spinbox. One addition I added is to make sure clicking the line edit selects all constants so a user can start typing a new word immediately.

class LineEdit(QLineEdit):
    valueChanged = pyqtSignal(str)

    def __init__(self, *args):
        super(LineEdit, self).__init__(*args)
        self.textChanged.connect(self.valueChanged.emit)

    def value(self):
        return self.text()

    def setValue(self, text):
        self.blockSignals(True)
        self.setText(text)
        self.blockSignals(False)

    def editValue(self, text):
        self.setText(text)


class LineEditSelected(LineEdit):
    def __init__(self):
        super(LineEditSelected, self).__init__()
        self.__state = False

    def focusInEvent(self, event):
        super(LineEditSelected, self).focusInEvent(event)
        self.selectAll()
        self.__state = True

    def mousePressEvent(self, event):
        super(LineEditSelected, self).mousePressEvent(event)
        if self.__state:
            self.selectAll()
            self.__state = False

Reflecting python objects

Reflection in python is very easy, and our use case simple.
Every python object has a __dict__ attribute that contains all the current members of an object (but not methods).
In python we tend to denote protected (internal) data by prefixing variable names with an underscore.
So to find all attributes that we want to inspect we can simply do:

for name in instance.__dict__:
    if name[0] == '_':
        continue

Now to control such an attribute with a widget we need to construct the right widget and connect the change event to a setter.
In python we can use the functools module to bind the global getattr and setattr methods and get a way to connect a callback to a property assignment.

    value = getattr(instance, name)  # get the current value by name, like the dot operator but using a string to get to the right property
    cls = factory.findEditorForType(type(value))  # factory to get the right widget for our data type, more on this later
    widget = cls()  # construct the widget
    widget.setValue(getattr(instance, name))  # set the editor's initial value to match with our data
    widget.valueChanged.connect(functools.partial(setattr, instance, name))  # make the editor update our data

Widget factory

The last piece of the puzzle is a way to generate widgets based on data types. I wanted to keep this abstract, so I made a class out of it.
We can register data type & widget type relations and it understands to create a widget if we have one registered for a base class of the type we’re querying.

class AEFactory(object):
    def __init__(self):
        self.__typeWidgets = {}

    def registerType(self, dataType, widgetConstructor):
        self.__typeWidgets[dataType] = widgetConstructor

    @staticmethod
    def _allBaseTypes(cls):
        """
        Recurse all base classes and return a list of all bases with most close relatives first.
        https://stackoverflow.com/questions/1401661/list-all-base-classes-in-a-hierarchy-of-given-class
        """
        result = list(cls.__bases__)
        for base in result:
            result.extend(AEFactory._allBaseTypes(base))
        return result

    def _findEditorForType(self, dataType):
        if dataType in self.__typeWidgets:
            return self.__typeWidgets[dataType]

        for baseType in AEFactory._allBaseTypes(dataType):
            if dataType in self.__typeWidgets:
                return self.__typeWidgets[baseType]

Complex data

Now this will work fine for simple objects with simple data types. But the real fun begins when we have instances whose properties are lists of other instances.
Our findEditorForType will return None in this case and we get an error. Instead, we should split this up in several steps. First we determine the type of data we’re dealing with, to defer the widget creation to any type of recursive function until we reach simple data types for which we can generate widgets.

from collections import OrderedDict

class AEFactor(object):

... the above code still goes here ...

    def generate(self, data, parent=None, name=None):
        """
        This recursively generates widgets & returns an iterator of every resulting item.
        """
        if isinstance(data, (dict, OrderedDict)):
            generator = self._generateMap(data)
        elif hasattr(data, '__getitem__') and hasattr(data, '__setitem__'):
            generator = self._generateList(data)
        elif hasattr(data, '__dict__'):
            generator = self._generateInstance(data)
        else:
            generator = self._generateField(data, parent, name)

    def _generateField(self, data, parent, name):
        cls = self._findEditorForType(type(data))
        assert cls, 'Error: could not inspect object "%s" (parent: %s, name: %s). No wrapper registered or non-supported compound type.' % (data, parent, name)
        widget = cls()
        widget.setValue(data)
        widget.valueChanged.connect(functools.partial(setattr, parent, name))
        yield widget

    def _generateInstance(self, data):
        for name in data.__dict__:
            if name[0] == '_':
                continue
            yield QLabel(name)
            for widget in self.generate(getattr(data, name), data, name):
                yield widget

    def _generateList(self, data):
        for i in xrange(len(data)):
            yield QLabel(str(i))
            for widget in self.generate(data[i], data, str(i)):
                yield widget

    def _generateMap(self, data):
        for key in data:
            yield QLabel(str(key))
            for widget in self.generate(data[key], data, key):
                yield widget

Formatting

If we have a class that needs a special widget or layout, like my particle editor, we may wish to grab the widgets generated for that class and manipulate them.
One case I have is that I have a random channel, which has a minimum, maximum and isRandom flag. If isRandom is turned off then I just want to show the minimum field because the maximum is unused. In order to do this I extended the factory with the ability to inject functions that take groups of widgets for a certain data
type. See registerWrapper, findWrapperForType and the modifications at the end of generate.

class AEFactory(object):
    def __init__(self):
        self.__typeWidgets = {}
        self.__typeWrappers = {}

    def registerType(self, dataType, widgetConstructor):
        self.__typeWidgets[dataType] = widgetConstructor

    def registerWrapper(self, dataType, wrapperFunction):
        """
        The wrapperFunction must accept a generator of widgets & return a generator of widgets.
        """
        self.__typeWrappers[dataType] = wrapperFunction

    @staticmethod
    def _allBaseTypes(cls):
        """
        Recurse all base classes and return a list of all bases with most close relatives first.
        https://stackoverflow.com/questions/1401661/list-all-base-classes-in-a-hierarchy-of-given-class
        """
        result = list(cls.__bases__)
        for base in result:
            result.extend(AEFactory._allBaseTypes(base))
        return result

    def _findEditorForType(self, dataType):
        if dataType in self.__typeWidgets:
            return self.__typeWidgets[dataType]

        for baseType in AEFactory._allBaseTypes(dataType):
            if dataType in self.__typeWidgets:
                return self.__typeWidgets[baseType]

    def _findWrapperForType(self, dataType):
        if dataType in self.__typeWrappers:
            return self.__typeWrappers[dataType]

        for baseType in AEFactory._allBaseTypes(dataType):
            if dataType in self.__typeWrappers:
                return self.__typeWrappers[baseType]

    def generate(self, data, parent=None, name=None):
        """
        This recursively generates widgets & returns an iterator of every resulting item.
        """
        if isinstance(data, (dict, OrderedDict)):
            generator = self._generateMap(data)
        elif hasattr(data, '__getitem__') and hasattr(data, '__setitem__'):
            generator = self._generateList(data)
        elif hasattr(data, '__dict__'):
            generator = self._generateInstance(data)
        else:
            generator = self._generateField(data, parent, name)

        wrapper = self._findWrapperForType(type(data))
        if wrapper:
            generator = wrapper(generator)
        for widget in generator:
            yield widget

    def _generateField(self, data, parent, name):
        cls = self._findEditorForType(type(data))
        assert cls, 'Error: could not inspect object "%s" (parent: %s, name: %s). No wrapper registered or non-supported compound type.' % (data, parent, name)
        widget = cls()
        widget.setValue(data)
        widget.valueChanged.connect(functools.partial(setattr, parent, name))
        yield widget

    def _generateInstance(self, data):
        for name in data.__dict__:
            if name[0] == '_':
                continue
            yield QLabel(name)
            for widget in self.generate(getattr(data, name), data, name):
                yield widget

    def _generateList(self, data):
        for i in xrange(len(data)):
            yield QLabel(str(i))
            for widget in self.generate(data[i], data, str(i)):
                yield widget

    def _generateMap(self, data):
        for key in data:
            yield QLabel(str(key))
            for widget in self.generate(data[key], data, key):
                yield widget
Note: I currently allow it to work on sub classes, with the risk of that subclass having extra attributes – or a different attribute order – resulting in the widgets being jumbled & my function breaking the layout completely. I’m not sure yet how to validate that a sub class matches the base class’ member layout, so maybe I should just allow explicit overrides for a single type without inheritance support.

Constraining class member order

One thing that annoys me, and maybe you noticed already, is that python does not guarantee that dictionaries are ordered.
For this the collections.OrderedDict type exists, but when dealing with class members and the __dict__ attribute we have no control over this.

Now my solution to this is pretty shaky, and I’m definitely not proud of what I came up with, but let me share it anyway!
First I created a class that overrides __setattr__ to keep track of the order in which data is set.
Then I override __getattribute__ so that when the __dict__ attribute is requested we return a wrapper around it that behaves
like the real dict, but implements all iterators to use the ordered keys list instead.

class FakeOrderedDict(object):
    def __init__(self, realDict, order):
        self.realDict = realDict
        self.order = order

    def __getitem__(self, key):
        return self.realDict[key]

    def __setitem__(self, key, value):
        self.realDict[key] = value

    def __iter__(self):
        return iter(self.order)

    def iterkeys(self):
        return iter(self.order)

    def itervalues(self):
        for key in self.order:
            yield self.realDict[key]

    def iteritems(self):
        for key in self.order:
            yield key, self.realDict[key]


class OrderedClass(object):
    def __init__(self):
        self.__dict__['_OrderedClass__attrs'] = []

    def __getattribute__(self, key):
        result = super(OrderedClass, self).__getattribute__(key)
        if key == '__dict__':
            if '_OrderedClass__attrs' in result:
                return FakeOrderedDict(result, result['_OrderedClass__attrs'])
        return result

    def __setattr__(self, key, value):
        order = self.__dict__['_OrderedClass__attrs']
        if key not in order:
            order.append(key)
        return super(OrderedClass, self).__setattr__(key, value)

That’s all folks

Example usage:

# create test objects
class Vector(list):
    pass


class Compound(OrderedClass):  # inheriting from OrderedClass to ensure widget order
    def __init__(self):
        super(Compound, self).__init__()
        self.x = 2.0  # note how explicit floats are important now
        self.y = 5.0


class Data(OrderedClass):
    def __init__(self):
        super(Data, self).__init__()
        self.name = 'List test'
        self.value = Vector([1.0, 5, True])
        self.dict = {'A': Compound(), 'B': Compound()}


def groupHLayout(widgets):
    h = QHBoxLayout()
    m = QWidget()
    for w in widgets:
        h.addWidget(w)
    m.setLayout(h)
    yield m


# create test data
data = Data()

# create Qt application
app = QApplication([])
window = QWidget()
main = QVBoxLayout()
window.setLayout(main)

# initialize inspector
factory = AEFactory()
factory.registerType(bool, IconBoolEdit)
factory.registerType(int, SpinBox)
factory.registerType(float, DoubleSpinBox)
factory.registerType(str, LineEdit)
factory.registerWrapper(Vector, groupHLayout)

# inspect the data
for widget in factory.generate(data):
    main.addWidget(widget)

window.show()
app.exec_()

# print the data after closing the editor to show we indeed propagated the changes to the data as they happened
print data.name, data.value, data.dict['A'].x, data.dict['A'].y, data.dict, data.dict['B'].x, data.dict['B'].y

Last, have a full code dump!

from collections import OrderedDict
import functools
from PyQt4.QtCore import *
from PyQt4.QtGui import *


class SpinBox(QSpinBox):
    """
    QSpinBox with right limits & that follows the AEComponent interface.
    """

    def __init__(self, value=0, bits=32):
        super(SpinBox, self).__init__()
        self.setMinimum(-2 ** (bits - 1))
        self.setMaximum(2 ** (bits - 1) - 1)
        self.setValue(value)
        self.setLineEdit(LineEditSelected())

    def setValue(self, value):
        self.blockSignals(True)
        super(SpinBox, self).setValue(value)
        self.blockSignals(False)

    def editValue(self, value):
        super(SpinBox, self).setValue(value)


class DoubleSpinBox(QDoubleSpinBox):
    """
    QDoubleSpinBox with right limits & that follows the AEComponent interface.
    """

    def __init__(self, value=0.0):
        super(DoubleSpinBox, self).__init__()
        self.setMinimum(-float('inf'))
        self.setMaximum(float('inf'))
        self.setValue(value)
        self.setSingleStep(0.01)  # Depending on use case this can be very coarse.
        self.setLineEdit(LineEditSelected())

    def setValue(self, value):
        self.blockSignals(True)
        super(DoubleSpinBox, self).setValue(value)
        self.blockSignals(False)

    def editValue(self, value):
        super(DoubleSpinBox, self).setValue(value)


class IconBoolEdit(QPushButton):
    """
    QPushButton with icons to act as a boolean (not tri-state) toggle.
    """
    valueChanged = pyqtSignal(bool)

    def __init__(self, *args):
        super(IconBoolEdit, self).__init__(*args)
        self.__icons = None, None  # icons.get('Unchecked'), icons.get('Checked')  # Implement your own way to get icons!
        self.setIcon(self.__icons[0] or QIcon())
        self.setCheckable(True)
        self.clicked.connect(self.__updateIcons)
        self.clicked.connect(self.__emitValueChanged)

    def setIcons(self, off, on):
        self.__icons = off, on
        self.__updateIcons(self.isChecked())

    def __updateIcons(self, state):
        self.setIcon(self.__icons[int(state)] or QIcon())

    def __emitValueChanged(self, state):
        self.valueChanged.emit(state)

    def value(self):
        return self.isChecked()

    def setValue(self, state):
        self.setChecked(state)
        self.__updateIcons(state)

    def editValue(self, state):
        self.setChecked(state)
        self.__updateIcons(state)
        self.__emitValueChanged(state)


class LineEdit(QLineEdit):
    valueChanged = pyqtSignal(str)

    def __init__(self, *args):
        super(LineEdit, self).__init__(*args)
        self.textChanged.connect(self.valueChanged.emit)

    def value(self):
        return self.text()

    def setValue(self, text):
        self.blockSignals(True)
        self.setText(text)
        self.blockSignals(False)

    def editValue(self, text):
        self.setText(text)


class LineEditSelected(LineEdit):
    def __init__(self):
        super(LineEditSelected, self).__init__()
        self.__state = False

    def focusInEvent(self, event):
        super(LineEditSelected, self).focusInEvent(event)
        self.selectAll()
        self.__state = True

    def mousePressEvent(self, event):
        super(LineEditSelected, self).mousePressEvent(event)
        if self.__state:
            self.selectAll()
            self.__state = False


class AEFactory(object):
    def __init__(self):
        self.__typeWidgets = {}
        self.__typeWrappers = {}

    def registerType(self, dataType, widgetConstructor):
        self.__typeWidgets[dataType] = widgetConstructor

    def registerWrapper(self, dataType, wrapperFunction):
        """
        The wrapperFunction must accept a generator of widgets & return a generator of widgets.
        """
        self.__typeWrappers[dataType] = wrapperFunction

    @staticmethod
    def _allBaseTypes(cls):
        """
        Recurse all base classes and return a list of all bases with most close relatives first.
        https://stackoverflow.com/questions/1401661/list-all-base-classes-in-a-hierarchy-of-given-class
        """
        result = list(cls.__bases__)
        for base in result:
            result.extend(AEFactory._allBaseTypes(base))
        return result

    def _findEditorForType(self, dataType):
        if dataType in self.__typeWidgets:
            return self.__typeWidgets[dataType]

        for baseType in AEFactory._allBaseTypes(dataType):
            if dataType in self.__typeWidgets:
                return self.__typeWidgets[baseType]

    def _findWrapperForType(self, dataType):
        if dataType in self.__typeWrappers:
            return self.__typeWrappers[dataType]

        for baseType in AEFactory._allBaseTypes(dataType):
            if dataType in self.__typeWrappers:
                return self.__typeWrappers[baseType]

    def generate(self, data, parent=None, name=None):
        """
        This recursively generates widgets & returns an iterator of every resulting item.
        """
        if isinstance(data, (dict, OrderedDict)):
            generator = self._generateMap(data)
        elif hasattr(data, '__getitem__') and hasattr(data, '__setitem__'):
            generator = self._generateList(data)
        elif hasattr(data, '__dict__'):
            generator = self._generateInstance(data)
        else:
            generator = self._generateField(data, parent, name)

        wrapper = self._findWrapperForType(type(data))
        if wrapper:
            generator = wrapper(generator)
        for widget in generator:
            yield widget

    def _generateField(self, data, parent, name):
        cls = self._findEditorForType(type(data))
        assert cls, 'Error: could not inspect object "%s" (parent: %s, name: %s). No wrapper registered or non-supported compound type.' % (data, parent, name)
        widget = cls()
        widget.setValue(data)
        widget.valueChanged.connect(functools.partial(setattr, parent, name))
        yield widget

    def _generateInstance(self, data):
        for name in data.__dict__:
            if name[0] == '_':
                continue
            yield QLabel(name)
            for widget in self.generate(getattr(data, name), data, name):
                yield widget

    def _generateList(self, data):
        for i in xrange(len(data)):
            yield QLabel(str(i))
            for widget in self.generate(data[i], data, str(i)):
                yield widget

    def _generateMap(self, data):
        for key in data:
            yield QLabel(str(key))
            for widget in self.generate(data[key], data, key):
                yield widget


class FakeOrderedDict(object):
    def __init__(self, realDict, order):
        self.realDict = realDict
        self.order = order

    def __getitem__(self, key):
        return self.realDict[key]

    def __setitem__(self, key, value):
        self.realDict[key] = value

    def __iter__(self):
        return iter(self.order)

    def iterkeys(self):
        return iter(self.order)

    def itervalues(self):
        for key in self.order:
            yield self.realDict[key]

    def iteritems(self):
        for key in self.order:
            yield key, self.realDict[key]


class OrderedClass(object):
    def __init__(self):
        self.__dict__['_OrderedClass__attrs'] = []

    def __getattribute__(self, key):
        result = super(OrderedClass, self).__getattribute__(key)
        if key == '__dict__':
            if '_OrderedClass__attrs' in result:
                return FakeOrderedDict(result, result['_OrderedClass__attrs'])
        return result

    def __setattr__(self, key, value):
        order = self.__dict__['_OrderedClass__attrs']
        if key not in order:
            order.append(key)
        return super(OrderedClass, self).__setattr__(key, value)


# create test objects
class Vector(list):
    pass


class Compound(OrderedClass):  # inheriting from OrderedClass to ensure widget order
    def __init__(self):
        super(Compound, self).__init__()
        self.x = 2.0  # note how explicit floats are important now
        self.y = 5.0


class Data(OrderedClass):
    def __init__(self):
        super(Data, self).__init__()
        self.name = 'List test'
        self.value = Vector([1.0, 5, True])
        self.dict = {'A': Compound(), 'B': Compound()}


def groupHLayout(widgets):
    h = QHBoxLayout()
    m = QWidget()
    for w in widgets:
        h.addWidget(w)
    m.setLayout(h)
    yield m


# create test data
data = Data()

# create Qt application
app = QApplication([])
window = QWidget()
main = QVBoxLayout()
window.setLayout(main)

# initialize inspector
factory = AEFactory()
factory.registerType(bool, IconBoolEdit)
factory.registerType(int, SpinBox)
factory.registerType(float, DoubleSpinBox)
factory.registerType(str, LineEdit)
factory.registerWrapper(Vector, groupHLayout)

# inspect the data
for widget in factory.generate(data):
    main.addWidget(widget)

window.show()
app.exec_()

# print the data after closing the editor to show we indeed propagated the changes to the data as they happened
print data.name, data.value, data.dict['A'].x, data.dict['A'].y, data.dict, data.dict['B'].x, data.dict['B'].y

Polygons & textures creeping in my raymarcher

This week I’ve been working on additional features in my 64k toolchain. None of this is yet viable for 64k executables but it enhances the tool quite a bit.

My first step was implementing vertex shader support. A cool thing about vertex shaders in openGL is that they are responsible for outputting the vertex data, nobody said anything about requiring input. So with a function like glDrawArraysInstanced, we have full reign in the vertex shader to generate points based on gl_VertexID and gl_InstanceID.

Here I’m generating a grid of 10×10 quads, added some barycentric coordinates as per This article

#version 420

uniform mat4 uV;
uniform mat4 uVi;
uniform mat4 uP;

out vec3 bary;
out vec2 uv;

void main()
{
    vec3 local = vec3(gl_VertexID % 2, gl_VertexID / 2, 0.5) - 0.5;
    vec3 global = vec3(gl_InstanceID % 10, gl_InstanceID / 10, 4.5) - 4.5;

    uv = (local + global).xy * vec2(0.1, 0.1 * 16 / 9) + 0.5;

    bary = vec3(0);
    bary[gl_VertexID % 3] = 1.0;

    gl_Position = uP * vec4(mat3(uVi) * ((local + global - uV[3].xyz) * vec3(1,1,-1)), 1);
}

This was surprisingly easy to implement. In the tool I scan a template definition XML to figure out which shader source files to stitch together and treat as 1 fragment shader. Adding the distinction between .frag and .vert files allowed me to compile the resulting program with a different vertex shader than the default one and it was up and running quite fast.

Next came a more interesting bit, mixing my raymarching things together with this polygonal grid.
There are 2 bits to this, one is matching the projection, two is depth testing, and thus matching the depth output from the raymarcher.

To project a vertex I subtract the ray origin from the vertex and then multiply it by the inverse rotation. Apparantly that flips the Z axis so I had to fix that too. Then I multiply that with the projection matrix. the “u” prefix means uniform variable.

vec4 viewCoord = vec4(uViewInverse * ((vertex - uRayOrigin) * vec3(1,1-1)), 1)

My ray direction is based on mixing the corners of a frustum these days, I used to rotate the ray to get a fisheye effect but that doesn’t fly with regular projection matrices. My frustum calculation looks something like this (before going into the shader as a mat4):

tanFov = tan(uniforms.get('uFovBias', 0.5))
horizontalFov = (tanFov * aspectRatio)
uniforms['uFrustum'] = (-horizontalFov, -tanFov, 1.0, 0.0,
                        horizontalFov, -tanFov, 1.0, 0.0,
                        -horizontalFov, tanFov, 1.0, 0.0,
                        horizontalFov, tanFov, 1.0, 0.0)

So I can get a projection matrix from that as well. Additionally I added a uniform for the clipRange so the raymarcher near/far planes match the polygonal ones.

uniforms['uClipRange'] = (0.01, 100.0)
near, far = uniforms['uClipRange']
projection = Mat44.frustum(-xfov * near, xfov * near, -tfov * near, tfov * near, near, far)

For reference my raymarching ray looks like this:

vec4 d = mix(mix(uFrustum[0], uFrustum[1], uv.x), mix(uFrustum[2], uFrustum[3],uv.x), uv.y);
Ray ray = Ray(uV[3].xyz, normalize(d.xyz * mat3(uV)));

With this raymarching a 10x10x0.01 box matches up perfectly with the polygonal plane on top! Then the next issue is depth testing. All my render targets are now equipped with a float32 depth buffer, depth testing is enabled and before every frame I clear all depth buffers. Now I find my grid on top of my test scene because the raymarcher does not yet write the depth.

Following this nice article I learned a laot about this topic.
So to get the distance along Z I first define the world-space view axis (0,0,-1). Dotting that with the (intersection – rayOrigin), which is the same as totalDistance * raydirection, yield the right eye-space Z distance. The rest is explained in the article. It is pretty straight forward to map the Z using the clipping planes previously defined to match gl_DepthRange. I first fit between a 01 range (ndcDepth) and then fit back to gl_depthRange. One final trick is to fade to the FAR depth if we have 100% fog.

    vec3 viewForward = vec3(0.0, 0.0, -1.0) * mat3(uV);
    float eyeHitZ = hit.totalDistance * dot(ray.direction, viewForward);
    float ndcDepth = ((uClipRange.y + uClipRange.x) + (2 * uClipRange.y * uClipRange.x) / eyeHitZ) / (uClipRange.y - uClipRange.x);
    float z = ((gl_DepthRange.diff * ndcDepth) + gl_DepthRange.near + gl_DepthRange.far) / 2.0;
    gl_FragDepth = mix(z, gl_DepthRange.far, step(0.999, outColor0.w));

Now as if that wasn’t enough cool stuff, I added the option to bind an image file to a shot. Whenever a shot gets drawn it’s texture list is queried, uploaded and bound to the user defined uniform names. Uploading is cached so every texture is loaded only once, I should probably add file watchers… The cool thing here is that not only can I now texture things, I can also enter storyboards and time them before working on actual 3D scenes!