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

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. – sharvey Mar 31 '13 at 19:37

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. – sharvey Apr 1 '13 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. – Ilmari Karonen Apr 1 '13 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? – sharvey Apr 1 '13 at 16:26
Right, there doesn't appear to be any "radius" in the formulas you quoted that could enter into those calculations. – Ilmari Karonen Apr 1 '13 at 23:01
I'm not closer to actually implementing it, but thanks for the answer. Guess I'll read the paper again. – sharvey Apr 2 '13 at 2:09