ShiboSoftwareDev/nema8-20mm-usbc-pd-controller

scripts/route-through-vias.mjs

import fs from "node:fs"

const [traceId, inputPath = "dist/index/circuit.json", outputPath = "/private/tmp/through-routed.circuit.json"] = process.argv.slice(2)
if (!traceId) throw new Error("usage: node scripts/route-through-vias.mjs <pcb_trace_id> [input] [output]")
const circuit = JSON.parse(fs.readFileSync(inputPath, "utf8"))
const target = circuit.find((element) => element.type === "pcb_trace" && element.pcb_trace_id === traceId)
if (!target) throw new Error(`trace not found: ${traceId}`)
const start = target.route[0]
const end = target.route[target.route.length - 1]
const width = Number(process.env.ROUTE_WIDTH ?? start.width ?? 0.15)
const clearance = Number(process.env.ROUTE_CLEARANCE ?? 0.08)
const gridStep = Number(process.env.ROUTE_GRID ?? 0.15)
const viaCost = Number(process.env.ROUTE_VIA_COST ?? 8)
const endpointEscapeRadius = Number(process.env.ROUTE_ENDPOINT_ESCAPE ?? 0.45)
const endpointPorts = new Set(target.connectsTo ?? [])
const board = circuit.find((element) => element.type === "pcb_board")
const innerCount = Math.max(0, (board?.num_layers ?? 2) - 2)
const layers = ["top", ...Array.from({ length: innerCount }, (_, index) => `inner${index + 1}`), "bottom"]

const distanceToSegment = (x, y, a, b) => {
  const vx = b.x - a.x
  const vy = b.y - a.y
  const denominator = vx * vx + vy * vy
  const t = denominator === 0 ? 0 : Math.max(0, Math.min(1, ((x - a.x) * vx + (y - a.y) * vy) / denominator))
  return Math.hypot(x - (a.x + t * vx), y - (a.y + t * vy))
}
const pointInInflatedRotatedRect = (x, y, obstacle) => {
  const angle = -(obstacle.rotation ?? 0) * Math.PI / 180
  const dx = x - obstacle.x
  const dy = y - obstacle.y
  const localX = dx * Math.cos(angle) - dy * Math.sin(angle)
  const localY = dx * Math.sin(angle) + dy * Math.cos(angle)
  return Math.abs(localX) <= obstacle.width / 2 + obstacle.margin &&
    Math.abs(localY) <= obstacle.height / 2 + obstacle.margin
}

const obstaclesByLayer = Object.fromEntries(layers.map((layer) => [layer, []]))
for (const element of circuit) {
  if (element.type === "pcb_trace") {
    if (element.connection_name === target.connection_name) continue
    for (let index = 1; index < element.route.length; index++) {
      const a = element.route[index - 1]
      const b = element.route[index]
      if (a.route_type !== "wire" || b.route_type !== "wire" || a.layer !== b.layer || !obstaclesByLayer[a.layer]) continue
      obstaclesByLayer[a.layer].push({ type: "segment", a, b,
        radius: (a.width ?? 0.15) / 2 + width / 2 + clearance })
    }
    continue
  }
  if (element.type === "pcb_via") {
    if (element.pcb_trace_id === traceId) continue
    for (const layer of layers) obstaclesByLayer[layer].push({ type: "circle", x: element.x, y: element.y,
      radius: element.outer_diameter / 2 + width / 2 + clearance })
    continue
  }
  if (element.type === "pcb_smtpad" && obstaclesByLayer[element.layer]) {
    if (endpointPorts.has(element.pcb_port_id)) continue
    const padWidth = element.width ?? (element.radius ? element.radius * 2 : 0.3)
    const padHeight = element.height ?? (element.radius ? element.radius * 2 : padWidth)
    obstaclesByLayer[element.layer].push({ type: "rect", x: element.x, y: element.y,
      width: padWidth, height: padHeight, rotation: element.ccw_rotation ?? 0,
      margin: width / 2 + clearance })
    continue
  }
  if (element.type === "pcb_plated_hole" || element.type === "pcb_hole") {
    const obstacleWidth = element.outer_width ?? element.outer_diameter ?? element.hole_width ?? element.hole_diameter
    const obstacleHeight = element.outer_height ?? element.outer_diameter ?? element.hole_height ?? element.hole_diameter
    if (!obstacleWidth || !obstacleHeight) continue
    for (const layer of layers) obstaclesByLayer[layer].push({ type: "rect", x: element.x, y: element.y,
      width: obstacleWidth, height: obstacleHeight, rotation: element.ccw_rotation ?? 0,
      margin: width / 2 + clearance })
  }
}

const isBlockedBy = (x, y, obstacle) =>
  obstacle.type === "circle" ? Math.hypot(x - obstacle.x, y - obstacle.y) <= obstacle.radius
    : obstacle.type === "segment" ? distanceToSegment(x, y, obstacle.a, obstacle.b) <= obstacle.radius
      : pointInInflatedRotatedRect(x, y, obstacle)
const isBlocked = (x, y, layer) => {
  if (Math.abs(x) > 9.7 || Math.abs(y) > 9.7) return true
  if (layer === start.layer && Math.hypot(x - start.x, y - start.y) <= endpointEscapeRadius) return false
  if (layer === end.layer && Math.hypot(x - end.x, y - end.y) <= endpointEscapeRadius) return false
  return obstaclesByLayer[layer].some((obstacle) => isBlockedBy(x, y, obstacle))
}

const minimum = -9.6
const size = Math.round(19.2 / gridStep) + 1
const area = size * size
const toGrid = (coordinate) => Math.max(0, Math.min(size - 1, Math.round((coordinate - minimum) / gridStep)))
const toCoordinate = (index) => minimum + index * gridStep
const keyOf = (layerIndex, xIndex, yIndex) => layerIndex * area + yIndex * size + xIndex
const decode = (key) => {
  const layerIndex = Math.floor(key / area)
  const planar = key % area
  return { layerIndex, xIndex: planar % size, yIndex: Math.floor(planar / size) }
}
const blocked = new Uint8Array(area * layers.length)
for (let layerIndex = 0; layerIndex < layers.length; layerIndex++) {
  for (let yIndex = 0; yIndex < size; yIndex++) for (let xIndex = 0; xIndex < size; xIndex++) {
    blocked[keyOf(layerIndex, xIndex, yIndex)] = isBlocked(
      toCoordinate(xIndex), toCoordinate(yIndex), layers[layerIndex],
    ) ? 1 : 0
  }
}
const startLayerIndex = layers.indexOf(start.layer)
const endLayerIndex = layers.indexOf(end.layer)
const startKey = keyOf(startLayerIndex, toGrid(start.x), toGrid(start.y))
const endKey = keyOf(endLayerIndex, toGrid(end.x), toGrid(end.y))
blocked[startKey] = 0
blocked[endKey] = 0

class MinHeap {
  values = []
  push(value) {
    this.values.push(value)
    for (let index = this.values.length - 1; index > 0;) {
      const parent = Math.floor((index - 1) / 2)
      if (this.values[parent].score <= value.score) break
      this.values[index] = this.values[parent]
      index = parent
      this.values[index] = value
    }
  }
  pop() {
    if (this.values.length === 1) return this.values.pop()
    const first = this.values[0]
    const last = this.values.pop()
    this.values[0] = last
    for (let index = 0;;) {
      const left = index * 2 + 1
      const right = left + 1
      if (left >= this.values.length) break
      let child = right < this.values.length && this.values[right].score < this.values[left].score ? right : left
      if (this.values[child].score >= this.values[index].score) break
      ;[this.values[index], this.values[child]] = [this.values[child], this.values[index]]
      index = child
    }
    return first
  }
}

const distances = new Float64Array(blocked.length)
distances.fill(Number.POSITIVE_INFINITY)
distances[startKey] = 0
const previous = new Int32Array(blocked.length)
previous.fill(-1)
const heap = new MinHeap()
heap.push({ key: startKey, score: 0 })
const planarMoves = [[1, 0], [-1, 0], [0, 1], [0, -1], [1, 1], [1, -1], [-1, 1], [-1, -1]]
while (heap.values.length > 0) {
  const current = heap.pop()
  const { key } = current
  if (key === endKey) break
  const { layerIndex, xIndex, yIndex } = decode(key)
  const currentDistance = distances[key]
  for (const [dx, dy] of planarMoves) {
    const nextX = xIndex + dx
    const nextY = yIndex + dy
    if (nextX < 0 || nextX >= size || nextY < 0 || nextY >= size) continue
    if (dx !== 0 && dy !== 0 && (blocked[keyOf(layerIndex, xIndex + dx, yIndex)] || blocked[keyOf(layerIndex, xIndex, yIndex + dy)])) continue
    const nextKey = keyOf(layerIndex, nextX, nextY)
    if (blocked[nextKey]) continue
    const nextDistance = currentDistance + Math.hypot(dx, dy)
    if (nextDistance >= distances[nextKey]) continue
    distances[nextKey] = nextDistance
    previous[nextKey] = key
    const heuristic = Math.hypot(nextX - toGrid(end.x), nextY - toGrid(end.y)) +
      (layerIndex === endLayerIndex ? 0 : viaCost)
    heap.push({ key: nextKey, score: nextDistance + heuristic })
  }
  const x = toCoordinate(xIndex)
  const y = toCoordinate(yIndex)
  let viaIsClear = Math.hypot(x - start.x, y - start.y) > endpointEscapeRadius + 0.35 &&
    Math.hypot(x - end.x, y - end.y) > endpointEscapeRadius + 0.35
  const viaInflationCells = Math.ceil(0.18 / gridStep)
  for (let candidateLayer = 0; candidateLayer < layers.length && viaIsClear; candidateLayer++) {
    for (let deltaY = -viaInflationCells; deltaY <= viaInflationCells && viaIsClear; deltaY++) {
      for (let deltaX = -viaInflationCells; deltaX <= viaInflationCells; deltaX++) {
        if (Math.hypot(deltaX, deltaY) * gridStep > 0.2) continue
        const checkX = xIndex + deltaX
        const checkY = yIndex + deltaY
        if (checkX < 0 || checkX >= size || checkY < 0 || checkY >= size ||
          blocked[keyOf(candidateLayer, checkX, checkY)]) { viaIsClear = false; break }
      }
    }
  }
  if (!viaIsClear) continue
  for (let nextLayer = 0; nextLayer < layers.length; nextLayer++) {
    if (nextLayer === layerIndex) continue
    const nextKey = keyOf(nextLayer, xIndex, yIndex)
    const nextDistance = currentDistance + viaCost
    if (nextDistance >= distances[nextKey]) continue
    distances[nextKey] = nextDistance
    previous[nextKey] = key
    const heuristic = Math.hypot(xIndex - toGrid(end.x), yIndex - toGrid(end.y)) +
      (nextLayer === endLayerIndex ? 0 : viaCost)
    heap.push({ key: nextKey, score: nextDistance + heuristic })
  }
}
if (previous[endKey] === -1) throw new Error(`no through-via route found for ${traceId}`)

const nodes = []
for (let key = endKey; key !== -1; key = previous[key]) {
  const node = decode(key)
  nodes.push({ x: toCoordinate(node.xIndex), y: toCoordinate(node.yIndex), layer: layers[node.layerIndex] })
  if (key === startKey) break
}
nodes.reverse()
const simplified = []
for (const node of nodes) {
  simplified.push(node)
  while (simplified.length >= 3) {
    const a = simplified[simplified.length - 3]
    const b = simplified[simplified.length - 2]
    const c = simplified[simplified.length - 1]
    if (a.layer !== b.layer || b.layer !== c.layer) break
    if (Math.abs((b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x)) > 1e-9) break
    simplified.splice(simplified.length - 2, 1)
  }
}
const route = [{ route_type: "wire", x: start.x, y: start.y, width, layer: start.layer }]
for (let index = 1; index < simplified.length; index++) {
  const previousNode = simplified[index - 1]
  const node = simplified[index]
  if (previousNode.layer !== node.layer) {
    route.push({ route_type: "via", x: node.x, y: node.y, from_layer: previousNode.layer,
      to_layer: node.layer, via_diameter: 0.45, via_hole_diameter: 0.3 })
  }
  route.push({ route_type: "wire", x: node.x, y: node.y, width, layer: node.layer })
}
route.push({ route_type: "wire", x: end.x, y: end.y, width, layer: end.layer })
target.route = route
for (let index = circuit.length - 1; index >= 0; index--) {
  if (circuit[index].type === "pcb_via" && circuit[index].pcb_trace_id === traceId) circuit.splice(index, 1)
}
let viaIndex = 20000
for (const point of route) if (point.route_type === "via") circuit.push({
  type: "pcb_via", pcb_via_id: `pcb_via_grid_${viaIndex++}`, pcb_trace_id: traceId,
  x: point.x, y: point.y, hole_diameter: 0.3, outer_diameter: 0.45,
  layers, from_layer: "top", to_layer: "bottom", subcircuit_id: "subcircuit_source_group_0",
})
fs.writeFileSync(outputPath, `${JSON.stringify(circuit)}\n`)
console.log(JSON.stringify(route))