# pwrliang/rayjoin architecture

> Architecture diagram of the GitHub repository pwrliang/rayjoin, generated by GitDiagram from its file tree, README and a sample of source files (last updated 2026-05-12). It is an AI-made overview: check details against the source.

- Interactive diagram: https://gitdiagram.com/pwrliang/rayjoin
- Repository: https://github.com/pwrliang/rayjoin

## Overview

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**.

Main entry points: [`src/app/query_config.h`](https://github.com/pwrliang/rayjoin/blob/main/src/app/query_config.h) (Query app), [`src/algo/lsi.h`](https://github.com/pwrliang/rayjoin/blob/main/src/algo/lsi.h) (LSI core), [`src/algo/pip.h`](https://github.com/pwrliang/rayjoin/blob/main/src/algo/pip.h) (PIP core), [`src/app/overlay_config.h`](https://github.com/pwrliang/rayjoin/blob/main/src/app/overlay_config.h) (Overlay app)

## Diagram (Mermaid)

```mermaid
flowchart TD

subgraph group_entry["Entry points"]
  node_query_exec["Query exec<br/>binary<br/>[query.cc]"]
  node_polyover_exec["Overlay exec<br/>binary<br/>[overlay.cc]"]
  node_run_query["Query runner<br/>cuda launch<br/>[run_query.cu]"]
  node_run_overlay["Overlay runner<br/>cuda launch<br/>[run_overlay.cu]"]
end

subgraph group_app["App layer"]
  node_query_app["Query app<br/>orchestrator<br/>[query_config.h]"]
  node_overlay_app["Overlay app<br/>orchestrator<br/>[overlay_config.h]"]
  node_lsi_app["LSI app<br/>workflow<br/>[lsi.h]"]
  node_pip_app["PIP app<br/>workflow<br/>[pip.h]"]
  node_map_overlay_app["Map overlay app<br/>workflow<br/>[map_overlay.h]"]
end

subgraph group_algo["Core algorithms"]
  node_lsi_core["LSI core<br/>spatial join<br/>[lsi.h]"]
  node_pip_core["PIP core<br/>spatial join<br/>[pip.h]"]
  node_rt_lsi["RT LSI<br/>optix kernel<br/>[rt_lsi_custom.cu]"]
  node_rt_pip["RT PIP<br/>optix kernel<br/>[rt_pip_custom.cu]"]
  node_launch_params["Launch params<br/>gpu config"]
end

subgraph group_backends["Backends"]
  node_uniform_grid["Uniform grid<br/>software backend<br/>[uniform_grid.h]"]
  node_lbvh_lib["LBVH library<br/>third-party backend<br/>[lbvh.cuh]"]
  node_rt_engine["RT engine<br/>optix engine<br/>[rt_engine.cu]"]
end

subgraph group_data["Geometry model"]
  node_map_model["Map model<br/>geometry model<br/>[map.h]"]
  node_polygon_parser["Polygon parser<br/>input parser<br/>[polygon_parser.h]"]
end

subgraph group_support["Support"]
  node_context["Context<br/>[context.h]"]
  node_util["Utilities<br/>support libs<br/>[util.h]"]
end

subgraph group_experiments["Experiments"]
  node_misc_tools["Preprocess tools<br/>dataset prep<br/>[shp2cdb.py]"]
  node_expr["Experiments<br/>benchmark suite<br/>[run_query.sh]"]
end

node_query_exec -->|"orchestrates"| node_query_app
node_polyover_exec -->|"orchestrates"| node_overlay_app
node_query_exec -->|"launches"| node_run_query
node_polyover_exec -->|"launches"| node_run_overlay
node_run_query -->|"executes"| node_lsi_core
node_run_query -->|"executes"| node_pip_core
node_run_overlay -->|"combines"| node_lsi_core
node_run_overlay -->|"combines"| node_pip_core
node_query_app -->|"selects"| node_lsi_app
node_query_app -->|"selects"| node_pip_app
node_overlay_app -->|"selects"| node_map_overlay_app
node_lsi_app -->|"backend"| node_uniform_grid
node_lsi_app -->|"backend"| node_lbvh_lib
node_lsi_app -->|"backend"| node_rt_engine
node_pip_app -->|"backend"| node_uniform_grid
node_pip_app -->|"backend"| node_lbvh_lib
node_pip_app -->|"backend"| node_rt_engine
node_map_overlay_app -->|"uses"| node_lsi_core
node_map_overlay_app -->|"uses"| node_pip_core
node_lsi_core -->|"specializes"| node_rt_lsi
node_pip_core -->|"specializes"| node_rt_pip
node_rt_lsi -->|"runs on"| node_rt_engine
node_rt_pip -->|"runs on"| node_rt_engine
node_lsi_core -->|"configures"| node_launch_params
node_pip_core -->|"configures"| node_launch_params
node_query_app -->|"consumes"| node_map_model
node_overlay_app -->|"consumes"| node_map_model
node_map_model -->|"parses"| node_polygon_parser
node_polygon_parser -->|"binds"| node_context
node_query_app -->|"uses"| node_util
node_overlay_app -->|"uses"| node_util
node_misc_tools -->|"prepares"| node_map_model
node_expr -->|"benchmarks"| node_query_exec
node_expr -->|"benchmarks"| node_polyover_exec

click node_query_exec "https://github.com/pwrliang/rayjoin/blob/main/src/query.cc"
click node_polyover_exec "https://github.com/pwrliang/rayjoin/blob/main/src/overlay.cc"
click node_run_query "https://github.com/pwrliang/rayjoin/blob/main/src/run_query.cu"
click node_run_overlay "https://github.com/pwrliang/rayjoin/blob/main/src/run_overlay.cu"
click node_query_app "https://github.com/pwrliang/rayjoin/blob/main/src/app/query_config.h"
click node_overlay_app "https://github.com/pwrliang/rayjoin/blob/main/src/app/overlay_config.h"
click node_lsi_app "https://github.com/pwrliang/rayjoin/blob/main/src/app/lsi.h"
click node_pip_app "https://github.com/pwrliang/rayjoin/blob/main/src/app/pip.h"
click node_map_overlay_app "https://github.com/pwrliang/rayjoin/blob/main/src/app/map_overlay.h"
click node_lsi_core "https://github.com/pwrliang/rayjoin/blob/main/src/algo/lsi.h"
click node_pip_core "https://github.com/pwrliang/rayjoin/blob/main/src/algo/pip.h"
click node_rt_lsi "https://github.com/pwrliang/rayjoin/blob/main/src/algo/rt_lsi_custom.cu"
click node_rt_pip "https://github.com/pwrliang/rayjoin/blob/main/src/algo/rt_pip_custom.cu"
click node_launch_params "https://github.com/pwrliang/rayjoin/blob/main/src/algo/launch_parameters.h"
click node_uniform_grid "https://github.com/pwrliang/rayjoin/blob/main/src/grid/uniform_grid.h"
click node_lbvh_lib "https://github.com/pwrliang/rayjoin/blob/main/deps/lbvh/lbvh.cuh"
click node_rt_engine "https://github.com/pwrliang/rayjoin/blob/main/src/rt/rt_engine.cu"
click node_map_model "https://github.com/pwrliang/rayjoin/blob/main/src/map/map.h"
click node_polygon_parser "https://github.com/pwrliang/rayjoin/blob/main/src/map/polygon_parser.h"
click node_context "https://github.com/pwrliang/rayjoin/blob/main/src/context.h"
click node_util "https://github.com/pwrliang/rayjoin/blob/main/src/util/util.h"
click node_misc_tools "https://github.com/pwrliang/rayjoin/blob/main/misc/shp2cdb.py"
click node_expr "https://github.com/pwrliang/rayjoin/blob/main/expr/run_query.sh"

classDef toneNeutral fill:#f8fafc,stroke:#334155,stroke-width:1.5px,color:#0f172a
classDef toneBlue fill:#dbeafe,stroke:#2563eb,stroke-width:1.5px,color:#172554
classDef toneAmber fill:#fef3c7,stroke:#d97706,stroke-width:1.5px,color:#78350f
classDef toneMint fill:#dcfce7,stroke:#16a34a,stroke-width:1.5px,color:#14532d
classDef toneRose fill:#ffe4e6,stroke:#e11d48,stroke-width:1.5px,color:#881337
classDef toneIndigo fill:#e0e7ff,stroke:#4f46e5,stroke-width:1.5px,color:#312e81
classDef toneTeal fill:#ccfbf1,stroke:#0f766e,stroke-width:1.5px,color:#134e4a
class node_query_exec,node_polyover_exec,node_run_query,node_run_overlay,node_misc_tools,node_expr toneBlue
class node_query_app,node_overlay_app,node_lsi_app,node_pip_app,node_map_overlay_app toneAmber
class node_lsi_core,node_pip_core,node_rt_lsi,node_rt_pip,node_launch_params toneMint
class node_uniform_grid,node_lbvh_lib,node_rt_engine toneRose
class node_map_model,node_polygon_parser toneIndigo
class node_context,node_util toneTeal
```

## Components

### Entry points

Top-level binaries and runtime launchers.

- [Query exec](https://github.com/pwrliang/rayjoin/blob/main/src/query.cc): binary · Main executable for LSI and PIP queries. · `src/query.cc`
- [Overlay exec](https://github.com/pwrliang/rayjoin/blob/main/src/overlay.cc): binary · Main executable for polygon overlay workflows. · `src/overlay.cc`
- [Query runner](https://github.com/pwrliang/rayjoin/blob/main/src/run_query.cu): cuda launch · GPU-side query launch and dispatch boundary. · `src/run_query.cu`
- [Overlay runner](https://github.com/pwrliang/rayjoin/blob/main/src/run_overlay.cu): cuda launch · GPU-side overlay launch and dispatch boundary. · `src/run_overlay.cu`

### App layer

Workload orchestration and backend-specific wrappers.

- [Query app](https://github.com/pwrliang/rayjoin/blob/main/src/app/query_config.h): orchestrator · Shared query orchestration and mode selection. · `src/app/query_config.h`
- [Overlay app](https://github.com/pwrliang/rayjoin/blob/main/src/app/overlay_config.h): orchestrator · Shared overlay orchestration and output handling. · `src/app/overlay_config.h`
- [LSI app](https://github.com/pwrliang/rayjoin/blob/main/src/app/lsi.h): workflow · Application wrapper for line-segment intersection. · `src/app/lsi.h`
- [PIP app](https://github.com/pwrliang/rayjoin/blob/main/src/app/pip.h): workflow · Application wrapper for point-in-polygon. · `src/app/pip.h`
- [Map overlay app](https://github.com/pwrliang/rayjoin/blob/main/src/app/map_overlay.h): workflow · Application wrapper that assembles overlay chains. · `src/app/map_overlay.h`

### Core algorithms

Shared spatial join logic and GPU kernels.

- [LSI core](https://github.com/pwrliang/rayjoin/blob/main/src/algo/lsi.h): spatial join · Backend-neutral line-segment intersection logic. · `src/algo/lsi.h`
- [PIP core](https://github.com/pwrliang/rayjoin/blob/main/src/algo/pip.h): spatial join · Backend-neutral point-in-polygon logic. · `src/algo/pip.h`
- [RT LSI](https://github.com/pwrliang/rayjoin/blob/main/src/algo/rt_lsi_custom.cu): optix kernel · Ray-tracing implementation for LSI. · `src/algo/rt_lsi_custom.cu`
- [RT PIP](https://github.com/pwrliang/rayjoin/blob/main/src/algo/rt_pip_custom.cu): optix kernel · Ray-tracing implementation for PIP. · `src/algo/rt_pip_custom.cu`
- [Launch params](https://github.com/pwrliang/rayjoin/blob/main/src/algo/launch_parameters.h): gpu config · Kernel launch and GPU configuration details. · `src/algo/launch_parameters.h`

### Backends

Alternative execution and acceleration strategies.

- [Uniform grid](https://github.com/pwrliang/rayjoin/blob/main/src/grid/uniform_grid.h): software backend · Grid-based spatial partitioning backend. · `src/grid/uniform_grid.h`
- [LBVH library](https://github.com/pwrliang/rayjoin/blob/main/deps/lbvh/lbvh.cuh): third-party backend · Bundled linear BVH acceleration library. · `deps/lbvh/lbvh.cuh`
- [RT engine](https://github.com/pwrliang/rayjoin/blob/main/src/rt/rt_engine.cu): optix engine · OptiX-facing ray tracing engine and SBT plumbing. · `src/rt/rt_engine.cu`

### Geometry model

Input parsing and spatial data structures.

- [Map model](https://github.com/pwrliang/rayjoin/blob/main/src/map/map.h): geometry model · Polygon parsing, graph structure, and scaling helpers. · `src/map/map.h`
- [Polygon parser](https://github.com/pwrliang/rayjoin/blob/main/src/map/polygon_parser.h): input parser · Loads and interprets polygon chain input. · `src/map/polygon_parser.h`

### Support

Shared utilities and configuration boundaries.

- [Context](https://github.com/pwrliang/rayjoin/blob/main/src/context.h): runtime context · Connects datasets, flags, and execution state. · `src/context.h`
- [Utilities](https://github.com/pwrliang/rayjoin/blob/main/src/util/util.h): support libs · Shared helpers for timing, containers, math, and atomics. · `src/util/util.h`

### Experiments

Benchmarking, plotting, and preprocessing workflows.

- [Preprocess tools](https://github.com/pwrliang/rayjoin/blob/main/misc/shp2cdb.py): dataset prep · Input conversion and dataset generation scripts. · `misc/shp2cdb.py`
- [Experiments](https://github.com/pwrliang/rayjoin/blob/main/expr/run_query.sh): benchmark suite · Scripts and logs for query, overlay, and scalability evaluation. · `expr/run_query.sh`

## Connections

- Query exec → Query app: orchestrates · CLI binary delegates query mode handling to the app layer.
- Overlay exec → Overlay app: orchestrates · CLI binary delegates overlay workflow handling to the app layer.
- Query exec → Query runner: launches · Entry binary reaches GPU query launch path.
- Overlay exec → Overlay runner: launches · Entry binary reaches GPU overlay launch path.
- Query runner → LSI core: executes · Query runner invokes the shared LSI engine when needed.
- Query runner → PIP core: executes · Query runner invokes the shared PIP engine when needed.
- Overlay runner → LSI core: combines · Overlay workflow uses LSI as one of its constituent stages.
- Overlay runner → PIP core: combines · Overlay workflow uses PIP to classify or filter results.
- Query app → LSI app: selects · Query orchestration routes to the LSI-specific wrapper.
- Query app → PIP app: selects · Query orchestration routes to the PIP-specific wrapper.
- Overlay app → Map overlay app: selects · Overlay orchestration routes to overlay-specific handling.
- LSI app → Uniform grid: backend · LSI can run on the uniform grid backend.
- LSI app → LBVH library: backend · LSI can run on the LBVH backend.
- LSI app → RT engine: backend · LSI can run through OptiX ray tracing.
- PIP app → Uniform grid: backend · PIP can run on the uniform grid backend.
- PIP app → LBVH library: backend · PIP can run on the LBVH backend.
- PIP app → RT engine: backend · PIP can run through OptiX ray tracing.
- Map overlay app → LSI core: uses · Overlay assembly depends on intersection computation.
- Map overlay app → PIP core: uses · Overlay assembly depends on containment computation.
- LSI core → RT LSI: specializes · RT-specific LSI implementation specializes the core algorithm.
- PIP core → RT PIP: specializes · RT-specific PIP implementation specializes the core algorithm.
- RT LSI → RT engine: runs on · OptiX LSI implementation uses the RT engine boundary.
- RT PIP → RT engine: runs on · OptiX PIP implementation uses the RT engine boundary.
- LSI core → Launch params: configures · LSI uses shared GPU launch settings.
- PIP core → Launch params: configures · PIP uses shared GPU launch settings.
- Query app → Map model: consumes · Query workflows consume parsed geometry and bounding structures.
- Overlay app → Map model: consumes · Overlay workflows consume parsed geometry and graph data.
- Map model → Polygon parser: parses · Map model is built from polygon chain input.
- Polygon parser → Context: binds · Parsed input and runtime flags are tied into execution context.
- Query app → Utilities: uses · Query orchestration relies on shared utilities.
- Overlay app → Utilities: uses · Overlay orchestration relies on shared utilities.
- Preprocess tools → Map model: prepares · Preprocessing tools convert external formats into runtime geometry.
- Experiments → Query exec: benchmarks · Experiment scripts evaluate the query binary.
- Experiments → Overlay exec: benchmarks · Experiment scripts evaluate the overlay binary.