# AI 꾸러미 — 가지가 자라는 나무 (공간 군체화) — Space colonization algorithm (tree growth)
> 잎이 될 점 구름을 뿌려 두고 가장 가까운 가지 끝을 그 점 쪽으로 한 마디씩 뻗게 해, 자연스럽게 갈라지는 나무를 키운다.  
> 견본: https://ai-techstudio.web.app/#t/i444

이 문서를 코드 도우미(Claude Code · Cursor · ChatGPT 등)에 그대로 주면 돼요. 「## 주문서」 가 할 일, 나머지는 참고 자료예요.

## 주문서

### 만들어 줘: 가지가 자라는 나무 (공간 군체화) — Space colonization algorithm (tree growth)

#### 1. 목표
섬 위 사과나무 한 그루를 공간 군체화로 키워 줘 — 잎 점 구름을 향해 가지가 뻗고, 굵기는 다빈치 규칙으로. 분위기는 그림책 동화.

#### 2. 핵심 기술 용어
- **Space colonization algorithm (tree growth)** — 공간 군체화 — 끌어당기는 점을 향해 가지가 자람
- **Attraction points · kill distance** — 끌어당기는 점 · 닿으면 지워지는 거리
- **Da Vinci's rule (pipe model, r^n = Σ r_i^n)** — 부모 굵기ⁿ = 자식 굵기ⁿ 의 합
- **TubeGeometry along branch chains** — 가지 사슬을 따라 관으로 감싸기

#### 3. 환경
- 플랫폼: three.js r186 (ES 모듈 · TypeScript, `import * as THREE from "three"`), WebGL2, 외부 라이브러리 추가 없이
- 화면: 3D · 브라우저 — PC 와 폰(가로 844×390 · 세로 390×844) 모두, 60fps 목표

#### 4. 조건
- 가까운 마디 찾기는 격자(해시 칸)로 — 모든 점 × 모든 마디를 비교하면 느려진다
- 새 마디가 기존 마디와 너무 가까우면(0.4 마디 길이 안) 만들지 않는다 (같은 자리 겹침 막기)
- 굵기는 끝에서 줄기 쪽으로 다빈치 규칙, 가장 가는 끝은 최소 굵기(0.013)
- 가지 사슬은 굵은 자식으로 이어 가고 나머지 자식은 새 사슬로 — 사슬마다 관 하나
- 씨앗(seed)이 같으면 같은 나무가 나오게 무작위는 씨앗 난수로

#### 5. 완성 기준 (이게 보이면 성공)
- 노란 빛 점(잎 점)을 향해 가지가 뻗어 자라고, 닿은 점은 사라진다
- 줄기는 굵고 끝으로 갈수록 가늘어지며, 갈라지는 곳의 굵기가 자연스럽다
- 「잎 점 수」 200 ~ 1500 · 「다빈치 굵기 지수 n」 2 ~ 3.5 슬라이더로 가지 수 · 굵기가 바뀐다
- 씨앗을 바꾸면 같은 규칙의 다른 나무가 나온다

#### 6. 진행 방식
- 핵심 코드 위주로, 설명은 짧게. 내 프로젝트에 끼워 넣기 쉬운 함수 · 클래스로 나눠 줘.
- 처음 화면에 바로 결과가 보이게, 그리고 켬/끔(또는 전/후) 비교를 할 수 있게 만들어 줘.
- 그림 · 소리 · 모델 파일이 필요하면 코드로 만든 임시 대체물로 먼저 돌아가게 하고, 진짜 파일로 바꿀 자리를 표시해 줘.
- 마지막에 「확인 방법」(무엇을 보면 성공인지)과 「조절할 값」 목록을 짧게 정리해 줘.
- 답변과 코드 주석은 한국어로 해 줘.

## 원리
- 수관 모양(구 몇 개를 겹친 덩이) 안에 잎이 될 점을 수백 개(견본 650개) 뿌린다.
- 점마다 영향 거리(0.55) 안에서 가장 가까운 가지 마디를 찾고, 마디마다 「자기를 고른 점들 쪽 방향」을 모두 더한다.
- 그 방향(+ 조금 위로, + 작은 흔들림)으로 한 마디(0.085) 새로 자란다. 가지가 점에 0.13 안으로 닿으면 그 점은 지운다.
- 점이 다 먹히거나 더 자랄 곳이 없으면 멈춘다 — 점이 갈리는 곳에서 가지도 저절로 갈라진다.
- 굵기는 끝에서부터 거꾸로: 부모 굵기 = (자식 굵기ⁿ 의 합)^(1/n), 견본 n = 2.5.

## 핵심 코드 — 한 성장 단계 + 다빈치 굵기
(발췌: demos/demosModelA.ts colonize() · treeChains() 를 정리)
```ts
const DI = 0.55, DK = 0.13, D = 0.085; // 영향 거리 · 지우는 거리 · 마디 길이

// 1) 점마다 가장 가까운 마디를 골라, 그 마디에 「점 쪽 방향」을 더한다
sum.clear();
for (let a = 0; a < na; a++) {
  if (!alive[a]) continue;
  let best = -1, bd = DI * DI;
  near(nodeGrid, ax[a * 3], ax[a * 3 + 1], ax[a * 3 + 2], (i) => {
    const d = (t.x[i] - ax[a * 3]) ** 2 + (t.y[i] - ax[a * 3 + 1]) ** 2 + (t.z[i] - ax[a * 3 + 2]) ** 2;
    if (d < bd) { bd = d; best = i; }
  });
  if (best < 0) continue;
  const l = Math.sqrt(bd) || 1;
  const s = sum.get(best) ?? [0, 0, 0];
  s[0] += (ax[a * 3] - t.x[best]) / l; s[1] += (ax[a * 3 + 1] - t.y[best]) / l; s[2] += (ax[a * 3 + 2] - t.z[best]) / l;
  sum.set(best, s);
}
// 2) 그 방향(+ 살짝 위로 · 작은 흔들림)으로 한 마디 자란다
for (const [i, s] of sum) {
  let dx = s[0] + (rnd() - 0.5) * 0.15, dy = s[1] + 0.12 * Math.hypot(s[0], s[1], s[2]), dz = s[2] + (rnd() - 0.5) * 0.15;
  const l = Math.hypot(dx, dy, dz) || 1;
  addNode(t.x[i] + (dx / l) * D, t.y[i] + (dy / l) * D, t.z[i] + (dz / l) * D, i); // 너무 가까운 마디가 있으면 건너뜀
}
// 3) 새 마디에 DK 안으로 닿은 점은 지운다 (alive[a] = 0)

// 굵기: 끝에서 거꾸로 — 부모ⁿ = Σ 자식ⁿ
for (let i = n - 1; i >= 0; i--) {
  let s = 0;
  for (const c of t.kids[i]) s += Math.pow(r[c], nexp);
  r[i] = Math.max(r0, s > 0 ? Math.pow(s, 1 / nexp) : r0);
}
```

## 흔한 실수 · 확인 목록
- [ ] **모든 점과 모든 마디를 비교하면 자랄수록 느려진다** — 공간을 영향 거리 크기 칸으로 나눈 해시 격자에 마디 · 점을 넣고 이웃 27칸만 본다.
- [ ] **두 점이 마디 하나를 반대쪽으로 당기면 가지가 제자리에서 맴돈다** — 같은 자리에 이미 마디가 있으면(0.4 × 마디 길이 안) 새로 만들지 않고, 방향에 작은 흔들림을 더한다.
- [ ] **굵기를 높이로만 정하면 갈라지는 곳이 뚝 끊겨 보인다** — 다빈치 규칙으로 끝에서부터 쌓아 올린다. n 이 2 ~ 3 사이면 자연스럽다.

## 완성 기준 체크리스트
- [ ] 노란 빛 점(잎 점)을 향해 가지가 뻗어 자라고, 닿은 점은 사라진다
- [ ] 줄기는 굵고 끝으로 갈수록 가늘어지며, 갈라지는 곳의 굵기가 자연스럽다
- [ ] 「잎 점 수」 200 ~ 1500 · 「다빈치 굵기 지수 n」 2 ~ 3.5 슬라이더로 가지 수 · 굵기가 바뀐다
- [ ] 씨앗을 바꾸면 같은 규칙의 다른 나무가 나온다

## 이 기술 정보
- id: `i444` · 분류: 3D 모델 · 캐릭터 › 3D 모델링 · 절차 · 3D · 난이도 보통 · 폰 부담 보통 (폰 주의) — 키우기는 한 번(수십 ms), 격자(칸 0.55)로 가까운 마디만 찾는다. 성장 단계 16장의 관 모양을 미리 지어 두어 보기는 가볍다.
- 라이브 견본 (브라우저에서 직접 조작): https://ai-techstudio.web.app/#t/i444
- 쓰면 좋을 때: 같은 규칙으로 모양이 조금씩 다른 나무 여러 그루가 필요할 때 / 수관 모양(둥근 · 납작 · 원뿔)을 정해 두고 그 안을 가지로 채우고 싶을 때 / 나무가 자라는 장면을 보여 줄 때
- 쓰지 말 때: 고사리 · 산호처럼 규칙이 뚜렷한 모양 — 대신 L-시스템(i445) / 동화풍 뭉게 덩이가 주인공일 때 — 대신 뭉게 나무(i538)

## 견본 실제 코드 (라이브 견본이 돌리는 코드 — three.js · TypeScript)
### demoColony — `src/demos/demosModelA.ts:733`
```ts
function demoColony(): Scene3D {
  const st = new Stage({ cam: [0, 1.9, 6.4], look: [0, 1.62, 0], island: 1.5 });
  const bark = new THREE.MeshStandardMaterial({ vertexColors: true, map: barkTexture(), roughness: 0.9, polygonOffset: true, polygonOffsetFactor: 1, polygonOffsetUnits: 1 });
  const trunk = st.model(new THREE.Mesh(new THREE.BufferGeometry(), bark));
  st.spin.add(trunk);
  const blob = leafBlobGeo();
  const leafMat = new THREE.MeshStandardMaterial({ roughness: 0.72, polygonOffset: true, polygonOffsetFactor: 1, polygonOffsetUnits: 1 });
  let leaves = st.model(new THREE.InstancedMesh(blob, leafMat, 1));
  const appleG = mergeGeometries([colorAttr(new THREE.SphereGeometry(1, 14, 10), 0xe8413a), colorAttr(new THREE.CylinderGeometry(0.08, 0.08, 0.6, 5).translate(0, 1, 0), 0x6b4a2a)])!;
  const apples = new THREE.InstancedMesh(appleG, new THREE.MeshPhysicalMaterial({ vertexColors: true, roughness: 0.3, clearcoat: 0.6 }), 10);
  apples.castShadow = true;
  st.spin.add(apples);
  const pts = new THREE.Points(new THREE.BufferGeometry(), pointsMat());
  st.spin.add(pts);
  const S = { seed: 3, count: 650, nexp: 2.5, auto: true, stage: 0, showPts: true };
  let col: Colony;
  let stages: THREE.BufferGeometry[] = [];
  let stageAt: number[] = [];
  let tips: number[] = [];
  let tipScale: number[] = [];
  let tipColor: THREE.Color[] = [];
  let appleTips: number[] = [];
  let killSorted: Float32Array = new Float32Array();
  const brown = new THREE.Color(0x6e4429);
  const light = new THREE.Color(0xb58456);
  const barkCol = (r: number, o: THREE.Color): void => {
    o.copy(brown).lerp(light, clamp(1 - r / 0.1, 0, 1));
  };
  const buildStages = (): void => {
    for (const g of stages) g.dispose();
    stages = [];
    stageAt = [];
    const K = 16;
    for (let k = 0; k < K; k++) {
      const s = Math.round(col.imax * Math.pow(k / (K - 1), 0.9));
      stageAt.push(s);
      stages.push(tubeGeo(treeChains(col, (i) => col.birth[i]! <= s, 0.013, S.nexp), 7, barkCol));
    }
  };
  const build = (): void => {
    const t0 = performance.now();
    col = colonize(S.seed, S.count);
    buildStages();
    const R0 = rng(S.seed + 5);
    tips = [];
    for (let i = 1; i < col.x.length; i++) if (!col.kids[i]!.length && col.birth[i]! > 0) tips.push(i);
    tipScale = tips.map(() => 0.12 + R0() * 0.06);
    const greens = [0x5fb34a, 0x76c655, 0x4f9e44, 0x8bd365, 0x69b84d];
    tipColor = tips.map((i) => new THREE.Color(greens[Math.floor(R0() * greens.length)]!).offsetHSL(0, 0, (col.y[i]! - 2) * 0.05));
    appleTips = tips.filter((i) => Math.hypot(col.x[i]!, col.z[i]!) > 0.75 && col.y[i]! < 2.1).sort(() => R0() - 0.5).slice(0, 10);
    st.spin.remove(leaves);
    st.models.splice(st.models.indexOf(leaves), 1);
    leaves.dispose();
    leaves = st.model(new THREE.InstancedMesh(blob, leafMat, Math.max(1, tips.length)));
    tips.forEach((_, k) => leaves.setColorAt(k, tipColor[k]!));
    st.spin.add(leaves);
    const pg = new THREE.BufferGeometry();
    pg.setAttribute('position', new THREE.BufferAttribute(col.ax, 3));
    pg.setAttribute('aKill', new THREE.BufferAttribute(col.kill, 1));
    pts.geometry.dispose();
    pts.geometry = pg;
    killSorted = col.kill.slice().sort();
    buildMs = performance.now() - t0;
  };
  let buildMs = 0;
  build();
  const m4 = new THREE.Matrix4();
  const q = new THREE.Quaternion();
  const sv = new THREE.Vector3();
  const pv = new THREE.Vector3();
  let lastG = -1;
  const setG = (g: number): void => {
    let k = 0;
    while (k + 1 < stageAt.length && stageAt[k + 1]! <= g) k++;
    trunk.geometry = stages[k]!;
    if (Math.abs(g - lastG) < 1e-3) return;
    lastG = g;
    tips.forEach((i, n) => {
      const e = easeBack((g - col.birth[i]! - 1) / 6) * tipScale[n]!;
      pv.set(col.x[i]!, col.y[i]! + 0.03, col.z[i]!);
      q.setFromAxisAngle(sv.set(0, 1, 0), i * 1.7);
      leaves.setMatrixAt(n, m4.compose(pv, q, sv.setScalar(Math.max(1e-4, e))));
    });
    leaves.instanceMatrix.needsUpdate = true;
    appleTips.forEach((i, n) => {
      const e = easeBack((g - col.imax - 5 - n * 0.6) / 3) * 0.055;
      pv.set(col.x[i]! * 1.08, col.y[i]! - 0.12, col.z[i]! * 1.08);
      apples.setMatrixAt(n, m4.compose(pv, q.identity(), sv.setScalar(Math.max(1e-4, e))));
    });
    apples.count = appleTips.length;
    apples.instanceMatrix.needsUpdate = true;
    (pts.material as THREE.ShaderMaterial).uniforms['uG']!.value = g;
  };
  return st.out({
    update(t) {
      let g: number;
      const gEnd = col.imax + 12;
      if (S.auto) {
        const T = 9.5;
        const k = t % T;
        g = k < 6.5 ? (k / 6.5) * gEnd : k < 8.9 ? gEnd : gEnd * (1 - ease((k - 8.9) / 0.6));
      } else g = (S.stage / 15) * gEnd;
      setG(g);
      st.spin.rotation.y = t * 0.22;
      pts.visible = S.showPts;
      let alive = 0;
      for (let lo = 0, hi = killSorted.length; lo < hi; ) {
        const mid = (lo + hi) >> 1;
        if (killSorted[mid]! > g) hi = mid;
        else lo = mid + 1;
        alive = killSorted.length - lo;
      }
      st.hud.tl.set(`▲ 삼각형 ${fmt(st.tris())}`);
      st.hud.bl.set(`남은 잎 점 ${fmt(alive)} · 마디 ${fmt(col.x.length)} · 생성 ${buildMs.toFixed(0)}ms`);
    },
    controls: [
      { type: 'toggle', label: '자동 재생 (자라기)', value: true, on: (v) => (S.auto = v) },
      { type: 'range', label: '자라기 단계', min: 0, max: 15, step: 1, value: 0, on: (v) => ((S.stage = v), (S.auto = false)) },
      { type: 'range', label: '잎 점 수 (끌어당기는 점)', min: 200, max: 1500, step: 50, value: 650, on: (v) => ((S.count = v), build(), (lastG = -1)) },
      { type: 'range', label: '다빈치 굵기 지수 n', min: 2, max: 3.5, step: 0.1, value: 2.5, on: (v) => ((S.nexp = v), buildStages()) },
      { type: 'toggle', label: '잎 점 보기', value: true, on: (v) => (S.showPts = v) },
      { type: 'toggle', label: '와이어프레임', value: false, on: (v) => (st.wire.on = v) },
      { type: 'button', label: '새로 만들기 (시드)', on: () => ((S.seed += 1), build(), (lastG = -1)) },
    ],
    dispose() {
      for (const g of stages) g.dispose();
      blob.dispose();
    },
  });
}
```

### i444 견본 항목 — `src/demos/demosModelA.ts:2740`
```ts
  i444: { kind: '3d', caption: '잎이 될 점(노란 빛)을 향해 가지가 뻗어 자람 — 점을 먹으면 사라지고, 굵기는 다빈치 규칙', make: demoColony }
```

## 관련 기술
- 먼저 알면 좋은 기술: [L-시스템 나무 · 풀 (규칙으로 그리기)](https://ai-techstudio.web.app/ai/t/i445.md) `i445`
- 다음에 해 볼 기술: [동화 뭉게 나무 (구 법선 잎 · 층별 바람)](https://ai-techstudio.web.app/ai/t/i538.md) `i538` · [표면에 디테일 흩뿌리기 (풀 · 꽃 · 자갈)](https://ai-techstudio.web.app/ai/t/i455.md) `i455`
- 참고 문서: [Runions 외 — Modeling Trees with a Space Colonization Algorithm (2007)](http://algorithmicbotany.org/papers/colonization.egwnp2007.html)