Meshes creation taking a lot of time for this map

[francocipollone]

Summary

Using maliput_osm I measured how much time it takes to convert to obj the following map:

lanelet2_s_shape_road.zip

Note: I noticed it because of using maliput_viz for checking out the maps.

franco@99dd75403bcd:~/maliput_ws_focal$ time maliput_to_obj --maliput_backend=osm --osm_file=zlanelet2_maps_scripts/lanelet2_s_shape_superelevated_road.osm
[INFO] Loading road network using osm backend implementation...
[INFO] Loading database from file: zlanelet2_maps_scripts/lanelet2_s_shape_superelevated_road.osm ...
[INFO] RoadNetwork loaded successfully.
[INFO] OBJ files location: /home/franco/maliput_ws_focal.
[INFO] Generating OBJ ...
[INFO] OBJ creation has finished.

real	0m38.100s
user	0m38.053s
sys	0m0.024s

The map is taking quite a lot and it isn't a large map at all.

Task

Investigate:

• which queries that are causing this map to take a lot to convert to obj.
• propose alternatives for speeding up query time.
  • e.g: LineStrings with an underlying kdtree for improving methods that iteratively looks for the closest point in the line string for a given xyz: francocipollone/kd_tree_line_string(wip)

[francocipollone]

First, to fall I proceeded to evaluate the time that the different query times take using maliput_osm(which relies on maliput_sparse), using as a point of comparison maliput_malidrive, which is our most mature backend.

Raw time measuring

Time the commands take for each map [in seconds]:

• Using maliput_osm backend:

  Commands \ Maps	straight_forward.osm	arc_lane.osm	arc_lane_dense.osm	circuit.osm
  ToInertialPosition	0.0000349	0.000038	0.000396724	0.0000786
  ToLanePosition	0.000057	0.00011	0.00157142	0.000165975
  ToSegmentPosition	0.000113384	0.00012	0.00206279	0.000283922
  ToRoadPosition	0.000127802	0.00019	0.00333671	0.00380658
  GetLaneBounds	0.000005538	0.000045	0.000273164	0.000024
  FindRoadPositions	0.000278457	0.000269	0.00440136	0.00376062
  Load RoadNetwork	0.00107941	0.00135913	0.776	0.0366056
  Create OBJ	0.3	1.288	57	4.866

• Using maliput_malidrive backend

  Commands	StraightForward.xodr	ArcLane.xodr	SShapeSuperelevatedRoad.xodr	Town01.xodr
  ToInertialPosition	0.00000922	0.00001148	0.00000758	0.000012574
  ToLanePosition	No Data	0.0000909	0.000275707	0.0000945
  ToSegmentPosition	No Data	0.0000884	0.000142952	0.000262818
  ToRoadPosition	0.000580999	0.000744922	0.000319315	0.0150418
  GetLaneBounds	0.00000045	0.000000754	0.0000004	0.000001269
  FindRoadPositions	0.00019737	0.000108947	0.000133448	0.0226323
  Load RoadNetwork	0.432921	0.0141271	0.142955	0.976303
  Create OBJ	13.523	0.391	1.666	13.373

In maliput_sparse, note that the higher the number of points describing the line strings, the higher the query time, therefore, the time for creating meshes will also be increased.

• In order to analyze this premise I focused the analysis on two maps in maliput_osm for evaluating this: arc_lane.osm and arc_lane_dense.osm
  • Both maps describe the same road geometry(arc-road & 2-lanes), however the number of points describing the line strings(in total) go from ~70 to ~3800 in arc_lane and arc_lane_dense maps respectively.

Analyzing the obj creation using a profiler

During the obj creation, several queries against the road geometry are performed, in order to properly analyze whether it is a lack of performance in the maliput::utility::GenerateObj algorithm or in maliput_sparse I decided to use a profiler in order to identify in which part of the code the time is spent the most.

For convenience, I decided to use Remotery, however I didn't use it directly, but via the interface that purposes ign-common3 which is more user friendly (profiler-tutorial)

• maliput branch using the profiler: maliput/francocipollone/profiler
• maliput_sparse branch using the profiler: maliput_sparse/francocipollone/profiler

Running profiler when creating obj file for:

• arc_lane.osm
  

• arc_lane_dense.osm
  

Note: These images are zoomed in in a particular part for the purposes of this document.

• maliput::utility::RenderSegment is in charge of rendering the segments of the road geometry. This method makes extensive calls to methods like maliput::api::Lane::lane_bounds and maliput::api::Lane::GetOrientation. The number of these called are the same for both maps, meaning that the maliput-to-obj algorithm is taking the same path in both cases.

• Under those api methods, maliput_sparse is doing his best in order to answer the query as quick as possible. Note how
  the methods under maliput_sparse namespace are called so many time more in arc_lane_dense than arc_lane map.
  For example, maliput_sparse::geometry::InterpolatedPointAtP is called near 2M times for arc_lane while it is called about 100M times for the arc_lane_dense map.

Diving deeper into maliput_sparse, the queries are relying on a brute force algorithm every time that the line strings are analyzed, therefore the time of each particular query is higher when having linestrings defined with a higher number of points.

In particular for the obj creation, the road geometry is "sampled" using a small sample step and the Lane::lane_bounds and Lane::GetOrientation methods are called in each step. In consequence, the time for the obj creation increases considerably for the arc_lane_dense map.

Possible Solution

For increasing performance when dealing with line string geometry queries. We should reorganize the space of each line string into a kdtree or similar. Most of the queries rely on geometrical queries that return the closest point or the two closest points of the line string to an external xyz point. We could be largely benefited by using maliput::math::kdtree class and having one kdtree space for each line string defining the lane, in a way that the linestring-related queries are answered in a performing way.

[francocipollone]

CC: @agalbachicar

[francocipollone]

Some questions/assumptions to answer/comment

• This is a particular case and in general, it isn't expected to have such
  a high density of points for defining line strings (10cm distance).

  It is true, however, it could reflect a different use case where the behavior would end up being the same: this is when having lanes that are long enough to require a similar number of points.

• This is for obj creation where orientation and lane bounds are queried a lot. What about other types of queries? The ones that an agent may want to do.

  Below an analysis is presented using delphyne_gazoo demo with one MOBIL car being spawned in the circuit.osm a map (22 lanes (between 20m to 50m each) constructed from points that are 1m distant ).

Performance analysis

I continued the analysis on the performance of this maliput_osm backend which mainly depends on it on maliput_sparse helper package.

For such a thing the following considerations were made:

• Map to be used:
  • circuit.osm: It reflects a relative regular maps(22 lanes) with a "decent" definition of the the lanes as the points describing the lanes are 1 meter away tops. Meaning that for a 50-meter lane, the lane will be defined by 50-point left and right strings.
• Agents:
  • A single MOBIL car will spawned using the delphyne_gazoo application. A simpler agent model like the RailCar agent wouldn't call as many queries as the MOBIL car would.
• Comparison: As delphyne_gazoo can be executed as well using maliput_multilane it will be used as point of comparison.

Using maliput_multilane backend

For running the gazoo demo with only one MOBIL car:

delphyne_gazoo -m maliput_multilane -n 1

Note: By default, it would also spawn three railcar agents, which I disabled by code.

Some notes from the profiler:

• Sim RTF: >99% -> 1 sec ~= 1 sec in sim
• Each simulation step is taking ~15ms
• For each step:
  • There is one method that takes most of the time:
    • RoadGeometry::ToRoadPosition: There are 12 calls that take 0.628ms in total.

Using maliput_osm backend

For running the gazoo demo with only one MOBIL car:

delphyne_gazoo -m maliput_osm -n 1

Note: By default, it would also spawn three railcar agents, which I disabled by code.

Here the results aren't that encouraging:

• Sim RTF: ~20/30 %: (You need more than 3sec per second of simulation)
• In consequence: Each simulation step is taking ~65 ms
• For each step:
• There are two methods that take most of the time:
  • RoadGeometry::ToRoadPosition: There are 12 calls that take 44.830ms in total.
    • It is worth noting this is directly affected by the Lane::ToLanePosition method 43.524ms in total as it is using brute force for finding the RoadPosition.
  • maliput::api::Lane::ToSegmentPosition: There are 42 calls that take 13.269ms in total.

Conclusions

• maliput_sparse doesn't performs as maliput_multilane in the delphyne_gazoo application
• The underlying model and the algorithm (most of them using brute force) make this backend not to be as performant as:
  • number of lanes increases.
  • number of points for describing the lanes increases.

Proposals

• There is already work on maliput for providing a base implementation for RoadGeometry::ToRoadPosition and RoadGeometry::FindRoadPosition methods.
  See Provides a default ToRoadPosition/FindRoadPosition implementations using kdtree data structure maliput#517
  I tried that branch with the same demo and I got some improvements:
  

  • The 12 calls of ToRoadPosition takes ~8 ms (vs the previous 43ms)
  • The 42 calls to maliput::api::Lane::ToSegmentPosition are still taking ~14 ms as they rely directly on the underlying geometry model.

• For reducing the query time we should better resolve mathematical queries in the underlying model. Similar to what was described in the previous post for the creation of the meshes.
  For solving queries like getting the closest point in the boundaries given a centerline's point , it is relying on brute force algorithms whose performance drastically drops for a higher number of points.
  

[francocipollone]

Closed as completed