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 }