Пишем программу 3D-моделирования в 500 строках кода

Введение

Люди от природы креативны. Мы постоянно проектируем и создаём новые, полезные и интересные вещи. Сегодня мы пишем ПО, помогающее процессу проектирования и творчества. Программы САПР (Computer-aided design, CAD) позволяют творцам проектировать здания, мосты, графику видеоигр, чудовищ для фильмов, объектов для 3D-печати и множество других вещей перед созданием физической версии проекта.

По своей сути, инструменты CAD являются способом абстрагирования трёхмерного проекта в нечто, что можно просматривать и редактировать на двухмерном экране. Чтобы справляться со своей задачей, инструменты CAD должны обеспечивать три основных элемента функциональности. Во-первых, они должны иметь структуру данных, описывающую проектируемый объект: это то, как компьютер понимает создаваемый пользователем трёхмерный мир. Во-вторых, инструмент CAD должен обеспечивать отображение проекта на экране пользователя. Пользователь проектирует физический объект с тремя измерениями, но экран компьютера имеет всего два измерения. Инструмент CAD должен моделировать способ восприятия нами объектов и отрисовывать их на экране так, чтобы пользователь смог понять все три измерения объекта. В-третьих, CAD должен предоставлять возможность взаимодействия с проектируемым объектом. Пользователь должен быть способен дополнять или модифицировать проект, чтобы создать нужный результат. Кроме того, все инструменты должны иметь возможность сохранения и загрузки проектов с диска, чтобы пользователи могли сотрудничать, обмениваться своей работой и сохранять её.

Специализированные инструменты CAD предоставляют множество дополнительных функций, соответствующих требованиям своей области. Например, в архитектурном CAD есть симуляции физики для тестирования климатических нагрузок на здание, в программе для 3D-печати будут присутствовать функции, проверяющие возможность печати объекта, а пакет для создания кинематографических спецэффектов содержит функции точной симуляции пирокинетики.

Однако во всех инструментах CAD должны присутствовать по крайней мере три описанных выше элемента: структура данных, описывающая проект, возможность отображения на экране и способ взаимодействия с проектом.

Давайте теперь узнаем, как можно описать 3D-проект, отобразить его на экране и взаимодействовать с ним всего в 500 строках на Python.

Рендеринг как ориентир

Движущей силой многих архитектурных решений 3D-редактора является процесс рендеринга. Нам нужна возможность хранения и рендеринга в проекте сложных объектов, но в то же время мы хотим обеспечить низкую сложность кода рендеринга. Давайте изучим процесс рендеринга и исследуем структуру данных для проекта, позволяющую нам хранить и отрисовывать произвольные сложные объекты при помощи простой логики рендеринга.

Управление интерфейсами и основным циклом

Прежде чем мы приступим к рендерингу, нам нужно подготовить некоторые аспекты. Во-первых, нам требуется создать окно для отображения проекта. Во-вторых, мы хотим обмениваться данными с графическими драйверами для рендеринга на экране. Мы бы не хотели обмениваться данными напрямую, поэтому для управления окном воспользуемся кроссплатформенным слоем абстракции под названием OpenGL и библиотекой под названием GLUT (OpenGL Utility Toolkit).

Примечание о OpenGL

OpenGL — это интерфейс программирования графических приложений (API) для кроссплатформенной разработки. Это стандартный API для разработки графических приложений для множества платформ. OpenGL имеет два основных варианта: Legacy OpenGL и Modern OpenGL.

Рендеринг в OpenGL основан на полигонах, задаваемых вершинами и нормалями. Например, для рендеринга одной стороны куба мы задаём 4 вершины и нормаль к стороне.

Legacy OpenGL имеет конвейер с фиксированными функциями (fixed function pipeline). Задавая глобальные переменные, программист может включать и отключать автоматизированные реализации таких функций, как освещение, раскраска, усечение граней и т.д. После чего OpenGL автоматически рендерит сцену со включенной функциональностью. Такая система является устаревшей.

В Modern OpenGL используется программируемый конвейер рендеринга (programmable rendering pipeline), при котором программист пишет небольшие программы, называемые «шейдерами»; они выполняются на специализированном графическом оборудовании (GPU). Программируемый конвейер Modern OpenGL заменил устаревший Legacy OpenGL.

В своём проекте мы будем использовать Legacy OpenGL. Фиксированная функциональность, предоставляемая Legacy OpenGL, очень полезна для обеспечения небольшого размера кода. Она уменьшает количество необходимых знаний линейной алгебры и упрощает наш код.

Что такое GLUT

Библиотека GLUT из комплекта OpenGL позволяет нам создавать окна операционной системы и регистрировать функции обратного вызова интерфейса пользователя. Этой базовой функциональности достаточно для наших целей. Если бы нам была нужна более функциональная библиотека для управления окнами и взаимодействия с пользователем, то мы бы задумались об использовании полноценного тулкита наподобие GTK или Qt.

Средство просмотра

Для управления параметрами GLUT и OpenGL, а также остальной частью программы моделирования мы создадим класс под названием Viewer. Мы будем использовать единственный экземпляр Viewer, управляющий созданием и рендерингом окон, содержащий основной цикл нашей программы. Внутри процесса инициализации Viewer мы создадим окно GUI и инициализируем OpenGL.

Функция init_interface создаёт окно, в которое будет рендериться редактор, и задаёт функцию, котороая должна вызываться для рендеринга проекта. Функция init_opengl задаёт нужное для программы состояние OpenGL. Она задаёт матрицы, включает отсечение задних граней, регистрирует источник света для освещения сцены и сообщает OpenGL, что объекты нужно раскрашивать. Функция init_scene создаёт объекты Scene и располагает начальные узлы, чтобы пользователь мог начать работу. Чуть ниже мы узнаем больше о структуре данных Scene. Наконец, init_interaction регистрирует обратные вызовы функций для взаимодействия с пользователем, что мы обсудим позже.

После инициализации Viewer мы вызываем glutMainLoop, чтобы перенести исполнение программы в GLUT. Эта функция никогда не выполняет возврат. Обратные вызовы функций, зарегистрированные нами для событий GLUT, будут вызываться при выполнении этих событий.

class Viewer(object):
    def __init__(self):
        """ Initialize the viewer. """
        self.init_interface()
        self.init_opengl()
        self.init_scene()
        self.init_interaction()
        init_primitives()

    def init_interface(self):
        """ initialize the window and register the render function """
        glutInit()
        glutInitWindowSize(640, 480)
        glutCreateWindow("3D Modeller")
        glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB)
        glutDisplayFunc(self.render)

    def init_opengl(self):
        """ initialize the opengl settings to render the scene """
        self.inverseModelView = numpy.identity(4)
        self.modelView = numpy.identity(4)

        glEnable(GL_CULL_FACE)
        glCullFace(GL_BACK)
        glEnable(GL_DEPTH_TEST)
        glDepthFunc(GL_LESS)

        glEnable(GL_LIGHT0)
        glLightfv(GL_LIGHT0, GL_POSITION, GLfloat_4(0, 0, 1, 0))
        glLightfv(GL_LIGHT0, GL_SPOT_DIRECTION, GLfloat_3(0, 0, -1))

        glColorMaterial(GL_FRONT_AND_BACK, GL_AMBIENT_AND_DIFFUSE)
        glEnable(GL_COLOR_MATERIAL)
        glClearColor(0.4, 0.4, 0.4, 0.0)

    def init_scene(self):
        """ initialize the scene object and initial scene """
        self.scene = Scene()
        self.create_sample_scene()

    def create_sample_scene(self):
        cube_node = Cube()
        cube_node.translate(2, 0, 2)
        cube_node.color_index = 2
        self.scene.add_node(cube_node)

        sphere_node = Sphere()
        sphere_node.translate(-2, 0, 2)
        sphere_node.color_index = 3
        self.scene.add_node(sphere_node)

        hierarchical_node = SnowFigure()
        hierarchical_node.translate(-2, 0, -2)
        self.scene.add_node(hierarchical_node)

    def init_interaction(self):
        """ init user interaction and callbacks """
        self.interaction = Interaction()
        self.interaction.register_callback('pick', self.pick)
        self.interaction.register_callback('move', self.move)
        self.interaction.register_callback('place', self.place)
        self.interaction.register_callback('rotate_color', self.rotate_color)
        self.interaction.register_callback('scale', self.scale)

    def main_loop(self):
        glutMainLoop()

if __name__ == "__main__":
    viewer = Viewer()
    viewer.main_loop()

Прежде чем разбирать функцию render, мы должны немного поговорить о линейной алгебре.

Координатное пространство

В нашем случае координатное пространство будет представлять собой точку начала координат и набор из трёх базисных векторов, обычно обозначаемых как оси $$, $$ и $$.

Точка

Любую точку в трёх измерениях можно представить как смещение в направлениях $$, $$ и $$ относительно точки начала координат. Описание точки задаётся относительно координатного пространства, в котором находится точка. Одна и та же точка имеет различные описания в разных координатных пространствах. Любая точка в трёх измерениях может быть представлена в любом трёхмерном координатном пространстве.

Вектор

Вектор — это значение из $$, $$ и $$, определяющее разницу между двумя точками по осям $$, $$ и $$.

Матрица преобразований

В компьютерной графике удобно использовать несколько разных координатных пространств для разных типов точек. Матрицы преобразований преобразуют точки из одного координатного пространства в другое. Чтобы преобразовать вектор $$ из одного координатного пространства в другое, мы выполняем умножение на матрицу преобразований $$: $$. Примерами распространённых матриц преобразования являются перемещение, масштабирование и поворот.

Координатные пространства модели, мира, окна просмотра и проецирования

Рисунок 1 — Конвейер преобразований

Для отрисовки на экране элемента нам нужно выполнить преобразование между несколькими координатными пространствами.

Все преобразования, показанные в правой части Рисунка 1, в том числе все преобразования из пространства камеры (Eye Space) в пространство окна просмотра (Viewport Space) будет выполнять за нас OpenGL.

Преобразование из пространства камеры в однородное пространство усечения (clip space) выполняется функцией gluPerspective, а преобразование в нормализованное пространство устройства и пространство окна обзора — функцией glViewport. Эти матрицы перемножаются и хранятся как матрица GL_PROJECTION. Для нашего проекта не обязательно знать терминологию или подробности работы этих матриц.

Однако нам самостоятельно придётся заняться левой частью схемы. Мы задаём матрицу, преобразующую точки модели (также называемой мешем) из пространств моделей в мировое пространство, это называется матрицей модели. Также мы задаём матрицу обзора, выполняющую преобразование из мирового пространства в пространство камеры. В этом проекте мы скомбинируем эти две матрицы, чтобы получить матрицу ModelView.

Чтобы узнать больше о полном конвейере рендеринга графики и используемых координатных пространствах, прочитайте главу 2 книги Real Time Rendering или другую книгу о компьютерной графике для начинающих.

Рендеринг при помощи Viewer

Функция render начинается с подготовки любого состояния OpenGL, что необходимо выполнять во время рендеринга. Она инициализирует матрицу проецирования при помощи init_view и использует данные из функции взаимодействия с пользователем для инициализации матрицы ModelView с матрицей преобразований, выполняющей переход из пространства сцены в мировое пространство. Подробнее о классе Interaction будет написано ниже. Она очищает экран при помощи glClear, приказывает сцене отрендериться, а затем рисует сетку единичных квадратов.

Перед рендерингом сетки мы отключаем освещение OpenGL. При отключении освещения OpenGL рендерит объекты сплошным цветом, а не симулирует источники освещения. Благодаря этому сетка визуально отличается от сцены. Далее glFlush подаёт сигнал графическому драйверу, что мы готовы к очистке буфера и отображению на экран.

    # class Viewer
    def render(self):
        """ The render pass for the scene """
        self.init_view()

        glEnable(GL_LIGHTING)
        glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT)

        # Load the modelview matrix from the current state of the trackball
        glMatrixMode(GL_MODELVIEW)
        glPushMatrix()
        glLoadIdentity()
        loc = self.interaction.translation
        glTranslated(loc[0], loc[1], loc[2])
        glMultMatrixf(self.interaction.trackball.matrix)

        # store the inverse of the current modelview.
        currentModelView = numpy.array(glGetFloatv(GL_MODELVIEW_MATRIX))
        self.modelView = numpy.transpose(currentModelView)
        self.inverseModelView = inv(numpy.transpose(currentModelView))

        # render the scene. This will call the render function for each object
        # in the scene
        self.scene.render()

        # draw the grid
        glDisable(GL_LIGHTING)
        glCallList(G_OBJ_PLANE)
        glPopMatrix()

        # flush the buffers so that the scene can be drawn
        glFlush()

    def init_view(self):
        """ initialize the projection matrix """
        xSize, ySize = glutGet(GLUT_WINDOW_WIDTH), glutGet(GLUT_WINDOW_HEIGHT)
        aspect_ratio = float(xSize) / float(ySize)

        # load the projection matrix. Always the same
        glMatrixMode(GL_PROJECTION)
        glLoadIdentity()

        glViewport(0, 0, xSize, ySize)
        gluPerspective(70, aspect_ratio, 0.1, 1000.0)
        glTranslated(0, 0, -15)

Что рендерить: сцена

После того, как мы инициализировали конвейер рендеринга для выполнения отрисовки в координатном пространстве мира, что мы будем рендерить? Вспомним, что наша цель — создание проекта, состоящего из 3D-моделей. Нам нужна структура данных для хранения этого проекта. а также структура данных для его рендеринга. Обратите внимание на вызов self.scene.render() в цикле рендеринга viewer. Что такое scene?

Класс Scene — это интерфейс со структурой данных, которую мы используем для описания проекта. Он абстрагирует подробности структуры данных и предоставляет функции интерфейса, необходимые для взаимодействия с проектом, в том числе функции для рендеринга, добавления элементов и манипулирования элементами. Существует один объект Scene, которым владеет viewer. Экземпляр Scene хранит список всех элементов сцены, называемый node_list. Также он отслеживает выбранный элемент. Функция render сцены просто вызывает render для каждого пункта списка node_list.

class Scene(object):

    # the default depth from the camera to place an object at
    PLACE_DEPTH = 15.0

    def __init__(self):
        # The scene keeps a list of nodes that are displayed
        self.node_list = list()
        # Keep track of the currently selected node.
        # Actions may depend on whether or not something is selected
        self.selected_node = None

    def add_node(self, node):
        """ Add a new node to the scene """
        self.node_list.append(node)

    def render(self):
        """ Render the scene. """
        for node in self.node_list:
            node.render()

Узлы

В функции render класса Scene мы вызываем render для каждого элемента node_list класса Scene. Но что за элементы находятся в этом списке? Мы называем их узлами. Узел может быть всем, что можно поместить в сцену. В объектно-ориентированном ПО мы пишем Node как абстрактный базовый класс. Любые классы, представляющие объекты, размещаемые в Scene, будут наследовать от Node. Этот базовый класс позволяет нам рассуждать о сцене абстрактно. Остальная часть кодовой базы не обязана знать подробностей об отображаемом ею объекте; ей достаточно знать, что они принадлежат к классу Node.

Каждый тип Node определяет собственное поведение для рендеринга самого себя и для любых других взаимодействий. Node отслеживает важные данные о самом себе: матрицу преобразований, матрицу масштабирования, цвет, и т.п. При умножении матрицы преобразований узла на его матрицу масштабирования, мы получаем матрицу преобразований из координатного пространства модели узла в координатное пространство мира. Кроме того, узел также хранит в себе параллельный осям ограничивающий параллелепипед (axis-aligned bounding box, AABB). Подробнее об AABB мы поговорим ниже.

Простейшей конкретной реализацией Node является примитив. Примитив — это единая фигура, которую можно добавить в сцену. В нашей программе примитивами будут куб (Cube) и сфера (Sphere).

class Node(object):
    """ Base class for scene elements """
    def __init__(self):
        self.color_index = random.randint(color.MIN_COLOR, color.MAX_COLOR)
        self.aabb = AABB([0.0, 0.0, 0.0], [0.5, 0.5, 0.5])
        self.translation_matrix = numpy.identity(4)
        self.scaling_matrix = numpy.identity(4)
        self.selected = False

    def render(self):
        """ renders the item to the screen """
        glPushMatrix()
        glMultMatrixf(numpy.transpose(self.translation_matrix))
        glMultMatrixf(self.scaling_matrix)
        cur_color = color.COLORS[self.color_index]
        glColor3f(cur_color[0], cur_color[1], cur_color[2])
        if self.selected:  # emit light if the node is selected
            glMaterialfv(GL_FRONT, GL_EMISSION, [0.3, 0.3, 0.3])

        self.render_self()

        if self.selected:
            glMaterialfv(GL_FRONT, GL_EMISSION, [0.0, 0.0, 0.0])
        glPopMatrix()

    def render_self(self):
        raise NotImplementedError(
            "The Abstract Node Class doesn't define 'render_self'")

class Primitive(Node):
    def __init__(self):
        super(Primitive, self).__init__()
        self.call_list = None

    def render_self(self):
        glCallList(self.call_list)


class Sphere(Primitive):
    """ Sphere primitive """
    def __init__(self):
        super(Sphere, self).__init__()
        self.call_list = G_OBJ_SPHERE


class Cube(Primitive):
    """ Cube primitive """
    def __init__(self):
        super(Cube, self).__init__()
        self.call_list = G_OBJ_CUBE

Рендеринг узлов основан на матрицах преобразований, хранящихся в каждом из узлов. Матрица преобразований узла — это сочетание его матрицы масштабирования и матрицы перемещения. Вне зависимости от типа узла, первым этапом рендеринга является задание матрице ModelView интерфейса OpenGL матрицы преобразований, чтобы выполнить переход от координатного пространства модели к координатному пространству окна просмотра. После обновления матриц OpenGL мы вызываем render_self, чтобы приказать узлу выполнить необходимые вызовы OpenGL для отрисовки себя. Затем мы отменяем все изменения, внесённые в состояние OpenGL этого конкретного узла. Мы используем функции OpenGL glPushMatrix и glPopMatrix для сохранения и восстановления состояния матрицы ModelView до и после рендеринга узла. Обратите внимание, что узел хранит свой цвет, расположение и масштаб, применяя их к состоянию OpenGL перед рендерингом.

Если узел в данный момент выделен, мы заставим его излучать свет. Благодаря этому пользователь будет видеть, какой узел выбран.

Для рендеринга примитивов мы используем функцию OpenGL списков вызовов. Список вызовов OpenGL — это набор вызовов OpenGL, заданных и объединённых под одним названием. Вызовы могут выполняться с помощью glCallList(LIST_NAME). Каждый примитив (Sphere и Cube) определяет список вызовов, необходимый для его рендеринга (не показан).

Например, список вызовов куба отрисовывает 6 граней куба с центром в точке начала координат и с рёбрами длиной ровно 1 единицу.

# Pseudocode Cube definition
# Left face
((-0.5, -0.5, -0.5), (-0.5, -0.5, 0.5), (-0.5, 0.5, 0.5), (-0.5, 0.5, -0.5)),
# Back face
((-0.5, -0.5, -0.5), (-0.5, 0.5, -0.5), (0.5, 0.5, -0.5), (0.5, -0.5, -0.5)),
# Right face
((0.5, -0.5, -0.5), (0.5, 0.5, -0.5), (0.5, 0.5, 0.5), (0.5, -0.5, 0.5)),
# Front face
((-0.5, -0.5, 0.5), (0.5, -0.5, 0.5), (0.5, 0.5, 0.5), (-0.5, 0.5, 0.5)),
# Bottom face
((-0.5, -0.5, 0.5), (-0.5, -0.5, -0.5), (0.5, -0.5, -0.5), (0.5, -0.5, 0.5)),
# Top face
((-0.5, 0.5, -0.5), (-0.5, 0.5, 0.5), (0.5, 0.5, 0.5), (0.5, 0.5, -0.5))

Использование исключительно примитивов сильно ограничивает возможности моделирования. 3D-модели обычно состоят из множества примитивов (или треугольных мешей, которые мы здесь рассматривать не будем). К счастью, структура класса Node упрощает создание узлов Scene, составленных из множественных примитивов. На самом деле, мы можем обеспечить поддержку произвольной группировки узлов без повышения сложности кода.

В качестве источника мотивации представим очень простую фигуру: обычного снеговика, составленного из трёх сфер. Даже несмотря на то, что фигура состоит из трёх отдельных примитивов, мы хотели бы иметь возможность работать с ней как с единым объектом.

Мы создадим класс HierarchicalNode, то есть Node, содержащий другие узлы. Он управляет списком «дочерних узлов». Функция render_self для иерархических узлов просто вызывает render_self для каждого из дочерних узлов. При помощи класса HierarchicalNode очень легко добавлять в сцену фигуры. Теперь для задания снеговика достаточно указать составляющие его фигуры, а также их относительные позиции и размеры.


Рисунок 2 — Иерархия подклассов Node

class HierarchicalNode(Node):
    def __init__(self):
        super(HierarchicalNode, self).__init__()
        self.child_nodes = []

    def render_self(self):
        for child in self.child_nodes:
            child.render()

class SnowFigure(HierarchicalNode):
    def __init__(self):
        super(SnowFigure, self).__init__()
        self.child_nodes = [Sphere(), Sphere(), Sphere()]
        self.child_nodes[0].translate(0, -0.6, 0) # scale 1.0
        self.child_nodes[1].translate(0, 0.1, 0)
        self.child_nodes[1].scaling_matrix = numpy.dot(
            self.scaling_matrix, scaling([0.8, 0.8, 0.8]))
        self.child_nodes[2].translate(0, 0.75, 0)
        self.child_nodes[2].scaling_matrix = numpy.dot(
            self.scaling_matrix, scaling([0.7, 0.7, 0.7]))
        for child_node in self.child_nodes:
            child_node.color_index = color.MIN_COLOR
        self.aabb = AABB([0.0, 0.0, 0.0], [0.5, 1.1, 0.5])

Вы могли заметить, что объекты Node образуют древовидную структуру данных. Функция render, проходящая иерархические узлы, выполняет обход в глубину по дереву. При обходе она хранит стек матриц ModelView, используемых для преобразования в мировое пространство. На каждом шаге она записывает в стек текущую матрицу ModelView, а когда завершает рендеринг всех дочерних узлов, она извлекает матрицу из стека, оставляя на вершине стека матрицу ModelView родительского узла.

Благодаря тому, что мы сделали класс Node расширяемым, можно добавлять в сцену новые типы фигур, не меняя весь остальной код манипуляций сценой и рендеринга. Благодаря концепции узлов мы абстрагируемся от того факта, что объект Scene может иметь множество дочерних элементов. Это называется шаблоном проектирования «Компоновщик».

Взаимодействие с пользователем

Теперь, когда наша программа моделирования способна хранить и отображать сцену, нам нужен способ взаимодействия с ней. Нам нужно упростить два вида взаимодействий. Во-первых, нам нужна возможность изменения перспективы обзора сцены. Мы хотим иметь возможность двигать глаз (камеру) по сцене. Во-вторых, нам нужна возможность добавления новых узлов и изменения узлов в сцене.

Для реализации взаимодействия с пользователем нам нужно знать, когда пользователь нажимает клавиши или двигает мышь. К счастью, операционная система знает, когда происходят эти события. GLUT позволяет нам регистрировать функцию, которая будет вызываться при совершении определённого события. Мы напишем функции для интерпретирования нажатий клавиш и движения мыши, а затем прикажем GLUT вызывать эти функции при нажатии соответствующих клавиш. Узнав, какие клавиши нажимает пользователь, мы должны будем интерпретировать ввод и применить к сцене соответствующие действия.

Логика прослушивания событий операционной системы и интерпретации их значения находится в классе Interaction. Написанный нами ранее класс Viewer владеет единственным экземпляром Interaction. Мы используем механизм функций обратного вызова GLUT для регистрации функций, вызываемых при нажатии клавиши мыши (glutMouseFunc), при перемещении мыши (glutMotionFunc), при нажатии клавиши клавиатуры (glutKeyboardFunc) и при нажатии клавиш со стрелками (glutSpecialFunc). Чуть ниже вы увидите функции, обрабатывающие события ввода.

class Interaction(object):
    def __init__(self):
        """ Handles user interaction """
        # currently pressed mouse button
        self.pressed = None
        # the current location of the camera
        self.translation = [0, 0, 0, 0]
        # the trackball to calculate rotation
        self.trackball = trackball.Trackball(theta = -25, distance=15)
        # the current mouse location
        self.mouse_loc = None
        # Unsophisticated callback mechanism
        self.callbacks = defaultdict(list)

        self.register()

    def register(self):
        """ register callbacks with glut """
        glutMouseFunc(self.handle_mouse_button)
        glutMotionFunc(self.handle_mouse_move)
        glutKeyboardFunc(self.handle_keystroke)
        glutSpecialFunc(self.handle_keystroke)

Функции обратного вызова операционной системы

Для осмысленного интерпретирования пользовательского ввода нам нужно скомбинировать знание о позиции мыши, клавишах мыши и клавиатуре. Поскольку для интерпретирования ввода в осмысленные действия требуется много строк кода, мы инкапсулируем его в отдельный класс, отдалённый от основного пути исполнения кода. Класс Interaction скрывает ненужную сложность от остальной части кодовой базы и преобразует события операционной системы в события уровня приложения.

    # class Interaction 
    def translate(self, x, y, z):
        """ translate the camera """
        self.translation[0] += x
        self.translation[1] += y
        self.translation[2] += z

    def handle_mouse_button(self, button, mode, x, y):
        """ Called when the mouse button is pressed or released """
        xSize, ySize = glutGet(GLUT_WINDOW_WIDTH), glutGet(GLUT_WINDOW_HEIGHT)
        y = ySize - y  # invert the y coordinate because OpenGL is inverted
        self.mouse_loc = (x, y)

        if mode == GLUT_DOWN:
            self.pressed = button
            if button == GLUT_RIGHT_BUTTON:
                pass
            elif button == GLUT_LEFT_BUTTON:  # pick
                self.trigger('pick', x, y)
            elif button == 3:  # scroll up
                self.translate(0, 0, 1.0)
            elif button == 4:  # scroll up
                self.translate(0, 0, -1.0)
        else:  # mouse button release
            self.pressed = None
        glutPostRedisplay()

    def handle_mouse_move(self, x, screen_y):
        """ Called when the mouse is moved """
        xSize, ySize = glutGet(GLUT_WINDOW_WIDTH), glutGet(GLUT_WINDOW_HEIGHT)
        y = ySize - screen_y  # invert the y coordinate because OpenGL is inverted
        if self.pressed is not None:
            dx = x - self.mouse_loc[0]
            dy = y - self.mouse_loc[1]
            if self.pressed == GLUT_RIGHT_BUTTON and self.trackball is not None:
                # ignore the updated camera loc because we want to always
                # rotate around the origin
                self.trackball.drag_to(self.mouse_loc[0], self.mouse_loc[1], dx, dy)
            elif self.pressed == GLUT_LEFT_BUTTON:
                self.trigger('move', x, y)
            elif self.pressed == GLUT_MIDDLE_BUTTON:
                self.translate(dx/60.0, dy/60.0, 0)
            else:
                pass
            glutPostRedisplay()
        self.mouse_loc = (x, y)

    def handle_keystroke(self, key, x, screen_y):
        """ Called on keyboard input from the user """
        xSize, ySize = glutGet(GLUT_WINDOW_WIDTH), glutGet(GLUT_WINDOW_HEIGHT)
        y = ySize - screen_y
        if key == 's':
            self.trigger('place', 'sphere', x, y)
        elif key == 'c':
            self.trigger('place', 'cube', x, y)
        elif key == GLUT_KEY_UP:
            self.trigger('scale', up=True)
        elif key == GLUT_KEY_DOWN:
            self.trigger('scale', up=False)
        elif key == GLUT_KEY_LEFT:
            self.trigger('rotate_color', forward=True)
        elif key == GLUT_KEY_RIGHT:
            self.trigger('rotate_color', forward=False)
        glutPostRedisplay()

Внутренние функции обратного вызова

В показанном выше фрагменте кода можно заметить, что когда экземпляр Interaction интерпретирует действие пользователя, он вызывает self.trigger со строкой, описывающей тип действия. Функция trigger в классе Interaction — это часть простой системы обратных вызовов, которую мы будем использовать для обработки событий на уровне приложения. Вспомним, что функция init_interaction в классе Viewer регистрирует обратные вызовы в экземпляре Interaction, вызывая register_callback.

    # class Interaction
    def register_callback(self, name, func):
        self.callbacks[name].append(func)

Когда коду интерфейса пользователя нужно запустить событие в сцене, класс Interaction вызывает все сохранённые обратные вызовы, имеющиеся для этого события:

    # class Interaction
    def trigger(self, name, *args, **kwargs):
        for func in self.callbacks[name]:
            func(*args, **kwargs)

Эта система обратных вызовов уровня приложения абстрагирует необходимость остальной части системы знать о вводе в операционной системе. Каждый обратный вызов уровня приложения представляет собой значимый запрос в рамках приложения. Класс Interaction используется как переводчик между событиями операционной системы и событиями уровня приложения. Это означает, что если бы мы решили портировать программу моделирования на другой тулкит, нам бы достаточно было заменить класс Interaction на класс, преобразующий ввод из нового тулкита в тот же набор значимых обратных вызовов уровня приложения. Мы используем обратные вызовы и аргументы в Таблице 1.


Эта простая система обратных вызовов обеспечивает всю функциональность, необходимую для нашей программы. Однако в готовом 3D-редакторе объекты интерфейса пользователя часто создаются и уничтожаются динамически. В таком случае нам потребовалась бы более сложная система прослушивания событий, в которой объекты могут и регистрировать и отменять регистрацию обратных вызовов для событий.

Взаимодействие со сценой

Благодаря механизму обратных вызовов мы можем получать значимую информацию о событиях пользовательского ввода от класса Interaction. Мы готовы к применению этих действий к Scene.

Перемещение сцены

В этой программе мы выполняем движение камеры преобразованием сцены. Другими словами, камера находится на одном месте, а пользовательский ввод двигает сцену, а не камеру. Камера расположена в точке [0, 0, -15] и направлена на точку начала координат мира. (Или же мы можем изменить матрицу перспективы так, чтобы она двигала камеру вместо сцены. Это архитектурное решение очень слабо повлияет на остальную часть программы.) Вернувшись к функции render в Viewer, мы видим, что состояние Interaction используется для преобразования состояния матрицы OpenGL перед рендерингом Scene. Существует два типа взаимодействия со сценой: поворот и перемещение.

Поворот сцены с помощью трекбола

Мы реализуем поворот сцены с помощью алгоритма trackball. Трекбол — это интуитивно-понятный интерфейс для манипуляций со сценой в трёх измерениях. Интерфейс трекбола работает так, как будто сцена находится внутри прозрачного шара. Если положить руку на поверхность шара и толкнуть его, шар повернётся. Аналогично, при зажимании правой клавиши мыши и перемещении курсора по экрану вращает сцену. Подробнее о теории трекбола можно прочитать в OpenGL Wiki. В нашей программе мы используем реализацию трекбола, являющуюся частью Glumpy.

Мы взаимодействуем с трекболом с помощью функции drag_to: текущее положение мыши является начальной точкой, а изменение положения мыши — параметрами функции.

self.trackball.drag_to(self.mouse_loc[0], self.mouse_loc[1], dx, dy)

Получившаяся матрица поворота — это trackball.matrix в окне просмотра при рендеринге сцены.

Примечание: кватернионы

Традиционно повороты описываются одним из двух способов. Первый — это значения поворота вокруг каждой из осей; можно хранить их как кортеж из трёх членов, представляющих собой числа с плавающей запятой. Другим распространённым способом задания поворотов является кватернион — элемент, состоящий из вектора с координатами $$, $$ и $$, а также поворота $$. Использование кватернионов имеет множество преимуществ по сравнению с поворотом по осям; в частности, они более стабильны численно. Благодаря использованию кватернионов можно избежать таких проблем, как «шарнирный замок» (gimbal lock). Недостаток кватернионов в том, что они менее интуитивно-понятны в работе. Если вы не боитесь и хотите узнать больше о кватернионах, то можете изучить это объяснение.

Реализация трекбола избегает gimbal lock благодаря хранению поворота сцены при помощи кватернионов. К счастью, нам не нужно работать с кватернионами напрямую, потому что матричный член трекбола преобразует поворот в матрицу.

Перемещение сцены

Перемещение сцены (например, сдвиг) гораздо проще, чем её поворот. Перемещения сцены выполняются колесом и левой клавишей мыши. Левая клавиша мыши перемещает сцену по координатам $$ и $$. Прокрутка колеса мыши перемещает сцену по координате $$ (ближе или дальше от камеры). Класс Interaction хранит текущее перемещение сцены и модифицирует его при помощи функции translate. Окно просмотра получает расположение камеры класса Interaction при рендеринге и использует его в вызове glTranslated.

Выбор объектов сцены

Теперь, когда пользователь может перемещать и поворачивать всю сцену для получения нужного обзора, следующим шагом будет обеспечение возможности изменения объектов и манипуляций ими.

Чтобы пользователь мог манипулировать объектами сцены, он должен иметь возможность выбора элементов.

Для выбора элемента мы используем текущую матрицу проецирования для генерации луча, представляющего щелчок мыши, как будто указатель мыши испускает в сцену луч. Выбранным узлом будет ближайший к камере узел, который пересёк луч. Следовательно, задача выбора сводится к задаче нахождения пересечений между лучом и узлами сцены. То есть вопрос заключается в том, как нам узнать, что луч столкнулся с узлом.

Вычисление точного ответа на вопрос, пересёкся ли луч с узлом — это сложная задача, с точки зрения и кода, и производительности. Нам бы потребовалось написать проверку пересечения луча с объектом для каждого типа примитива. Для узлов сцены со сложными геометриями мешей
и множеством граней вычисление точного пересечения луча с объектом потребует проверки луча с каждой гранью, что будет вычислительно затратной задачей.

Для сохранения компактности кода и достаточной производительности мы используем простую и быструю аппроксимацию теста пересечения луча с объектом. В нашей реализации каждый узел хранит параллельный осям ограничивающий параллелепипед (axis-aligned bounding box, AABB), который является аппроксимацией занимаемого узлом пространства. Чтобы проверить, пересекается ли луч с узлом, мы проверим, пересекается ли луч с AABB узла. Такая реализация означает, что все узлы используют один код для тестов пересечения, а вычислительные затраты остаются постоянными и небольшими для всех типов узлов.

    # class Viewer
    def get_ray(self, x, y):
        """ 
        Generate a ray beginning at the near plane, in the direction that
        the x, y coordinates are facing 

        Consumes: x, y coordinates of mouse on screen 
        Return: start, direction of the ray 
        """
        self.init_view()

        glMatrixMode(GL_MODELVIEW)
        glLoadIdentity()

        # get two points on the line.
        start = numpy.array(gluUnProject(x, y, 0.001))
        end = numpy.array(gluUnProject(x, y, 0.999))

        # convert those points into a ray
        direction = end - start
        direction = direction / norm(direction)

        return (start, direction)

    def pick(self, x, y):
        """ Execute pick of an object. Selects an object in the scene. """
        start, direction = self.get_ray(x, y)
        self.scene.pick(start, direction, self.modelView)

Чтобы определить, какой из узлов щёлкнули мышью, мы обходим сцену, проверяя, пересёкся ли луч с каким-нибудь из узлов. Вы снимаем выбор с текущего узла и выбираем узел, который ближе всего пересекается к точке начала луча.

    # class Scene
    def pick(self, start, direction, mat):
        """ 
        Execute selection.
            
        start, direction describe a Ray. 
        mat is the inverse of the current modelview matrix for the scene.
        """
        if self.selected_node is not None:
            self.selected_node.select(False)
            self.selected_node = None

        # Keep track of the closest hit.
        mindist = sys.maxint
        closest_node = None
        for node in self.node_list:
            hit, distance = node.pick(start, direction, mat)
            if hit and distance < mindist:
                mindist, closest_node = distance, node

        # If we hit something, keep track of it.
        if closest_node is not None:
            closest_node.select()
            closest_node.depth = mindist
            closest_node.selected_loc = start + direction * mindist
            self.selected_node = closest_node

В классе Node функция pick проверяет, пересекается ли луч с AABB Node. Если узел выбран, то функция select переключает состояние выбора узла. Обратите внимание, что в качестве третьего параметра функция ray_hit AABB получает матрицу преобразований между координатным пространством параллелепипеда и координатным пространством луча. Перед вызовом функции ray_hit каждый узел вносит собственные преобразования в матрицу.

    # class Node
    def pick(self, start, direction, mat):
        """ 
        Return whether or not the ray hits the object

        Consume:  
        start, direction form the ray to check
        mat is the modelview matrix to transform the ray by 
        """

        # transform the modelview matrix by the current translation
        newmat = numpy.dot(
            numpy.dot(mat, self.translation_matrix), 
            numpy.linalg.inv(self.scaling_matrix)
        )
        results = self.aabb.ray_hit(start, direction, newmat)
        return results

    def select(self, select=None):
       """ Toggles or sets selected state """
       if select is not None:
           self.selected = select
       else:
           self.selected = not self.selected

Схему выбора на основе пересечения луча и AABB очень легко понять и реализовать. Однако в некоторых ситуациях результаты оказываются ошибочными.


Рисунок 3 — Ошибка AABB

Например, в случае примитива Sphere, сама сфера касается AABB только в центре каждой из граней AABB. Однако если пользователь нажмёт на угол AABB сферы, будет обнаружена коллизия со сферой, даже если пользователь хотел нажать на что-то за ней (Рисунок 3).

Такой компромисс между сложностью, производительностью и точностью очень распространён в компьютерной графике и во многих областях проектирования ПО.

Изменение объектов сцены

Далее мы хотим дать пользователю возможность манипуляций с выбранными узлами. Ему может потребоваться перемещать выбранный узел, изменять его размер или цвет. Когда пользователь вводит команду манипуляции с узлом, класс Interaction преобразует ввод в действие, которое намеревался сделать пользователь, и вызывает соответствующую функцию обратного вызова.

Когда Viewer получает обратный вызов для одного из этих событий, он вызывает соответствующую функцию Scene, которая, в свою очередь, применяет преобразование к текущему выбранному Node.

    # class Viewer
    def move(self, x, y):
        """ Execute a move command on the scene. """
        start, direction = self.get_ray(x, y)
        self.scene.move_selected(start, direction, self.inverseModelView)

    def rotate_color(self, forward):
        """ 
        Rotate the color of the selected Node. 
        Boolean 'forward' indicates direction of rotation. 
        """
        self.scene.rotate_selected_color(forward)

    def scale(self, up):
        """ Scale the selected Node. Boolean up indicates scaling larger."""
        self.scene.scale_selected(up)

Смена цвета

Манипуляция цветом выполняется через список возможных цветов. Пользователь может перемещаться по списку клавишами со стрелками. Сцена отдаёт команду смены цвета текущему выбранному узлу.

    # class Scene
    def rotate_selected_color(self, forwards):
        """ Rotate the color of the currently selected node """
        if self.selected_node is None: return
        self.selected_node.rotate_color(forwards)

Каждый цвет хранит свой текущий цвет. Функция rotate_color просто изменяет текущий цвет узла. Цвет передаётся OpenGL с помощью glColor при рендеринге узла.

    # class Node
    def rotate_color(self, forwards):
        self.color_index += 1 if forwards else -1
        if self.color_index > color.MAX_COLOR:
            self.color_index = color.MIN_COLOR
        if self.color_index < color.MIN_COLOR:
            self.color_index = color.MAX_COLOR

Масштабирование узлов

Как и в случае с цветом, сцена отдаёт команды изменения масштаба выбранному узлу, если он есть.

    # class Scene
    def scale_selected(self, up):
        """ Scale the current selection """
        if self.selected_node is None: return
        self.selected_node.scale(up)

Каждый узел хранит текущую матрицу, содержащую его масштаб. Матрица, изменяющая масштаб по параметрам $$, $$ и $$ в соответствующих направлениях, имеет вид:

$$

Когда пользователь изменяет масштаб узла, получившаяся матрица масштабирования умножается на текущую матрицу масштабирования узла.

    # class Node
    def scale(self, up):
        s =  1.1 if up else 0.9
        self.scaling_matrix = numpy.dot(self.scaling_matrix, scaling([s, s, s]))
        self.aabb.scale(s)

Функция scaling возвращает матрицу, соответствующую коэффициентам масштабирования $$, $$ и $$.

def scaling(scale):
    s = numpy.identity(4)
    s[0, 0] = scale[0]
    s[1, 1] = scale[1]
    s[2, 2] = scale[2]
    s[3, 3] = 1
    return s

Перемещение узлов

Для перемещения узла мы используем то же вычисление луча, что и для выбора. Мы передаём луч, представляющий текущую позицию мыши, в функцию move сцены. Новое местоположение узла должно находится на луче. Чтобы определить, куда луч должен поместить узел, нам нужно знать, расстояние узла от камеры. Так как мы сохранили местоположение узла и расстояние до камеры при его выборе (в функции pick), можно использовать здесь эти данные. Мы находим точку, находящуюся на том же расстоянии от камеры вдоль луча и вычисляем разность векторов между новым и старым местоположением. Затем мы перемещаем узел на получившийся вектор.

    # class Scene
    def move_selected(self, start, direction, inv_modelview):
        """ 
        Move the selected node, if there is one.
            
        Consume: 
        start, direction describes the Ray to move to
        mat is the modelview matrix for the scene 
        """
        if self.selected_node is None: return

        # Find the current depth and location of the selected node
        node = self.selected_node
        depth = node.depth
        oldloc = node.selected_loc

        # The new location of the node is the same depth along the new ray
        newloc = (start + direction * depth)

        # transform the translation with the modelview matrix
        translation = newloc - oldloc
        pre_tran = numpy.array([translation[0], translation[1], translation[2], 0])
        translation = inv_modelview.dot(pre_tran)

        # translate the node and track its location
        node.translate(translation[0], translation[1], translation[2])
        node.selected_loc = newloc

Обратите внимание, что новое и старое местоположения задаются в координатном пространстве камеры. Нам нужно, чтобы перемещение задавалось в координатном пространстве мира. Следовательно, мы преобразуем перемещение в пространстве камеры в перемещение в мировом пространстве, умножив на матрицу, обратную modelview.

Как и в случае с масштабом, каждый узел хранит матрицу, представляющую его перемещение. Матрица перемещения выглядит так:

$$

При перемещении узла мы создаём новую матрицу перемещения для текущего перемещения, и умножаем её на матрицу перемещения узла, чтобы использовать во время рендеринга.

    # class Node
    def translate(self, x, y, z):
        self.translation_matrix = numpy.dot(
            self.translation_matrix, 
            translation([x, y, z]))

Функция translation возвращает матрицу перемещения, соответствующую списку расстояний перемещения по $$, $$ и $$.

def translation(displacement):
    t = numpy.identity(4)
    t[0, 3] = displacement[0]
    t[1, 3] = displacement[1]
    t[2, 3] = displacement[2]
    return t

Размещение новых узлов

Для размещения узлов используются методики и из выбора, и из перемещения. Для определения места размещения узла мы используем то же вычисление луча для текущего расположения курсора мыши.

    # class Viewer
    def place(self, shape, x, y):
        """ Execute a placement of a new primitive into the scene. """
        start, direction = self.get_ray(x, y)
        self.scene.place(shape, start, direction, self.inverseModelView)

Для размещения нового узла мы сначала просто создаём новый экземпляр соответствующего типа узла и добавляем его в сцену. Мы хотим разместить узел под курсором пользователя, поэтому находим точку на луче на фиксированном расстоянии от камеры. Луч тоже представлен в пространстве камеры, поэтому мы преобразуем получившийся вектор перемещения в координатное пространство мира, умножив его на матрицу, обратную modelview. Затем мы перемещаем новый узел на вычисленный вектор.

    # class Scene
    def place(self, shape, start, direction, inv_modelview):
        """ 
        Place a new node.
            
        Consume:  
        shape the shape to add
        start, direction describes the Ray to move to
        inv_modelview is the inverse modelview matrix for the scene 
        """
        new_node = None
        if shape == 'sphere': new_node = Sphere()
        elif shape == 'cube': new_node = Cube()
        elif shape == 'figure': new_node = SnowFigure()

        self.add_node(new_node)

        # place the node at the cursor in camera-space
        translation = (start + direction * self.PLACE_DEPTH)

        # convert the translation to world-space
        pre_tran = numpy.array([translation[0], translation[1], translation[2], 1])
        translation = inv_modelview.dot(pre_tran)

        new_node.translate(translation[0], translation[1], translation[2])

Итог

Поздравляю! Мы успешно реализовали небольшой 3D-редактор!


Рисунок 4 — Пример сцены

Мы узнали, как разработать расширяемую структуру данных, описывающую модели в сцене. Также мы поняли, что использование шаблона проектирования «Компоновщик» и древовидных структур данных упрощает обход сцены для рендеринга и позволяет добавлять новые типы узлов без повышения сложности кода. Мы использовали эту структуру данных для рендеринга проекта на экран и манипулировали матрицами OpenGL при обходе графа сцены. Мы создали очень простую систему обратных вызовов для событий уровня приложения, и использовали её для инкапсуляции обработки событий операционной системы. Далее мы рассмотрели возможные реализации обнаружения коллизий луча с объектом и компромиссы между точностью, сложностью и производительностью. В конце мы реализовали методы манипуляций с содержимым сцены.

При разработке полнофункционального 3D-приложения вы столкнётесь с этими же базовыми строительными блоками. Структура графа сцены и относительные координатные пространства используются во многих видах приложений для работы с 3D-графикой, от САПР до игровых движков. Сильным упрощением в этом проекте стал интерфейс пользователя. Готовый 3D-редактор должен иметь полный интерфейс пользователя, которому потребуется гораздо более сложная система событий, чем наша простая система обратных вызовов.

Вы можете экспериментировать дальше и попробовать добавить в проект новые функции. Попробуйте реализовать что-нибудь из этого списка:

• Добавить тип Node для поддержки мешей треугольников произвольной формы.
• Добавить стек отмены действий, чтобы можно было отменять/повторять действия пользователя.
• Сохранение/загрузка проекта в трёхмерный формат файлов, например, в DXF.
• Интеграция движка рендеринга: экспорт проекта для использования в фотореалистичном рендерере.
• Улучшить распознавание коллизий точным пересечением луча с объектом.

Дальнейшее исследование

Для дальнейшего изучения реального ПО 3D-моделирования интересно рассмотреть проекты с открытым исходным кодом.

Blender — это полнофункциональный пакет для 3D-анимаций с открытым исходным кодом. В нём есть полный 3D-конвейер для создания спецэффектов в видео или для создания игр. Моделирование — это небольшая часть данного проекта, и оно является хорошим примером интеграции моделирования в большой программный пакет.

OpenSCAD — это инструмент для 3D-моделирования с открытым исходным кодом. Он не интерактивен — программа считывает скрипт, определяющий, как генерировать сцену. Это даёт проектировщику «полный контроль над процессом моделирования».

Подробнее об алгоритмах и техниках компьютерной графики можно узнать из замечательного ресурса Graphics Gems.

Об авторе

Эрик — разработчик ПО и фанат двухмерной и трёхмерной компьютерной графики. Он занимался разработкой видеоигр, ПО для трёхмерных спецэффектов и инструментов САПР. Если дело касается симулирования реальности, то есть вероятность, что ему захочется об этом узнать. Найти его онлайн можно на сайте erickdransch.com.