CPU hit testing

WebGL renderer가 화면을 그린다고 해서 클릭 판정도 GPU가 해야 하는 것은 아닙니다. 많은 2D 에디터는 처음에 CPU hit testing으로 충분합니다.

scene model의 geometry를 직접 검사해서 어떤 node를 눌렀는지 찾습니다.

layer order를 거꾸로 검사한다

앞에 보이는 도형이 먼저 선택되어야 합니다. 그래서 보통 draw order의 역순으로 검사합니다.

function hitTest(drawList, worldPoint) {
  for (let i = drawList.length - 1; i >= 0; i -= 1) {
    const node = drawList[i];
    if (node.locked || node.visible === false) continue;
    if (pointInNode(worldPoint, node)) return node;
  }

  return null;
}

이 방식은 단순하지만 아주 중요합니다. CSS의 event target과 z-index가 하던 일을 우리가 직접 하는 것입니다.

local 좌표로 되돌리면 쉬워진다

회전되거나 scale된 도형을 world 좌표에서 직접 검사하면 복잡합니다. 대신 pointer를 node local 좌표로 되돌립니다.

localPoint = inverse(nodeWorldMatrix) * worldPoint

그다음 local bounds를 검사합니다.

function pointInNode(worldPoint, node) {
  const localPoint = transformPoint(invert3(node.worldMatrix), worldPoint);

  return (
    localPoint.x >= 0 &&
    localPoint.y >= 0 &&
    localPoint.x <= node.width &&
    localPoint.y <= node.height
  );
}

broad phase는 나중에 붙인다

도형이 많아지면 spatial index나 bounds cache가 필요해집니다. 하지만 처음에는 전체 순회로 시작해도 됩니다.

중요한 것은 hit testing이 renderer buffer가 아니라 scene model을 기준으로 한다는 점입니다.

frame clipping까지 포함한 hit test

frame이 child를 clip한다면 hit test도 그 정책을 따라야 합니다. 보이지 않는 child가 선택되면 renderer와 input이 서로 다른 모델을 쓰는 버그입니다.

function hitTestTree(node, scene, worldPoint, hits = []) {
  if (node.visible === false || node.locked) return hits;

  if (node.type === "frame" && node.clipsContent && !pointInNode(worldPoint, node)) {
    return hits;
  }

  for (const childId of node.children ?? []) {
    hitTestTree(scene.nodesById.get(childId), scene, worldPoint, hits);
  }

  if (node.type !== "page" && pointInNode(worldPoint, node)) {
    hits.push(node);
  }

  return hits;
}

최종 선택은 hits[hits.length - 1]처럼 마지막에 그려진 node를 고르면 됩니다.

오늘의 핵심

CPU hit testing은 GPU renderer 위에서도 여전히 강력한 출발점입니다.

world pointer
-> layer order reverse scan
-> inverse node matrix
-> local bounds check