View Javadoc

    1   /*
    2    * Licensed to the Apache Software Foundation (ASF) under one or more
    3    * contributor license agreements.  See the NOTICE file distributed with
    4    * this work for additional information regarding copyright ownership.
    5    * The ASF licenses this file to You under the Apache License, Version 2.0
    6    * (the "License"); you may not use this file except in compliance with
    7    * the License.  You may obtain a copy of the License at
    8    *
    9    *      http://www.apache.org/licenses/LICENSE-2.0
    10   *
    11   * Unless required by applicable law or agreed to in writing, software
    12   * distributed under the License is distributed on an "AS IS" BASIS,
    13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    14   * See the License for the specific language governing permissions and
    15   * limitations under the License.
    16   */
    17  package org.apache.commons.geometry.euclidean.threed;
    18
    19  import java.io.IOException;
    20  import java.text.ParseException;
    21  import java.util.ArrayList;
    22  import java.util.Arrays;
    23  import java.util.Collections;
    24  import java.util.List;
    25  import java.util.stream.Collectors;
    26
    27  import org.apache.commons.geometry.core.GeometryTestUtils;
    28  import org.apache.commons.geometry.core.RegionLocation;
    29  import org.apache.commons.geometry.core.partitioning.Split;
    30  import org.apache.commons.geometry.core.partitioning.SplitLocation;
    31  import org.apache.commons.geometry.core.partitioning.bsp.RegionCutRule;
    32  import org.apache.commons.geometry.core.precision.DoublePrecisionContext;
    33  import org.apache.commons.geometry.core.precision.EpsilonDoublePrecisionContext;
    34  import org.apache.commons.geometry.euclidean.EuclideanTestUtils;
    35  import org.apache.commons.geometry.euclidean.threed.RegionBSPTree3D.PartitionedRegionBuilder3D;
    36  import org.apache.commons.geometry.euclidean.threed.RegionBSPTree3D.RegionNode3D;
    37  import org.apache.commons.geometry.euclidean.threed.line.Line3D;
    38  import org.apache.commons.geometry.euclidean.threed.line.LinecastPoint3D;
    39  import org.apache.commons.geometry.euclidean.threed.line.Lines3D;
    40  import org.apache.commons.geometry.euclidean.threed.mesh.TriangleMesh;
    41  import org.apache.commons.geometry.euclidean.threed.shape.Parallelepiped;
    42  import org.apache.commons.geometry.euclidean.twod.path.LinePath;
    43  import org.apache.commons.numbers.angle.PlaneAngleRadians;
    44  import org.junit.Assert;
    45  import org.junit.Test;
    46
    47  public class RegionBSPTree3DTest {
    48
    49      private static final double TEST_EPS = 1e-10;
    50
    51      private static final DoublePrecisionContext TEST_PRECISION =
    52              new EpsilonDoublePrecisionContext(TEST_EPS);
    53
    54      @Test
    55      public void testCtor_default() {
    56          // act
    57          final RegionBSPTree3D tree = new RegionBSPTree3D();
    58
    59          // assert
    60          Assert.assertFalse(tree.isFull());
    61          Assert.assertTrue(tree.isEmpty());
    62      }
    63
    64      @Test
    65      public void testCtor_boolean() {
    66          // act
    67          final RegionBSPTree3D a = new RegionBSPTree3D(true);
    68          final RegionBSPTree3D b = new RegionBSPTree3D(false);
    69
    70          // assert
    71          Assert.assertTrue(a.isFull());
    72          Assert.assertFalse(a.isEmpty());
    73
    74          Assert.assertFalse(b.isFull());
    75          Assert.assertTrue(b.isEmpty());
    76      }
    77
    78      @Test
    79      public void testEmpty() {
    80          // act
    81          final RegionBSPTree3D tree = RegionBSPTree3D.empty();
    82
    83          // assert
    84          Assert.assertFalse(tree.isFull());
    85          Assert.assertTrue(tree.isEmpty());
    86
    87          Assert.assertNull(tree.getCentroid());
    88          Assert.assertEquals(0.0, tree.getSize(), TEST_EPS);
    89          Assert.assertEquals(0, tree.getBoundarySize(), TEST_EPS);
    90
    91          EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.OUTSIDE,
    92                  Vector3D.of(-Double.MAX_VALUE, -Double.MAX_VALUE, -Double.MAX_VALUE),
    93                  Vector3D.of(-100, -100, -100),
    94                  Vector3D.of(0, 0, 0),
    95                  Vector3D.of(100, 100, 100),
    96                  Vector3D.of(Double.MAX_VALUE, Double.MAX_VALUE, Double.MAX_VALUE));
    97      }
    98
    99      @Test
    100     public void testFull() {
    101         // act
    102         final RegionBSPTree3D tree = RegionBSPTree3D.full();
    103
    104         // assert
    105         Assert.assertTrue(tree.isFull());
    106         Assert.assertFalse(tree.isEmpty());
    107
    108         Assert.assertNull(tree.getCentroid());
    109         GeometryTestUtils.assertPositiveInfinity(tree.getSize());
    110         Assert.assertEquals(0, tree.getBoundarySize(), TEST_EPS);
    111
    112         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.INSIDE,
    113                 Vector3D.of(-Double.MAX_VALUE, -Double.MAX_VALUE, -Double.MAX_VALUE),
    114                 Vector3D.of(-100, -100, -100),
    115                 Vector3D.of(0, 0, 0),
    116                 Vector3D.of(100, 100, 100),
    117                 Vector3D.of(Double.MAX_VALUE, Double.MAX_VALUE, Double.MAX_VALUE));
    118     }
    119
    120     @Test
    121     public void testPartitionedRegionBuilder_halfSpace() {
    122         // act
    123         final RegionBSPTree3D tree = RegionBSPTree3D.partitionedRegionBuilder()
    124                 .insertPartition(
    125                     Planes.fromPointAndNormal(Vector3D.ZERO, Vector3D.Unit.PLUS_Z, TEST_PRECISION))
    126                 .insertBoundary(
    127                         Planes.fromPointAndNormal(Vector3D.ZERO, Vector3D.Unit.MINUS_Z, TEST_PRECISION).span())
    128                 .build();
    129
    130         // assert
    131         Assert.assertFalse(tree.isFull());
    132         Assert.assertTrue(tree.isInfinite());
    133
    134         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.INSIDE, Vector3D.of(0, 0, 1));
    135         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.BOUNDARY, Vector3D.ZERO);
    136         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.OUTSIDE, Vector3D.of(0, 0, -1));
    137     }
    138
    139     @Test
    140     public void testPartitionedRegionBuilder_cube() {
    141         // arrange
    142         final Parallelepiped cube = Parallelepiped.unitCube(TEST_PRECISION);
    143         final List<PlaneConvexSubset> boundaries = cube.getBoundaries();
    144
    145         final Vector3D lowerBound = Vector3D.of(-2, -2, -2);
    146
    147         final int maxUpper = 5;
    148         final int maxLevel = 4;
    149
    150         // act/assert
    151         Bounds3D bounds;
    152         for (int u = 0; u <= maxUpper; ++u) {
    153             for (int level = 0; level <= maxLevel; ++level) {
    154                 bounds = Bounds3D.from(lowerBound, Vector3D.of(u, u, u));
    155
    156                 checkFinitePartitionedRegion(bounds, level, cube);
    157                 checkFinitePartitionedRegion(bounds, level, boundaries);
    158             }
    159         }
    160     }
    161
    162     @Test
    163     public void testPartitionedRegionBuilder_nonConvex() {
    164         // arrange
    165         final RegionBSPTree3D src = Parallelepiped.unitCube(TEST_PRECISION).toTree();
    166         src.union(Parallelepiped.axisAligned(Vector3D.ZERO, Vector3D.of(1, 1, 1), TEST_PRECISION).toTree());
    167
    168         final List<PlaneConvexSubset> boundaries = src.getBoundaries();
    169
    170         final Vector3D lowerBound = Vector3D.of(-2, -2, -2);
    171
    172         final int maxUpper = 5;
    173         final int maxLevel = 4;
    174
    175         // act/assert
    176         Bounds3D bounds;
    177         for (int u = 0; u <= maxUpper; ++u) {
    178             for (int level = 0; level <= maxLevel; ++level) {
    179                 bounds = Bounds3D.from(lowerBound, Vector3D.of(u, u, u));
    180
    181                 checkFinitePartitionedRegion(bounds, level, src);
    182                 checkFinitePartitionedRegion(bounds, level, boundaries);
    183             }
    184         }
    185     }
    186
    187     /** Check that a partitioned BSP tree behaves the same as a non-partitioned tree when
    188      * constructed with the given boundary source.
    189      * @param bounds
    190      * @param level
    191      * @param src
    192      */
    193     private void checkFinitePartitionedRegion(final Bounds3D bounds, final int level, final BoundarySource3D src) {
    194         // arrange
    195         final String msg = "Partitioned region check failed with bounds= " + bounds + " and level= " + level;
    196
    197         final RegionBSPTree3D standard = RegionBSPTree3D.from(src.boundaryStream().collect(Collectors.toList()));
    198
    199         // act
    200         final RegionBSPTree3D partitioned = RegionBSPTree3D.partitionedRegionBuilder()
    201                 .insertAxisAlignedGrid(bounds, level, TEST_PRECISION)
    202                 .insertBoundaries(src)
    203                 .build();
    204
    205         // assert
    206         Assert.assertEquals(msg, standard.getSize(), partitioned.getSize(), TEST_EPS);
    207         Assert.assertEquals(msg, standard.getBoundarySize(), partitioned.getBoundarySize(), TEST_EPS);
    208         EuclideanTestUtils.assertCoordinatesEqual(standard.getCentroid(), partitioned.getCentroid(), TEST_EPS);
    209
    210         final RegionBSPTree3D diff = RegionBSPTree3D.empty();
    211         diff.difference(partitioned, standard);
    212         Assert.assertTrue(msg, diff.isEmpty());
    213     }
    214
    215     /** Check that a partitioned BSP tree behaves the same as a non-partitioned tree when
    216      * constructed with the given boundaries.
    217      * @param bounds
    218      * @param level
    219      * @param boundaries
    220      */
    221     private void checkFinitePartitionedRegion(final Bounds3D bounds, final int level,
    222                                               final List<? extends PlaneConvexSubset> boundaries) {
    223         // arrange
    224         final String msg = "Partitioned region check failed with bounds= " + bounds + " and level= " + level;
    225
    226         final RegionBSPTree3D standard = RegionBSPTree3D.from(boundaries);
    227
    228         // act
    229         final RegionBSPTree3D partitioned = RegionBSPTree3D.partitionedRegionBuilder()
    230                 .insertAxisAlignedGrid(bounds, level, TEST_PRECISION)
    231                 .insertBoundaries(boundaries)
    232                 .build();
    233
    234         // assert
    235         Assert.assertEquals(msg, standard.getSize(), partitioned.getSize(), TEST_EPS);
    236         Assert.assertEquals(msg, standard.getBoundarySize(), partitioned.getBoundarySize(), TEST_EPS);
    237         EuclideanTestUtils.assertCoordinatesEqual(standard.getCentroid(), partitioned.getCentroid(), TEST_EPS);
    238
    239         final RegionBSPTree3D diff = RegionBSPTree3D.empty();
    240         diff.difference(partitioned, standard);
    241         Assert.assertTrue(msg, diff.isEmpty());
    242     }
    243
    244     @Test
    245     public void testPartitionedRegionBuilder_insertPartitionAfterBoundary() {
    246         // arrange
    247         final PartitionedRegionBuilder3D builder = RegionBSPTree3D.partitionedRegionBuilder();
    248         builder.insertBoundary(Planes.triangleFromVertices(
    249                 Vector3D.ZERO, Vector3D.of(1, 0, 0), Vector3D.of(0, 1, 0), TEST_PRECISION));
    250
    251         final Plane partition = Planes.fromNormal(Vector3D.Unit.PLUS_Z, TEST_PRECISION);
    252
    253         final String msg = "Cannot insert partitions after boundaries have been inserted";
    254
    255         // act/assert
    256         GeometryTestUtils.assertThrows(() -> {
    257             builder.insertPartition(partition);
    258         }, IllegalStateException.class, msg);
    259
    260         GeometryTestUtils.assertThrows(() -> {
    261             builder.insertPartition(partition.span());
    262         }, IllegalStateException.class, msg);
    263
    264         GeometryTestUtils.assertThrows(() -> {
    265             builder.insertAxisAlignedPartitions(Vector3D.ZERO, TEST_PRECISION);
    266         }, IllegalStateException.class, msg);
    267
    268         GeometryTestUtils.assertThrows(() -> {
    269             builder.insertAxisAlignedGrid(Bounds3D.from(Vector3D.ZERO, Vector3D.of(1, 1, 1)), 1, TEST_PRECISION);
    270         }, IllegalStateException.class, msg);
    271     }
    272
    273     @Test
    274     public void testCopy() {
    275         // arrange
    276         final RegionBSPTree3D tree = new RegionBSPTree3D(true);
    277         tree.getRoot().cut(Planes.fromNormal(Vector3D.Unit.PLUS_Z, TEST_PRECISION));
    278
    279         // act
    280         final RegionBSPTree3D copy = tree.copy();
    281
    282         // assert
    283         Assert.assertNotSame(tree, copy);
    284         Assert.assertEquals(3, copy.count());
    285     }
    286
    287     @Test
    288     public void testBoundaries() {
    289         // arrange
    290         final RegionBSPTree3D tree = createRect(Vector3D.ZERO, Vector3D.of(1, 1, 1));
    291
    292         // act
    293         final List<PlaneConvexSubset> facets = new ArrayList<>();
    294         tree.boundaries().forEach(facets::add);
    295
    296         // assert
    297         Assert.assertEquals(6, facets.size());
    298     }
    299
    300     @Test
    301     public void testGetBoundaries() {
    302         // arrange
    303         final RegionBSPTree3D tree = createRect(Vector3D.ZERO, Vector3D.of(1, 1, 1));
    304
    305         // act
    306         final List<PlaneConvexSubset> facets = tree.getBoundaries();
    307
    308         // assert
    309         Assert.assertEquals(6, facets.size());
    310     }
    311
    312     @Test
    313     public void testBoundaryStream() {
    314         // arrange
    315         final RegionBSPTree3D tree = createRect(Vector3D.ZERO, Vector3D.of(1, 1, 1));
    316
    317         // act
    318         final List<PlaneConvexSubset> facets = tree.boundaryStream().collect(Collectors.toList());
    319
    320         // assert
    321         Assert.assertEquals(6, facets.size());
    322     }
    323
    324     @Test
    325     public void testBoundaryStream_noBoundaries() {
    326         // arrange
    327         final RegionBSPTree3D tree = RegionBSPTree3D.full();
    328
    329         // act
    330         final List<PlaneConvexSubset> facets = tree.boundaryStream().collect(Collectors.toList());
    331
    332         // assert
    333         Assert.assertEquals(0, facets.size());
    334     }
    335
    336     @Test
    337     public void testTriangleStream_noBoundaries() {
    338         // arrange
    339         final RegionBSPTree3D full = RegionBSPTree3D.full();
    340         final RegionBSPTree3D empty = RegionBSPTree3D.empty();
    341
    342         // act/assert
    343         Assert.assertEquals(0, full.triangleStream().count());
    344         Assert.assertEquals(0, empty.triangleStream().count());
    345     }
    346
    347     @Test
    348     public void testTriangleStream() {
    349         // arrange
    350         final RegionBSPTree3D tree = createRect(Vector3D.ZERO, Vector3D.of(1, 1, 1));
    351
    352         // act
    353         final List<Triangle3D> tris = tree.triangleStream().collect(Collectors.toList());
    354
    355         // assert
    356         Assert.assertEquals(12, tris.size());
    357     }
    358
    359     @Test
    360     public void testTriangleStream_roundTrip() {
    361         // arrange
    362         final RegionBSPTree3D a = createRect(Vector3D.ZERO, Vector3D.of(1, 1, 1));
    363         final RegionBSPTree3D b = createRect(Vector3D.of(0.5, 0.5, 0.5), Vector3D.of(1.5, 1.5, 1.5));
    364
    365         final RegionBSPTree3D tree = RegionBSPTree3D.empty();
    366         tree.union(a);
    367         tree.union(b);
    368
    369         // act
    370         final List<Triangle3D> tris = tree.triangleStream().collect(Collectors.toList());
    371         final RegionBSPTree3D result = RegionBSPTree3D.from(tris);
    372
    373         // assert
    374         Assert.assertEquals(15.0 / 8.0, result.getSize(), TEST_EPS);
    375         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0.75, 0.75, 0.75), result.getCentroid(), TEST_EPS);
    376     }
    377
    378     @Test
    379     public void testToTriangleMesh() {
    380         // arrange
    381         final RegionBSPTree3D tree = createRect(Vector3D.ZERO, Vector3D.of(1, 1, 1));
    382
    383         // act
    384         final TriangleMesh mesh = tree.toTriangleMesh(TEST_PRECISION);
    385
    386         // assert
    387         Assert.assertEquals(8, mesh.getVertexCount());
    388         Assert.assertEquals(12, mesh.getFaceCount());
    389
    390         final Bounds3D bounds = mesh.getBounds();
    391         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.ZERO, bounds.getMin(), TEST_EPS);
    392         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, 1, 1), bounds.getMax(), TEST_EPS);
    393
    394         final RegionBSPTree3D otherTree = mesh.toTree();
    395         Assert.assertEquals(1, otherTree.getSize(), TEST_EPS);
    396         Assert.assertEquals(6, otherTree.getBoundarySize(), TEST_EPS);
    397         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0.5, 0.5, 0.5), otherTree.getCentroid(), TEST_EPS);
    398     }
    399
    400     @Test
    401     public void testToTriangleMesh_empty() {
    402         // arrange
    403         final RegionBSPTree3D tree = RegionBSPTree3D.empty();
    404
    405         // act
    406         final TriangleMesh mesh = tree.toTriangleMesh(TEST_PRECISION);
    407
    408         // assert
    409         // no boundaries
    410         Assert.assertEquals(0, mesh.getVertexCount());
    411         Assert.assertEquals(0, mesh.getFaceCount());
    412     }
    413
    414     @Test
    415     public void testToTriangleMesh_full() {
    416         // arrange
    417         final RegionBSPTree3D tree = RegionBSPTree3D.full();
    418
    419         // act
    420         final TriangleMesh mesh = tree.toTriangleMesh(TEST_PRECISION);
    421
    422         // assert
    423         // no boundaries
    424         Assert.assertEquals(0, mesh.getVertexCount());
    425         Assert.assertEquals(0, mesh.getFaceCount());
    426     }
    427
    428     @Test
    429     public void testToTriangleMesh_infiniteBoundary() {
    430         // arrange
    431         final RegionBSPTree3D tree = RegionBSPTree3D.empty();
    432         tree.getRoot().insertCut(Planes.fromNormal(Vector3D.Unit.PLUS_Z, TEST_PRECISION));
    433
    434         // act/assert
    435         GeometryTestUtils.assertThrows(() -> {
    436             tree.toTriangleMesh(TEST_PRECISION);
    437         }, IllegalStateException.class);
    438     }
    439
    440     @Test
    441     public void testGetBounds_hasBounds() {
    442         // arrange
    443         final RegionBSPTree3D tree = createRect(Vector3D.ZERO, Vector3D.of(1, 1, 1));
    444
    445         // act
    446         final Bounds3D bounds = tree.getBounds();
    447
    448         // assert
    449         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.ZERO, bounds.getMin(), TEST_EPS);
    450         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, 1, 1), bounds.getMax(), TEST_EPS);
    451     }
    452
    453     @Test
    454     public void testGetBounds_noBounds() {
    455         // act/assert
    456         Assert.assertNull(RegionBSPTree3D.empty().getBounds());
    457         Assert.assertNull(RegionBSPTree3D.full().getBounds());
    458
    459         final RegionBSPTree3D halfFull = RegionBSPTree3D.empty();
    460         halfFull.getRoot().insertCut(Planes.fromPointAndNormal(Vector3D.ZERO, Vector3D.Unit.PLUS_Z, TEST_PRECISION));
    461         Assert.assertNull(halfFull.getBounds());
    462     }
    463
    464     @Test
    465     public void testToTree_returnsSameInstance() {
    466         // arrange
    467         final RegionBSPTree3D tree = createRect(Vector3D.ZERO, Vector3D.of(1, 2, 1));
    468
    469         // act/assert
    470         Assert.assertSame(tree, tree.toTree());
    471     }
    472
    473     @Test
    474     public void testHalfSpace() {
    475         // act
    476         final RegionBSPTree3D tree = RegionBSPTree3D.empty();
    477         tree.insert(Planes.fromPointAndNormal(Vector3D.ZERO, Vector3D.Unit.PLUS_Y, TEST_PRECISION).span());
    478
    479         // assert
    480         Assert.assertFalse(tree.isEmpty());
    481         Assert.assertFalse(tree.isFull());
    482
    483         EuclideanTestUtils.assertPositiveInfinity(tree.getSize());
    484         EuclideanTestUtils.assertPositiveInfinity(tree.getBoundarySize());
    485         Assert.assertNull(tree.getCentroid());
    486
    487         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.INSIDE,
    488                 Vector3D.of(-Double.MAX_VALUE, -Double.MAX_VALUE, -Double.MAX_VALUE),
    489                 Vector3D.of(-100, -100, -100));
    490         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.BOUNDARY, Vector3D.of(0, 0, 0));
    491         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.OUTSIDE,
    492                 Vector3D.of(100, 100, 100),
    493                 Vector3D.of(Double.MAX_VALUE, Double.MAX_VALUE, Double.MAX_VALUE));
    494     }
    495
    496     @Test
    497     public void testGeometricProperties_mixedCutRules() {
    498         // act
    499         final RegionBSPTree3D tree = RegionBSPTree3D.empty();
    500
    501         final Vector3D min = Vector3D.ZERO;
    502         final Vector3D max = Vector3D.of(1, 1, 1);
    503
    504         final Plane top = Planes.fromPointAndNormal(max, Vector3D.Unit.PLUS_Z, TEST_PRECISION);
    505         final Plane bottom = Planes.fromPointAndNormal(min, Vector3D.Unit.MINUS_Z, TEST_PRECISION);
    506         final Plane left = Planes.fromPointAndNormal(min, Vector3D.Unit.MINUS_X, TEST_PRECISION);
    507         final Plane right = Planes.fromPointAndNormal(max, Vector3D.Unit.PLUS_X, TEST_PRECISION);
    508         final Plane front = Planes.fromPointAndNormal(min, Vector3D.Unit.MINUS_Y, TEST_PRECISION);
    509         final Plane back = Planes.fromPointAndNormal(max, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
    510
    511         final Plane diag = Planes.fromPointAndNormal(Vector3D.of(0.5, 0.5, 0.5), Vector3D.of(0.5, -0.5, 0), TEST_PRECISION);
    512         final Plane midCut = Planes.fromPointAndNormal(Vector3D.of(0.5, 0.5, 0.5), Vector3D.Unit.PLUS_Z, TEST_PRECISION);
    513
    514         tree.getRoot()
    515             .cut(diag, RegionCutRule.INHERIT);
    516
    517         tree.getRoot()
    518             .getMinus().cut(top)
    519             .getMinus().cut(bottom.reverse(), RegionCutRule.PLUS_INSIDE)
    520             .getPlus().cut(left, RegionCutRule.MINUS_INSIDE)
    521             .getMinus().cut(back.reverse(), RegionCutRule.PLUS_INSIDE)
    522             .getPlus().cut(midCut, RegionCutRule.INHERIT);
    523
    524         tree.getRoot()
    525             .getPlus().cut(top.reverse(), RegionCutRule.PLUS_INSIDE)
    526             .getPlus().cut(bottom)
    527             .getMinus().cut(right, RegionCutRule.MINUS_INSIDE)
    528             .getMinus().cut(front.reverse(), RegionCutRule.PLUS_INSIDE)
    529             .getPlus().cut(midCut, RegionCutRule.INHERIT);
    530
    531         // assert
    532         Assert.assertFalse(tree.isEmpty());
    533         Assert.assertFalse(tree.isFull());
    534
    535         Assert.assertEquals(1, tree.getSize(), TEST_EPS);
    536         Assert.assertEquals(6, tree.getBoundarySize(), TEST_EPS);
    537         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0.5, 0.5, 0.5), tree.getCentroid(), TEST_EPS);
    538
    539         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.INSIDE, Vector3D.of(0.5, 0.5, 0.5));
    540         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.BOUNDARY, min, max);
    541         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.OUTSIDE,
    542                 Vector3D.of(2, 2, 2), Vector3D.of(2, 2, -2),
    543                 Vector3D.of(2, -2, 2), Vector3D.of(2, -2, -2),
    544                 Vector3D.of(-2, 2, 2), Vector3D.of(-2, 2, -2),
    545                 Vector3D.of(-2, -2, 2), Vector3D.of(-2, -2, -2));
    546     }
    547
    548     @Test
    549     public void testFrom_boundaries() {
    550         // act
    551         final RegionBSPTree3D tree = RegionBSPTree3D.from(Arrays.asList(
    552                     Planes.convexPolygonFromVertices(Arrays.asList(
    553                             Vector3D.ZERO, Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y), TEST_PRECISION),
    554                     Planes.convexPolygonFromVertices(Arrays.asList(
    555                             Vector3D.ZERO, Vector3D.Unit.MINUS_Z, Vector3D.Unit.PLUS_X), TEST_PRECISION)
    556                 ));
    557
    558         // assert
    559         Assert.assertFalse(tree.isFull());
    560         Assert.assertFalse(tree.isEmpty());
    561
    562         Assert.assertEquals(RegionLocation.OUTSIDE, tree.getRoot().getLocation());
    563
    564         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.INSIDE,
    565                 Vector3D.of(1, 1, -1), Vector3D.of(-1, 1, -1));
    566         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.OUTSIDE,
    567                 Vector3D.of(1, 1, 1), Vector3D.of(-1, 1, 1), Vector3D.of(1, -1, 1),
    568                 Vector3D.of(-1, -1, 1), Vector3D.of(1, -1, -1), Vector3D.of(-1, -1, -1));
    569     }
    570
    571     @Test
    572     public void testFrom_boundaries_fullIsTrue() {
    573         // act
    574         final RegionBSPTree3D tree = RegionBSPTree3D.from(Arrays.asList(
    575                     Planes.convexPolygonFromVertices(Arrays.asList(
    576                             Vector3D.ZERO, Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y), TEST_PRECISION),
    577                     Planes.convexPolygonFromVertices(Arrays.asList(
    578                             Vector3D.ZERO, Vector3D.Unit.MINUS_Z, Vector3D.Unit.PLUS_X), TEST_PRECISION)
    579                 ), true);
    580
    581         // assert
    582         Assert.assertFalse(tree.isFull());
    583         Assert.assertFalse(tree.isEmpty());
    584
    585         Assert.assertEquals(RegionLocation.INSIDE, tree.getRoot().getLocation());
    586
    587         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.INSIDE,
    588                 Vector3D.of(1, 1, -1), Vector3D.of(-1, 1, -1));
    589         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.OUTSIDE,
    590                 Vector3D.of(1, 1, 1), Vector3D.of(-1, 1, 1), Vector3D.of(1, -1, 1),
    591                 Vector3D.of(-1, -1, 1), Vector3D.of(1, -1, -1), Vector3D.of(-1, -1, -1));
    592     }
    593
    594     @Test
    595     public void testFrom_boundaries_noBoundaries() {
    596         // act/assert
    597         Assert.assertTrue(RegionBSPTree3D.from(Collections.emptyList()).isEmpty());
    598         Assert.assertTrue(RegionBSPTree3D.from(Collections.emptyList(), true).isFull());
    599         Assert.assertTrue(RegionBSPTree3D.from(Collections.emptyList(), false).isEmpty());
    600     }
    601
    602     @Test
    603     public void testFromConvexVolume_full() {
    604         // arrange
    605         final ConvexVolume volume = ConvexVolume.full();
    606
    607         // act
    608         final RegionBSPTree3D tree = volume.toTree();
    609         Assert.assertNull(tree.getCentroid());
    610
    611         // assert
    612         Assert.assertTrue(tree.isFull());
    613     }
    614
    615     @Test
    616     public void testFromConvexVolume_infinite() {
    617         // arrange
    618         final ConvexVolume volume = ConvexVolume.fromBounds(Planes.fromNormal(Vector3D.Unit.PLUS_Z, TEST_PRECISION));
    619
    620         // act
    621         final RegionBSPTree3D tree = volume.toTree();
    622
    623         // assert
    624         GeometryTestUtils.assertPositiveInfinity(tree.getSize());
    625         GeometryTestUtils.assertPositiveInfinity(tree.getBoundarySize());
    626         Assert.assertNull(tree.getCentroid());
    627
    628         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.OUTSIDE, Vector3D.of(0, 0, 1));
    629         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.BOUNDARY, Vector3D.ZERO);
    630         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.INSIDE, Vector3D.of(0, 0, -1));
    631     }
    632
    633     @Test
    634     public void testFromConvexVolume_finite() {
    635         // arrange
    636         final ConvexVolume volume = ConvexVolume.fromBounds(
    637                     Planes.fromPointAndNormal(Vector3D.ZERO, Vector3D.Unit.MINUS_X, TEST_PRECISION),
    638                     Planes.fromPointAndNormal(Vector3D.ZERO, Vector3D.Unit.MINUS_Y, TEST_PRECISION),
    639                     Planes.fromPointAndNormal(Vector3D.ZERO, Vector3D.Unit.MINUS_Z, TEST_PRECISION),
    640
    641                     Planes.fromPointAndNormal(Vector3D.of(1, 1, 1), Vector3D.Unit.PLUS_X, TEST_PRECISION),
    642                     Planes.fromPointAndNormal(Vector3D.of(1, 1, 1), Vector3D.Unit.PLUS_Y, TEST_PRECISION),
    643                     Planes.fromPointAndNormal(Vector3D.of(1, 1, 1), Vector3D.Unit.PLUS_Z, TEST_PRECISION)
    644                 );
    645
    646         // act
    647         final RegionBSPTree3D tree = volume.toTree();
    648
    649         // assert
    650         Assert.assertEquals(1, tree.getSize(), TEST_EPS);
    651         Assert.assertEquals(6, tree.getBoundarySize(), TEST_EPS);
    652         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0.5, 0.5, 0.5), tree.getCentroid(), TEST_EPS);
    653
    654         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.OUTSIDE,
    655                 Vector3D.of(-1, 0.5, 0.5), Vector3D.of(2, 0.5, 0.5),
    656                 Vector3D.of(0.5, -1, 0.5), Vector3D.of(0.5, 2, 0.5),
    657                 Vector3D.of(0.5, 0.5, -1), Vector3D.of(0.5, 0.5, 2));
    658         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.BOUNDARY, Vector3D.ZERO);
    659         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.INSIDE, Vector3D.of(0.5, 0.5, 0.5));
    660     }
    661
    662     @Test
    663     public void testLinecast_empty() {
    664         // arrange
    665         final RegionBSPTree3D tree = RegionBSPTree3D.empty();
    666
    667         // act/assert
    668         LinecastChecker3D.with(tree)
    669             .expectNothing()
    670             .whenGiven(Lines3D.fromPoints(Vector3D.ZERO, Vector3D.Unit.PLUS_X, TEST_PRECISION));
    671
    672         LinecastChecker3D.with(tree)
    673             .expectNothing()
    674             .whenGiven(Lines3D.segmentFromPoints(Vector3D.Unit.MINUS_X, Vector3D.Unit.PLUS_X, TEST_PRECISION));
    675     }
    676
    677     @Test
    678     public void testLinecast_full() {
    679         // arrange
    680         final RegionBSPTree3D tree = RegionBSPTree3D.full();
    681
    682         // act/assert
    683         LinecastChecker3D.with(tree)
    684             .expectNothing()
    685             .whenGiven(Lines3D.fromPoints(Vector3D.ZERO, Vector3D.Unit.PLUS_X, TEST_PRECISION));
    686
    687         LinecastChecker3D.with(tree)
    688             .expectNothing()
    689             .whenGiven(Lines3D.segmentFromPoints(Vector3D.Unit.MINUS_X, Vector3D.Unit.PLUS_X, TEST_PRECISION));
    690     }
    691
    692     @Test
    693     public void testLinecast() {
    694         // arrange
    695         final RegionBSPTree3D tree = createRect(Vector3D.ZERO, Vector3D.of(1, 1, 1));
    696
    697         // act/assert
    698         LinecastChecker3D.with(tree)
    699             .expectNothing()
    700             .whenGiven(Lines3D.fromPoints(Vector3D.of(0, 5, 5), Vector3D.of(1, 6, 6), TEST_PRECISION));
    701
    702         final Vector3D corner = Vector3D.of(1, 1, 1);
    703
    704         LinecastChecker3D.with(tree)
    705             .expect(Vector3D.ZERO, Vector3D.Unit.MINUS_X)
    706             .and(Vector3D.ZERO, Vector3D.Unit.MINUS_Y)
    707             .and(Vector3D.ZERO, Vector3D.Unit.MINUS_Z)
    708             .and(corner, Vector3D.Unit.PLUS_Z)
    709             .and(corner, Vector3D.Unit.PLUS_Y)
    710             .and(corner, Vector3D.Unit.PLUS_X)
    711             .whenGiven(Lines3D.fromPoints(Vector3D.ZERO, corner, TEST_PRECISION));
    712
    713         LinecastChecker3D.with(tree)
    714             .expect(corner, Vector3D.Unit.PLUS_Z)
    715             .and(corner, Vector3D.Unit.PLUS_Y)
    716             .and(corner, Vector3D.Unit.PLUS_X)
    717             .whenGiven(Lines3D.segmentFromPoints(Vector3D.of(0.5, 0.5, 0.5), corner, TEST_PRECISION));
    718     }
    719
    720     @Test
    721     public void testLinecast_complementedTree() {
    722         // arrange
    723         final RegionBSPTree3D tree = createRect(Vector3D.ZERO, Vector3D.of(1, 1, 1));
    724
    725         tree.complement();
    726
    727         // act/assert
    728         LinecastChecker3D.with(tree)
    729             .expectNothing()
    730             .whenGiven(Lines3D.fromPoints(Vector3D.of(0, 5, 5), Vector3D.of(1, 6, 6), TEST_PRECISION));
    731
    732         final Vector3D corner = Vector3D.of(1, 1, 1);
    733
    734         LinecastChecker3D.with(tree)
    735             .expect(Vector3D.ZERO, Vector3D.Unit.PLUS_Z)
    736             .and(Vector3D.ZERO, Vector3D.Unit.PLUS_Y)
    737             .and(Vector3D.ZERO, Vector3D.Unit.PLUS_X)
    738             .and(corner, Vector3D.Unit.MINUS_X)
    739             .and(corner, Vector3D.Unit.MINUS_Y)
    740             .and(corner, Vector3D.Unit.MINUS_Z)
    741             .whenGiven(Lines3D.fromPoints(Vector3D.ZERO, corner, TEST_PRECISION));
    742
    743         LinecastChecker3D.with(tree)
    744             .expect(corner, Vector3D.Unit.MINUS_X)
    745             .and(corner, Vector3D.Unit.MINUS_Y)
    746             .and(corner, Vector3D.Unit.MINUS_Z)
    747             .whenGiven(Lines3D.segmentFromPoints(Vector3D.of(0.5, 0.5, 0.5), corner, TEST_PRECISION));
    748     }
    749
    750     @Test
    751     public void testLinecast_complexRegion() {
    752         // arrange
    753         final RegionBSPTree3D a = RegionBSPTree3D.empty();
    754         Parallelepiped.axisAligned(Vector3D.ZERO, Vector3D.of(0.5, 1, 1), TEST_PRECISION).boundaryStream()
    755             .map(PlaneConvexSubset::reverse)
    756             .forEach(a::insert);
    757         a.complement();
    758
    759         final RegionBSPTree3D b = RegionBSPTree3D.empty();
    760         Parallelepiped.axisAligned(Vector3D.of(0.5, 0, 0), Vector3D.of(1, 1, 1), TEST_PRECISION).boundaryStream()
    761             .map(PlaneConvexSubset::reverse)
    762             .forEach(b::insert);
    763         b.complement();
    764
    765         final RegionBSPTree3D c = createRect(Vector3D.of(0.5, 0.5, 0.5), Vector3D.of(1.5, 1.5, 1.5));
    766
    767         final RegionBSPTree3D tree = RegionBSPTree3D.empty();
    768         tree.union(a, b);
    769         tree.union(c);
    770
    771         // act/assert
    772         final Vector3D corner = Vector3D.of(1.5, 1.5, 1.5);
    773
    774         LinecastChecker3D.with(tree)
    775             .expect(corner, Vector3D.Unit.PLUS_Z)
    776             .and(corner, Vector3D.Unit.PLUS_Y)
    777             .and(corner, Vector3D.Unit.PLUS_X)
    778             .whenGiven(Lines3D.segmentFromPoints(Vector3D.of(0.25, 0.25, 0.25), Vector3D.of(2, 2, 2), TEST_PRECISION));
    779     }
    780
    781     @Test
    782     public void testLinecast_removesDuplicatePoints() {
    783         // arrange
    784         final RegionBSPTree3D tree = RegionBSPTree3D.empty();
    785         tree.insert(Planes.fromNormal(Vector3D.Unit.PLUS_X, TEST_PRECISION).span());
    786         tree.insert(Planes.fromNormal(Vector3D.Unit.PLUS_Y, TEST_PRECISION).span());
    787
    788         // act/assert
    789         LinecastChecker3D.with(tree)
    790             .expect(Vector3D.ZERO, Vector3D.Unit.PLUS_Y)
    791             .whenGiven(Lines3D.fromPoints(Vector3D.of(1, 1, 1), Vector3D.of(-1, -1, -1), TEST_PRECISION));
    792
    793         LinecastChecker3D.with(tree)
    794         .expect(Vector3D.ZERO, Vector3D.Unit.PLUS_Y)
    795             .whenGiven(Lines3D.segmentFromPoints(Vector3D.of(1, 1, 1), Vector3D.of(-1, -1, -1), TEST_PRECISION));
    796     }
    797
    798     @Test
    799     public void testLinecastFirst_multipleDirections() {
    800         // arrange
    801         final RegionBSPTree3D tree = createRect(Vector3D.of(-1, -1, -1), Vector3D.of(1, 1, 1));
    802
    803         final Line3D xPlus = Lines3D.fromPoints(Vector3D.ZERO, Vector3D.of(1, 0, 0), TEST_PRECISION);
    804         final Line3D xMinus = Lines3D.fromPoints(Vector3D.ZERO, Vector3D.of(-1, 0, 0), TEST_PRECISION);
    805
    806         final Line3D yPlus = Lines3D.fromPoints(Vector3D.ZERO, Vector3D.of(0, 1, 0), TEST_PRECISION);
    807         final Line3D yMinus = Lines3D.fromPoints(Vector3D.ZERO, Vector3D.of(0, -1, 0), TEST_PRECISION);
    808
    809         final Line3D zPlus = Lines3D.fromPoints(Vector3D.ZERO, Vector3D.of(0, 0, 1), TEST_PRECISION);
    810         final Line3D zMinus = Lines3D.fromPoints(Vector3D.ZERO, Vector3D.of(0, 0, -1), TEST_PRECISION);
    811
    812         // act/assert
    813         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(-1, 0, 0),
    814                 tree.linecastFirst(xPlus.rayFrom(Vector3D.of(-1.1, 0, 0))).getNormal(), TEST_EPS);
    815         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(-1, 0, 0),
    816                 tree.linecastFirst(xPlus.rayFrom(Vector3D.of(-1, 0, 0))).getNormal(), TEST_EPS);
    817         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, 0, 0),
    818                 tree.linecastFirst(xPlus.rayFrom(Vector3D.of(-0.9, 0, 0))).getNormal(), TEST_EPS);
    819         Assert.assertNull(tree.linecastFirst(xPlus.rayFrom(Vector3D.of(1.1, 0, 0))));
    820
    821         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, 0, 0),
    822                 tree.linecastFirst(xMinus.rayFrom(Vector3D.of(1.1, 0, 0))).getNormal(), TEST_EPS);
    823         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, 0, 0),
    824                 tree.linecastFirst(xMinus.rayFrom(Vector3D.of(1, 0, 0))).getNormal(), TEST_EPS);
    825         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(-1, 0, 0),
    826                 tree.linecastFirst(xMinus.rayFrom(Vector3D.of(0.9, 0, 0))).getNormal(), TEST_EPS);
    827         Assert.assertNull(tree.linecastFirst(xMinus.rayFrom(Vector3D.of(-1.1, 0, 0))));
    828
    829         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, -1, 0),
    830                 tree.linecastFirst(yPlus.rayFrom(Vector3D.of(0, -1.1, 0))).getNormal(), TEST_EPS);
    831         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, -1, 0),
    832                 tree.linecastFirst(yPlus.rayFrom(Vector3D.of(0, -1, 0))).getNormal(), TEST_EPS);
    833         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, 1, 0),
    834                 tree.linecastFirst(yPlus.rayFrom(Vector3D.of(0, -0.9, 0))).getNormal(), TEST_EPS);
    835         Assert.assertNull(tree.linecastFirst(yPlus.rayFrom(Vector3D.of(0, 1.1, 0))));
    836
    837         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, 1, 0),
    838                 tree.linecastFirst(yMinus.rayFrom(Vector3D.of(0, 1.1, 0))).getNormal(), TEST_EPS);
    839         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, 1, 0),
    840                 tree.linecastFirst(yMinus.rayFrom(Vector3D.of(0, 1, 0))).getNormal(), TEST_EPS);
    841         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, -1, 0),
    842                 tree.linecastFirst(yMinus.rayFrom(Vector3D.of(0, 0.9, 0))).getNormal(), TEST_EPS);
    843         Assert.assertNull(tree.linecastFirst(yMinus.rayFrom(Vector3D.of(0, -1.1, 0))));
    844
    845         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, 0, -1),
    846                 tree.linecastFirst(zPlus.rayFrom(Vector3D.of(0, 0, -1.1))).getNormal(), TEST_EPS);
    847         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, 0, -1),
    848                 tree.linecastFirst(zPlus.rayFrom(Vector3D.of(0, 0, -1))).getNormal(), TEST_EPS);
    849         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, 0, 1),
    850                 tree.linecastFirst(zPlus.rayFrom(Vector3D.of(0, 0, -0.9))).getNormal(), TEST_EPS);
    851         Assert.assertNull(tree.linecastFirst(zPlus.rayFrom(Vector3D.of(0, 0, 1.1))));
    852
    853         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, 0, 1),
    854                 tree.linecastFirst(zMinus.rayFrom(Vector3D.of(0, 0, 1.1))).getNormal(), TEST_EPS);
    855         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, 0, 1),
    856                 tree.linecastFirst(zMinus.rayFrom(Vector3D.of(0, 0, 1))).getNormal(), TEST_EPS);
    857         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, 0, -1),
    858                 tree.linecastFirst(zMinus.rayFrom(Vector3D.of(0, 0, 0.9))).getNormal(), TEST_EPS);
    859         Assert.assertNull(tree.linecastFirst(zMinus.rayFrom(Vector3D.of(0, 0, -1.1))));
    860     }
    861
    862     // issue GEOMETRY-38
    863     @Test
    864     public void testLinecastFirst_linePassesThroughVertex() {
    865         // arrange
    866         final Vector3D lowerCorner = Vector3D.ZERO;
    867         final Vector3D upperCorner = Vector3D.of(1, 1, 1);
    868         final Vector3D center = lowerCorner.lerp(upperCorner, 0.5);
    869
    870         final RegionBSPTree3D tree = createRect(lowerCorner, upperCorner);
    871
    872         final Line3D upDiagonal = Lines3D.fromPoints(lowerCorner, upperCorner, TEST_PRECISION);
    873         final Line3D downDiagonal = upDiagonal.reverse();
    874
    875         // act/assert
    876         final LinecastPoint3D upFromOutsideResult = tree.linecastFirst(upDiagonal.rayFrom(Vector3D.of(-1, -1, -1)));
    877         Assert.assertNotNull(upFromOutsideResult);
    878         EuclideanTestUtils.assertCoordinatesEqual(lowerCorner, upFromOutsideResult.getPoint(), TEST_EPS);
    879
    880         final LinecastPoint3D upFromCenterResult = tree.linecastFirst(upDiagonal.rayFrom(center));
    881         Assert.assertNotNull(upFromCenterResult);
    882         EuclideanTestUtils.assertCoordinatesEqual(upperCorner, upFromCenterResult.getPoint(), TEST_EPS);
    883
    884         final LinecastPoint3D downFromOutsideResult = tree.linecastFirst(downDiagonal.rayFrom(Vector3D.of(2, 2, 2)));
    885         Assert.assertNotNull(downFromOutsideResult);
    886         EuclideanTestUtils.assertCoordinatesEqual(upperCorner, downFromOutsideResult.getPoint(), TEST_EPS);
    887
    888         final LinecastPoint3D downFromCenterResult = tree.linecastFirst(downDiagonal.rayFrom(center));
    889         Assert.assertNotNull(downFromCenterResult);
    890         EuclideanTestUtils.assertCoordinatesEqual(lowerCorner, downFromCenterResult.getPoint(), TEST_EPS);
    891     }
    892
    893     // Issue GEOMETRY-43
    894     @Test
    895     public void testLinecastFirst_lineParallelToFace() {
    896         // arrange - setup box
    897         final Vector3D lowerCorner = Vector3D.ZERO;
    898         final Vector3D upperCorner = Vector3D.of(1, 1, 1);
    899
    900         final RegionBSPTree3D tree = createRect(lowerCorner, upperCorner);
    901
    902         final Vector3D firstPointOnLine = Vector3D.of(0.5, -1.0, 0);
    903         final Vector3D secondPointOnLine = Vector3D.of(0.5, 2.0, 0);
    904         final Line3D bottomLine = Lines3D.fromPoints(firstPointOnLine, secondPointOnLine, TEST_PRECISION);
    905
    906         final Vector3D expectedIntersection1 = Vector3D.of(0.5, 0, 0.0);
    907         final Vector3D expectedIntersection2 = Vector3D.of(0.5, 1.0, 0.0);
    908
    909         // act/assert
    910         LinecastPoint3D bottom = tree.linecastFirst(bottomLine.rayFrom(firstPointOnLine));
    911         Assert.assertNotNull(bottom);
    912         EuclideanTestUtils.assertCoordinatesEqual(expectedIntersection1, bottom.getPoint(), TEST_EPS);
    913
    914         bottom = tree.linecastFirst(bottomLine.rayFrom(Vector3D.of(0.5, 0.1, 0.0)));
    915         Assert.assertNotNull(bottom);
    916         final Vector3D intersection = bottom.getPoint();
    917         Assert.assertNotNull(intersection);
    918         EuclideanTestUtils.assertCoordinatesEqual(expectedIntersection2, intersection, TEST_EPS);
    919     }
    920
    921     @Test
    922     public void testLinecastFirst_rayPointOnFace() {
    923         // arrange
    924         final Vector3D lowerCorner = Vector3D.ZERO;
    925         final Vector3D upperCorner = Vector3D.of(1, 1, 1);
    926
    927         final RegionBSPTree3D tree = createRect(lowerCorner, upperCorner);
    928
    929         final Vector3D pt = Vector3D.of(0.5, 0.5, 0);
    930         final Line3D intoBoxLine = Lines3D.fromPoints(pt, pt.add(Vector3D.Unit.PLUS_Z), TEST_PRECISION);
    931         final Line3D outOfBoxLine = Lines3D.fromPoints(pt, pt.add(Vector3D.Unit.MINUS_Z), TEST_PRECISION);
    932
    933         // act/assert
    934         final LinecastPoint3D intoBoxResult = tree.linecastFirst(intoBoxLine.rayFrom(pt));
    935         EuclideanTestUtils.assertCoordinatesEqual(pt, intoBoxResult.getPoint(), TEST_EPS);
    936
    937         final LinecastPoint3D outOfBoxResult = tree.linecastFirst(outOfBoxLine.rayFrom(pt));
    938         EuclideanTestUtils.assertCoordinatesEqual(pt, outOfBoxResult.getPoint(), TEST_EPS);
    939     }
    940
    941     @Test
    942     public void testLinecastFirst_rayPointOnVertex() {
    943         // arrange
    944         final Vector3D lowerCorner = Vector3D.ZERO;
    945         final Vector3D upperCorner = Vector3D.of(1, 1, 1);
    946
    947         final RegionBSPTree3D tree = createRect(lowerCorner, upperCorner);
    948
    949         final Line3D intoBoxLine = Lines3D.fromPoints(lowerCorner, upperCorner, TEST_PRECISION);
    950         final Line3D outOfBoxLine = intoBoxLine.reverse();
    951
    952         // act/assert
    953         final LinecastPoint3D intoBoxResult = tree.linecastFirst(intoBoxLine.rayFrom(lowerCorner));
    954         EuclideanTestUtils.assertCoordinatesEqual(lowerCorner, intoBoxResult.getPoint(), TEST_EPS);
    955
    956         final LinecastPoint3D outOfBoxResult = tree.linecastFirst(outOfBoxLine.rayFrom(lowerCorner));
    957         EuclideanTestUtils.assertCoordinatesEqual(lowerCorner, outOfBoxResult.getPoint(), TEST_EPS);
    958     }
    959
    960     @Test
    961     public void testLinecastFirst_onlyReturnsPointsWithinSegment() throws IOException, ParseException {
    962         // arrange
    963         final Vector3D lowerCorner = Vector3D.ZERO;
    964         final Vector3D upperCorner = Vector3D.of(1, 1, 1);
    965
    966         final RegionBSPTree3D tree = createRect(lowerCorner, upperCorner);
    967
    968         final Line3D line = Lines3D.fromPointAndDirection(Vector3D.of(0.5, 0.5, 0.5), Vector3D.Unit.PLUS_X, TEST_PRECISION);
    969
    970         // act/assert
    971         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.Unit.MINUS_X,
    972                 tree.linecastFirst(line.span()).getNormal(), TEST_EPS);
    973         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.Unit.PLUS_X,
    974                 tree.linecastFirst(line.reverse().span()).getNormal(), TEST_EPS);
    975
    976         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.Unit.MINUS_X,
    977                 tree.linecastFirst(line.segment(Vector3D.of(-2, 0.5, 0.5), Vector3D.of(0.5, 0.5, 0.5))).getNormal(), TEST_EPS);
    978         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.Unit.MINUS_X,
    979                 tree.linecastFirst(line.segment(Vector3D.of(-2, 0.5, 0.5), Vector3D.of(0, 0.5, 0.5))).getNormal(), TEST_EPS);
    980
    981         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.Unit.PLUS_X,
    982                 tree.linecastFirst(line.segment(Vector3D.of(0.5, 0.5, 0.5), Vector3D.of(2, 0.5, 0.5))).getNormal(), TEST_EPS);
    983         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.Unit.PLUS_X,
    984                 tree.linecastFirst(line.segment(Vector3D.of(0.5, 0.5, 0.5), Vector3D.of(1, 0.5, 0.5))).getNormal(), TEST_EPS);
    985
    986         Assert.assertNull(tree.linecastFirst(line.segment(Vector3D.of(-2, 0.5, 0.5), Vector3D.of(-1, 0.5, 0.5))));
    987         Assert.assertNull(tree.linecastFirst(line.segment(Vector3D.of(-2, 0.5, 0.5), Vector3D.of(-1, 0.5, 0.5))));
    988         Assert.assertNull(tree.linecastFirst(line.segment(Vector3D.of(0.25, 0.5, 0.5), Vector3D.of(0.75, 0.5, 0.5))));
    989     }
    990
    991     @Test
    992     public void testInvertedRegion() {
    993         // arrange
    994         final RegionBSPTree3D tree = createRect(Vector3D.of(-0.5, -0.5, -0.5), Vector3D.of(0.5, 0.5, 0.5));
    995
    996         // act
    997         tree.complement();
    998
    999         // assert
    1000         Assert.assertFalse(tree.isEmpty());
    1001         Assert.assertFalse(tree.isFull());
    1002
    1003         EuclideanTestUtils.assertPositiveInfinity(tree.getSize());
    1004         Assert.assertEquals(6, tree.getBoundarySize(), TEST_EPS);
    1005         Assert.assertNull(tree.getCentroid());
    1006
    1007         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.INSIDE,
    1008                 Vector3D.of(-Double.MAX_VALUE, -Double.MAX_VALUE, -Double.MAX_VALUE),
    1009                 Vector3D.of(-100, -100, -100),
    1010                 Vector3D.of(100, 100, 100),
    1011                 Vector3D.of(Double.MAX_VALUE, Double.MAX_VALUE, Double.MAX_VALUE));
    1012         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.OUTSIDE,
    1013                 Vector3D.of(0, 0, 0));
    1014     }
    1015
    1016     @Test
    1017     public void testUnitBox() {
    1018         // act
    1019         final RegionBSPTree3D tree = createRect(Vector3D.of(-0.5, -0.5, -0.5), Vector3D.of(0.5, 0.5, 0.5));
    1020
    1021         // assert
    1022         Assert.assertFalse(tree.isEmpty());
    1023         Assert.assertFalse(tree.isFull());
    1024
    1025         Assert.assertEquals(1.0, tree.getSize(), TEST_EPS);
    1026         Assert.assertEquals(6.0, tree.getBoundarySize(), TEST_EPS);
    1027         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.ZERO, tree.getCentroid(), TEST_EPS);
    1028
    1029         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.OUTSIDE,
    1030                 Vector3D.of(-1, 0, 0),
    1031                 Vector3D.of(1, 0, 0),
    1032                 Vector3D.of(0, -1, 0),
    1033                 Vector3D.of(0, 1, 0),
    1034                 Vector3D.of(0, 0, -1),
    1035                 Vector3D.of(0, 0, 1),
    1036
    1037                 Vector3D.of(1, 1, 1),
    1038                 Vector3D.of(1, 1, -1),
    1039                 Vector3D.of(1, -1, 1),
    1040                 Vector3D.of(1, -1, -1),
    1041                 Vector3D.of(-1, 1, 1),
    1042                 Vector3D.of(-1, 1, -1),
    1043                 Vector3D.of(-1, -1, 1),
    1044                 Vector3D.of(-1, -1, -1));
    1045
    1046         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.BOUNDARY,
    1047                 Vector3D.of(0.5, 0, 0),
    1048                 Vector3D.of(-0.5, 0, 0),
    1049                 Vector3D.of(0, 0.5, 0),
    1050                 Vector3D.of(0, -0.5, 0),
    1051                 Vector3D.of(0, 0, 0.5),
    1052                 Vector3D.of(0, 0, -0.5),
    1053
    1054                 Vector3D.of(0.5, 0.5, 0.5),
    1055                 Vector3D.of(0.5, 0.5, -0.5),
    1056                 Vector3D.of(0.5, -0.5, 0.5),
    1057                 Vector3D.of(0.5, -0.5, -0.5),
    1058                 Vector3D.of(-0.5, 0.5, 0.5),
    1059                 Vector3D.of(-0.5, 0.5, -0.5),
    1060                 Vector3D.of(-0.5, -0.5, 0.5),
    1061                 Vector3D.of(-0.5, -0.5, -0.5));
    1062
    1063         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.INSIDE,
    1064                 Vector3D.of(0, 0, 0),
    1065
    1066                 Vector3D.of(0.4, 0.4, 0.4),
    1067                 Vector3D.of(0.4, 0.4, -0.4),
    1068                 Vector3D.of(0.4, -0.4, 0.4),
    1069                 Vector3D.of(0.4, -0.4, -0.4),
    1070                 Vector3D.of(-0.4, 0.4, 0.4),
    1071                 Vector3D.of(-0.4, 0.4, -0.4),
    1072                 Vector3D.of(-0.4, -0.4, 0.4),
    1073                 Vector3D.of(-0.4, -0.4, -0.4));
    1074     }
    1075
    1076     @Test
    1077     public void testTwoBoxes_disjoint() {
    1078         // act
    1079         final RegionBSPTree3D tree = RegionBSPTree3D.empty();
    1080         tree.union(createRect(Vector3D.of(-0.5, -0.5, -0.5), Vector3D.of(0.5, 0.5, 0.5)));
    1081         tree.union(createRect(Vector3D.of(1.5, -0.5, -0.5), Vector3D.of(2.5, 0.5, 0.5)));
    1082
    1083         // assert
    1084         Assert.assertFalse(tree.isEmpty());
    1085         Assert.assertFalse(tree.isFull());
    1086
    1087         Assert.assertEquals(2.0, tree.getSize(), TEST_EPS);
    1088         Assert.assertEquals(12.0, tree.getBoundarySize(), TEST_EPS);
    1089         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, 0, 0), tree.getCentroid(), TEST_EPS);
    1090
    1091         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.OUTSIDE,
    1092                 Vector3D.of(-1, 0, 0),
    1093                 Vector3D.of(1, 0, 0),
    1094                 Vector3D.of(3, 0, 0));
    1095
    1096         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.INSIDE,
    1097                 Vector3D.of(0, 0, 0),
    1098                 Vector3D.of(2, 0, 0));
    1099     }
    1100
    1101     @Test
    1102     public void testTwoBoxes_sharedSide() {
    1103         // act
    1104         final RegionBSPTree3D tree = RegionBSPTree3D.empty();
    1105         tree.union(createRect(Vector3D.of(-0.5, -0.5, -0.5), Vector3D.of(0.5, 0.5, 0.5)));
    1106         tree.union(createRect(Vector3D.of(0.5, -0.5, -0.5), Vector3D.of(1.5, 0.5, 0.5)));
    1107
    1108         // assert
    1109         Assert.assertFalse(tree.isEmpty());
    1110         Assert.assertFalse(tree.isFull());
    1111
    1112         Assert.assertEquals(2.0, tree.getSize(), TEST_EPS);
    1113         Assert.assertEquals(10.0, tree.getBoundarySize(), TEST_EPS);
    1114         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0.5, 0, 0), tree.getCentroid(), TEST_EPS);
    1115
    1116         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.OUTSIDE,
    1117                 Vector3D.of(-1, 0, 0),
    1118                 Vector3D.of(2, 0, 0));
    1119
    1120         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.INSIDE,
    1121                 Vector3D.of(0, 0, 0),
    1122                 Vector3D.of(1, 0, 0));
    1123     }
    1124
    1125     @Test
    1126     public void testTwoBoxes_separationLessThanTolerance() {
    1127         // arrange
    1128         final double eps = 1e-6;
    1129         final DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(eps);
    1130
    1131         // act
    1132         final RegionBSPTree3D tree = RegionBSPTree3D.empty();
    1133         tree.union(createRect(Vector3D.of(-0.5, -0.5, -0.5), Vector3D.of(0.5, 0.5, 0.5), precision));
    1134         tree.union(createRect(Vector3D.of(0.5 + 1e-7, -0.5, -0.5), Vector3D.of(1.5 + 1e-7, 0.5, 0.5), precision));
    1135
    1136         // assert
    1137         Assert.assertFalse(tree.isEmpty());
    1138         Assert.assertFalse(tree.isFull());
    1139
    1140         Assert.assertEquals(2.0, tree.getSize(), eps);
    1141         Assert.assertEquals(10.0, tree.getBoundarySize(), eps);
    1142         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0.5 + 5.4166e-8, 0, 0), tree.getCentroid(), TEST_EPS);
    1143
    1144         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.OUTSIDE,
    1145                 Vector3D.of(-1, 0, 0),
    1146                 Vector3D.of(2, 0, 0));
    1147
    1148         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.INSIDE,
    1149                 Vector3D.of(0, 0, 0),
    1150                 Vector3D.of(1, 0, 0));
    1151     }
    1152
    1153     @Test
    1154     public void testTwoBoxes_sharedEdge() {
    1155         // act
    1156         final RegionBSPTree3D tree = RegionBSPTree3D.empty();
    1157         tree.union(createRect(Vector3D.of(-0.5, -0.5, -0.5), Vector3D.of(0.5, 0.5, 0.5)));
    1158         tree.union(createRect(Vector3D.of(0.5, 0.5, -0.5), Vector3D.of(1.5, 1.5, 0.5)));
    1159
    1160         // assert
    1161         Assert.assertFalse(tree.isEmpty());
    1162         Assert.assertFalse(tree.isFull());
    1163
    1164         Assert.assertEquals(2.0, tree.getSize(), TEST_EPS);
    1165         Assert.assertEquals(12.0, tree.getBoundarySize(), TEST_EPS);
    1166         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0.5, 0.5, 0), tree.getCentroid(), TEST_EPS);
    1167
    1168
    1169         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.OUTSIDE,
    1170                 Vector3D.of(-1, 0, 0),
    1171                 Vector3D.of(1, 0, 0),
    1172                 Vector3D.of(0, 1, 0),
    1173                 Vector3D.of(2, 1, 0));
    1174
    1175         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.INSIDE,
    1176                 Vector3D.of(0, 0, 0),
    1177                 Vector3D.of(1, 1, 0));
    1178     }
    1179
    1180     @Test
    1181     public void testTwoBoxes_sharedPoint() {
    1182         // act
    1183         final RegionBSPTree3D tree = RegionBSPTree3D.empty();
    1184         tree.union(createRect(Vector3D.of(-0.5, -0.5, -0.5), Vector3D.of(0.5, 0.5, 0.5)));
    1185         tree.union(createRect(Vector3D.of(0.5, 0.5, 0.5), Vector3D.of(1.5, 1.5, 1.5)));
    1186
    1187         // assert
    1188         Assert.assertFalse(tree.isEmpty());
    1189         Assert.assertFalse(tree.isFull());
    1190
    1191         Assert.assertEquals(2.0, tree.getSize(), TEST_EPS);
    1192         Assert.assertEquals(12.0, tree.getBoundarySize(), TEST_EPS);
    1193         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0.5, 0.5, 0.5), tree.getCentroid(), TEST_EPS);
    1194
    1195         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.OUTSIDE,
    1196                 Vector3D.of(-1, 0, 0),
    1197                 Vector3D.of(1, 0, 0),
    1198                 Vector3D.of(0, 1, 1),
    1199                 Vector3D.of(2, 1, 1));
    1200
    1201         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.INSIDE,
    1202                 Vector3D.of(0, 0, 0),
    1203                 Vector3D.of(1, 1, 1));
    1204     }
    1205
    1206     @Test
    1207     public void testTetrahedron() {
    1208         // arrange
    1209         final Vector3D vertex1 = Vector3D.of(1, 2, 3);
    1210         final Vector3D vertex2 = Vector3D.of(2, 2, 4);
    1211         final Vector3D vertex3 = Vector3D.of(2, 3, 3);
    1212         final Vector3D vertex4 = Vector3D.of(1, 3, 4);
    1213
    1214         final List<PlaneConvexSubset> boundaries = Arrays.asList(
    1215                 Planes.convexPolygonFromVertices(Arrays.asList(vertex3, vertex2, vertex1), TEST_PRECISION),
    1216                 Planes.convexPolygonFromVertices(Arrays.asList(vertex2, vertex3, vertex4), TEST_PRECISION),
    1217                 Planes.convexPolygonFromVertices(Arrays.asList(vertex4, vertex3, vertex1), TEST_PRECISION),
    1218                 Planes.convexPolygonFromVertices(Arrays.asList(vertex1, vertex2, vertex4), TEST_PRECISION)
    1219             );
    1220
    1221         // act
    1222         final RegionBSPTree3D tree = RegionBSPTree3D.full();
    1223         tree.insert(boundaries);
    1224
    1225         // assert
    1226         Assert.assertEquals(1.0 / 3.0, tree.getSize(), TEST_EPS);
    1227         Assert.assertEquals(2.0 * Math.sqrt(3.0), tree.getBoundarySize(), TEST_EPS);
    1228         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1.5, 2.5, 3.5), tree.getCentroid(), TEST_EPS);
    1229
    1230         final double third = 1.0 / 3.0;
    1231         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.BOUNDARY,
    1232             vertex1, vertex2, vertex3, vertex4,
    1233             Vector3D.linearCombination(third, vertex1, third, vertex2, third, vertex3),
    1234             Vector3D.linearCombination(third, vertex2, third, vertex3, third, vertex4),
    1235             Vector3D.linearCombination(third, vertex3, third, vertex4, third, vertex1),
    1236             Vector3D.linearCombination(third, vertex4, third, vertex1, third, vertex2)
    1237         );
    1238         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.OUTSIDE,
    1239             Vector3D.of(1, 2, 4),
    1240             Vector3D.of(2, 2, 3),
    1241             Vector3D.of(2, 3, 4),
    1242             Vector3D.of(1, 3, 3)
    1243         );
    1244     }
    1245
    1246     @Test
    1247     public void testSphere() {
    1248         // arrange
    1249         // (use a high tolerance value here since the sphere is only an approximation)
    1250         final double approximationTolerance = 0.2;
    1251         final double radius = 1.0;
    1252
    1253         // act
    1254         final RegionBSPTree3D tree = createSphere(Vector3D.of(1, 2, 3), radius, 8, 16);
    1255
    1256         // assert
    1257         Assert.assertFalse(tree.isEmpty());
    1258         Assert.assertFalse(tree.isFull());
    1259
    1260         Assert.assertEquals(sphereVolume(radius), tree.getSize(), approximationTolerance);
    1261         Assert.assertEquals(sphereSurface(radius), tree.getBoundarySize(), approximationTolerance);
    1262         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, 2, 3), tree.getCentroid(), TEST_EPS);
    1263
    1264         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.OUTSIDE,
    1265                 Vector3D.of(-0.1, 2, 3),
    1266                 Vector3D.of(2.1, 2, 3),
    1267                 Vector3D.of(1, 0.9, 3),
    1268                 Vector3D.of(1, 3.1, 3),
    1269                 Vector3D.of(1, 2, 1.9),
    1270                 Vector3D.of(1, 2, 4.1),
    1271                 Vector3D.of(1.6, 2.6, 3.6));
    1272
    1273         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.INSIDE,
    1274                 Vector3D.of(1, 2, 3),
    1275                 Vector3D.of(0.1, 2, 3),
    1276                 Vector3D.of(1.9, 2, 3),
    1277                 Vector3D.of(1, 2.1, 3),
    1278                 Vector3D.of(1, 2.9, 3),
    1279                 Vector3D.of(1, 2, 2.1),
    1280                 Vector3D.of(1, 2, 3.9),
    1281                 Vector3D.of(1.5, 2.5, 3.5));
    1282     }
    1283
    1284     @Test
    1285     public void testProjectToBoundary() {
    1286         // arrange
    1287         final RegionBSPTree3D tree = createRect(Vector3D.ZERO, Vector3D.of(1, 1, 1));
    1288
    1289         // act/assert
    1290         checkProject(tree, Vector3D.of(0.5, 0.5, 0.5), Vector3D.of(0, 0.5, 0.5));
    1291         checkProject(tree, Vector3D.of(0.4, 0.5, 0.5), Vector3D.of(0, 0.5, 0.5));
    1292         checkProject(tree, Vector3D.of(1.5, 0.5, 0.5), Vector3D.of(1, 0.5, 0.5));
    1293         checkProject(tree, Vector3D.of(2, 2, 2), Vector3D.of(1, 1, 1));
    1294     }
    1295
    1296     @Test
    1297     public void testProjectToBoundary_invertedRegion() {
    1298         // arrange
    1299         final RegionBSPTree3D tree = createRect(Vector3D.ZERO, Vector3D.of(1, 1, 1));
    1300
    1301         tree.complement();
    1302
    1303         // act/assert
    1304         checkProject(tree, Vector3D.of(0.4, 0.5, 0.5), Vector3D.of(0, 0.5, 0.5));
    1305         checkProject(tree, Vector3D.of(1.5, 0.5, 0.5), Vector3D.of(1, 0.5, 0.5));
    1306         checkProject(tree, Vector3D.of(2, 2, 2), Vector3D.of(1, 1, 1));
    1307     }
    1308
    1309     private void checkProject(final RegionBSPTree3D tree, final Vector3D toProject, final Vector3D expectedPoint) {
    1310         final Vector3D proj = tree.project(toProject);
    1311
    1312         EuclideanTestUtils.assertCoordinatesEqual(expectedPoint, proj, TEST_EPS);
    1313     }
    1314
    1315     @Test
    1316     public void testBoolean_union() throws IOException {
    1317         // arrange
    1318         final double tolerance = 0.05;
    1319         final double size = 1.0;
    1320         final double radius = size * 0.5;
    1321         final RegionBSPTree3D box = createRect(Vector3D.ZERO, Vector3D.of(size, size, size));
    1322         final RegionBSPTree3D sphere = createSphere(Vector3D.of(size * 0.5, size * 0.5, size), radius, 8, 16);
    1323
    1324         // act
    1325         final RegionBSPTree3D result = RegionBSPTree3D.empty();
    1326         result.union(box, sphere);
    1327
    1328         // assert
    1329         Assert.assertFalse(result.isEmpty());
    1330         Assert.assertFalse(result.isFull());
    1331
    1332         Assert.assertEquals(cubeVolume(size) + (sphereVolume(radius) * 0.5),
    1333                 result.getSize(), tolerance);
    1334         Assert.assertEquals(cubeSurface(size) - circleSurface(radius) + (0.5 * sphereSurface(radius)),
    1335                 result.getBoundarySize(), tolerance);
    1336
    1337         EuclideanTestUtils.assertRegionLocation(result, RegionLocation.OUTSIDE,
    1338                 Vector3D.of(-0.1, 0.5, 0.5),
    1339                 Vector3D.of(1.1, 0.5, 0.5),
    1340                 Vector3D.of(0.5, -0.1, 0.5),
    1341                 Vector3D.of(0.5, 1.1, 0.5),
    1342                 Vector3D.of(0.5, 0.5, -0.1),
    1343                 Vector3D.of(0.5, 0.5, 1.6));
    1344
    1345         EuclideanTestUtils.assertRegionLocation(result, RegionLocation.INSIDE,
    1346                 Vector3D.of(0.1, 0.5, 0.5),
    1347                 Vector3D.of(0.9, 0.5, 0.5),
    1348                 Vector3D.of(0.5, 0.1, 0.5),
    1349                 Vector3D.of(0.5, 0.9, 0.5),
    1350                 Vector3D.of(0.5, 0.5, 0.1),
    1351                 Vector3D.of(0.5, 0.5, 1.4));
    1352     }
    1353
    1354     @Test
    1355     public void testUnion_self() {
    1356         // arrange
    1357         final double tolerance = 0.2;
    1358         final double radius = 1.0;
    1359
    1360         final RegionBSPTree3D sphere = createSphere(Vector3D.ZERO, radius, 8, 16);
    1361
    1362         final RegionBSPTree3D copy = RegionBSPTree3D.empty();
    1363         copy.copy(sphere);
    1364
    1365         // act
    1366         final RegionBSPTree3D result = RegionBSPTree3D.empty();
    1367         result.union(sphere, copy);
    1368
    1369         // assert
    1370         Assert.assertFalse(result.isEmpty());
    1371         Assert.assertFalse(result.isFull());
    1372
    1373         Assert.assertEquals(sphereVolume(radius), result.getSize(), tolerance);
    1374         Assert.assertEquals(sphereSurface(radius), result.getBoundarySize(), tolerance);
    1375         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.ZERO, result.getCentroid(), TEST_EPS);
    1376
    1377         EuclideanTestUtils.assertRegionLocation(result, RegionLocation.OUTSIDE,
    1378                 Vector3D.of(-1.1, 0, 0),
    1379                 Vector3D.of(1.1, 0, 0),
    1380                 Vector3D.of(0, -1.1, 0),
    1381                 Vector3D.of(0, 1.1, 0),
    1382                 Vector3D.of(0, 0, -1.1),
    1383                 Vector3D.of(0, 0, 1.1));
    1384
    1385         EuclideanTestUtils.assertRegionLocation(result, RegionLocation.INSIDE,
    1386                 Vector3D.of(-0.9, 0, 0),
    1387                 Vector3D.of(0.9, 0, 0),
    1388                 Vector3D.of(0, -0.9, 0),
    1389                 Vector3D.of(0, 0.9, 0),
    1390                 Vector3D.of(0, 0, -0.9),
    1391                 Vector3D.of(0, 0, 0.9),
    1392                 Vector3D.ZERO);
    1393     }
    1394
    1395     @Test
    1396     public void testBoolean_intersection() throws IOException {
    1397         // arrange
    1398         final double tolerance = 0.05;
    1399         final double size = 1.0;
    1400         final double radius = size * 0.5;
    1401         final RegionBSPTree3D box = createRect(Vector3D.ZERO, Vector3D.of(size, size, size));
    1402         final RegionBSPTree3D sphere = createSphere(Vector3D.of(size * 0.5, size * 0.5, size), radius, 8, 16);
    1403
    1404         // act
    1405         final RegionBSPTree3D result = RegionBSPTree3D.empty();
    1406         result.intersection(box, sphere);
    1407
    1408         // assert
    1409         Assert.assertFalse(result.isEmpty());
    1410         Assert.assertFalse(result.isFull());
    1411
    1412         Assert.assertEquals(sphereVolume(radius) * 0.5, result.getSize(), tolerance);
    1413         Assert.assertEquals(circleSurface(radius) + (0.5 * sphereSurface(radius)),
    1414                 result.getBoundarySize(), tolerance);
    1415
    1416         EuclideanTestUtils.assertRegionLocation(result, RegionLocation.OUTSIDE,
    1417                 Vector3D.of(-0.1, 0.5, 1.0),
    1418                 Vector3D.of(1.1, 0.5, 1.0),
    1419                 Vector3D.of(0.5, -0.1, 1.0),
    1420                 Vector3D.of(0.5, 1.1, 1.0),
    1421                 Vector3D.of(0.5, 0.5, 0.4),
    1422                 Vector3D.of(0.5, 0.5, 1.1));
    1423
    1424         EuclideanTestUtils.assertRegionLocation(result, RegionLocation.INSIDE,
    1425                 Vector3D.of(0.1, 0.5, 0.9),
    1426                 Vector3D.of(0.9, 0.5, 0.9),
    1427                 Vector3D.of(0.5, 0.1, 0.9),
    1428                 Vector3D.of(0.5, 0.9, 0.9),
    1429                 Vector3D.of(0.5, 0.5, 0.6),
    1430                 Vector3D.of(0.5, 0.5, 0.9));
    1431     }
    1432
    1433     @Test
    1434     public void testIntersection_self() {
    1435         // arrange
    1436         final double tolerance = 0.2;
    1437         final double radius = 1.0;
    1438
    1439         final RegionBSPTree3D sphere = createSphere(Vector3D.ZERO, radius, 8, 16);
    1440         final RegionBSPTree3D copy = RegionBSPTree3D.empty();
    1441         copy.copy(sphere);
    1442
    1443         // act
    1444         final RegionBSPTree3D result = RegionBSPTree3D.empty();
    1445         result.intersection(sphere, copy);
    1446
    1447         // assert
    1448         Assert.assertFalse(result.isEmpty());
    1449         Assert.assertFalse(result.isFull());
    1450
    1451         Assert.assertEquals(sphereVolume(radius), result.getSize(), tolerance);
    1452         Assert.assertEquals(sphereSurface(radius), result.getBoundarySize(), tolerance);
    1453         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.ZERO, result.getCentroid(), TEST_EPS);
    1454
    1455         EuclideanTestUtils.assertRegionLocation(result, RegionLocation.OUTSIDE,
    1456                 Vector3D.of(-1.1, 0, 0),
    1457                 Vector3D.of(1.1, 0, 0),
    1458                 Vector3D.of(0, -1.1, 0),
    1459                 Vector3D.of(0, 1.1, 0),
    1460                 Vector3D.of(0, 0, -1.1),
    1461                 Vector3D.of(0, 0, 1.1));
    1462
    1463         EuclideanTestUtils.assertRegionLocation(result, RegionLocation.INSIDE,
    1464                 Vector3D.of(-0.9, 0, 0),
    1465                 Vector3D.of(0.9, 0, 0),
    1466                 Vector3D.of(0, -0.9, 0),
    1467                 Vector3D.of(0, 0.9, 0),
    1468                 Vector3D.of(0, 0, -0.9),
    1469                 Vector3D.of(0, 0, 0.9),
    1470                 Vector3D.ZERO);
    1471     }
    1472
    1473     @Test
    1474     public void testBoolean_xor_twoCubes() throws IOException {
    1475         // arrange
    1476         final double size = 1.0;
    1477         final RegionBSPTree3D box1 = createRect(Vector3D.ZERO, Vector3D.of(size, size, size));
    1478         final RegionBSPTree3D box2 = createRect(Vector3D.of(0.5, 0.5, 0.5), Vector3D.of(0.5 + size, 0.5 + size, 0.5 + size));
    1479
    1480         // act
    1481         final RegionBSPTree3D result = RegionBSPTree3D.empty();
    1482         result.xor(box1, box2);
    1483
    1484         // assert
    1485         Assert.assertFalse(result.isEmpty());
    1486         Assert.assertFalse(result.isFull());
    1487
    1488         Assert.assertEquals((2 * cubeVolume(size)) - (2 * cubeVolume(size * 0.5)), result.getSize(), TEST_EPS);
    1489         Assert.assertEquals(2 * cubeSurface(size), result.getBoundarySize(), TEST_EPS);
    1490
    1491         EuclideanTestUtils.assertRegionLocation(result, RegionLocation.OUTSIDE,
    1492                 Vector3D.of(-0.1, -0.1, -0.1),
    1493                 Vector3D.of(0.75, 0.75, 0.75),
    1494                 Vector3D.of(1.6, 1.6, 1.6));
    1495
    1496         EuclideanTestUtils.assertRegionLocation(result, RegionLocation.BOUNDARY,
    1497                 Vector3D.of(0, 0, 0),
    1498                 Vector3D.of(0.5, 0.5, 0.5),
    1499                 Vector3D.of(1, 1, 1),
    1500                 Vector3D.of(1.5, 1.5, 1.5));
    1501
    1502         EuclideanTestUtils.assertRegionLocation(result, RegionLocation.INSIDE,
    1503                 Vector3D.of(0.1, 0.1, 0.1),
    1504                 Vector3D.of(0.4, 0.4, 0.4),
    1505                 Vector3D.of(1.1, 1.1, 1.1),
    1506                 Vector3D.of(1.4, 1.4, 1.4));
    1507     }
    1508
    1509     @Test
    1510     public void testBoolean_xor_cubeAndSphere() throws IOException {
    1511         // arrange
    1512         final double tolerance = 0.05;
    1513         final double size = 1.0;
    1514         final double radius = size * 0.5;
    1515         final RegionBSPTree3D box = createRect(Vector3D.ZERO, Vector3D.of(size, size, size));
    1516         final RegionBSPTree3D sphere = createSphere(Vector3D.of(size * 0.5, size * 0.5, size), radius, 8, 16);
    1517
    1518         // act
    1519         final RegionBSPTree3D result = RegionBSPTree3D.empty();
    1520         result.xor(box, sphere);
    1521
    1522         // assert
    1523         Assert.assertFalse(result.isEmpty());
    1524         Assert.assertFalse(result.isFull());
    1525
    1526         Assert.assertEquals(cubeVolume(size), result.getSize(), tolerance);
    1527         Assert.assertEquals(cubeSurface(size) + (sphereSurface(radius)),
    1528                 result.getBoundarySize(), tolerance);
    1529
    1530         EuclideanTestUtils.assertRegionLocation(result, RegionLocation.OUTSIDE,
    1531                 Vector3D.of(-0.1, 0.5, 0.5),
    1532                 Vector3D.of(1.1, 0.5, 0.5),
    1533                 Vector3D.of(0.5, -0.1, 0.5),
    1534                 Vector3D.of(0.5, 1.1, 0.5),
    1535                 Vector3D.of(0.5, 0.5, -0.1),
    1536                 Vector3D.of(0.5, 0.5, 1.6),
    1537                 Vector3D.of(0.5, 0.5, 0.9));
    1538
    1539         EuclideanTestUtils.assertRegionLocation(result, RegionLocation.INSIDE,
    1540                 Vector3D.of(0.1, 0.5, 0.5),
    1541                 Vector3D.of(0.9, 0.5, 0.5),
    1542                 Vector3D.of(0.5, 0.1, 0.5),
    1543                 Vector3D.of(0.5, 0.9, 0.5),
    1544                 Vector3D.of(0.5, 0.5, 0.1),
    1545                 Vector3D.of(0.5, 0.5, 1.4));
    1546     }
    1547
    1548     @Test
    1549     public void testXor_self() {
    1550         // arrange
    1551         final double radius = 1.0;
    1552
    1553         final RegionBSPTree3D sphere = createSphere(Vector3D.ZERO, radius, 8, 16);
    1554         final RegionBSPTree3D copy = RegionBSPTree3D.empty();
    1555         copy.copy(sphere);
    1556
    1557         // act
    1558         final RegionBSPTree3D result = RegionBSPTree3D.empty();
    1559         result.xor(sphere, copy);
    1560
    1561         // assert
    1562         Assert.assertTrue(result.isEmpty());
    1563         Assert.assertFalse(result.isFull());
    1564
    1565         Assert.assertEquals(0.0, result.getSize(), TEST_EPS);
    1566         Assert.assertEquals(0.0, result.getBoundarySize(), TEST_EPS);
    1567         Assert.assertNull(result.getCentroid());
    1568
    1569         EuclideanTestUtils.assertRegionLocation(result, RegionLocation.OUTSIDE,
    1570                 Vector3D.of(-1.1, 0, 0),
    1571                 Vector3D.of(1.1, 0, 0),
    1572                 Vector3D.of(0, -1.1, 0),
    1573                 Vector3D.of(0, 1.1, 0),
    1574                 Vector3D.of(0, 0, -1.1),
    1575                 Vector3D.of(0, 0, 1.1),
    1576                 Vector3D.of(-0.9, 0, 0),
    1577                 Vector3D.of(0.9, 0, 0),
    1578                 Vector3D.of(0, -0.9, 0),
    1579                 Vector3D.of(0, 0.9, 0),
    1580                 Vector3D.of(0, 0, -0.9),
    1581                 Vector3D.of(0, 0, 0.9),
    1582                 Vector3D.ZERO);
    1583     }
    1584
    1585     @Test
    1586     public void testBoolean_difference() throws IOException {
    1587         // arrange
    1588         final double tolerance = 0.05;
    1589         final double size = 1.0;
    1590         final double radius = size * 0.5;
    1591         final RegionBSPTree3D box = createRect(Vector3D.ZERO, Vector3D.of(size, size, size));
    1592         final RegionBSPTree3D sphere = createSphere(Vector3D.of(size * 0.5, size * 0.5, size), radius, 8, 16);
    1593
    1594         // act
    1595         final RegionBSPTree3D result = RegionBSPTree3D.empty();
    1596         result.difference(box, sphere);
    1597
    1598         // assert
    1599         Assert.assertFalse(result.isEmpty());
    1600         Assert.assertFalse(result.isFull());
    1601
    1602         Assert.assertEquals(cubeVolume(size) - (sphereVolume(radius) * 0.5), result.getSize(), tolerance);
    1603         Assert.assertEquals(cubeSurface(size) - circleSurface(radius) + (0.5 * sphereSurface(radius)),
    1604                 result.getBoundarySize(), tolerance);
    1605
    1606         EuclideanTestUtils.assertRegionLocation(result, RegionLocation.OUTSIDE,
    1607                 Vector3D.of(-0.1, 0.5, 1.0),
    1608                 Vector3D.of(1.1, 0.5, 1.0),
    1609                 Vector3D.of(0.5, -0.1, 1.0),
    1610                 Vector3D.of(0.5, 1.1, 1.0),
    1611                 Vector3D.of(0.5, 0.5, -0.1),
    1612                 Vector3D.of(0.5, 0.5, 0.6));
    1613
    1614         EuclideanTestUtils.assertRegionLocation(result, RegionLocation.INSIDE,
    1615                 Vector3D.of(0.1, 0.5, 0.4),
    1616                 Vector3D.of(0.9, 0.5, 0.4),
    1617                 Vector3D.of(0.5, 0.1, 0.4),
    1618                 Vector3D.of(0.5, 0.9, 0.4),
    1619                 Vector3D.of(0.5, 0.5, 0.1),
    1620                 Vector3D.of(0.5, 0.5, 0.4));
    1621     }
    1622
    1623     @Test
    1624     public void testDifference_self() {
    1625         // arrange
    1626         final double radius = 1.0;
    1627
    1628         final RegionBSPTree3D sphere = createSphere(Vector3D.ZERO, radius, 8, 16);
    1629         final RegionBSPTree3D copy = sphere.copy();
    1630
    1631         // act
    1632         final RegionBSPTree3D result = RegionBSPTree3D.empty();
    1633         result.difference(sphere, copy);
    1634
    1635         // assert
    1636         Assert.assertTrue(result.isEmpty());
    1637         Assert.assertFalse(result.isFull());
    1638
    1639         Assert.assertEquals(0.0, result.getSize(), TEST_EPS);
    1640         Assert.assertEquals(0.0, result.getBoundarySize(), TEST_EPS);
    1641         Assert.assertNull(result.getCentroid());
    1642
    1643         EuclideanTestUtils.assertRegionLocation(result, RegionLocation.OUTSIDE,
    1644                 Vector3D.of(-1.1, 0, 0),
    1645                 Vector3D.of(1.1, 0, 0),
    1646                 Vector3D.of(0, -1.1, 0),
    1647                 Vector3D.of(0, 1.1, 0),
    1648                 Vector3D.of(0, 0, -1.1),
    1649                 Vector3D.of(0, 0, 1.1),
    1650                 Vector3D.of(-0.9, 0, 0),
    1651                 Vector3D.of(0.9, 0, 0),
    1652                 Vector3D.of(0, -0.9, 0),
    1653                 Vector3D.of(0, 0.9, 0),
    1654                 Vector3D.of(0, 0, -0.9),
    1655                 Vector3D.of(0, 0, 0.9),
    1656                 Vector3D.ZERO);
    1657     }
    1658
    1659     @Test
    1660     public void testBoolean_multiple() throws IOException {
    1661         // arrange
    1662         final double tolerance = 0.05;
    1663         final double size = 1.0;
    1664         final double radius = size * 0.5;
    1665         final RegionBSPTree3D box = createRect(Vector3D.ZERO, Vector3D.of(size, size, size));
    1666         final RegionBSPTree3D sphereToAdd = createSphere(Vector3D.of(size * 0.5, size * 0.5, size), radius, 8, 16);
    1667         final RegionBSPTree3D sphereToRemove1 = createSphere(Vector3D.of(size * 0.5, 0, size * 0.5), radius, 8, 16);
    1668         final RegionBSPTree3D sphereToRemove2 = createSphere(Vector3D.of(size * 0.5, 1, size * 0.5), radius, 8, 16);
    1669
    1670         // act
    1671         final RegionBSPTree3D result = RegionBSPTree3D.empty();
    1672         result.union(box, sphereToAdd);
    1673         result.difference(sphereToRemove1);
    1674         result.difference(sphereToRemove2);
    1675
    1676         // assert
    1677         Assert.assertFalse(result.isEmpty());
    1678         Assert.assertFalse(result.isFull());
    1679
    1680         Assert.assertEquals(cubeVolume(size) - (sphereVolume(radius) * 0.5),
    1681                 result.getSize(), tolerance);
    1682         Assert.assertEquals(cubeSurface(size) - (3.0 * circleSurface(radius)) + (1.5 * sphereSurface(radius)),
    1683                 result.getBoundarySize(), tolerance);
    1684
    1685         EuclideanTestUtils.assertRegionLocation(result, RegionLocation.OUTSIDE,
    1686                 Vector3D.of(-0.1, 0.5, 0.5),
    1687                 Vector3D.of(1.1, 0.5, 0.5),
    1688                 Vector3D.of(0.5, 0.4, 0.5),
    1689                 Vector3D.of(0.5, 0.6, 0.5),
    1690                 Vector3D.of(0.5, 0.5, -0.1),
    1691                 Vector3D.of(0.5, 0.5, 1.6));
    1692
    1693         EuclideanTestUtils.assertRegionLocation(result, RegionLocation.INSIDE,
    1694                 Vector3D.of(0.1, 0.5, 0.1),
    1695                 Vector3D.of(0.9, 0.5, 0.1),
    1696                 Vector3D.of(0.5, 0.4, 0.1),
    1697                 Vector3D.of(0.5, 0.6, 0.1),
    1698                 Vector3D.of(0.5, 0.5, 0.1),
    1699                 Vector3D.of(0.5, 0.5, 1.4));
    1700     }
    1701
    1702     @Test
    1703     public void testToConvex_empty() {
    1704         // act
    1705         final List<ConvexVolume> result = RegionBSPTree3D.empty().toConvex();
    1706
    1707         // assert
    1708         Assert.assertEquals(0, result.size());
    1709     }
    1710
    1711     @Test
    1712     public void testToConvex_singleBox() {
    1713         // arrange
    1714         final RegionBSPTree3D tree = createRect(Vector3D.of(1, 2, 3), Vector3D.of(2, 3, 4));
    1715
    1716         // act
    1717         final List<ConvexVolume> result = tree.toConvex();
    1718
    1719         // assert
    1720         Assert.assertEquals(1, result.size());
    1721
    1722         final ConvexVolume vol = result.get(0);
    1723         Assert.assertEquals(1, vol.getSize(), TEST_EPS);
    1724         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1.5, 2.5, 3.5), vol.getCentroid(), TEST_EPS);
    1725     }
    1726
    1727     @Test
    1728     public void testToConvex_multipleBoxes() {
    1729         // arrange
    1730         final RegionBSPTree3D tree = createRect(Vector3D.of(4, 5, 6), Vector3D.of(5, 6, 7));
    1731         tree.union(createRect(Vector3D.ZERO, Vector3D.of(2, 1, 1)));
    1732
    1733         // act
    1734         final List<ConvexVolume> result = tree.toConvex();
    1735
    1736         // assert
    1737         Assert.assertEquals(2, result.size());
    1738
    1739         final boolean smallFirst = result.get(0).getSize() < result.get(1).getSize();
    1740
    1741         final ConvexVolume small = smallFirst ? result.get(0) : result.get(1);
    1742         final ConvexVolume large = smallFirst ? result.get(1) : result.get(0);
    1743
    1744         Assert.assertEquals(1, small.getSize(), TEST_EPS);
    1745         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(4.5, 5.5, 6.5), small.getCentroid(), TEST_EPS);
    1746
    1747         Assert.assertEquals(2, large.getSize(), TEST_EPS);
    1748         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, 0.5, 0.5), large.getCentroid(), TEST_EPS);
    1749     }
    1750
    1751     @Test
    1752     public void testSplit() {
    1753         // arrange
    1754         final RegionBSPTree3D tree = createRect(Vector3D.of(-0.5, -0.5, -0.5), Vector3D.of(0.5, 0.5, 0.5));
    1755
    1756         final Plane splitter = Planes.fromNormal(Vector3D.Unit.PLUS_X, TEST_PRECISION);
    1757
    1758         // act
    1759         final Split<RegionBSPTree3D> split = tree.split(splitter);
    1760
    1761         // assert
    1762         Assert.assertEquals(SplitLocation.BOTH, split.getLocation());
    1763
    1764         final RegionBSPTree3D minus = split.getMinus();
    1765         Assert.assertEquals(0.5, minus.getSize(), TEST_EPS);
    1766         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(-0.25, 0, 0), minus.getCentroid(), TEST_EPS);
    1767
    1768         final RegionBSPTree3D plus = split.getPlus();
    1769         Assert.assertEquals(0.5, plus.getSize(), TEST_EPS);
    1770         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0.25, 0, 0), plus.getCentroid(), TEST_EPS);
    1771     }
    1772
    1773     @Test
    1774     public void testGetNodeRegion() {
    1775         // arrange
    1776         final RegionBSPTree3D tree = createRect(Vector3D.ZERO, Vector3D.of(1, 1, 1));
    1777
    1778         // act/assert
    1779         final ConvexVolume rootVol = tree.getRoot().getNodeRegion();
    1780         GeometryTestUtils.assertPositiveInfinity(rootVol.getSize());
    1781         Assert.assertNull(rootVol.getCentroid());
    1782
    1783         final ConvexVolume plusVol = tree.getRoot().getPlus().getNodeRegion();
    1784         GeometryTestUtils.assertPositiveInfinity(plusVol.getSize());
    1785         Assert.assertNull(plusVol.getCentroid());
    1786
    1787         final ConvexVolume centerVol = tree.findNode(Vector3D.of(0.5, 0.5, 0.5)).getNodeRegion();
    1788         Assert.assertEquals(1, centerVol.getSize(), TEST_EPS);
    1789         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0.5, 0.5, 0.5), centerVol.getCentroid(), TEST_EPS);
    1790     }
    1791
    1792     // GEOMETRY-59
    1793     @Test
    1794     public void testSlightlyConcavePrism() {
    1795         // arrange
    1796         final Vector3D[] vertices = {
    1797             Vector3D.of(0, 0, 0),
    1798             Vector3D.of(2, 1e-7, 0),
    1799             Vector3D.of(4, 0, 0),
    1800             Vector3D.of(2, 2, 0),
    1801             Vector3D.of(0, 0, 2),
    1802             Vector3D.of(2, 1e-7, 2),
    1803             Vector3D.of(4, 0, 2),
    1804             Vector3D.of(2, 2, 2)
    1805         };
    1806
    1807         final int[][] facets = {
    1808             {4, 5, 6, 7},
    1809             {3, 2, 1, 0},
    1810             {0, 1, 5, 4},
    1811             {1, 2, 6, 5},
    1812             {2, 3, 7, 6},
    1813             {3, 0, 4, 7}
    1814         };
    1815
    1816         final List<PlaneConvexSubset> faces = indexedFacetsToBoundaries(vertices, facets);
    1817
    1818         // act
    1819         final RegionBSPTree3D tree = RegionBSPTree3D.full();
    1820         tree.insert(faces);
    1821
    1822         // assert
    1823         Assert.assertFalse(tree.isFull());
    1824         Assert.assertFalse(tree.isEmpty());
    1825
    1826         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.INSIDE, Vector3D.of(2, 1, 1));
    1827         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.OUTSIDE,
    1828                 Vector3D.of(2, 1, 3), Vector3D.of(2, 1, -3),
    1829                 Vector3D.of(2, -1, 1), Vector3D.of(2, 3, 1),
    1830                 Vector3D.of(-1, 1, 1), Vector3D.of(4, 1, 1));
    1831     }
    1832
    1833     private static List<PlaneConvexSubset> indexedFacetsToBoundaries(final Vector3D[] vertices, final int[][] facets) {
    1834         final List<PlaneConvexSubset> boundaries = new ArrayList<>();
    1835
    1836         final List<Vector3D> vertexList = new ArrayList<>();
    1837
    1838         for (int i = 0; i < facets.length; ++i) {
    1839             final int[] indices = facets[i];
    1840
    1841             for (int j = 0; j < indices.length; ++j) {
    1842                 vertexList.add(vertices[indices[j]]);
    1843             }
    1844
    1845             // insert into an embedded tree and convert to convex polygons so that we can support
    1846             // non-convex facet boundaries
    1847             final EmbeddingPlane plane = Planes.fromPoints(vertexList, TEST_PRECISION).getEmbedding();
    1848
    1849             final LinePath subPath = LinePath.builder(TEST_PRECISION)
    1850                     .appendVertices(plane.toSubspace(vertexList))
    1851                     .close();
    1852             final EmbeddedTreePlaneSubset subset = new EmbeddedTreePlaneSubset(plane, subPath.toTree());
    1853
    1854             boundaries.addAll(subset.toConvex());
    1855
    1856             vertexList.clear();
    1857         }
    1858
    1859         return boundaries;
    1860     }
    1861
    1862     private static RegionBSPTree3D createRect(final Vector3D a, final Vector3D b) {
    1863         return createRect(a, b, TEST_PRECISION);
    1864     }
    1865
    1866     private static RegionBSPTree3D createRect(final Vector3D a, final Vector3D b, final DoublePrecisionContext precision) {
    1867         return Parallelepiped.axisAligned(a, b, precision).toTree();
    1868     }
    1869
    1870     private static RegionBSPTree3D createSphere(final Vector3D center, final double radius, final int stacks, final int slices) {
    1871
    1872         final List<Plane> planes = new ArrayList<>();
    1873
    1874         // add top and bottom planes (+/- z)
    1875         final Vector3D topZ = Vector3D.of(center.getX(), center.getY(), center.getZ() + radius);
    1876         final Vector3D bottomZ = Vector3D.of(center.getX(), center.getY(), center.getZ() - radius);
    1877
    1878         planes.add(Planes.fromPointAndNormal(topZ, Vector3D.Unit.PLUS_Z, TEST_PRECISION));
    1879         planes.add(Planes.fromPointAndNormal(bottomZ, Vector3D.Unit.MINUS_Z, TEST_PRECISION));
    1880
    1881         // add the side planes
    1882         final double vDelta = PlaneAngleRadians.PI / stacks;
    1883         final double hDelta = PlaneAngleRadians.PI * 2 / slices;
    1884
    1885         final double adjustedRadius = (radius + (radius * Math.cos(vDelta * 0.5))) / 2.0;
    1886
    1887         double vAngle;
    1888         double hAngle;
    1889         double stackRadius;
    1890         double stackHeight;
    1891         double x;
    1892         double y;
    1893         Vector3D pt;
    1894         Vector3D norm;
    1895
    1896         vAngle = -0.5 * vDelta;
    1897         for (int v = 0; v < stacks; ++v) {
    1898             vAngle += vDelta;
    1899
    1900             stackRadius = Math.sin(vAngle) * adjustedRadius;
    1901             stackHeight = Math.cos(vAngle) * adjustedRadius;
    1902
    1903             hAngle = -0.5 * hDelta;
    1904             for (int h = 0; h < slices; ++h) {
    1905                 hAngle += hDelta;
    1906
    1907                 x = Math.cos(hAngle) * stackRadius;
    1908                 y = Math.sin(hAngle) * stackRadius;
    1909
    1910                 norm = Vector3D.of(x, y, stackHeight).normalize();
    1911                 pt = center.add(norm.multiply(adjustedRadius));
    1912
    1913                 planes.add(Planes.fromPointAndNormal(pt, norm, TEST_PRECISION));
    1914             }
    1915         }
    1916
    1917         final RegionBSPTree3D tree = RegionBSPTree3D.full();
    1918         RegionNode3D node = tree.getRoot();
    1919
    1920         for (final Plane plane : planes) {
    1921             node = node.cut(plane).getMinus();
    1922         }
    1923
    1924         return tree;
    1925     }
    1926
    1927     private static double cubeVolume(final double size) {
    1928         return size * size * size;
    1929     }
    1930
    1931     private static double cubeSurface(final double size) {
    1932         return 6.0 * size * size;
    1933     }
    1934
    1935     private static double sphereVolume(final double radius) {
    1936         return 4.0 * Math.PI * radius * radius * radius / 3.0;
    1937     }
    1938
    1939     private static double sphereSurface(final double radius) {
    1940         return 4.0 * Math.PI * radius * radius;
    1941     }
    1942
    1943     private static double circleSurface(final double radius) {
    1944         return Math.PI * radius * radius;
    1945     }
    1946 }