Numba Celltree
==============
.. image:: https://img.shields.io/github/actions/workflow/status/deltares/numba_celltree/ci.yml?style=flat-square
:target: https://github.com/deltares/numba_celltree/actions?query=workflows%3Aci
.. image:: https://img.shields.io/codecov/c/github/deltares/numba_celltree.svg?style=flat-square
:target: https://app.codecov.io/gh/deltares/numba_celltree
.. image:: https://img.shields.io/badge/code%20style-black-000000.svg?style=flat-square
:target: https://github.com/psf/black
Finding your way around in unstructured meshes is difficult. Numba Celltree
provides methods for searching for points, lines, boxes, and cells (convex
polygons) in a two dimensional unstructured mesh.
.. code:: python
import numpy as np
from numba_celltree import CellTree2d
vertices, faces = demo.generate_disk(5, 5)
vertices += 1.0
vertices *= 5.0
tree = CellTree2d(vertices, faces, -1)
# Intersection with two triangles
triangle_vertices = np.array(
[
[5.0, 3.0],
[7.0, 3.0],
[7.0, 5.0],
[0.0, 6.0],
[4.0, 4.0],
[6.0, 10.0],
]
)
triangles = np.array([[0, 1, 2], [3, 4, 5]])
tri_i, cell_i, area = tree.intersect_faces(triangle_vertices, triangles, -1)
# Intersection with two lines
edge_coords = np.array(
[
[[0.0, 0.0], [10.0, 10.0]],
[[0.0, 10.0], [10.0, 0.0]],
]
)
edge_i, cell_i, intersections = tree.intersect_edges(edge_coords)
.. image:: https://raw.githubusercontent.com/Deltares/numba_celltree/main/docs/_static/intersection-example.svg
:target: https://github.com/deltares/numba_celltree
Installation
------------
.. code:: console
pip install numba_celltree
Documentation
-------------
.. image:: https://img.shields.io/github/actions/workflow/status/deltares/numba_celltree/ci.yml?style=flat-square
:target: https://deltares.github.io/numba_celltree/
Background
----------
This package provides the cell tree data structure described in:
Garth, C., & Joy, K. I. (2010). Fast, memory-efficient cell location in
unstructured grids for visualization. IEEE Transactions on Visualization and
Computer Graphics, 16(6), 1541-1550.
This paper can be read `here
<https://escholarship.org/content/qt0vq7q87f/qt0vq7q87f.pdf>`_.
The tree building code is a direction translation of the (public domain) `C++
code
<https://github.com/NOAA-ORR-ERD/cell_tree2d/blob/master/src/cell_tree2d.cpp>`_
by Jay Hennen, which is available in the `cell_tree2d
<https://github.com/NOAA-ORR-ERD/cell_tree2d>`_ python package. This
implementation is currently specialized for two spatial dimensions, but
extension to three dimensions is relatively straightforward. Another (BSD
licensed) implementation which supports three dimensions can be found in VTK's
`CellTreeLocator
<https://vtk.org/doc/nightly/html/classvtkCellTreeLocator.html>`_.
The cell tree of the ``cell_tree2d`` currently only locates points. I've added
additional methods for locating and clipping lines and convex polygons.
Just-In-Time Compilation: Numba
-------------------------------
This package relies on `Numba <https://numba.pydata.org/>`_ to just-in-time
compile Python code into fast machine code. This has the benefit of keeping
this package a "pure" Python package, albeit with a dependency on Numba.
With regards to performance:
* Building the tree is marginally faster compared to the C++ implementation
(~15%).
* Serial point queries are somewhat slower (~50%), but Numba's automatic
parallelization speeds things up significantly. (Of course the C++ code can
be parallelized in the same manner with ``pragma omp parallel for``.)
* The other queries have not been compared, as the C++ code lacks the
functionality.
* In traversing the tree, recursion in Numba appears to be less performant than
maintaining a stack of nodes to traverse. The VTK implementation also uses
a stack rather than recursion. Ideally, we would use a stack memory allocated
array since this seems to result in a ~30% speed-up (especially when running
multi-threaded), but these stack allocated arrays cannot be grown
dynamically.
* Numba (like its `LLVM JIT sister Julia <https://julialang.org/>`_) does not
allocate small arrays on the stack automatically, like C++ and Fortran
compilers do. However, it can be done `manually
<https://github.com/numba/numba/issues/5084>`_. This cuts down runtimes for
some functions by at least a factor 2, more so in parallel. However, these
stack allocated arrays work only in the context of Numba. They must be
disabled when running in uncompiled Python -- there is some code in
``numba_celltree.utils`` which takes care of this.
* Some methods like ``locate_points`` are trivially parallelizable, since
there is one return value for each point. In that case, we can pre-allocate
the output array immediately and apply ``nb.prange``, letting it spawn threads
as needed.
* Some methods, however, return an a priori unknown number of values. At the
time of writing, Numba's lists are
`not thread safe <https://github.com/numba/numba/issues/5878>`_. There are
two options here. The first option is to query twice: the first time we only
count, then we allocate the results array(s), and the second time we store
the actual values. Since parallelization generally results in speedups over a
factor 2, this still results in a net gain. The second option is to chunk
manually, and assign one chunk per thread. Each chunk can then allocate
dynamically; we store the output of each thread in a list (of numpy arrays).
This has overhead in terms of continuous bounds-checking and a final merge,
but appears to be on net ~30% faster than the query-twice scheme. The net
gain may disappear with a sufficiently large number of CPUs as at some point the
serial merge and larger number of dynamic allocations starts dominating the
total run time (on my 16 core laptop, querying once is still superior).
To debug, set the environmental variable ``NUMBA_DISABLE_JIT=1``. Re-enable by
setting ``NUMBA_DISABLE_JIT=0``.
.. code:: bash
export NUMBA_DISABLE_JIT=1
In Windows Command Prompt:
.. code:: console
set NUMBA_DISABLE_JIT=1
In Windows Powershell:
.. code:: console
$env:NUMBA_DISABLE_JIT=1
In Python itself:
.. code:: python
import os
os.environ["NUMBA_DISABLE_JIT"] = "1"
This must be done before importing the package to have effect.
Raw data
{
"_id": null,
"home_page": null,
"name": "numba-celltree",
"maintainer": null,
"docs_url": null,
"requires_python": ">=3.9",
"maintainer_email": "Huite Bootsma <huite.bootsma@deltares.nl>",
"keywords": "mesh, spatial index, ugrid, unstructured grid",
"author": null,
"author_email": null,
"download_url": "https://files.pythonhosted.org/packages/75/46/c9df1ec69ff43f81dc7efe4a0b2fee6a160ae5729a98aade2b7579259f1d/numba_celltree-0.2.2.tar.gz",
"platform": null,
"description": "Numba Celltree\n==============\n\n.. image:: https://img.shields.io/github/actions/workflow/status/deltares/numba_celltree/ci.yml?style=flat-square\n :target: https://github.com/deltares/numba_celltree/actions?query=workflows%3Aci\n.. image:: https://img.shields.io/codecov/c/github/deltares/numba_celltree.svg?style=flat-square\n :target: https://app.codecov.io/gh/deltares/numba_celltree\n.. image:: https://img.shields.io/badge/code%20style-black-000000.svg?style=flat-square\n :target: https://github.com/psf/black\n\nFinding your way around in unstructured meshes is difficult. Numba Celltree\nprovides methods for searching for points, lines, boxes, and cells (convex\npolygons) in a two dimensional unstructured mesh.\n\n.. code:: python\n\n import numpy as np\n from numba_celltree import CellTree2d\n\n\n vertices, faces = demo.generate_disk(5, 5)\n vertices += 1.0\n vertices *= 5.0\n tree = CellTree2d(vertices, faces, -1)\n\n # Intersection with two triangles\n triangle_vertices = np.array(\n [\n [5.0, 3.0],\n [7.0, 3.0],\n [7.0, 5.0],\n [0.0, 6.0],\n [4.0, 4.0],\n [6.0, 10.0],\n ]\n )\n triangles = np.array([[0, 1, 2], [3, 4, 5]])\n tri_i, cell_i, area = tree.intersect_faces(triangle_vertices, triangles, -1)\n\n # Intersection with two lines\n edge_coords = np.array(\n [\n [[0.0, 0.0], [10.0, 10.0]],\n [[0.0, 10.0], [10.0, 0.0]],\n ]\n )\n edge_i, cell_i, intersections = tree.intersect_edges(edge_coords)\n\n.. image:: https://raw.githubusercontent.com/Deltares/numba_celltree/main/docs/_static/intersection-example.svg\n :target: https://github.com/deltares/numba_celltree\n\nInstallation\n------------\n\n.. code:: console\n\n pip install numba_celltree\n \nDocumentation\n-------------\n\n.. image:: https://img.shields.io/github/actions/workflow/status/deltares/numba_celltree/ci.yml?style=flat-square\n :target: https://deltares.github.io/numba_celltree/\n\nBackground\n----------\n\nThis package provides the cell tree data structure described in:\n\nGarth, C., & Joy, K. I. (2010). Fast, memory-efficient cell location in\nunstructured grids for visualization. IEEE Transactions on Visualization and\nComputer Graphics, 16(6), 1541-1550.\n\nThis paper can be read `here\n<https://escholarship.org/content/qt0vq7q87f/qt0vq7q87f.pdf>`_.\n\nThe tree building code is a direction translation of the (public domain) `C++\ncode\n<https://github.com/NOAA-ORR-ERD/cell_tree2d/blob/master/src/cell_tree2d.cpp>`_\nby Jay Hennen, which is available in the `cell_tree2d\n<https://github.com/NOAA-ORR-ERD/cell_tree2d>`_ python package. This\nimplementation is currently specialized for two spatial dimensions, but\nextension to three dimensions is relatively straightforward. Another (BSD\nlicensed) implementation which supports three dimensions can be found in VTK's\n`CellTreeLocator\n<https://vtk.org/doc/nightly/html/classvtkCellTreeLocator.html>`_.\n\nThe cell tree of the ``cell_tree2d`` currently only locates points. I've added\nadditional methods for locating and clipping lines and convex polygons.\n\nJust-In-Time Compilation: Numba\n-------------------------------\n\nThis package relies on `Numba <https://numba.pydata.org/>`_ to just-in-time\ncompile Python code into fast machine code. This has the benefit of keeping\nthis package a \"pure\" Python package, albeit with a dependency on Numba.\n\nWith regards to performance:\n\n* Building the tree is marginally faster compared to the C++ implementation\n (~15%).\n* Serial point queries are somewhat slower (~50%), but Numba's automatic\n parallelization speeds things up significantly. (Of course the C++ code can\n be parallelized in the same manner with ``pragma omp parallel for``.)\n* The other queries have not been compared, as the C++ code lacks the\n functionality.\n* In traversing the tree, recursion in Numba appears to be less performant than\n maintaining a stack of nodes to traverse. The VTK implementation also uses\n a stack rather than recursion. Ideally, we would use a stack memory allocated\n array since this seems to result in a ~30% speed-up (especially when running\n multi-threaded), but these stack allocated arrays cannot be grown\n dynamically.\n* Numba (like its `LLVM JIT sister Julia <https://julialang.org/>`_) does not\n allocate small arrays on the stack automatically, like C++ and Fortran\n compilers do. However, it can be done `manually\n <https://github.com/numba/numba/issues/5084>`_. This cuts down runtimes for\n some functions by at least a factor 2, more so in parallel. However, these\n stack allocated arrays work only in the context of Numba. They must be\n disabled when running in uncompiled Python -- there is some code in\n ``numba_celltree.utils`` which takes care of this.\n* Some methods like ``locate_points`` are trivially parallelizable, since\n there is one return value for each point. In that case, we can pre-allocate\n the output array immediately and apply ``nb.prange``, letting it spawn threads\n as needed.\n* Some methods, however, return an a priori unknown number of values. At the\n time of writing, Numba's lists are \n `not thread safe <https://github.com/numba/numba/issues/5878>`_. There are\n two options here. The first option is to query twice: the first time we only\n count, then we allocate the results array(s), and the second time we store\n the actual values. Since parallelization generally results in speedups over a\n factor 2, this still results in a net gain. The second option is to chunk\n manually, and assign one chunk per thread. Each chunk can then allocate\n dynamically; we store the output of each thread in a list (of numpy arrays).\n This has overhead in terms of continuous bounds-checking and a final merge,\n but appears to be on net ~30% faster than the query-twice scheme. The net\n gain may disappear with a sufficiently large number of CPUs as at some point the\n serial merge and larger number of dynamic allocations starts dominating the\n total run time (on my 16 core laptop, querying once is still superior).\n\nTo debug, set the environmental variable ``NUMBA_DISABLE_JIT=1``. Re-enable by\nsetting ``NUMBA_DISABLE_JIT=0``.\n\n.. code:: bash\n\n export NUMBA_DISABLE_JIT=1\n\nIn Windows Command Prompt:\n\n.. code:: console\n\n set NUMBA_DISABLE_JIT=1\n\nIn Windows Powershell:\n\n.. code:: console\n\n $env:NUMBA_DISABLE_JIT=1\n\nIn Python itself:\n\n.. code:: python\n\n import os\n\n os.environ[\"NUMBA_DISABLE_JIT\"] = \"1\"\n\nThis must be done before importing the package to have effect. \n",
"bugtrack_url": null,
"license": "MIT",
"summary": "Cell Tree Spatial Index",
"version": "0.2.2",
"project_urls": {
"Code": "https://github.com/deltares/numba_celltree",
"Home": "https://github.com/deltares/numba_celltree",
"Issues": "https://github.com/deltares/numba_celltree/issues"
},
"split_keywords": [
"mesh",
" spatial index",
" ugrid",
" unstructured grid"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "0db0c3e8810ae280bb6c757de6acdfdbb9b7bfd020b2adf3445a2ab3c1b3bb64",
"md5": "b74d1cfd20f35f3b4e6b90cd6edf3a24",
"sha256": "b5e5fc874cc078b3a2a931cf3e3c360b505a80b0581599fb768f8dc424a5c77a"
},
"downloads": -1,
"filename": "numba_celltree-0.2.2-py3-none-any.whl",
"has_sig": false,
"md5_digest": "b74d1cfd20f35f3b4e6b90cd6edf3a24",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": ">=3.9",
"size": 36250,
"upload_time": "2024-10-15T13:47:08",
"upload_time_iso_8601": "2024-10-15T13:47:08.321484Z",
"url": "https://files.pythonhosted.org/packages/0d/b0/c3e8810ae280bb6c757de6acdfdbb9b7bfd020b2adf3445a2ab3c1b3bb64/numba_celltree-0.2.2-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "7546c9df1ec69ff43f81dc7efe4a0b2fee6a160ae5729a98aade2b7579259f1d",
"md5": "6ceb74190c505821b0d0b142a476f21d",
"sha256": "c5b1988a739833bc45587640f1ba19fca8d377298c2ba60d0a08683389f21c63"
},
"downloads": -1,
"filename": "numba_celltree-0.2.2.tar.gz",
"has_sig": false,
"md5_digest": "6ceb74190c505821b0d0b142a476f21d",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.9",
"size": 46328,
"upload_time": "2024-10-15T13:47:09",
"upload_time_iso_8601": "2024-10-15T13:47:09.538039Z",
"url": "https://files.pythonhosted.org/packages/75/46/c9df1ec69ff43f81dc7efe4a0b2fee6a160ae5729a98aade2b7579259f1d/numba_celltree-0.2.2.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2024-10-15 13:47:09",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "deltares",
"github_project": "numba_celltree",
"travis_ci": false,
"coveralls": false,
"github_actions": true,
"lcname": "numba-celltree"
}
JSON
