forked from celeritas-project/celeritas
/
CsgTreeUtils.cc
144 lines (128 loc) · 4.33 KB
/
CsgTreeUtils.cc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
//----------------------------------*-C++-*----------------------------------//
// Copyright 2023-2024 UT-Battelle, LLC, and other Celeritas developers.
// See the top-level COPYRIGHT file for details.
// SPDX-License-Identifier: (Apache-2.0 OR MIT)
//---------------------------------------------------------------------------//
//! \file orange/orangeinp/CsgTreeUtils.cc
//---------------------------------------------------------------------------//
#include "CsgTreeUtils.hh"
#include <algorithm>
#include <utility>
#include <variant>
#include <vector>
#include "corecel/cont/Range.hh"
#include "detail/InfixStringBuilder.hh"
#include "detail/NodeReplacementInserter.hh"
namespace celeritas
{
namespace orangeinp
{
//---------------------------------------------------------------------------//
/*!
* Replace the given node ID with the replacement node.
*
* This recurses through daughters of "Joined" to simplify their originating
* surfaces if possible.
* - "negated": non-constant daughter node is replaced with ~b
* - "replaced": non-constant daughter node is replaced with `b`
* - "joined": for (false, or): all daughters are "false"
* for (true, and): all daughters are "true"
* - surface: "true"
* - constant: check for contradiction
*
* \return Node ID of the lowest node that required simplification.
*/
NodeId replace_down(CsgTree* tree, NodeId n, Node repl)
{
CELER_EXPECT(is_boolean_node(repl));
detail::NodeReplacementInserter::VecNode stack{{n, std::move(repl)}};
NodeId lowest_node{n};
while (!stack.empty())
{
n = std::move(stack.back().first);
repl = std::move(stack.back().second);
stack.pop_back();
lowest_node = std::min(n, lowest_node);
Node prev = tree->exchange(n, std::move(repl));
std::visit(detail::NodeReplacementInserter{&stack, repl}, prev);
}
return lowest_node;
}
//---------------------------------------------------------------------------//
/*!
* Simplify all nodes in the tree starting with this one.
*
* \return Lowest ID of any simplified node
*/
NodeId simplify_up(CsgTree* tree, NodeId start)
{
CELER_EXPECT(tree);
CELER_EXPECT(start < tree->size());
// Sweep bottom to top to simplify the tree
NodeId result;
for (auto node_id : range(start, NodeId{tree->size()}))
{
bool simplified = tree->simplify(node_id);
if (simplified && !result)
{
result = node_id;
}
}
return result;
}
//---------------------------------------------------------------------------//
/*!
* Iteratively simplify all nodes in the tree.
*
* The input 'start' node should be the minimum node from a \c replace_down
* operation. In the worst case, it should take as many sweeps as the depth of
* the tree.
*/
void simplify(CsgTree* tree, NodeId start)
{
CELER_EXPECT(tree);
CELER_EXPECT(start > tree->false_node_id() && start < tree->size());
while (start)
{
auto next_start = simplify_up(tree, start);
CELER_ASSERT(!next_start || next_start > start);
start = next_start;
}
}
//---------------------------------------------------------------------------//
/*!
* Convert a node to an infix string expression.
*/
[[nodiscard]] std::string build_infix_string(CsgTree const& tree, NodeId n)
{
CELER_EXPECT(n < tree.size());
std::ostringstream os;
detail::InfixStringBuilder build_impl{tree, &os};
build_impl(n);
return os.str();
}
//---------------------------------------------------------------------------//
/*!
* Construct the sorted set of all surfaces that are part of the tree.
*
* This list removes surfaces that have been eliminated by logical replacement.
* Thanks to the CSG tree's deduplication, each surface should appear in the
* tree at most once.
*/
[[nodiscard]] std::vector<LocalSurfaceId> calc_surfaces(CsgTree const& tree)
{
std::vector<LocalSurfaceId> result;
for (auto node_id : range(NodeId{tree.size()}))
{
if (Surface const* s = std::get_if<Surface>(&tree[node_id]))
{
result.push_back(s->id);
}
}
std::sort(result.begin(), result.end());
CELER_ENSURE(std::unique(result.begin(), result.end()) == result.end());
return result;
}
//---------------------------------------------------------------------------//
} // namespace orangeinp
} // namespace celeritas