# Flowfield density conversion

I'm trying to implement flowfield navigation, as described in http://grail.cs.washington.edu/projects/crowd-flows/ but I can't understand how the Density Function in Figure 4 of the paper is supposed to handle unit radius.

Has anyone ever implemented that and can provide more information?

This is the part in question:

Their algorithm seems to be using only 4 cells, pointing to the lower left of the unit, so is this some kind of kernel that needs to be applied multiple times?

Thanks.

• Could not add more relevant tags because of reputation level. Mar 31, 2013 at 19:37

## 1 Answer

No, it's not a "kernel that needs to be applied multiple times". You just apply the formulas as written, once.

It's kind of a weird rule, though, and not very clearly described. Let me try to clarify it a bit:

• First, find the four cells whose shared corner is closest to the unit. The unit will contribute a non-zero amount of density only to those cells. Call those cells A, B, C and D as in figure 4(b).

• Let Δx and Δy be the horizontal and vertical distance of the unit from the center of cell A, measured in units of one cell width/height.

• Let ρA = min(1−Δx, 1−Δy)λ, ρB = min(Δx, 1−Δy)λ, ρC = min(Δx, Δy)λ and ρD = min(1−Δx, Δy)λ, as described in the paper.

• Let the unit contribute ρA density to cell A, ρB density to cell B, ρC density to cell C and ρD density to cell D.

As I said, the rule is kind of weird, and I have no obvious geometric interpretation to offer for it. It does, however, satisfy the expected properties that:

• When the unit is exactly in the middle of any cell X, then (regardless of which of A, B, C or D we choose X to be) it contributes 1λ = 1 unit of density to cell X and 0 units of density to any other cell.

• When the unit is exactly at the corner of four cells, it contributes (1/2)λ units of density to each of the four cells (and nothing to any other cell, by definition).

However, note that, using this rule, the total amount of density contributed by a unit to all cells is not constant, not even if λ = 1. In particular, when the unit is exactly at the midpoint of the edge between two cells, it contributes (1/2)λ units of density to those two cells, and nothing to any other cell. Thus, calling the resulting value a "density" seems a bit misleading.

Edit: Another way of writing the formulas for ρA, ρB, ρC and ρD, which may make the symmetry of the definitions more apparent, is to define dX = max( |x − xX|, |y − yX| ) as the chessboard distance of the unit at (x, y) from the center of the cell X at (xX, yX), measured in cell widths/heights. Then, for any cell X,

• ρX = 0 if dX ≥ 1, and
• ρX = (1 − dX)λ otherwise.
• I don't understand the reason why the bottom left cells adjacent to the one the agent is in should receive density value while the top right ones should not. Apr 1, 2013 at 2:35
• @sharvey: Because in the picture, the agent is below and to the left of the center of the cell it is in. Apr 1, 2013 at 7:30
• Ah, it makes sense. But just to be clear, the radius of the unit has nothing to do with the density calculation, right? Apr 1, 2013 at 16:26
• Right, there doesn't appear to be any "radius" in the formulas you quoted that could enter into those calculations. Apr 1, 2013 at 23:01
• I'm not closer to actually implementing it, but thanks for the answer. Guess I'll read the paper again. Apr 2, 2013 at 2:09