# AI 꾸러미 — BVH 빠른 고르기 (three-mesh-bvh) — Bounding volume hierarchy (BVH) > 삼각형을 경계 상자 나무(BVH)에 나눠 담아, 광선이 맞을 만한 상자 속 삼각형만 검사해 큰 모델에서도 누른 곳을 빨리 찾는다. > 견본: https://ai-techstudio.web.app/#t/i67 이 문서를 코드 도우미(Claude Code · Cursor · ChatGPT 등)에 그대로 주면 돼요. 「## 주문서」 가 할 일, 나머지는 참고 자료예요. ## 주문서 ### 만들어 줘: BVH 빠른 고르기 (three-mesh-bvh) — Bounding volume hierarchy (BVH) #### 1. 목표 삼각형이 많은 3D 모델 고르기에서 광선 검사를 BVH 로 빠르게 해 줘 — 삼각형을 경계 상자 나무에 나눠 담고, 광선이 상자를 안 지나면 그 안은 통째로 건너뛰기. 검사한 삼각형 수를 전부 검사와 나란히 상자 나무가 보이는 설명 그림(으)로 보여 줘. #### 2. 핵심 기술 용어 - **Bounding volume hierarchy (BVH)** — 경계 상자 나무 — 상자 안에 작은 상자들 - **three-mesh-bvh (computeBoundsTree · acceleratedRaycast)** — three.js 용 BVH 라이브러리 - **Ray–AABB slab test** — 광선과 축 정렬 상자가 만나는지 (판 사이 구간 겹치기) - **Raycasting** — 광선을 쏘아 맞는 면 찾기 #### 3. 환경 - 플랫폼: three.js r186 (ES 모듈 · TypeScript, `import * as THREE from "three"`), WebGL2, 외부 라이브러리 추가 없이 - 화면: 3D · 브라우저 — PC 와 폰(가로 844×390 · 세로 390×844) 모두, 60fps 목표 #### 4. 조건 - 나무는 처음 한 번만 만들고, 모양이 바뀔 때만 다시 - 나누기는 상자의 긴 축을 따라 가운데(정렬 후 절반)에서, 잎 하나에 삼각형 6개 이하 - 상자 검사는 판 사이 구간(slab) 방식 — 광선 방향 성분이 0 이면 따로 처리 - 전부 검사와 BVH 검사의 「검사한 삼각형 수」를 나란히 보여 줘 효과를 숫자로 #### 5. 완성 기준 (이게 보이면 성공) - 광선이 움직일 때 BVH 쪽은 지나가는 상자만 밝게, 나머지 상자는 흐리게 보인다 - 맞은 삼각형(빨강)은 두 쪽이 같고, 검사한 삼각형 수는 BVH 쪽이 훨씬 적다 - 삼각형 수를 늘려도 BVH 쪽 검사 수는 조금만 는다 #### 6. 진행 방식 - 핵심 코드 위주로, 설명은 짧게. 내 프로젝트에 끼워 넣기 쉬운 함수 · 클래스로 나눠 줘. - 처음 화면에 바로 결과가 보이게, 그리고 켬/끔(또는 전/후) 비교를 할 수 있게 만들어 줘. - 그림 · 소리 · 모델 파일이 필요하면 코드로 만든 임시 대체물로 먼저 돌아가게 하고, 진짜 파일로 바꿀 자리를 표시해 줘. - 마지막에 「확인 방법」(무엇을 보면 성공인지)과 「조절할 값」 목록을 짧게 정리해 줘. - 답변과 코드 주석은 한국어로 해 줘. ## 원리 - 모든 삼각형을 검사하면 광선 하나에 N 번 — 삼각형 10만 개면 프레임마다 10만 번. - 삼각형 묶음을 감싸는 상자를 만들고, 긴 축을 따라 가운데서 둘로 나누기를 반복한다 (한 칸에 6개 이하면 멈춤). - 광선이 상자를 안 지나면 그 안 삼각형은 통째로 건너뛴다 — 보통 log N 단계만 내려간다. - three.js 에서는 three-mesh-bvh 의 geometry.computeBoundsTree() 와 Mesh.prototype.raycast = acceleratedRaycast 로 같은 일을 한다. ## 핵심 코드 — 2D 경계 상자 나무 만들기 + 광선으로 걸러 검사하기 (발췌: demos/demosSystem.ts i67 build() · boxHit() 와 draw 의 walk 를 정리) ```ts type Box = [number, number, number, number]; // x0 y0 x1 y1 interface Node { b: Box; items: number[]; kids: Node[] } // tris[i] = [ax, ay, bx, by, cx, cy] , bounds(ids) = 그 삼각형들을 감싸는 상자 function build(ids: number[]): Node { const b = bounds(ids); if (ids.length <= 6) return { b, items: ids, kids: [] }; const ax = b[2] - b[0] > b[3] - b[1] ? 0 : 1; // 긴 축 const sorted = [...ids].sort((p, q) => tris[p][ax] + tris[p][ax + 2] - (tris[q][ax] + tris[q][ax + 2])); const m = sorted.length >> 1; return { b, items: [], kids: [build(sorted.slice(0, m)), build(sorted.slice(m))] }; } // 선분 (ax,ay)→(bx,by) 이 상자를 지나는지 — 판 사이 구간 겹치기 function boxHit(b: Box, ax: number, ay: number, bx: number, by: number): boolean { let t0 = 0, t1 = 1; const d = [bx - ax, by - ay], o = [ax, ay]; for (let k = 0; k < 2; k++) { if (Math.abs(d[k]) < 1e-9) { if (o[k] < b[k] || o[k] > b[k + 2]) return false; continue; } let a1 = (b[k] - o[k]) / d[k], a2 = (b[k + 2] - o[k]) / d[k]; if (a1 > a2) [a1, a2] = [a2, a1]; t0 = Math.max(t0, a1); t1 = Math.min(t1, a2); if (t0 > t1) return false; } return true; } // 맞을 만한 삼각형만 모으기 — 상자를 안 지나면 그 아래는 통째로 건너뜀 function candidates(n: Node, ax: number, ay: number, bx: number, by: number, out: number[]): void { if (!boxHit(n.b, ax, ay, bx, by)) return; out.push(...n.items); for (const k of n.kids) candidates(k, ax, ay, bx, by, out); } ``` ## 흔한 실수 · 확인 목록 - [ ] **매 프레임 나무를 다시 만들면 전부 검사보다 느려진다** — 나무는 모양이 바뀔 때만. 물체가 움직이기만 하면 광선을 물체 좌표로 바꿔서 같은 나무로 묻는다. - [ ] **광선 방향 성분이 0 일 때 나누기를 하면 무한대 · NaN 이 나온다** — 방향 성분이 아주 작으면 시작점이 그 축 범위 안인지만 본다 (견본 boxHit). - [ ] **외곽선 껍데기 · 그림자용 복제까지 광선 대상에 넣으면 엉뚱한 것이 잡힌다** — 고를 대상 배열을 따로 두거나 껍데기의 raycast 를 빈 함수로 둔다. ## 완성 기준 체크리스트 - [ ] 광선이 움직일 때 BVH 쪽은 지나가는 상자만 밝게, 나머지 상자는 흐리게 보인다 - [ ] 맞은 삼각형(빨강)은 두 쪽이 같고, 검사한 삼각형 수는 BVH 쪽이 훨씬 적다 - [ ] 삼각형 수를 늘려도 BVH 쪽 검사 수는 조금만 는다 ## 이 기술 정보 - id: `i67` · 분류: 게임 시스템 · AI › 속도 기법 · 3D · 난이도 보통 · 폰 부담 가벼움 (폰 OK) — 나무 만들기는 처음 한 번(삼각형 N log N). 검사는 전부 검사의 수십분의 일 — 견본 110개 중 맞을 만한 칸만. - 라이브 견본 (브라우저에서 직접 조작): https://ai-techstudio.web.app/#t/i67 - 쓰면 좋을 때: 삼각형 수만 개 넘는 모델을 누르거나 끌 때 Raycaster 가 느릴 때 / 매 프레임 여러 광선(발 디딤 · 시야 검사)을 쏠 때 - 쓰지 말 때: 물체가 몇 개뿐인 판 게임 — 상자 · 보이지 않는 판으로 고르는 편이 쉽다 / 모양이 매 프레임 바뀌는 메시 — 나무를 다시 만드는 비용이 크다 (대신 단순한 충돌 모양) ## 견본 실제 코드 (라이브 견본이 돌리는 코드 — three.js · TypeScript) ### i67 견본 항목 — `src/demos/demosSystem.ts:2394` ```ts i67: { kind: '2d', caption: '광선이 맞는 삼각형 찾기 — 왼쪽은 전부 검사, 오른쪽 BVH 는 상자 나무로 맞을 만한 곳만 골라 검사', make() { type Tri = [number, number, number, number, number, number]; const R = rnd(9); const tris: Tri[] = []; while (tris.length < 110) { const a = R() * Math.PI * 2; const rad = 74 * (0.72 + 0.28 * Math.cos(5 * a)) * Math.sqrt(R()); const cx = Math.cos(a) * rad; const cy = Math.sin(a) * rad * 0.85; const s = 6; const r0 = R() * 6.28; tris.push([cx + Math.cos(r0) * s, cy + Math.sin(r0) * s, cx + Math.cos(r0 + 2.1) * s, cy + Math.sin(r0 + 2.1) * s, cx + Math.cos(r0 + 4.2) * s, cy + Math.sin(r0 + 4.2) * s]); } interface Node { b: [number, number, number, number]; items: number[]; kids: Node[]; depth: number; } const bounds = (ids: number[]): [number, number, number, number] => { let x0 = 1e9; let y0 = 1e9; let x1 = -1e9; let y1 = -1e9; for (const i of ids) { const tr = tris[i]!; for (let k = 0; k < 6; k += 2) { x0 = Math.min(x0, tr[k]!); x1 = Math.max(x1, tr[k]!); y0 = Math.min(y0, tr[k + 1]!); y1 = Math.max(y1, tr[k + 1]!); } } return [x0, y0, x1, y1]; }; const build = (ids: number[], depth: number): Node => { const b = bounds(ids); if (ids.length <= 6) return { b, items: ids, kids: [], depth }; const ax = b[2] - b[0] > b[3] - b[1] ? 0 : 1; const sorted = [...ids].sort((p, q) => tris[p]![ax]! + tris[p]![ax + 2]! - (tris[q]![ax]! + tris[q]![ax + 2]!)); const m = sorted.length >> 1; return { b, items: [], kids: [build(sorted.slice(0, m), depth + 1), build(sorted.slice(m), depth + 1)], depth }; }; const root = build(tris.map((_, i) => i), 0); const segHit = (ax: number, ay: number, bx: number, by: number, cx: number, cy: number, dx: number, dy: number): boolean => { const d = (bx - ax) * (dy - cy) - (by - ay) * (dx - cx); if (Math.abs(d) < 1e-9) return false; const u = ((cx - ax) * (dy - cy) - (cy - ay) * (dx - cx)) / d; const v = ((cx - ax) * (by - ay) - (cy - ay) * (bx - ax)) / d; return u >= 0 && u <= 1 && v >= 0 && v <= 1; }; const triHit = (tr: Tri, ax: number, ay: number, bx: number, by: number): boolean => segHit(ax, ay, bx, by, tr[0], tr[1], tr[2], tr[3]) || segHit(ax, ay, bx, by, tr[2], tr[3], tr[4], tr[5]) || segHit(ax, ay, bx, by, tr[4], tr[5], tr[0], tr[1]); const boxHit = (b: [number, number, number, number], ax: number, ay: number, bx: number, by: number): boolean => { let t0 = 0; let t1 = 1; const d = [bx - ax, by - ay]; const o = [ax, ay]; for (let k = 0; k < 2; k++) { const dk = d[k]!; const lo = b[k]!; const hi = b[k + 2]!; if (Math.abs(dk) < 1e-9) { if (o[k]! < lo || o[k]! > hi) return false; } else { let a1 = (lo - o[k]!) / dk; let a2 = (hi - o[k]!) / dk; if (a1 > a2) [a1, a2] = [a2, a1]; t0 = Math.max(t0, a1); t1 = Math.min(t1, a2); if (t0 > t1) return false; } } return true; }; return { draw(g, w, h, t) { stage(g, w, h, NAVY); const ax = -88; const ay = Math.sin(t * 0.37) * 45; const bx = 88; const by = -ay * 0.5 + Math.sin(t * 0.61 + 1) * 35; const ang = Math.atan2(by - ay, bx - ax); const panel = (ox: number, bvh: boolean): void => { box(g, ox, 22, 150, 140, 12, 'rgba(255,255,255,0.05)', bvh ? '#7af0c8' : '#ffb2a8', 1.5); g.save(); rr(g, ox, 22, 150, 140, 12); g.clip(); g.translate(ox + 75, 92); g.scale(0.82, 0.82); const tested = new Set(); const boxesOn: Node[] = []; const boxesOff: Node[] = []; if (bvh) { const walk = (n: Node): void => { if (!boxHit(n.b, ax, ay, bx, by)) { boxesOff.push(n); return; } boxesOn.push(n); n.items.forEach((i) => tested.add(i)); n.kids.forEach(walk); }; walk(root); } else tris.forEach((_, i) => tested.add(i)); if (bvh) { for (const n of boxesOff) if (n.depth <= 3) box(g, n.b[0], n.b[1], n.b[2] - n.b[0], n.b[3] - n.b[1], 2, null, 'rgba(154,176,255,0.25)', 1); for (const n of boxesOn) box(g, n.b[0], n.b[1], n.b[2] - n.b[0], n.b[3] - n.b[1], 2, null, `hsla(${150 + n.depth * 20},90%,65%,0.9)`, 1.4); } let hits = 0; tris.forEach((tr, i) => { const tt = tested.has(i); const hit = tt && triHit(tr, ax, ay, bx, by); if (hit) hits++; g.beginPath(); g.moveTo(tr[0], tr[1]); g.lineTo(tr[2], tr[3]); g.lineTo(tr[4], tr[5]); g.closePath(); g.fillStyle = hit ? '#ff5a6a' : tt ? (bvh ? '#ffd23f' : 'rgba(255,178,168,0.75)') : 'rgba(154,176,255,0.3)'; g.fill(); }); line(g, ax - 10, ay - Math.tan(ang) * 10, bx + 10, by + Math.tan(ang) * 10, '#fff', 1.8); circle(g, ax, ay, 3.5, '#fff'); g.restore(); txt(g, bvh ? 'three-mesh-bvh' : '전부 검사', ox + 75, 12, 10, bvh ? '#7af0c8' : '#ffb2a8', 'center', 800, TF); pill(g, `삼각형 검사 ${tested.size}개 · 맞음 ${hits}`, ox + 75, 176, bvh ? '#3ccf7a' : '#ff7a6b', '#10142e', 8); }; panel(8, false); panel(162, true); }, }; }, } ``` ## 관련 기술 - 먼저 알면 좋은 기술: [포인터 끌기 · 3D 고르기](https://ai-techstudio.web.app/ai/t/u79.md) `u79` - 다음에 해 볼 기술: [고정 물체 합치기 (그리기 호출 줄이기)](https://ai-techstudio.web.app/ai/t/i391.md) `i391` - 참고 문서: [three-mesh-bvh (GitHub)](https://github.com/gkjohnson/three-mesh-bvh) · [Wikipedia — Bounding volume hierarchy](https://en.wikipedia.org/wiki/Bounding_volume_hierarchy)