HGrid.cc

Go to the documentation of this file.

//Copyright (c) 2013-2014, The MercuryDPM Developers Team. All rights reserved.
//For the list of developers, see <http://www.MercuryDPM.org/Team>.
//
//Redistribution and use in source and binary forms, with or without
//modification, are permitted provided that the following conditions are met:
//  * Redistributions of source code must retain the above copyright
//    notice, this list of conditions and the following disclaimer.
//  * Redistributions in binary form must reproduce the above copyright
//    notice, this list of conditions and the following disclaimer in the
//    documentation and/or other materials provided with the distribution.
//  * Neither the name MercuryDPM nor the
//    names of its contributors may be used to endorse or promote products
//    derived from this software without specific prior written permission.
//
//THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
//ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
//WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
//DISCLAIMED. IN NO EVENT SHALL THE MERCURYDPM DEVELOPERS TEAM BE LIABLE FOR ANY
//DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
//(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
//LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
//ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
//(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
//SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

#include "HGrid.h"
#include "Logger.h"
#include "Particles/BaseParticle.h"
#include <bitset>

HGrid::HGrid()
{
    needsRebuilding_ = true;
    numberOfBuckets_ = 10;
    cellOverSizeRatio_ = 1.0;
    occupiedLevelsMask_ = 0;
    logger(DEBUG, "HGrid::HGrid() finished");
}

HGrid::HGrid(unsigned int num_buckets, double cellOverSizeRatio, std::vector<double>& cellSizes)
{
    needsRebuilding_ = false;
    numberOfBuckets_ = num_buckets;
    cellOverSizeRatio_ = cellOverSizeRatio;
    occupiedLevelsMask_ = 0;
    
    firstBaseParticleInBucket_.resize(numberOfBuckets_, nullptr);
    bucketIsChecked_.resize(numberOfBuckets_, false);

    //std::cout<<"Creating HGrid "<<cellSizes.size()<<" levels:"<<std::endl;
    for (unsigned int i = 0; i < cellSizes.size(); i++)
    {
        //std::cout<<"Level="<<i<<" size="<<cellSizes[i]<<std::endl;
        cellSizes_.push_back(cellSizes[i]);
        invCellSizes_.push_back(1.0 / cellSizes[i]);
    }
    logger(DEBUG, "HGrid::HGrid(unsigned int, double, vector<double>&) constructor finished.");
    /*  std::cout << "HGrid::HGrid(" << num_buckets << ", " << cellOverSizeRatio << ", [";
        for (auto p: cellSizes) std::cout << p << " "; 
        std::cout << "]) finished" << std::endl;*/
}

HGrid::~HGrid()
{
    logger(DEBUG, "HGrid::~HGrid() destructor finished");
}

void HGrid::insertParticleToHgrid(BaseParticle *obj)
{
    if(!needsRebuilding_)
    {
        // Find lowest level where object fully fits inside cell, taking cellOverSizeRatio_ into account
        Mdouble diameter = obj->getInteractionRadius() * 2.0;
        unsigned int level = 0;
        while (level < cellSizes_.size() && cellSizes_[level] <= diameter * cellOverSizeRatio_)
        {
            level++;
        }

        if (level >= cellSizes_.size())
        {
            logger(WARN, "WARNING: object (id = %, index = %) is larger (d = %, cellOverSizeRatio = %) than largest grid cell (%) allows.", obj->getId(), obj->getIndex(), diameter, cellOverSizeRatio_, cellSizes_.back());
            needsRebuilding_ = true;
        }

        obj->setHGridLevel(level);
        // indicate level is in use - not levels with no particles no collision detection is performed
        this->occupiedLevelsMask_ |= (1 << level);
    }
    else
    {
        logger(WARN, "WARNING: the HGrid needs to be rebuild before insertParticleToHgrid may be called!");
    }
}

unsigned int HGrid::computeHashBucketIndex(int x, int y, int z, unsigned int l) const
{
    const unsigned int h1 = 0x8da6b343u; // Large multiplicative constants;
    const unsigned int h2 = 0xd8163841u; // here arbitrarily chosen primes
    const unsigned int h3 = 0xcb1ab31fu;
    const unsigned int h4 = 0x165667b1u;
    
    unsigned long int n = h1 * x + h2 * y + h3 * z + h4 * l;
    n = n % numberOfBuckets_;
    
    return static_cast<unsigned int>(n);
}

unsigned int HGrid::computeHashBucketIndex(int x, int y, unsigned int l) const
{
    const unsigned int h1 = 0x8da6b343u; // Large multiplicative constants;
    const unsigned int h2 = 0xd8163841u; // here arbitrarily chosen primes
    const unsigned int h4 = 0x165667b1u;
    
    unsigned long int n = h1 * x + h2 * y + h4 * l;
    n = n % numberOfBuckets_;
    
    return static_cast<unsigned int>(n);
}

unsigned int HGrid::getNumberOfBuckets() const
{
    return numberOfBuckets_;
}

void HGrid::clearBucketIsChecked()
{
    for (std::vector<bool>::iterator it = bucketIsChecked_.begin(); it != bucketIsChecked_.end(); ++it)
    {
        (*it) = false;
    }
}

const std::vector<double>& HGrid::getCellSizes() const
{
    return cellSizes_;
}

const std::vector<double>& HGrid::getInvCellSizes() const
{
    return invCellSizes_;
}

void HGrid::clearFirstBaseParticleInBucket()
{
    for (BaseParticle*& p : firstBaseParticleInBucket_)
    {
        p = nullptr;
    }
}

bool HGrid::getBucketIsChecked(unsigned int i) const
{
    return bucketIsChecked_[i];
}

const BaseParticle* HGrid::getFirstBaseParticleInBucket(unsigned int i) const
{
    return firstBaseParticleInBucket_[i];
}

BaseParticle* HGrid::getFirstBaseParticleInBucket(unsigned int i)
{
    return firstBaseParticleInBucket_[i];
}

void HGrid::setBucketIsChecked(unsigned int i)
{
    bucketIsChecked_[i] = true;
}

unsigned int HGrid::getNumberOfLevels() const
{
    return cellSizes_.size();
}

void HGrid::setFirstBaseParticleInBucket(unsigned int i, BaseParticle* p)
{
    firstBaseParticleInBucket_[i] = p;
}

double HGrid::getCellSize(unsigned int i) const
{
    return cellSizes_[i];
}

double HGrid::getInvCellSize(unsigned int i) const
{
    return invCellSizes_[i];
}

bool HGrid::getNeedsRebuilding() const
{
    return needsRebuilding_;
}

Mdouble HGrid::getCellOverSizeRatio() const
{
    return cellOverSizeRatio_;
}

int HGrid::getOccupiedLevelsMask() const
{
    return occupiedLevelsMask_;
}

void HGrid::info() const
{
    //std::cout << "  needsRebuilding " << std::boolalpha << needsRebuilding_ << std::endl; 
    logger(INFO,"  numberOfBuckets %", numberOfBuckets_);
    logger(INFO, "  cellOverSizeRatio %", cellOverSizeRatio_);
    //std::cout << "  occupiedLevelsMask " << std::bitset<8>(occupiedLevelsMask_) << std::endl; 
    logger(INFO, "  cellSizes");
    for (auto p: cellSizes_)
    {
        std::cout << " " << p;
    } std::cout << std::endl;
    // std::cout << "std::vector<double> invCellSizes_[" << invCellSizes_.size() << "]="; 
    // for (auto p: invCellSizes_) std::cout << p << " "; 
    // std::cout << std::endl; 
    // std::cout << "std::vector<BaseParticle> firstBaseParticleInBucket_[" << firstBaseParticleInBucket_.size() << "]=... (not shown)"; 
    // //for (auto p: firstBaseParticleInBucket_) std::cout << p << " "; 
    // std::cout << std::endl; 
    // std::cout << "std::vector<bool> bucketIsChecked_[" << bucketIsChecked_.size() << "]=... (not shown)"; 
    // //for (auto p: bucketIsChecked_) std::cout << p << " "; 
    // std::cout << std::endl; 
}