---

Introduction

abspy is a Python tool for 3D adaptive binary space partitioning and beyond. It adaptively partitions ambient 3D space into a linear cell complex using planar primitives, dynamically generating an adjacency graph in the process. Designed primarily for compact surface reconstruction, abspy also supports a range of other applications.

Key features

• Manipulation of planar primitives from point cloud or reference mesh
• Linear cell complex creation with adaptive binary space partitioning (a-BSP)
• Dynamic BSP-tree (NetworkX graph) updated locally upon primitive insertion
• Support of polygonal surface reconstruction with graph cut
• Compatible data structure with Easy3D on point cloud, primitive, mesh and cell complex
• Robust spatial operations underpinned by the rational ring from SageMath's exact kernel

Installation

All-in-one installation

Create a conda environment with the latest abspy release and all its dependencies installed:

bash git clone https://github.com/chenzhaiyu/abspy && cd abspy conda env create -f environment.yml && conda activate abspy

Manual installation

Still easy! Create a conda environment and enter it:

bash conda create --name abspy python=3.11 && conda activate abspy

Install the dependencies:

```bash

You may replace conda with mamba for faster package parsing

conda install mamba -c conda-forge

conda install -c conda-forge networkx numpy tqdm scikit-learn matplotlib colorlog scipy trimesh rtree pyglet sage=10.2 ```

Preferably, the latest abspy release can be found and installed via PyPI:

bash pip install abspy

Otherwise, you can install the latest version locally:

bash git clone https://github.com/chenzhaiyu/abspy && cd abspy pip install .

Quick start

Example 1 - Reconstruction from point cloud

The example loads a point cloud to VertexGroup (.vg), partitions ambient space into a cell complex, creates the adjacency graph, and extracts the object's outer surface.

```python from abspy import VertexGroup, AdjacencyGraph, CellComplex

load a point cloud in VertexGroup

vertexgroup = VertexGroup(filepath='tutorials/data/testpoints.vg')

normalise point cloud

vertexgroup.normalisetocentroidand_scale()

initialise cell complex

cellcomplex = CellComplex(vertexgroup.planes, vertexgroup.aabbs, vertexgroup.obbs, vertexgroup.pointsgrouped, buildgraph=True, additionalplanes=None)

refine planar primitives

cellcomplex.refineplanes()

prioritise certain planes (e.g., vertical ones)

cellcomplex.prioritiseplanes(prioritise_verticals=False)

construct cell complex

cell_complex.construct()

print info about cell complex

cellcomplex.printinfo()

cells inside reference mesh

cellsinmesh = cellcomplex.cellsinmesh('tutorials/data/testmesh.ply')

build adjacency graph from cell complex

adjacencygraph = AdjacencyGraph(cellcomplex.graph)

calculate volumes

volumes = cellcomplex.volumes(multiplier=10e5) volumes = [0.1 if i in cellsin_mesh else vol for i, vol in enumerate(volumes)]

assign graph weights

adjacencygraph.assignweightstonlinks(cellcomplex.cells, attribute='areaoverlap', factor=0.000, cacheinterfaces=True) adjacencygraph.assignweightstostlinks(adjacencygraph.to_dict(volumes))

perform graph cut to extract surface

, _ = adjacencygraph.cut()

save surface model to an OBJ file

adjacencygraph.savesurface_obj('tutorials/output/surface.obj', engine='mesh') ```

Example 2 - Convex decomposition from mesh

The example loads a mesh to VertexGroupReference, partitions ambient space into a cell complex, identifies cells inside reference mesh, and visualizes the cells.

```python from abspy import VertexGroupReference vertexgroupreference = VertexGroupReference(filepath='tutorials/data/test_mesh.ply')

initialise cell complex

cellcomplex = CellComplex(vertexgroupreference.planes, vertexgroupreference.aabbs, vertexgroupreference.obbs, buildgraph=True)

construct cell complex

cell_complex.construct()

cells inside reference mesh

cellsinmesh = cellcomplex.cellsinmesh('tutorials/data/testmesh.ply', engine='distance')

save cell complex file

cell_complex.save('tutorials/output/complex.cc')

visualise the inside cells

if len(cellsinmesh): cellcomplex.visualise(indicescells=cellsinmesh) ```

Please find the usage of abspy at API reference, with self-explanatory examples in ./tutorials. For the data structure of a .vg/.bvg file, please refer to VertexGroup.

Testing abspy

To run the test suite, first install pytest, and execute all tests:

bash pytest

Contributing to abspy

Please see the Contribution Guide for more information.

FAQ

• How can I install abspy on Windows

For Windows users, you may need to build SageMath from source or install all other dependencies into a pre-built SageMath environment. Otherwise, virtualization with docker may come to the rescue.

• How can I use abspy for surface reconstruction?

As shown in Example 1, the surface is defined between adjacent cells where one is inside and the other outside. For more information, please refer to Points2Poly which integrates abspy with deep implicit fields, and PolyGNN which learns a piecewise planar occupancy function supported by abspy, for 3D building reconstruction.

License

See the MIT license for details.

Citation

If you use abspy in a scientific work, please consider citing the paper:

bibtex @article{chen2022points2poly, title = {Reconstructing compact building models from point clouds using deep implicit fields}, journal = {ISPRS Journal of Photogrammetry and Remote Sensing}, volume = {194}, pages = {58-73}, year = {2022}, issn = {0924-2716}, doi = {https://doi.org/10.1016/j.isprsjprs.2022.09.017}, url = {https://www.sciencedirect.com/science/article/pii/S0924271622002611}, author = {Zhaiyu Chen and Hugo Ledoux and Seyran Khademi and Liangliang Nan} }

To cite the abspy software package itself, please use: bibtex @article{chen2025abspy, title = {abspy: A Python package for 3D adaptive binary space partitioning and modeling}, journal = {Journal of Open Source Software}, volume = {10}, number = {110}, pages = {7946}, year = {2025}, doi = {10.21105/joss.07946}, url = {https://doi.org/10.21105/joss.07946}, publisher = {The Open Journal}, author = {Zhaiyu Chen}, }