GridAnalysis

GridAnalysis is a 2D Java/JavaFX implementation and visual laboratory for the Hagrid irregular-grid ray-tracing accelerator. It is intended to make the construction and traversal algorithms inspectable before translating them to a 3D GPU implementation such as OpenCL or CUDA.

The 2D model preserves the structure of Hagrid while translating octrees to quadtrees, eight children to four, XYZ coordinates to XY, and box faces to box edges.

Merged irregular grid	Expanded ray traversal

This repository focuses on algorithmic correctness, inspection, and traversal experimentation. It does not prescribe an optimised Java memory representation; applications are expected to choose layouts appropriate to their own CPU, GPU, interop, and allocation requirements.

Construction pipeline

The implementation follows the original pipeline:

1. Build creates the initial adaptive grid from primitive density.
2. Merge combines compatible neighbouring cells.
3. Flatten converts the hierarchy into traversal-ready cell ownership.
4. Expand enlarges cell exit bounds so a ray can safely skip neighbouring cells whose primitive references have already been considered.
5. Compress optionally stores cell bounds as unsigned 16-bit coordinates and replaces reference end offsets with -1 sentinels, matching Hagrid's compact SmallCell traversal representation.

Build and Merge are the established foundation of this port. Flatten, basic expansion, aggressive partial expansion, SmallCell compression, and an interactive traversal debugger are available for analysis.

Expansion does not change voxel ownership. It creates a second set of bounds used only to decide how far traversal may advance. These expanded bounds may overlap: correctness depends on the expanded cell containing only regions whose primitive-reference set is a subset of the selected cell's references. The optimisation is successful when it returns the same nearest primitive and hit distance as unexpanded traversal while reducing traversal steps or primitive tests.

Compressed traversal representation

Compression is a storage and memory-access optimisation applied after the cell bounds are finalised. It does not alter voxel ownership, expanded exit bounds, or the expected hit result. The Java representation mirrors Hagrid's CUDA SmallCell shape:

public record SmallCell(UShort2 min, UShort2 max, int begin) {}

UShort2 stores raw Java short values and reads them with Short.toUnsignedInt, preserving the CUDA unsigned range of 0..65535. Compression succeeds only when both virtual-grid dimensions fit in that range.

Full cells use [begin, end) reference ranges. Compressed cells remove end and instead use a compact sentinel-terminated reference array:

Full references:       cell 0 = [3, 7], cell 1 = empty, cell 2 = [9]
Compressed references: [3, 7, -1, 9, -1]
SmallCell.begin:        [0, -1, 3]

Traversal supports both representations. Compression should therefore return the same nearest hit, traversal path, and step count; its benefit is the smaller logical cell representation and sequential sentinel-based reference access. The Hagrid.compression construction option is disabled by default, while the laboratory exposes a Compress checkbox for direct comparison.

Memory-layout scope: This project does not treat the Java in-memory representation as a finished optimisation. Java records and ordinary arrays are used to express and validate Hagrid's data shapes and algorithms; a SmallCell record is not guaranteed to occupy the same packed bytes as the CUDA structure because JVM object headers, references, alignment, and runtime decisions still apply. Users targeting production CPU or GPU performance should provide an appropriate packed representation, such as primitive structure-of-arrays, direct buffers, foreign-memory layouts, TypedMemory, or native OpenCL/CUDA buffers. Choosing and benchmarking that representation is intentionally left to each integration.

Observed traversal results

The interactive 2D scenario already demonstrates the purpose of the expansion passes clearly. For the same ray placed along a primitive edge, the laboratory observed:

Construction mode	Traversal steps
Build + Merge + Flatten	52
Build + Merge + Flatten + Expand + aggressive partial expansion	10

That is a reduction of 42 cell transitions, or approximately 81% fewer traversal steps, for this particular ray and scene configuration. The expanded exit bounds let traversal cross several compatible ownership cells at once instead of stopping at every original cell boundary.

This is an illustrative result rather than a general performance benchmark. Different rays, density parameters, primitive layouts, and scene bounds produce different reductions. The important correctness check is that optimised and unoptimised traversal report the same nearest primitive and hit distance; step count and primitive-test work can then be compared safely.

Build and run

The project uses Maven with JDK 25 and JavaFX 26 Early Access.

mvn clean package
mvn javafx:run

The executable entry point is gridanalysis.ExpansionDebugLauncher; the JavaFX application class is gridanalysis.ExpansionDebug.

To open the dedicated low-resolution expansion and traversal laboratory:

mvn javafx:run@expansion-debug

Windows installer for the expansion debugger

The repository includes a jpackage build script that bundles a Java runtime, the application, JavaFX, Start Menu integration, a desktop shortcut, and the project icon into an MSI installer. Building the installer requires JDK 25, Maven, and the WiX Toolset:

powershell -ExecutionPolicy Bypass -File .\package-expansion-debug.ps1

The installer is written to target\installer. The script uses gridanalysis.ExpansionDebugLauncher as its entry point, so the installed application opens the expansion and traversal laboratory directly. To produce an EXE installer or an unpacked application image instead:

powershell -ExecutionPolicy Bypass -File .\package-expansion-debug.ps1 -Type exe
powershell -ExecutionPolicy Bypass -File .\package-expansion-debug.ps1 -Type app-image

Reusable PNG source, transparent PNG, and multi-resolution ICO assets are kept under src\main\resources\icons.

The laboratory can enable Merge, Flatten, Expand, aggressive partial expansion, and Compress independently where their pipeline dependencies permit. It can also edit Hagrid density and expansion parameters, inspect cells and reference sets, and step a ray through the resulting grid. Drag the ray origin around the outer grid boundary and drag its red arrowhead to change direction. Each traversal step reports the current voxel/cell, tested primitives, nearest hit, exit distance, and work. The reusable gridanalysis.algorithm.Traversal class contains the actual 2D cell-walking algorithm; the JavaFX laboratory only controls and visualises it.

Density model

The Java implementation uses the dimensionally correct 2D analogue of Hagrid's grid-resolution heuristic:

Rx = dx * sqrt(lambda * N / A)
Ry = dy * sqrt(lambda * N / A)

Here A is the scene or cell area, N is its primitive count, and lambda is the selected density. Uniformly scaling all scene coordinates therefore leaves the grid topology unchanged. Aspect ratio, primitive count, primitive distribution, and the density parameters still influence subdivision.

The future 3D GPU implementation should use the paper's original cube-root volume formula. Its scene dimensions scale linearly while volume scales cubically, so it has the same uniform-scale invariance in three dimensions.

Tests

Files under src/test/java are assertion-based programs with main methods, not JUnit tests. Maven compiles them during the test phase. The focused harnesses can also be run directly after packaging:

java -ea -cp "target\classes;target\test-classes" gridanalysis.algorithm.ExpandTest
java -ea -cp "target\classes;target\test-classes" gridanalysis.algorithm.BuildDensityTest
java -ea -cp "target\classes;target\test-classes" gridanalysis.algorithm.CompressTest

CompressTest checks unsigned coordinates above 32767, empty-cell encoding, sentinel placement, and rejection of dimensions that exceed 16 bits.

Interactive laboratory

The screenshots above show the merged irregular grid and an expanded traversal through it. The laboratory displays ownership cells, scene primitives, a draggable sample ray, selected traversal bounds, construction-stage controls, and live traversal diagnostics.