Planes.java
/*
* 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.commons.geometry.euclidean.threed;
import java.text.MessageFormat;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.List;
import java.util.function.BiFunction;
import org.apache.commons.geometry.core.partitioning.HyperplaneBoundedRegion;
import org.apache.commons.geometry.core.partitioning.Split;
import org.apache.commons.geometry.core.partitioning.SplitLocation;
import org.apache.commons.geometry.euclidean.internal.EuclideanUtils;
import org.apache.commons.geometry.euclidean.threed.line.Line3D;
import org.apache.commons.geometry.euclidean.threed.line.LineConvexSubset3D;
import org.apache.commons.geometry.euclidean.twod.ConvexArea;
import org.apache.commons.geometry.euclidean.twod.Line;
import org.apache.commons.geometry.euclidean.twod.LineConvexSubset;
import org.apache.commons.geometry.euclidean.twod.Lines;
import org.apache.commons.geometry.euclidean.twod.RegionBSPTree2D;
import org.apache.commons.geometry.euclidean.twod.Vector2D;
import org.apache.commons.geometry.euclidean.twod.path.LinePath;
import org.apache.commons.numbers.core.Precision;
/** Class containing factory methods for constructing {@link Plane} and {@link PlaneSubset} instances.
*/
public final class Planes {
/** Utility class; no instantiation. */
private Planes() {
}
/** Build a plane from a point and two (on plane) vectors.
* @param p the provided point (on plane)
* @param u u vector (on plane)
* @param v v vector (on plane)
* @param precision precision context used to compare floating point values
* @return a new plane
* @throws IllegalArgumentException if the norm of the given values is zero, NaN, or infinite.
*/
public static EmbeddingPlane fromPointAndPlaneVectors(final Vector3D p, final Vector3D u, final Vector3D v,
final Precision.DoubleEquivalence precision) {
final Vector3D.Unit uNorm = u.normalize();
final Vector3D.Unit vNorm = uNorm.orthogonal(v);
final Vector3D.Unit wNorm = uNorm.cross(vNorm).normalize();
final double originOffset = -p.dot(wNorm);
return new EmbeddingPlane(uNorm, vNorm, wNorm, originOffset, precision);
}
/** Build a plane from a normal.
* Chooses origin as point on plane.
* @param normal normal direction to the plane
* @param precision precision context used to compare floating point values
* @return a new plane
* @throws IllegalArgumentException if the norm of the given values is zero, NaN, or infinite.
*/
public static Plane fromNormal(final Vector3D normal, final Precision.DoubleEquivalence precision) {
return fromPointAndNormal(Vector3D.ZERO, normal, precision);
}
/** Build a plane from a point and a normal.
*
* @param p point belonging to the plane
* @param normal normal direction to the plane
* @param precision precision context used to compare floating point values
* @return a new plane
* @throws IllegalArgumentException if the norm of the given values is zero, NaN, or infinite.
*/
public static Plane fromPointAndNormal(final Vector3D p, final Vector3D normal,
final Precision.DoubleEquivalence precision) {
final Vector3D.Unit unitNormal = normal.normalize();
final double originOffset = -p.dot(unitNormal);
return new Plane(unitNormal, originOffset, precision);
}
/** Build a plane from three points.
* <p>
* The plane is oriented in the direction of {@code (p2-p1) ^ (p3-p1)}
* </p>
*
* @param p1 first point belonging to the plane
* @param p2 second point belonging to the plane
* @param p3 third point belonging to the plane
* @param precision precision context used to compare floating point values
* @return a new plane
* @throws IllegalArgumentException if the points do not define a unique plane
*/
public static Plane fromPoints(final Vector3D p1, final Vector3D p2, final Vector3D p3,
final Precision.DoubleEquivalence precision) {
return fromPoints(Arrays.asList(p1, p2, p3), precision);
}
/** Construct a plane from a collection of points lying on the plane. The plane orientation is
* determined by the overall orientation of the point sequence. For example, if the points wind
* around the z-axis in a counter-clockwise direction, then the plane normal will point up the
* +z axis. If the points wind in the opposite direction, then the plane normal will point down
* the -z axis. The {@code u} vector for the plane is set to the first non-zero vector between
* points in the sequence (ie, the first direction in the path).
*
* @param pts collection of sequenced points lying on the plane
* @param precision precision context used to compare floating point values
* @return a new plane containing the given points
* @throws IllegalArgumentException if the given collection does not contain at least 3 points or the
* points do not define a unique plane
*/
public static Plane fromPoints(final Collection<Vector3D> pts, final Precision.DoubleEquivalence precision) {
return new PlaneBuilder(pts, precision).build();
}
/** Create a new plane subset from a plane and an embedded convex subspace area.
* @param plane embedding plane for the area
* @param area area embedded in the plane
* @return a new convex sub plane instance
*/
public static PlaneConvexSubset subsetFromConvexArea(final EmbeddingPlane plane, final ConvexArea area) {
if (area.isFinite()) {
// prefer a vertex-based representation for finite areas
final List<Vector3D> vertices = plane.toSpace(area.getVertices());
return fromConvexPlanarVertices(plane, vertices);
}
return new EmbeddedAreaPlaneConvexSubset(plane, area);
}
/** Create a new convex polygon from the given sequence of vertices. The vertices must define a unique
* plane, meaning that at least 3 unique vertices must be given. The given sequence is assumed to be closed,
* ie that an edge exists between the last vertex and the first.
* @param pts collection of points defining the convex polygon
* @param precision precision context used to compare floating point values
* @return a new convex polygon defined by the given sequence of vertices
* @throws IllegalArgumentException if fewer than 3 vertices are given or the vertices do not define a
* unique plane
* @see #fromPoints(Collection, Precision.DoubleEquivalence)
*/
public static ConvexPolygon3D convexPolygonFromVertices(final Collection<Vector3D> pts,
final Precision.DoubleEquivalence precision) {
final List<Vector3D> vertices = new ArrayList<>(pts.size());
final Plane plane = new PlaneBuilder(pts, precision).buildForConvexPolygon(vertices);
// make sure that the first point is not repeated at the end
final Vector3D firstPt = vertices.get(0);
final Vector3D lastPt = vertices.get(vertices.size() - 1);
if (firstPt.eq(lastPt, precision)) {
vertices.remove(vertices.size() - 1);
}
if (vertices.size() == EuclideanUtils.TRIANGLE_VERTEX_COUNT) {
return new SimpleTriangle3D(plane, vertices.get(0), vertices.get(1), vertices.get(2));
}
return new VertexListConvexPolygon3D(plane, vertices);
}
/** Construct a triangle from three vertices. The triangle plane is oriented such that the points
* are arranged in a counter-clockwise order when looking down the plane normal.
* @param p1 first vertex
* @param p2 second vertex
* @param p3 third vertex
* @param precision precision context used for floating point comparisons
* @return a triangle constructed from the three vertices
* @throws IllegalArgumentException if the points do not define a unique plane
*/
public static Triangle3D triangleFromVertices(final Vector3D p1, final Vector3D p2, final Vector3D p3,
final Precision.DoubleEquivalence precision) {
final Plane plane = fromPoints(p1, p2, p3, precision);
return new SimpleTriangle3D(plane, p1, p2, p3);
}
/** Construct a list of {@link Triangle3D} instances from a set of vertices and arrays of face indices.
* For example, the following code constructs a list of triangles forming a square pyramid.
* <pre>
* Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-10);
*
* Vector3D[] vertices = {
* Vector3D.ZERO,
* Vector3D.of(1, 0, 0),
* Vector3D.of(1, 1, 0),
* Vector3D.of(0, 1, 0),
* Vector3D.of(0.5, 0.5, 4)
* };
*
* int[][] faceIndices = {
* {0, 2, 1},
* {0, 3, 2},
* {0, 1, 4},
* {1, 2, 4},
* {2, 3, 4},
* {3, 0, 4}
* };
*
* List<Triangle3D> triangles = Planes.indexedTriangles(vertices, faceIndices, TEST_PRECISION);
* </pre>
* @param vertices vertices available for use in triangle construction
* @param faceIndices array of indices for each triangular face; each entry in the array is an array of
* 3 index values into {@code vertices}, defining the 3 vertices that will be used to construct the
* triangle
* @param precision precision context used for floating point comparisons
* @return a list of triangles constructed from the set of vertices and face indices
* @throws IllegalArgumentException if any face index array does not contain exactly 3 elements or a set
* of 3 vertices do not define a plane
* @throws IndexOutOfBoundsException if any index into {@code vertices} is out of bounds
*/
public static List<Triangle3D> indexedTriangles(final Vector3D[] vertices, final int[][] faceIndices,
final Precision.DoubleEquivalence precision) {
return indexedTriangles(Arrays.asList(vertices), faceIndices, precision);
}
/** Construct a list of {@link Triangle3D} instances from a set of vertices and arrays of face indices.
* @param vertices vertices available for use in triangle construction
* @param faceIndices array of indices for each triangular face; each entry in the array is an array of
* 3 index values into {@code vertices}, defining the 3 vertices that will be used to construct the
* triangle
* @param precision precision context used for floating point comparisons
* @return a list of triangles constructed from the set of vertices and face indices
* @throws IllegalArgumentException if any face index array does not contain exactly 3 elements or a set
* of 3 vertices do not define a plane
* @throws IndexOutOfBoundsException if any index into {@code vertices} is out of bounds
* @see #indexedTriangles(Vector3D[], int[][], Precision.DoubleEquivalence)
*/
public static List<Triangle3D> indexedTriangles(final List<? extends Vector3D> vertices, final int[][] faceIndices,
final Precision.DoubleEquivalence precision) {
final int numFaces = faceIndices.length;
final List<Triangle3D> triangles = new ArrayList<>(numFaces);
int[] face;
for (int i = 0; i < numFaces; ++i) {
face = faceIndices[i];
if (face.length != EuclideanUtils.TRIANGLE_VERTEX_COUNT) {
throw new IllegalArgumentException(MessageFormat.format(
"Invalid number of vertex indices for face at index {0}: expected {1} but found {2}",
i, EuclideanUtils.TRIANGLE_VERTEX_COUNT, face.length));
}
triangles.add(triangleFromVertices(
vertices.get(face[0]),
vertices.get(face[1]),
vertices.get(face[2]),
precision
));
}
return triangles;
}
/** Construct a list of {@link ConvexPolygon3D} instances from a set of vertices and arrays of face indices. Each
* face must contain at least 3 vertices but the number of vertices per face does not need to be constant.
* For example, the following code constructs a list of convex polygons forming a square pyramid.
* Note that the first face (the pyramid base) uses a different number of vertices than the other faces.
* <pre>
* Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-10);
*
* Vector3D[] vertices = {
* Vector3D.ZERO,
* Vector3D.of(1, 0, 0),
* Vector3D.of(1, 1, 0),
* Vector3D.of(0, 1, 0),
* Vector3D.of(0.5, 0.5, 4)
* };
*
* int[][] faceIndices = {
* {0, 3, 2, 1}, // square base
* {0, 1, 4},
* {1, 2, 4},
* {2, 3, 4},
* {3, 0, 4}
* };
*
* List<ConvexPolygon3D> polygons = Planes.indexedConvexPolygons(vertices, faceIndices, precision);
* </pre>
* @param vertices vertices available for use in convex polygon construction
* @param faceIndices array of indices for each triangular face; each entry in the array is an array of
* at least 3 index values into {@code vertices}, defining the vertices that will be used to construct the
* convex polygon
* @param precision precision context used for floating point comparisons
* @return a list of convex polygons constructed from the set of vertices and face indices
* @throws IllegalArgumentException if any face index array does not contain at least 3 elements or a set
* of vertices do not define a planar convex polygon
* @throws IndexOutOfBoundsException if any index into {@code vertices} is out of bounds
*/
public static List<ConvexPolygon3D> indexedConvexPolygons(final Vector3D[] vertices, final int[][] faceIndices,
final Precision.DoubleEquivalence precision) {
return indexedConvexPolygons(Arrays.asList(vertices), faceIndices, precision);
}
/** Construct a list of {@link ConvexPolygon3D} instances from a set of vertices and arrays of face indices. Each
* face must contain at least 3 vertices but the number of vertices per face does not need to be constant.
* @param vertices vertices available for use in convex polygon construction
* @param faceIndices array of indices for each triangular face; each entry in the array is an array of
* at least 3 index values into {@code vertices}, defining the vertices that will be used to construct the
* convex polygon
* @param precision precision context used for floating point comparisons
* @return a list of convex polygons constructed from the set of vertices and face indices
* @throws IllegalArgumentException if any face index array does not contain at least 3 elements or a set
* of vertices do not define a planar convex polygon
* @throws IndexOutOfBoundsException if any index into {@code vertices} is out of bounds
* @see #indexedConvexPolygons(Vector3D[], int[][], Precision.DoubleEquivalence)
*/
public static List<ConvexPolygon3D> indexedConvexPolygons(final List<? extends Vector3D> vertices,
final int[][] faceIndices, final Precision.DoubleEquivalence precision) {
final int numFaces = faceIndices.length;
final List<ConvexPolygon3D> polygons = new ArrayList<>(numFaces);
final List<Vector3D> faceVertices = new ArrayList<>();
int[] face;
for (int i = 0; i < numFaces; ++i) {
face = faceIndices[i];
if (face.length < EuclideanUtils.TRIANGLE_VERTEX_COUNT) {
throw new IllegalArgumentException(MessageFormat.format(
"Invalid number of vertex indices for face at index {0}: required at least {1} but found {2}",
i, EuclideanUtils.TRIANGLE_VERTEX_COUNT, face.length));
}
for (final int vertexIndex : face) {
faceVertices.add(vertices.get(vertexIndex));
}
polygons.add(convexPolygonFromVertices(
faceVertices,
precision
));
faceVertices.clear();
}
return polygons;
}
/** Get the boundaries of a 3D region created by extruding a polygon defined by a list of vertices. The ends
* ("top" and "bottom") of the extruded 3D region are flat while the sides follow the boundaries of the original
* 2D region.
* @param vertices vertices forming the 2D polygon to extrude
* @param plane plane to extrude the 2D polygon from
* @param extrusionVector vector to extrude the polygon vertices through
* @param precision precision context used to construct the 3D region boundaries
* @return the boundaries of the extruded 3D region
* @throws IllegalStateException if {@code vertices} contains only a single unique vertex
* @throws IllegalArgumentException if regions of non-zero size cannot be produced with the
* given plane and extrusion vector. This occurs when the extrusion vector has zero length
* or is orthogonal to the plane normal
* @see LinePath#fromVertexLoop(Collection, Precision.DoubleEquivalence)
* @see #extrude(LinePath, EmbeddingPlane, Vector3D, Precision.DoubleEquivalence)
*/
public static List<PlaneConvexSubset> extrudeVertexLoop(final List<Vector2D> vertices,
final EmbeddingPlane plane, final Vector3D extrusionVector, final Precision.DoubleEquivalence precision) {
final LinePath path = LinePath.fromVertexLoop(vertices, precision);
return extrude(path, plane, extrusionVector, precision);
}
/** Get the boundaries of the 3D region created by extruding a 2D line path. The ends ("top" and "bottom") of
* the extruded 3D region are flat while the sides follow the boundaries of the original 2D region. The path is
* converted to a BSP tree before extrusion.
* @param path path to extrude
* @param plane plane to extrude the path from
* @param extrusionVector vector to extrude the polygon points through
* @param precision precision precision context used to construct the 3D region boundaries
* @return the boundaries of the extruded 3D region
* @throws IllegalArgumentException if regions of non-zero size cannot be produced with the
* given plane and extrusion vector. This occurs when the extrusion vector has zero length
* or is orthogonal to the plane normal
* @see #extrude(RegionBSPTree2D, EmbeddingPlane, Vector3D, Precision.DoubleEquivalence)
*/
public static List<PlaneConvexSubset> extrude(final LinePath path, final EmbeddingPlane plane,
final Vector3D extrusionVector, final Precision.DoubleEquivalence precision) {
return extrude(path.toTree(), plane, extrusionVector, precision);
}
/** Get the boundaries of the 3D region created by extruding a 2D region. The ends ("top" and "bottom") of
* the extruded 3D region are flat while the sides follow the boundaries of the original 2D region.
* @param region region to extrude
* @param plane plane to extrude the region from
* @param extrusionVector vector to extrude the region points through
* @param precision precision precision context used to construct the 3D region boundaries
* @return the boundaries of the extruded 3D region
* @throws IllegalArgumentException if regions of non-zero size cannot be produced with the
* given plane and extrusion vector. This occurs when the extrusion vector has zero length
* or is orthogonal to the plane normal
*/
public static List<PlaneConvexSubset> extrude(final RegionBSPTree2D region, final EmbeddingPlane plane,
final Vector3D extrusionVector, final Precision.DoubleEquivalence precision) {
return new PlaneRegionExtruder(plane, extrusionVector, precision).extrude(region);
}
/** Get the unique intersection of the plane subset with the given line. Null is
* returned if no unique intersection point exists (ie, the line and plane are
* parallel or coincident) or the line does not intersect the plane subset.
* @param planeSubset plane subset to intersect with
* @param line line to intersect with this plane subset
* @return the unique intersection point between the line and this plane subset
* or null if no such point exists.
*/
static Vector3D intersection(final PlaneSubset planeSubset, final Line3D line) {
final Vector3D pt = planeSubset.getPlane().intersection(line);
return (pt != null && planeSubset.contains(pt)) ? pt : null;
}
/** Get the unique intersection of the plane subset with the given line subset. Null
* is returned if the underlying line and plane do not have a unique intersection
* point (ie, they are parallel or coincident) or the intersection point is unique
* but is not contained in both the line subset and plane subset.
* @param planeSubset plane subset to intersect with
* @param lineSubset line subset to intersect with
* @return the unique intersection point between this plane subset and the argument or
* null if no such point exists.
*/
static Vector3D intersection(final PlaneSubset planeSubset, final LineConvexSubset3D lineSubset) {
final Vector3D pt = intersection(planeSubset, lineSubset.getLine());
return (pt != null && lineSubset.contains(pt)) ? pt : null;
}
/** Validate that the actual plane contains the same points as the expected plane, throwing an exception if not.
* The subspace orientations of embedding planes are not considered.
* @param expected the expected plane
* @param actual the actual plane
* @throws IllegalArgumentException if the actual plane is not equivalent to the expected plane
*/
static void validatePlanesEquivalent(final Plane expected, final Plane actual) {
if (!expected.eq(actual, expected.getPrecision())) {
throw new IllegalArgumentException("Arguments do not represent the same plane. Expected " +
expected + " but was " + actual + ".");
}
}
/** Generic split method that uses performs the split using the subspace region of the plane subset.
* @param splitter splitting hyperplane
* @param subset the plane subset being split
* @param factory function used to create new plane subset instances
* @param <T> Plane subset implementation type
* @return the result of the split operation
*/
static <T extends PlaneSubset> Split<T> subspaceSplit(final Plane splitter, final T subset,
final BiFunction<? super EmbeddingPlane, ? super HyperplaneBoundedRegion<Vector2D>, T> factory) {
final EmbeddingPlane thisPlane = subset.getPlane().getEmbedding();
final Line3D intersection = thisPlane.intersection(splitter);
if (intersection == null) {
return getNonIntersectingSplitResult(splitter, subset);
} else {
final EmbeddingPlane embeddingPlane = subset.getPlane().getEmbedding();
// the lines intersect; split the subregion
final Vector3D intersectionOrigin = intersection.getOrigin();
final Vector2D subspaceP1 = embeddingPlane.toSubspace(intersectionOrigin);
final Vector2D subspaceP2 = embeddingPlane.toSubspace(intersectionOrigin.add(intersection.getDirection()));
final Line subspaceSplitter = Lines.fromPoints(subspaceP1, subspaceP2, thisPlane.getPrecision());
final Split<? extends HyperplaneBoundedRegion<Vector2D>> split =
subset.getEmbedded().getSubspaceRegion().split(subspaceSplitter);
final SplitLocation subspaceSplitLoc = split.getLocation();
if (SplitLocation.MINUS == subspaceSplitLoc) {
return new Split<>(subset, null);
} else if (SplitLocation.PLUS == subspaceSplitLoc) {
return new Split<>(null, subset);
}
final T minus = (split.getMinus() != null) ? factory.apply(thisPlane, split.getMinus()) : null;
final T plus = (split.getPlus() != null) ? factory.apply(thisPlane, split.getPlus()) : null;
return new Split<>(minus, plus);
}
}
/** Get a split result for cases where the splitting plane and the plane containing the subset being split
* do not intersect. Callers are responsible for ensuring that the planes involved do not actually intersect.
* @param <T> Plane subset implementation type
* @param splitter plane performing the splitting
* @param subset subset being split
* @return the split result for the non-intersecting split
*/
private static <T extends PlaneSubset> Split<T> getNonIntersectingSplitResult(
final Plane splitter, final T subset) {
final Plane plane = subset.getPlane();
final double offset = splitter.offset(plane);
final int comp = plane.getPrecision().compare(offset, 0.0);
if (comp < 0) {
return new Split<>(subset, null);
} else if (comp > 0) {
return new Split<>(null, subset);
} else {
return new Split<>(null, null);
}
}
/** Construct a convex polygon 3D from a plane and a list of vertices lying in the plane. Callers are
* responsible for ensuring that the vertices lie in the plane and define a convex polygon.
* @param plane the plane containing the convex polygon
* @param vertices vertices defining the closed, convex polygon. The must must contain at least 3 unique
* vertices and should not include the start vertex at the end of the list.
* @return a new convex polygon instance
* @throws IllegalArgumentException if the size of {@code vertices} if less than 3
*/
static ConvexPolygon3D fromConvexPlanarVertices(final Plane plane, final List<Vector3D> vertices) {
final int size = vertices.size();
if (size == EuclideanUtils.TRIANGLE_VERTEX_COUNT) {
return new SimpleTriangle3D(plane, vertices.get(0), vertices.get(1), vertices.get(2));
}
return new VertexListConvexPolygon3D(plane, vertices);
}
/** Convert a convex polygon defined by a plane and list of points into a triangle fan.
* @param plane plane containing the convex polygon
* @param vertices vertices defining the convex polygon
* @return a triangle fan representing the same area as the convex polygon
* @throws IllegalArgumentException if fewer than 3 vertices are given
*/
static List<Triangle3D> convexPolygonToTriangleFan(final Plane plane, final List<Vector3D> vertices) {
return EuclideanUtils.convexPolygonToTriangleFan(vertices,
tri -> new SimpleTriangle3D(plane, tri.get(0), tri.get(1), tri.get(2)));
}
/** Internal helper class used to construct planes from sequences of points. Instances can be also be
* configured to collect lists of unique points found during plane construction and validate that the
* defined region is convex.
*/
private static final class PlaneBuilder {
/** The point sequence to build a plane for. */
private final Collection<? extends Vector3D> pts;
/** Precision context used for floating point comparisons. */
private final Precision.DoubleEquivalence precision;
/** The start point from the point sequence. */
private Vector3D startPt;
/** The previous point from the point sequence. */
private Vector3D prevPt;
/** The previous vector from the point sequence, preceding from the {@code startPt} to {@code prevPt}. */
private Vector3D prevVector;
/** The computed {@code normal} vector for the plane. */
private Vector3D.Unit normal;
/** The x component of the sum of all cross products from adjacent vectors in the point sequence. */
private double crossSumX;
/** The y component of the sum of all cross products from adjacent vectors in the point sequence. */
private double crossSumY;
/** The z component of the sum of all cross products from adjacent vectors in the point sequence. */
private double crossSumZ;
/** If true, an exception will be thrown if the point sequence is discovered to be non-convex. */
private boolean requireConvex;
/** List that unique vertices discovered in the input sequence will be added to. */
private List<? super Vector3D> uniqueVertexOutput;
/** Construct a new build instance for the given point sequence and precision context.
* @param pts point sequence
* @param precision precision context used to perform floating point comparisons
*/
PlaneBuilder(final Collection<? extends Vector3D> pts, final Precision.DoubleEquivalence precision) {
this.pts = pts;
this.precision = precision;
}
/** Build a plane from the configured point sequence.
* @return a plane built from the configured point sequence
* @throws IllegalArgumentException if the points do not define a plane
*/
Plane build() {
if (pts.size() < EuclideanUtils.TRIANGLE_VERTEX_COUNT) {
throw nonPlanar();
}
pts.forEach(this::processPoint);
return createPlane();
}
/** Build a plane from the configured point sequence, validating that the points form a convex region
* and adding all discovered unique points to the given list.
* @param vertexOutput list that unique points discovered in the point sequence will be added to
* @return a plane created from the configured point sequence
* @throws IllegalArgumentException if the points do not define a plane or the {@code requireConvex}
* flag is true and the points do not define a convex area
*/
Plane buildForConvexPolygon(final List<? super Vector3D> vertexOutput) {
this.requireConvex = true;
this.uniqueVertexOutput = vertexOutput;
return build();
}
/** Process a point from the point sequence.
* @param pt
* @throws IllegalArgumentException if the points do not define a plane or the {@code requireConvex}
* flag is true and the points do not define a convex area
*/
private void processPoint(final Vector3D pt) {
if (prevPt == null) {
startPt = pt;
prevPt = pt;
if (uniqueVertexOutput != null) {
uniqueVertexOutput.add(pt);
}
} else if (!prevPt.eq(pt, precision)) { // skip duplicate points
final Vector3D vec = startPt.vectorTo(pt);
if (prevVector != null) {
processCrossProduct(prevVector.cross(vec));
}
if (uniqueVertexOutput != null) {
uniqueVertexOutput.add(pt);
}
prevPt = pt;
prevVector = vec;
}
}
/** Process the computed cross product of two vectors from the input point sequence. The vectors
* start at the first point in the sequence and point to adjacent points later in the sequence.
* @param cross the cross product of two vectors from the input point sequence
* @throws IllegalArgumentException if the points do not define a plane or the {@code requireConvex}
* flag is true and the points do not define a convex area
*/
private void processCrossProduct(final Vector3D cross) {
crossSumX += cross.getX();
crossSumY += cross.getY();
crossSumZ += cross.getZ();
final double crossNorm = cross.norm();
if (!precision.eqZero(crossNorm)) {
// the cross product has non-zero magnitude
if (normal == null) {
// save the first non-zero cross product as our normal
normal = cross.normalize();
} else {
final double crossDot = normal.dot(cross) / crossNorm;
// check non-planar before non-convex since the former is a more general type
// of issue
if (!precision.eq(1.0, Math.abs(crossDot))) {
throw nonPlanar();
} else if (requireConvex && crossDot < 0) {
throw nonConvex();
}
}
}
}
/** Construct the plane instance using the value gathered during point processing.
* @return the created plane instance
* @throws IllegalArgumentException if the point do not define a plane
*/
private Plane createPlane() {
if (normal == null) {
throw nonPlanar();
}
// flip the normal if needed to match the overall orientation of the points
if (normal.dot(Vector3D.of(crossSumX, crossSumY, crossSumZ)) < 0) {
normal = normal.negate();
}
// construct the plane
final double originOffset = -startPt.dot(normal);
return new Plane(normal, originOffset, precision);
}
/** Return an exception with a message stating that the points given to this builder do not
* define a plane.
* @return an exception stating that the points do not define a plane
*/
private IllegalArgumentException nonPlanar() {
return new IllegalArgumentException("Points do not define a plane: " + pts);
}
/** Return an exception with a message stating that the points given to this builder do not
* define a convex region.
* @return an exception stating that the points do not define a plane
*/
private IllegalArgumentException nonConvex() {
return new IllegalArgumentException("Points do not define a convex region: " + pts);
}
}
/** Class designed to create 3D regions by taking a 2D region and extruding from a base plane
* through an extrusion vector. The ends ("top" and "bottom") of the extruded 3D region are flat
* while the sides follow the boundaries of the original 2D region.
*/
private static final class PlaneRegionExtruder {
/** Base plane to extrude from. */
private final EmbeddingPlane basePlane;
/** Vector to extrude along; the extruded plane is translated from the base plane by this amount. */
private final Vector3D extrusionVector;
/** True if the extrusion vector points to the plus side of the base plane. */
private final boolean extrudingOnPlusSide;
/** Precision context used to create boundaries. */
private final Precision.DoubleEquivalence precision;
/** Construct a new instance that performs extrusions from {@code basePlane} along {@code extrusionVector}.
* @param basePlane base plane to extrude from
* @param extrusionVector vector to extrude along
* @param precision precision context used to construct boundaries
* @throws IllegalArgumentException if the given extrusion vector and plane produce regions
* of zero size
*/
PlaneRegionExtruder(final EmbeddingPlane basePlane, final Vector3D extrusionVector,
final Precision.DoubleEquivalence precision) {
this.basePlane = basePlane;
// Extruded plane; this forms the end of the 3D region opposite the base plane.
final EmbeddingPlane extrudedPlane = basePlane.translate(extrusionVector);
if (basePlane.contains(extrudedPlane)) {
throw new IllegalArgumentException(
"Extrusion vector produces regions of zero size: extrusionVector= " +
extrusionVector + ", plane= " + basePlane);
}
this.extrusionVector = extrusionVector;
this.extrudingOnPlusSide = basePlane.getNormal().dot(extrusionVector) > 0;
this.precision = precision;
}
/** Extrude the given 2D BSP tree using the configured base plane and extrusion vector.
* @param subspaceRegion region to extrude
* @return the boundaries of the extruded region
*/
public List<PlaneConvexSubset> extrude(final RegionBSPTree2D subspaceRegion) {
final List<PlaneConvexSubset> extrudedBoundaries = new ArrayList<>();
// add the boundaries
addEnds(subspaceRegion, extrudedBoundaries);
addSides(subspaceRegion, extrudedBoundaries);
return extrudedBoundaries;
}
/** Add the end ("top" and "bottom") of the extruded subspace region to the result list.
* @param subspaceRegion subspace region being extruded.
* @param result list to add the boundary results to
*/
private void addEnds(final RegionBSPTree2D subspaceRegion, final List<? super PlaneConvexSubset> result) {
// add the base boundaries
final List<ConvexArea> baseAreas = subspaceRegion.toConvex();
final List<PlaneConvexSubset> baseList = new ArrayList<>(baseAreas.size());
final List<PlaneConvexSubset> extrudedList = new ArrayList<>(baseAreas.size());
final AffineTransformMatrix3D extrudeTransform = AffineTransformMatrix3D.createTranslation(extrusionVector);
PlaneConvexSubset base;
for (final ConvexArea area : baseAreas) {
base = subsetFromConvexArea(basePlane, area);
if (extrudingOnPlusSide) {
base = base.reverse();
}
baseList.add(base);
extrudedList.add(base.transform(extrudeTransform).reverse());
}
result.addAll(baseList);
result.addAll(extrudedList);
}
/** Add the side boundaries of the extruded region to the result list.
* @param subspaceRegion subspace region being extruded.
* @param result list to add the boundary results to
*/
private void addSides(final RegionBSPTree2D subspaceRegion, final List<? super PlaneConvexSubset> result) {
Vector2D subStartPt;
Vector2D subEndPt;
PlaneConvexSubset boundary;
for (final LinePath path : subspaceRegion.getBoundaryPaths()) {
for (final LineConvexSubset lineSubset : path.getElements()) {
subStartPt = lineSubset.getStartPoint();
subEndPt = lineSubset.getEndPoint();
boundary = (subStartPt != null && subEndPt != null) ?
extrudeSideFinite(basePlane.toSpace(subStartPt), basePlane.toSpace(subEndPt)) :
extrudeSideInfinite(lineSubset);
result.add(boundary);
}
}
}
/** Extrude a single, finite boundary forming one of the sides of the extruded region.
* @param startPt start point of the boundary
* @param endPt end point of the boundary
* @return the extruded region side boundary
*/
private ConvexPolygon3D extrudeSideFinite(final Vector3D startPt, final Vector3D endPt) {
final Vector3D extrudedStartPt = startPt.add(extrusionVector);
final Vector3D extrudedEndPt = endPt.add(extrusionVector);
final List<Vector3D> vertices = extrudingOnPlusSide ?
Arrays.asList(startPt, endPt, extrudedEndPt, extrudedStartPt) :
Arrays.asList(startPt, extrudedStartPt, extrudedEndPt, endPt);
return convexPolygonFromVertices(vertices, precision);
}
/** Extrude a single, infinite boundary forming one of the sides of the extruded region.
* @param lineSubset line subset to extrude
* @return the extruded region side boundary
*/
private PlaneConvexSubset extrudeSideInfinite(final LineConvexSubset lineSubset) {
final Vector2D subLinePt = lineSubset.getLine().getOrigin();
final Vector2D subLineDir = lineSubset.getLine().getDirection();
final Vector3D linePt = basePlane.toSpace(subLinePt);
final Vector3D lineDir = linePt.vectorTo(basePlane.toSpace(subLinePt.add(subLineDir)));
final EmbeddingPlane sidePlane;
if (extrudingOnPlusSide) {
sidePlane = fromPointAndPlaneVectors(linePt, lineDir, extrusionVector, precision);
} else {
sidePlane = fromPointAndPlaneVectors(linePt, extrusionVector, lineDir, precision);
}
final Vector2D sideLineOrigin = sidePlane.toSubspace(linePt);
final Vector2D sideLineDir = sideLineOrigin.vectorTo(sidePlane.toSubspace(linePt.add(lineDir)));
final Vector2D extrudedSideLineOrigin = sidePlane.toSubspace(linePt.add(extrusionVector));
final Vector2D sideExtrusionDir = sidePlane.toSubspace(sidePlane.getOrigin().add(extrusionVector))
.normalize();
// construct a list of lines forming the bounds of the extruded subspace region
final List<Line> lines = new ArrayList<>();
// add the top and bottom lines (original and extruded)
if (extrudingOnPlusSide) {
lines.add(Lines.fromPointAndDirection(sideLineOrigin, sideLineDir, precision));
lines.add(Lines.fromPointAndDirection(extrudedSideLineOrigin, sideLineDir.negate(), precision));
} else {
lines.add(Lines.fromPointAndDirection(sideLineOrigin, sideLineDir.negate(), precision));
lines.add(Lines.fromPointAndDirection(extrudedSideLineOrigin, sideLineDir, precision));
}
// if we have a point on the original line, then connect the two
final Vector2D startPt = lineSubset.getStartPoint();
final Vector2D endPt = lineSubset.getEndPoint();
if (startPt != null) {
lines.add(Lines.fromPointAndDirection(
sidePlane.toSubspace(basePlane.toSpace(startPt)),
extrudingOnPlusSide ? sideExtrusionDir.negate() : sideExtrusionDir,
precision));
} else if (endPt != null) {
lines.add(Lines.fromPointAndDirection(
sidePlane.toSubspace(basePlane.toSpace(endPt)),
extrudingOnPlusSide ? sideExtrusionDir : sideExtrusionDir.negate(),
precision));
}
return subsetFromConvexArea(sidePlane, ConvexArea.fromBounds(lines));
}
}
}