9 template <
typename entity_t,
typename value_t,
size_t DIM>
15 m_center((vmin + vmax) / 2.),
17 m_iwidth(1 / m_width) {}
19 template <
typename entity_t,
typename value_t,
size_t DIM>
21 const entity_t* entity,
const VertexType& center,
const Size& size)
23 m_vmin(center - size.
get() * 0.5),
24 m_vmax(center + size.
get() * 0.5),
27 m_iwidth(1 / m_width) {}
29 template <
typename entity_t,
typename value_t,
size_t DIM>
33 assert(boxes.size() > 1);
35 for (
size_t i = 0; i < boxes.size(); i++) {
36 if (i < boxes.size() - 1) {
38 boxes[i]->setSkip(boxes[i + 1]);
42 boxes[i]->setSkip(
nullptr);
57 template <
typename entity_t,
typename value_t,
size_t DIM>
63 assert(boxes.size() > 1);
67 vertex_array_type::Constant(std::numeric_limits<value_type>::lowest()));
71 for (
size_t i = 0; i < boxes.size(); i++) {
72 vmin = vmin.min(boxes[i]->
min().array());
73 vmax = vmax.max(boxes[i]->
max().array());
82 template <
typename entity_t,
typename value_t,
size_t DIM>
88 assert(boxes.size() > 1);
89 std::vector<const self_t*> box_ptrs;
90 box_ptrs.reserve(boxes.size());
91 std::transform(boxes.begin(), boxes.end(), std::back_inserter(box_ptrs),
92 [](
const auto*
box) {
return box; });
93 return wrap(box_ptrs, envelope);
96 template <
typename entity_t,
typename value_t,
size_t DIM>
102 assert(boxes.size() > 1);
103 std::vector<const self_t*> box_ptrs;
104 box_ptrs.reserve(boxes.size());
105 std::transform(boxes.begin(), boxes.end(), std::back_inserter(box_ptrs),
106 [](
auto&
box) {
return &
box; });
107 return wrap(box_ptrs, envelope);
110 template <
typename entity_t,
typename value_t,
size_t DIM>
114 return t.minCoeff() >= 0 && t.maxCoeff() < 1;
117 template <
typename entity_t,
typename value_t,
size_t DIM>
143 return tmin < tmax && tmax > 0.0;
146 template <
typename entity_t,
typename value_t,
size_t DIM>
147 template <
size_t s
ides>
150 const auto& normals = fr.
normals();
163 for (
size_t i = 0; i < sides + 1; i++) {
168 p_vtx = (normal.array() < 0).
template cast<value_type>() * fr_vmin +
169 (normal.array() >= 0).
template cast<value_type>() * fr_vmax;
174 if (p_vtx.dot(normal) < 0) {
185 template <
typename entity_t,
typename value_t,
size_t DIM>
191 if (m_right_child !=
nullptr) {
192 m_right_child->setSkip(skip);
196 template <
typename entity_t,
typename value_t,
size_t DIM>
202 template <
typename entity_t,
typename value_t,
size_t DIM>
208 template <
typename entity_t,
typename value_t,
size_t DIM>
210 return m_entity !=
nullptr;
213 template <
typename entity_t,
typename value_t,
size_t DIM>
219 template <
typename entity_t,
typename value_t,
size_t DIM>
221 const entity_t* entity) {
225 template <
typename entity_t,
typename value_t,
size_t DIM>
231 template <
typename entity_t,
typename value_t,
size_t DIM>
237 template <
typename entity_t,
typename value_t,
size_t DIM>
243 template <
typename entity_t,
typename value_t,
size_t DIM>
245 std::ostream& os)
const {
248 for (
size_t i = 0; i < DIM; i++) {
256 for (
size_t i = 0; i < DIM; i++) {
265 for (
size_t i = 0; i < DIM; i++) {
277 template <
typename entity_t,
typename value_t,
size_t DIM>
278 template <
size_t D, std::enable_if_t<D == 3,
int>>
287 std::array<VertexType, 8> vertices({{
288 {m_vmin.x(), m_vmin.y(), m_vmin.z()},
289 {m_vmin.x(), m_vmax.y(), m_vmin.z()},
290 {m_vmax.x(), m_vmax.y(), m_vmin.z()},
291 {m_vmax.x(), m_vmin.y(), m_vmin.z()},
292 {m_vmin.x(), m_vmin.y(), m_vmax.z()},
293 {m_vmin.x(), m_vmax.y(), m_vmax.z()},
294 {m_vmax.x(), m_vmax.y(), m_vmax.z()},
295 {m_vmax.x(), m_vmin.y(), m_vmax.z()},
301 for (
size_t i = 1; i < 8; i++) {
303 vmin = vmin.cwiseMin(vtx);
304 vmax = vmax.cwiseMax(vtx);
310 template <
typename entity_t,
typename value_t,
size_t DIM>
311 template <
size_t D, std::enable_if_t<D == 2,
int>>
316 const transform_type& trf)
const {
320 std::array<VertexType, 4> vertices({{{m_vmin.x(), m_vmin.y()},
321 {m_vmin.x(), m_vmax.y()},
322 {m_vmax.x(), m_vmax.y()},
323 {m_vmax.x(), m_vmin.y()}}});
325 VertexType vmin = trf * vertices[0];
326 VertexType vmax = trf * vertices[0];
328 for (
size_t i = 1; i < 4; i++) {
329 const VertexType vtx = trf * vertices[i];
330 vmin = vmin.cwiseMin(vtx);
331 vmax = vmax.cwiseMax(vtx);
337 template <
typename entity_t,
typename value_t,
size_t DIM>
340 std::tie(m_vmin, m_vmax) = transformVertices(trf);
343 template <
typename entity_t,
typename value_t,
size_t DIM>
348 std::tie(vmin, vmax) = transformVertices(trf);
349 return self_t(m_entity, vmin, vmax);
352 template <
typename entity_t,
typename value_t,
size_t DIM>
353 template <
size_t D, std::enable_if_t<D == 3,
int>>
357 static_assert(DIM == 3,
"PLY output only supported in 3D");
364 helper.
face(std::vector<VertexType>({trf *
a, trf *
b, trf *
c, trf *
d}),
368 write({vmin.x(), vmin.y(), vmin.z()}, {vmin.x(), vmax.y(), vmin.z()},
369 {vmin.x(), vmax.y(), vmax.z()}, {vmin.x(), vmin.y(), vmax.z()});
371 write({vmax.x(), vmin.y(), vmin.z()}, {vmax.x(), vmax.y(), vmin.z()},
372 {vmax.x(), vmax.y(), vmax.z()}, {vmax.x(), vmin.y(), vmax.z()});
374 write({vmin.x(), vmin.y(), vmin.z()}, {vmax.x(), vmin.y(), vmin.z()},
375 {vmax.x(), vmin.y(), vmax.z()}, {vmin.x(), vmin.y(), vmax.z()});
377 write({vmin.x(), vmax.y(), vmin.z()}, {vmax.x(), vmax.y(), vmin.z()},
378 {vmax.x(), vmax.y(), vmax.z()}, {vmin.x(), vmax.y(), vmax.z()});
380 write({vmin.x(), vmin.y(), vmin.z()}, {vmax.x(), vmin.y(), vmin.z()},
381 {vmax.x(), vmax.y(), vmin.z()}, {vmin.x(), vmax.y(), vmin.z()});
383 write({vmin.x(), vmin.y(), vmax.z()}, {vmax.x(), vmin.y(), vmax.z()},
384 {vmax.x(), vmax.y(), vmax.z()}, {vmin.x(), vmax.y(), vmax.z()});
387 template <
typename entity_t,
typename value_t,
size_t DIM>
388 template <
size_t D, std::enable_if_t<D == 2,
int>>
391 std::string label, std::string fillcolor)
const {
392 static_assert(DIM == 2,
"SVG is only supported in 2D");
396 using transform_t = Eigen::Transform<value_t, DIM, Eigen::Affine>;
398 transform_t trf = transform_t::Identity();
400 trf = trf * Eigen::Scaling(
VertexType(1, -1));
406 os <<
"cx=\"" << p.x() <<
"\" cy=\"" << p.y() <<
"\" r=\"" <<
r <<
"\"";
407 os <<
" fill=\"" << color <<
"\"";
414 VertexType center = trf * center_ - size * 0.5;
417 os <<
"x=\"" << center.x() <<
"\" y=\"" << center.y() <<
"\" ";
418 os <<
"width=\"" << size.x() <<
"\" height=\"" << size.y() <<
"\"";
419 os <<
" fill=\"" << color <<
"\"";
423 auto draw_text = [&](
const VertexType& center_, std::string text,
424 std::string
color,
size_t size) {
426 os <<
"<text dominant-baseline=\"middle\" text-anchor=\"middle\" ";
427 os <<
"fill=\"" << color <<
"\" font-size=\"" << size <<
"\" ";
428 os <<
"x=\"" << center.x() <<
"\" y=\"" << center.y() <<
"\">";
429 os << text <<
"</text>\n";
432 draw_rect(m_center, m_width, fillcolor);
433 draw_point(m_vmin,
"black", 2);
434 draw_point(m_vmax,
"black", 2);
435 draw_text(m_center, label,
"white", 10);
440 template <
typename box_t>
443 typename box_t::vertex_array_type envelope,
444 const std::vector<box_t*>& lprims,
size_t depth) {
445 using VertexType =
typename box_t::VertexType;
447 assert(lprims.size() > 0);
448 if (lprims.size() == 1) {
450 return lprims.front();
453 if (depth >= max_depth) {
455 auto bb = std::make_unique<box_t>(lprims, envelope);
456 store.push_back(std::move(
bb));
457 return store.back().get();
460 std::array<std::vector<box_t*>, 8> octants;
462 VertexType vmin, vmax;
463 std::tie(vmin, vmax) = box_t::wrap(lprims);
464 VertexType glob_ctr = (vmin + vmax) / 2.;
466 for (
auto*
box : lprims) {
467 VertexType ctr =
box->center() - glob_ctr;
468 if (ctr.x() < 0 && ctr.y() < 0 && ctr.z() < 0) {
469 octants[0].push_back(
box);
472 if (ctr.x() > 0 && ctr.y() < 0 && ctr.z() < 0) {
473 octants[1].push_back(
box);
476 if (ctr.x() < 0 && ctr.y() > 0 && ctr.z() < 0) {
477 octants[2].push_back(
box);
480 if (ctr.x() > 0 && ctr.y() > 0 && ctr.z() < 0) {
481 octants[3].push_back(
box);
485 if (ctr.x() < 0 && ctr.y() < 0 && ctr.z() > 0) {
486 octants[4].push_back(
box);
489 if (ctr.x() > 0 && ctr.y() < 0 && ctr.z() > 0) {
490 octants[5].push_back(
box);
493 if (ctr.x() < 0 && ctr.y() > 0 && ctr.z() > 0) {
494 octants[6].push_back(
box);
497 if (ctr.x() > 0 && ctr.y() > 0 && ctr.z() > 0) {
498 octants[7].push_back(
box);
503 octants[0].push_back(
box);
506 std::vector<box_t*> sub_octs;
507 for (
const auto& sub_prims : octants) {
508 if (sub_prims.size() <= 8) {
509 if (sub_prims.empty()) {
511 }
else if (sub_prims.size() == 1) {
512 sub_octs.push_back(sub_prims.front());
514 store.push_back(std::make_unique<box_t>(sub_prims, envelope));
515 sub_octs.push_back(store.back().get());
520 octree_inner(store, max_depth, envelope, sub_prims, depth + 1));
524 if (sub_octs.size() == 1) {
525 return sub_octs.front();
528 auto bb = std::make_unique<box_t>(sub_octs, envelope);
529 store.push_back(std::move(
bb));
530 return store.back().get();
533 template <
typename box_t>
535 const std::vector<box_t*>& prims,
size_t max_depth,
536 typename box_t::value_type envelope1) {
537 static_assert(
box_t::dim == 3,
"Octree can only be created in 3D");
539 using vertex_array_type =
typename box_t::vertex_array_type;
541 vertex_array_type envelope(vertex_array_type::Constant(envelope1));
543 box_t* top =
octree_inner(store, max_depth, envelope, prims, 0);
547 template <
typename T,
typename U,
size_t V>