pwrliang/rayjoin

1. What this repository is

RayJoin is a GPU-accelerated spatial join system focused on two queries: line-segment intersection (LSI) and point-in-polygon (PIP). A third workflow, polygon overlay, is built by combining the LSI and PIP results. The core design choice is to run these spatial operations on NVIDIA GPUs, with a ray-tracing-backed path using OptiX / RT Cores alongside software fallbacks.

2. Top-level execution boundary

The repository builds two main binaries from src/query.cc and src/overlay.cc:

- query_exec for LSI or PIP evaluation

- polyover_exec for polygon overlay

These binaries are the main entry points and wrap the same underlying data model and accelerator options.

3. High-level orchestration layer

src/app/ contains the application-facing orchestration for each workload and backend combination. It separates query/overlay behavior from accelerator choice, with variants for:

- grid

- lbvh

- rt

This is where mode selection, result checking, and output handling are coordinated.

4. Core algorithm layer

src/algo/ holds the shared algorithm logic for spatial joins:

- lsi.h for line-segment intersection

- pip.h for point-in-polygon

- rt_lsi_custom.cu and rt_pip_custom.cu for RT-specific implementations

- launch_parameters.h for GPU launch/configuration details

This layer is the main computation engine, with a backend-neutral interface and backend-specific implementations underneath.

5. Acceleration backends

The system has three distinct execution strategies:

- Uniform grid: software spatial partitioning in src/grid/

- LBVH: a linear BVH backend using the bundled third-party library in deps/lbvh/

- RT: OptiX-based ray tracing in src/rt/

This backend split is central to the architecture: the same spatial query is executed through different index structures and traversal engines.

6. Ray-tracing subsystem

src/rt/ is the hardware-accelerated path. It defines:

- the RT engine (rt_engine.cu/.h)

- primitive and SBT record abstractions

- OptiX-facing data structures

This subsystem is the bridge between spatial geometry and GPU ray tracing, and it is the part that depends most directly on NVIDIA OptiX and CUDA.

7. Geometry and map model

src/map/ contains the geometry/data model:

- polygon parsing

- bounding boxes

- planar graph representation

- scaling helpers

src/context.h and related config/flags files connect parsed polygon datasets to the runtime. The repository’s inputs are CDB-format polygon chains, and this layer is responsible for turning those into structures the accelerators can consume.

8. Output and result handling

src/app/output_chain.h and the overlay/query app headers indicate that results are not just boolean predicates; overlay workflows need to preserve intersection chains and output geometry. The -xsect_factor parameter in the README reflects this: the system preallocates space for intersection results because overlay can generate large intermediate outputs.

9. Utility and support code

src/util/ provides general-purpose infrastructure used across the system: timers, queues, bitsets, array views, rational/integer helpers, atomics, and math utilities. This is shared support code rather than a separate subsystem, but it underpins both CPU orchestration and GPU-facing data preparation.

10. Input preparation and dataset conversion

The repository assumes CDB format as the runtime input format. The misc/ directory contains preprocessing tools to convert from shapefiles or WKT and to generate derived datasets:

- wkt2shp.py, shp2cdb.py

- raster- and point-generation helpers

- TIGER/shape conversion utilities

This preprocessing pipeline is outside the runtime join path but is essential to getting datasets into RayJoin’s expected chain-based polygon representation.

11. Experiment and evaluation harness

expr/ is a large experiment/plotting area containing:

- shell scripts to run different evaluations

- logs for grid/LBVH/RT comparisons

- scripts that generate figures and speedup tables

This directory is not part of the production runtime, but it shows the intended benchmark flows: compare backends, vary enlargement factors, and evaluate scalability on both real and synthetic data.

12. Build and dependency boundaries

The project is CMake-based and targets CUDA builds with external dependencies on gflags, glog, OptiX 8, and CUDA 12.3+. The bundled deps/lbvh/ library provides the LBVH implementation. The architecture therefore spans standard C++ host code plus CUDA/OptiX device code, with explicit separation between third-party acceleration code and RayJoin’s own algorithms.

13. Operational flow to diagram

A useful architecture diagram would show:

CDB polygon inputs → map/parser layer → app/workload selection → chosen backend (grid / LBVH / RT) → query kernels / traversal engine → LSI/PIP results → overlay assembly or query output.

The main architectural distinction is between the shared geometry/query logic and the three alternative acceleration backends.