How FloodFillCache Optimizes Building Footprint Detection and Prevents Tree Placement in Arnis

The FloodFillCache pre-computes polygon rasterization in parallel using Rayon, stores results in a memory-efficient CoordinateBitmap, and enables O(1) bit-tests to prevent trees from generating inside building footprints.

The Arnis repository generates Minecraft worlds from OpenStreetMap data, requiring efficient spatial queries to distinguish building interiors from outdoor areas. The FloodFillCache module (src/floodfill_cache.rs) solves this by pre-calculating filled polygon areas and converting them into compact bitmaps, eliminating redundant rasterization during tree generation.

Pre-computing Building Footprints with Parallel Flood Filling

Identifying Ways That Require Flood Fill

The cache first filters OSM elements using way_needs_flood_fill, which checks tags for buildings, landuse, leisure, amenity, natural areas, highway areas, and historic tombs. This logic resides in src/floodfill_cache.rs between lines 30-46.

Parallel Rasterization with Rayon

For each qualifying way, the system executes flood_fill_area in parallel using the Rayon crate. The results populate way_cache: FnvHashMap<u64, Vec<(i32, i32)>>, mapping OSM way IDs to world coordinate vectors. This pre-computation happens inside FloodFillCache::precompute at lines 45-71.

use arnis::floodfill_cache::FloodFillCache;
use std::time::Duration;

// Elements come from the OSM parser
let elements = /* Vec<ProcessedElement> */;

// Pre-compute all flood-fills in parallel with a 5-second timeout per operation
let floodfill_cache = FloodFillCache::precompute(
    &elements,
    Some(&Duration::from_secs(5))
);

Memory Optimization via CoordinateBitmap

Converting Coordinates to Bit-Mapped Storage

Rather than storing millions of coordinates in a HashSet, collect_building_footprints creates a CoordinateBitmap that allocates one bit per (x,z) coordinate. This reduces memory consumption by approximately 200× compared to hash-based storage, crucial for large world generation.

Querying Building Footprints

The bitmap provides O(1) containment checks via contains(x, z), enabling rapid validation of whether a specific world coordinate lies inside any building footprint. The implementation spans lines 55-73 in src/floodfill_cache.rs.

use arnis::coordinate_system::cartesian::XZBBox;

// Determine world bounds from parsed elements
let world_bbox = XZBBox::from_elements(&elements);

// Collect bit-mapped bitmap of every building footprint
let building_footprints = floodfill_cache.collect_building_footprints(
    &elements,
    &world_bbox,
);

Preventing Tree Generation Inside Buildings

During tree generation in src/element_processing/tree.rs, the Tree::create_of_type function accepts an optional reference to the building footprint bitmap. Before placing a tree at coordinates (x, z), it performs the check at lines 79-84:

// In src/element_processing/tree.rs
if let Some(footprints) = building_footprints {
    if footprints.contains(x, z) {
        return; // abort tree placement inside a building
    }
}

This check executes in constant time, allowing millions of tree placement attempts to be validated efficiently without re-rasterizing building geometries.

Implementation Example

Combining these components into a complete workflow:

use arnis::floodfill_cache::FloodFillCache;
use arnis::element_processing::tree::Tree;
use arnis::world_editor::WorldEditor;
use arnis::coordinate_system::cartesian::XZBBox;
use std::time::Duration;

// 1. Parse OSM elements
let elements = parse_osm_data(/* … */);

// 2. Pre-compute flood fills in parallel
let cache = FloodFillCache::precompute(&elements, Some(&Duration::from_secs(5)));

// 3. Build building footprint bitmap
let bbox = XZBBox::from_elements(&elements);
let footprints = cache.collect_building_footprints(&elements, &bbox);

// 4. Generate trees with collision detection
let mut editor = WorldEditor::new(/* … */);
for (x, z) in tree_candidates {
    Tree::create(&mut editor, (x, 64, z), Some(&footprints));
}

Summary

• FloodFillCache decouples expensive polygon rasterization from world generation logic by pre-computing filled areas in parallel using Rayon.
• CoordinateBitmap compresses building footprints into a bit-packed structure, reducing memory usage by ~200× compared to hash sets.
• O(1) containment tests via contains(x, z) allow tree generation to skip building interiors without re-rasterizing geometries.
• The architecture is implemented in src/floodfill_cache.rs and consumed by src/element_processing/tree.rs to prevent vegetation from spawning inside structures.

Frequently Asked Questions

How does FloodFillCache improve performance compared to on-demand rasterization?

FloodFillCache executes polygon filling once during initialization using parallel iterators (Rayon), storing results in FnvHashMap<u64, Vec<(i32, i32)>>. This eliminates redundant rasterization during tree placement, where millions of coordinate checks would otherwise require repeated geometric calculations. The cache transforms an O(n) per-check operation into an O(1) hash lookup followed by an O(1) bit test.

What is CoordinateBitmap and why is it more efficient than HashSet?

CoordinateBitmap is a bit-packed spatial index where each (x,z) coordinate maps to a single bit. Compared to a HashSet<(i32, i32)>, it reduces memory consumption by approximately 200× because it stores one bit per coordinate rather than two 32-bit integers plus hash overhead. This efficiency is critical for large Minecraft worlds where building footprints may cover millions of blocks.

Can tree generation work without the building footprint bitmap?

Yes, tree generation proceeds normally if building_footprints is None. In src/element_processing/tree.rs, the placement logic checks if let Some(footprints) = building_footprints before testing containment. When the bitmap is absent, trees generate at all candidate coordinates without building collision detection, which is useful for debugging or generating worlds without building data.

How does the timeout parameter in FloodFillCache::precompute work?

The optional timeout parameter in FloodFillCache::precompute limits the execution time for individual flood-fill operations. Passed as Option<&Duration>, it prevents stalled generation when processing extremely complex or malformed OSM polygons. If a single flood-fill exceeds the duration, the operation aborts for that specific way, allowing world generation to continue with partial data rather than crashing or hanging indefinitely.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}