orangeinp/detail/LocalSurfaceInserter.hh

0001 //----------------------------------*-C++-*----------------------------------//
0002 // Copyright 2023-2024 UT-Battelle, LLC, and other Celeritas developers.
0003 // See the top-level COPYRIGHT file for details.
0004 // SPDX-License-Identifier: (Apache-2.0 OR MIT)
0005 //---------------------------------------------------------------------------//
0006 //! \file orange/orangeinp/detail/LocalSurfaceInserter.hh
0007 //---------------------------------------------------------------------------//
0008 #pragma once
0009
0010 #include <algorithm>
0011 #include <unordered_map>
0012 #include <vector>
0013
0014 #include "orange/OrangeTypes.hh"
0015 #include "orange/surf/SoftSurfaceEqual.hh"
0016 #include "orange/surf/VariantSurface.hh"
0017
0018 #include "SurfaceGridHash.hh"
0019
0020 namespace celeritas
0021 {
0022 namespace orangeinp
0023 {
0024 namespace detail
0025 {
0026 //---------------------------------------------------------------------------//
0027 /*!
0028  * Merge local surfaces as they're being built.
0029  *
0030  * This will \em sometimes will return the ID of a previously inserted surface,
0031  * and \em sometimes will push the surface onto the vector of existing ones.
0032  *
0033  * There are three cases to consider:
0034  * - The new surface is entirely unique: we insert and return the new ID.
0035  * - The surface is soft equivalent but not exactly like an existing surface:
0036  *   we insert but return an existing ID.
0037  * - The surface is exactly the same: we do \em not insert, and return the
0038  *   existing id.
0039  *
0040  * The second case adds the surface so that multiple nearby surfaces can be
0041  * \em chained together, even if the tolerance between the furthest apart is
0042  * greater than the soft equivalence tolerance.
0043  *
0044  * To speed up insertion when large numbers of potentially similar surface are
0045  * constructed, this class uses a hash table to "bin" surfaces based on a
0046  * function of their spatial coordinates. Surfaces that *could* compare equal
0047  * all share the same bin or are at the edge of an adjacent one. Since this
0048  * hash table uses the standard library's implementation, it resizes
0049  * dynamically to keep the number of surfaces per bucket low (assuming a good
0050  * hash function), thus keeping insertion time at an amortized O(1) versus the
0051  * O(N) that would result from comparing against every other surface.
0052  */
0053 class LocalSurfaceInserter
0054 {
0055   public:
0056     //!@{
0057     //! \name Type aliases
0058     using VecSurface = std::vector<VariantSurface>;
0059     //!@}
0060
0061   public:
0062     // Construct with tolerance and a pointer to the surfaces vector
0063     LocalSurfaceInserter(VecSurface* v, Tolerance<> const& tol);
0064
0065     // Construct a surface with deduplication
0066     template<class S>
0067     LocalSurfaceId operator()(S const& surface);
0068
0069   private:
0070     //// TYPES ////
0071
0072     using MapSurfId = std::unordered_map<LocalSurfaceId, LocalSurfaceId>;
0073     using MultimapSurfaces
0074         = std::unordered_multimap<SurfaceGridHash::key_type, LocalSurfaceId>;
0075
0076     //// DATA ////
0077
0078     VecSurface* surfaces_;
0079
0080     // Deduplication
0081     SoftSurfaceEqual soft_surface_equal_;
0082     ExactSurfaceEqual exact_surface_equal_;
0083     MapSurfId merged_;
0084
0085     // Hash acceleration
0086     MultimapSurfaces hashed_surfaces_;
0087     SurfaceGridHash calc_hashes_;
0088
0089     //// METHODS ////
0090
0091     LocalSurfaceId merge_impl(LocalSurfaceId source, LocalSurfaceId target);
0092     LocalSurfaceId find_merged(LocalSurfaceId target) const;
0093
0094     //! Width of a hash bin, in units of the problem's length scale
0095     static constexpr real_type bin_width_frac() { return 0.01; }
0096 };
0097
0098 //---------------------------------------------------------------------------//
0099 }  // namespace detail
0100 }  // namespace orangeinp
0101 }  // namespace celeritas