Triangle.java

Go to the documentation of this file.

/*******************************************************************************
 * Copyright (c) 2012 Stefan Profanter. All rights reserved. This program and the accompanying
 * materials are made available under the terms of the GNU Public License v3.0 which accompanies
 * this distribution, and is available at http://www.gnu.org/licenses/gpl.html
 * 
 * Contributors: Stefan Profanter - initial API and implementation, Year: 2012; Andrei Stoica -
 * refactored implementation during the Google Summer of Code 2014
 ******************************************************************************/
package edu.tum.cs.vis.model.util;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.concurrent.locks.Lock;

import javax.vecmath.Point2f;
import javax.vecmath.Point3f;
import javax.vecmath.Tuple3f;
import javax.vecmath.Vector3d;
import javax.vecmath.Vector3f;

import org.apache.log4j.Logger;

import processing.core.PConstants;
import processing.core.PGraphics;

public class Triangle extends DrawObject {

        private static final long       serialVersionUID                        = -5164768039180386782L;

        private static Logger           logger                                          = Logger.getLogger(Triangle.class);

        protected Point2f                       texPosition[];

        protected Vector3f                      normalVector                            = null;

        protected Vector3f                      cornerarea                                      = null;

        protected Point3f                       centroid;

        protected Set<Triangle>         neighbors                                       = new HashSet<Triangle>(3);

        protected Edge[]                        edges                                           = new Edge[3];

        private boolean                         isSharpTriangle                         = false;

        private boolean                         isSeedTriangle                          = false;

        private int                                     regionLabel                                     = -1;

        private final float[]           curvatureMinMaxValue            = { 0.0f, 0.0f, 0.0f };

        private boolean                         isCurvatureMinMaxValueInit      = false;

        private boolean                         isVisited                                       = false;

        public Triangle() {
                super(3);
        }

        public Triangle(Tuple3f p1, Tuple3f p2, Tuple3f p3) {
                this(new Vertex(p1), new Vertex(p2), new Vertex(p3));
        }

        public Triangle(Tuple3f p1, Vector3f normP1, Tuple3f p2, Vector3f normP2, Tuple3f p3,
                        Vector3f normP3) {
                super(3);
                position[0] = new Vertex(p1, normP1);
                position[1] = new Vertex(p2, normP2);
                position[2] = new Vertex(p3, normP3);
        }

        public Triangle(Vertex p1, Vertex p2, Vertex p3) {
                super(3);
                position[0] = p1;
                position[1] = p2;
                position[2] = p3;
        }

        public boolean addNeighbor(Triangle neighbor, Lock lock) {
                boolean add = false;

                add = isDirectNeighbor(neighbor, Thresholds.FAST_NEIGHBOR_DETECTION);

                if (add) {
                        if (lock != null)
                                lock.lock();
                        // to make sure neighbors is not cached
                        synchronized (neighbors) {
                                neighbors.add(neighbor);
                        }
                        synchronized (neighbor.neighbors) {
                                neighbor.neighbors.add(this);
                        }
                        if (lock != null)
                                lock.unlock();
                }
                return add;
        }

        public void addNeighbor(Triangle neighbor) {
                synchronized (neighbors) {
                        neighbors.add(neighbor);
                }
                synchronized (neighbor.neighbors) {
                        neighbor.neighbors.add(this);
                }

        }

        public void removeNeighbor(Triangle n) {
                if (neighbors != null) {
                        synchronized (neighbors) {
                                neighbors.remove(n);
                        }
                }
                if (n.neighbors != null) {
                        synchronized (n.neighbors) {
                                n.neighbors.remove(this);
                        }
                }
        }

        public void draw(PGraphics g, DrawSettings drawSettings) {
                applyColor(g, drawSettings);

                if (drawSettings != null && drawSettings.drawType == DrawType.POINTS) {

                        for (int i = 0; i < position.length; i++) {
                                if (position[i].overrideColor != null) {
                                        g.stroke(position[i].overrideColor.getRed(),
                                                        position[i].overrideColor.getGreen(),
                                                        position[i].overrideColor.getBlue());
                                        g.noFill();
                                } else if (drawSettings.getOverrideColor() == null && position[i].color != null) {
                                        g.stroke(position[i].color.getRed(), position[i].color.getGreen(),
                                                        position[i].color.getBlue());
                                        g.noFill();
                                }
                                g.point(position[i].x, position[i].y, position[i].z);
                        }
                } else {
                        g.beginShape(PConstants.TRIANGLES);
                        if (appearance == null || appearance.getImageReference() == null /*no appearance*/
                                        || drawSettings.getOverrideColor() != null /*override*/
                                        || position[0].overrideColor != null /* points have colors */) {
                                // no texture only color

                                for (int i = 0; i < position.length; i++) {

                                        if (drawSettings != null && drawSettings.drawType == DrawType.LINES) {
                                                if (position[i].overrideColor != null) {
                                                        g.stroke(position[i].overrideColor.getRed(),
                                                                        position[i].overrideColor.getGreen(),
                                                                        position[i].overrideColor.getBlue());
                                                        g.noFill();
                                                } else if (drawSettings.getOverrideColor() == null
                                                                && position[i].color != null) {
                                                        g.stroke(position[i].color.getRed(), position[i].color.getGreen(),
                                                                        position[i].color.getBlue());
                                                        g.noFill();
                                                }
                                        } else {
                                                if (position[i].overrideColor != null) {
                                                        g.fill(position[i].overrideColor.getRed(),
                                                                        position[i].overrideColor.getGreen(),
                                                                        position[i].overrideColor.getBlue());
                                                } else if ((drawSettings == null || drawSettings.getOverrideColor() == null)
                                                                && position[i].color != null) {
                                                        g.fill(position[i].color.getRed(), position[i].color.getGreen(),
                                                                        position[i].color.getBlue());
                                                }
                                        }

                                        if (position[i].getNormalVector() != null)
                                                g.normal(position[i].getNormalVector().x, position[i].getNormalVector().y,
                                                                position[i].getNormalVector().z);
                                        g.vertex(position[i].x, position[i].y, position[i].z);
                                }

                        } else {
                                // has texture
                                g.texture(appearance.getImageReference());

                                for (int i = 0; i < position.length; i++) {

                                        g.vertex(position[i].x, position[i].y, position[i].z, texPosition[i].x,
                                                        texPosition[i].y);

                                }

                        }
                        g.endShape();
                }
        }

        public float getArea() {
                if (position.length == 3) {

                        Point3f v = (Point3f) position[1].clone();
                        v.sub(position[0]);
                        Point3f w = (Point3f) position[2].clone();
                        w.sub(position[0]);

                        Vector3f v1 = new Vector3f(v);
                        Vector3f w1 = new Vector3f(w);

                        Vector3f cross = new Vector3f();
                        cross.cross(v1, w1);
                        return cross.length() / 2f;
                }

                logger.error("getArea not implemented for " + position.length + "-Triangle");
                return 0;
        }

        public Point3f getCentroid() {
                return centroid;
        }

        public Vector3f getCornerarea() {
                return cornerarea;
        }

        public Set<Triangle> getNeighbors() {
                return neighbors;
        }

        public List<Triangle> getNeighborsOfEdge(final Edge edge) {
                List<Triangle> toAdd = new ArrayList<Triangle>();
                for (Triangle t : neighbors) {
                        Edge[] tEdges = t.getEdges();
                        for (int i = 0; i < tEdges.length; ++i) {
                                if (edge.isDirectNeighbor(tEdges[i])) {
                                        toAdd.add(t);
                                }
                        }
                }
                return toAdd;
        }

        public Edge getCommonEdge(final Triangle triangle) {
                if (neighbors.contains(triangle)) {
                        Edge[] triangleEdges = triangle.getEdges();
                        for (int i = 0; i < edges.length; ++i) {
                                for (int j = 0; j < triangleEdges.length; ++j) {
                                        if (edges[i].isDirectNeighbor(triangleEdges[j])) {
                                                return edges[i];
                                        }
                                }
                        }
                }
                return null;
        }

        @Override
        public Edge[] getEdges() {
                return edges;
        }

        public Edge[] getSharpEdges() {
                int numSharpEdges = 0;
                for (int i = 0; i < edges.length; ++i) {
                        if (edges[i].isSharpEdge()) {
                                numSharpEdges++;
                        }
                }
                if (numSharpEdges == 3) {
                        return edges;
                }
                Edge[] sharpEdges = new Edge[numSharpEdges];
                numSharpEdges = 0;
                for (int i = 0; i < edges.length; ++i) {
                        if (edges[i].isSharpEdge()) {
                                sharpEdges[numSharpEdges++] = edges[i];
                        }
                }
                return sharpEdges;
        }

        public Edge[] getNonSharpEdges() {
                int numNonSharpEdges = 0;
                for (int i = 0; i < edges.length; ++i) {
                        if (!edges[i].isSharpEdge()) {
                                numNonSharpEdges++;
                        }
                }
                if (numNonSharpEdges == 3) {
                        return edges;
                }
                Edge[] nonSharpEdges = new Edge[numNonSharpEdges];
                if (numNonSharpEdges == 0) {
                        return nonSharpEdges;
                }
                numNonSharpEdges = 0;
                for (int i = 0; i < edges.length; ++i) {
                        if (!edges[i].isSharpEdge()) {
                                nonSharpEdges[numNonSharpEdges++] = edges[i];
                        }
                }
                return nonSharpEdges;
        }

        public Vertex getOppositeVertexFromEdge(Edge edge) {
                boolean flagNotDirectNeighbor = true;
                boolean flagSharpEdgeBounded = false;
                // first get the common edge section belonging to the triangle
                for (int i = 0; i < edges.length; ++i) {
                        if (edges[i].isDirectNeighbor(edge)) {
                                flagNotDirectNeighbor = false;
                                if (edges[i].isSharpEdge()) {
                                        flagSharpEdgeBounded = true;
                                        break;
                                }
                                edge = edges[i];
                                break;
                        }
                }

                if (flagNotDirectNeighbor) {
                        logger.warn(edge + " is not a direct neighbor of any edge of\n" + this.toString());
                        return null;
                }

                if (flagSharpEdgeBounded) {
                        return null;
                }
                // determine opposite vertex
                for (int i = 0; i < position.length; ++i) {
                        if (!edge.hasVertex(position[i])) {
                                return position[i];
                        }
                }
                // commented out the warning as returning null does not affect performance
                // logger.warn("Could not identify opposite vertex of\n" + edge + "\nfor\n" +
                // this.toString());
                return null;
        }

        public float[] getCurvatureValues() {
                return curvatureMinMaxValue;
        }

        public boolean getIsCurvatureMinMaxValueInit() {
                return isCurvatureMinMaxValueInit;
        }

        public void addSharpEdge(Edge edge) {
                for (int i = 0; i < edges.length; ++i) {
                        if (edges[i].isDirectNeighbor(edge)) {
                                edges[i].isSharpEdge(true);
                                return;
                        }
                }
        }

        public int getRegionLabel() {
                return regionLabel;
        }

        public double getDihedralAngle(Triangle t) {
                return this.getNormalVector().angle(t.getNormalVector());
        }

        public Vector3f getNormalVector() {
                return normalVector;
        }

        public Point2f[] getTexPosition() {
                return texPosition;
        }

        public boolean isVisited() {
                return isVisited;
        }

        public void setIsVisited(final boolean isVisited) {
                this.isVisited = isVisited;
        }

        public boolean intersectsRay(Point3f rayStart, Point3f rayEnd) {
                return intersectsRay(rayStart, rayEnd, null);
        }

        public boolean calculateNormalVector() {
                // Calculate normal vector for triangle
                Vector3f avgVertexNorm = new Vector3f();
                for (int i = 0; i < 3; i++) {
                        if (position[i].getNormalVector() == null) {
                                avgVertexNorm = null;
                                break;
                        }
                        avgVertexNorm.add(position[i].getNormalVector());
                }
                if (avgVertexNorm != null) {
                        avgVertexNorm.scale(1f / 3f);
                }

                Vector3f a = new Vector3f(position[0]);
                a.sub(position[1]);
                Vector3f b = new Vector3f(position[1]);
                b.sub(position[2]);

                /*Vector3f a = new Vector3f(position[1]);
                a.sub(position[0]);
                Vector3f b = new Vector3f(position[2]);
                b.sub(position[0]);*/
                Vector3f norm = new Vector3f();
                norm.cross(a, b);
                if (norm.lengthSquared() == 0) {
                        return false;
                }
                norm.normalize();

                if (avgVertexNorm != null && avgVertexNorm.dot(norm) < 0)
                        norm.scale(-1f);

                this.normalVector = norm;
                return true;
        }

        public boolean intersectsRay(Point3f p1, Point3f p2, Point3f intersectionPoint) {

                if (position.length != 3) {
                        System.out.println("intersectRay not implemented for not triangles!!");
                        return false;
                }

                Vector3d u, v, n; // triangle vectors
                Vector3d dir, w0, w; // ray vectors
                double r, a, b; // params to calc ray-plane intersect

                // get triangle edge vectors and plane normal
                u = new Vector3d(position[1]);
                u.sub(new Vector3d(position[0]));
                v = new Vector3d(position[2]);
                v.sub(new Vector3d(position[0]));

                n = new Vector3d();
                n.cross(u, v); // Normal vector
                if (n.equals(new Vector3d(0, 0, 0))) // triangle is degenerate
                        return false; // do not deal with this case

                dir = new Vector3d(p2);// ray direction vector
                dir.sub(new Vector3d(p1));

                w0 = new Vector3d(p1);
                w0.sub(new Vector3d(position[0]));

                a = -n.dot(w0);
                b = n.dot(dir);
                // SMALL_NUM 0.00000001 // anything that avoids division overflow
                if (Math.abs(b) < 0.00000001) { // ray is parallel to triangle plane
                        if (a == 0) // ray lies in triangle plane
                                return false;

                        return false; // ray disjoint from plane
                }

                // get intersect point of ray with triangle plane
                r = a / b;

                // if (r < 0.0) // ray goes away from triangle
                // return false; // => no intersect
                // for a segment, also test if (r > 1.0) => no intersect

                Point3f intersect = intersectionPoint;

                if (intersect == null)
                        intersect = new Point3f();

                intersect.set(dir); // intersect point of ray and plane
                intersect.scale((float) r);
                intersect.add(p1);

                // is I inside T?
                double uu, uv, vv, wu, wv, D;
                uu = new Vector3d(u).dot(u);
                uv = new Vector3d(u).dot(v);
                vv = new Vector3d(v).dot(v);
                w = new Vector3d(intersect);
                w.sub(new Vector3d(position[0]));
                wu = new Vector3d(w).dot(u);
                wv = new Vector3d(w).dot(v);
                D = uv * uv - uu * vv;

                // get and test parametric coords
                double s, t;
                s = (uv * wv - vv * wu) / D;
                if (s < 0.0 || s > 1.0) // I is outside T
                        return false;
                t = (uv * wu - uu * wv) / D;
                if (t < 0.0 || (s + t) > 1.0) // I is outside T
                        return false;

                return true; // I is in T
        }

        public boolean isDirectNeighbor(Triangle tr, final boolean fastDetection) {
                int eqCnt = 0;
                if (fastDetection == true) {
                        // fast detection based only on checking the vertices
                        boolean isNeighbor = false;
                        for (int i = 0; i < position.length; i++) {
                                if (i == 2 && eqCnt == 0)
                                        break; // if 2 of 3 points aren't equal, it is no neighbor
                                Vertex p1 = position[i];
                                for (Vertex p2 : tr.position) {
                                        if (p1.x == p2.x && p1.y == p2.y && p1.z == p2.z) {
                                                eqCnt++;
                                                break;
                                        }
                                }
                                if (eqCnt == 2) {
                                        isNeighbor = true; // two common vertices, so neighbors
                                } else if (eqCnt == 3) {
                                        return false; // similar triangles back to back
                                }
                        }
                        return isNeighbor;
                } else {
                        // slow detection based on edges
                        List<Edge> trEdges = new ArrayList<Edge>();
                        trEdges.addAll(Arrays.asList(tr.getEdges()));
                        for (int i = 0; i < edges.length; ++i) {
                                for (int j = 0; j < trEdges.size(); ++j) {
                                        if (edges[i].isDirectNeighbor(trEdges.get(j))) {
                                                eqCnt++;
                                                trEdges.remove(trEdges.get(j));
                                                break;
                                        }
                                }
                                if (eqCnt == 2) {
                                        return false;
                                }
                        }
                        // if one hit only happened the triangles are neighbors
                        if (eqCnt == 1) {
                                return true;
                        }
                        // otherwise they are not neighbors at all or just the same or back-faced
                        return false;
                }
        }

        public boolean isAdjacentNeighbor(Triangle tr) {

                int eqCnt = 0;
                boolean isNeighbor = false;

                for (int i = 0; i < 3; i++) {
                        if (i == 2 && eqCnt == 0)
                                break; // if 2 of 3 points aren't equal, it is no neighbor
                        Point3f p1 = position[i];
                        for (Point3f p2 : tr.position) {
                                if (p1 == p2) {
                                        eqCnt++;
                                        if (eqCnt == 2) {
                                                isNeighbor = true;
                                        }
                                        if (eqCnt == 3) {
                                                // if triangle has same position but is backface
                                                isNeighbor = false;
                                        }
                                        break;
                                }

                        }
                }
                return isNeighbor;
        }

        public void setCornerarea(Vector3f cornerarea) {
                this.cornerarea = cornerarea;
        }

        public void setNeighbors(Set<Triangle> neighbors) {
                this.neighbors = neighbors;
        }

        public void setNormalVector(Vector3f normalVector) {
                this.normalVector = normalVector;
        }

        public void setTexPosition(Point2f[] texPosition) {
                this.texPosition = texPosition;
        }

        public boolean containsEdge(Edge edge) {
                for (int i = 0; i < edges.length; ++i) {
                        if (edges[i].isEqualTo(edge)) {
                                return true;
                        }
                }
                return false;
        }

        public boolean isSharpTriangle() {
                return isSharpTriangle;
        }

        public boolean checkIsSharpTriangle() {
                if (position[0].isSharpVertex() && position[1].isSharpVertex()
                                && position[2].isSharpVertex()) {
                        this.isSharpTriangle = true;
                        return true;
                }
                return false;
        }

        public void setRegionLabel(final int newLabel) {
                this.regionLabel = newLabel;
        }

        public int numOfSharpVertices() {
                int cont = 0;
                for (int i = 0; i < position.length; ++i) {
                        if (position[i].isSharpVertex()) {
                                cont++;
                        }
                }
                return cont;
        }

        public void updateEdges() {
                for (int j = 0; j < position.length; j++) {
                        edges[j] = new Edge(position[(j + 2) % position.length], position[(j + 1)
                                        % position.length]);
                }
        }

        public boolean updateIsSeedTriangle() {
                int numOfSharpVertices = this.numOfSharpVertices();
                if (numOfSharpVertices == 0) {
                        if (((position[0].getClusterCurvatureVal()[0] == position[1].getClusterCurvatureVal()[0]) && (position[1]
                                        .getClusterCurvatureVal()[0] == position[2].getClusterCurvatureVal()[0]))
                                        && ((position[0].getClusterCurvatureVal()[1] == position[1]
                                                        .getClusterCurvatureVal()[1]) && (position[1].getClusterCurvatureVal()[1] == position[2]
                                                        .getClusterCurvatureVal()[1]))
                                        && ((position[0].getClusterCurvatureVal()[2] == position[1]
                                                        .getClusterCurvatureVal()[2]) && (position[1].getClusterCurvatureVal()[2] == position[2]
                                                        .getClusterCurvatureVal()[2]))) {
                                setCurvatureLevels(position[0].getClusterCurvatureVal()[0],
                                                position[0].getClusterCurvatureVal()[1],
                                                position[0].getClusterCurvatureVal()[2]);
                                this.isSeedTriangle = true;
                                return true;
                        }
                        this.isSeedTriangle = false;
                        return false;
                } else if (numOfSharpVertices == 1) {
                        Vertex[] v = new Vertex[2];
                        int cont = 0;
                        if (!position[0].isSharpVertex()) {
                                v[cont] = position[0];
                                ++cont;
                        }
                        if (!position[1].isSharpVertex()) {
                                v[cont] = position[1];
                                ++cont;
                        }
                        if (!position[2].isSharpVertex() && cont < 2) {
                                v[cont] = position[2];
                        }
                        if ((v[0].getClusterCurvatureVal()[0] == v[1].getClusterCurvatureVal()[0])
                                        && v[0].getClusterCurvatureVal()[1] == v[1].getClusterCurvatureVal()[1]
                                        && v[0].getClusterCurvatureVal()[2] == v[1].getClusterCurvatureVal()[2]) {
                                setCurvatureLevels(v[0].getClusterCurvatureVal()[0],
                                                v[0].getClusterCurvatureVal()[1], v[0].getClusterCurvatureVal()[2]);
                                this.isSeedTriangle = true;
                                return true;
                        }
                        this.isSeedTriangle = false;
                        return false;
                } else if (numOfSharpVertices == 2) {
                        for (int i = 0; i < position.length; ++i) {
                                if (position[i].isSharpVertex()) {
                                        setCurvatureLevels(position[i].getClusterCurvatureVal()[0],
                                                        position[i].getClusterCurvatureVal()[1],
                                                        position[i].getClusterCurvatureVal()[2]);
                                        this.isSeedTriangle = true;
                                        return true;
                                }
                        }
                        this.isSeedTriangle = false;
                        return false;
                }
                this.isSeedTriangle = false;
                return false;
        }

        public boolean isSeedTriangle() {
                return isSeedTriangle;
        }

        public void setCurvatureLevels(final float minCurvatureLevel, final float maxCurvatureLevel,
                        final float minMaxCurvatureLevel) {
                this.isCurvatureMinMaxValueInit = true;
                this.curvatureMinMaxValue[0] = minCurvatureLevel;
                this.curvatureMinMaxValue[1] = maxCurvatureLevel;
                this.curvatureMinMaxValue[2] = minMaxCurvatureLevel;
        }

        /*
         * (non-Javadoc)
         * @see edu.tum.cs.vis.model.util.DrawObject#updateCentroid()
         */
        @Override
        public void updateCentroid() {
                centroid = new Point3f(0, 0, 0);

                for (int i = 0; i < position.length; i++) {
                        centroid.add(position[i]);
                }
                centroid.scale(1f / position.length);
        }

        /*
         * (non-Javadoc)
         * @see java.lang.Object#toString()
         */
        @Override
        public String toString() {
                String print = "Triangle: " + System.identityHashCode(this) + "\n";
                print = print + "V1: " + position[0] + " V2: " + position[1] + " V3: " + position[2] + "\n";
                print = print + "isSeedTriangle: " + isSeedTriangle + "\n";
                if (regionLabel != -1) {
                        print = print + "Region: " + regionLabel + "\n";
                        print = print + "KMin: " + curvatureMinMaxValue[0] + ", KMax: "
                                        + curvatureMinMaxValue[1] + ", KMinKMax : " + curvatureMinMaxValue[2] + "\n";
                } else {
                        print = print + "Region: unset" + "\n";
                }
                return print;
        }
}