Создание движка для 3D-рендеринга на Java

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

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

Итак, для чего же это всё нужно? Во-первых, создание движка для 3D-рендеринга поможет понять, как же работают современные движки изнутри. Во-вторых, сам движок при желании можно использовать и в своём собственном приложении, не прибегая к вызову внешних зависимостей. В случае с Java это значит, что вы можете создать своё собственное приложение для просмотра 3D-изображений без зависимостей (далёких от API Java), которое будет работать практически везде и уместится в 50 КБ!

Само собой, если вы хотите создать какое-нибудь большое 3D-приложение с плавной анимацией, вам лучше использовать OpenGL/WebGL. Однако, имея базовое представление о том, как устроены подобные движки, работа с более сложными движками будет казаться в разы проще.

В этой статье я постараюсь объяснить базовый 3D-рендеринг с ортографической проекцией, простую треугольную растеризацию (процесс, обратный векторизации), Z-буферизацию и плоское затенение. Я не буду заострять своё внимание на таких вещах, как оптимизация, текстуры и разные настройки освещения — если вам это нужно,  попробуйте использовать более подходящие для этого инструменты, вроде OpenGL (существует множество библиотек, позволяющих вам работать с OpenGL, даже используя Java).

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

Довольно болтать — давайте приступим к делу!

GUI

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

			import javax.swing.*;
import java.awt.*;

public class DemoViewer {

    public static void main(String[] args) {

        JFrame frame = new JFrame();
        Container pane = frame.getContentPane();
        pane.setLayout(new BorderLayout());

        // slider to control horizontal rotation
        JSlider headingSlider = new JSlider(0, 360, 180);
        pane.add(headingSlider, BorderLayout.SOUTH);

        // slider to control vertical rotation
        JSlider pitchSlider = new JSlider(SwingConstants.VERTICAL, -90, 90, 0);
        pane.add(pitchSlider, BorderLayout.EAST);

        // panel to display render results
        JPanel renderPanel = new JPanel() {
            public void paintComponent(Graphics g) {
                Graphics2D g2 = (Graphics2D) g;
                g2.setColor(Color.BLACK);
                g2.fillRect(0, 0, getWidth(), getHeight());
                // rendering magic will happen here
                }
            };

        pane.add(renderPanel, BorderLayout.CENTER);
        frame.setSize(400, 400);
        frame.setVisible(true);
    }
}
		

Результат должен выглядеть вот так:

Теперь давайте добавим некоторые модели — вершины и треугольники. Вершина — это просто структура для хранения наших трёх координат (X, Y и Z), а треугольник соединяет вместе три вершины и содержит их цвет.

			class Vertex {

    double x;
    double y;
    double z;
    Vertex(double x, double y, double z) {
        this.x = x;
        this.y = y;
        this.z = z;
    }
}

class Triangle {
    Vertex v1;
    Vertex v2;
    Vertex v3;
    Color color;
    Triangle(Vertex v1, Vertex v2, Vertex v3, Color color) {
        this.v1 = v1;
        this.v2 = v2;
        this.v3 = v3;
        this.color = color;
    }
}
		

Здесь я буду считать, что X означает перемещение влево-вправо, Y — вверх-вниз, а Z будет глубиной (так, что ось Z перпендикулярна вашему экрану). Положительная Z будет означать «ближе к пользователю».

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

Код также будет достаточно простым — мы просто создаём 4 треугольника и добавляем их в ArrayList:

			List tris = new ArrayList<>();

tris.add(new Triangle(new Vertex(100, 100, 100),
                      new Vertex(-100, -100, 100),
                      new Vertex(-100, 100, -100),
                      Color.WHITE));

tris.add(new Triangle(new Vertex(100, 100, 100),
                      new Vertex(-100, -100, 100),
                      new Vertex(100, -100, -100),
                      Color.RED));

tris.add(new Triangle(new Vertex(-100, 100, -100),
                      new Vertex(100, -100, -100),
                      new Vertex(100, 100, 100),
                      Color.GREEN));

tris.add(new Triangle(new Vertex(-100, 100, -100),
                      new Vertex(100, -100, -100),
                      new Vertex(-100, -100, 100),
                      Color.BLUE));
		

В результате мы получим фигуру, центр которой находится в начале координат (0, 0, 0), что довольно удобно, так как мы будем вращать фигуру относительно этой точки.

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

			g2.translate(getWidth() / 2, getHeight() / 2);
g2.setColor(Color.WHITE);
for (Triangle t : tris) {
    Path2D path = new Path2D.Double();
    path.moveTo(t.v1.x, t.v1.y);
    path.lineTo(t.v2.x, t.v2.y);
    path.lineTo(t.v3.x, t.v3.y);
    path.closePath();
    g2.draw(path);
}
		

Заметьте, что сейчас я совершил все преобразования до отрисовки треугольников. Это сделано, чтобы для того, что бы поместить наш центр (0, 0, 0) в центр экрана — по умолчанию начало координат находится в левом верхнем углу экрана. После компиляции вы должны получить:

Вы можете не поверить, но это наш тетраэдр в ортогональной проекции, честно!

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

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

Возьмём наш входной вектор A:

И умножим его на так называемую матрицу трансформации T, чтобы получить в итоге выходной вектор B:

Например, вот как будет выглядеть трансформация, если мы умножим на 2:

Вы не можете описать любую возможную трансформацию, используя матрицы размера 3×3 — например, если переход происходит за пределы пространства. Вы можете использовать матрицы размера 4×4, делая перекос в 4D-пространство, но об этом не в этой статье.

Трансформации, которые нам пригодятся здесь — масштабирование и вращение.

Любое вращение в 3D-пространстве может быть выражено в 3 примитивных вращениях: вращение в плоскости XY, вращение в плоскости YZ и вращение в плоскости XZ. Мы можем записать матрицы трансформации для каждого из данных вращений следующим путём:

• Матрица вращения XY:

• Матрица вращения YZ:

• Матрица вращения XZ:

И вот здесь начинается магия: если вам нужно сначала совершить вращение точки в плоскости XY, используя матрицу трансформации T1, и затем совершить вращение этой точки в плоскости YZ, используя матрицу трансформации T2, то вы можете просто умножить T1 на T2  и получить одну матрицу, которая опишет всё вращение:

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

Что ж, довольно страшной математики, давайте вернёмся к коду. Создадим служебный класс Matrix3, который будет обрабатывать перемножения  типа “матрица-матрица” и “вектор-матрица”:

			class Matrix3 {
    double[] values;
    Matrix3(double[] values) {
        this.values = values;
    }

    Matrix3 multiply(Matrix3 other) {
        double[] result = new double[9];
        for (int row = 0; row < 3; row++) {
            for (int col = 0; col < 3; col++) {
                for (int i = 0; i < 3; i++) {
                    result[row * 3 + col] += this.values[row * 3 + i] * other.values[i * 3 + col];
                }
            }
        }
    return new Matrix3(result);
    }

    Vertex transform(Vertex in) {
        return new Vertex(in.x * values[0] + in.y * values[3] + in.z * values[6],
                          in.x * values[1] + in.y * values[4] + in.z * values[7],
                          in.x * values[2] + in.y * values[5] + in.z * values[8]);
    }
}
		

Теперь можно и оживить наши скроллеры вращения. Горизонтальный скроллер будет контролировать вращение влево-вправо (XZ), а вертикальный скроллер будет контролировать вращение вверх-вниз (YZ).

Давайте создадим нашу матрицу вращения:

			double heading = Math.toRadians(headingSlider.getValue());
Matrix3 transform = new Matrix3(new double[] {Math.cos(heading), 0, -Math.sin(heading),
                                              0, 1, 0,
                                              Math.sin(heading), 0, Math.cos(heading)});
g2.translate(getWidth() / 2, getHeight() / 2);
g2.setColor(Color.WHITE);
for (Triangle t : tris) {
    Vertex v1 = transform.transform(t.v1);
    Vertex v2 = transform.transform(t.v2);
    Vertex v3 = transform.transform(t.v3);
    Path2D path = new Path2D.Double();
    path.moveTo(v1.x, v1.y);
    path.lineTo(v2.x, v2.y);
    path.lineTo(v3.x, v3.y);
    path.closePath();
    g2.draw(path);
}
		

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

			headingSlider.addChangeListener(e -> renderPanel.repaint()); 
pitchSlider.addChangeListener(e -> renderPanel.repaint());
		

Как вы, наверное, уже заметили, вращение вверх-вниз ещё не работает. Добавим эти строки в код:

			Matrix3 headingTransform = new Matrix3(new double[] {Math.cos(heading), 0, Math.sin(heading),
                                                     0, 1, 0, 
                                                     -Math.sin(heading), 0, Math.cos(heading)}); 
double pitch = Math.toRadians(pitchSlider.getValue()); 
Matrix3 pitchTransform = new Matrix3(new double[] {1, 0, 0, 
                                                   0, Math.cos(pitch), Math.sin(pitch), 
                                                   0, -Math.sin(pitch), Math.cos(pitch)}); 
Matrix3 transform = headingTransform.multiply(pitchTransform);
		

До сих пор мы отрисовывали только каркасное представление нашей фигуры. Теперь давайте заполним его чем-нибудь. Для этого нам нужно сначала растеризовать треугольник — представить его в виде пикселей на экране.

Я буду использовать очень простой, но крайне неэффективный метод — растеризация через барицентрические координаты. Настоящие 3D-движки используют растеризацию, задействуя железо компьютера, что очень быстро и эффективно, но мы не можем использовать нашу видеокарту, так что будем делать всё вручную, через код.

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

			BufferedImage img = new BufferedImage(getWidth(), getHeight(), BufferedImage.TYPE_INT_ARGB);

for (Triangle t : tris) {
    Vertex v1 = transform.transform(t.v1);
    Vertex v2 = transform.transform(t.v2);
    Vertex v3 = transform.transform(t.v3);

    // since we are not using Graphics2D anymore, we have to do translation manually
    v1.x += getWidth() / 2;
    v1.y += getHeight() / 2;
    v2.x += getWidth() / 2;
    v2.y += getHeight() / 2;
    v3.x += getWidth() / 2;
    v3.y += getHeight() / 2;

    // compute rectangular bounds for triangle
    int minX = (int) Math.max(0, Math.ceil(Math.min(v1.x, Math.min(v2.x, v3.x))));
    int maxX = (int) Math.min(img.getWidth() - 1, Math.floor(Math.max(v1.x, Math.max(v2.x, v3.x))));
    int minY = (int) Math.max(0, Math.ceil(Math.min(v1.y, Math.min(v2.y, v3.y))));
    int maxY = (int) Math.min(img.getHeight() - 1, Math.floor(Math.max(v1.y, Math.max(v2.y, v3.y))));

    double triangleArea = (v1.y - v3.y) * (v2.x - v3.x) + (v2.y - v3.y) * (v3.x - v1.x);
    for (int y = minY; y <= maxY; y++) {
        for (int x = minX; x <= maxX; x++) {
            double b1 = ((y - v3.y) * (v2.x - v3.x) + (v2.y - v3.y) * (v3.x - x)) / triangleArea;
            double b2 = ((y - v1.y) * (v3.x - v1.x) + (v3.y - v1.y) * (v1.x - x)) / triangleArea;
            double b3 = ((y - v2.y) * (v1.x - v2.x) + (v1.y - v2.y) * (v2.x - x)) / triangleArea;
            if (b1 >= 0 && b1 <= 1 && b2 >= 0 && b2 <= 1 && b3 >= 0 && b3 <= 1) {
                img.setRGB(x, y, t.color.getRGB());
            }
        }
    }
}

g2.drawImage(img, 0, 0, null);
		

Довольно много кода, но теперь у нас есть цветной тетраэдр на экране.

Если вы поиграетесь с демкой, то вы заметите, что не всё сделано идеально — например, синий треугольник всегда выше других. Так происходит потому, что мы отрисовываем наши треугольники один за другим. Синий здесь — последний, поэтому он отрисовывается поверх других.

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

			double[] zBuffer = new double[img.getWidth() * img.getHeight()];

// initialize array with extremely far away depths
for (int q = 0; q < zBuffer.length; q++) {
    zBuffer[q] = Double.NEGATIVE_INFINITY;
}

for (Triangle t : tris) {
    // handle rasterization...
    // for each rasterized pixel:
    double depth = b1 * v1.z + b2 * v2.z + b3 * v3.z;
    int zIndex = y * img.getWidth() + x;
    if (zBuffer[zIndex] < depth) {
        img.setRGB(x, y, t.color.getRGB());
        zBuffer[zIndex] = depth;
    }
}
		

Теперь видно, что у нашего тетраэдра есть одна белая сторона:

Вот мы и получили работающий движок для 3D-рендеринга!

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

В компьютерной графике мы можем достичь подобного эффекта с помощью так называемого «затенения» — изменения цвета поверхности в зависимости от угла наклона и расстояния относительно источника света.

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

Для начала нам нужно посчитать вектор нормали для нашего треугольника. Если у нас есть треугольник ABC, мы можем посчитать его вектор нормали, рассчитав векторное произведение векторов AB и AC и поделив получившийся вектор на его длину.

Векторное произведение — это бинарная операция на двух векторах, которые определены в 3D пространстве вот так:

Вот так выглядит визуальное представление того, что делает наше векторное произведение:

			for (Triangle t : tris) {
    // transform vertices before calculating normal...
    Vertex norm = new Vertex(ab.y * ac.z - ab.z * ac.y,
                             ab.z * ac.x - ab.x * ac.z,
                             ab.x * ac.y - ab.y * ac.x);
    double normalLength = Math.sqrt(norm.x * norm.x + norm.y * norm.y + norm.z * norm.z);
    norm.x /= normalLength;
    norm.y /= normalLength;
    norm.z /= normalLength;
}
		

Теперь нам нужно посчитать косинус между нормалью треугольника и направлением света. Для упрощения будем считать, что наш источник света расположен прямо за камерой на каком-либо расстоянии (такая конфигурация называется «направленный свет») — таким образом, наш источник света будет находиться в точке (0, 0, 1).

Косинус угла между векторами можно посчитать по формуле:

Где ||A|| — длина вектора, а числитель — скалярное произведение векторов A и B:

Обратите внимание на то, что длина вектора направления света  равна 1, так же, как и длина нормали треугольника (мы уже нормализовали это). Таким образом, формула просто превращается в это:

Заметьте, что только Z компонент направления света не равен нулю, так что мы можем просто всё упростить:

В коде это всё выглядит тривиально:

			double angleCos = Math.abs(norm.z);
		

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

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

			public static Color getShade(Color color, double shade) {
    int red = (int) (color.getRed() * shade);
    int green = (int) (color.getGreen() * shade);
    int blue = (int) (color.getBlue() * shade);

    return new Color(red, green, blue);
}
		

Код будет давать нам некоторые эффекты затенения, но спадать они будут куда быстрее, чем нам нужно. Так происходит, потому что в Java используется спектр цветов sRGB.

Так что нам нужно конвертировать каждый цвет в линейный формат, применить затенение и затем конвертировать обратно. Реальный переход из sRGB к линейному RGB — довольно трудоёмкий процесс, так что я не буду выполнять полный перечень задач здесь. Вместо этого, я сделаю нечто приближенное к этому.

			public static Color getShade(Color color, double shade) {
    double redLinear = Math.pow(color.getRed(), 2.4) * shade;
    double greenLinear = Math.pow(color.getGreen(), 2.4) * shade;
    double blueLinear = Math.pow(color.getBlue(), 2.4) * shade;

    int red = (int) Math.pow(redLinear, 1/2.4);
    int green = (int) Math.pow(greenLinear, 1/2.4);
    int blue = (int) Math.pow(blueLinear, 1/2.4);

    return new Color(red, green, blue);
}
		

И теперь мы видим, как наш тетраэдр оживляется. У нас есть работающий движок для 3D рендеринга с цветами, освещением, затенением, и заняло это около 200 строк кода — неплохо!

Вот небольшой бонус для вас — вы можете быстро создать фигуру, приближенную к сфере из своего тетраэдра. Этого можно достичь путём разбивания каждого треугольника на 4 маленьких и «надувая».

			public static List inflate(List tris) {
    List result = new ArrayList<>();
    for (Triangle t : tris) {
        Vertex m1 = new Vertex((t.v1.x + t.v2.x)/2, (t.v1.y + t.v2.y)/2, (t.v1.z + t.v2.z)/2);
        Vertex m2 = new Vertex((t.v2.x + t.v3.x)/2, (t.v2.y + t.v3.y)/2, (t.v2.z + t.v3.z)/2);
        Vertex m3 = new Vertex((t.v1.x + t.v3.x)/2, (t.v1.y + t.v3.y)/2, (t.v1.z + t.v3.z)/2);
        result.add(new Triangle(t.v1, m1, m3, t.color));
        result.add(new Triangle(t.v2, m1, m2, t.color));
        result.add(new Triangle(t.v3, m2, m3, t.color));
        result.add(new Triangle(m1, m2, m3, t.color));
    }
    for (Triangle t : result) {
        for (Vertex v : new Vertex[] { t.v1, t.v2, t.v3 }) {
            double l = Math.sqrt(v.x * v.x + v.y * v.y + v.z * v.z) / Math.sqrt(30000);
            v.x /= l;
            v.y /= l;
            v.z /= l;
        }
    }
    return result;
}
		

Вот что должно у вас получиться:

Я бы закончил эту статью, порекомендовав одну занимательную книгу: “Основы 3D-математики для графики и разработки игр”. В ней вы можете найти детальное объяснение процесса рендеринга и математики в этом процессе. Её стоит прочитать, если вам интересны движки для рендеринга.