8
\$\begingroup\$

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:

enter image description here

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.

\$\endgroup\$
1
  • \$\begingroup\$ Could not add more relevant tags because of reputation level. \$\endgroup\$
    – sharvey
    Mar 31, 2013 at 19:37

1 Answer 1

3
\$\begingroup\$

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.
\$\endgroup\$
5
  • \$\begingroup\$ 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. \$\endgroup\$
    – sharvey
    Apr 1, 2013 at 2:35
  • \$\begingroup\$ @sharvey: Because in the picture, the agent is below and to the left of the center of the cell it is in. \$\endgroup\$ Apr 1, 2013 at 7:30
  • \$\begingroup\$ Ah, it makes sense. But just to be clear, the radius of the unit has nothing to do with the density calculation, right? \$\endgroup\$
    – sharvey
    Apr 1, 2013 at 16:26
  • \$\begingroup\$ Right, there doesn't appear to be any "radius" in the formulas you quoted that could enter into those calculations. \$\endgroup\$ Apr 1, 2013 at 23:01
  • \$\begingroup\$ I'm not closer to actually implementing it, but thanks for the answer. Guess I'll read the paper again. \$\endgroup\$
    – sharvey
    Apr 2, 2013 at 2:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .