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