Explicit Corridor Map generator

Explicit Corridor Map generator v3.4


	Generalized Voronoi Diagram		Medial Axis		Explicit Corridor Map

Purpose

The software creates a 2D annotated Medial axis (i.e. navigation mesh) for planning paths.

Download

The demo version can be downloaded here.

Compiling the framework

The main project file is voronoi2d/Voronoi2D.sln. It can be compiled by Visual Studio 2008.

Usage

ECM -r [-m] [-i] [-o] [-v]

  -r resolution Sets the number of pixels in one dimension.
                 The maximum resolution is the resolution of your screen. Default value: 1000.
  -m multiplier  Multiplies the resolution by the multiplier, increasing the quality of the ECM.
                 Default: 1.
  -i filename    Loads the 2D footprint from a .pri file. Default: 5 standard scenes are loaded.
  -o filename    Writes the Explicit Corridor Map to an .ecm or .ipe file.
                 Default IPE version: 7. Include -V 6 to save in IPE version 6 format.
  -v on|off      Switches the visualization on/off. Default: on. Must be off when m > 1.

Notes

A higher value of (resolution * multiplier) implies a higher quality output. The resolution (in pixels) is not allowed to exeed the maximum of the width and height of your screen. The value is limited by the amount of memory, e.g. on a modern PC you may use 1000 and 10, respectively.
If the visualization is on, you can interactively draw primitives such as points, circles, lines, triangles and polygons. Right-click for all options.
Drawing on an empty canvas can be done by: ECM -r 1000 -i data/empty0.pri.
Loading five standard scenes can be done by: ECM -r 1000. Select the scene using F1...F5.
Make sure that you do not force the application to use anti-aliasing when it is run. These settings can be checked in the control pannel of your graphics card.
You can use option -o to write the output to a vector image. The .ipe file can be edited with IPE 7 (or IPE 6.0) and saved to png, eps, or pdf.

Reference

Roland Geraerts. Planning Short Paths with Clearance using Explicit Corridors.
In IEEE International Conference on Robotics and Automation (ICRA2010), pp. 1997-2004, 2010.

The input file format (.pri)

The file must contain the next two lines, where xMin, yMin, xMax, yMax, and value are floats:

bounding_box xMin yMin xMax yMax
max_dist value

The parameter max_dist is used for computing the height of the distance meshes. Its value is related to the maximum distance between primitives (scaled to a unit square): Its minimum is 0 (no free space) and its maximum is sqrt(2)=1.42 (1 point obstacle in the corner). The value is computed as max_dist = 2 * max_clearance / sqrt((xMax-xMin)^2+(yMax-yMin)^2). Use key 'D' to print this value. This value is automatically computed when a .PRI file is saved.

Next, the file may contain instances of the following primitives:

point x y
disk x y radius
line x1 y1 x2 y2
line_open x1 y1 x2 y2
triangle x1 y1 x2 y2 x3 y3
polygon nrPoints x1 y1 ... xi yi
border
checked

The border primitive is a shortcut for 4x line_open placed on the bounding box of the environment. Successive primitives after the keyword checked aren't internally checked for sanity. When a .PRI file is saved, all primitives have been checked, so the keyword checked is automatically incorporated. Examples can be found in the data map of the archive (see Download).

A .pri file can be edited in any text editor, or created in the ECM program. For more complicated scenes I perform the following actions. First, I create a footprint using Maya. This footprint is then exported to wrl (and I make sure that there are no non-convex polygons.) Then, I use Callisto (included in the CMM framework) to convert wrl to xml. Next, I use this program to convert the xml file to a pri file.

The output file format (.ecm)

The file format for a Explicit Corridor Map is given below. An indentation means that the given line can occur 0, 1, or more times, depending on the value of nrVertices, nrEdges, nrSamples and nrOtherCps, respectively. The width and height are new in version 2.1 and denote the dimensions of the environment.

CMMGraph v2.2
nrVerices width height
 vertex_id x y clearance connectedComponentNr nrEdges
  edge_id distance nrSamples 
                                         clearance_min
   sample_x sample_y sample_clearance type_cell type_cell_reverse
   cp_left_x cp_left_y cp_right_x cp_right_y nrOtherCps
    cp_other_x cp_other_y

The following data types are used:

String:

CMMGraph v2.2

Integer: nrVerices, vertex_id, connectedComponentNr, nrEdges, edge_id, and nrSamples.
Enum: type_cell, type_cell_reverse. The enumeration is a bitfield that encodes the current cell (defined by the sample and its successor sample) and the previous cell (defined by the sample and its predecessor sample). While the cell type can be deduced from the closest points, it may save time in the path planning application. The enum stores information about the cell's

medial axis, bit 1-3: ma_point, ma_line, ma_parabola
left boundary, bit 4-7: left_line, left_circle_obstacle, left_circle,
leftright_point
right boundary, bit 8-10: right_line, right_circle_obstacle, right_circle
debugging information, bit 0: cell_type_not_initialized

Float: all other variables

For efficiency reasons, only connections between two vertices with vertex_id id1 and id2 are stored if id1 < id2. Hence, the opposite connections need to be added when the file is imported. Make sure that you also reverse the list of samples. Example code is provided in the Download section.

Examples

The following Explicit Corridor Maps were created by running the program using the given command line. Click on an image to see the corresponding pdf (generated by using the -o option and ipe's pdf export function). This pdf can also be opened/edited in IPE 7.

Prm1


	`ECM -r 1000 -i data/prm1.pri -o prm1.ecm -o prm1.ipe -v off`

Zelda


	`ECM -r 1000 -i data/zelda.pri -o zelda.ecm -v off`

City


	`ECM -r 1000 -i data/city.pri -o city.ecm -v off -m 4`

Military


	`ECM -r 1600 -i data/military.pri -o military.ecm -v off` Your desktop size has to be at least 1600x1600 pixels for this one to work. To obtain the same corridor map, you can alternatively use `ECM -r 800 -i data/military.pri -o military.ecm -v off -m 2`

Some statistics

The following table shows the number of nodes, edges and samples for the scenes. These statistics are based on the settings provided on this page, using version 3.31.
If you run the program, your statistics may be slightly different due to using a different cpu/gpu.

Scene	dimensions (m)	#pixels	#nodes	#edges	#samples	time (ms)
Prm1	100x100	1000x1000	94	95	287	15
Zelda	100x100	1000x1000	287	342	1245	28
City	500x500	4000x4000	1474	1653	6392	299
Military	200x200	1600x1600	56	70	283	33

Release notes

Version 2.0 (12/08/2008)
First release.

Version 2.2 (14/08/2008)
The quality of the Corridor Map can be increased by providing a multiplier > 1. This multiplier increases the resolution of the Generalized Voronoi Diagram to (resolution*multiplier) x (resolution*multiplier). This option (-m) can be used only when the visualization is switched off).

Version 2.6.2 (05/11/2008)
The output on the screen can be saved to the IPE 6.0 file format (which is a vector format). Click on the pictures below for some results. By using IPE, you can convert to e.g. EPS or PDF. If you choose for PDF, you may need to move all geometry a few pixels from the border to prevent errors with the bounding box.

Version 3.0 (10/11/2009)
The program now generates an Explicit Corridor Map. This structure is a Generalized Voronoi Diagram (or more precisely: Medial Axis) enhanced with event points. With each event point, its left and right closest point to the obstacles is stored. The diagram forms a planar subdivision and consumes O(n) memory, where n is the number of obstacle vertices. The program now outputs .ecm-files with header CMMGraph v2.0. Another difference with the previous version is that the corridor's boundaries cannot intersect an obstacle anymore, so there is no need for a an error-measure. In version 3.01, the header was changed into CMMGraph v2.1. because the dimensions of the scene are added to the file. Also, a fixed floating point precision (3 digits after the comma) is printed. In version 3.02, the bounding box as well as the stepsize were removed from the graph; the header changed into CMMGraph v2.2.

Version 3.1 (11/12/2009)
Non-convex polygons are now converted into convex ones by triangulation; (Other decomposition schemes, such as optimal convex decomposition, are implemented but not yet integrated in the code.) Non-simple polygons are discarded. The decomposition algorithms were implemented by Jacob v/d Weerd. Lines are drawn when a triangle or polygon is being constructed. Earth quake mode added (key 'e').

Version 3.2 (28/01/2009)
Fixed bug on sanity checks for the input primitives. These checks include removing dubble points and redundant colinear points.

Version 3.21 (18/02/2010)
Fixed bug dealing width limited precision for determination of the cell type. Difference layers (i.e. footprint, vertices, samples, closestPoints, medialAxis) are created when a scene is saved to IPE, so it is easy to change their properties. Use option -o to write the result to an IPE-file. This is useful when you want to create a high quality ECM (so when multiplyer m > 1).

Version 3.22 (26/02/2010)
Added support for IPE 7. A 'header' file (ipe_header.txt) is included which is used as template. This file can be edited if you want. Use command-line option -V to explicitly set the ipe output version. Currently, IPE versions 6 and 7 are allowed. The default version is 7. Fixed bug: correctly loading/saving the primitive border. Added: The number of primitives is printed.

Version 3.23 (08/03/2010)
Removed the need for retrieving the depth buffer. Tracing the Voronoi boundaries is done more efficiently (i.e. closest points are only computed when necessary). These two changes have led to halved running times / memory usage. Better handeled degenerate cases (like connected line segments whose angle is approximately 180 degrees). Hence, edges will now also run into these corners. In the GUI, the vertex numbers can be visualized using key 'n'.

Drawing and its Explicit Corridor Map.

Version 3.24 (12/03/2010)
Cleaned up the code and project. Added key 'U' which deletes the current scene. Added key 'D' which computes variable max_dist.

Version 3.3 (15/03/2010)
Improved efficiency of retrieving the color buffer and added support for a large multiplier (option -m), yielding a large effective resolution. As a test, we used the zelda environment and put it in a 8x8 block. It measured 800x800 meter and consisted of 9.556 polygons. We computed the ECM with 20.000x20.000 pixels which took 11.8 seconds. The medial axis consisted of 18.536 vertices and 22.180 edges. The ECM added 82.400 samples with their closest points.

The ECM of the Zelda8x8 environment. Click the image to download the ECM (6.2MB).

Version 3.31 (24/03/2010)
Added keyword checked for use in a pri-file. When the file is loaded, internal checks are skipped, leading to faster loading times. Cleaned up some code. Fixed bounding box integer bug (can now also be a floating point number in the PRI file) (19/04/2010).

Version 3.4 (06/07/2010)
The minimum clearance was computed incorrectly at some places (e.g. point-point situation).

Version 3.41 (23/12/2010)
When the obstacles completely filled the space, the resulting graph was not emptied. In addition, the multiplier option -m was removed and is now automatically determined. The resolution can be set using option -r.

Version 3.42 (10/01/2011)
Handling an arbitrary placed rectangular bounding box. Consequently, the environment can have an arbitrary center point and does not have to be a square anymore. Moved to graph version 2.3.

Version 3.43 (13/01/2011)
The free space does not have to be connected anymore. So, support for different islands of free space has been added.

Comments

Please send comments to me, e.g. for bugs.