Collision map generation and planning

A method for interference checking a path of a tool which moves in a workspace, said method performed on a computing device having a processor and memory and comprising:

• creating a workspace height map having an array of pixels each defining a height of workspace obstacles above a reference plane;
• creating a tool height map having an array of pixels each defining a height of downward-facing surfaces of the tool above a tool center point;
• generating a collision map, including defining a grid of cells in the reference plane and, for each grid cell, determining a height of the tool center point required to avoid a collision between the tool height map and the workspace height map and storing the height as a grid cell value, including positioning the tool height map with the tool center point at a location over the grid cell, defining a workspace height sub-map from a projection of the tool height map onto the workspace height map, and for each pixel of the tool height map, determining a height required in order to avoid collision with a corresponding pixel of the workspace height sub-map;
• defining a plurality of check points of the tool center point along the tool path, where for each of the check points, a corresponding grid cell in the collision map is identified by normal projection of the check point onto the reference plane, and a check point height is identified as the normal distance from the check point to the reference plane;
• performing an interference check, for each of the check points, by comparing the check point height to the grid cell value for the corresponding grid cell;
• calculating a collision avoidance waypoint for any of the check points which yield an interference in the interference check, and computing a new tool path using the collision avoidance waypoints;
• and
• sending motion commands to a machine tool, by the computing device, causing the machine tool to move the tool according to the new tool path.

A machine tool interference checking system comprising:

• a machine moving a tool in a workspace;
• and
• a computing device having a processor and memory, said computing device being in communication with the machine and configured to perform steps including;
• creating a workspace height map having an array of pixels each defining a height of workspace obstacles above a reference plane;
• creating a tool height map having an array of pixels each defining a height of downward-facing surfaces of the tool above a tool center point;
• generating a collision map, including defining a grid of cells in the reference plane and, for each grid cell, determining a height of the tool center point required to avoid an interference between the tool height map and the workspace height map, and storing the height as a grid cell value;
• defining a plurality of check points of the tool along a tool path, where for each of the check points, a corresponding grid cell in the collision map is identified by normal projection of the check point onto the reference plane, and a check point height is identified as the normal distance from the check point to the reference plane;
• and
• performing an interference check, for each of the check points, by comparing the check point height to the grid cell value for the corresponding grid cell.