La Analogía de Flatland
Flatland (1884) de Edwin Abbott: habitantes de un plano bidimensional. Perciben longitud y anchura. Profundidad: la tercera dimensión sobre ellos, invisible. No pueden percibirla, no pueden usarla, no pueden construir con ella. La geometría de su mundo contiene una dimensión que estructuralmente descartan.
MOAD-0007 funciona de la misma manera. Los objetos en el espacio 3D llevan posición, rotación y volumen delimitador: una rica estructura geométrica. Un escaneo lineal los trata como una lista plana. La estructura espacial: presente, sin usar, descartada. Cada prueba de intersección escanea toda la lista, como si los objetos no tuvieran geometría ni posición.
El Ejemplo de Three.js
Three.js Raycaster.intersectObjects(): dada una rayo (una posición y dirección en el espacio 3D), encuentra todos los objetos que el rayo intersecta. La implementación: itera a través de los N objetos de la escena, prueba cada uno contra el rayo. O(N) por llamada.
Un controlador de eventos hover llama a intersectObjects() una vez por fotograma a 60 fotogramas por segundo. Con N=100 objetos: 6,000 pruebas de intersección por segundo. Con N=10,000 objetos: 600,000 pruebas por segundo. El costo: proporcional a N, no al número de objetos que el rayo realmente intersecta.
En N=100: invisible. El presupuesto de fotograma (16.7ms a 60fps) absorbe el costo sin queja.
En N=10,000: dominante. 600,000 pruebas de intersección por segundo saturan el hilo principal. La tasa de fotogramas cae. La escena que funcionaba en N=100 colapsa silenciosamente cuando N cruza el umbral.
La estructura que descarta el escaneo lineal
Los objetos ocupan posiciones en el espacio. Un objeto en la posición (1000, 0, 0) no puede intersectar un rayo que apunta en la dirección (-1, 0, 0) desde la posición (0, 0, 0): el objeto se encuentra en la dirección opuesta. Un escaneo lineal lo comprueba de todos modos.
Los objetos tienen volúmenes de contorno: una esfera o caja que encierra todo el objeto. Un rayo que no intersecta el volumen de contorno de un objeto no puede intersectar el objeto. Un escaneo lineal calcula la prueba de intersección completa de todos modos.
La geometría codifica qué objetos omitir. El escaneo lineal ignora la geometría. Este es el descarte.
Qué significa 'Descartar la Estructura'
La analogía de Flatland: los habitantes de Abbott no podían percibir la profundidad. Un Defecto de Flatland descarta la estructura geométrica que existe en los datos pero nunca entra en el algoritmo.
Por qué un Conjunto Hash no puede resolver MOAD-0007
MOAD-0001 fix: reemplaza una prueba de pertenencia secuencial con un conjunto hash. list.contains(x): O(N). set.has(x): O(1). La pregunta de pertenencia: '¿está x en esta colección?' No hay geometría espacial involucrada.
MOAD-0007 fix: reemplaza un escaneo espacial lineal con un índice espacial (BVH, octree, k-d tree, R-tree). La pregunta espacial: '¿qué objetos de esta colección intersectan este rayo/esfera/frustum?' Se requiere proximidad espacial.
Un conjunto hash responde a la pertenencia: '¿está presente este objeto exacto?' O(1). No puede responder a la proximidad: '¿qué objetos están cerca de este rayo?' Un conjunto hash no tiene noción de distancia ni de extensión espacial. El hashing descarta la geometría tan completamente como un escaneo lineal.
Un BVH responde a la proximidad: '¿qué objetos caen dentro de esta consulta espacial?' O(log N + k). Organiza los objetos por posición, por lo que las consultas de proximidad omiten objetos geométricamente distantes.
| Pregunta | Estructura correcta | Estructura incorrecta |
|---|---|---|
| ¿Está el objeto X en este conjunto? | HashSet (O(1)) | Lista lineal (O(N)) |
| ¿Qué objetos intersectan este rayo? | BVH/octree/k-d tree (O(log N)) | Escaneo lineal O HashSet (O(N) o O(N)) |
MOAD-0001 y MOAD-0007: ambas operaciones O(N) reemplazadas por algo más rápido. Se requieren estructuras diferentes porque las preguntas son distintas.
Cuándo construir, cuándo omitir
Construir un BVH cuesta O(N log N). Consultar cuesta O(log N + k). Punto de equilibrio: cuando el número de consultas supera al de construcciones lo suficiente como para que el ahorro en consultas supere el costo de construcción.
En N=100: el escaneo lineal toma microsegundos. La construcción del BVH añade sobrecarga. Omitir el BVH.
En N=10,000 a 60 Hz: el escaneo lineal domina el presupuesto de fotogramas. Las consultas al BVH cuestan 1/1,000 del escaneo lineal. Construir el BVH una vez; consultar 60 veces por segundo. El punto de equilibrio se alcanza antes del primer fotograma.
La regla: construir cuando N * Q > N log N, donde Q = consultas por ciclo de reconstrucción. Para escenas 3D interactivas: Q = 60 por segundo, umbral de N = unos pocos cientos de objetos.
Diagnosticar y corregir una escena 3D
Una aplicación de visualización 3D renderiza 5,000 objetos geométricos. Un controlador de hover se activa 60 veces por segundo. En cada evento de hover, el controlador llama a scene.intersectObjects(ray, objects) que itera sobre los 5,000 objetos y prueba cada uno contra el rayo. La tasa de fotogramas cayó de 60 fps a 8 fps.
Un compañero de equipo sugiere: 'Coloca todos los objetos en un Set para una búsqueda O(1).'