Элементарный графический движок на Java

Disclaimer. Данный "движок" написан исключительно for fun и вряд ли сможет найти реальное применение.



Задача. Объекты в пространстве представлены в виде множества цветных треугольников. Задана позиция наблюдателя и положение прямоугольного "окна", через которое он смотрит на объекты. Необходимо воспроизвести изображение, которое видит наблюдатель через "окно".

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

Обозначения
O - точка, в которой находится наблюдатель
G, H, I - три угла "окна". Со стороны наблюдателя: G - верхний-левый, H - нижний-левый, I - нижний-правый.

Самое интересное здесь - геометрия. Объясню вкратце, что да как.

Во-первых, построение луча. Конец луча - всегда точка O. Вторая точка P, через которую проходит луч, лежит в "окне" и выбирается следующим образом:
P = G + HI * w/resW + GH * h/resH,
где HI - вектор из H в I, GH - вектор из G в H,
w и h - координаты простреливаемой точки в окне,
resW и resH - количество точек(разрешение) по горизонтали и вертикали.

Далее для каждого треугольника ищем точку пересечения с ним луча и среди всех пересечений выбираем ближайшее.
Для начала находим точку пересечения луча и плоскости, в которой лежит треугольник. Уравнение плоскости находим так, а точку пересечения - так. Далее, если точка пересечения существует, необходимо определить, лежит ли она внутри треугольника. Для этого был использован следующий факт: точка Q лежит внутри треугольника ABC тогда и только тогда, когда площадь треугольника ABC равна сумме площадей треугольников ABQ, ACQ и BCQ. Площадь треугольника подсчитывается по векторному произведению двух его сторон. Возвращаясь к точке пересечения с плоскостью: там в результате получилось значение мю, которое представляет собой параметр при параметрическом задании луча. То есть чем больше мю, тем дальше точка пересечения находится от наблюдателя. Поэтому это значение мю очень удобно использовать для поиска ближайшего пересекаемого треугольника: достаточно среди всех мю выбрать наименьшее неотрицательное(отрицательное мю означает, что треугольник находился позади наблюдателя).

После нахождения ближайшего пересекаемого треугольника рисуем пиксель цвета этого треугольника в точке (w, h).

Спецификация входного файла
Координаты точек представляют собой вещественные или целые числа, записанные через пробел или табуляцию. Координат три и записываются в привычном порядке: x, y, z. Цвет записывается в виде трёх целых чисел из множества [0, 255] - это R, G и B соответственно.

Входной файл называется input и должен быть расположен в текущей директории.

Входной файл должен содержать в указанном порядке:
Координаты точки O;
координаты точек G, H, I;
разрешение картинки по горизонтали и вертикали resW и resH(целые, положительные);
количество треугольников - целое, неотрицательное;
затем для каждого треугольника: координаты трёх вершин и цвет.

Переводы строк допустимы между любыми числами.

Примеры
Привожу скриншоты и ссылки на исходники файла input в двух экземлярах.
1. Пирамида

http://pastebin.com/Pr8ehGUs
http://paste.org.ru/?0tcyqw

2. Пересечение двух треугольников

http://pastebin.com/wUVWLvwN
http://paste.org.ru/?k4nyz8

3. Перспектива
Смежные плоскости образуют прямой угол.

http://pastebin.com/y95Trgdf
http://paste.org.ru/?c0y6ds

4. Рандом
100 произвольных треугольников в кубе 200x200x200. Картинка рендерится заметно дольше остальных.

http://pastebin.com/TtbwWE5U
http://paste.org.ru/?t0i3rc

5. Поворот
Если вместо угла H указать противоположный, то картинка повернётся.

http://pastebin.com/QKQHut45
http://paste.org.ru/?jqgdl9

А при первом запуске я получил такую картину:

Дело в том, что в программе используется не очевидное сравнение вещественных чисел с нулём a == 0, а более правильное Math.abs(a) < EPS, где EPS - маленькое число. Так вот, оказалось, что константа EPS у меня была настолько маленькой, а float настолько невместительным, что сумма площадей треугольников(см. выше) не сходилась. Поэтому не все пересечения посчитались правильно и оказались видны задние стенки пирамиды.
Кстати, то же самое касается сравнения на равенство двух вещественных чисел - это общий случай: вместо a == b следует делать Math.abs(a-b) < EPS.

Исходный код
Расположение файлов в папках несложно определить из имени пакета.

GeometryHelper.java

package com.blogspot.codingbreak.simple3d.geometry;

public class GeometryHelper {

    /**
     * 
     * @return value m >= 0 so that p = ray.p1 + m * (ray.p2 - ray.p1) is the
     *         intersection point. Null if there is no interection points.
     */
    public static Float intersectRayAndTriangle(final Ray ray,
            final Triangle triangle) {
        // calculating the triangle's plane equation:
        final float a = triangle.getA().getY()
                * (triangle.getB().getZ() - triangle.getC().getZ())
                + triangle.getB().getY()
                * (triangle.getC().getZ() - triangle.getA().getZ())
                + triangle.getC().getY()
                * (triangle.getA().getZ() - triangle.getB().getZ());
        final float b = triangle.getA().getZ()
                * (triangle.getB().getX() - triangle.getC().getX())
                + triangle.getB().getZ()
                * (triangle.getC().getX() - triangle.getA().getX())
                + triangle.getC().getZ()
                * (triangle.getA().getX() - triangle.getB().getX());
        final float c = triangle.getA().getX()
                * (triangle.getB().getY() - triangle.getC().getY())
                + triangle.getB().getX()
                * (triangle.getC().getY() - triangle.getA().getY())
                + triangle.getC().getX()
                * (triangle.getA().getY() - triangle.getB().getY());
        final float d = -triangle.getA().getX()
                * (triangle.getB().getY() * triangle.getC().getZ() - triangle
                        .getC().getY()
                        * triangle.getB().getZ())
                - triangle.getB().getX()
                * (triangle.getC().getY() * triangle.getA().getZ() - triangle
                        .getA().getY()
                        * triangle.getC().getZ())
                - triangle.getC().getX()
                * (triangle.getA().getY() * triangle.getB().getZ() - triangle
                        .getB().getY()
                        * triangle.getA().getZ());
        http://codingbreak.blogspot.com/ 
        {}
        final float numerator = a * ray.getP1().getX() + b * ray.getP1().getY()
                + c * ray.getP1().getZ() + d;
        final float denominator = a * (ray.getP2().getX() - ray.getP1().getX())
                + b * (ray.getP2().getY() - ray.getP1().getY()) + c
                * (ray.getP2().getZ() - ray.getP1().getZ());

        Float mu;
        if (Math.abs(denominator) < 1e-6) {
            // denominator == 0 => ray is parallel to triangle, there is no
            // intersection point
            mu = null;
        } else {
            mu = Float.valueOf(-numerator / denominator);
        }

        if (mu != null) {
            final float px = ray.getP1().getX() + mu
                    * (ray.getP2().getX() - ray.getP1().getX());
            final float py = ray.getP1().getY() + mu
                    * (ray.getP2().getY() - ray.getP1().getY());
            final float pz = ray.getP1().getZ() + mu
                    * (ray.getP2().getZ() - ray.getP1().getZ());
            final Point p = new Point(px, py, pz);
            if (!isPointLiesInsideTriangle(p, triangle)) {
                mu = null;
            }
        }
        return mu;
    }

    static boolean isPointLiesInsideTriangle(final Point p,
            final Triangle triangle) {
        float s0 = areaOfTriangle(triangle.getA(), triangle.getB(), triangle
                .getC());
        float s1 = areaOfTriangle(triangle.getA(), triangle.getB(), p);
        float s2 = areaOfTriangle(triangle.getA(), triangle.getC(), p);
        float s3 = areaOfTriangle(triangle.getC(), triangle.getB(), p);
        return Math.abs(s0 - s1 - s2 - s3) < 1f;
    }

    static float areaOfTriangle(Point a, Point b, Point c) {
        float px = b.getX() - a.getX();
        float py = b.getY() - a.getY();
        float pz = b.getZ() - a.getZ();

        float qx = c.getX() - a.getX();
        float qy = c.getY() - a.getY();
        float qz = c.getZ() - a.getZ();

        float x = py * qz - pz * qy;
        float y = pz * qx - px * qz;
        float z = px * qy - py * qx;

        float s = (float) (.5 * Math.sqrt(x * x + y * y + z * z));
        return Math.abs(s);
    }
}

Point.java

package com.blogspot.codingbreak.simple3d.geometry;

public class Point {
    private final float x;
    private final float y;
    private final float z;

    public Point(float x, float y, float z) {
        this.x = x;
        this.y = y;
        this.z = z;
    }

    public float getX() {
        return x;
    }

    public float getY() {
        return y;
    }

    public float getZ() {
        return z;
    }
}

Ray.java

package com.blogspot.codingbreak.simple3d.geometry;

public class Ray {
    private final Point p1;
    private final Point p2;

    public Ray(Point p1, Point p2) {
        this.p1 = p1;
        this.p2 = p2;
    }

    public Point getP1() {
        return p1;
    }

    public Point getP2() {
        return p2;
    }
}

Triangle.java

package com.blogspot.codingbreak.simple3d.geometry;

import java.awt.Color;

public class Triangle {
    private final Point a;
    private final Point b;
    private final Point c;
    private final Color color;

    public Triangle(Point a, Point b, Point c, Color color) {
        this.a = a;
        this.b = b;
        this.c = c;
        this.color = color;
    }

    public Point getA() {
        return a;
    }

    public Point getB() {
        return b;
    }

    public Point getC() {
        return c;
    }

    public Color getColor() {
        return color;
    }
}

DemoFrame.java

package com.blogspot.codingbreak.simple3d;

import java.awt.Color;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

import javax.swing.JFrame;

import com.blogspot.codingbreak.simple3d.geometry.Point;
import com.blogspot.codingbreak.simple3d.geometry.Triangle;

class DemoFrame extends JFrame {

    public static void main(String[] args) {
        new DemoFrame().setVisible(true);
    }

    public DemoFrame() {
        super("Simple3D demo frame");
        setDefaultCloseOperation(DISPOSE_ON_CLOSE);

        Simple3DDrawingPanel drawing = null;
        try {
            drawing = loadFromFile(new File("input"));
            getContentPane().add(drawing);
            this.pack();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }

    /**
     * Loads all the space information(objects, camera coordinates, etc) from file and
     * constructs Simple3DDrawingPanel object.
     * 
     * @param file
     * @return Simple3DDrawingPanel object
     * @throws FileNotFoundException
     */
    private static Simple3DDrawingPanel loadFromFile(final File file)
            throws FileNotFoundException {
        final Scanner in = new Scanner(file);
        
        final Point o = readPoint(in);
        final Point g = readPoint(in);
        final Point h = readPoint(in);
        final Point i = readPoint(in);
        final int resolutionW = in.nextInt();
        final int resolutionH = in.nextInt();

        final int n = in.nextInt(); // the number of triangles
        final Set<Triangle> triangles = new HashSet<Triangle>(n);
        for (int j = 0; j < n; ++j) {
            final Point a = readPoint(in);
            final Point b = readPoint(in);
            final Point c = readPoint(in);
            final Color color = readColor(in);
            
            final Triangle triangle = new Triangle(a, b, c, color);
            triangles.add(triangle);
        }

        in.close();
        final Simple3DDrawingPanel drawingPanel = new Simple3DDrawingPanel(o,
                g, h, i, resolutionW, resolutionH, triangles);
        return drawingPanel;
    }

    private static Point readPoint(final Scanner in) {
        final float x = in.nextFloat();
        final float y = in.nextFloat();
        final float z = in.nextFloat();
        return new Point(x, y, z);
    }

    private static Color readColor(final Scanner in) {
        final int colorR = in.nextInt();
        final int colorG = in.nextInt();
        final int colorB = in.nextInt();
        return new Color(colorR, colorG, colorB);
    }

}

RandomGenerator.java

package com.blogspot.codingbreak.simple3d;

import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.Random;

public class RandomGenerator {

    private static float bound = 200f;
    private static float deltaX = 1000f;

    public static void main(String[] args) throws FileNotFoundException {
        PrintWriter out = new PrintWriter(new File("random"));

        out
                .print("0 0 0\n\n500 -320 240\n500 -320 -240\n500 320 -240\n\n640 480\n\n");

        int n = 100;
        out.print(n);
        out.print("\n\n");

        Random generator = new Random();
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < 3; ++j) {
                float x = (generator.nextFloat()-.5f) * bound+deltaX;
                float y = (generator.nextFloat()-.5f) * bound;
                float z = (generator.nextFloat()-.5f) * bound;

                out.printf("%f %f %f\n", x, y, z);
            }
            int r = generator.nextInt(256);
            int g = generator.nextInt(256);
            int b = generator.nextInt(256);
            out.printf("%d %d %d\n\n", r, g, b);
        }

        out.close();
    }

}

Simple3DDrawingPanel.java

package com.blogspot.codingbreak.simple3d;

import java.awt.Color;
import java.awt.Dimension;
import java.awt.Graphics;
import java.util.Set;

import javax.swing.JPanel;

import com.blogspot.codingbreak.simple3d.geometry.GeometryHelper;
import com.blogspot.codingbreak.simple3d.geometry.Point;
import com.blogspot.codingbreak.simple3d.geometry.Ray;
import com.blogspot.codingbreak.simple3d.geometry.Triangle;

public class Simple3DDrawingPanel extends JPanel {

    private static Color BACKGROUND_COLOR = Color.BLACK;

    private Point O;
    private Point G;
    private Point H;
    private Point I;
    private Set<Triangle> triangles;
    private int resolutionW;
    private int resolutionH;

    public Simple3DDrawingPanel(final Point o, final Point g, final Point h,
            final Point i, final int resolutionW, final int resolutionH,
            final Set<Triangle> triangles) {
        this.G = g;
        this.H = h;
        this.I = i;
        this.resolutionW = resolutionW;
        this.resolutionH = resolutionH;
        this.triangles = triangles;
        this.O = o;
        setPreferredSize(new Dimension(resolutionW, resolutionH));
    }

    private Point getPointByCoordinates(final int w, final int h) {
        final float x = G.getX() + (I.getX() - H.getX()) * w / resolutionW
                + (H.getX() - G.getX()) * h / resolutionH;
        final float y = G.getY() + (I.getY() - H.getY()) * w / resolutionW
                + (H.getY() - G.getY()) * h / resolutionH;
        final float z = G.getZ() + (I.getZ() - H.getZ()) * w / resolutionW
                + (H.getZ() - G.getZ()) * h / resolutionH;
        return new Point(x, y, z);
    }

    @Override
    public void paintComponent(Graphics g) {
        super.paintComponent(g);
        g.setColor(Color.BLACK);
        for (int w = 0; w < resolutionW; w++) {
            for (int h = 0; h < resolutionH; ++h) {
                final Point point = getPointByCoordinates(w, h);
                final Ray ray = new Ray(O, point);

                Float mu = null;
                Color color = null;
                for (final Triangle triangle : triangles) {
                    final Float muCurrent = GeometryHelper
                            .intersectRayAndTriangle(ray, triangle);
                    if (muCurrent != null && (mu == null || mu > muCurrent)) {
                        mu = muCurrent;
                        color = triangle.getColor();
                    }
                }
                if (mu == null) {
                    color = BACKGROUND_COLOR;
                }

                g.setColor(color);
                g.drawRect(w, h, 1, 1);
            }
        }
    }

}