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.examples.jmh.euclidean;
    18
    19  import java.util.List;
    20  import java.util.concurrent.TimeUnit;
    21
    22  import org.apache.commons.geometry.euclidean.threed.PlaneConvexSubset;
    23  import org.apache.commons.geometry.euclidean.threed.RegionBSPTree3D;
    24  import org.apache.commons.geometry.euclidean.threed.Vector3D;
    25  import org.apache.commons.geometry.euclidean.threed.shape.Sphere;
    26  import org.apache.commons.numbers.core.Precision;
    27  import org.openjdk.jmh.annotations.Benchmark;
    28  import org.openjdk.jmh.annotations.BenchmarkMode;
    29  import org.openjdk.jmh.annotations.Fork;
    30  import org.openjdk.jmh.annotations.Level;
    31  import org.openjdk.jmh.annotations.Measurement;
    32  import org.openjdk.jmh.annotations.Mode;
    33  import org.openjdk.jmh.annotations.OutputTimeUnit;
    34  import org.openjdk.jmh.annotations.Param;
    35  import org.openjdk.jmh.annotations.Scope;
    36  import org.openjdk.jmh.annotations.Setup;
    37  import org.openjdk.jmh.annotations.State;
    38  import org.openjdk.jmh.annotations.Warmup;
    39
    40  /** Benchmarks for the {@link RegionBSPTree3D} class.
    41   */
    42  @BenchmarkMode(Mode.AverageTime)
    43  @OutputTimeUnit(TimeUnit.NANOSECONDS)
    44  @Warmup(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
    45  @Measurement(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
    46  @Fork(value = 1, jvmArgs = {"-server", "-Xms512M", "-Xmx512M"})
    47  public class RegionBSPTree3DPerformance {
    48
    49      /** Base class for inputs that use sphere approximation boundaries.
    50       */
    51      @State(Scope.Thread)
    52      public static class SphericalBoundaryInputBase {
    53
    54          /** The input to use for the subdivisions parameter when generating the
    55           * sphere boundaries.
    56           */
    57          @Param({"2", "3", "4"})
    58          private int subdivisions;
    59
    60          /** Compute the boundaries for the instance.
    61           * @return the boundaries for the instance.
    62           */
    63          protected List<PlaneConvexSubset> computeBoundaries() {
    64              final Sphere sphere = Sphere.from(Vector3D.ZERO, 1, Precision.doubleEquivalenceOfEpsilon(1e-10));
    65              return sphere.toTree(subdivisions).getBoundaries();
    66          }
    67      }
    68
    69      /** Class providing a list of boundaries for a sphere approximation.
    70       */
    71      @State(Scope.Thread)
    72      public static class SphericalBoundaryInput extends SphericalBoundaryInputBase {
    73
    74          /** List containing the convex boundaries of the sphere approximation. */
    75          private List<PlaneConvexSubset> boundaries;
    76
    77          /** Set up the instance for the benchmark. */
    78          @Setup(Level.Iteration)
    79          public void setup() {
    80              boundaries = computeBoundaries();
    81          }
    82
    83          /** Get the computed sphere boundaries.
    84           * @return the computed sphere boundaries
    85           */
    86          public List<PlaneConvexSubset> getBoundaries() {
    87              return boundaries;
    88          }
    89      }
    90
    91      /** Class providing a region approximating a spherical boundary. The region is in a worst-case
    92       * tree structure, meaning that the tree is completely unbalanced.
    93       */
    94      @State(Scope.Thread)
    95      public static class WorstCaseSphericalRegionInput extends SphericalBoundaryInputBase {
    96
    97          /** The sphere approximation region. */
    98          private RegionBSPTree3D tree;
    99
    100         /** Set up the instance for the benchmark. */
    101         @Setup(Level.Iteration)
    102         public void setup() {
    103             tree = RegionBSPTree3D.empty();
    104             tree.insert(computeBoundaries());
    105         }
    106
    107         /** Get the tree for the instance.
    108          * @return the tree for the instance
    109          */
    110         public RegionBSPTree3D getTree() {
    111             return tree;
    112         }
    113     }
    114
    115     /** Benchmark testing the performance of tree creation for a convex region. The insertion
    116      * behavior is worst-case, meaning that the tree is unbalanced and degenerates into a simple
    117      * list of nodes.
    118      * @param input benchmark boundary input
    119      * @return created BSP tree
    120      */
    121     @Benchmark
    122     public RegionBSPTree3D insertConvexWorstCase(final SphericalBoundaryInput input) {
    123         final RegionBSPTree3D tree = RegionBSPTree3D.empty();
    124
    125         for (final PlaneConvexSubset boundary : input.getBoundaries()) {
    126             tree.insert(boundary);
    127         }
    128
    129         return tree;
    130     }
    131
    132     /** Benchmark testing the performance of boundary determination using a tree with a worst-case,
    133      * unbalanced structure.
    134      * @param input input tree
    135      * @return list of tree boundaries
    136      */
    137     @Benchmark
    138     public List<PlaneConvexSubset> boundaryConvexWorstCase(final WorstCaseSphericalRegionInput input) {
    139         return input.getTree().getBoundaries();
    140     }
    141 }