voxel triangle

package com.neonsoup.coords3i;

import java.io.IOException;
import java.io.Serializable;
import java.util.Iterator;
import java.util.NoSuchElementException;

import com.neonsoup.coords2i.ArrayIntContainer;
import com.neonsoup.coords2i.Direction;
import com.neonsoup.coords2i.FilledRectangle;
import com.neonsoup.coords2i.IntContainer;
import com.neonsoup.coords2i.Line8Iterator;

public class Polygon26 extends AbstractShape {

    private static final int CELL_STATE_EMPTY = Integer.MAX_VALUE;
    private static final int CELL_STATE_NOT_CALCULATED = Integer.MAX_VALUE - 1;

    private transient Point[] vertices;

    private transient CoordPlane projectionPlane;
    private transient IntContainer projection;


    public Polygon26(Point... vertices) {
        this.vertices = new Point[vertices.length];
        for (int i = 0; i < vertices.length; i++) {
            this.vertices[i] = new Point(vertices[i]);
        }

        generateProjection();
    }


    private void generateProjection() {
        Point normal = new Point();

        {
            Point p0 = new Point(vertices[0]);
            p0.sub(vertices[2]);

            Point p1 = new Point(vertices[1]);
            p1.sub(vertices[2]);

            normal.x = p0.y * p1.z - p0.z * p1.y;
            normal.y = p0.z * p1.x - p0.x * p1.z;
            normal.z = p0.x * p1.y - p0.y * p1.x;
        }

        if (Math.abs(normal.z) >= Math.abs(normal.x)
            && Math.abs(normal.z) >= Math.abs(normal.y)) {

            projectionPlane = CoordPlane.XY;

        } else if (Math.abs(normal.y) >= Math.abs(normal.x)
                   && Math.abs(normal.y) >= Math.abs(normal.z)) {

            projectionPlane = CoordPlane.ZX;
        } else {
            projectionPlane = CoordPlane.YZ;
        }

        FilledRectangle projectionBoundingBox = new FilledRectangle();

        for (Point p : vertices) {
            projectionBoundingBox.expand(projectionPlane.getFirstCoord(p),
                                         projectionPlane.getSecondCoord(p));
        }

        IntContainer projectionErr = new ArrayIntContainer(projectionBoundingBox);

        projection = new ArrayIntContainer(projectionBoundingBox,
                                           CELL_STATE_EMPTY);

        {
            com.neonsoup.coords2i.LineIterator line = new Line8Iterator();

            com.neonsoup.coords2i.Point cursor = new com.neonsoup.coords2i.Point();

            for (int i = 0; i < vertices.length; i++) {
                Point v1 = vertices[i];
                Point v2 = vertices[(i + 1) % vertices.length];

                cursor.set(projectionPlane.getFirstCoord(v1),
                           projectionPlane.getSecondCoord(v1));

                line.reset(cursor.x,
                           cursor.y,
                           projectionPlane.getFirstCoord(v2),
                           projectionPlane.getSecondCoord(v2));

                while (line.hasNext()) {
                    cursor.add(line.next());
                    projection.put(cursor, CELL_STATE_NOT_CALCULATED);
                }
            }
        }

        fillProjection();

        Point firstPoint = vertices[0];

        {
            int maxCoord = projectionPlane.getPerpendicularCoord(firstPoint);
            for (Point p : vertices) {
                projection.put(projectionPlane.getFirstCoord(p),
                               projectionPlane.getSecondCoord(p),
                               projectionPlane.getPerpendicularCoord(p));

                int coord = projectionPlane.getPerpendicularCoord(p);
                if (coord > maxCoord) {
                    maxCoord = coord;
                    firstPoint = p;
                }
            }
        }

        {

            int dx = projectionPlane.getFirstCoord(normal);
            int dy = projectionPlane.getSecondCoord(normal);
            int dz = projectionPlane.getPerpendicularCoord(normal);

            com.neonsoup.coords2i.HollowRectangle waveRect;
            waveRect = new com.neonsoup.coords2i.HollowRectangle();
            waveRect.expand(projectionPlane.getFirstCoord(firstPoint),
                            projectionPlane.getSecondCoord(firstPoint));

            boolean somethingChanged = true;

            while (somethingChanged) {
                somethingChanged = false;
                for (com.neonsoup.coords2i.Point p : waveRect) {
                    int centerProjVal = projection.get(p);
                    if (centerProjVal != CELL_STATE_EMPTY
                        && centerProjVal != CELL_STATE_NOT_CALCULATED) {

                        int centerErr = projectionErr.get(p);

                        for (Direction dir : Direction.DIR_8) {
                            int newX = p.x + dir.x;
                            int newY = p.y + dir.y;

                            if (projection.get(newX, newY) != CELL_STATE_NOT_CALCULATED) {
                                continue;
                            }

                            int newZ = centerProjVal;
                            int newErr = centerErr;

                            newErr += dx * dir.x;
                            newErr += dy * dir.y;

                            if (dz >= 0) {
                                while (2 * newErr >= dz) {
                                    newZ--;
                                    newErr -= dz;
                                }
                                while (2 * newErr <= -dz) {
                                    newZ++;
                                    newErr += dz;
                                }
                            } else {
                                while (2 * newErr <= dz) {
                                    newZ--;
                                    newErr -= dz;
                                }
                                while (2 * newErr >= -dz) {
                                    newZ++;
                                    newErr += dz;
                                }
                            }

                            projection.put(newX, newY, newZ);
                            projectionErr.put(newX, newY, newErr);

                            somethingChanged = true;
                        }
                    }
                }

                waveRect.grow();
            }
        }
    }


    private void fillProjection() {
        FilledRectangle area = projection.getBoundingRectangle();

        for (int x = area.minX; x <= area.maxX; x++) {
            int state = 0;
            int startedAt = 0;

            for (int y = area.minY; y <= area.maxY; y++) {
                if (projection.get(x, y) == CELL_STATE_NOT_CALCULATED) {
                    if (state == 0) {
                        state = 1;
                    } else if (state == 2) {
                        for (int y2 = startedAt; y2 < y; y2++) {
                            projection.put(x, y2, CELL_STATE_NOT_CALCULATED);
                        }
                        break;
                    }
                } else if (state == 1) {
                    startedAt = y;
                    state = 2;
                }
            }
        }
    }


    @Override
    public Iterator<Point> iterator() {
        return new PointIteratorBasedShapeIterator(this);
    }


    @Override
    public PointIterator pointIterator() {
        return new Polygon26PointIterator();
    }


    private class Polygon26PointIterator implements
                                        PointIterator,
                                        Serializable {

        private static final long serialVersionUID = -8909605563473525751L;

        private Point current = new Point();
        private Point next = new Point();
        private com.neonsoup.coords2i.PointIterator boundingBoxIterator = projection
                .getBoundingRectangle().pointIterator();

        private boolean started = false;


        public Polygon26PointIterator() {
            findNext();
        }


        private void findNext() {
            while (boundingBoxIterator.hasNext()) {
                boundingBoxIterator.next();

                int val = projection.get(boundingBoxIterator.currentX(),
                                         boundingBoxIterator.currentY());

                if (val != CELL_STATE_EMPTY) {
                    projectionPlane.setFirstCoord(next, boundingBoxIterator
                            .currentX());
                    projectionPlane.setSecondCoord(next, boundingBoxIterator
                            .currentY());
                    projectionPlane.setPerpendicularCoord(next, val);

                    return;
                }
            }

            next = null;
        }


        @Override
        public boolean hasNext() {
            return next != null;
        }


        @Override
        public void next() {
            if (next == null) {
                throw new NoSuchElementException();
            }

            started = true;

            current.set(next);
            findNext();
        }


        @Override
        public int currentX() {
            if (!started) {
                throw new IllegalStateException();
            }
            return current.x;
        }


        @Override
        public int currentY() {
            if (!started) {
                throw new IllegalStateException();
            }
            return current.y;
        }


        @Override
        public int currentZ() {
            if (!started) {
                throw new IllegalStateException();
            }
            return current.z;
        }


        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }

    }


    @Override
    public boolean contains(int x, int y, int z) {
        return projection.get(projectionPlane.getFirstCoord(x, y, z),
                              projectionPlane.getSecondCoord(x, y, z)) == projectionPlane
                .getPerpendicularCoord(x, y, z);
    }


    @Override
    public void getBoundingRectangle(com.neonsoup.coords3i.Rectangle dest) {
        dest.setEmpty();
        for (Point p : vertices) {
            dest.expand(p);
        }
    }


    private void writeObject(java.io.ObjectOutputStream out)
            throws IOException {

        out.defaultWriteObject();

        out.writeInt(vertices.length);
        for (Point p : vertices) {
            out.writeInt(p.x);
            out.writeInt(p.y);
            out.writeInt(p.z);
        }
    }


    private void readObject(java.io.ObjectInputStream in) throws IOException,
            ClassNotFoundException {

        in.defaultReadObject();

        int len = in.readInt();

        this.vertices = new Point[len];

        for (int i = 0; i < len; i++) {
            int x = in.readInt();
            int y = in.readInt();
            int z = in.readInt();

            this.vertices[i] = new Point(x, y, z);
        }

        generateProjection();
    }

}