Line data Source code
1 : // EnergyPlus, Copyright (c) 1996-2023, The Board of Trustees of the University of Illinois,
2 : // The Regents of the University of California, through Lawrence Berkeley National Laboratory
3 : // (subject to receipt of any required approvals from the U.S. Dept. of Energy), Oak Ridge
4 : // National Laboratory, managed by UT-Battelle, Alliance for Sustainable Energy, LLC, and other
5 : // contributors. All rights reserved.
6 : //
7 : // NOTICE: This Software was developed under funding from the U.S. Department of Energy and the
8 : // U.S. Government consequently retains certain rights. As such, the U.S. Government has been
9 : // granted for itself and others acting on its behalf a paid-up, nonexclusive, irrevocable,
10 : // worldwide license in the Software to reproduce, distribute copies to the public, prepare
11 : // derivative works, and perform publicly and display publicly, and to permit others to do so.
12 : //
13 : // Redistribution and use in source and binary forms, with or without modification, are permitted
14 : // provided that the following conditions are met:
15 : //
16 : // (1) Redistributions of source code must retain the above copyright notice, this list of
17 : // conditions and the following disclaimer.
18 : //
19 : // (2) Redistributions in binary form must reproduce the above copyright notice, this list of
20 : // conditions and the following disclaimer in the documentation and/or other materials
21 : // provided with the distribution.
22 : //
23 : // (3) Neither the name of the University of California, Lawrence Berkeley National Laboratory,
24 : // the University of Illinois, U.S. Dept. of Energy nor the names of its contributors may be
25 : // used to endorse or promote products derived from this software without specific prior
26 : // written permission.
27 : //
28 : // (4) Use of EnergyPlus(TM) Name. If Licensee (i) distributes the software in stand-alone form
29 : // without changes from the version obtained under this License, or (ii) Licensee makes a
30 : // reference solely to the software portion of its product, Licensee must refer to the
31 : // software as "EnergyPlus version X" software, where "X" is the version number Licensee
32 : // obtained under this License and may not use a different name for the software. Except as
33 : // specifically required in this Section (4), Licensee shall not use in a company name, a
34 : // product name, in advertising, publicity, or other promotional activities any name, trade
35 : // name, trademark, logo, or other designation of "EnergyPlus", "E+", "e+" or confusingly
36 : // similar designation, without the U.S. Department of Energy's prior written consent.
37 : //
38 : // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR
39 : // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
40 : // AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
41 : // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
42 : // CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
43 : // SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
44 : // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
45 : // OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
46 : // POSSIBILITY OF SUCH DAMAGE.
47 :
48 : // EnergyPlus Headers
49 : #include <EnergyPlus/DataSurfaces.hh>
50 : #include <EnergyPlus/SurfaceOctree.hh>
51 :
52 : // C++ Headers
53 : #include <algorithm>
54 : #include <cmath>
55 : #include <limits>
56 :
57 : namespace EnergyPlus {
58 :
59 : // Package: Surface Octree System
60 : //
61 : // Purpose: Spatial sort of surfaces for fast, scalable identification of active surfaces for algorithms
62 : // making spatial queries such as solar shading, solar reflection, and daylighting obstruction
63 : //
64 : // Author: Stuart Mentzer (Stuart_Mentzer@objexx.com)
65 : //
66 : // History:
67 : // Sep 2015: Experimental code
68 : // Jan 2016: Initial release
69 : //
70 : // Notes:
71 : // Initial octree is for use in daylighting but should be adaptable to other use cases:
72 : // Surfaces without vertices are omitted
73 : // Transparent surfaces are omitted (can't obstruct light)
74 : // The octree holds live references to surfaces so it must be updated if surfaces change after its construction (this doesn't occur in EnergyPlus
75 : // currently) Copy and move ctors/assignment omitted for now since not needed The use of multiple octrees for faster lookups of surface type subsets
76 : // may be worthwhile for performance in some uses Octree variations and parameter tuning can give better performance for specific applications This
77 : // design uses "tight" cubes (no overlap) and surfaces filtering down to deepest cube they fit in completely Alternative designs that might offer
78 : // somewhat better or worse performance:
79 : // Loose cubes oversied by x2 or some other factor to allow surfaces to filter down further: This requires more cubes to be processed for a given
80 : // operation Filter all surfaces down to leaf cubes placing a surface in any cube it intersects: More specificity but redundant surfaces in each
81 : // operation so must collect them in a set
82 :
83 : // Surface in Cube?
84 0 : bool SurfaceOctreeCube::contains(Surface const &surface) const
85 : {
86 0 : for (Vertex const &v : surface.Vertex) { // All surface vertices must be in cube
87 0 : if (!contains(v)) return false;
88 : }
89 0 : return true;
90 : }
91 :
92 : // Surfaces Outer Cube Initilization
93 15 : void SurfaceOctreeCube::init(EPVector<Surface> &surfaces)
94 : {
95 15 : assert(d_ == 0u);
96 15 : assert(n_ == 0u);
97 15 : surfaces_.clear();
98 15 : surfaces_.reserve(surfaces.size());
99 5606 : for (Surface &surface : surfaces) {
100 10775 : if ((surface.Vertex.size() >= 3) && // Skip no-vertex "surfaces"
101 5184 : (!surface.IsTransparent) // Skip transparent surfaces
102 : ) {
103 5184 : surfaces_.push_back(&surface);
104 : }
105 : }
106 :
107 : // No surfaces handler
108 15 : if (surfaces_.empty()) {
109 0 : l_ = u_ = c_ = Vertex(0.0);
110 0 : w_ = r_ = 0.0;
111 0 : return;
112 : }
113 :
114 : // Bounding box corners and center
115 15 : Surface const &surface_0(*surfaces_[0]);
116 15 : assert(!surface_0.Vertex.empty());
117 15 : l_ = u_ = surface_0.Vertex[0]; // Initialize corners to first vertex of first surface
118 5199 : for (Surface const *surface_p : surfaces_) { // Surfaces
119 5184 : auto const &vertices(surface_p->Vertex);
120 26158 : for (auto const &vertex : vertices) { // Expand cube to hold surface vertices
121 20974 : l_.min(vertex);
122 20974 : u_.max(vertex);
123 : }
124 : }
125 15 : c_ = cen(l_, u_); // Center vertex
126 :
127 : // Expand bounding box to cube with uniform side width
128 30 : Vertex const diagonal(u_ - l_); // Diagonal
129 15 : w_ = ObjexxFCL::max(diagonal.x, diagonal.y, diagonal.z);
130 15 : r_ = 0.75 * (w_ * w_);
131 15 : Real const h(0.5 * w_); // Half-width
132 15 : l_ = c_ - h;
133 15 : u_ = c_ + h;
134 :
135 15 : assert(valid());
136 :
137 : // Branch sub-tree
138 15 : branch();
139 : }
140 :
141 : // Valid?
142 495 : bool SurfaceOctreeCube::valid() const
143 : {
144 495 : if (((l_.x <= c_.x) && (l_.y <= c_.y) && (l_.z <= c_.z)) && ((c_.x <= u_.x) && (c_.y <= u_.y) && (c_.z <= u_.z))) {
145 : Real const tol2(
146 990 : std::max(std::max(ObjexxFCL::magnitude_squared(l_), ObjexxFCL::magnitude_squared(u_)) * (4 * std::numeric_limits<Real>::epsilon()),
147 1485 : 2 * std::numeric_limits<Real>::min()));
148 495 : if (ObjexxFCL::distance_squared(c_, cen(l_, u_)) <= tol2) {
149 1485 : Real const tol(std::max(std::sqrt(std::max(ObjexxFCL::magnitude_squared(l_), ObjexxFCL::magnitude_squared(u_))) *
150 495 : (4 * std::numeric_limits<Real>::epsilon()),
151 1485 : 2 * std::numeric_limits<Real>::min()));
152 990 : Vertex const d(u_ - l_); // Diagonal
153 495 : return (std::abs(d.x - w_) <= tol) && (std::abs(d.x - d.y) <= tol) && (std::abs(d.x - d.z) <= tol); // Uniform side widths?
154 : }
155 : }
156 0 : return false;
157 : }
158 :
159 : // Branch to Sub-Tree
160 495 : void SurfaceOctreeCube::branch()
161 : {
162 495 : if ((surfaces_.size() > maxSurfaces_) && (d_ < maxDepth_)) {
163 : // Assign Surfaces to cubes containing them
164 326 : Surfaces surfaces_all;
165 163 : surfaces_all.swap(surfaces_);
166 10240 : for (auto *surface_p : surfaces_all) { // Surfaces
167 10077 : surfaceBranch(*surface_p);
168 : }
169 :
170 : // Compact occupied cube array
171 163 : n_ = 0u;
172 1467 : for (std::uint8_t i = 0; i < 8; ++i) {
173 1304 : SurfaceOctreeCube *&cube = cubes_[i];
174 1304 : if (cube != nullptr) {
175 480 : if (n_ < i) {
176 315 : cubes_[n_] = cube;
177 315 : cube = nullptr;
178 : }
179 480 : ++n_;
180 : }
181 : }
182 :
183 : // Branch sub-tree recursively
184 643 : for (std::uint8_t i = 0; i < n_; ++i) {
185 480 : cubes_[i]->branch();
186 : }
187 : }
188 495 : }
189 :
190 : // Surface Branch Processing
191 10077 : void SurfaceOctreeCube::surfaceBranch(Surface &surface)
192 : {
193 10077 : Real const h(0.5 * w_); // Half-width
194 20154 : Vertex sl(surface.Vertex[0]), su(surface.Vertex[0]); // Surface bounding box corners
195 10077 : auto const &vertices(surface.Vertex); // Surface vertices
196 50677 : for (auto const &vertex : vertices) { // Expand bounding box to hold surface vertices
197 40600 : sl.min(vertex);
198 40600 : su.max(vertex);
199 : }
200 20154 : Vertex const ctr(cen(sl, su));
201 10077 : std::uint8_t const i(ctr.x <= c_.x ? 0 : 1);
202 10077 : std::uint8_t const j(ctr.y <= c_.y ? 0 : 1);
203 10077 : std::uint8_t const k(ctr.z <= c_.z ? 0 : 1);
204 10077 : SurfaceOctreeCube *&cube = cubes_[(i << 2) + (j << 1) + k];
205 10077 : if (cube != nullptr) { // Candidate cube exists
206 15587 : if (((cube->l_.x <= sl.x) && (cube->l_.y <= sl.y) && (cube->l_.z <= sl.z)) &&
207 14011 : ((su.x <= cube->u_.x) && (su.y <= cube->u_.y) && (su.z <= cube->u_.z))) { // Surface is contained in sub-cube
208 5717 : cube->add(surface);
209 : } else { // Surface stays in this cube
210 2601 : surfaces_.push_back(&surface);
211 : }
212 : } else { // Create cube if surface contained
213 1759 : Real const x(i * h);
214 1759 : Real const y(j * h);
215 1759 : Real const z(k * h);
216 3518 : Vertex const l(l_.x + x, l_.y + y, l_.z + z);
217 3518 : Vertex const u(c_.x + x, c_.y + y, c_.z + z);
218 2754 : if (((l.x <= sl.x) && (l.y <= sl.y) && (l.z <= sl.z)) &&
219 1749 : ((su.x <= u.x) && (su.y <= u.y) && (su.z <= u.z))) { // Surface is contained in sub-cube
220 480 : cube = new SurfaceOctreeCube(d_ + 1, l, u, h);
221 480 : cube->add(surface);
222 : } else { // Surface stays in this cube
223 1279 : surfaces_.push_back(&surface);
224 : }
225 : }
226 10077 : }
227 :
228 : // Surface in Cube?
229 0 : bool SurfaceOctreeCube::contains(Vertex const &l, Vertex const &u, Surface const &surface)
230 : {
231 0 : for (Vertex const &v : surface.Vertex) { // All surface vertices must be in cube
232 0 : if (!contains(l, u, v)) return false;
233 : }
234 0 : return true;
235 : }
236 :
237 : // Static Data Member Definitions
238 : std::uint8_t const SurfaceOctreeCube::maxDepth_ = 255u; // Max tree depth
239 : SurfaceOctreeCube::size_type const SurfaceOctreeCube::maxSurfaces_ = 10u; // Max surfaces in a cube before subdividing
240 :
241 2313 : } // namespace EnergyPlus
|
