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.mesh;
    18
    19  import java.util.ArrayList;
    20  import java.util.Arrays;
    21  import java.util.Collection;
    22  import java.util.Collections;
    23  import java.util.Comparator;
    24  import java.util.Iterator;
    25  import java.util.List;
    26  import java.util.Map;
    27  import java.util.NoSuchElementException;
    28  import java.util.Objects;
    29  import java.util.TreeMap;
    30  import java.util.function.Function;
    31  import java.util.stream.Stream;
    32  import java.util.stream.StreamSupport;
    33
    34  import org.apache.commons.geometry.core.Transform;
    35  import org.apache.commons.geometry.euclidean.internal.EuclideanUtils;
    36  import org.apache.commons.geometry.euclidean.threed.BoundarySource3D;
    37  import org.apache.commons.geometry.euclidean.threed.Bounds3D;
    38  import org.apache.commons.geometry.euclidean.threed.PlaneConvexSubset;
    39  import org.apache.commons.geometry.euclidean.threed.Planes;
    40  import org.apache.commons.geometry.euclidean.threed.Triangle3D;
    41  import org.apache.commons.geometry.euclidean.threed.Vector3D;
    42  import org.apache.commons.numbers.core.Precision;
    43
    44  /** A simple implementation of the {@link TriangleMesh} interface. This class ensures that
    45   * faces always contain 3 valid references into the vertex list but does not enforce that
    46   * the referenced vertices are unique or that they define a triangle with non-zero size. For
    47   * example, a mesh could contain a face with 3 vertices that are considered equivalent by the
    48   * configured precision context. Attempting to call the {@link TriangleMesh.Face#getPolygon()}
    49   * method on such a face results in an exception. The
    50   * {@link TriangleMesh.Face#definesPolygon()} method can be used to determine if a face defines
    51   * a valid triangle.
    52   *
    53   * <p>Instances of this class are guaranteed to be immutable.</p>
    54   */
    55  public final class SimpleTriangleMesh implements TriangleMesh {
    56
    57      /** Vertices in the mesh. */
    58      private final List<Vector3D> vertices;
    59
    60      /** Faces in the mesh. */
    61      private final List<int[]> faces;
    62
    63      /** The bounds of the mesh. */
    64      private final Bounds3D bounds;
    65
    66      /** Object used for floating point comparisons. */
    67      private final Precision.DoubleEquivalence precision;
    68
    69      /** Construct a new instance from a vertex list and set of faces. No validation is
    70       * performed on the input.
    71       * @param vertices vertex list
    72       * @param faces face indices list
    73       * @param bounds mesh bounds
    74       * @param precision precision context used when creating face polygons
    75       */
    76      private SimpleTriangleMesh(final List<Vector3D> vertices, final List<int[]> faces, final Bounds3D bounds,
    77              final Precision.DoubleEquivalence precision) {
    78          this.vertices = Collections.unmodifiableList(vertices);
    79          this.faces = Collections.unmodifiableList(faces);
    80          this.bounds = bounds;
    81          this.precision = precision;
    82      }
    83
    84      /** {@inheritDoc} */
    85      @Override
    86      public Iterable<Vector3D> vertices() {
    87          return getVertices();
    88      }
    89
    90      /** {@inheritDoc} */
    91      @Override
    92      public List<Vector3D> getVertices() {
    93          return vertices;
    94      }
    95
    96      /** {@inheritDoc} */
    97      @Override
    98      public int getVertexCount() {
    99          return vertices.size();
    100     }
    101
    102     /** {@inheritDoc} */
    103     @Override
    104     public Iterable<TriangleMesh.Face> faces() {
    105         return () -> new FaceIterator<>(Function.identity());
    106     }
    107
    108     /** {@inheritDoc} */
    109     @Override
    110     public List<TriangleMesh.Face> getFaces() {
    111         final int count = getFaceCount();
    112
    113         final List<Face> faceList = new ArrayList<>(count);
    114         for (int i = 0; i < count; ++i) {
    115             faceList.add(getFace(i));
    116         }
    117
    118         return faceList;
    119     }
    120
    121     /** {@inheritDoc} */
    122     @Override
    123     public int getFaceCount() {
    124         return faces.size();
    125     }
    126
    127     /** {@inheritDoc} */
    128     @Override
    129     public TriangleMesh.Face getFace(final int index) {
    130         return new SimpleTriangleFace(index, faces.get(index));
    131     }
    132
    133     /** {@inheritDoc} */
    134     @Override
    135     public Bounds3D getBounds() {
    136         return bounds;
    137     }
    138
    139     /** Get the precision context for the mesh. This context is used during construction of
    140      * face {@link Triangle3D} instances.
    141      * @return the precision context for the mesh
    142      */
    143     public Precision.DoubleEquivalence getPrecision() {
    144         return precision;
    145     }
    146
    147     /** {@inheritDoc} */
    148     @Override
    149     public Stream<PlaneConvexSubset> boundaryStream() {
    150         return createFaceStream(Face::getPolygon);
    151     }
    152
    153     /** {@inheritDoc} */
    154     @Override
    155     public Stream<Triangle3D> triangleStream() {
    156         return createFaceStream(Face::getPolygon);
    157     }
    158
    159     /** {@inheritDoc} */
    160     @Override
    161     public SimpleTriangleMesh transform(final Transform<Vector3D> transform) {
    162         // only the vertices and bounds are modified; the faces are the same
    163         final Bounds3D.Builder boundsBuilder = Bounds3D.builder();
    164         final List<Vector3D> tVertices = new ArrayList<>(vertices.size());
    165
    166         Vector3D tVertex;
    167         for (final Vector3D vertex : vertices) {
    168             tVertex = transform.apply(vertex);
    169
    170             boundsBuilder.add(tVertex);
    171             tVertices.add(tVertex);
    172         }
    173
    174         final Bounds3D tBounds = boundsBuilder.hasBounds() ?
    175                 boundsBuilder.build() :
    176                 null;
    177
    178         return new SimpleTriangleMesh(tVertices, faces, tBounds, precision);
    179     }
    180
    181     /** Return this instance if the given precision context is equal to the current precision context.
    182      * Otherwise, create a new mesh with the given precision context but the same vertices, faces, and
    183      * bounds.
    184      * @param meshPrecision precision context to use when generating face polygons
    185      * @return a mesh instance with the given precision context and the same mesh structure as the current
    186      *      instance
    187      */
    188     @Override
    189     public SimpleTriangleMesh toTriangleMesh(final Precision.DoubleEquivalence meshPrecision) {
    190         if (this.precision.equals(meshPrecision)) {
    191             return this;
    192         }
    193
    194         return new SimpleTriangleMesh(vertices, faces, bounds, meshPrecision);
    195     }
    196
    197     /** {@inheritDoc} */
    198     @Override
    199     public String toString() {
    200         final StringBuilder sb = new StringBuilder();
    201         sb.append(getClass().getSimpleName())
    202             .append("[vertexCount= ")
    203             .append(getVertexCount())
    204             .append(", faceCount= ")
    205             .append(getFaceCount())
    206             .append(", bounds= ")
    207             .append(getBounds())
    208             .append(']');
    209
    210         return sb.toString();
    211     }
    212
    213     /** Create a stream containing the results of applying {@code fn} to each face in
    214      * the mesh.
    215      * @param <T> Stream element type
    216      * @param fn function used to extract the stream values from each face
    217      * @return a stream containing the results of applying {@code fn} to each face in
    218      *      the mesh
    219      */
    220     private <T> Stream<T> createFaceStream(final Function<TriangleMesh.Face, T> fn) {
    221         final Iterable<T> iterable = () -> new FaceIterator<>(fn);
    222         return StreamSupport.stream(iterable.spliterator(), false);
    223     }
    224
    225     /** Return a builder for creating new triangle mesh objects.
    226      * @param precision precision object used for floating point comparisons
    227      * @return a builder for creating new triangle mesh objects
    228      */
    229     public static Builder builder(final Precision.DoubleEquivalence precision) {
    230         return new Builder(precision);
    231     }
    232
    233     /** Construct a new triangle mesh from the given vertices and face indices.
    234      * @param vertices vertices for the mesh
    235      * @param faces face indices for the mesh
    236      * @param precision precision context used for floating point comparisons
    237      * @return a new triangle mesh instance
    238      * @throws IllegalArgumentException if any of the face index arrays does not have exactly 3 elements or
    239      *       if any index is not a valid index into the vertex list
    240      */
    241     public static SimpleTriangleMesh from(final Vector3D[] vertices, final int[][] faces,
    242                                           final Precision.DoubleEquivalence precision) {
    243         return from(Arrays.asList(vertices), Arrays.asList(faces), precision);
    244     }
    245
    246     /** Construct a new triangle mesh from the given vertices and face indices.
    247      * @param vertices vertices for the mesh
    248      * @param faces face indices for the mesh
    249      * @param precision precision context used for floating point comparisons
    250      * @return a new triangle mesh instance
    251      * @throws IllegalArgumentException if any of the face index arrays does not have exactly 3 elements or
    252      *       if any index is not a valid index into the vertex list
    253      */
    254     public static SimpleTriangleMesh from(final Collection<Vector3D> vertices, final Collection<int[]> faces,
    255                                           final Precision.DoubleEquivalence precision) {
    256         final Builder builder = builder(precision);
    257
    258         return builder.addVertices(vertices)
    259                 .addFaces(faces)
    260                 .build();
    261     }
    262
    263     /** Construct a new mesh instance containing all triangles from the given boundary
    264      * source. Equivalent vertices are reused wherever possible.
    265      * @param boundarySrc boundary source to construct a mesh from
    266      * @param precision precision context used for floating point comparisons
    267      * @return new mesh instance containing all triangles from the given boundary
    268      *      source
    269      * @throws IllegalStateException if any boundary in the boundary source has infinite size and cannot
    270      *      be converted to triangles
    271      */
    272     public static SimpleTriangleMesh from(final BoundarySource3D boundarySrc,
    273             final Precision.DoubleEquivalence precision) {
    274         final Builder builder = builder(precision);
    275         try (Stream<Triangle3D> stream = boundarySrc.triangleStream()) {
    276             stream.forEach(tri -> builder.addFaceUsingVertices(
    277                 tri.getPoint1(),
    278                 tri.getPoint2(),
    279                 tri.getPoint3()));
    280         }
    281
    282         return builder.build();
    283     }
    284
    285     /** Internal implementation of {@link TriangleMesh.Face}.
    286      */
    287     private final class SimpleTriangleFace implements TriangleMesh.Face {
    288
    289         /** The index of the face in the mesh. */
    290         private final int index;
    291
    292         /** Vertex indices for the face. */
    293         private final int[] vertexIndices;
    294
    295         SimpleTriangleFace(final int index, final int[] vertexIndices) {
    296             this.index = index;
    297             this.vertexIndices = vertexIndices;
    298         }
    299
    300         /** {@inheritDoc} */
    301         @Override
    302         public int getIndex() {
    303             return index;
    304         }
    305
    306         /** {@inheritDoc} */
    307         @Override
    308         public int[] getVertexIndices() {
    309             return vertexIndices.clone();
    310         }
    311
    312         /** {@inheritDoc} */
    313         @Override
    314         public List<Vector3D> getVertices() {
    315             return Arrays.asList(
    316                     getPoint1(),
    317                     getPoint2(),
    318                     getPoint3());
    319         }
    320
    321         /** {@inheritDoc} */
    322         @Override
    323         public Vector3D getPoint1() {
    324             return vertices.get(vertexIndices[0]);
    325         }
    326
    327         /** {@inheritDoc} */
    328         @Override
    329         public Vector3D getPoint2() {
    330             return vertices.get(vertexIndices[1]);
    331         }
    332
    333         /** {@inheritDoc} */
    334         @Override
    335         public Vector3D getPoint3() {
    336             return vertices.get(vertexIndices[2]);
    337         }
    338
    339         /** {@inheritDoc} */
    340         @Override
    341         public boolean definesPolygon() {
    342             final Vector3D p1 = getPoint1();
    343             final Vector3D v1 = p1.vectorTo(getPoint2());
    344             final Vector3D v2 = p1.vectorTo(getPoint3());
    345
    346             return !precision.eqZero(v1.cross(v2).norm());
    347         }
    348
    349         /** {@inheritDoc} */
    350         @Override
    351         public Triangle3D getPolygon() {
    352             return Planes.triangleFromVertices(
    353                     getPoint1(),
    354                     getPoint2(),
    355                     getPoint3(),
    356                     precision);
    357         }
    358
    359         /** {@inheritDoc} */
    360         @Override
    361         public String toString() {
    362             final StringBuilder sb = new StringBuilder();
    363             sb.append(getClass().getSimpleName())
    364                 .append("[index= ")
    365                 .append(getIndex())
    366                 .append(", vertexIndices= ")
    367                 .append(Arrays.toString(getVertexIndices()))
    368                 .append(", vertices= ")
    369                 .append(getVertices())
    370                 .append(']');
    371
    372             return sb.toString();
    373         }
    374     }
    375
    376     /** Internal class for iterating through the mesh faces and extracting a value from each.
    377      * @param <T> Type returned by the iterator
    378      */
    379     private final class FaceIterator<T> implements Iterator<T> {
    380
    381         /** The current index of the iterator. */
    382         private int index;
    383
    384         /** Function to apply to each face in the mesh. */
    385         private final Function<? super TriangleMesh.Face, T> fn;
    386
    387         /** Construct a new instance for iterating through the mesh faces and extracting
    388          * a value from each.
    389          * @param fn function to apply to each face in order to obtain the iterated value
    390          */
    391         FaceIterator(final Function<? super TriangleMesh.Face, T> fn) {
    392             this.fn = fn;
    393         }
    394
    395         /** {@inheritDoc} */
    396         @Override
    397         public boolean hasNext() {
    398             return index < faces.size();
    399         }
    400
    401         /** {@inheritDoc} */
    402         @Override
    403         public T next() {
    404             if (hasNext()) {
    405                 final Face face = getFace(index++);
    406                 return fn.apply(face);
    407             }
    408             throw new NoSuchElementException();
    409         }
    410     }
    411
    412     /** Builder class for creating mesh instances.
    413      */
    414     public static final class Builder {
    415
    416         /** List of vertices. */
    417         private final ArrayList<Vector3D> vertices = new ArrayList<>();
    418
    419         /** Map of vertices to their first occurrence in the vertex list. */
    420         private Map<Vector3D, Integer> vertexIndexMap;
    421
    422         /** List of face vertex indices. */
    423         private final ArrayList<int[]> faces = new ArrayList<>();
    424
    425         /** Object used to construct the 3D bounds of the vertex list. */
    426         private final Bounds3D.Builder boundsBuilder = Bounds3D.builder();
    427
    428         /** Precision context used for floating point comparisons; this value may be null
    429          * if vertices are not to be combined in this builder.
    430          */
    431         private final Precision.DoubleEquivalence precision;
    432
    433         /** Flag set to true once a mesh is constructed from this builder. */
    434         private boolean built;
    435
    436         /** Construct a new builder.
    437          * @param precision precision context used for floating point comparisons; may
    438          *      be null if vertices are not to be combined in this builder.
    439          */
    440         private Builder(final Precision.DoubleEquivalence precision) {
    441             Objects.requireNonNull(precision, "Precision context must not be null");
    442
    443             this.precision = precision;
    444         }
    445
    446         /** Use a vertex in the constructed mesh. If an equivalent vertex already exist, as determined
    447          * by the configured {@link Precision.DoubleEquivalence}, then the index of the previously added
    448          * vertex is returned. Otherwise, the given vertex is added to the vertex list and the index
    449          * of the new entry is returned. This is in contrast with the {@link #addVertex(Vector3D)},
    450          * which always adds a new entry to the vertex list.
    451          * @param vertex vertex to use
    452          * @return the index of the added vertex or an equivalent vertex that was added previously
    453          * @see #addVertex(Vector3D)
    454          */
    455         public int useVertex(final Vector3D vertex) {
    456             final int nextIdx = vertices.size();
    457             final int actualIdx = addToVertexIndexMap(vertex, nextIdx, getVertexIndexMap());
    458
    459             // add to the vertex list if not already present
    460             if (actualIdx == nextIdx) {
    461                 addToVertexList(vertex);
    462             }
    463
    464             return actualIdx;
    465         }
    466
    467         /** Add a vertex directly to the vertex list, returning the index of the added vertex.
    468          * The vertex is added regardless of whether or not an equivalent vertex already
    469          * exists in the list. This is in contrast with the {@link #useVertex(Vector3D)} method,
    470          * which only adds a new entry to the vertex list if an equivalent one does not
    471          * already exist.
    472          * @param vertex the vertex to append
    473          * @return the index of the appended vertex in the vertex list
    474          */
    475         public int addVertex(final Vector3D vertex) {
    476             final int idx = addToVertexList(vertex);
    477
    478             if (vertexIndexMap != null) {
    479                 // add to the map in order to keep it in sync
    480                 addToVertexIndexMap(vertex, idx, vertexIndexMap);
    481             }
    482
    483             return idx;
    484         }
    485
    486         /** Add a group of vertices directly to the vertex list. No equivalent vertices are reused.
    487          * @param newVertices vertices to append
    488          * @return this instance
    489          * @see #addVertex(Vector3D)
    490          */
    491         public Builder addVertices(final Vector3D[] newVertices) {
    492             return addVertices(Arrays.asList(newVertices));
    493         }
    494
    495         /** Add a group of vertices directly to the vertex list. No equivalent vertices are reused.
    496          * @param newVertices vertices to append
    497          * @return this instance
    498          * @see #addVertex(Vector3D)
    499          */
    500         public Builder addVertices(final Collection<? extends Vector3D> newVertices) {
    501             final int newSize = vertices.size() + newVertices.size();
    502             ensureVertexCapacity(newSize);
    503
    504             for (final Vector3D vertex : newVertices) {
    505                 addVertex(vertex);
    506             }
    507
    508             return this;
    509         }
    510
    511         /** Ensure that this instance has enough capacity to store at least {@code numVertices}
    512          * number of vertices without reallocating space. This can be used to help improve performance
    513          * and memory usage when creating meshes with large numbers of vertices.
    514          * @param numVertices the number of vertices to ensure that this instance can contain
    515          * @return this instance
    516          */
    517         public Builder ensureVertexCapacity(final int numVertices) {
    518             vertices.ensureCapacity(numVertices);
    519             return this;
    520         }
    521
    522         /** Get the current number of vertices in this mesh.
    523          * @return the current number of vertices in this mesh
    524          */
    525         public int getVertexCount() {
    526             return vertices.size();
    527         }
    528
    529         /** Get the vertex at the given index.
    530          * @param index index of the vertex to retrieve
    531          * @return vertex at the given index
    532          * @throws IndexOutOfBoundsException if the index is out of bounds of the mesh vertex list
    533          */
    534         public Vector3D getVertex(final int index) {
    535             return vertices.get(index);
    536         }
    537
    538         /** Append a face to this mesh.
    539          * @param index1 index of the first vertex in the face
    540          * @param index2 index of the second vertex in the face
    541          * @param index3 index of the third vertex in the face
    542          * @return this instance
    543          * @throws IllegalArgumentException if any of the arguments is not a valid index into
    544          *      the current vertex list
    545          */
    546         public Builder addFace(final int index1, final int index2, final int index3) {
    547             validateCanModify();
    548
    549             final int[] indices = {
    550                 validateVertexIndex(index1),
    551                 validateVertexIndex(index2),
    552                 validateVertexIndex(index3)
    553             };
    554
    555             faces.add(indices);
    556
    557             return this;
    558         }
    559
    560         /** Append a face to this mesh.
    561          * @param face array containing the 3 vertex indices defining the face
    562          * @return this instance
    563          * @throws IllegalArgumentException if {@code face} does not contain exactly 3 elements
    564          *      or if any of the vertex indices is not a valid index into the current vertex list
    565          */
    566         public Builder addFace(final int[] face) {
    567             if (face.length != EuclideanUtils.TRIANGLE_VERTEX_COUNT) {
    568                 throw new IllegalArgumentException("Face must contain " + EuclideanUtils.TRIANGLE_VERTEX_COUNT +
    569                         " vertex indices; found " + face.length);
    570             }
    571
    572             addFace(face[0], face[1], face[2]);
    573
    574             return this;
    575         }
    576
    577         /** Append a group of faces to this mesh.
    578          * @param faceIndices faces to append
    579          * @return this instance
    580          * @throws IllegalArgumentException if any of the face index arrays does not have exactly 3 elements or
    581          *       if any index is not a valid index into the current vertex list
    582          */
    583         public Builder addFaces(final int[][] faceIndices) {
    584             return addFaces(Arrays.asList(faceIndices));
    585         }
    586
    587         /** Append a group of faces to this mesh.
    588          * @param faceIndices faces to append
    589          * @return this instance
    590          * @throws IllegalArgumentException if any of the face index arrays does not have exactly 3 elements or
    591          *       if any index is not a valid index into the current vertex list
    592          */
    593         public Builder addFaces(final Collection<int[]> faceIndices) {
    594             final int newSize = faces.size() + faceIndices.size();
    595             ensureFaceCapacity(newSize);
    596
    597             for (final int[] face : faceIndices) {
    598                 addFace(face);
    599             }
    600
    601             return this;
    602         }
    603
    604         /** Add a face to this mesh, only adding vertices to the vertex list if equivalent vertices are
    605          * not found.
    606          * @param p1 first face vertex
    607          * @param p2 second face vertex
    608          * @param p3 third face vertex
    609          * @return this instance
    610          * @see #useVertex(Vector3D)
    611          */
    612         public Builder addFaceUsingVertices(final Vector3D p1, final Vector3D p2, final Vector3D p3) {
    613             return addFace(
    614                         useVertex(p1),
    615                         useVertex(p2),
    616                         useVertex(p3)
    617                     );
    618         }
    619
    620         /** Add a face and its vertices to this mesh. The vertices are always added to the vertex list,
    621          * regardless of whether or not equivalent vertices exist in the vertex list.
    622          * @param p1 first face vertex
    623          * @param p2 second face vertex
    624          * @param p3 third face vertex
    625          * @return this instance
    626          * @see #addVertex(Vector3D)
    627          */
    628         public Builder addFaceAndVertices(final Vector3D p1, final Vector3D p2, final Vector3D p3) {
    629             return addFace(
    630                         addVertex(p1),
    631                         addVertex(p2),
    632                         addVertex(p3)
    633                     );
    634         }
    635
    636         /** Ensure that this instance has enough capacity to store at least {@code numFaces}
    637          * number of faces without reallocating space. This can be used to help improve performance
    638          * and memory usage when creating meshes with large numbers of faces.
    639          * @param numFaces the number of faces to ensure that this instance can contain
    640          * @return this instance
    641          */
    642         public Builder ensureFaceCapacity(final int numFaces) {
    643             faces.ensureCapacity(numFaces);
    644             return this;
    645         }
    646
    647         /** Get the current number of faces in this mesh.
    648          * @return the current number of faces in this meshr
    649          */
    650         public int getFaceCount() {
    651             return faces.size();
    652         }
    653
    654         /** Build a triangle mesh containing the vertices and faces in this builder.
    655          * @return a triangle mesh containing the vertices and faces in this builder
    656          */
    657         public SimpleTriangleMesh build() {
    658             built = true;
    659
    660             final Bounds3D bounds = boundsBuilder.hasBounds() ?
    661                     boundsBuilder.build() :
    662                     null;
    663
    664             vertices.trimToSize();
    665             faces.trimToSize();
    666
    667             return new SimpleTriangleMesh(
    668                     vertices,
    669                     faces,
    670                     bounds,
    671                     precision);
    672         }
    673
    674         /** Get the vertex index map, creating and initializing it if needed.
    675          * @return the vertex index map
    676          */
    677         private Map<Vector3D, Integer> getVertexIndexMap() {
    678             if (vertexIndexMap == null) {
    679                 vertexIndexMap = new TreeMap<>(new FuzzyVectorComparator(precision));
    680
    681                 // populate the index map
    682                 final int size = vertices.size();
    683                 for (int i = 0; i < size; ++i) {
    684                     addToVertexIndexMap(vertices.get(i), i, vertexIndexMap);
    685                 }
    686             }
    687             return vertexIndexMap;
    688         }
    689
    690         /** Add a vertex to the given vertex index map. The vertex is inserted and mapped to {@code targetidx}
    691          *  if an equivalent vertex does not already exist. The index now associated with the given vertex
    692          *  or its equivalent is returned.
    693          * @param vertex vertex to add
    694          * @param targetIdx the index to associate with the vertex if no equivalent vertex has already been
    695          *      mapped
    696          * @param map vertex index map
    697          * @return the index now associated with the given vertex or its equivalent
    698          */
    699         private int addToVertexIndexMap(final Vector3D vertex, final int targetIdx,
    700                 final Map<? super Vector3D, Integer> map) {
    701             validateCanModify();
    702
    703             final Integer actualIdx = map.putIfAbsent(vertex, targetIdx);
    704
    705             return actualIdx != null ?
    706                     actualIdx :
    707                     targetIdx;
    708         }
    709
    710         /** Append the given vertex to the end of the vertex list. The index of the vertex is returned.
    711          * @param vertex the vertex to append
    712          * @return the index of the appended vertex
    713          */
    714         private int addToVertexList(final Vector3D vertex) {
    715             validateCanModify();
    716
    717             boundsBuilder.add(vertex);
    718
    719             final int idx = vertices.size();
    720             vertices.add(vertex);
    721
    722             return idx;
    723         }
    724
    725         /** Throw an exception if the given vertex index is not valid.
    726          * @param idx vertex index to validate
    727          * @return the validated index
    728          * @throws IllegalArgumentException if the given index is not a valid index into
    729          *      the vertices list
    730          */
    731         private int validateVertexIndex(final int idx) {
    732             if (idx < 0 || idx >= vertices.size()) {
    733                 throw new IllegalArgumentException("Invalid vertex index: " + idx);
    734             }
    735
    736             return idx;
    737         }
    738
    739         /** Throw an exception if the builder has been used to construct a mesh instance
    740          * and can no longer be modified.
    741          */
    742         private void validateCanModify() {
    743             if (built) {
    744                 throw new IllegalStateException("Builder instance cannot be modified: mesh construction is complete");
    745             }
    746         }
    747     }
    748
    749     /** Comparator used to sort vectors using non-strict ("fuzzy") comparisons.
    750      * Vectors are considered equal if their values in all coordinate dimensions
    751      * are equivalent as evaluated by the precision context.
    752      */
    753     private static final class FuzzyVectorComparator implements Comparator<Vector3D> {
    754         /** Precision context to determine floating-point equality. */
    755         private final Precision.DoubleEquivalence precision;
    756
    757         /** Construct a new instance that uses the given precision context for
    758          * floating point comparisons.
    759          * @param precision precision context used for floating point comparisons
    760          */
    761         FuzzyVectorComparator(final Precision.DoubleEquivalence precision) {
    762             this.precision = precision;
    763         }
    764
    765         /** {@inheritDoc} */
    766         @Override
    767         public int compare(final Vector3D a, final Vector3D b) {
    768             int result = precision.compare(a.getX(), b.getX());
    769             if (result == 0) {
    770                 result = precision.compare(a.getY(), b.getY());
    771                 if (result == 0) {
    772                     result = precision.compare(a.getZ(), b.getZ());
    773                 }
    774             }
    775
    776             return result;
    777         }
    778     }
    779 }