Candidate.h

Go to the documentation of this file.

#ifndef CANDIDATE_HEADER
#define CANDIDATE_HEADER
#include <algorithm>
#include <limits>
 
#include "Octree.h"
#include "PrimitiveShape.h"
#include "ScoreComputer.h"
#include <MiscLib/NoShrinkVector.h>
#include <MiscLib/Random.h>
#include <MiscLib/RefCountPtr.h>
#include <MiscLib/RefCounted.h>
#include <MiscLib/Vector.h>
 
#ifndef DLL_LINKAGE
#define DLL_LINKAGE
#endif
 
class DLL_LINKAGE Candidate
{
public:
    Candidate();
    Candidate(PrimitiveShape* shape, size_t level);
 
    PrimitiveShape*
    Shape()
    {
        return m_shape;
    }
 
    void
    Shape(PrimitiveShape* shape)
    {
        m_shape = shape;
    }
 
    float
    LowerBound() const
    {
        return m_lowerBound;
    }
 
    float
    UpperBound() const
    {
        return m_upperBound;
    }
 
    MiscLib::RefCounted<MiscLib::Vector<size_t>>*
    Indices()
    {
        return m_indices;
    }
 
    void
    Indices(MiscLib::RefCounted<MiscLib::Vector<size_t>>* indices)
    {
        m_indices = indices;
    }
 
    size_t
    ComputedSubsets() const
    {
        return m_subset;
    }
 
    float
    ExpectedValue() const
    {
        return (m_lowerBound + m_upperBound) / 2.f;
    }
 
    void
    SetSubset(size_t subset)
    {
        m_subset = subset;
    }
 
    size_t
    Level() const
    {
        return m_level;
    }
 
    void Reset();
    template <class ScoreVisitorT>
    bool ImproveBounds(const MiscLib::Vector<ImmediateOctreeType*>& octrees,
                       const PointCloud& pc,
                       ScoreVisitorT& scoreVisitor,
                       size_t currentSize,
                       float bitmapEpsilon,
                       size_t maxSubset,
                       size_t minPoints = 500);
    template <class ScoreVisitorT>
    void RecomputeBounds(const MiscLib::Vector<ImmediateOctreeType*>& octrees,
                         const PointCloud& pc,
                         ScoreVisitorT& scoreVisitor,
                         size_t currentSize,
                         float epsilon,
                         float normalThresh,
                         float bitmapEpsilon);
    void Reindex(const MiscLib::Vector<int>& newIndices,
                 int minInvalidIndex,
                 size_t mergedSubsets,
                 const MiscLib::Vector<size_t>& subsetSizes,
                 const PointCloud& pc,
                 size_t currentSize,
                 float epsilon,
                 float normalThresh,
                 float bitmapEpsilon);
    void Reindex(const MiscLib::Vector<size_t>& reindex);
    template <class ScoreVisitorT>
    void GlobalScore(ScoreVisitorT& scoreVisitor, const IndexedOctreeType& oct);
    float WeightedScore(const PointCloud& pc, float epsilon, float normalThresh) const;
    void ConnectedComponent(const PointCloud& pc, float bitmapEpsilon, float* borderRatio = 0);
    template <class ScoreVisitorT>
    float GlobalWeightedScore(ScoreVisitorT& scoreVisitor,
                              const IndexedOctreeType& oct,
                              const PointCloud& pc,
                              float epsilon,
                              float normalThresh,
                              float bitmapEpsilon);
    inline bool operator<(const Candidate& c) const;
    inline bool operator>(const Candidate& c) const;
    inline bool operator<=(const Candidate& c) const;
    inline bool operator>=(const Candidate& c) const;
    inline void Clone(Candidate* c) const;
    bool
    IsEquivalent(const Candidate& c, const PointCloud& pc, float epsilon, float normalThresh) const;
 
    size_t
    Size() const
    {
        return m_indices->size();
    }
 
private:
    inline void GetBounds(size_t sampledPoints, size_t totalPoints);
    inline void Induct(double totalSize,
                       double sampleSize,
                       double totalCorrectSize,
                       float* lower,
                       float* upper) const;
    inline void Deduct(double totalSize,
                       double sampleSize,
                       double totalCorrectSize,
                       float* lower,
                       float* upper) const;
 
    void GetScore(const PointCloud& pc, float bitmapEpsilon, bool doFiltering);
    void GetScoreMaxCCSize(const PointCloud& pc, float bitmapEpsilon, bool doFiltering);
    void GetScoreMaxCCMinBorder(const PointCloud& pc, float bitmapEpsilon, bool doFiltering);
 
    float GetVariance(const PointCloud& pc);
    float GetPseudoVariance(const PointCloud& pc);
 
private:
    MiscLib::RefCountPtr<PrimitiveShape> m_shape;
    size_t m_subset;
    float m_lowerBound;
    float m_upperBound;
    MiscLib::RefCountPtr<MiscLib::RefCounted<MiscLib::Vector<size_t>>> m_indices;
    size_t m_level;
    bool m_hasConnectedComponent;
    size_t m_score;
};
 
bool
Candidate::operator<(const Candidate& c) const
{
    return ExpectedValue() < c.ExpectedValue();
}
 
bool
Candidate::operator>(const Candidate& c) const
{
    return ExpectedValue() > c.ExpectedValue();
}
 
bool
Candidate::operator<=(const Candidate& c) const
{
    return ExpectedValue() <= c.ExpectedValue();
}
 
bool
Candidate::operator>=(const Candidate& c) const
{
    return ExpectedValue() >= c.ExpectedValue();
}
 
void
Candidate::Clone(Candidate* c) const
{
    c->m_shape = m_shape->Clone();
    c->m_shape->Release();
    c->m_subset = m_subset;
    c->m_lowerBound = m_lowerBound;
    c->m_upperBound = m_upperBound;
    c->m_indices = new MiscLib::RefCounted<MiscLib::Vector<size_t>>(*m_indices);
    c->m_indices->Release();
    c->m_level = m_level;
    ;
    c->m_hasConnectedComponent = m_hasConnectedComponent;
    c->m_score = m_score;
}
 
void
Candidate::GetBounds(size_t sampledPoints, size_t totalPoints)
{
    Induct(
        (double)totalPoints, (double)sampledPoints, (double)m_score, &m_lowerBound, &m_upperBound);
    m_lowerBound = std::max(0.f, m_lowerBound);
}
 
void
Candidate::Induct(double totalSize,
                  double sampleSize,
                  double totalCorrectSize,
                  float* lower,
                  float* upper) const
{
    Deduct(-2.0 - sampleSize, -2.0 - totalSize, -1.0 - totalCorrectSize, lower, upper);
    *lower = -1.f - *lower;
    *upper = -1.f - *upper;
}
 
void
Candidate::Deduct(double totalSize,
                  double sampleSize,
                  double totalCorrectSize,
                  float* lower,
                  float* upper) const
{
    double nI = sampleSize * totalCorrectSize;
    double denom = nI * (totalSize - sampleSize) * (totalSize - totalCorrectSize);
    double frac = denom / (totalSize - 1);
    double dev = std::sqrt(frac);
    *lower = float((nI - dev) / totalSize); // 95% quantile
    *upper = float((nI + dev) / totalSize); // 95% quantile
}
 
template <class ScoreVisitorT>
bool
Candidate::ImproveBounds(const MiscLib::Vector<ImmediateOctreeType*>& octrees,
                         const PointCloud& pc,
                         ScoreVisitorT& scoreVisitor,
                         size_t currentSize,
                         float bitmapEpsilon,
                         size_t maxSubset,
                         size_t minPoints)
{
    if (m_subset >= maxSubset)
    {
        return false;
    }
    if (m_subset >= octrees.size())
    {
        return false;
    }
 
    size_t sampledPoints = 0;
    for (size_t i = 0; i < m_subset; ++i)
    {
        sampledPoints += octrees[i]->size();
    }
 
    size_t newlySampledPoints = 0;
    scoreVisitor.SetIndices(m_indices);
    do
    {
        scoreVisitor.SetOctree(*octrees[m_subset]);
        m_shape->Visit(&scoreVisitor);
        newlySampledPoints += octrees[m_subset]->size();
        sampledPoints += octrees[m_subset]->size();
        ++m_subset;
    } while (m_subset < octrees.size() && newlySampledPoints < minPoints);
 
    m_score = m_indices->size();
    GetBounds(sampledPoints, currentSize);
 
    // check if connected component is worthwhile
    if (m_subset == 1)
    {
        return true;
    }
    if (m_hasConnectedComponent ||
        (2.f * (m_upperBound - (m_lowerBound / .7f)) / (m_upperBound + (m_lowerBound / .7f))) < .3f)
    {
        if (!m_hasConnectedComponent && m_indices->size() < 2)
        {
            return true;
        }
        m_hasConnectedComponent = true;
        m_score = m_shape->ConnectedComponent(
            pc, (4 << ((octrees.size() - m_subset) / 2)) * bitmapEpsilon, m_indices, false);
        m_indices->resize(m_score);
        if (m_subset >= octrees.size())
        {
            GetScore(pc, bitmapEpsilon, true);
            m_upperBound = m_lowerBound = m_score;
            return true;
        }
        GetScore(pc, (2 << ((octrees.size() - m_subset) / 2)) * bitmapEpsilon, false);
 
        GetBounds(sampledPoints, currentSize);
    }
    return true;
}
 
template <class ScoreVisitorT>
void
Candidate::RecomputeBounds(const MiscLib::Vector<ImmediateOctreeType*>& octrees,
                           const PointCloud& pc,
                           ScoreVisitorT& scoreVisitor,
                           size_t currentSize,
                           float epsilon,
                           float normalThresh,
                           float bitmapEpsilon)
{
    // run over indices and check if still unassigned
    const MiscLib::Vector<int>& shapeIndex = scoreVisitor.GetShapeIndex();
    size_t indicesSize = m_indices->size();
    for (size_t i = 0; i < indicesSize;)
    {
        if (shapeIndex[(*m_indices)[i]] != -1)
        {
            --indicesSize;
            std::swap((*m_indices)[i], (*m_indices)[indicesSize]);
        }
        else
        {
            ++i;
        }
    }
 
    m_score = indicesSize;
 
    if (m_hasConnectedComponent)
    {
        if (m_indices->size() != indicesSize) // dirty!
        {
            if ((float)indicesSize / m_indices->size() > 0.95)
            {
                m_indices->resize(indicesSize);
 
                GetScore(pc,
                         m_subset >= octrees.size()
                             ? bitmapEpsilon
                             : (4 << ((octrees.size() - m_subset) / 2)) * bitmapEpsilon,
                         m_subset >= octrees.size());
 
                if (m_subset >= octrees.size())
                {
                    m_upperBound = m_lowerBound = (float)m_indices->size();
                    return;
                }
                // reevaluate bounds
            }
            else
            {
                m_subset = 0;
                m_hasConnectedComponent = false;
                m_indices->clear();
                m_score = 0;
                ImproveBounds(octrees, pc, scoreVisitor, currentSize, bitmapEpsilon, 1);
                return;
            }
        }
        else if (m_subset > octrees.size())
        {
            return;
        }
        // reevaluate bounds
    }
    else
    {
        m_indices->resize(indicesSize);
        m_score = m_indices->size();
    }
    size_t sampledPoints = 0, endi = std::min(m_subset, octrees.size());
    for (size_t i = 0; i < endi; ++i)
    {
        sampledPoints += octrees[i]->size();
    }
 
    GetBounds(sampledPoints, currentSize);
}
 
template <class ScoreVisitorT>
void
Candidate::GlobalScore(ScoreVisitorT& scoreVisitor, const IndexedOctreeType& oct)
{
    m_indices->clear();
    scoreVisitor.SetOctree(oct);
    scoreVisitor.SetIndices(m_indices);
    m_shape->Visit(&scoreVisitor);
    m_lowerBound = m_upperBound = (float)m_indices->size();
}
 
template <class ScoreVisitorT>
float
Candidate::GlobalWeightedScore(ScoreVisitorT& scoreVisitor,
                               const IndexedOctreeType& oct,
                               const PointCloud& pc,
                               float epsilon,
                               float normalThresh,
                               float bitmapEpsilon)
{
    GlobalScore(scoreVisitor, oct);
    ConnectedComponent(pc, bitmapEpsilon);
    return WeightedScore(pc, epsilon, normalThresh);
}
 
#endif