This is an automated email from the ASF dual-hosted git repository. asf-gitbox-commits pushed a commit to branch geoapi-4.0 in repository https://gitbox.apache.org/repos/asf/sis.git
commit 6607faa5287f7dcebf70e444753549a0b009266f Author: jsorel <[email protected]> AuthorDate: Mon Oct 19 09:36:26 2026 +0200 fix(EarClipping): preserve normal direction in EarClipping --- .../operation/triangulate/EarClipping.java | 97 ++++++++--- .../main/org/apache/sis/maths/Maths.java | 29 ++++ .../operation/triangulate/EarClippingTest.java | 193 +++++++++++++++++++++ .../test/org/apache/sis/maths/MathsTest.java | 46 +++++ 4 files changed, 341 insertions(+), 24 deletions(-) diff --git a/incubator/src/org.apache.sis.geometry/main/org/apache/sis/geometries/operation/triangulate/EarClipping.java b/incubator/src/org.apache.sis.geometry/main/org/apache/sis/geometries/operation/triangulate/EarClipping.java index 41c77e90a8..00ed3a038d 100644 --- a/incubator/src/org.apache.sis.geometry/main/org/apache/sis/geometries/operation/triangulate/EarClipping.java +++ b/incubator/src/org.apache.sis.geometry/main/org/apache/sis/geometries/operation/triangulate/EarClipping.java @@ -25,6 +25,7 @@ import java.util.stream.IntStream; import org.apache.sis.geometries.DataPoints; import org.apache.sis.geometries.DataPointsType; import org.apache.sis.geometries.mesh.MeshPrimitive; +import org.apache.sis.geometries.operation.OperationException; import org.apache.sis.geometries.surface.Polygon; import org.apache.sis.maths.Array; import org.apache.sis.maths.Maths; @@ -44,10 +45,19 @@ import org.apache.sis.util.ArraysExt; * the polygon: the triangles reference the vertices instead of copying their positions, so that * all the attributes of the vertices are kept.</p> * + * <p>The triangles have the orientation of the exterior ring of the polygon: seen from any side, + * they turn in the same direction as the exterior ring, so a face of a solid keeps its normal.</p> + * * @author Johann Sorel */ public class EarClipping { + /** + * Largest area, relative to the square of the size of the polygon, enclosed by vertices left without ear. + * Those vertices are aligned or along the cuts joining the holes, and the area is the rounding errors. + */ + private static final double AREA_TOLERANCE = 1E-10; + /** * Result of a triangulation: the vertices of the triangles, and the triangles as indices of those vertices. * @@ -79,11 +89,17 @@ public class EarClipping { /** * Indices in {@link #source} of the vertices of the ring joining the holes to the exterior ring, without - * repeated consecutive positions and without the closing position. The ring is clockwise in the plane - * of the triangulation. + * repeated consecutive positions and without the closing position. The ring has the orientation of the + * exterior ring. */ private int[] ring; + /** + * Whether the {@linkplain #ring} is clockwise in the plane of the triangulation. + * The triangles are cut in the direction of the ring, so they have the same orientation. + */ + private boolean clockwise; + /** * For each vertex of the {@linkplain #ring}, the previous and next vertices which are not cut yet. * Cutting an ear unlinks its vertex from the ring. @@ -105,8 +121,10 @@ public class EarClipping { * * @param geometry geometry to triangulate * @return the vertices of the triangles and their indices. + * @throws OperationException if the polygon cannot be triangulated, which happens with an invalid polygon + * such as a polygon whose exterior ring intersects itself. */ - public Triangulation triangulateIndexed(Polygon geometry) { + public Triangulation triangulateIndexed(Polygon geometry) throws OperationException { source = geometry.getDataPoints(); final int[] axes = workingAxes(geometry.getExteriorRing().getDataPoints().getAttributeArray(DataPointsType.ATT_POSITION)); working = new Vector<?>[source.size()]; @@ -118,8 +136,10 @@ public class EarClipping { /** * Triangulates the given polygon into an indexed mesh holding all the attributes of the polygon. + * + * @throws OperationException if the polygon cannot be triangulated. */ - public MeshPrimitive.Triangles toMesh(Polygon polygon) { + public MeshPrimitive.Triangles toMesh(Polygon polygon) throws OperationException { final Triangulation triangulation = triangulateIndexed(polygon); final DataPoints vertices = triangulation.vertices(); final MeshPrimitive.Triangles mesh = new MeshPrimitive.Triangles(); @@ -133,20 +153,16 @@ public class EarClipping { /** * Returns the order of the coordinates to use for triangulating a polygon with the given positions, * to be given to {@link Vector#swizzle(int...)}. The triangulation works on the two first coordinates - * of that order. The axis along which the {@linkplain Maths#calculatePolygonNormal(Array) normal of the - * polygon} is the largest is moved after the two axes of the projection plane, so that a vertical polygon - * is not degenerate. If the polygon can be triangulated in its (x,y) plane, the order is unchanged. + * of that order. With three or more dimensions, the three first axes are in the {@linkplain Maths#projectionAxes + * projection order} of the {@linkplain Maths#calculatePolygonNormal(Array) normal of the polygon}: the axis along + * which the normal is the largest goes after the two axes of the projection plane, so that a vertical polygon is + * not degenerate, and the polygon is counterclockwise in that plane. The other axes keep their order. + * In two dimensions, the order is unchanged. */ static int[] workingAxes(final Array positions) { - final int dim = positions.getDimension(); - final int[] axes = ArraysExt.range(0, dim); - if (dim >= 3) { - final double[] normal = Maths.calculatePolygonNormal(positions); - final double nx = Math.abs(normal[0]), ny = Math.abs(normal[1]), nz = Math.abs(normal[2]); - final int drop = (nz >= nx && nz >= ny) ? 2 : (nx >= ny) ? 0 : 1; - //shift the following axes of the plane to the place of the dropped axis, which goes after them. - System.arraycopy(axes, drop + 1, axes, drop, 2 - drop); - axes[2] = drop; + final int[] axes = ArraysExt.range(0, positions.getDimension()); + if (axes.length >= 3) { + System.arraycopy(Maths.projectionAxes(Maths.calculatePolygonNormal(positions)), 0, axes, 0, 3); } return axes; } @@ -174,14 +190,13 @@ public class EarClipping { * ring, which stays a valid polygon, until only one triangle is left. * * @param joined indices in {@link #source} of the ring positions, the last one at the location of the first one. + * @throws OperationException if the vertices left without ear still enclose an area. */ - private void run(final int[] joined) { + private void run(final int[] joined) throws OperationException { //remove the repeated consecutive positions, and the closing position which repeats the first one. ring = IntStream.range(0, joined.length - 1).filter((i) -> !working[joined[i]].equals(working[joined[i + 1]])) .map((i) -> joined[i]).toArray(); - if (!Maths.isClockWise(Arrays.stream(joined).mapToObj((i) -> working[i]).toList())) { - ArraysExt.reverse(ring); - } + clockwise = Maths.isClockWise(Arrays.stream(joined).mapToObj((i) -> working[i]).toList()); final int n = ring.length; previous = new int[n]; next = new int[n]; @@ -192,9 +207,12 @@ public class EarClipping { angles = new Angle[n]; Arrays.fill(angles, Angle.UNKNOWN); - //walk around the ring, until a whole turn finds no ear, which should not happen if the geometry is correct. - int vertex = 0; - for (int remaining = n, attempts = 0; remaining >= 3 && attempts < remaining; vertex = next[vertex]) { + /* + * Walk around the ring, until a whole turn finds no ear. With a valid polygon, this happens only when + * the vertices left enclose no area, for example when they are aligned along the cut joining a hole. + */ + int vertex = 0, remaining = n; + for (int attempts = 0; remaining >= 3 && attempts < remaining; vertex = next[vertex]) { if (isConvex(vertex) && isEar(vertex)) { triangles.add(new int[] {ring[previous[vertex]], ring[vertex], ring[next[vertex]]}); //unlink the vertex, the angles at its neighbors may change. @@ -208,6 +226,37 @@ public class EarClipping { attempts++; } } + if (remaining >= 3 && !isDegenerate(vertex)) { + throw new OperationException("Cannot triangulate the polygon: no ear found among the " + remaining + + " vertices left, the polygon may be invalid, for example with a ring intersecting itself."); + } + } + + /** + * Returns whether the vertices which are not cut yet enclose no area, compared to the size of the polygon. + * The area is computed relatively to one of those vertices, for reducing the rounding errors. + * + * @param start a vertex which is not cut yet. + */ + private boolean isDegenerate(final int start) { + final Vector<?> origin = position(start); + final double ox = origin.get(0), oy = origin.get(1); + double area = 0; // twice the signed area. + int vertex = start; + do { + final Vector<?> a = position(vertex), b = position(next[vertex]); + area += (a.get(0) - ox) * (b.get(1) - oy) - (b.get(0) - ox) * (a.get(1) - oy); + vertex = next[vertex]; + } while (vertex != start); + double xmin = Double.POSITIVE_INFINITY, xmax = Double.NEGATIVE_INFINITY; + double ymin = Double.POSITIVE_INFINITY, ymax = Double.NEGATIVE_INFINITY; + for (final int index : ring) { + final Vector<?> p = working[index]; + xmin = Math.min(xmin, p.get(0)); xmax = Math.max(xmax, p.get(0)); + ymin = Math.min(ymin, p.get(1)); ymax = Math.max(ymax, p.get(1)); + } + final double size = Math.max(xmax - xmin, ymax - ymin); + return Math.abs(area) / 2 <= AREA_TOLERANCE * size * size; } /** @@ -222,7 +271,7 @@ public class EarClipping { */ private boolean isConvex(final int vertex) { if (angles[vertex] == Angle.UNKNOWN) { - final boolean convex = Maths.isConvex(position(previous[vertex]), position(vertex), position(next[vertex]), true); + final boolean convex = Maths.isConvex(position(previous[vertex]), position(vertex), position(next[vertex]), clockwise); angles[vertex] = convex ? Angle.CONVEX : Angle.CONCAVE; } return angles[vertex] == Angle.CONVEX; diff --git a/incubator/src/org.apache.sis.geometry/main/org/apache/sis/maths/Maths.java b/incubator/src/org.apache.sis.geometry/main/org/apache/sis/maths/Maths.java index 43b573aaa4..185505bc55 100644 --- a/incubator/src/org.apache.sis.geometry/main/org/apache/sis/maths/Maths.java +++ b/incubator/src/org.apache.sis.geometry/main/org/apache/sis/maths/Maths.java @@ -138,6 +138,35 @@ public final class Maths { return normal; } + /** + * Returns the order of the coordinates for projecting a planar figure on a coordinate plane without changing + * its orientation, to be given to {@link Vector#swizzle(int...)}. The projection plane is made of the two first + * axes of the returned order. The last axis is the one along which the normal is the largest, so that a figure + * perpendicular to another coordinate plane is not degenerate. The two first axes are ordered so that a figure + * seen counterclockwise from the side where the normal points is counterclockwise in the projection plane. + * For example, a triangle (a,b,c) whose normal (b−a)×(c−a) has the direction of the given normal is on the + * left side of {@linkplain #lineSide(ReadOnly.Vector, ReadOnly.Vector, ReadOnly.Vector) line side} once projected, + * and a ring is counterclockwise in the projection plane of its {@linkplain #calculatePolygonNormal(Array) normal}. + * + * <p>The orientation is kept because each component of the normal is twice the area of the figure projected + * on the coordinate plane of the two following axes in cyclic order, positive if counterclockwise. A zero + * normal gives the (x,y) plane.</p> + * + * @param normal normal of the plane. Only the three first components are used, and only their direction matters. + * @return the order of the three axes: the two axes of the projection plane, then the axis left out. + * @throws IllegalArgumentException if the normal has less than 3 components + */ + public static int[] projectionAxes(double[] normal) { + if (normal.length < 3) { + throw new IllegalArgumentException("The normal shall have at least 3 components, found " + normal.length + "."); + } + final double nx = Math.abs(normal[0]), ny = Math.abs(normal[1]), nz = Math.abs(normal[2]); + final int drop = (nz >= nx && nz >= ny) ? 2 : (nx >= ny) ? 0 : 1; + //the cyclic order keeps the handedness, then swapping the plane axes reverses the orientation. + final int u = (drop + 1) % 3, v = (drop + 2) % 3; + return (normal[drop] < 0) ? new int[] {v, u, drop} : new int[] {u, v, drop}; + } + public static double[] subtract(float[] A, float[] B){ return new double[] { A[0] - (double) B[0], diff --git a/incubator/src/org.apache.sis.geometry/test/org/apache/sis/geometries/operation/triangulate/EarClippingTest.java b/incubator/src/org.apache.sis.geometry/test/org/apache/sis/geometries/operation/triangulate/EarClippingTest.java new file mode 100644 index 0000000000..a649a46445 --- /dev/null +++ b/incubator/src/org.apache.sis.geometry/test/org/apache/sis/geometries/operation/triangulate/EarClippingTest.java @@ -0,0 +1,193 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You 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 org.apache.sis.geometries.operation.triangulate; + +import java.util.ArrayList; +import java.util.List; +import org.opengis.referencing.crs.CoordinateReferenceSystem; +import org.apache.sis.geometries.DataPoints; +import org.apache.sis.geometries.DataPointsType; +import org.apache.sis.geometries.Geometries; +import org.apache.sis.geometries.GeometryFactory; +import org.apache.sis.geometries.curve.LinearRing; +import org.apache.sis.geometries.operation.OperationException; +import org.apache.sis.geometries.surface.Polygon; +import org.apache.sis.maths.Maths; +import org.apache.sis.maths.NDArrays; +import org.apache.sis.maths.Vectors; +import org.apache.sis.referencing.CommonCRS; + +// Test dependencies +import static org.junit.jupiter.api.Assertions.*; +import org.junit.jupiter.api.Test; + + +/** + * Tests {@link EarClipping}. + * + * @author Johann Sorel (Geomatys) + */ +public class EarClippingTest { + + private static final CoordinateReferenceSystem CRS2D = CommonCRS.WGS84.normalizedGeographic(); + + private static final CoordinateReferenceSystem CRS3D = Geometries.getUndefinedCRS(3); + + /** + * Each face of a box, with its exterior ring in both directions, gives two triangles which turn in the + * direction of the ring. The faces perpendicular to every axis are tested, in particular those of normal + * along y which were projected on a plane reversing their orientation. + */ + @Test + public void testFaceOrientation() { + final double x0 = 0, y0 = 0, z0 = 0, x1 = 2, y1 = 3, z1 = 4; + final double[][] faces = { + {x0,y0,z0, x0,y0,z1, x0,y1,z1, x0,y1,z0, x0,y0,z0}, + {x1,y0,z0, x1,y1,z0, x1,y1,z1, x1,y0,z1, x1,y0,z0}, + {x0,y0,z0, x1,y0,z0, x1,y0,z1, x0,y0,z1, x0,y0,z0}, + {x0,y1,z0, x0,y1,z1, x1,y1,z1, x1,y1,z0, x0,y1,z0}, + {x0,y0,z0, x0,y1,z0, x1,y1,z0, x1,y0,z0, x0,y0,z0}, + {x0,y0,z1, x1,y0,z1, x1,y1,z1, x0,y1,z1, x0,y0,z1} + }; + final double[] areas = {12, 12, 8, 8, 6, 6}; + for (int i = 0; i < faces.length; i++) { + assertOriented(polygon(CRS3D, faces[i]), areas[i], 2); + assertOriented(polygon(CRS3D, reverse(faces[i], 3)), areas[i], 2); + } + } + + /** + * A polygon with a hole gives triangles which turn in the direction of the exterior ring, + * in a vertical plane of normal along y and in an oblique plane, with the ring in both directions. + */ + @Test + public void testHoleOrientation() { + final double[] exterior = {0,0, 6,0, 6,4, 0,4, 0,0}; + final double[] hole = {2,1, 2,3, 4,3, 4,1, 2,1}; + final double area = 24 - 4; + //the plane y = 1, and an oblique plane made of two orthonormal vectors. + final double[][][] planes = { + {{0, 1, 0}, {1, 0, 0}, {0, 0, 1}}, + {{5, -2, 3}, {1/3., 2/3., 2/3.}, {2/3., 1/3., -2/3.}} + }; + for (final double[][] plane : planes) { + for (final boolean reversed : new boolean[] {false, true}) { + final double[] e = toPlane(reversed ? reverse(exterior, 2) : exterior, plane); + final double[] h = toPlane(reversed ? reverse(hole, 2) : hole, plane); + assertOriented(polygon(CRS3D, e, h), area, 8); + } + } + } + + /** + * In two dimensions, the triangles turn in the direction of the exterior ring, whether it is counterclockwise + * or clockwise. The polygon is concave, and has aligned positions. + */ + @Test + public void testOrientation2D() { + final double[] shape = {0,0, 2,0, 4,0, 4,1, 1,1, 1,4, 0,4, 0,0}; + for (final boolean reversed : new boolean[] {false, true}) { + final Polygon polygon = polygon(CRS2D, reversed ? reverse(shape, 2) : shape); + final EarClipping.Triangulation triangulation = new EarClipping().triangulateIndexed(polygon); + final DataPoints vertices = triangulation.vertices(); + final int[] triangles = triangulation.triangles(); + double area = 0; + for (int i = 0; i < triangles.length; i += 3) { + final double side = Maths.lineSide(vertices.getPosition(triangles[i]), + vertices.getPosition(triangles[i+1]), + vertices.getPosition(triangles[i+2])); + assertTrue(reversed ? side < 0 : side > 0, "The triangle shall turn in the direction of the ring."); + area += Math.abs(side) / 2; + } + assertEquals(7, area, 1E-12); + } + } + + /** + * A ring which intersects itself cannot be triangulated, which shall be reported instead of returning + * the triangles found before the failure. + */ + @Test + public void testSelfIntersectingRing() { + final Polygon bowTie = polygon(CRS2D, new double[] {0,0, 2,2, 2,0, 0,2, 0,0}); + assertThrows(OperationException.class, () -> new EarClipping().triangulateIndexed(bowTie)); + } + + /** + * Triangulates the given polygon and verifies that each triangle turns in the direction of the exterior ring, + * which is that its normal has the direction of the normal of the ring. Also verifies the area and the number + * of triangles. + */ + private static void assertOriented(final Polygon polygon, final double area, final int count) { + final double[] normal = Maths.calculatePolygonNormal( + polygon.getExteriorRing().getDataPoints().getAttributeArray(DataPointsType.ATT_POSITION)); + final EarClipping.Triangulation triangulation = new EarClipping().triangulateIndexed(polygon); + final DataPoints vertices = triangulation.vertices(); + final int[] triangles = triangulation.triangles(); + assertEquals(count * 3, triangles.length, "Number of triangles."); + double sum = 0; + for (int i = 0; i < triangles.length; i += 3) { + final double[] a = vertices.getPosition(triangles[i ]).toArrayDouble(); + final double[] b = vertices.getPosition(triangles[i+1]).toArrayDouble(); + final double[] c = vertices.getPosition(triangles[i+2]).toArrayDouble(); + final double[] n = Vectors.cross(Vectors.subtract(b, a), Vectors.subtract(c, a)); + assertTrue(Vectors.dot(n, normal) > 0, "The triangle shall turn in the direction of the exterior ring."); + sum += Vectors.length(n) / 2; + } + assertEquals(area, sum, 1E-9); + } + + /** + * Creates a polygon from the coordinates of its exterior ring followed by those of its holes. + */ + private static Polygon polygon(final CoordinateReferenceSystem crs, final double[] exterior, final double[]... holes) { + final List<LinearRing> interiors = new ArrayList<>(); + for (final double[] hole : holes) { + interiors.add(ring(crs, hole)); + } + return GeometryFactory.DEFAULT.createPolygon(ring(crs, exterior), interiors); + } + + private static LinearRing ring(final CoordinateReferenceSystem crs, final double... coordinates) { + return GeometryFactory.DEFAULT.createLinearRing(GeometryFactory.DEFAULT.createDataPoints(NDArrays.of(crs, coordinates))); + } + + /** + * Returns the positions in reverse order, each position having the given number of coordinates. + */ + private static double[] reverse(final double[] coordinates, final int dimension) { + final double[] reversed = new double[coordinates.length]; + for (int i = 0; i < coordinates.length; i += dimension) { + System.arraycopy(coordinates, i, reversed, coordinates.length - dimension - i, dimension); + } + return reversed; + } + + /** + * Converts (u,v) coordinates to three-dimensional coordinates in the plane made of an origin and two vectors. + */ + private static double[] toPlane(final double[] uv, final double[][] plane) { + final double[] origin = plane[0], u = plane[1], v = plane[2]; + final double[] xyz = new double[uv.length / 2 * 3]; + for (int i = 0, j = 0; i < uv.length; i += 2) { + for (int k = 0; k < 3; k++) { + xyz[j++] = origin[k] + uv[i] * u[k] + uv[i+1] * v[k]; + } + } + return xyz; + } +} diff --git a/incubator/src/org.apache.sis.geometry/test/org/apache/sis/maths/MathsTest.java b/incubator/src/org.apache.sis.geometry/test/org/apache/sis/maths/MathsTest.java index ab7d3e59eb..140dde08a1 100644 --- a/incubator/src/org.apache.sis.geometry/test/org/apache/sis/maths/MathsTest.java +++ b/incubator/src/org.apache.sis.geometry/test/org/apache/sis/maths/MathsTest.java @@ -16,6 +16,8 @@ */ package org.apache.sis.maths; +import java.util.Arrays; + // Test dependencies import static org.junit.jupiter.api.Assertions.*; import org.junit.jupiter.api.Disabled; @@ -198,6 +200,50 @@ public class MathsTest { assertThrows(IllegalArgumentException.class, () -> Maths.calculatePolygonNormal(NDArrays.of(2, new double[] {0,0, 1,0, 0,1}))); } + /** + * Tests {@link Maths#projectionAxes(double[])} on the normals of the six faces of a cube. + * The axis left out is the one of the normal, and the order of the two others depends on its sign. + */ + @Test + public void testProjectionAxes() { + assertArrayEquals(new int[] {0, 1, 2}, Maths.projectionAxes(new double[] { 0, 0, 1})); + assertArrayEquals(new int[] {1, 0, 2}, Maths.projectionAxes(new double[] { 0, 0, -1})); + assertArrayEquals(new int[] {1, 2, 0}, Maths.projectionAxes(new double[] { 1, 0, 0})); + assertArrayEquals(new int[] {2, 1, 0}, Maths.projectionAxes(new double[] {-1, 0, 0})); + assertArrayEquals(new int[] {2, 0, 1}, Maths.projectionAxes(new double[] { 0, 1, 0})); + assertArrayEquals(new int[] {0, 2, 1}, Maths.projectionAxes(new double[] { 0, -1, 0})); + assertArrayEquals(new int[] {0, 1, 2}, Maths.projectionAxes(new double[] { 0, 0, 0}), "A zero normal gives the (x,y) plane."); + assertArrayEquals(new int[] {0, 1, 2}, Maths.projectionAxes(new double[] { 1, 1, 1}), "Ties leave out z first."); + assertThrows(IllegalArgumentException.class, () -> Maths.projectionAxes(new double[] {0, 1})); + } + + /** + * Tests that {@link Maths#projectionAxes(double[])} keeps the orientation: a triangle whose normal has the + * direction given to the method is counterclockwise once projected, and the reversed triangle clockwise. + */ + @Test + public void testProjectionAxesOrientation() { + final double[][] normals = { + {0, 0, 1}, {0, 0, -1}, {1, 0, 0}, {-1, 0, 0}, {0, 1, 0}, {0, -1, 0}, + {1, 2, 3}, {-3, 1, -2}, {0.5, -4, 0.1}, {-0.2, 0.3, -0.25} + }; + for (final double[] normal : normals) { + //two vectors of the plane such as t1 × t2 has the direction of the normal. + final double[] other = (Math.abs(normal[0]) < 0.9 * Vectors.length(normal)) ? new double[] {1, 0, 0} : new double[] {0, 1, 0}; + final double[] t1 = Vectors.cross(normal, other); + final double[] t2 = Vectors.cross(normal, t1); + final Vector<?> a = vector(0.3, -1.7, 2.1); + final Vector<?> b = vector(a.get(0) + t1[0], a.get(1) + t1[1], a.get(2) + t1[2]); + final Vector<?> c = vector(a.get(0) + t2[0], a.get(1) + t2[1], a.get(2) + t2[2]); + final int[] axes = Maths.projectionAxes(normal); + final String message = Arrays.toString(normal); + assertTrue(Maths.lineSide(a.swizzle(axes), b.swizzle(axes), c.swizzle(axes)) > 0, message); + assertTrue(Maths.lineSide(a.swizzle(axes), c.swizzle(axes), b.swizzle(axes)) < 0, message); + assertEquals(Math.abs(normal[axes[2]]), Math.max(Math.abs(normal[0]), Math.max(Math.abs(normal[1]), Math.abs(normal[2]))), + message + ": the axis left out shall be the largest component of the normal."); + } + } + @Test public void testNormalizedByte() { assertEquals(-1.0, Maths.normalizedByte(Byte.MIN_VALUE), 0.0);
