Loading...
Searching...
No Matches
SignedFloodFill.h
Go to the documentation of this file.
// Copyright Contributors to the OpenVDB Project
// SPDX-License-Identifier: MPL-2.0
//
/// @file SignedFloodFill.h
///
/// @brief Propagate the signs of distance values from the active voxels
/// in the narrow band to the inactive values outside the narrow band.
///
/// @author Ken Museth
#ifndef OPENVDB_TOOLS_SIGNEDFLOODFILL_HAS_BEEN_INCLUDED
#define OPENVDB_TOOLS_SIGNEDFLOODFILL_HAS_BEEN_INCLUDED
#include <openvdb/version.h>
#include <openvdb/Types.h> // for Index typedef
#include <openvdb/math/Math.h> // for math::negative
#include <openvdb/tree/NodeManager.h>
#include <openvdb/openvdb.h>
#include <map>
#include <type_traits>
namespace openvdb {
OPENVDB_USE_VERSION_NAMESPACE
namespace OPENVDB_VERSION_NAME {
namespace tools {
/// @brief Set the values of all inactive voxels and tiles of a narrow-band
/// level set from the signs of the active voxels, setting outside values to
/// +background and inside values to -background.
///
/// @warning This method should only be used on closed, symmetric narrow-band level sets.
///
/// @note If a LeafManager is used the cached leaf nodes are reused,
/// resulting in slightly better overall performance.
///
/// @param tree Tree or LeafManager that will be flood filled.
/// @param threaded enable or disable threading (threading is enabled by default)
/// @param grainSize used to control the threading granularity (default is 1)
/// @param minLevel Specify the lowest tree level to process (leafnode level = 0)
///
/// @throw TypeError if the ValueType of @a tree is not floating-point.
template<typename TreeOrLeafManagerT>
void
signedFloodFill(TreeOrLeafManagerT& tree, bool threaded = true,
size_t grainSize = 1, Index minLevel = 0);
/// @brief Set the values of all inactive voxels and tiles of a narrow-band
/// level set from the signs of the active voxels, setting exterior values to
/// @a outsideWidth and interior values to @a insideWidth. Set the background value
/// of this tree to @a outsideWidth.
///
/// @warning This method should only be used on closed, narrow-band level sets.
///
/// @note If a LeafManager is used the cached leaf nodes are reused
/// resulting in slightly better overall performance.
///
/// @param tree Tree or LeafManager that will be flood filled
/// @param outsideWidth the width of the outside of the narrow band
/// @param insideWidth the width of the inside of the narrow band
/// @param threaded enable or disable threading (threading is enabled by default)
/// @param grainSize used to control the threading granularity (default is 1)
/// @param minLevel Specify the lowest tree level to process (leafnode level = 0)
///
/// @throw TypeError if the ValueType of @a tree is not floating-point.
template<typename TreeOrLeafManagerT>
void
signedFloodFillWithValues(
TreeOrLeafManagerT& tree,
const typename TreeOrLeafManagerT::ValueType& outsideWidth,
const typename TreeOrLeafManagerT::ValueType& insideWidth,
bool threaded = true,
size_t grainSize = 1,
Index minLevel = 0);
////////////////////////// Implementation of SignedFloodFill ////////////////////////////
template<typename TreeOrLeafManagerT>
class SignedFloodFillOp
{
public:
using ValueT = typename TreeOrLeafManagerT::ValueType;
using RootT = typename TreeOrLeafManagerT::RootNodeType;
using LeafT = typename TreeOrLeafManagerT::LeafNodeType;
static_assert(std::is_signed<ValueT>::value,
"signed flood fill is supported only for signed value grids");
SignedFloodFillOp(const TreeOrLeafManagerT& tree, Index minLevel = 0)
: mOutside(ValueT(math::Abs(tree.background())))
, mInside(ValueT(math::negative(mOutside)))
, mMinLevel(minLevel)
{
}
SignedFloodFillOp(ValueT outsideValue, ValueT insideValue, Index minLevel = 0)
: mOutside(ValueT(math::Abs(outsideValue)))
, mInside(ValueT(math::negative(math::Abs(insideValue))))
, mMinLevel(minLevel)
{
}
// Nothing to do at the leaf node level
void operator()(LeafT& leaf) const
{
if (LeafT::LEVEL < mMinLevel) return;
if (!leaf.allocate()) return; // this assures that the buffer is allocated and in-memory
const typename LeafT::NodeMaskType& valueMask = leaf.getValueMask();
// WARNING: "Never do what you're about to see at home, we're what you call experts!"
typename LeafT::ValueType* buffer =
const_cast<typename LeafT::ValueType*>(&(leaf.getFirstValue()));
const Index first = valueMask.findFirstOn();
if (first < LeafT::SIZE) {
bool xInside = buffer[first]<0, yInside = xInside, zInside = xInside;
for (Index x = 0; x != (1 << LeafT::LOG2DIM); ++x) {
const Index x00 = x << (2 * LeafT::LOG2DIM);
if (valueMask.isOn(x00)) xInside = buffer[x00] < 0; // element(x, 0, 0)
yInside = xInside;
for (Index y = 0; y != (1 << LeafT::LOG2DIM); ++y) {
const Index xy0 = x00 + (y << LeafT::LOG2DIM);
if (valueMask.isOn(xy0)) yInside = buffer[xy0] < 0; // element(x, y, 0)
zInside = yInside;
for (Index z = 0; z != (1 << LeafT::LOG2DIM); ++z) {
const Index xyz = xy0 + z; // element(x, y, z)
if (valueMask.isOn(xyz)) {
zInside = buffer[xyz] < 0;
} else {
buffer[xyz] = zInside ? mInside : mOutside;
}
}
}
}
} else {// if no active voxels exist simply use the sign of the first value
leaf.fill(buffer[0] < 0 ? mInside : mOutside);
}
}
// Prune the child nodes of the internal nodes
template<typename NodeT>
void operator()(NodeT& node) const
{
if (NodeT::LEVEL < mMinLevel) return;
// We assume the child nodes have already been flood filled!
const typename NodeT::NodeMaskType& childMask = node.getChildMask();
// WARNING: "Never do what you're about to see at home, we're what you call experts!"
typename NodeT::UnionType* table = const_cast<typename NodeT::UnionType*>(node.getTable());
const Index first = childMask.findFirstOn();
if (first < NodeT::NUM_VALUES) {
bool xInside = table[first].getChild()->getFirstValue()<0;
bool yInside = xInside, zInside = xInside;
for (Index x = 0; x != (1 << NodeT::LOG2DIM); ++x) {
const int x00 = x << (2 * NodeT::LOG2DIM); // offset for block(x, 0, 0)
if (childMask.isOn(x00)) xInside = table[x00].getChild()->getLastValue()<0;
yInside = xInside;
for (Index y = 0; y != (1 << NodeT::LOG2DIM); ++y) {
const Index xy0 = x00 + (y << NodeT::LOG2DIM); // offset for block(x, y, 0)
if (childMask.isOn(xy0)) yInside = table[xy0].getChild()->getLastValue()<0;
zInside = yInside;
for (Index z = 0; z != (1 << NodeT::LOG2DIM); ++z) {
const Index xyz = xy0 + z; // offset for block(x, y, z)
if (childMask.isOn(xyz)) {
zInside = table[xyz].getChild()->getLastValue()<0;
} else {
table[xyz].setValue(zInside ? mInside : mOutside);
}
}
}
}
} else {//no child nodes exist simply use the sign of the first tile value.
const ValueT v = table[0].getValue()<0 ? mInside : mOutside;
for (Index i = 0; i < NodeT::NUM_VALUES; ++i) table[i].setValue(v);
}
}
// Prune the child nodes of the root node
void operator()(RootT& root) const
{
if (RootT::LEVEL < mMinLevel) return;
using ChildT = typename RootT::ChildNodeType;
// Insert the child nodes into a map sorted according to their origin
std::map<Coord, ChildT*> nodeKeys;
typename RootT::ChildOnIter it = root.beginChildOn();
for (; it; ++it) nodeKeys.insert(std::pair<Coord, ChildT*>(it.getCoord(), &(*it)));
static const Index DIM = RootT::ChildNodeType::DIM;
// We employ a simple z-scanline algorithm that inserts inactive tiles with
// the inside value if they are sandwiched between inside child nodes only!
typename std::map<Coord, ChildT*>::const_iterator b = nodeKeys.begin(), e = nodeKeys.end();
if ( b == e ) return;
for (typename std::map<Coord, ChildT*>::const_iterator a = b++; b != e; ++a, ++b) {
Coord d = b->first - a->first; // delta of neighboring coordinates
if (d[0]!=0 || d[1]!=0 || d[2]==Int32(DIM)) continue;// not same z-scanline or neighbors
const ValueT fill[] = { a->second->getLastValue(), b->second->getFirstValue() };
if (!(fill[0] < 0) || !(fill[1] < 0)) continue; // scanline isn't inside
Coord c = a->first + Coord(0u, 0u, DIM);
for (; c[2] != b->first[2]; c[2] += DIM) root.addTile(c, mInside, false);
}
root.setBackground(mOutside, /*updateChildNodes=*/false);
}
private:
const ValueT mOutside, mInside;
const Index mMinLevel;
};// SignedFloodFillOp
//{
/// @cond OPENVDB_DOCS_INTERNAL
template<typename TreeOrLeafManagerT>
inline
typename std::enable_if<std::is_signed<typename TreeOrLeafManagerT::ValueType>::value, void>::type
doSignedFloodFill(TreeOrLeafManagerT& tree,
typename TreeOrLeafManagerT::ValueType outsideValue,
typename TreeOrLeafManagerT::ValueType insideValue,
bool threaded,
size_t grainSize,
Index minLevel)
{
tree::NodeManager<TreeOrLeafManagerT> nodes(tree);
SignedFloodFillOp<TreeOrLeafManagerT> op(outsideValue, insideValue, minLevel);
nodes.foreachBottomUp(op, threaded, grainSize);
}
// Dummy (no-op) implementation for unsigned types
template <typename TreeOrLeafManagerT>
inline
typename std::enable_if<!std::is_signed<typename TreeOrLeafManagerT::ValueType>::value, void>::type
doSignedFloodFill(TreeOrLeafManagerT&,
const typename TreeOrLeafManagerT::ValueType&,
const typename TreeOrLeafManagerT::ValueType&,
bool,
size_t,
Index)
{
OPENVDB_THROW(TypeError,
"signedFloodFill is supported only for signed value grids");
}
/// @endcond
//}
// If the narrow-band is symmetric and unchanged
template <typename TreeOrLeafManagerT>
void
signedFloodFillWithValues(
TreeOrLeafManagerT& tree,
const typename TreeOrLeafManagerT::ValueType& outsideValue,
const typename TreeOrLeafManagerT::ValueType& insideValue,
bool threaded,
size_t grainSize,
Index minLevel)
{
doSignedFloodFill(tree, outsideValue, insideValue, threaded, grainSize, minLevel);
}
template <typename TreeOrLeafManagerT>
void
signedFloodFill(TreeOrLeafManagerT& tree,
bool threaded,
size_t grainSize,
Index minLevel)
{
const typename TreeOrLeafManagerT::ValueType v = tree.root().background();
doSignedFloodFill(tree, v, math::negative(v), threaded, grainSize, minLevel);
}
////////////////////////////////////////
// Explicit Template Instantiation
#ifdef OPENVDB_USE_EXPLICIT_INSTANTIATION
#ifdef OPENVDB_INSTANTIATE_SIGNEDFLOODFILL
#include <openvdb/util/ExplicitInstantiation.h>
#endif
#define _FUNCTION(TreeT) \
void signedFloodFill(TreeT&, bool, size_t, Index)
OPENVDB_REAL_TREE_INSTANTIATE(_FUNCTION)
#undef _FUNCTION
#define _FUNCTION(TreeT) \
void signedFloodFill(tree::LeafManager<TreeT>&, bool, size_t, Index)
OPENVDB_REAL_TREE_INSTANTIATE(_FUNCTION)
#undef _FUNCTION
#define _FUNCTION(TreeT) \
void signedFloodFillWithValues(TreeT&, const TreeT::ValueType&, const TreeT::ValueType&, bool, size_t, Index)
OPENVDB_REAL_TREE_INSTANTIATE(_FUNCTION)
#undef _FUNCTION
#define _FUNCTION(TreeT) \
void signedFloodFillWithValues(tree::LeafManager<TreeT>&, const TreeT::ValueType&, const TreeT::ValueType&, bool, size_t, Index)
OPENVDB_REAL_TREE_INSTANTIATE(_FUNCTION)
#undef _FUNCTION
#endif // OPENVDB_USE_EXPLICIT_INSTANTIATION
} // namespace tools
} // namespace OPENVDB_VERSION_NAME
} // namespace openvdb
#endif // OPENVDB_TOOLS_RESETBACKGROUND_HAS_BEEN_INCLUDED
ExplicitInstantiation.h
Math.h
General-purpose arithmetic and comparison routines, most of which accept arbitrary value types (or at...
openvdb::v10_0::TypeError
Definition Exceptions.h:64
openvdb::v10_0::math::Coord
Signed (x, y, z) 32-bit integer coordinates.
Definition Coord.h:25
openvdb::v10_0::tools::SignedFloodFillOp::SignedFloodFillOp
SignedFloodFillOp(const TreeOrLeafManagerT &tree, Index minLevel=0)
Definition SignedFloodFill.h:91
openvdb::v10_0::tools::SignedFloodFillOp::operator()
void operator()(LeafT &leaf) const
Definition SignedFloodFill.h:106
openvdb::v10_0::tools::SignedFloodFillOp::operator()
void operator()(NodeT &node) const
Definition SignedFloodFill.h:145
openvdb::v10_0::tools::SignedFloodFillOp::operator()
void operator()(RootT &root) const
Definition SignedFloodFill.h:182
openvdb::v10_0::tools::SignedFloodFillOp::ValueT
typename TreeOrLeafManagerT::ValueType ValueT
Definition SignedFloodFill.h:85
openvdb::v10_0::tools::SignedFloodFillOp::SignedFloodFillOp
SignedFloodFillOp(ValueT outsideValue, ValueT insideValue, Index minLevel=0)
Definition SignedFloodFill.h:98
openvdb::v10_0::tools::SignedFloodFillOp::LeafT
typename TreeOrLeafManagerT::LeafNodeType LeafT
Definition SignedFloodFill.h:87
openvdb::v10_0::tools::SignedFloodFillOp::RootT
typename TreeOrLeafManagerT::RootNodeType RootT
Definition SignedFloodFill.h:86
openvdb::v10_0::tree::NodeManager
To facilitate threading over the nodes of a tree, cache node pointers in linear arrays,...
Definition NodeManager.h:531
openvdb::v10_0::math
Definition Types.h:28
openvdb::v10_0::math::negative
T negative(const T &val)
Return the unary negation of the given value.
Definition Math.h:128
openvdb::v10_0::tools::signedFloodFillWithValues
void signedFloodFillWithValues(TreeOrLeafManagerT &tree, const typename TreeOrLeafManagerT::ValueType &outsideWidth, const typename TreeOrLeafManagerT::ValueType &insideWidth, bool threaded=true, size_t grainSize=1, Index minLevel=0)
Set the values of all inactive voxels and tiles of a narrow-band level set from the signs of the acti...
Definition SignedFloodFill.h:253
openvdb::v10_0::tools::Abs
MeshToVoxelEdgeData::EdgeData Abs(const MeshToVoxelEdgeData::EdgeData &x)
Definition MeshToVolume.h:3707
openvdb::v10_0::tools::signedFloodFill
void signedFloodFill(TreeOrLeafManagerT &tree, bool threaded=true, size_t grainSize=1, Index minLevel=0)
Set the values of all inactive voxels and tiles of a narrow-band level set from the signs of the acti...
Definition SignedFloodFill.h:267
openvdb::v10_0::tree
Definition PointDataGrid.h:169
openvdb::v10_0::Index
Index32 Index
Definition Types.h:54
openvdb::v10_0::Int32
int32_t Int32
Definition Types.h:56
openvdb
Definition Exceptions.h:13
OPENVDB_THROW
#define OPENVDB_THROW(exception, message)
Definition Exceptions.h:74
Types.h
NodeManager.h
NodeManager produces linear arrays of all tree nodes allowing for efficient threading and bottom-up p...
openvdb.h
OPENVDB_VERSION_NAME
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition version.h.in:121
OPENVDB_USE_VERSION_NAMESPACE
#define OPENVDB_USE_VERSION_NAMESPACE
Definition version.h.in:212
OPENVDB_REAL_TREE_INSTANTIATE
#define OPENVDB_REAL_TREE_INSTANTIATE(Function)
Definition version.h.in:157