orangeinp/detail/LocalSurfaceInserter.hh

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