/*
    * Licensed to the Apache Software Foundation (ASF) under one or more
    * contributor license agreements.  See the NOTICE file distributed with
    * this work for additional information regarding copyright ownership.
    * The ASF licenses this file to You under the Apache License, Version 2.0
    * (the "License"); you may not use this file except in compliance with
    * the License.  You may obtain a copy of the License at
    *
    *      http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  package org.apache.commons.geometry.euclidean.threed;
  
  import java.util.ArrayList;
  import java.util.List;
  import java.util.stream.Stream;
  import java.util.stream.StreamSupport;
  
  import org.apache.commons.geometry.core.partitioning.Hyperplane;
  import org.apache.commons.geometry.core.partitioning.HyperplaneConvexSubset;
  import org.apache.commons.geometry.core.partitioning.HyperplaneSubset;
  import org.apache.commons.geometry.core.partitioning.Split;
  import org.apache.commons.geometry.core.partitioning.bsp.AbstractBSPTree;
  import org.apache.commons.geometry.core.partitioning.bsp.AbstractPartitionedRegionBuilder;
  import org.apache.commons.geometry.core.partitioning.bsp.AbstractRegionBSPTree;
  import org.apache.commons.geometry.core.partitioning.bsp.BSPTreeVisitor;
  import org.apache.commons.geometry.core.partitioning.bsp.RegionCutBoundary;
  import org.apache.commons.geometry.euclidean.threed.line.Line3D;
  import org.apache.commons.geometry.euclidean.threed.line.LineConvexSubset3D;
  import org.apache.commons.geometry.euclidean.threed.line.LinecastPoint3D;
  import org.apache.commons.numbers.core.Precision;
  
  /** Binary space partitioning (BSP) tree representing a region in three dimensional
   * Euclidean space.
   */
  public final class RegionBSPTree3D extends AbstractRegionBSPTree<Vector3D, RegionBSPTree3D.RegionNode3D>
      implements BoundarySource3D {
  
      /** Create a new, empty region. */
      public RegionBSPTree3D() {
          this(false);
      }
  
      /** Create a new region. If {@code full} is true, then the region will
       * represent the entire 3D space. Otherwise, it will be empty.
       * @param full whether or not the region should contain the entire
       *      3D space or be empty
       */
      public RegionBSPTree3D(final boolean full) {
          super(full);
      }
  
      /** Return a deep copy of this instance.
       * @return a deep copy of this instance.
       * @see #copy(org.apache.commons.geometry.core.partitioning.bsp.BSPTree)
       */
      public RegionBSPTree3D copy() {
          final RegionBSPTree3D result = RegionBSPTree3D.empty();
          result.copy(this);
  
          return result;
      }
  
      /** {@inheritDoc} */
      @Override
      public Iterable<PlaneConvexSubset> boundaries() {
          return createBoundaryIterable(PlaneConvexSubset.class::cast);
      }
  
      /** {@inheritDoc} */
      @Override
      public Stream<PlaneConvexSubset> boundaryStream() {
          return StreamSupport.stream(boundaries().spliterator(), false);
      }
  
      /** {@inheritDoc} */
      @Override
      public List<PlaneConvexSubset> getBoundaries() {
          return createBoundaryList(PlaneConvexSubset.class::cast);
      }
  
      /** Return a list of {@link ConvexVolume}s representing the same region
       * as this instance. One convex volume is returned for each interior leaf
       * node in the tree.
       * @return a list of convex volumes representing the same region as this
       *      instance
       */
      public List<ConvexVolume> toConvex() {
          final List<ConvexVolume> result = new ArrayList<>();
  
          toConvexRecursive(getRoot(), ConvexVolume.full(), result);
  
          return result;
      }
 
     /** Recursive method to compute the convex volumes of all inside leaf nodes in the subtree rooted at the given
      * node. The computed convex volumes are added to the given list.
      * @param node root of the subtree to compute the convex volumes for
      * @param nodeVolume the convex volume for the current node; this will be split by the node's cut hyperplane to
      *      form the convex volumes for any child nodes
      * @param result list containing the results of the computation
      */
     private void toConvexRecursive(final RegionNode3D node, final ConvexVolume nodeVolume,
             final List<? super ConvexVolume> result) {
 
         if (node.isLeaf()) {
             // base case; only add to the result list if the node is inside
             if (node.isInside()) {
                 result.add(nodeVolume);
             }
         } else {
             // recurse
             final Split<ConvexVolume> split = nodeVolume.split(node.getCutHyperplane());
 
             toConvexRecursive(node.getMinus(), split.getMinus(), result);
             toConvexRecursive(node.getPlus(), split.getPlus(), result);
         }
     }
 
     /** {@inheritDoc} */
     @Override
     public Split<RegionBSPTree3D> split(final Hyperplane<Vector3D> splitter) {
         return split(splitter, RegionBSPTree3D.empty(), RegionBSPTree3D.empty());
     }
 
     /** {@inheritDoc} */
     @Override
     public Vector3D project(final Vector3D pt) {
         // use our custom projector so that we can disambiguate points that are
         // actually equidistant from the target point
         final BoundaryProjector3D projector = new BoundaryProjector3D(pt);
         accept(projector);
 
         return projector.getProjected();
     }
 
     /** Return the current instance.
      */
     @Override
     public RegionBSPTree3D toTree() {
         return this;
     }
 
     /** {@inheritDoc} */
     @Override
     public List<LinecastPoint3D> linecast(final LineConvexSubset3D subset) {
         final LinecastVisitor visitor = new LinecastVisitor(subset, false);
         accept(visitor);
 
         return visitor.getResults();
     }
 
     /** {@inheritDoc} */
     @Override
     public LinecastPoint3D linecastFirst(final LineConvexSubset3D subset) {
         final LinecastVisitor visitor = new LinecastVisitor(subset, true);
         accept(visitor);
 
         return visitor.getFirstResult();
     }
 
     /** {@inheritDoc} */
     @Override
     protected RegionSizeProperties<Vector3D> computeRegionSizeProperties() {
         // handle simple cases
         if (isFull()) {
             return new RegionSizeProperties<>(Double.POSITIVE_INFINITY, null);
         } else if (isEmpty()) {
             return new RegionSizeProperties<>(0, null);
         }
 
         final RegionSizePropertiesVisitor visitor = new RegionSizePropertiesVisitor();
         accept(visitor);
 
         return visitor.getRegionSizeProperties();
     }
 
     /** {@inheritDoc} */
     @Override
     protected RegionNode3D createNode() {
         return new RegionNode3D(this);
     }
 
     /** Return a new instance containing all of 3D space.
      * @return a new instance containing all of 3D space.
      */
     public static RegionBSPTree3D full() {
         return new RegionBSPTree3D(true);
     }
 
     /** Return a new, empty instance. The represented region is completely empty.
      * @return a new, empty instance.
      */
     public static RegionBSPTree3D empty() {
         return new RegionBSPTree3D(false);
     }
 
     /** Construct a new tree from the given boundaries. If no boundaries
      * are present, the returned tree is empty.
      * @param boundaries boundaries to construct the tree from
      * @return a new tree instance constructed from the given boundaries
      * @see #from(Iterable, boolean)
      */
     public static RegionBSPTree3D from(final Iterable<? extends PlaneConvexSubset> boundaries) {
         return from(boundaries, false);
     }
 
     /** Construct a new tree from the given boundaries. If {@code full} is true, then
      * the initial tree before boundary insertion contains the entire space. Otherwise,
      * it is empty.
      * @param boundaries boundaries to construct the tree from
      * @param full if true, the initial tree will contain the entire space
      * @return a new tree instance constructed from the given boundaries
      */
     public static RegionBSPTree3D from(final Iterable<? extends PlaneConvexSubset> boundaries, final boolean full) {
         final RegionBSPTree3D tree = new RegionBSPTree3D(full);
         tree.insert(boundaries);
 
         return tree;
     }
 
     /** Create a new {@link PartitionedRegionBuilder3D} instance which can be used to build balanced
      * BSP trees from region boundaries.
      * @return a new {@link PartitionedRegionBuilder3D} instance
      */
     public static PartitionedRegionBuilder3D partitionedRegionBuilder() {
         return new PartitionedRegionBuilder3D();
     }
 
     /** BSP tree node for three dimensional Euclidean space.
      */
     public static final class RegionNode3D extends AbstractRegionBSPTree.AbstractRegionNode<Vector3D, RegionNode3D> {
         /** Simple constructor.
          * @param tree the owning tree instance
          */
         RegionNode3D(final AbstractBSPTree<Vector3D, RegionNode3D> tree) {
             super(tree);
         }
 
         /** Get the region represented by this node. The returned region contains
          * the entire area contained in this node, regardless of the attributes of
          * any child nodes.
          * @return the region represented by this node
          */
         public ConvexVolume getNodeRegion() {
             ConvexVolume volume = ConvexVolume.full();
 
             RegionNode3D child = this;
             RegionNode3D parent;
 
             while ((parent = child.getParent()) != null) {
                 final Split<ConvexVolume> split = volume.split(parent.getCutHyperplane());
 
                 volume = child.isMinus() ? split.getMinus() : split.getPlus();
 
                 child = parent;
             }
 
             return volume;
         }
 
         /** {@inheritDoc} */
         @Override
         protected RegionNode3D getSelf() {
             return this;
         }
     }
 
     /** Class used to build regions in Euclidean 3D space by inserting boundaries into a BSP
      * tree containing "partitions", i.e. structural cuts where both sides of the cut have the same region location.
      * When partitions are chosen that effectively divide the region boundaries at each partition level, the
      * constructed tree is shallower and more balanced than one constructed from the region boundaries alone,
      * resulting in improved performance. For example, consider a mesh approximation of a sphere. The region is
      * convex so each boundary has all of the other boundaries on its minus side; the plus sides are all empty.
      * When these boundaries are inserted directly into a tree, the tree degenerates into a simple linked list of
      * nodes with a height directly proportional to the number of boundaries. This means that many operations on the
      * tree, such as inside/outside testing of points, involve iterating through each and every region boundary. In
      * contrast, if a partition is first inserted that passes through the sphere center, the first BSP tree node
      * contains region nodes on its plus <em>and</em> minus sides, cutting the height of the tree in half. Operations
      * such as inside/outside testing are then able to skip half of the tree nodes with a single test on the
      * root node, resulting in drastically improved performance. Insertion of additional partitions (using a grid
      * layout, for example) can produce even shallower trees, although there is a point unique to each boundary set at
      * which the addition of more partitions begins to decrease instead of increase performance.
      *
      * <h2>Usage</h2>
      * <p>Usage of this class consists of two phases: (1) <em>partition insertion</em> and (2) <em>boundary
      * insertion</em>. Instances begin in the <em>partition insertion</em> phase. Here, partitions can be inserted
      * into the empty tree using {@link PartitionedRegionBuilder3D#insertPartition(PlaneConvexSubset) insertPartition}
      * or similar methods. The {@link org.apache.commons.geometry.core.partitioning.bsp.RegionCutRule#INHERIT INHERIT}
      * cut rule is used internally to insert the cut so the represented region remains empty even as partitions are
      * inserted.
      * </p>
      *
      * <p>The instance moves into the <em>boundary insertion</em> phase when the caller inserts the first region
      * boundary, using {@link PartitionedRegionBuilder3D#insertBoundary(PlaneConvexSubset) insertBoundary} or
      * similar methods. Attempting to insert a partition after this point results in an {@code IllegalStateException}.
      * This ensures that partitioning cuts are always located higher up the tree than boundary cuts.</p>
      *
      * <p>After all boundaries are inserted, the {@link PartitionedRegionBuilder3D#build() build} method is used
      * to perform final processing and return the computed tree.</p>
      */
     public static final class PartitionedRegionBuilder3D
         extends AbstractPartitionedRegionBuilder<Vector3D, RegionNode3D> {
 
         /** Construct a new builder instance.
          */
         private PartitionedRegionBuilder3D() {
             super(RegionBSPTree3D.empty());
         }
 
         /** Insert a partition plane.
          * @param partition partition to insert
          * @return this instance
          * @throws IllegalStateException if a boundary has previously been inserted
          */
         public PartitionedRegionBuilder3D insertPartition(final Plane partition) {
             return insertPartition(partition.span());
         }
 
         /** Insert a plane convex subset as a partition.
          * @param partition partition to insert
          * @return this instance
          * @throws IllegalStateException if a boundary has previously been inserted
          */
         public PartitionedRegionBuilder3D insertPartition(final PlaneConvexSubset partition) {
             insertPartitionInternal(partition);
 
             return this;
         }
 
         /** Insert a set of three axis aligned planes intersecting at the given point as partitions.
          * The planes all contain the {@code center} point and have the normals {@code +x}, {@code +y},
          * and {@code +z} in that order. If inserted into an empty tree, this will partition the space
          * into 8 sections.
          * @param center center point for the partitions; all 3 inserted planes intersect at this point
          * @param precision precision context used to construct the planes
          * @return this instance
          * @throws IllegalStateException if a boundary has previously been inserted
          */
         public PartitionedRegionBuilder3D insertAxisAlignedPartitions(final Vector3D center,
                 final Precision.DoubleEquivalence precision) {
 
             insertPartition(Planes.fromPointAndNormal(center, Vector3D.Unit.PLUS_X, precision));
             insertPartition(Planes.fromPointAndNormal(center, Vector3D.Unit.PLUS_Y, precision));
             insertPartition(Planes.fromPointAndNormal(center, Vector3D.Unit.PLUS_Z, precision));
 
             return this;
         }
 
         /** Insert a 3D grid of partitions. The partitions are constructed recursively: at each level a set of
          * three axis-aligned partitioning planes are inserted using
          * {@link #insertAxisAlignedPartitions(Vector3D, Precision.DoubleEquivalence) insertAxisAlignedPartitions}.
          * The algorithm then recurses using bounding boxes from the min point to the center and from the center
          * point to the max. Note that this means no partitions are ever inserted directly on the boundaries of
          * the given bounding box. This is intentional and done to allow this method to be called directly with the
          * bounding box from a set of boundaries to be inserted without unnecessarily adding partitions that will
          * never have region boundaries on both sides.
          * @param bounds bounding box for the grid
          * @param level recursion level for the grid; each level subdivides each grid cube into 8 sections, making the
          *      total number of grid cubes equal to {@code 8 ^ level}
          * @param precision precision context used to construct the partition planes
          * @return this instance
          * @throws IllegalStateException if a boundary has previously been inserted
          */
         public PartitionedRegionBuilder3D insertAxisAlignedGrid(final Bounds3D bounds, final int level,
                 final Precision.DoubleEquivalence precision) {
 
             insertAxisAlignedGridRecursive(bounds.getMin(), bounds.getMax(), level, precision);
 
             return this;
         }
 
         /** Recursively insert axis-aligned grid partitions.
          * @param min min point for the grid cube to partition
          * @param max max point for the grid cube to partition
          * @param level current recursion level
          * @param precision precision context used to construct the partition planes
          */
         private void insertAxisAlignedGridRecursive(final Vector3D min, final Vector3D max, final int level,
                 final Precision.DoubleEquivalence precision) {
             if (level > 0) {
                 final Vector3D center = min.lerp(max, 0.5);
 
                 insertAxisAlignedPartitions(center, precision);
 
                 final int nextLevel = level - 1;
                 insertAxisAlignedGridRecursive(min, center, nextLevel, precision);
                 insertAxisAlignedGridRecursive(center, max, nextLevel, precision);
             }
         }
 
         /** Insert a region boundary.
          * @param boundary region boundary to insert
          * @return this instance
          */
         public PartitionedRegionBuilder3D insertBoundary(final PlaneConvexSubset boundary) {
             insertBoundaryInternal(boundary);
 
             return this;
         }
 
         /** Insert a collection of region boundaries.
          * @param boundaries boundaries to insert
          * @return this instance
          */
         public PartitionedRegionBuilder3D insertBoundaries(final Iterable<? extends PlaneConvexSubset> boundaries) {
             for (final PlaneConvexSubset boundary : boundaries) {
                 insertBoundaryInternal(boundary);
             }
 
             return this;
         }
 
         /** Insert all boundaries from the given source.
          * @param boundarySrc source of boundaries to insert
          * @return this instance
          */
         public PartitionedRegionBuilder3D insertBoundaries(final BoundarySource3D boundarySrc) {
             try (Stream<PlaneConvexSubset> stream = boundarySrc.boundaryStream()) {
                 stream.forEach(this::insertBoundaryInternal);
             }
 
             return this;
         }
 
         /** Build and return the region BSP tree.
          * @return the region BSP tree
          */
         public RegionBSPTree3D build() {
             return (RegionBSPTree3D) buildInternal();
         }
     }
 
     /** Class used to project points onto the 3D region boundary.
      */
     private static final class BoundaryProjector3D extends BoundaryProjector<Vector3D, RegionNode3D> {
         /** Simple constructor.
          * @param point the point to project onto the region's boundary
          */
         private BoundaryProjector3D(final Vector3D point) {
             super(point);
         }
 
         /** {@inheritDoc} */
         @Override
         protected Vector3D disambiguateClosestPoint(final Vector3D target, final Vector3D a, final Vector3D b) {
             // return the point with the smallest coordinate values
             final int cmp = Vector3D.COORDINATE_ASCENDING_ORDER.compare(a, b);
             return cmp < 0 ? a : b;
         }
     }
 
     /** Visitor for computing geometric properties for 3D BSP tree instances.
      *  The volume of the region is computed using the equation
      *  <code>V = (1/3)*&Sigma;<sub>F</sub>[(C<sub>F</sub>&sdot;N<sub>F</sub>)*area(F)]</code>,
      *  where <code>F</code> represents each face in the region, <code>C<sub>F</sub></code>
      *  represents the centroid of the face, and <code>N<sub>F</sub></code> represents the
      *  normal of the face. (More details can be found in the article
      *  <a href="https://en.wikipedia.org/wiki/Polyhedron#Volume">here</a>.)
      *  This essentially splits up the region into pyramids with a 2D face forming
      *  the base of each pyramid. The centroid is computed in a similar way. The centroid
      *  of each pyramid is calculated using the fact that it is located 3/4 of the way along the
      *  line from the apex to the base. The region centroid then becomes the volume-weighted
      *  average of these pyramid centers.
      *  @see <a href="https://en.wikipedia.org/wiki/Polyhedron#Volume">Polyhedron#Volume</a>
      */
     private static final class RegionSizePropertiesVisitor implements BSPTreeVisitor<Vector3D, RegionNode3D> {
 
         /** Accumulator for boundary volume contributions. */
         private double volumeSum;
 
         /** Centroid contribution x coordinate accumulator. */
         private double sumX;
 
         /** Centroid contribution y coordinate accumulator. */
         private double sumY;
 
         /** Centroid contribution z coordinate accumulator. */
         private double sumZ;
 
         /** {@inheritDoc} */
         @Override
         public Result visit(final RegionNode3D node) {
             if (node.isInternal()) {
                 final RegionCutBoundary<Vector3D> boundary = node.getCutBoundary();
 
                 for (final HyperplaneConvexSubset<Vector3D> outsideFacing : boundary.getOutsideFacing()) {
                     addBoundaryContribution(outsideFacing, false);
                 }
 
                 for (final HyperplaneConvexSubset<Vector3D> insideFacing : boundary.getInsideFacing()) {
                     addBoundaryContribution(insideFacing, true);
                 }
             }
 
             return Result.CONTINUE;
         }
 
         /** Return the computed size properties for the visited region.
          * @return the computed size properties for the visited region.
          */
         public RegionSizeProperties<Vector3D> getRegionSizeProperties() {
             double size = Double.POSITIVE_INFINITY;
             Vector3D centroid = null;
 
             // we only have a finite size if the volume sum is finite and positive
             // (negative indicates a finite outside surrounded by an infinite inside)
             if (Double.isFinite(volumeSum) && volumeSum > 0.0) {
                 // apply the 1/3 pyramid volume scaling factor
                 size = volumeSum / 3.0;
 
                 // Since the volume we used when adding together the boundary contributions
                 // was 3x the actual pyramid size, we'll multiply by 1/4 here instead
                 // of 3/4 to adjust for the actual centroid position in each pyramid.
                 final double centroidScale = 1.0 / (4 * size);
                 centroid =  Vector3D.of(
                         sumX * centroidScale,
                         sumY * centroidScale,
                         sumZ * centroidScale);
             }
 
             return new RegionSizeProperties<>(size, centroid);
         }
 
         /** Add the contribution of the given node cut boundary. If {@code reverse} is true,
          * the volume of the contribution is reversed before being added to the total.
          * @param boundary node cut boundary
          * @param reverse if true, the boundary contribution is reversed before being added to the total.
          */
         private void addBoundaryContribution(final HyperplaneSubset<Vector3D> boundary, final boolean reverse) {
             final PlaneSubset boundarySubset = (PlaneSubset) boundary;
 
             final Plane boundaryPlane = boundarySubset.getPlane();
             final double boundaryArea = boundarySubset.getSize();
             final Vector3D boundaryCentroid = boundarySubset.getCentroid();
 
             if (Double.isInfinite(boundaryArea)) {
                 volumeSum = Double.POSITIVE_INFINITY;
             } else if (boundaryCentroid != null) {
                 // the volume here is actually 3x the actual pyramid volume; we'll apply
                 // the final scaling all at once at the end
                 double scaledVolume = boundaryArea * boundaryCentroid.dot(boundaryPlane.getNormal());
                 if (reverse) {
                     scaledVolume = -scaledVolume;
                 }
 
                 volumeSum += scaledVolume;
 
                 sumX += scaledVolume * boundaryCentroid.getX();
                 sumY += scaledVolume * boundaryCentroid.getY();
                 sumZ += scaledVolume * boundaryCentroid.getZ();
             }
         }
     }
 
     /** BSP tree visitor that performs a linecast operation against the boundaries of the visited tree.
      */
     private static final class LinecastVisitor implements BSPTreeVisitor<Vector3D, RegionNode3D> {
 
         /** The line subset to intersect with the boundaries of the BSP tree. */
         private final LineConvexSubset3D linecastSubset;
 
         /** If true, the visitor will stop visiting the tree once the first linecast
          * point is determined.
          */
         private final boolean firstOnly;
 
         /** The minimum abscissa found during the search. */
         private double minAbscissa = Double.POSITIVE_INFINITY;
 
         /** List of results from the linecast operation. */
         private final List<LinecastPoint3D> results = new ArrayList<>();
 
         /** Create a new instance with the given intersecting line convex subset.
          * @param linecastSubset line subset to intersect with the BSP tree region boundary
          * @param firstOnly if true, the visitor will stop visiting the tree once the first
          *      linecast point is determined
          */
         LinecastVisitor(final LineConvexSubset3D linecastSubset, final boolean firstOnly) {
             this.linecastSubset = linecastSubset;
             this.firstOnly = firstOnly;
         }
 
         /** Get the first {@link org.apache.commons.geometry.euclidean.twod.LinecastPoint2D}
          * resulting from the linecast operation.
          * @return the first linecast result point
          */
         public LinecastPoint3D getFirstResult() {
             final List<LinecastPoint3D> sortedResults = getResults();
 
             return sortedResults.isEmpty() ?
                     null :
                     sortedResults.get(0);
         }
 
         /** Get a list containing the results of the linecast operation. The list is
          * sorted and filtered.
          * @return list of sorted and filtered results from the linecast operation
          */
         public List<LinecastPoint3D> getResults() {
             LinecastPoint3D.sortAndFilter(results);
 
             return results;
         }
 
         /** {@inheritDoc} */
         @Override
         public Order visitOrder(final RegionNode3D internalNode) {
             final Plane cut = (Plane) internalNode.getCutHyperplane();
             final Line3D line = linecastSubset.getLine();
 
             final boolean plusIsNear = line.getDirection().dot(cut.getNormal()) < 0;
 
             return plusIsNear ?
                     Order.PLUS_NODE_MINUS :
                     Order.MINUS_NODE_PLUS;
         }
 
         /** {@inheritDoc} */
         @Override
         public Result visit(final RegionNode3D node) {
             if (node.isInternal()) {
                 // check if the line subset intersects the node cut hyperplane
                 final Line3D line = linecastSubset.getLine();
                 final Vector3D pt = ((Plane) node.getCutHyperplane()).intersection(line);
 
                 if (pt != null) {
                     if (firstOnly && !results.isEmpty() &&
                             line.getPrecision().compare(minAbscissa, line.abscissa(pt)) < 0) {
                         // we have results and we are now sure that no other intersection points will be
                         // found that are closer or at the same position on the intersecting line.
                         return Result.TERMINATE;
                     } else if (linecastSubset.contains(pt)) {
                         // we've potentially found a new linecast point; add it to the list of potential
                         // results
                         final LinecastPoint3D potentialResult = computeLinecastPoint(pt, node);
                         if (potentialResult != null) {
                             results.add(potentialResult);
 
                             // update the min abscissa
                             minAbscissa = Math.min(minAbscissa, potentialResult.getAbscissa());
                         }
                     }
                 }
             }
 
             return Result.CONTINUE;
         }
 
         /** Compute the linecast point for the given intersection point and tree node, returning null
          * if the point does not actually lie on the region boundary.
          * @param pt intersection point
          * @param node node containing the cut that the linecast line intersected with
          * @return a new linecast point instance or null if the intersection point does not lie
          *      on the region boundary
          */
         private LinecastPoint3D computeLinecastPoint(final Vector3D pt, final RegionNode3D node) {
             final Plane cut = (Plane) node.getCutHyperplane();
             final RegionCutBoundary<Vector3D> boundary = node.getCutBoundary();
 
             boolean onBoundary = false;
             boolean negateNormal = false;
 
             if (boundary.containsInsideFacing(pt)) {
                 // on inside-facing boundary
                 onBoundary = true;
                 negateNormal = true;
             } else  if (boundary.containsOutsideFacing(pt)) {
                 // on outside-facing boundary
                 onBoundary = true;
             }
 
             if (onBoundary) {
                 Vector3D normal = cut.getNormal();
                 if (negateNormal) {
                     normal = normal.negate();
                 }
 
                 return new LinecastPoint3D(pt, normal, linecastSubset.getLine());
             }
 
             return null;
         }
     }
 }