tomat: waypoint corridor generator

Long time ago I implemented waypoint corridor generator inspired by work of Julien Pettré:
Julien Pettré, Jean-Paul Laumond and Daniel Thalmann
“A navigation graph for real-time crowd animation on multi-layered and uneven terrain” 2005

At that time I also was inspired of GPGPU power and opportunities. That is why I sketched this generator with ps2.0 shaders. In this paper they generated walkable corridor as union of adjacent waypoints.

The 1st step to get waypoint corridor a line which is equidistant to its boundaries.

To generate so called medial-axis or skeleton I used 2.0 shader and 2 ARGB32F render target with ping-pong approach. It was in pre CUDE epoch :)

The skeleton \ medial-axis generation steps:

I need an input image either depth or height-field of a scene. I used scene’s depth from top-down orthogonal perspective.

generate borders. I mean what borders are unwalkable areas or places where height difference between nearest pixels of render-target from previous step is greater than user defined threshold (fHeghtTreshold in shader). To accomplish that I use PSCountCopy shader.

It's supposed to be a city block of high-rise buildings with generated borders

next step is distance field generation with PSCalcDist shader. I issue this shader via full screen quad and 2 render-target with ping-pong swap. At the end of this step each pixel is contained closest distance from pixel itself to nearest border. I should run this operation not more than quarter width \ height of the render-target or widest matched walkable corridor.

generated distance field

the last step is medial-axis generation - pass of PSCalcMedialPre shader to prepare of generated distance for medial-axis generation shader and medial-axis generation pass itself with PSCalcMedial shader.

medial-axis from distance field

Finally into the render-target I get line which is located at the same distance from all borders – medial-axis I think.

Next step is a waypoint corridor generation but unfortunately I finished only half of the work as GPGPU implementation. That time I sketched this part with CPU.

To create waypoint corridor from medial-axis:

I read back last render-target then collect point position and distance from the lines. That’s how I get raw waypoints. I convert theirs position and closest border distance to world space.

But these waypoints is still is raw data as they are located at adjacent pixels of medial-axis. This redurant information is filtered with bruteforce solution. In a loop I pick up one waypoint and remove all waypoints which position inside the radius of picked one. Finaly I get nice corridor of interconnected waypoints.