FCPW: Fastest Closest Points in the West

FCPW is an acceleration library for performing fast geometric queries, such as closest points and ray intersections, on 3D triangle meshes and 2D line segment meshes. It is available in C++ and Python, and offers GPU acceleration via the Slang shading language and CPU vectorization via the Enoki library.

C++ API

The easiest and most direct way to use FCPW is through the Scene class which provides methods to load geometry, build and refit the acceleration structure and perform geometric queries. Here is an example of performing a closest point query on a 3D triangle mesh:

#include <fcpw/fcpw.h>
using namespace fcpw;

// initialize a 3d scene
Scene<3> scene;

// load positions and indices of a single triangle mesh
scene.setObjectCount(1);
scene.setObjectVertices(positions, 0);
scene.setObjectTriangles(indices, 0);

// build acceleration structure
AggregateType aggregateType = AggregateType::Bvh_SurfaceArea;
bool buildVectorizedBvh = true;
scene.build(aggregateType, buildVectorizedBvh);

// perform a closest point query
Interaction<3> interaction;
bool found = scene.findClosestPoint(queryPoint, interaction);

// access distance and closest point via interaction.d and interaction.p (resp.)

The Scene class is templated on dimension, which enables it to work with geometric data in any dimension as long as primitives are defined for the dimension of interest. In addition to triangles in 3D, FCPW also provides support for line segments in 2D. The Interaction class stores information relevant to the query, such as the distance to and closest point on the primitive.

If your scene consists of multiple objects with the same type of primitives (e.g. triangles), it is better to "flatten" those objects into a single object (with a list of positions and indices). FCPW then builds a single acceleration structure over all primitives in the scene. If multiple objects are loaded, FCPW instead builds a hierarchy of acceleration structures, with a structure for each object in the scene.

Refer to demo.cpp for a complete demo, and fcpw.h for the full API, which includes the list of supported geometric queries, heuristrics for constructing the accerlation structure, as well as support for refitting, instancing and CSG operations. Details regarding GPU support and installation are provided below.

Python API

FCPW's C++ and Python APIs follow a similar structure. However, since Python does not support templates, Python classes and functions use explicit _2D or _3D dimension tags:

import fcpw

# initialize a 3d scene
scene = fcpw.scene_3D()

# load positions and indices of a single triangle mesh
scene.set_object_count(1)
scene.set_object_vertices(positions, 0)
scene.set_object_triangles(indices, 0)

# build acceleration structure
aggregate_type = fcpw.aggregate_type.bvh_surface_area
build_vectorized_bvh = True
scene.build(aggregate_type, build_vectorized_bvh)

# perform several closest point queries
interactions = fcpw.interaction_3D_list()
scene.find_closest_points(query_points, squared_max_radii, interactions)

# extract closest points
closest_points = [i.p for i in interactions]

Refer to demo.py for a complete demo. The full API can be viewed in the Python console using help(fcpw).

GPU Support

GPU support for a large collection of query points is provided through the GPUScene class in C++, and gpu_scene_*D classes in Python. FCPW currently requires the acceleration structure to be built on the CPU and then transferred to the GPU. For instance, in C++ we have:

#include <fcpw/fcpw_gpu.h>
using namespace fcpw;

// initialize a 3d scene and load geometry (same as above)
Scene<3> scene;
...

// build acceleration structure on CPU
bool buildVectorizedCPUBvh = false; // NOTE: must build non-vectorized structure
scene.build(AggregateType::Bvh_SurfaceArea, buildVectorizedCPUBvh);

// transfer scene to GPU
GPUScene<3> gpuScene("PATH_TO_FCPW_DIRECTORY");
gpuScene.transferToGPU(scene);

// initialize bounding spheres 
std::vector<GPUBoundingSphere> boundingSpheres;
for (auto q: queryPoints) {
	float3 queryPoint = float3{q[0], q[1], q[2]};
	boundingSpheres.emplace_back(GPUBoundingSphere(queryPoint, INFINITY));
}

// perform several closest point queries on GPU
std::vector<GPUInteraction> interactions;
gpuScene.findClosestPoints(boundingSpheres, interactions);

and in Python:

import fcpw

# initialize a 3d scene and load geometry (same as above)
scene = fcpw.scene_3D()
...

# build acceleration structure on CPU
build_vectorized_cpu_bvh = False # NOTE: must build non-vectorized structure
scene.build(fcpw.aggregate_type.bvh_surface_area, build_vectorized_cpu_bvh)

# transfer scene to GPU
gpu_scene = fcpw.gpu_scene_3D("PATH_TO_FCPW_DIRECTORY")
gpu_scene.transfer_to_gpu(scene)

# perform several closest point queries on GPU
interactions = fcpw.gpu_interaction_list()
gpu_scene.find_closest_points(query_points, squared_max_radii, interactions)

Refer to demo.cpp and demo.py for complete demos. GPU support is available on Linux and Windows (Slang currently only has unofficial support for macOS).

For those developing directly on the GPU, the acceleration structure can also be accessed through bvh.slang. Slang offers CUDA, HLSL, Vulkan, OpenGL and Metal (experimental) as compilation targets. Refer to its user guide for further details on compiling to these targets.

C++ Installation

FCPW is developed as a header-only library. It can be downloaded and compiled using CMake as follows:

git clone https://github.com/rohan-sawhney/fcpw.git
cd fcpw && git submodule update --init --recursive
[...clone additional dependencies...] // instructions below
mkdir build && cd build
cmake [-DFCPW_BUILD_DEMO=ON] [-DFCPW_USE_ENOKI=OFF] [-DFCPW_ENABLE_GPU_SUPPORT=ON] ..
make -j8 // for Linux and Mac; cmake generates a visual studio project for Windows.

The FCPW_BUILD_DEMO option requires polyscope as a dependency in the deps repo. Clone polyscope using:

git clone --recurse-submodules https://github.com/nmwsharp/polyscope.git deps/polyscope

The C++ demo can be run from the build directory with the command:

./demos/demo [--useGpu]

For CPU vectorization, Enoki is included by default as a submodule. It can be disabled with the command -DFCPW_USE_ENOKI=OFF, in which case FCPW falls back to Eigen for non-vectorized CPU queries.

To include FCPW in your project without GPU support, add the following lines to your CMakeLists.txt file:

add_subdirectory(fcpw)
target_link_libraries(YOUR_TARGET fcpw)
target_include_directories(YOUR_TARGET PRIVATE ${FCPW_EIGEN_INCLUDES})
target_include_directories(YOUR_TARGET PRIVATE ${FCPW_ENOKI_INCLUDES})

If your prefer to directly include FCPW header files without CMake, then you'll have to define a few extra variables before including the library:

#define FCPW_USE_ENOKI
#define FCPW_SIMD_WIDTH 4 // change based on the SIMD width supported by your machine
#include <fcpw/fcpw.h>

Finally, GPU support can be enabled with the command FCPW_ENABLE_GPU_SUPPORT=ON. Additionally include the following lines in your CMakeLists.txt file:

target_link_libraries(YOUR_TARGET ${FCPW_SLANG_LIBRARY})
target_link_libraries(YOUR_TARGET ${FCPW_SLANG_GLSLANG_LIBRARY})
target_link_libraries(YOUR_TARGET ${FCPW_GFX_LIBRARY})
target_include_directories(YOUR_TARGET PRIVATE ${FCPW_SLANG_INCLUDES})

On Windows, you may need to download necessary DLL files from the official DirectX Shader Compiler repository on GitHub here. Copy dxil.dll and dxcompiler.dll to C:\Windows\System32\ for 64-bit systems or to C:\Windows\SysWOW64\ for 32-bit systems. This makes the DLLs available to all applications system-wide.

Python Installation

Pre-built Python wheels are available for Linux, Windows and macOS on PyPI:

pip install fcpw

These wheels can also be downloaded and installed from Releases:

pip install fcpw-*.whl

Alternatively, to build Python bindings on your local machine, first clone nanobind using:

git clone --recurse-submodules https://github.com/wjakob/nanobind.git deps/nanobind

To build and install the bindings, run:

pip install . [--config-settings=cmake.define.FCPW_ENABLE_GPU_SUPPORT=ON]

Finally, launch the Python demo from the demos folder using:

python -m pip install polyscope
python demo.py [--use_gpu]

Citation

@software{FCPW,
author = {Sawhney, Rohan},
title = {FCPW: Fastest Closest Points in the West},
version = {1.0},
year = {2021}
}

Author

Rohan Sawhney

License

Released under the MIT License.