Skip to main content

Fast Gaussian Accumulator

PyPI Docs Run Tests License

A Gaussian Sphere Accumulator refers to the notion of discretizing the surface of the unit sphere (a gaussian surface) into buckets/cells. One can then integrate/accumulate a list of points (aka unit normals) into these buckets. The end result is then a histogram of the sphere. There are many choices for the discretization process, however this library uses equilateral triangles because each cell will have nearly the same area and shape. This process is done by refining an icosahedron. The following image shows our discretization strategy. The first object discretizes a sphere with uniform spacing of phi/theta (note small cells at poles), the second object is an icosahedron, the third object is the first level of refinement for an icosahedron, the last object is the second level of refinement of an icosahedron.

Icosahedron

Once a level of refinement is chosen, one can then integrate point vectors into the cells/buckets. For example integrating the normals of a level four (4) icosahedron would look like the image below. Bright yellow indicates more counts for the triangle cells. This is basically showing that the floor [0, 0, 1] and walls [0, +/-1, 0] are common.

GaussianAccumulator

Finding the Cell

To do this one must find the cell that corresponds to the point. This is a search process that has been implemented in several fashions in this repo. The main ways are as follows:

  • 3D KD Tree - Do a nearest neighbor search using a binary tree.
    • GaussianAccumulatorKDPY - One implementation using scipy kdtree.
    • GaussianAccumulatorKD One implementation uses C++ nanoflann.
  • Global Index and Local Search - A 3D point is transformed to a unique integer id. The unique ids have the property that ids close to each other will be close to each other in 3D space. The closest id is found corresponding to a triangle cell. A local search of triangle neighbors is performed to find closest triangle cell to the point.
    • GaussianAccumulatorOpt - Works good on only on the top hemisphere. Projects 3D point to plane using Azimuth Equal Area projection. Convert 2D point to int32 index using Hilbert Curve. This implementation is severely limited and is not recommended.
    • GaussianAccumulatorS2Beta - Works on full sphere! Uses Googles S2 space filling curve (uint64). 3D point is projected to unit cube, assigned to a face of the cube, and then a Hilbert curve index is found for that cube face. This is recommended, and what I use.

Use GaussianAccumulatorS2Beta! Look at python -m examples.python.run_normals

Peak Detection

There are two (2) peak detection methods of used within this repository. The user can choose which one best suite there needs.

2D Image Peak Detection

This method basically unwraps the icosahedron as a 2D image in a very particular way as described by Gauge Equivariant Convolutional Networks and the Icosahedral CNN. This unwrapping is hardcoded and fixed once a refinement level is chosen so its very fast. The library then uses a 2D peak detector algorithm followed up with agglomerative hierarchial clustering (AHC) to group similar peaks. All of this is user configurable.

1D Signal Peak Detection

This performs peak detection on the 1D thread following the hilbert curve. This produces more peaks which are actually near each other on S2 and are then grouped with AHC. This actually works pretty well, but I recommend to use the 2D Image Peak Detector.

Installation

For python there are pre-built binary wheel on PyPI for Windows and Linux. You can install with pip install fastgac.

Below are instruction to build the C++ Package (and python package) manaully with CMake. Installation is entirely through CMake now. You must have CMake 3.14 or higher installed and a C++ compiler with C++ 14 or higher.

Build Project Library

  1. mkdir cmake-build && cd cmake-build. - create build folder directory
  2. cmake ../ -DCMAKE_BUILD_TYPE=Release . For windows also add -DCMAKE_GENERATOR_PLATFORM=x64
  3. cmake --build . -j$(nproc) --config Release - Build FastGA

Build and Install Python Extension

For Developers

  1. Install conda or create a python virtual environment (Why?). I recommend conda for Windows users.
  2. cd cmake-build && cmake --build . --target python-package --config Release -j$(nproc)
  3. cd lib/python_package && pip install -e .

If you want to run the examples then you need to install the following (from main directory):

  1. pip install -r dev-requirements.txt

For Python Users (Requires CMake)

  1. Install conda or create a python virtual environment (Why?). I recommend conda for Windows users.
  2. pip install .

If you want to run the examples then you need to install the following (from main directory):

  1. pip install -r dev-requirements.txt

Documentation

Please see documentation website for more details.

Citation

To support our work please cite:

@Article{s20174819,
AUTHOR = {Castagno, Jeremy and Atkins, Ella},
TITLE = {Polylidar3D-Fast Polygon Extraction from 3D Data},
JOURNAL = {Sensors},
VOLUME = {20},
YEAR = {2020},
NUMBER = {17},
ARTICLE-NUMBER = {4819},
URL = {https://www.mdpi.com/1424-8220/20/17/4819},
ISSN = {1424-8220}
}

Metadata

Release files for fastgac 1.0.5

For a detailed explanation of source distributions (sdists) and built distributions (wheels), please see the package formats documentation.

Source distribution (sdist)

Source distribution for fastgac 1.0.5
File Size Uploaded Provenance Actions
fastgac-1.0.5.tar.gz 114.0 kB Without provenance Details for fastgac-1.0.5.tar.gz

Built distributions (wheels)

Table of built distributions (wheels) for fastgac 1.0.5
File Actions
fastgac-1.0.5-cp39-cp39-win_amd64.whl CPython 3.9 CPython 3.9 Windows x86-64 Details for fastgac-1.0.5-cp39-cp39-win_amd64.whl
fastgac-1.0.5-cp39-cp39-manylinux2010_x86_64.whl CPython 3.9 CPython 3.9 Linux glibc 2.12+ x86-64 Details for fastgac-1.0.5-cp39-cp39-manylinux2010_x86_64.whl
fastgac-1.0.5-cp39-cp39-macosx_11_0_arm64.whl CPython 3.9 CPython 3.9 macOS 11.0+ ARM64 Details for fastgac-1.0.5-cp39-cp39-macosx_11_0_arm64.whl
fastgac-1.0.5-cp39-cp39-macosx_10_9_x86_64.whl CPython 3.9 CPython 3.9 macOS 10.9+ x86-64 Details for fastgac-1.0.5-cp39-cp39-macosx_10_9_x86_64.whl
fastgac-1.0.5-cp39-cp39-macosx_10_9_universal2.whl CPython 3.9 CPython 3.9 macOS 10.9+ universal2 (ARM64, x86-64) Details for fastgac-1.0.5-cp39-cp39-macosx_10_9_universal2.whl
fastgac-1.0.5-cp38-cp38-win_amd64.whl CPython 3.8 CPython 3.8 Windows x86-64 Details for fastgac-1.0.5-cp38-cp38-win_amd64.whl
fastgac-1.0.5-cp38-cp38-manylinux2010_x86_64.whl CPython 3.8 CPython 3.8 Linux glibc 2.12+ x86-64 Details for fastgac-1.0.5-cp38-cp38-manylinux2010_x86_64.whl
fastgac-1.0.5-cp38-cp38-macosx_10_9_x86_64.whl CPython 3.8 CPython 3.8 macOS 10.9+ x86-64 Details for fastgac-1.0.5-cp38-cp38-macosx_10_9_x86_64.whl
fastgac-1.0.5-cp37-cp37m-win_amd64.whl CPython 3.7 CPython 3.7 pymalloc Windows x86-64 Details for fastgac-1.0.5-cp37-cp37m-win_amd64.whl
fastgac-1.0.5-cp37-cp37m-manylinux2010_x86_64.whl CPython 3.7 CPython 3.7 pymalloc Linux glibc 2.12+ x86-64 Details for fastgac-1.0.5-cp37-cp37m-manylinux2010_x86_64.whl
fastgac-1.0.5-cp37-cp37m-macosx_10_9_x86_64.whl CPython 3.7 CPython 3.7 pymalloc macOS 10.9+ x86-64 Details for fastgac-1.0.5-cp37-cp37m-macosx_10_9_x86_64.whl
fastgac-1.0.5-cp36-cp36m-win_amd64.whl CPython 3.6 CPython 3.6 pymalloc Windows x86-64 Details for fastgac-1.0.5-cp36-cp36m-win_amd64.whl
fastgac-1.0.5-cp36-cp36m-manylinux2010_x86_64.whl CPython 3.6 CPython 3.6 pymalloc Linux glibc 2.12+ x86-64 Details for fastgac-1.0.5-cp36-cp36m-manylinux2010_x86_64.whl
fastgac-1.0.5-cp36-cp36m-macosx_10_9_x86_64.whl CPython 3.6 CPython 3.6 pymalloc macOS 10.9+ x86-64 Details for fastgac-1.0.5-cp36-cp36m-macosx_10_9_x86_64.whl

Total release size: 4.4 MB

Release files / fastgac-1.0.5.tar.gz

Download URL fastgac-1.0.5.tar.gz
Size 114.0 kB
Tags Source
SHA-256 checksum
How to use checksums
6ca237edf24298d1fc726934d3d495c6dabd0cc2ca2ce8d1f4262d53ac7ba6b6
BLAKE2b-256 checksum
How to use checksums
c1c2cb51c8067453b8e1592727eb00c690ec9905e56f6d59aea98852afe81667
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via twine/3.4.1 importlib_metadata/4.5.0 pkginfo/1.7.0 requests/2.25.1 requests-toolbelt/0.9.1 tqdm/4.61.0 CPython/3.9.5

Release files / fastgac-1.0.5-cp39-cp39-win_amd64.whl

Download URL fastgac-1.0.5-cp39-cp39-win_amd64.whl
Size 254.3 kB
Tags CPython 3.9 Windows x86-64
SHA-256 checksum
How to use checksums
72866157cdc042591f2613372b2fd853802560b4f6a8d8c3b4801779b7605ac8
BLAKE2b-256 checksum
How to use checksums
e90ca8e3a05536de151432678df7e2622f0b83744cb724c30f5ad90b2a724119
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via twine/3.4.1 importlib_metadata/4.5.0 pkginfo/1.7.0 requests/2.25.1 requests-toolbelt/0.9.1 tqdm/4.61.0 CPython/3.9.5

Release files / fastgac-1.0.5-cp39-cp39-manylinux2010_x86_64.whl

Download URL fastgac-1.0.5-cp39-cp39-manylinux2010_x86_64.whl
Size 358.1 kB
Tags CPython 3.9 Linux glibc 2.12+ x86-64
SHA-256 checksum
How to use checksums
ea8bfb52859e80f403494d435660f781a270eb5e86cbf1dc4270c908c8b1e6ad
BLAKE2b-256 checksum
How to use checksums
e063d9fcb3b273623328c7e9257f4378ef059111e281d032e3354a46c2e1a139
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via twine/3.4.1 importlib_metadata/4.5.0 pkginfo/1.7.0 requests/2.25.1 requests-toolbelt/0.9.1 tqdm/4.61.0 CPython/3.9.5

Release files / fastgac-1.0.5-cp39-cp39-macosx_11_0_arm64.whl

Download URL fastgac-1.0.5-cp39-cp39-macosx_11_0_arm64.whl
Size 312.2 kB
Tags CPython 3.9 macOS 11.0+ ARM64
SHA-256 checksum
How to use checksums
767bbc1433bc342c1b58ba97550b0a6781c2199dca91ab8adaaa1b212c3d0b18
BLAKE2b-256 checksum
How to use checksums
ed646d99cc8eb9ba9880055b4362b867c5583dc39be6be0a7787e99206856159
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via twine/3.4.1 importlib_metadata/4.5.0 pkginfo/1.7.0 requests/2.25.1 requests-toolbelt/0.9.1 tqdm/4.61.0 CPython/3.9.5

Release files / fastgac-1.0.5-cp39-cp39-macosx_10_9_x86_64.whl

Download URL fastgac-1.0.5-cp39-cp39-macosx_10_9_x86_64.whl
Size 312.2 kB
Tags CPython 3.9 macOS 10.9+ x86-64
SHA-256 checksum
How to use checksums
0b75fb43ea5ff36bc8f7747e633702bd9cd292607222d7c71dd9a55f860ffe25
BLAKE2b-256 checksum
How to use checksums
3e7847d0909904f164b120aa6c1780007a1dc862c8966837bbb06de3f851c599
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via twine/3.4.1 importlib_metadata/4.5.0 pkginfo/1.7.0 requests/2.25.1 requests-toolbelt/0.9.1 tqdm/4.61.0 CPython/3.9.5

Release files / fastgac-1.0.5-cp39-cp39-macosx_10_9_universal2.whl

Download URL fastgac-1.0.5-cp39-cp39-macosx_10_9_universal2.whl
Size 312.2 kB
Tags CPython 3.9 macOS 10.9+ universal2 (ARM64, x86-64)
SHA-256 checksum
How to use checksums
a73addd8778218a7f000c4dfda107e29df481a423a717ba44e459c55c0d9f196
BLAKE2b-256 checksum
How to use checksums
ef12dc01208f9d457076cff58662bf7d171bdeca2d9fe7ee4668bcea4a50099b
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via twine/3.4.1 importlib_metadata/4.5.0 pkginfo/1.7.0 requests/2.25.1 requests-toolbelt/0.9.1 tqdm/4.61.0 CPython/3.9.5

Release files / fastgac-1.0.5-cp38-cp38-win_amd64.whl

Download URL fastgac-1.0.5-cp38-cp38-win_amd64.whl
Size 254.2 kB
Tags CPython 3.8 Windows x86-64
SHA-256 checksum
How to use checksums
0cbd82d21acf6162d1d8d21fef79a7c41c73534984273abf38551f67421a3ad0
BLAKE2b-256 checksum
How to use checksums
8afa81134778baa46a7a1dba5928617f0db659a3191bae98adbb87d1fe1a3553
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via twine/3.4.1 importlib_metadata/4.5.0 pkginfo/1.7.0 requests/2.25.1 requests-toolbelt/0.9.1 tqdm/4.61.0 CPython/3.9.5

Release files / fastgac-1.0.5-cp38-cp38-manylinux2010_x86_64.whl

Download URL fastgac-1.0.5-cp38-cp38-manylinux2010_x86_64.whl
Size 358.1 kB
Tags CPython 3.8 Linux glibc 2.12+ x86-64
SHA-256 checksum
How to use checksums
525c1a04d893a41b87b0dc9444d588297f8f691f7a2b811018ae2e038a7100fc
BLAKE2b-256 checksum
How to use checksums
71c4c01a3b0bd8c5129ec96eefd58716ae7291af91526cae42002db6d8cc17a1
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via twine/3.4.1 importlib_metadata/4.5.0 pkginfo/1.7.0 requests/2.25.1 requests-toolbelt/0.9.1 tqdm/4.61.0 CPython/3.9.5

Release files / fastgac-1.0.5-cp38-cp38-macosx_10_9_x86_64.whl

Download URL fastgac-1.0.5-cp38-cp38-macosx_10_9_x86_64.whl
Size 312.1 kB
Tags CPython 3.8 macOS 10.9+ x86-64
SHA-256 checksum
How to use checksums
e9d8ec68cf04918d12a358b090f667e15e9cd6b5f26c0c6f7954ca7f36a4a439
BLAKE2b-256 checksum
How to use checksums
13d40195cdb396c074c74764c26400dddb082835d67db51c8dce0ae1dce6b520
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via twine/3.4.1 importlib_metadata/4.5.0 pkginfo/1.7.0 requests/2.25.1 requests-toolbelt/0.9.1 tqdm/4.61.0 CPython/3.9.5

Release files / fastgac-1.0.5-cp37-cp37m-win_amd64.whl

Download URL fastgac-1.0.5-cp37-cp37m-win_amd64.whl
Size 250.0 kB
Tags CPython 3.7 CPython 3.7 pymalloc Windows x86-64
SHA-256 checksum
How to use checksums
d08b6e36af7d963c276d15ed97d75334fa7663d5b581fb5267db37f8fd7dc54e
BLAKE2b-256 checksum
How to use checksums
544e2623ec894a68f1d8f8e90a38a5afcdb5f9991c31fb74403871f29fa04282
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via twine/3.4.1 importlib_metadata/4.5.0 pkginfo/1.7.0 requests/2.25.1 requests-toolbelt/0.9.1 tqdm/4.61.0 CPython/3.9.5

Release files / fastgac-1.0.5-cp37-cp37m-manylinux2010_x86_64.whl

Download URL fastgac-1.0.5-cp37-cp37m-manylinux2010_x86_64.whl
Size 361.8 kB
Tags CPython 3.7 CPython 3.7 pymalloc Linux glibc 2.12+ x86-64
SHA-256 checksum
How to use checksums
ca83c87bb5d23f0d8105af2c2d65e9c7b6168e5b05d47961669aa914f8df6fc6
BLAKE2b-256 checksum
How to use checksums
f076cd9589c5905437e714f5993fc9a1e06d83ec1f8e7dec427001029758cdd1
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via twine/3.4.1 importlib_metadata/4.5.0 pkginfo/1.7.0 requests/2.25.1 requests-toolbelt/0.9.1 tqdm/4.61.0 CPython/3.9.5

Release files / fastgac-1.0.5-cp37-cp37m-macosx_10_9_x86_64.whl

Download URL fastgac-1.0.5-cp37-cp37m-macosx_10_9_x86_64.whl
Size 302.4 kB
Tags CPython 3.7 CPython 3.7 pymalloc macOS 10.9+ x86-64
SHA-256 checksum
How to use checksums
3d79a07d1d6397e76c92f43307ccf9d2d85d783e65dd5f85311b777ca5668e49
BLAKE2b-256 checksum
How to use checksums
2ef60dfc4ebdb44738af5dc59e42c62f52e83d4e85466510c03bd6be7c1f0a5b
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via twine/3.4.1 importlib_metadata/4.5.0 pkginfo/1.7.0 requests/2.25.1 requests-toolbelt/0.9.1 tqdm/4.61.0 CPython/3.9.5

Release files / fastgac-1.0.5-cp36-cp36m-win_amd64.whl

Download URL fastgac-1.0.5-cp36-cp36m-win_amd64.whl
Size 249.7 kB
Tags CPython 3.6 CPython 3.6 pymalloc Windows x86-64
SHA-256 checksum
How to use checksums
cb2cd6f1a70a8c637d60bd1df50cced55856db41491b6886c52d988be1d03c07
BLAKE2b-256 checksum
How to use checksums
89e61da82ace769b8decb0b816b8e6ca6ac10f851fd38e0483f2374d4bfaf9b7
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via twine/3.4.1 importlib_metadata/4.5.0 pkginfo/1.7.0 requests/2.25.1 requests-toolbelt/0.9.1 tqdm/4.61.0 CPython/3.9.5

Release files / fastgac-1.0.5-cp36-cp36m-manylinux2010_x86_64.whl

Download URL fastgac-1.0.5-cp36-cp36m-manylinux2010_x86_64.whl
Size 362.1 kB
Tags CPython 3.6 CPython 3.6 pymalloc Linux glibc 2.12+ x86-64
SHA-256 checksum
How to use checksums
9d14e6498015a6fd755afa247f0b68136cbf003a054bd25d19c68518c629955d
BLAKE2b-256 checksum
How to use checksums
965f9b4179ed434f9b949eccc0f2edd9a6d724ffeb181927d160007126b50b72
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via twine/3.4.1 importlib_metadata/4.5.0 pkginfo/1.7.0 requests/2.25.1 requests-toolbelt/0.9.1 tqdm/4.61.0 CPython/3.9.5

Release files / fastgac-1.0.5-cp36-cp36m-macosx_10_9_x86_64.whl

Download URL fastgac-1.0.5-cp36-cp36m-macosx_10_9_x86_64.whl
Size 302.3 kB
Tags CPython 3.6 CPython 3.6 pymalloc macOS 10.9+ x86-64
SHA-256 checksum
How to use checksums
c78d9781351f7c9603f5fca840e79af16dec9cf5d84fb336b8615ae965eda000
BLAKE2b-256 checksum
How to use checksums
7db76ccdba19485d03613c002437fa108011fe462e631770ce25c548edf5e99c
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via twine/3.4.1 importlib_metadata/4.5.0 pkginfo/1.7.0 requests/2.25.1 requests-toolbelt/0.9.1 tqdm/4.61.0 CPython/3.9.5

Security for fastgac 1.0.5

Provenance

Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.

No provenance found

None of the files in this release were uploaded with provenance metadata.

A note on package security

PyPI is a repository for distributing packages, not a service for auditing them. While third-party security researchers and our staff do their best to detect and remove malicious packages, PyPI cannot guarantee the quality, security or suitability of any given package.

To learn more about protecting yourself from malicious actors, visit our package security documentation.

Anthropic, PBC Visionary sponsor Bloomberg Visionary sponsor Hudson River Trading Visionary sponsor Meta Visionary sponsor NVIDIA Visionary sponsor Microsoft Sustainability sponsor Depot Continuous Integration AWS Cloud computing and Security Sponsor Datadog Monitoring Fastly CDN Google Download Analytics Sentry Error logging StatusPage Status page