📐 04. 기하학적 시스템

충돌 검출, 배치 최적화, 컨테이너 분석을 위한 기하학 모듈 상세

🎯 시스템 개요

WebPilot Engine의 기하학적 시스템은 물리적으로 정확한 3D 배치를 보장합니다.

┌─────────────────────────────────────────────────────────────┐
│                    Geometry Systems                          │
├─────────────────┬─────────────────┬─────────────────────────┤
│   Phase B       │   Phase C       │   Phase D               │
│   OBB Collision │   NavMesh       │   Raycasting            │
│                 │   Placement     │   Container             │
├─────────────────┼─────────────────┼─────────────────────────┤
│   충돌 검출      │   보행 영역     │   경계 감지             │
│   15축 SAT      │   A* 경로       │   Slabs Method          │
└─────────────────┴─────────────────┴─────────────────────────┘
                          │
                          ▼
              ┌───────────────────────┐
              │   MCTSPlacementService │
              │   (통합 배치 서비스)    │
              └───────────────────────┘

🔴 Phase B: OBB 충돌 시스템

파일 위치

src/lib/geometry/OBBCollisionSystem.ts

OBB (Oriented Bounding Box)란?

AABB(축 정렬 박스)와 달리 회전이 적용된 바운딩 박스입니다.

    AABB (Axis-Aligned)        OBB (Oriented)
    ┌──────────────┐           ╱╲
    │              │          ╱  ╲
    │    ┌───┐     │         ╱    ╲
    │    │ ◇ │     │        ╱  ◇   ╲
    │    └───┘     │       ╱        ╲
    │              │      ╱──────────╲
    └──────────────┘
    
    공간 낭비 큼               정확한 경계

데이터 구조

// src/lib/geometry/OBBCollisionSystem.ts

import * as THREE from 'three';

/**
 * OBB (Oriented Bounding Box) 정의
 */
export interface OBB {
    center: THREE.Vector3;      // 중심점
    halfExtents: THREE.Vector3; // 반 크기 (width/2, height/2, depth/2)
    rotation: THREE.Matrix3;    // 3x3 회전 행렬
}

/**
 * 충돌 검사 결과
 */
export interface CollisionResult {
    collides: boolean;
    mtv?: THREE.Vector3;        // Minimum Translation Vector
    penetrationDepth?: number;  // 침투 깊이
    contactPoint?: THREE.Vector3; // 접촉점
}

/**
 * OBB 생성 함수
 */
export function createOBB(
    center: [number, number, number],
    halfExtents: [number, number, number],
    rotation?: THREE.Matrix3
): OBB {
    return {
        center: new THREE.Vector3(...center),
        halfExtents: new THREE.Vector3(...halfExtents),
        rotation: rotation || new THREE.Matrix3().identity()
    };
}

15축 SAT (Separating Axis Theorem) 알고리즘

두 OBB가 충돌하는지 검사하려면 15개의 분리 축을 테스트해야 합니다.

/**
 * OBB 충돌 검사 (15축 SAT)
 * 
 * 테스트할 축:
 * - OBB A의 3개 면 법선 (Ax, Ay, Az)
 * - OBB B의 3개 면 법선 (Bx, By, Bz)
 * - A×B 외적 조합 (9개)
 *   - Ax×Bx, Ax×By, Ax×Bz
 *   - Ay×Bx, Ay×By, Ay×Bz
 *   - Az×Bx, Az×By, Az×Bz
 */
export function checkOBBCollision(a: OBB, b: OBB): CollisionResult {
    // A와 B의 로컬 축 추출
    const axesA = getAxes(a.rotation);  // [Ax, Ay, Az]
    const axesB = getAxes(b.rotation);  // [Bx, By, Bz]
    
    // 중심 간 벡터
    const centerDiff = new THREE.Vector3().subVectors(b.center, a.center);
    
    let minPenetration = Infinity;
    let minAxis: THREE.Vector3 | null = null;
    
    // 1. A의 3개 면 법선 테스트
    for (const axis of axesA) {
        const result = testAxis(axis, a, b, centerDiff);
        if (result.separated) {
            return { collides: false };
        }
        if (result.penetration < minPenetration) {
            minPenetration = result.penetration;
            minAxis = axis;
        }
    }
    
    // 2. B의 3개 면 법선 테스트
    for (const axis of axesB) {
        const result = testAxis(axis, a, b, centerDiff);
        if (result.separated) {
            return { collides: false };
        }
        if (result.penetration < minPenetration) {
            minPenetration = result.penetration;
            minAxis = axis;
        }
    }
    
    // 3. 외적 조합 9개 테스트
    for (const axisA of axesA) {
        for (const axisB of axesB) {
            const crossAxis = new THREE.Vector3().crossVectors(axisA, axisB);
            
            // 평행한 축은 스킵 (외적이 0에 가까움)
            if (crossAxis.lengthSq() < 0.0001) continue;
            
            crossAxis.normalize();
            
            const result = testAxis(crossAxis, a, b, centerDiff);
            if (result.separated) {
                return { collides: false };
            }
            if (result.penetration < minPenetration) {
                minPenetration = result.penetration;
                minAxis = crossAxis;
            }
        }
    }
    
    // 모든 축에서 분리되지 않음 = 충돌
    return {
        collides: true,
        mtv: minAxis?.clone().multiplyScalar(minPenetration),
        penetrationDepth: minPenetration
    };
}

/**
 * 단일 축에 대한 분리 테스트
 */
function testAxis(
    axis: THREE.Vector3,
    a: OBB, b: OBB,
    centerDiff: THREE.Vector3
): { separated: boolean; penetration: number } {
    // A를 축에 투영한 반경
    const radiusA = projectOBB(a, axis);
    // B를 축에 투영한 반경
    const radiusB = projectOBB(b, axis);
    // 중심 간 거리
    const distance = Math.abs(centerDiff.dot(axis));
    
    const penetration = (radiusA + radiusB) - distance;
    
    return {
        separated: penetration < 0,
        penetration: Math.max(0, penetration)
    };
}

/**
 * OBB를 축에 투영한 반경 계산
 */
function projectOBB(obb: OBB, axis: THREE.Vector3): number {
    const axes = getAxes(obb.rotation);
    
    return Math.abs(obb.halfExtents.x * axes[0].dot(axis)) +
           Math.abs(obb.halfExtents.y * axes[1].dot(axis)) +
           Math.abs(obb.halfExtents.z * axes[2].dot(axis));
}

BVH (Bounding Volume Hierarchy) 가속

대량의 오브젝트 충돌 검사를 O(n²)에서 O(log n)으로 최적화합니다.

// src/lib/geometry/BVHTree.ts

export class BVHTree {
    private root: BVHNode | null = null;
    
    /**
     * 새 오브젝트 삽입
     */
    insert(primitive: Primitive): void {
        const aabb = this.calculateAABB(primitive);
        if (!this.root) {
            this.root = new BVHLeaf(primitive, aabb);
        } else {
            this.root = this.insertRecursive(this.root, primitive, aabb);
        }
    }
    
    /**
     * 충돌 후보 쿼리 (O(log n))
     */
    query(aabb: AABB): Primitive[] {
        const results: Primitive[] = [];
        this.queryRecursive(this.root, aabb, results);
        return results;
    }
    
    /**
     * 배치 가능 여부 확인
     */
    canPlace(position: [number, number, number], scale: [number, number, number]): boolean {
        const aabb = this.calculateAABBFromParams(position, scale);
        const candidates = this.query(aabb);
        
        // 후보들과 정밀 OBB 충돌 검사
        for (const candidate of candidates) {
            const obb = createOBBFromPrimitive(candidate);
            const testOBB = createOBB(position, scale.map(s => s/2));
            
            if (checkOBBCollision(obb, testOBB).collides) {
                return false;
            }
        }
        
        return true;
    }
}

🟢 Phase C: NavMesh 배치 시스템

파일 위치

src/lib/geometry/NavMeshPlacementSystem.ts

개념

NavMesh(Navigation Mesh)는 보행 가능한 영역을 정의합니다.

    ┌───────────────────────────────────┐
    │  ██████████████████████████████   │
    │  █                            █   │
    │  █   ┌────┐      ┌────┐       █   │
    │  █   │장애물│      │장애물│       █   │
    │  █   └────┘      └────┘       █   │
    │  █         ░░░░░░░░░          █   │
    │  █         ░보행 가능░          █   │
    │  █         ░░░░░░░░░          █   │
    │  ██████████████████████████████   │
    └───────────────────────────────────┘

데이터 구조

// src/lib/geometry/NavMeshPlacementSystem.ts

export interface NavMesh {
    vertices: Float32Array;    // 정점 배열
    triangles: Uint32Array;    // 삼각형 인덱스
    walkableAreas: WalkableArea[];
    obstacles: Obstacle[];
}

export interface WalkableArea {
    id: string;
    polygon: THREE.Vector2[];  // 2D 폴리곤 (XZ 평면)
    height: number;            // Y 좌표
}

export interface NavMeshConfig {
    cellSize: number;          // 그리드 셀 크기 (기본: 0.3m)
    cellHeight: number;        // 높이 단위 (기본: 0.2m)
    walkableHeight: number;    // 최소 보행 높이 (기본: 2.0m)
    walkableRadius: number;    // 에이전트 반경 (기본: 0.6m)
    walkableClimb: number;     // 최대 등반 높이 (기본: 0.4m)
    walkableSlopeAngle: number; // 최대 경사각 (기본: 45도)
}

export interface NavMeshPlacementResult {
    isValid: boolean;
    position: [number, number, number];
    nearestWalkable?: [number, number, number];
    blocksPath: boolean;
}

NavMesh 생성

/**
 * Zone에서 NavMesh 생성
 */
export function createNavMeshFromZone(
    zone: Zone,
    obstacles: Obstacle[],
    config: NavMeshConfig = DEFAULT_CONFIG
): NavMesh {
    // 1. 보행 가능 영역 정의 (Zone 경계)
    const walkableArea: WalkableArea = {
        id: zone.id,
        polygon: zoneToPolygon(zone),
        height: zone.bounds.min[1]
    };
    
    // 2. 장애물 제외
    const processedAreas = subtractObstacles(walkableArea, obstacles);
    
    // 3. 삼각형 분할 (Delaunay)
    const mesh = triangulate(processedAreas);
    
    return {
        vertices: mesh.vertices,
        triangles: mesh.triangles,
        walkableAreas: processedAreas,
        obstacles
    };
}

/**
 * NavMesh 기반 배치 검증
 */
export function validatePlacement(
    position: [number, number, number],
    scale: [number, number, number],
    navMesh: NavMesh
): NavMeshPlacementResult {
    // 1. 보행 가능 영역 내 위치 확인
    const isOnWalkable = isPointOnNavMesh(
        new THREE.Vector2(position[0], position[2]),
        navMesh
    );
    
    // 2. 경로 차단 여부 확인
    const footprint = calculateFootprint(position, scale);
    const blocksPath = checkPathBlocking(footprint, navMesh);
    
    return {
        isValid: isOnWalkable && !blocksPath,
        position,
        blocksPath,
        nearestWalkable: isOnWalkable ? undefined : 
            findNearestWalkable(position, navMesh)
    };
}

A* 경로 탐색

/**
 * NavMesh 위에서 A* 경로 탐색
 */
export function findPath(
    start: THREE.Vector2,
    end: THREE.Vector2,
    navMesh: NavMesh
): THREE.Vector2[] | null {
    const openSet = new PriorityQueue<NavNode>();
    const closedSet = new Set<string>();
    const startNode = findTriangle(start, navMesh);
    const endNode = findTriangle(end, navMesh);
    
    if (!startNode || !endNode) return null;
    
    openSet.push({ node: startNode, g: 0, h: heuristic(start, end) });
    
    while (!openSet.isEmpty()) {
        const current = openSet.pop()!;
        
        if (current.node === endNode) {
            return reconstructPath(current);
        }
        
        closedSet.add(current.node.id);
        
        for (const neighbor of getNeighbors(current.node, navMesh)) {
            if (closedSet.has(neighbor.id)) continue;
            
            const g = current.g + distance(current.node, neighbor);
            const h = heuristic(neighbor.center, end);
            
            openSet.push({ node: neighbor, g, h, parent: current });
        }
    }
    
    return null; // 경로 없음
}

🔵 Phase D: Raycasting 컨테이너 시스템

파일 위치

src/lib/geometry/RaycastingContainerSystem.ts

개념

레이캐스팅으로 컨테이너 경계를 감지하고 오브젝트가 컨테이너 내부에 있는지 확인합니다.

           ceiling ────────────────────────
               ↑
               │   레이캐스트
               │
           object ●────────────→ wall
               │
               │
               ↓
           floor ─────────────────────────

Slabs Method (레이-AABB 교차)

효율적인 레이-박스 교차 검사 알고리즘입니다.

// src/lib/geometry/RaycastingContainerSystem.ts

export interface Container {
    id: string;
    bounds: THREE.Box3;
    floorY: number;
    ceilingY: number;
    walls: THREE.Plane[];
}

export interface PlacementConstraints {
    minY: number;
    maxY: number;
    validZones: Zone[];
    avoidAreas: THREE.Box3[];
}

/**
 * Slabs Method로 레이-AABB 교차 검사
 */
export function rayIntersectsAABB(
    rayOrigin: THREE.Vector3,
    rayDirection: THREE.Vector3,
    box: THREE.Box3
): { hit: boolean; tNear: number; tFar: number } {
    let tNear = -Infinity;
    let tFar = Infinity;
    
    // X축 slab
    if (Math.abs(rayDirection.x) > 1e-8) {
        const t1 = (box.min.x - rayOrigin.x) / rayDirection.x;
        const t2 = (box.max.x - rayOrigin.x) / rayDirection.x;
        tNear = Math.max(tNear, Math.min(t1, t2));
        tFar = Math.min(tFar, Math.max(t1, t2));
    } else if (rayOrigin.x < box.min.x || rayOrigin.x > box.max.x) {
        return { hit: false, tNear: 0, tFar: 0 };
    }
    
    // Y축 slab
    if (Math.abs(rayDirection.y) > 1e-8) {
        const t1 = (box.min.y - rayOrigin.y) / rayDirection.y;
        const t2 = (box.max.y - rayOrigin.y) / rayDirection.y;
        tNear = Math.max(tNear, Math.min(t1, t2));
        tFar = Math.min(tFar, Math.max(t1, t2));
    } else if (rayOrigin.y < box.min.y || rayOrigin.y > box.max.y) {
        return { hit: false, tNear: 0, tFar: 0 };
    }
    
    // Z축 slab
    if (Math.abs(rayDirection.z) > 1e-8) {
        const t1 = (box.min.z - rayOrigin.z) / rayDirection.z;
        const t2 = (box.max.z - rayOrigin.z) / rayDirection.z;
        tNear = Math.max(tNear, Math.min(t1, t2));
        tFar = Math.min(tFar, Math.max(t1, t2));
    } else if (rayOrigin.z < box.min.z || rayOrigin.z > box.max.z) {
        return { hit: false, tNear: 0, tFar: 0 };
    }
    
    return {
        hit: tNear <= tFar && tFar > 0,
        tNear,
        tFar
    };
}

/**
 * 점이 컨테이너 내부에 있는지 확인
 */
export function isPointInsideContainer(
    point: THREE.Vector3,
    container: Container
): boolean {
    return container.bounds.containsPoint(point);
}

/**
 * 오브젝트가 컨테이너 내부에 완전히 포함되는지 확인
 */
export function isObjectInsideContainer(
    objectBounds: THREE.Box3,
    container: Container
): boolean {
    return container.bounds.containsBox(objectBounds);
}

/**
 * 시맨틱 역할에 따른 Y 좌표 제약 조건
 */
export function getPlacementConstraints(
    semanticRole: SemanticRole,
    container: Container
): PlacementConstraints {
    const height = container.ceilingY - container.floorY;
    
    switch (semanticRole) {
        case 'furniture_floor':
            return {
                minY: container.floorY,
                maxY: container.floorY,  // 바닥에 고정
                validZones: [],
                avoidAreas: []
            };
            
        case 'decoration_floating':
            return {
                minY: container.floorY + height * 0.3,  // 30% 이상
                maxY: container.ceilingY - height * 0.1, // 90% 이하
                validZones: [],
                avoidAreas: []
            };
            
        case 'decoration_hanging':
            return {
                minY: container.ceilingY - height * 0.3,  // 상단 30%
                maxY: container.ceilingY,
                validZones: [],
                avoidAreas: []
            };
            
        case 'lighting':
            return {
                minY: container.floorY + height * 0.5,  // 중간 이상
                maxY: container.ceilingY,
                validZones: [],
                avoidAreas: []
            };
            
        default:
            return {
                minY: container.floorY,
                maxY: container.ceilingY,
                validZones: [],
                avoidAreas: []
            };
    }
}

🔗 MCTS 통합

모든 기하학 시스템은 MCTSPlacementService에서 통합됩니다.

// src/services/ai-pipeline/MCTSPlacementService.ts

export const MCTSPlacementService = {
    async place(layout, retrievalResult, scaleOutput): Promise<PlacementResult> {
        const bvhManager = new DynamicBVHManager();
        const placedObjects: PlacedObject[] = [];
        
        // 컨테이너 생성
        const container = createContainerFromScale(layout.containerBounds);
        
        // NavMesh 생성
        const navMesh = createNavMeshFromZone(layout.zones[0], []);
        
        for (const asset of retrievalResult.assets) {
            const scale = scaleMap[asset.id];
            const zone = findSuitableZone(asset, layout);
            
            // [Phase D] Y 좌표 제약 조건 적용
            const constraints = getPlacementConstraints(
                asset.semanticRole,
                container
            );
            
            // [Phase B] MCTS로 최적 위치 탐색 (BVH 가속)
            const optimal = this.findOptimalPositionBVH(
                asset, zone, scale, bvhManager
            );
            
            // Y 좌표 제약 적용
            optimal.position[1] = Math.max(
                constraints.minY,
                Math.min(constraints.maxY, optimal.position[1])
            );
            
            // [Phase C] NavMesh 검증
            const navResult = validatePlacement(
                optimal.position, scale, navMesh
            );
            
            if (!navResult.isValid) {
                // 가장 가까운 유효 위치로 조정
                if (navResult.nearestWalkable) {
                    optimal.position[0] = navResult.nearestWalkable[0];
                    optimal.position[2] = navResult.nearestWalkable[2];
                }
            }
            
            // BVH에 추가
            bvhManager.addObject(asset.id, optimal.position, scale);
            
            placedObjects.push({
                id: asset.id,
                position: optimal.position,
                rotation: optimal.rotation,
                scale,
                asset_path: asset.path
            });
        }
        
        return {
            objects: placedObjects,
            stats: {
                total_objects: placedObjects.length,
                collisions_resolved: bvhManager.count(),
                iterations: 50,
                placement_time_ms: performance.now() - startTime
            }
        };
    }
}

📊 성능 비교

알고리즘	시간 복잡도	100개 오브젝트	1000개 오브젝트
Brute Force	O(n²)	100ms	10,000ms
BVH 가속	O(n log n)	15ms	150ms
SAT (15축)	O(1) per pair	0.1ms	0.1ms

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

📐 04. 기하학적 시스템

🎯 시스템 개요

🔴 Phase B: OBB 충돌 시스템

파일 위치

OBB (Oriented Bounding Box)란?

데이터 구조

15축 SAT (Separating Axis Theorem) 알고리즘

BVH (Bounding Volume Hierarchy) 가속

🟢 Phase C: NavMesh 배치 시스템

파일 위치

개념

데이터 구조

NavMesh 생성

A* 경로 탐색

🔵 Phase D: Raycasting 컨테이너 시스템

파일 위치

개념

Slabs Method (레이-AABB 교차)

🔗 MCTS 통합

📊 성능 비교

FilesExpand file tree

04_GEOMETRY_SYSTEMS.md

Latest commit

History

04_GEOMETRY_SYSTEMS.md

File metadata and controls

📐 04. 기하학적 시스템

🎯 시스템 개요

🔴 Phase B: OBB 충돌 시스템

파일 위치

OBB (Oriented Bounding Box)란?

데이터 구조

15축 SAT (Separating Axis Theorem) 알고리즘

BVH (Bounding Volume Hierarchy) 가속

🟢 Phase C: NavMesh 배치 시스템

파일 위치

개념

데이터 구조

NavMesh 생성

A* 경로 탐색

🔵 Phase D: Raycasting 컨테이너 시스템

파일 위치

개념

Slabs Method (레이-AABB 교차)

🔗 MCTS 통합

📊 성능 비교