42 lines
3.5 KiB
Markdown
42 lines
3.5 KiB
Markdown
|
# Cost and Collision Engine Spec
|
||
|
|
|
||
|
|
This document describes the methods for ensuring "analytic correctness" while maintaining a computationally efficient cost function.
|
||
|
|
|
||
|
|
## 1. Analytic Correctness
|
||
|
|
The router balances speed and verification using a two-tier approach.
|
||
|
|
|
||
|
|
### 1.1. R-Tree Geometry Engine
|
||
|
|
The router uses an **R-Tree of Polygons** for all geometric queries.
|
||
|
|
* **Move Validation:** Every "Move" proposed by the search is checked for intersection against the R-Tree.
|
||
|
|
* **Pre-dilation for Clearance:** All obstacles and paths use a global clearance $C$. At the start of the session, all user-provided obstacles are **pre-dilated by $(W_{max} + C)/2$** for initial broad pruning. However, individual path dilation for intersection tests uses $(W_i + C)/2$ for a specific net's width $W_i$.
|
||
|
|
* **Safety Zone:** To prevent immediate collision flags for ports placed on or near obstacle boundaries, the router ignores collisions within a radius of **2nm** of start and end ports.
|
||
|
|
* **Single Layer:** All routing and collision detection occur on a single layer.
|
||
|
|
|
||
|
|
### 1.2. Cost Calculation (Soft Constraint)
|
||
|
|
The "Danger Cost" $g_{proximity}(n)$ is a function of the distance $d$ to the nearest obstacle:
|
||
|
|
$$g_{proximity}(n) = \begin{cases} \infty & \text{if } d < (W_i + C)/2 \\ \frac{k}{d^2} & \text{if } (W_i + C)/2 \le d < \text{Safety Threshold} \\ 0 & \text{if } d \ge \text{Safety Threshold} \end{cases}$$
|
||
|
|
|
||
|
|
To optimize A* search, a **Static Danger Map (Precomputed Grid)** is used for the heuristic.
|
||
|
|
* **Grid Resolution:** Default **1000nm (1µm)**.
|
||
|
|
* **Static Nature:** The grid only accounts for fixed obstacles. It is computed once at the start of the session and is **not re-computed** during the Negotiated Congestion loop.
|
||
|
|
* **Efficiency:** For a 20x20mm layout, this results in a 20k x 20k matrix.
|
||
|
|
* **Memory:** Using a `uint8` or `float16` representation, this consumes ~400-800MB (Default < 2GB). For extremely high resolution or larger areas, the system supports up to **20GB** allocation.
|
||
|
|
* **Precision:** Strict intersection checks still use the R-Tree for "analytic correctness."
|
||
|
|
|
||
|
|
## 2. Collision Detection Implementation
|
||
|
|
The system relies on `shapely` for geometry and `rtree` for spatial indexing.
|
||
|
|
1. **Arc Resolution:** Arcs are represented as polygons approximated by segments with a maximum deviation (sagitta).
|
||
|
|
2. **Intersection Test:** A "Move" is valid only if its geometry does not intersect any obstacle in the R-Tree.
|
||
|
|
3. **Self-Intersection:** Paths from the same net must not intersect themselves.
|
||
|
|
4. **No Crossings:** Strictly 2D; no crossings (vias or bridges) are supported.
|
||
|
|
|
||
|
|
## 3. Negotiated Congestion (Path R-Tree)
|
||
|
|
To handle multiple nets, the router maintains a separate R-Tree containing the dilated geometries ($C/2$) of all currently routed paths.
|
||
|
|
* **Congestion Cost:** $P \times (\text{Overlaps in Path R-Tree})$.
|
||
|
|
* **Failure Policy:** If no collision-free path is found after the max iterations, the router returns the **"least-bad" (lowest cost)** path. These paths MUST be explicitly flagged as invalid (e.g., via an `is_valid=False` attribute or a non-zero `collision_count`) so the user can identify and manually fix the failure.
|
||
|
|
|
||
|
|
## 4. Handling Global Clearances
|
||
|
|
Clearances are global. Both obstacles and paths are pre-dilated once. This ensures that any two objects maintain at least $C$ distance if their dilated versions do not intersect.
|
||
|
|
|
||
|
|
## 5. Locked Paths
|
||
|
|
The router supports **Locked Paths**—existing geometries inserted into the static Obstacle R-Tree, ensuring they are never modified or rerouted.
|