La Analogía de Flatland
El libro Flatland de Edwin Abbott (1884): los habitantes de un plano bidimensional. Perciben longitud y anchura. La profundidad: el tercer dimensión por encima de ellos, invisible. No pueden percibirlo, no pueden usarlo, no pueden construir con él. 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 tridimensional tienen posición, rotación y volumen de encuadre: 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 la lista completa, como si los objetos no tuvieran geometría y no tuvieran posición.
El Ejemplo de Three.js
Three.js Raycaster.intersectObjects(): dado un rayo (una posición y dirección en el espacio tridimensional), encontrar todos los objetos que el rayo intersecta. La implementación: iterar a través de todos los N objetos del escenario, probar a cada uno contra el rayo. O(N) por llamada.
Un manejador de eventos de desplazamiento 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.
A N=100: invisible. El presupuesto de fotogramas (16.7ms a 60fps) absorbe el costo sin queja.
A N=10,000: dominante. 600,000 pruebas de intersección por segundo saturan el hilo principal. La tasa de fotogramas disminuye. El escenario que funcionaba a N=100 colapsa silenciosamente mientras N supera el umbral.
La Estructura que el Escaneo Lineal Descarta
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 verifica de todos modos.
Los objetos tienen volùmenes de encuadre: una esfera o caja que encierra todo el objeto. Un rayo que no intersecta el volumen de encuadre 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 saltarse. El escaneo lineal ignora la geometría. Esto 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 de Hash no puede solucionar MOAD-0007
Solución MOAD-0001: reemplaza una prueba de pertenencia secuencial con un conjunto de hash. list.contains(x): O(N). set.has(x): O(1). La pregunta de pertenencia: '¿x está en este conjunto?' Sin geometría espacial involucrada.
Solución MOAD-0007: reemplaza un escaneo lineal espacial con un índice espacial (BVH, octree, k-d tree, R-tree). La pregunta espacial: '¿cuáles objetos en este conjunto intersectan este rayo/sfera/frustro?' Se requiere proximidad espacial.
Un conjunto de hash responde la pertenencia: '¿este objeto exacto está presente?' O(1). No puede responder proximidad: '¿cuáles objetos están cerca de este rayo?' Un conjunto de hash no tiene noción de distancia o extensión espacial. La encripción descarta la geometría tan completamente como un escaneo lineal.
Un BVH responde la proximidad: '¿cuáles objetos caen dentro de esta consulta espacial?' O(log N + k). Organiza los objetos por posición, por lo que las consultas de proximidad saltan objetos geométricamente distantes.
| Pregunta | Estructura Correcta | Estructura Incorrecta |
|----------|---------------------|------------------------|
| ¿El objeto X está 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(Conjunto de Hash (O(N) o O(N)) |
MOAD-0001 & MOAD-0007: ambos operaciones O(N) reemplazadas por algo más rápido. Se requieren diferentes estructuras porque las preguntas difieren.
Cuándo construir, cuándo omitir
Construir una BVH cuesta O(N log N). Consultas: O(log N + k). Equilibrio: cuando las consultas superen en número las construcciones de modo que los ahorros en consultas superen el costo de construcción.
A N = 100: escaneo lineal toma microsegundos. Construcción de BVH añade overhead. Saltarse la BVH.
A N = 10,000 a 60Hz: el escaneo lineal domina el presupuesto del marco. Consultas de BVH cuestan 1/1,000 de la consulta del escaneo lineal. Construya la BVH una vez; consulte 60 veces por segundo. Equilibrio alcanzado antes del primer marco.
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.
Diagnóstico y solución de un problema de escena 3D
Una aplicación de visualización 3D renderiza 5,000 objetos geométricos. Un manipulador de hover dispara 60 veces por segundo. En cada evento de hover, el manipulador llama a scene.intersectObjects(ray, objects) que itera todos los 5,000 objetos y los prueba contra el rayo. La tasa de marcos se redujo de 60fps a 8fps.
Un compañero sugiere: 'Agrupe todos los objetos en un Set para una consulta O(1).'