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