Line data Source code
1 : // EnergyPlus, Copyright (c) 1996-2025, 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)) {
88 0 : return false;
89 : }
90 : }
91 0 : return true;
92 : }
93 :
94 : // Surfaces Outer Cube Initilization
95 16 : void SurfaceOctreeCube::init(EPVector<Surface> &surfaces)
96 : {
97 16 : assert(d_ == 0u);
98 16 : assert(n_ == 0u);
99 16 : surfaces_.clear();
100 16 : surfaces_.reserve(surfaces.size());
101 6707 : for (Surface &surface : surfaces) {
102 12845 : if ((surface.Vertex.size() >= 3) && // Skip no-vertex "surfaces"
103 6154 : (!surface.IsTransparent) // Skip transparent surfaces
104 : ) {
105 6154 : surfaces_.push_back(&surface);
106 : }
107 16 : }
108 :
109 : // No surfaces handler
110 16 : if (surfaces_.empty()) {
111 0 : l_ = u_ = c_ = Vertex(0.0);
112 0 : w_ = r_ = 0.0;
113 0 : return;
114 : }
115 :
116 : // Bounding box corners and center
117 16 : Surface const &surface_0(*surfaces_[0]);
118 16 : assert(!surface_0.Vertex.empty());
119 16 : l_ = u_ = surface_0.Vertex[0]; // Initialize corners to first vertex of first surface
120 6170 : for (Surface const *surface_p : surfaces_) { // Surfaces
121 6154 : auto const &vertices(surface_p->Vertex);
122 31008 : for (auto const &vertex : vertices) { // Expand cube to hold surface vertices
123 24854 : l_.min(vertex);
124 24854 : u_.max(vertex);
125 : }
126 16 : }
127 16 : c_ = cen(l_, u_); // Center vertex
128 :
129 : // Expand bounding box to cube with uniform side width
130 16 : Vertex const diagonal(u_ - l_); // Diagonal
131 16 : w_ = ObjexxFCL::max(diagonal.x, diagonal.y, diagonal.z);
132 16 : r_ = 0.75 * (w_ * w_);
133 16 : Real const h(0.5 * w_); // Half-width
134 16 : l_ = c_ - h;
135 16 : u_ = c_ + h;
136 :
137 16 : assert(valid());
138 :
139 : // Branch sub-tree
140 16 : branch();
141 16 : }
142 :
143 : // Valid?
144 573 : bool SurfaceOctreeCube::valid() const
145 : {
146 573 : 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))) {
147 : Real const tol2(
148 573 : std::max(std::max(ObjexxFCL::magnitude_squared(l_), ObjexxFCL::magnitude_squared(u_)) * (4 * std::numeric_limits<Real>::epsilon()),
149 573 : 2 * std::numeric_limits<Real>::min()));
150 573 : if (ObjexxFCL::distance_squared(c_, cen(l_, u_)) <= tol2) {
151 573 : Real const tol(std::max(std::sqrt(std::max(ObjexxFCL::magnitude_squared(l_), ObjexxFCL::magnitude_squared(u_))) *
152 573 : (4 * std::numeric_limits<Real>::epsilon()),
153 573 : 2 * std::numeric_limits<Real>::min()));
154 573 : Vertex const d(u_ - l_); // Diagonal
155 573 : return (std::abs(d.x - w_) <= tol) && (std::abs(d.x - d.y) <= tol) && (std::abs(d.x - d.z) <= tol); // Uniform side widths?
156 573 : }
157 : }
158 0 : return false;
159 : }
160 :
161 : // Branch to Sub-Tree
162 573 : void SurfaceOctreeCube::branch()
163 : {
164 573 : if ((surfaces_.size() > maxSurfaces_) && (d_ < maxDepth_)) {
165 : // Assign Surfaces to cubes containing them
166 191 : Surfaces surfaces_all;
167 191 : surfaces_all.swap(surfaces_);
168 12727 : for (auto *surface_p : surfaces_all) { // Surfaces
169 12536 : surfaceBranch(*surface_p);
170 191 : }
171 :
172 : // Compact occupied cube array
173 191 : n_ = 0u;
174 1719 : for (std::uint8_t i = 0; i < 8; ++i) {
175 1528 : SurfaceOctreeCube *&cube = cubes_[i];
176 1528 : if (cube != nullptr) {
177 557 : if (n_ < i) {
178 385 : cubes_[n_] = cube;
179 385 : cube = nullptr;
180 : }
181 557 : ++n_;
182 : }
183 : }
184 :
185 : // Branch sub-tree recursively
186 748 : for (std::uint8_t i = 0; i < n_; ++i) {
187 557 : cubes_[i]->branch();
188 : }
189 191 : }
190 573 : }
191 :
192 : // Surface Branch Processing
193 12536 : void SurfaceOctreeCube::surfaceBranch(Surface &surface)
194 : {
195 12536 : Real const h(0.5 * w_); // Half-width
196 12536 : Vertex sl(surface.Vertex[0]), su(surface.Vertex[0]); // Surface bounding box corners
197 12536 : auto const &vertices(surface.Vertex); // Surface vertices
198 62972 : for (auto const &vertex : vertices) { // Expand bounding box to hold surface vertices
199 50436 : sl.min(vertex);
200 50436 : su.max(vertex);
201 : }
202 12536 : Vertex const ctr(cen(sl, su));
203 12536 : std::uint8_t const i(ctr.x <= c_.x ? 0 : 1);
204 12536 : std::uint8_t const j(ctr.y <= c_.y ? 0 : 1);
205 12536 : std::uint8_t const k(ctr.z <= c_.z ? 0 : 1);
206 12536 : SurfaceOctreeCube *&cube = cubes_[(i << 2) + (j << 1) + k];
207 12536 : if (cube != nullptr) { // Candidate cube exists
208 10578 : if (((cube->l_.x <= sl.x) && (cube->l_.y <= sl.y) && (cube->l_.z <= sl.z)) &&
209 9309 : ((su.x <= cube->u_.x) && (su.y <= cube->u_.y) && (su.z <= cube->u_.z))) { // Surface is contained in sub-cube
210 7351 : cube->add(surface);
211 : } else { // Surface stays in this cube
212 3227 : surfaces_.push_back(&surface);
213 : }
214 : } else { // Create cube if surface contained
215 1958 : Real const x(i * h);
216 1958 : Real const y(j * h);
217 1958 : Real const z(k * h);
218 1958 : Vertex const l(l_.x + x, l_.y + y, l_.z + z);
219 1958 : Vertex const u(c_.x + x, c_.y + y, c_.z + z);
220 1958 : if (((l.x <= sl.x) && (l.y <= sl.y) && (l.z <= sl.z)) &&
221 1162 : ((su.x <= u.x) && (su.y <= u.y) && (su.z <= u.z))) { // Surface is contained in sub-cube
222 557 : cube = new SurfaceOctreeCube(d_ + 1, l, u, h);
223 557 : cube->add(surface);
224 : } else { // Surface stays in this cube
225 1401 : surfaces_.push_back(&surface);
226 : }
227 1958 : }
228 12536 : }
229 :
230 : // Surface in Cube?
231 0 : bool SurfaceOctreeCube::contains(Vertex const &l, Vertex const &u, Surface const &surface)
232 : {
233 0 : for (Vertex const &v : surface.Vertex) { // All surface vertices must be in cube
234 0 : if (!contains(l, u, v)) {
235 0 : return false;
236 : }
237 : }
238 0 : return true;
239 : }
240 :
241 : // Static Data Member Definitions
242 : std::uint8_t const SurfaceOctreeCube::maxDepth_ = 255u; // Max tree depth
243 : SurfaceOctreeCube::size_type const SurfaceOctreeCube::maxSurfaces_ = 10u; // Max surfaces in a cube before subdividing
244 :
245 : } // namespace EnergyPlus
|
