VanGoghTriangulator3D.java
/*
* Copyright (C) 2012 Alberto Irurueta Carro (alberto@irurueta.com)
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package com.irurueta.geometry;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
/**
* This class defines a triangulator for 3D polygons. Triangulators divide
* polygons into triangles, which are the simplest geometric figure.
* This implementation uses Van Gogh or Ear Cutting algorithm for triangulation.
*/
public class VanGoghTriangulator3D extends Triangulator3D {
/**
* Default orientation threshold which is 90ยบ.
*/
public static final double DEFAULT_ORIENTATION_THRESHOLD = Math.PI / 2.0;
/**
* Minimum allowed threshold.
*/
public static final double MIN_THRESHOLD = 0.0;
/**
* Number of 3D inhomogeneous coordinates.
*/
public static final int INHOM_COORDS = 3;
/**
* Returns triangulator method.
* Each method implementation will divide polygons into triangles using
* different techniques.
*
* @return Triangulator method.
*/
@Override
public TriangulatorMethod getMethod() {
return TriangulatorMethod.VAN_GOGH_TRIANGULATOR;
}
/**
* Triangulates provided polygon by dividing it into a set of triangles.
*
* @param polygon Polygon to be triangulated.
* @return List of triangles forming the polygon that has been triangulated.
* @throws TriangulatorException Raised if triangulation cannot be done.
* Usually this indicates numerical instability or polygon degeneracy.
*/
@Override
public List<Triangle3D> triangulate(final Polygon3D polygon) throws TriangulatorException {
// triangulation will modify provided list of vertices, so we make a copy
// of it
//original vertices
final var vertices = polygon.getVertices();
final var verticesCopy = new ArrayList<>(polygon.getVertices());
return internalTriangulate(verticesCopy, null, vertices);
}
/**
* Triangulates a polygon formed by provided vertices.
*
* @param vertices List of points considered as vertices of a polygon.
* @return List of triangles forming the polygon that has been triangulated.
* @throws TriangulatorException Raised if triangulation cannot be done.
* Usually this indicates numerical instability or polygon degeneracy.
*/
@Override
public List<Triangle3D> triangulate(final List<Point3D> vertices) throws TriangulatorException {
if (vertices.size() < MIN_VERTICES) {
throw new TriangulatorException();
}
// triangulation will modify provided list of vertices, so we make a copy
// of it
final var verticesCopy = new ArrayList<>(vertices);
return internalTriangulate(verticesCopy, null, vertices);
}
/**
* Triangulates a polygon formed by provided vertices.
*
* @param vertices List of points considered as vertices of a polygon.
* @param indices List where indices of original vertices will be stored.
* This list can be used to refer to the original order of vertices. Notice
* that vertices indices might be repeated because vertices might appear in
* more than one triangle after triangulation. If this parameter is null,
* indices won't be stored in this list.
* @return List of triangles forming the polygon that has been triangulated.
* @throws TriangulatorException Raised if triangulation cannot be done.
* Usually this indicates numerical instability or polygon degeneracy.
*/
@Override
public List<Triangle3D> triangulate(final List<Point3D> vertices, final List<int[]> indices)
throws TriangulatorException {
if (vertices.size() < MIN_VERTICES) {
throw new TriangulatorException();
}
// triangulation will modify provided list of vertices, so we make a copy
// of it
final var verticesCopy = new ArrayList<>(vertices);
return internalTriangulate(verticesCopy, indices, vertices);
}
/**
* Determines if provided triangle can be considered as an ear of the
* remaining polygon formed by provided vertices.
* An ear is usually a triangle located at a corner of a polygon.
* A triangle is considered an ear if no other vertex of the polygon lies
* within the triangle and if the triangle is not convex (is concave).
*
* @param triangle A triangle.
* @param polygonVertices A list of points forming the remaining polygon
* @return true if triangle is ear, false otherwise.
* @throws CoincidentPointsException Raised if orientation of polygons
* cannot be determined, usually because consecutive vertices in a polygon
* are coincident, there are numerical instabilities or polygon degeneracies.
*/
public static boolean isEar(final Triangle3D triangle, final List<Point3D> polygonVertices)
throws CoincidentPointsException {
boolean isInside;
boolean isReversed;
// in a counterclockwise polygon, reversed orientation means that
// triangle is not convex and cannot be an ear
final var triangleVertices = triangle.getVertices();
// check that no points in the polygon (aside from points belonging to
// the triangle) lie inside the triangle
for (final var testPoint : polygonVertices) {
// Do not compare with polygon elements which are triangle points
// if end is reached then polygon and triangle is equal and hence the
// polygon is the ear
if (triangleVertices.contains(testPoint)) {
continue;
}
isInside = triangle.isInside(testPoint);
isReversed = isPolygonOrientationReversed(triangleVertices, polygonVertices);
// if a point is inside the triangle or orientation is reversed, then
// it is not an ear
if (isInside || isReversed) {
return false;
}
}
// no points in the polygon where found inside the triangle and
// orientation is the same, so an ear is detected
return true;
}
/**
* Given the list of vertices of two polygons, determines if polygons have
* reversed orientation, or in other words, it the angle between the
* orientation of both polygons is larger than DEFAULT_ORIENTATION_THRESHOLD
* (i.e. 90 degrees or pi / 2 radians).
*
* @param vertices1 Vertices of 1st polygon.
* @param vertices2 Vertices of 2nd polygon.
* @return True if polygons have reversed orientation, false otherwise.
* @throws CoincidentPointsException Raised if orientation of polygons .
* cannot be determined, usually because consecutive vertices in a polygon
* are coincident, there are numerical instabilities or polygon degeneracies.
* @see Polygon3D#getAngleBetweenPolygons(List, List)
*/
public static boolean isPolygonOrientationReversed(final List<Point3D> vertices1, final List<Point3D> vertices2)
throws CoincidentPointsException {
return isPolygonOrientationReversed(vertices1, vertices2, DEFAULT_ORIENTATION_THRESHOLD);
}
/**
* Given the list of vertices of two polygons, determines if polygons have
* reversed orientation, or in other words, it the angle between the
* orientation of both polygons is larger than provided threshold.
*
* @param vertices1 Vertices of 1st polygon.
* @param vertices2 Vertices of 2nd polygon.
* @param threshold Angle threshold expressed in radians to determine if
* polygons have reversed orientation.
* @return True if polygons have reversed orientation, false otherwise.
* @throws IllegalArgumentException Raised if provided threshold is negative.
* @throws CoincidentPointsException Raised if orientation of polygons
* cannot be determined, usually because consecutive vertices in a polygon
* are coincident, there are numerical instabilities or polygon degeneracies.
* @see Polygon3D#getAngleBetweenPolygons(List, List)
*/
public static boolean isPolygonOrientationReversed(
final List<Point3D> vertices1, final List<Point3D> vertices2, final double threshold)
throws CoincidentPointsException {
if (threshold < MIN_THRESHOLD) {
throw new IllegalArgumentException();
}
return isOrientationReversed(Polygon3D.getAngleBetweenPolygons(vertices1, vertices2), threshold);
}
/**
* Given an angle, determines if orientation can be considered to be
* reversed.
*
* @param angle Angle in radians.
* @return True if absolute value of angle is larger than
* DEFAULT_ORIENTATION_THRESHOLD, false otherwise.
*/
public static boolean isOrientationReversed(final double angle) {
return isOrientationReversed(angle, DEFAULT_ORIENTATION_THRESHOLD);
}
/**
* Given an angle, determines if orientation can be considered to be
* reversed.
*
* @param angle Angle in radians.
* @param threshold Threshold to determine if orientation is reversed
* @return True if absolute value of angle is larger than provided
* threshold, false otherwise.
*/
public static boolean isOrientationReversed(final double angle, final double threshold) {
return Math.abs(angle) > Math.abs(threshold);
}
/**
* Internal method that computes the actual triangulation.
*
* @param verticesCopy List of points considered as verticesCopy of a
* polygon. This list will be modified after execution of this method
* @param indices List where indices of original verticesCopy will be
* stored.
* This list can be used to refer to the original order of verticesCopy.
* Notice that verticesCopy indices might be repeated because verticesCopy
* might appear in more than one triangle after triangulation. If this
* parameter is null, indices won't be stored in this list.
* @param originalVertices Reference to original list of vertices that won't
* be modified.
* @return List of triangles forming the polygon that has been triangulated.
* @throws TriangulatorException Raised if triangulation cannot be done.
* Usually this indicates numerical instability or polygon degeneracy.
*/
private static List<Triangle3D> internalTriangulate(
final List<Point3D> verticesCopy, final List<int[]> indices, final List<Point3D> originalVertices)
throws TriangulatorException {
if (verticesCopy.size() < MIN_VERTICES) {
throw new TriangulatorException();
}
final var result = new LinkedList<Triangle3D>();
boolean isEar;
boolean madeCut;
Triangle3D triangle = null;
// Second, apply algorithm
while (verticesCopy.size() > MIN_VERTICES) {
madeCut = false;
final var lastElement = verticesCopy.size() - 1;
for (int i = 0; i <= lastElement; i++) {
if (i == 0) {
if (triangle == null) {
// instantiate triangle if not already instantiated
triangle = new Triangle3D(verticesCopy.get(lastElement),
verticesCopy.get(0), verticesCopy.get(1));
} else {
triangle.setVertices(verticesCopy.get(lastElement),
verticesCopy.get(0), verticesCopy.get(1));
}
} else if (i == lastElement) {
triangle.setVertices(verticesCopy.get(lastElement - 1), verticesCopy.get(lastElement),
verticesCopy.get(0));
} else {
triangle.setVertices(verticesCopy.get(i - 1), verticesCopy.get(i), verticesCopy.get(i + 1));
}
try {
isEar = isEar(triangle, verticesCopy);
} catch (CoincidentPointsException e) {
isEar = false;
}
if (isEar) {
// If it is an ear, we build a face out of the triangle being
// cut and remove it from polygon by cutting it
result.add(triangle);
// so that it cannot be reused after being added
triangle = null;
// cut ear
verticesCopy.remove(i);
madeCut = true;
// Leave from FOR loop to loop again to new reduced verticesCopy set
break;
}
}
// if arrived here but no cut was made and polygon size contains
// more than 3 verticesCopy, then the algorithm failed for some reason
if (!madeCut) {
throw new TriangulatorException();
}
}
// instantiate final triangle
triangle = new Triangle3D(verticesCopy.get(0), verticesCopy.get(1), verticesCopy.get(2));
final var arePointsColinear = triangle.areVerticesColinear();
// only add final triangle if not co-linear (area greater than small
// threshold)
if (!arePointsColinear) {
result.add(triangle);
}
// add indices of triangles verticesCopy
computeIndices(originalVertices, result, indices);
return result;
}
/**
* Computes indices of resulting triangles vertices respect to original
* polygon vertices. Indices are stored in provided indices list.
*
* @param vertices Vertices of polygon.
* @param triangles Triangles obtained after triangulation.
* @param indices Indices of original positions of resulting triangle's
* vertices.
*/
private static void computeIndices(
final List<Point3D> vertices, final List<Triangle3D> triangles, final List<int[]> indices) {
if (indices != null) {
int vertexCounter;
int triangleVertexCounter;
int[] triangleIndices;
for (final var t : triangles) {
triangleVertexCounter = 0;
triangleIndices = new int[Triangle3D.NUM_VERTICES];
for (final var p1 : t.getVertices()) {
vertexCounter = 0;
for (final var p2 : vertices) {
if (p1 == p2) {
triangleIndices[triangleVertexCounter] = vertexCounter;
break;
}
vertexCounter++;
}
triangleVertexCounter++;
}
indices.add(triangleIndices);
}
}
}
}