Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add spatial_hash implementation #8

Merged
merged 9 commits into from
Nov 11, 2022
Merged

Add spatial_hash implementation #8

merged 9 commits into from
Nov 11, 2022

Conversation

nahueespinosa
Copy link
Member

@nahueespinosa nahueespinosa commented Nov 5, 2022

For different parts of the algorithm we will need to mark particles that are close to each other with a cluster id. This is used in adaptive sampling to compute the KL-distance and it is also normally used in the estimation process, where they take the most likely cluster (by adding up the weights) and computing the mean and covariance of those samples.

One way of doing that is to discretize particle positions with respect to an user-defined cell size, and then compute a hash that represents that region of space. This is known as voxel hashing.

Here is a super simple implementation that takes a tuple of doubles and has the following properties after rounding the real values:

  • In 3-dimensions, it guarantees no collisions in the integer range that goes from -1,048,576 to 1,048,575 per axis (21 bits).
  • In 2-dimensions, the usable range goes from -2,147,483,648 to 2,147,483,647 (32 bits).

@nahueespinosa nahueespinosa force-pushed the nahuel/voxel_hash branch 2 times, most recently from e528efa to fd8e6c0 Compare November 5, 2022 22:06
Copy link
Collaborator

@hidmic hidmic left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

@nahueespinosa Awesome work as usual. Left some comments.

beluga/core/include/beluga/voxel_hash.h Outdated Show resolved Hide resolved
beluga/core/include/beluga/voxel_hash.h Outdated Show resolved Hide resolved
beluga/core/include/beluga/voxel_hash.h Outdated Show resolved Hide resolved
beluga/core/CMakeLists.txt Outdated Show resolved Hide resolved
@hidmic
Copy link
Collaborator

hidmic commented Nov 7, 2022

This LGTM if @camistolo is on board.

@hidmic hidmic requested a review from camistolo November 7, 2022 18:21
@nahueespinosa nahueespinosa self-assigned this Nov 9, 2022
@nahueespinosa nahueespinosa changed the title Add voxel_hash implementation Add spatial_hash implementation Nov 11, 2022
@nahueespinosa
Copy link
Member Author

Alright, going in!

@nahueespinosa nahueespinosa merged commit ffaffa5 into master Nov 11, 2022
@nahueespinosa nahueespinosa deleted the nahuel/voxel_hash branch November 13, 2022 12:58
@nahueespinosa nahueespinosa added the cpp Related to C++ code label Jan 7, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
cpp Related to C++ code
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet

2 participants