forked from celeritas-project/celeritas
/
CsgTree.hh
125 lines (104 loc) · 4.07 KB
/
CsgTree.hh
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
//----------------------------------*-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/CsgTree.hh
//---------------------------------------------------------------------------//
#pragma once
#include <iostream>
#include <unordered_map>
#include <variant>
#include <vector>
#include "corecel/OpaqueId.hh"
#include "corecel/math/HashUtils.hh"
#include "CsgTypes.hh"
namespace celeritas
{
namespace orangeinp
{
//---------------------------------------------------------------------------//
/*!
* DAG of constructed CSG nodes within a universe.
*
* Inserting a new node performs one local simplification for "join" types
* (removing duplicates, replacing zero- and one- entry special cases); and all
* nodes are inserted into a deduplicated map of nodes that may be further
* simplified later (see \c CsgAlgorithms).
*
* The tree is a topologically sorted graph where the leaves are the lower node
* indices. The intent is for higher nodes to be simplified to boolean values,
* e.g., by representing that all points in space are inside a cylinder by
* replacing a \c Joined node with \c True . To facilitate this while
* preserving node indices, \c True and \c False nodes are automatically
* inserted as the first two node IDs. Because \c False is represented as "not
* true" during evaluation, it actually stores \c Negated{true_node_id()} and
* the deduplication table maps \c False to \c false_node_id() .
*
* \note The node classes use aggregate initialization so cannot be created
* directly as \c Node variant classes using \c std::in_place_type .
*/
class CsgTree
{
public:
//!@{
//! \name Type aliases
using Node = orangeinp::Node;
using NodeId = orangeinp::NodeId;
using size_type = NodeId::size_type;
using Insertion = std::pair<NodeId, bool>;
//!@}
public:
// Construct with no nodes except "true" and "false"
CsgTree();
// Add a node and return the new ID and whether it's unique
Insertion insert(Node&& n);
// Add a surface ID and return the new ID
inline Insertion insert(LocalSurfaceId s);
//! Number of nodes
NodeId::size_type size() const { return nodes_.size(); }
// Get a node
inline Node const& operator[](NodeId node_id) const;
// Replace a node with a logically equivalent one, simplifying
Node exchange(NodeId node_id, Node&& n);
// Simplify a single node in-place [O(1)]
bool simplify(NodeId);
//// STATIC HELPERS ////
static constexpr NodeId true_node_id() { return NodeId{0}; }
static constexpr NodeId false_node_id() { return NodeId{1}; }
private:
// Tree structure: nodes may have been simplified
std::vector<Node> nodes_;
// Hashed nodes, both original and simplified
std::unordered_map<Node, NodeId> ids_;
//// HELPER FUNCTIONS ////
// Get a node (only this class can modify the node once added)
Node& at(NodeId node_id);
};
//---------------------------------------------------------------------------//
// FREE FUNCTIONS
//---------------------------------------------------------------------------//
// Print the tree's contents
std::ostream& operator<<(std::ostream& os, CsgTree const&);
//---------------------------------------------------------------------------//
// INLINE DEFINITIONS
//---------------------------------------------------------------------------//
/*!
* Add a surface.
*/
auto CsgTree::insert(LocalSurfaceId s) -> Insertion
{
return this->insert(orangeinp::Surface{s});
}
//---------------------------------------------------------------------------//
/*!
* Get a node by ID.
*/
auto CsgTree::operator[](NodeId node_id) const -> Node const&
{
CELER_EXPECT(node_id < nodes_.size());
return nodes_[node_id.unchecked_get()];
}
//---------------------------------------------------------------------------//
} // namespace orangeinp
} // namespace celeritas