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

> Learn how FloodFillCache optimizes building footprint detection. It pre-computes polygon rasterization in parallel for O(1) bit-tests, preventing trees inside buildings.

- Repository: [Louis Erbkamm/arnis](https://github.com/louis-e/arnis)
- Tags: internals
- Published: 2026-03-20

---

**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`](https://github.com/louis-e/arnis/blob/main/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`](https://github.com/louis-e/arnis/blob/main/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.

```rust
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`](https://github.com/louis-e/arnis/blob/main/src/floodfill_cache.rs).

```rust
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`](https://github.com/louis-e/arnis/blob/main/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:

```rust
// 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:

```rust
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`](https://github.com/louis-e/arnis/blob/main/src/floodfill_cache.rs) and consumed by [`src/element_processing/tree.rs`](https://github.com/louis-e/arnis/blob/main/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`](https://github.com/louis-e/arnis/blob/main/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.