package com.brackeen.javagamebook.bsp2D;

import java.awt.geom.Point2D;
import java.awt.Rectangle;
import java.util.*;
import com.brackeen.javagamebook.math3D.*;

/**
    Klasa BSPTreeBuilder buduje drzewo BSP na podstawie listy wielokątów.
    Wielokąty muszą być reprezentowane przez obiekty klasy BSPPolygon.

    Klasa nie próbuje na razie optymalizować porządek podziałów;
    można wprowadzić taką optymalizację polegającą na wybieraniu
    podziałów w kolejności umożliwiającej z minimalizowanie liczby
    dzielonych wielokątów i tworzenie bardziej zrównoważonego,
    kompletnego drzewa.
*/
public class BSPTreeBuilder {

    /**
        Aktualnie budowane drzewo BSP.
    */
    protected BSPTree currentTree;

    /**
        Buduje drzewo BSP.
    */
    public BSPTree build(List polygons) {
        currentTree = new BSPTree(createNewNode(polygons));
        buildNode(currentTree.getRoot());
        return currentTree;
    }


    /**
        Buduje węzeł w drzewie BSP.
    */
    protected void buildNode(BSPTree.Node node) {

        // jeśli węzeł jest liściem, kończę jego budowę
        if (node instanceof BSPTree.Leaf) {
            return;
        }

        // klasyfikuje wszystkie wielokąty zgodnie z podziałem
        // (przód, tył lub na linii podziału)
        ArrayList collinearList = new ArrayList();
        ArrayList frontList = new ArrayList();
        ArrayList backList = new ArrayList();
        List allPolygons = node.polygons;
        node.polygons = null;
        for (int i=0; i<allPolygons.size(); i++) {
            BSPPolygon poly = (BSPPolygon)allPolygons.get(i);
            int side = node.partition.getSide(poly);
            if (side == BSPLine.COLLINEAR) {
                collinearList.add(poly);
            }
            else if (side == BSPLine.FRONT) {
                frontList.add(poly);
            }
            else if (side == BSPLine.BACK) {
                backList.add(poly);
            }
            else if (side == BSPLine.SPANNING) {
                BSPPolygon front = clipBack(poly, node.partition);
                BSPPolygon back = clipFront(poly, node.partition);
                if (front != null) {
                    frontList.add(front);
                }
                if (back != null) {
                    backList.add(back);
                }

            }
        }

        // czyści i dostosowuje długości list
        collinearList.trimToSize();
        frontList.trimToSize();
        backList.trimToSize();
        node.polygons = collinearList;
        node.front = createNewNode(frontList);
        node.back = createNewNode(backList);

        // buduje przednie i tylne węzły
        buildNode(node.front);
        buildNode(node.back);
        if (node.back instanceof BSPTree.Leaf) {
            ((BSPTree.Leaf)node.back).isBack = true;
        }
    }



    /**
        Tworzy nowy węzeł na podstawie listy wielokątów. Jeśli żaden z
        wielokątów nie pełni roli ściany, tworzony jest liść.
    */
    protected BSPTree.Node createNewNode(List polygons) {

        BSPLine partition = choosePartition(polygons);

        // brak dostępnych podziałów — węzeł jest liściem
        if (partition == null) {
            BSPTree.Leaf leaf = new BSPTree.Leaf();
            leaf.polygons = polygons;
            buildLeaf(leaf);
            return leaf;
        }
        else {
            BSPTree.Node node = new BSPTree.Node();
            node.polygons = polygons;
            node.partition = partition;
            return node;
        }
    }


    /**
        Buduje liść drzewa, oblicza kilka dodatkowych wartości, jak
        ograniczenia liścia, wysokość podłogi i wysokość sufitu.
    */
    protected void buildLeaf(BSPTree.Leaf leaf) {

        if (leaf.polygons.size() == 0) {
            // liść reprezentuje pustą przestrzeń
            leaf.ceilHeight = Float.MAX_VALUE;
            leaf.floorHeight = Float.MIN_VALUE;
            leaf.bounds = null;
            return;
        }

        float minX = Float.MAX_VALUE;
        float maxX = Float.MIN_VALUE;
        float minY = Float.MAX_VALUE;
        float maxY = Float.MIN_VALUE;
        float minZ = Float.MAX_VALUE;
        float maxZ = Float.MIN_VALUE;

        // znajduje min y, maks y i ograniczenia
        Iterator i = leaf.polygons.iterator();
        while (i.hasNext()) {
            BSPPolygon poly = (BSPPolygon)i.next();
            for (int j=0; j<poly.getNumVertices(); j++) {
                Vector3D v = poly.getVertex(j);
                minX = Math.min(minX, v.x);
                maxX = Math.max(maxX, v.x);
                minY = Math.min(minY, v.y);
                maxY = Math.max(maxY, v.y);
                minZ = Math.min(minZ, v.z);
                maxZ = Math.max(maxZ, v.z);
            }
        }

        // znajduje dowolną poziomą powierzchnię
        i = leaf.polygons.iterator();
        while (i.hasNext()) {
            BSPPolygon poly = (BSPPolygon)i.next();
            // jeśli podłoga
            if (poly.getNormal().y == 1) {
                float y = poly.getVertex(0).y;
                if (y > minY && y < maxY) {
                    minY = y;
                }
            }
        }

        // ustawia wartości reprezentowane w liściu
        leaf.ceilHeight = maxY;
        leaf.floorHeight = minY;
        leaf.bounds = new Rectangle(
            (int)Math.floor(minX), (int)Math.floor(minZ),
            (int)Math.ceil(maxX-minX+1),
            (int)Math.ceil(maxZ-minZ+1));
    }



    /**
        Z listy wielokątów wybiera linię, która będzie pełnić rolę linii
        podziału. Metoda po prostu zwraca linię stworzoną na podstawie
        pierwszego pionowego wielokąty (ściany) lub wartość null, jeśli
        na liście nie ma takich wielokątów. Można w tym miejscu zastosować
        bardziej inteligentną metodę wybierającą linię podziału w taki
        sposób, by zminimalizować liczbę dzielonych wielokątów i
        doprowadzić do stworzenia bardziej wyważonego drzewa BSP.
    */
    protected BSPLine choosePartition(List polygons) {
        for (int i=0; i<polygons.size(); i++) {
            BSPPolygon poly = (BSPPolygon)polygons.get(i);
            if (poly.isWall()) {
                return new BSPLine(poly);
            }
        }
        return null;
    }


    /**
        Odcina część wielokąta znajdującą się z przodu linii przekazanej
        w formie argumentu. Zwracany wielokąt jest jego częścią
        znajdującą się z tyłu linii podziału. Zwraca wartość null, jeśli
        dana linia nie przecina wielokąta. Oryginalny wielokąt pozostaje
        niezmieniony.
    */
    protected BSPPolygon clipFront(BSPPolygon poly, BSPLine line) {
        return clip(poly, line, BSPLine.FRONT);
    }


    /**
        Odcina część wielokąta znajdującą się z tyłu linii przekazanej
        w formie argumentu. Zwracany wielokąt jest jego częścią
        znajdującą się z przodu linii podziału. Zwraca wartość null,
        jeśli dana linia nie przecina wielokąta. Oryginalny wielokąt
        pozostaje niezmieniony.
    */
    protected BSPPolygon clipBack(BSPPolygon poly, BSPLine line) {
        return clip(poly, line, BSPLine.BACK);
    }


    /**
        Przycina wielokąt BSPPolygon w taki sposób, by jego część
        znajdująca się z określonej strony linii podziału BSPLine.FRONT
        lub BSPLine.BACK) została usunięta; zwraca przycięty wielokąt.
        Zwraca wartość null, jeśli dana linia nie przecina wielokąta.
        Oryginalny wielokąt pozostaje niezmieniony.
    */
    protected BSPPolygon clip(BSPPolygon poly, BSPLine line, int clipSide)
    {
        ArrayList vertices = new ArrayList();
        BSPLine polyEdge = new BSPLine();

        // dodaje wierzchołki, które nie znajdują się po tej stronie linii
        Point2D.Float intersection = new Point2D.Float();
        for (int i=0; i<poly.getNumVertices(); i++) {
            int next = (i+1) % poly.getNumVertices();
            Vector3D v1 = poly.getVertex(i);
            Vector3D v2 = poly.getVertex(next);
            int side1 = line.getSideThin(v1.x, v1.z);
            int side2 = line.getSideThin(v2.x, v2.z);
            if (side1 != clipSide) {
                vertices.add(v1);
            }

            if ((side1 == BSPLine.FRONT && side2 == BSPLine.BACK) ||
                (side2 == BSPLine.FRONT && side1 == BSPLine.BACK))
            {
                // upewnia się, że v1.z < v2.z
                if (v1.z > v2.z) {
                    Vector3D temp = v1;
                    v1 = v2;
                    v2 = temp;
                }
                polyEdge.setLine(v1.x, v1.z, v2.x, v2.z);
                float f = polyEdge.getIntersection(line);
                Vector3D tPoint = new Vector3D(
                    v1.x + f * (v2.x - v1.x),
                    v1.y + f * (v2.y - v1.y),
                    v1.z + f * (v2.z - v1.z));
                vertices.add(tPoint);
                // usuwa wszystkie stworzone T-złącza
                removeTJunctions(v1, v2, tPoint);
            }

        }

        // Usuwa wszystkie pokrywające się wierzchołki: (A->A) jest zamieniane na (A)
        for (int i=0; i<vertices.size(); i++) {
            Vector3D v = (Vector3D)vertices.get(i);
            Vector3D next = (Vector3D)vertices.get(
                (i+1) % vertices.size());
            if (v.equals(next)) {
                vertices.remove(i);
                i--;
            }
        }

        if (vertices.size() < 3) {
            return null;
        }

        // Tworzy wielokąt
        Vector3D[] array = new Vector3D[vertices.size()];
        vertices.toArray(array);
        return poly.clone(array);
    }



    /**
        Usuń z bieżącego drzewa wszystkie T-złącza wzdłuż linii definiowanej
        za pomocą pary (v1, v2). Znajdź wszystkie wielokąty przylegające
        krawędziami do tej linii i wstaw pomiędzy nimi punkty T-przecięcia.
    */
    protected void removeTJunctions(final Vector3D v1, final Vector3D v2, final Vector3D tPoint)
    {
        BSPTreeTraverser traverser = new BSPTreeTraverser(
            new BSPTreeTraverseListener() {
                public boolean visitPolygon(BSPPolygon poly,
                    boolean isBackLeaf)
                {
                    removeTJunctions(poly, v1, v2, tPoint);
                    return true;
                }
            }
        );
        traverser.traverse(currentTree);
    }


    /**
        Usuń wszystkie T-złącza z przekazanego wielokąta. Punkt T-przecięcia
        jest wstawiany pomiędzy punktami v1 i v2, jeśli pomiędzy nimi nie
        istnieją żadne inne punkty.
    */
    protected void removeTJunctions(BSPPolygon poly, Vector3D v1, Vector3D v2, Vector3D tPoint)
    {
        for (int i=0; i<poly.getNumVertices(); i++) {
            int next = (i+1) % poly.getNumVertices();
            Vector3D p1 = poly.getVertex(i);
            Vector3D p2 = poly.getVertex(next);
            if ((p1.equals(v1) && p2.equals(v2)) ||
                (p1.equals(v2) && p2.equals(v1)))
            {
                poly.insertVertex(next, tPoint);
                return;
            }
        }
    }


}
