implements spatial hashing for the search of particle neighbours More...

#include <Neighbour.h>

Public Member Functions
	Neighbour (const int _numParticles, const float _smoothingLength)
	ctor
	~Neighbour ()
	dtor
void	reInitialise (const int _numParticles, const float _smoothingLength)
	reinitialise the spatial structure
void	refreshHashmap (std::vector< FluidParticle > &_particleList)
	refresh the hash map at each iteration
void	clearHashmap ()
	clear the hash map
std::vector< FluidParticle >	determineNeighbours (const ngl::Vector _centerPosition)
	return neighbours of a particle
void	setCellSize (const ngl::Real _size)
	set the cell size of the spatial structure
Private Member Functions
int	modulus (const int _a, const int _b)
	calculate the modulus of 2 numbers
int	getNextPrimeNumber (const int _start)
	return the next prime number
std::vector< int >	discretize (const ngl::Vector _position)
	discretise an array of vectors into an array of integers
int	hashPosition (const ngl::Vector _position)
	hash a position to a hash key
void	getCellNeighbours (const ngl::Vector _centerPosition, const bool _checkWithinSmoothingLength, std::vector< FluidParticle > &o_neighbourList)
	determine neighbours of a particle, given its position
bool	isParticleAlreadyInList (const int _testId, std::vector< FluidParticle > &_neighbourList)
	check if a neighbour is a duplicate
Private Attributes
hashmap	m_hashMap
	the spatial hash map
float	m_cellSize
	the cell size used for spatial calculations
int	m_mapSize
	the map size
int	m_largePrime1
	large prime number 1
int	m_largePrime2
	large prime number 2
int	m_largePrime3
	large prime number 3
int	m_initialNeighbourListSize
	reserved space size for neighbours

Detailed Description

implements spatial hashing for the search of particle neighbours

Definition at line 21 of file Neighbour.h.

Constructor & Destructor Documentation

Neighbour::Neighbour	(	const int	_numParticles,
		const float	_smoothingLength
	)

ctor

Parameters:

[in]	_numParticles	the fluid particle count
[in]	_smoothingLength	the smoothing length

Definition at line 10 of file Neighbour.cpp.

{
    //initialise large prime numbers
    m_largePrime1 = 73856093;
    m_largePrime2 = 19349663;
    m_largePrime3 = 83492791;

    //initialise neighbour list
    m_initialNeighbourListSize = 50;

    //initialise hash params
    reInitialise(_numParticles, _smoothingLength);
}

Neighbour::~Neighbour ( )

dtor

Definition at line 27 of file Neighbour.cpp.

{
    //clean up
    std::cout << "Neighbour Cleanup" << std::endl;
}

Member Function Documentation

void Neighbour::clearHashmap ( )

clear the hash map

Definition at line 162 of file Neighbour.cpp.

References m_hashMap.

{
    //clears hashmap
    m_hashMap.clear();
}

std::vector< FluidParticle > Neighbour::determineNeighbours ( const ngl::Vector _centerPosition )

return neighbours of a particle

Parameters:

[in] _centerPosition the particle's position

Definition at line 231 of file Neighbour.cpp.

References discretize(), getCellNeighbours(), and m_cellSize.

{
    //initialise temp neighbour lists
    std::vector<FluidParticle> neighbourList;
    //neighbourList.reserve(m_initialNeighbourListSize);

    std::vector<FluidParticle> neighbourTempList;
    //neighbourTempList.reserve(m_initialNeighbourListSize);

    //first, get neighbours @ centerposition
    getCellNeighbours(_centerPosition, false, neighbourTempList);

    //then, get neighbours from bounding box [centerPos - cellSize, centerPos + cellSize]
    ngl::Vector limit(m_cellSize, m_cellSize, m_cellSize);
    std::vector<int> discreteMinBounds = discretize(_centerPosition - limit);
    std::vector<int> discreteMaxBounds = discretize(_centerPosition + limit);

    //loop from minBound to maxBound and find neighbours in hashmap
    ngl::Real sampleStep = 0.85;
    for (ngl::Real x = discreteMinBounds[0]; x < discreteMaxBounds[0]; x += sampleStep)
    {
        for (ngl::Real y = discreteMinBounds[1]; y < discreteMaxBounds[1]; y += sampleStep)
        {
            for (ngl::Real z = discreteMinBounds[2]; z < discreteMaxBounds[2]; z += sampleStep)
            {
                //fill in neighbour list with neighbours @ test position(x,y,z)
                getCellNeighbours(ngl::Vector(x, y, z), true, neighbourTempList);
            }
        }
    }

    //do a final distance check to ensure neighbours are within smoothing length
    for (int i = 0; i < neighbourTempList.size(); ++i)
    {
        //get separation distance between centerposition and neighbour position
        ngl::Real distance = (_centerPosition - neighbourTempList[i].getPosition()).length();

        //add to final list only if distance is within smoothing length (cell size)
        if (distance < m_cellSize) neighbourList.push_back(neighbourTempList[i]);
    }

    //return final list
    return neighbourList;
}

Here is the call graph for this function:

std::vector< int > Neighbour::discretize ( const ngl::Vector _position ) [private]

discretise an array of vectors into an array of integers

Parameters:

[in] _position the vector position to discretise

Definition at line 124 of file Neighbour.cpp.

References m_cellSize.

{
    std::vector<int> pos;
    pos.reserve(3);

    pos.push_back(floor(_position.m_x / m_cellSize));
    pos.push_back(floor(_position.m_y / m_cellSize));
    pos.push_back(floor(_position.m_z / m_cellSize));

    return pos;
}

Here is the caller graph for this function:

void Neighbour::getCellNeighbours	(	const ngl::Vector	_centerPosition,
		const bool	_checkWithinSmoothingLength,
		std::vector< FluidParticle > &	o_neighbourList
	)		`[private]`

determine neighbours of a particle, given its position

Parameters:

[in]	_centerPosition	the position of the particle
[in]	_checkWithinSmoothingLength	flag to determine whether only neighbours within the smoothing length are added
[out]	o_neighbourList	stores the list neighbours

Definition at line 191 of file Neighbour.cpp.

References Particle::getId(), and Particle::getPosition().

{
    //hash position
    int hashKey = hashPosition(_centerPosition);

    //get particles of cell[hashkey] from hash map
    std::pair<hashmap::iterator, hashmap::iterator> neighbourCandidateList = m_hashMap.equal_range(hashKey);

    //loop over neighbour list
    for (hashmap::iterator candidate = neighbourCandidateList.first; candidate != neighbourCandidateList.second; candidate++)
    {
        //get neighbour particle
        FluidParticle neighbourCandidate = (*candidate).second;

        //consider only non-duplicate candidates
        if (!isParticleAlreadyInList(neighbourCandidate.getId(), o_neighbourList))
        {
            //assume neighbour is valid
            bool isValidToAdd = true;

            //filter only neighbours within smoothing length if check is enabled
            if (_checkWithinSmoothingLength)
            {
                //get separation distance between centerposition and neighbour position
                ngl::Real distance = (_centerPosition - neighbourCandidate.getPosition()).length();

                //check if distance is within smoothing length (cell size)
                if (distance > m_cellSize) isValidToAdd = false;
            }

            //add neighbour particle to neighbour list if valid
            if (isValidToAdd) o_neighbourList.push_back(neighbourCandidate);
        }
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

int Neighbour::getNextPrimeNumber ( const int _start ) [private]

return the next prime number

Parameters:

[in] _start the start number from which to find the next prime number

Definition at line 59 of file Neighbour.cpp.

{
    int i = _start;

    bool isPrimeNumberFound = true;
    bool isNextPrimeNumberFound = false;

    //Get Square root of number and iterate, start from 2
    int check = (int)sqrt((double)i);
    for (int j = 2; j <= check; j++)
    {
        if (i % j == 0)
        {
            isPrimeNumberFound = false;
            break;
        }
    }
    if (isPrimeNumberFound)
    {
        //i itself is the next prime number
        return i;
    }
    else
    {
        //i is not a prime number -> must search next one

        i++;
        isPrimeNumberFound = true;

        // Increment current number to find next prime number
        while (isNextPrimeNumberFound == false)
        {
            check = (int)sqrt((double)(i));

            for (int j = 2; j <= check; j++)
            {
                if (i % j == 0)
                {
                    isPrimeNumberFound = false;
                    break;
                }
            }

            if (isPrimeNumberFound)
                isNextPrimeNumberFound = true;
            else
            {
                i++;
                isPrimeNumberFound = true;
            }
        }

        if (isNextPrimeNumberFound)
        {
            //i is the next prime number

            return i;
        }
    }

    //eventually, nothing found?
    return _start;
}

int Neighbour::hashPosition ( const ngl::Vector _position ) [private]

hash a position to a hash key

Parameters:

[in] _position the position to hash

Definition at line 136 of file Neighbour.cpp.

References discretize(), m_largePrime1, m_largePrime2, m_largePrime3, m_mapSize, and modulus().

{
    //discretize position to array of int
    std::vector<int> discretePosition = discretize(_position);

    //calculate hash key
    int key = modulus((discretePosition[0] * m_largePrime1) ^ (discretePosition[1] * m_largePrime2) ^ (discretePosition[2] * m_largePrime3), m_mapSize);

    return key;
}

Here is the call graph for this function:

Here is the caller graph for this function:

bool Neighbour::isParticleAlreadyInList	(	const int	_testId,
		std::vector< FluidParticle > &	_neighbourList
	)		`[private]`

check if a neighbour is a duplicate

Parameters:

[in]	_testId	the id of the neighbour to check in the list
[in]	_neighbourList	the list of neighbour that will be used for the duplicate check

Definition at line 169 of file Neighbour.cpp.

{
    //assume not found
    bool found = false;

    //loop through the temporary neighbour list
    for (int i = 0; i < _neighbourList.size(); i++)
    {
        if (_neighbourList[i].getId() == _testId)
        {
            found = true;
            break;
        }
    }

    return found;
}

int Neighbour::modulus	(	const int	_a,
		const int	_b
	)		`[private]`

calculate the modulus of 2 numbers

Parameters:

[in]	_a	the first number
[in]	_b	the second number

Definition at line 46 of file Neighbour.cpp.

{
    //perform huge integer modulus

    //issue of negative modulus : http://mathforum.org/library/drmath/view/52343.html
    //solved at stackoverflow : http://stackoverflow.com/questions/1082917/mod-of-negative-number-is-melting-my-brain

    //adapted from StackOverflow
    int modulus = _a % _b;
    return modulus < 0 ? modulus + _b : modulus;
}

Here is the caller graph for this function:

void Neighbour::refreshHashmap ( std::vector< FluidParticle > & _particleList )

refresh the hash map at each iteration

Parameters:

[in] _particleList the fluid particles

Definition at line 147 of file Neighbour.cpp.

References hashPosition(), and m_hashMap.

{
#pragma omp for schedule(dynamic, 50)
    //loop through each particle in the fluid
    for (int i = 0; i < _particleList.size(); ++i)
    {
        //hash position
        int hashKey = hashPosition(_particleList[i].getPosition());

#pragma omp critical
        //add (hashkey, particle) pair to hashmap
        m_hashMap.insert(std::pair<int, FluidParticle>(hashKey, _particleList[i]));
    }
}

Here is the call graph for this function:

void Neighbour::reInitialise	(	const int	_numParticles,
		const float	_smoothingLength
	)

reinitialise the spatial structure

Parameters:

[in]	_numParticles	the fluid particle count
[in]	_smoothingLength	the smoothing length

Definition at line 34 of file Neighbour.cpp.

{
    //initialise cell size
    m_cellSize = _smoothingLength;

    //initialise hash map size
    m_mapSize = getNextPrimeNumber(2 * _numParticles);
}

Here is the caller graph for this function: