hit testing과 bounding box

이번에는 hit testing입니다.

사용자가 클릭했을 때 어떤 오브젝트를 선택해야 할까요? 겉으로는 간단한 질문인데, 회전, scale, 그룹, 잠금, 숨김, 얇은 선까지 들어오면 금방 진지해집니다.

hit testing은 “포인터가 어떤 도형을 가리키는가”를 결정하는 과정입니다.

두 단계로 나누자

보통 hit testing은 빠른 검사와 정확한 검사로 나눕니다.

broad phase: pointer inside AABB
narrow phase: local = inverse(M) * pointer
rectangle hit: 0 <= localX <= width and 0 <= localY <= height

먼저 AABB로 후보를 줄입니다. 빠르지만 거칠죠. 그 다음 후보에 대해서만 포인터를 local 좌표로 되돌려 정확히 검사합니다.

회전된 사각형도 local에서는 여전히 0..width, 0..height입니다. 그래서 inverse transform이 hit testing의 좋은 친구입니다.

여기서 AABB는 “얘가 후보일지도?”를 빠르게 보는 상자입니다. 최종 판정이 아닙니다. 회전된 사각형의 AABB는 실제 도형보다 큽니다. AABB 안에 들어왔다는 이유만으로 hit이라고 하면 모서리 빈 공간을 클릭해도 선택됩니다. 사용자는 “저기 빈 곳 눌렀는데 왜 잡혀요?”라고 묻고, 우리는 조용히 커피를 내려야 합니다. 그러지 맙시다.

local로 hit testing 한다는 뜻

편집기에서 포인터는 보통 screen 좌표로 들어옵니다.

screenPoint = event.client - viewportRect.left/top - viewportOrigin

그런데 오브젝트 판정은 오브젝트의 local 좌표에서 하는 편이 쉽습니다. 그래서 오브젝트의 world matrix를 뒤집어 포인터를 local로 데려옵니다.

localPoint = inverse(worldMatrix) * screenPoint

예를 들어 local 원점이 사각형 중심이고, 크기가 width = 148, height = 92라면 local bounds는 이렇게 잡을 수 있습니다.

left   = -width / 2
right  =  width / 2
top    = -height / 2
bottom =  height / 2

정확한 사각형 hit test는 그냥 범위 검사입니다.

hit =
  left <= localX <= right
  and
  top <= localY <= bottom

중요한 점은 회전이나 scale을 여기서 다시 생각하지 않는다는 겁니다. 이미 inverse(worldMatrix)가 그 복잡한 일을 처리했습니다. local로 돌아온 순간, 도형은 다시 얌전한 자기 모양이 됩니다. 약간 귀가한 도형입니다.

AABB, OBB, local bounds

용어가 비슷해서 한 번 정리하고 갑시다.

local bounds
  오브젝트 자기 좌표계의 bounds

OBB, oriented bounding box
  회전된 상태를 유지한 box

AABB, axis-aligned bounding box
  screen/world 축에 평행한 box

hit testing에서는 보통 이렇게 씁니다.

1. world AABB로 빠르게 후보를 줄인다.
2. 후보의 inverse matrix로 pointer를 local로 보낸다.
3. local shape 공식으로 정확히 검사한다.

오브젝트가 10개면 그냥 전부 검사해도 됩니다. 하지만 10,000개가 되면 broad phase가 필요합니다. 그때는 AABB를 spatial index, quadtree, grid bucket 같은 구조에 넣기도 합니다. 지금은 일단 “AABB는 후보 필터, local shape은 최종 판정”만 잡으면 됩니다.

border-radius가 있는 div는?

border-radius가 들어간 사각형은 눈으로 보기에는 그냥 사각형이 아닙니다. 모서리가 잘려 나간 rounded rect입니다. 그래서 정확한 hit test도 rounded rect 공식으로 해야 합니다.

uniform radius인 경우 가장 쉬운 방식은 이렇습니다.

1. localPoint가 전체 rect 밖이면 miss
2. corner가 아닌 중앙 영역이면 hit
3. corner 영역이면 가장 가까운 corner circle 중심까지의 거리를 검사

코드 느낌으로 쓰면:

r = min(radius, width / 2, height / 2)
nearestX = clamp(localX, left + r, right - r)
nearestY = clamp(localY, top + r, bottom - r)
hit = distance(localPoint, nearestPoint) <= r

이 공식은 rounded rect를 “사각형 + 네 모서리의 원”으로 보는 방식입니다. border-radius가 각 corner마다 다르면 corner별 radius를 따로 적용해야 합니다. CSS는 radius 합이 변보다 커지면 내부적으로 radius를 줄이는 규칙도 있으니, 디자인 에디터 모델에서는 normalized radius를 저장해두는 편이 좋습니다.

DOM의 실제 click target에 맡기면 브라우저가 알아서 해주는 부분도 있지만, 편집기에서는 보통 모델 기준 hit testing을 직접 합니다. 선택 정책, 잠금, 투명 영역, clip-path, resize handle, stroke tolerance까지 브라우저 기본 hit target만으로는 관리하기 어렵기 때문입니다.

사각형이 아닌 경우

도형마다 local shape 공식이 달라집니다. 하지만 흐름은 같습니다.

screen pointer
-> inverse(worldMatrix)
-> local pointer
-> shape-specific hit test

원이나 ellipse는 정규화된 거리로 검사합니다.

ellipseHit =
  ((localX - cx) / rx)^2 + ((localY - cy) / ry)^2 <= 1

polygon은 ray casting이나 winding number를 씁니다.

polygonHit = pointInPolygon(localPoint, localVertices)

선이나 path는 “선 위에 정확히 있는가”보다 “선에서 몇 px 이내인가”로 봅니다.

strokeHit = distanceToPath(localPoint) <= tolerance

이때 tolerance는 보통 screen pixel 기준으로 정합니다. 예를 들어 1px 선도 6px 정도의 잡기 영역을 줄 수 있습니다. zoom이 있는 환경에서는 대략 이렇게 local tolerance로 바꿉니다.

localTolerance = screenTolerance / zoom

scale이 x/y로 다르거나 matrix가 skew를 포함하면 더 조심해야 합니다. 그때는 local에서 대충 나누기보다, path를 screen으로 변환한 뒤 screen 거리로 검사하거나 matrix의 scale 성분을 따로 계산합니다.

선택 순서는 렌더링 순서와 맞춘다

사용자가 보는 화면에서 위에 있는 오브젝트가 먼저 선택되어야 합니다. 그래서 보통 위쪽 레이어부터 아래로 검사합니다.

잠긴 요소와 숨겨진 요소는 후보에서 제외합니다. 단, 제품 정책에 따라 잠긴 요소는 hover만 보이고 선택은 안 되게 할 수도 있습니다. 이런 정책은 수학보다 UX 결정에 가깝습니다.

얇은 선이나 작은 handle은 실제 shape보다 넓은 screen pixel tolerance를 둡니다. 1px 선을 정확히 1px로만 잡히게 하면 사용자가 꽤 피곤해집니다.

데모에서 볼 것

데모에서는 포인터를 움직이며 회전된 도형의 AABB와 local shape 판정이 어떻게 다른지 비교합니다. 노란색은 AABB 안에는 들어왔지만 실제 shape hit은 아닌 상태이고, 초록색은 정확한 hit입니다.

Hit 버튼을 누르면 rect, rounded, ellipse 모드가 바뀝니다. 같은 matrix를 쓰더라도 마지막 shape 공식만 바뀌는 걸 보세요. 이게 핵심입니다. 좌표 변환은 공통이고, 도형 판정은 타입별로 갈라집니다.

오늘의 핵심은 hit test를 “브라우저가 클릭한 요소 찾기”로만 보지 않는 것입니다. 편집기는 모델, 레이어 순서, 좌표 변환, UX tolerance를 함께 봐야 합니다.