enum Coverage
{
NO_COVERAGE,
+ UNCERTAIN_COVERAGE,
PARTIAL_COVERAGE,
FULL_COVERAGE
};
const LinAl::Vector<T, D> &min_pt = cell.bounding_box.get_minimum_point();
const LinAl::Vector<T, D> &max_pt = cell.bounding_box.get_maximum_point();
+
+ // Skip cells that are already fully inside the established bounds.
+ bool internal = true;
+ for(unsigned i=0; (i<D && internal); ++i)
+ internal = (min_pt[i]>=tight_min_pt[i] && max_pt[i]<=tight_max_pt[i]);
+ if(internal)
+ {
+ queue.pop_front();
+ continue;
+ }
+
LinAl::Vector<T, D> center = (min_pt+max_pt)/T(2);
// Bisect each dimension.
child.coverage = get_coverage(child.bounding_box);
if(child.coverage==FULL_COVERAGE || (child.level==detail && child.coverage!=NO_COVERAGE))
{
- /* Adjust the bounds when we are certain that it's covered by at
- least part of the shape. Also adjust for uncertain results if
- we're on the last level. */
+ /* Immediately merge cells with full coverage. Also merge cells
+ at the last level. */
for(unsigned j=0; j<D; ++j)
{
tight_min_pt[j] = std::min(tight_min_pt[j], child_min_pt[j]);
}
}
else if(child.coverage==PARTIAL_COVERAGE)
+ {
+ /* Merge cells with confirmed partial coverage so the cell is
+ left just outside the bounding box. */
+ for(unsigned j=0; j<D; ++j)
+ {
+ tight_min_pt[j] = std::min(tight_min_pt[j], child_max_pt[j]);
+ tight_max_pt[j] = std::max(tight_max_pt[j], child_min_pt[j]);
+ }
+ }
+
+ if(child.level<detail && child.coverage!=NO_COVERAGE && child.coverage!=FULL_COVERAGE)
queue.push_back(child);
}