/**
 * Copyright (c) 2011, The University of Southampton and the individual contributors.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without modification,
 * are permitted provided that the following conditions are met:
 *
 *   *  Redistributions of source code must retain the above copyright notice,
 *      this list of conditions and the following disclaimer.
 *
 *   *  Redistributions in binary form must reproduce the above copyright notice,
 *      this list of conditions and the following disclaimer in the documentation
 *      and/or other materials provided with the distribution.
 *
 *   *  Neither the name of the University of Southampton nor the names of its
 *      contributors may be used to endorse or promote products derived from this
 *      software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
 * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
package org.openimaj.image.processing.transform;

import java.util.ArrayList;
import java.util.List;

import org.openimaj.image.Image;
import org.openimaj.image.pixel.Pixel;
import org.openimaj.image.processor.ImageProcessor;
import org.openimaj.image.renderer.ScanRasteriser;
import org.openimaj.image.renderer.ScanRasteriser.ScanLineListener;
import org.openimaj.math.geometry.point.Point2d;
import org.openimaj.math.geometry.shape.Polygon;
import org.openimaj.math.geometry.shape.Rectangle;
import org.openimaj.math.geometry.shape.Shape;
import org.openimaj.math.geometry.transforms.TransformUtilities;
import org.openimaj.util.pair.Pair;

import Jama.Matrix;

/**
 * Implementation of a piecewise warp. The warp can be piecewise affine,
 * piecewise homographic or a mixture of the two. Basically this means you can
 * warp images represented by triangles, quads or a mixture of the two.
 * 
 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk)
 * 
 * @param <T>
 *            the pixel type
 * @param <I>
 *            the actual image of the concrete subclass
 */
public class PiecewiseMeshWarp<T, I extends Image<T, I>> implements ImageProcessor<I> {
        List<Pair<Shape>> matchingRegions;
        List<Matrix> transforms = new ArrayList<Matrix>();
        Rectangle bounds;

        /**
         * Construct the warp with a list of matching shapes (which must be either
         * quads or triangles). The pairs map from the measured/observed space to
         * the canonical space.
         * 
         * @param matchingRegions
         *            the matching shapes
         */
        public PiecewiseMeshWarp(List<Pair<Shape>> matchingRegions) {
                this.matchingRegions = matchingRegions;
                initTransforms();
        }

        protected final Matrix getTransform(Point2d p) {
                final int sz = matchingRegions.size();

                for (int i = 0; i < sz; i++) {
                        if (matchingRegions.get(i).secondObject().isInside(p)) {
                                return transforms.get(i);
                        }
                }
                return null;
        }

        /**
         * Get the shape in the observation space for a point in the canonical
         * space.
         * 
         * @param p
         *            point in the canonical space.
         * @return the matching shape in observed space
         */
        public Shape getMatchingShape(Point2d p) {
                for (int i = 0; i < matchingRegions.size(); i++) {
                        final Pair<Shape> matching = matchingRegions.get(i);
                        if (matching.secondObject().isInside(p)) {
                                return matching.firstObject();
                        }
                }
                return null;
        }

        /**
         * Get the shape pair index for a point in the canonical space.
         * 
         * @param p
         *            the point in canonical space.
         * @return the index of the matching point pair
         */
        public int getMatchingShapeIndex(Point2d p) {
                for (int i = 0; i < matchingRegions.size(); i++) {
                        final Pair<Shape> matching = matchingRegions.get(i);
                        if (matching.secondObject().isInside(p)) {
                                return i;
                        }
                }
                return -1;
        }

        protected void initTransforms() {
                bounds = new Rectangle(Float.MAX_VALUE, Float.MAX_VALUE, 0, 0);

                for (final Pair<Shape> shape : matchingRegions) {
                        final Polygon p1 = shape.firstObject().asPolygon();
                        final Polygon p2 = shape.secondObject().asPolygon();

                        bounds.x = (float) Math.min(bounds.x, p2.minX());
                        bounds.y = (float) Math.min(bounds.y, p2.minY());
                        bounds.width = (float) Math.max(bounds.width, p2.maxX());
                        bounds.height = (float) Math.max(bounds.height, p2.maxY());

                        if (p1.nVertices() == 3) {
                                transforms.add(getTransform3(polyMatchToPointsMatch(p2, p1)));
                        } else if (p1.nVertices() == 4) {
                                transforms.add(getTransform4(polyMatchToPointsMatch(p2, p1)));
                        } else {
                                throw new RuntimeException("Only polygons with 3 or 4 vertices are supported!");
                        }
                }

                bounds.width -= bounds.x;
                bounds.height -= bounds.y;
        }

        protected List<Pair<Point2d>> polyMatchToPointsMatch(Polygon pa, Polygon pb) {
                final List<Pair<Point2d>> pts = new ArrayList<Pair<Point2d>>();
                for (int i = 0; i < pa.nVertices(); i++) {
                        final Point2d pta = pa.getVertices().get(i);
                        final Point2d ptb = pb.getVertices().get(i);

                        pts.add(new Pair<Point2d>(pta, ptb));
                }
                return pts;
        }

        protected Matrix getTransform4(List<Pair<Point2d>> pts) {
                return TransformUtilities.homographyMatrixNorm(pts);
        }

        protected Matrix getTransform3(List<Pair<Point2d>> pts) {
                return TransformUtilities.affineMatrix(pts);
        }

        @Override
        public void processImage(final I image) {
                final int width = image.getWidth();
                final int height = image.getHeight();

                final I ret = image.newInstance(width, height);

                final Scan scan = new Scan(width, height, image, ret);

                for (int i = 0; i < matchingRegions.size(); i++) {
                        final Polygon from = matchingRegions.get(i).secondObject().asPolygon();
                        scan.tf = transforms.get(i);

                        ScanRasteriser.scanFill(from.points, scan);
                }

                image.internalAssign(ret);
        }

        /**
         * Transform the content of the input image into an output image of the
         * given dimensions.
         * 
         * @param image
         *            the input image
         * @param width
         *            the output width
         * @param height
         *            the output height
         * @return the output image
         */
        public I transform(final I image, int width, int height) {
                final I ret = image.newInstance(width, height);

                final Scan scan = new Scan(width, height, image, ret);

                for (int i = 0; i < matchingRegions.size(); i++) {
                        final Polygon from = matchingRegions.get(i).secondObject().asPolygon();
                        scan.tf = transforms.get(i);

                        ScanRasteriser.scanFill(from.points, scan);
                }

                return ret;
        }

        private class Scan implements ScanLineListener {
                private final Pixel p = new Pixel();
                private final int xmin = (int) Math.max(0, bounds.x);
                private final int ymin = (int) Math.max(0, bounds.y);
                private final int xmax;
                private final int ymax;
                private final I image;
                private final I ret;
                Matrix tf;

                Scan(int width, int height, I image, I ret) {
                        xmax = (int) Math.min(width, bounds.x + bounds.width);
                        ymax = (int) Math.min(height, bounds.y + bounds.height);
                        this.image = image;
                        this.ret = ret;
                }

                @Override
                public void process(int x1, int x2, int y) {
                        if (y < ymin || y > ymax)
                                return;

                        final int startx = Math.max(xmin, Math.min(x1, x2));
                        final int stopx = Math.min(xmax, Math.max(x1, x2));

                        for (int x = startx; x <= stopx; x++) {
                                p.x = x;
                                p.y = y;

                                p.transformInplace(tf);

                                ret.setPixel(x, y, image.getPixelInterp(p.x, p.y));
                        }
                }
        }
}