Geometría

Algoritmos geométricos

Binary space partitioning o Partición Binaria del Espacio (BSP) es un método para subdividir recursivamente un espacio en elementos convexos empleando hiperplanos. Esta subdivisión da lugar a una representación de la escena por medio de una estructura de datos del árbol conocida como árbol de BSP.- .........................................................................:http://es.wikipedia.org/w/index.php?title=Especial:Libro&bookcmd=download&collection_id=87a568a6b64bfa06bc0b4f1eda77081b73a8c53f&writer=rdf2latex&return_to=Partici%C3%B3n+binaria+del+espacio

Introducción Modelado procedural C.S.G. Arboles BSP Octrees Links

Árboles BSP Problemas en el pintado de un espacio 3D: Uno de los problemas mas grandes, y el que soluciona el uso de arboles BSP, y por lo tanto el que vamos a explicar aquí , es el problema del pintado de un mundo con una cantidad elevada de polígonos, y la determinacion de las caras a mostrar y las caras ocultas. Existen varias soluciones, todas ellas basadas en la division del espacio por medio de arboles, ya sean BSP, Quadtrees, Octrees, etcetera. ¿Que es un arbol BSP? Empecemos explicando que significa BSP. BSP es el acronimo de Binary Space Partitioning (Particionamiento binario del espacio). Sabiendo su significado ya podemos hacernos una idea de en que consistira un “BSP Tree”. Basicamente se toma el mundo y se divide en dos de forma recursiva, esto es, se toman sus hijos y se aplica nuevamente la particion como si cada hijo fuera un mundo completo. ¿Como se construye un arbol BSP? La construccion de un arbol BSP es muy basica. Consiste en lo siguiente: Se toma una region R del mundo a dibujar, y un plano P, que atravesara a R por su centro. Tomando a P como plano de division se crean dos nuevas regiones: R+ y R-, que seran divididas recursivamente si fuese necesario. Por tanto un arbol BSP es un conjunto de relaciones padre-hijo, y su representacion grafica da como resultado un arbol binario (obviamente). Asi un particionador de un espacio n-dimensional es un subconjunto del espacio con n-1 dimensiones, que divide la region en 2 subregiones de tal manera que para hacer una ruta de cualquier punto de R+ a cualquier otro de R- hay que atravesar necesariamente el particionador (plano P). Elementos de un arbol BSP Los elementos de los arboles BSP son los particionadores, y los nodos internos y los nodos hojas. Los nodos internos son los que son divididos y los nodos hojas son los que ya no cumplen la condicion booleana que insta a seguir dividiendolos (que esten dentro del campo de vision, que esten suficientemente cerca de la camara, etc). Los nodos hojas tambien poseen atributos, que suelen ser condiciones booleanas al igual que los nodos internos, para determinar si finalmente ese nodo se dibujara, o el nivel de detalle con el que se hara (entre otras cosas). Ademas de estos elementos hacen falta mas: Cada nodo interno necesita una referecencia a su particionador, y los nodos internos y los nodos hojas necesitan diferenciarse, lo cual se puede hacer con un simple bit. Visualizacion con arboles BSP Con lo visto hasta ahora un lector no iniciado en el mundo de la imagen 3D podria pensar que los arboles BSP se construyen para visualizar cada fotograma. Esto no es asi, principalmente por coste computacional. Construir un arbol BSP para dibujar una escena puede llevar mucho tiempo si la escena es muy compleja. Podria usarse para renderizacion, pero para aplicaciones interactivas que no tienen un desarrollo planificado, es decir, no hay una secuencia de fotogramas determinada, esto se hace inabordable mediante este metodo. Sin embargo si se usan en este tipo de aplicaciones, aunque de una manera distinta a la que puede parecer mas evidente. El procedimiento es construir el arbol BSP una sola vez, y para el pintado de la escena simplemente comprobar los nodos a ser dibujados. Si un nodo interno no debe ser pintado sus hijos tampoco, y por tanto se descartan para la escena. Esto tal vez necesite mas atributos en los nodos, pero resulta un metodo muy aceptable de pintado de escenas, de hecho es muy usado en juegos 3D, que necesitan una elevada capacidad de calculo y un numero muy alto de fotogramas por segundo. El detalle y los arboles BSP Ya hemos visto lo que es un arbol BSP, como se construye, sus elementos principales y como visualizar la informacion que contiene. Ahora tenemos que adoptar un compromiso entre detalle y tamaño. Los arboles BSP se pueden utilizar para determinar el nivel de detalle de objetos lejanos, pero tambien para “definir” las lineas entre objetos. Esto es trabajo de otro campo de la imagen 3D, no obstante debemos tener en mente que si tenemos 2 objetos y 4 regiones, la “linea de transicion” de uno a otro, o de uno al fondo de la escena sera muy pronunciado. Por otro parte si hacemos una division excesiva del espacio tendremos k hacer muchas mas comprobaciones, ya que habra mas nodos hoja a ser pintados y el arbol sera mucho mas grande. A modo de conclusion sobre esta incursion en el mundo de los arboles BSP diremos que hay que buscar el balance entre calidad de imagen y recursos necesarios. Los arboles BSP pueden ser una potente herramienta, pero con una mala gestion pueden provocar un efecto contrario al buscado. La Fórmula del área de Gauss, Fórmula de la Lazada o Algoritmo de la Lazada, es un algoritmo matemático usado para calcular elárea de un polígono simple cuyos vértices están descritos como pares de coordenadas en el plano.1 2 Es conocido como fórmula de la lazada debido al constante cruce de productos de las correspondientes coordenadas de cada par de vértices, similar al atar una lazada.1 También recibe el nombre de Fórmula del área de Gauss en honor a Carl Friedrich Gauss. Tiene múltiples aplicaciones en agrimensura e ingeniería de montes entre otras áreas.- .....................................................:http://es.wikipedia.org/w/index.php?title=Especial:Libro&bookcmd=download&collection_id=7cebabe4e687c3f263b8d6378b60cd11d4798f32&writer=rdf2latex&return_to=F%C3%B3rmula+del+%C3%A1rea+de+Gauss El cálculo del área de un polígono irregular requiere de métodos alternativos de cálculo de áreas. El método más común es dividir el polígono en N triángulos (siendo N el número de lados del polígono) y calcular la área como suma de las áreas de los triángulos. El área del polígono irregular se puede calcular mediante dos procedimientos alternativos: el método de triangulación o el determinante de Gauss: Triangulación del polígono irregular Sea P un polígono irregular. Se desea calcular su área (A). El método de triangulación consiste en dividir el polígono en figuras más fáciles de calcular el área. En este caso se divide en N triángulos y el área del polígono será la suma del área de esos N triángulos. Se divide el polígono en N triángulos (T1, T2, T3,…, TN) . Estos triángulos cumplen que uno de sus lados es un lado del polígono y que todos confluyen en un mismo punto interior. Se miden las alturas (h1, h2,…, hN) de los triángulos. La altura de cada triángulo será el segmento de recta perpendicular al lado del polígono que va desde ese mismo lado hasta el punto interior. Se calculan las áreas de los N triángulos. El área del primer triángulo es: Utilizamos la misma fórmula para calcular el área de los otros N-1 triángulos. Sumamos las N áreas y obtenemos el área del polígono irregular: Determinante de Gauss Un procedimiento muy útil para hallar el área de cualquier polígono irregular es a través del determinante de Gauss. Supone dibujar la figura sobre un plano cartesiano, fijando las coordenadas de cada uno de los vértices del polígono. Se elige al azar cualquiera de ellos y se colocan los pares en la siguiente fórmula. Se ha de recorrer el polígono en el sentido contrario al de las agujas del reloj, teniendo en cuenta que el primer par de coordenadas corresponden al vértice elegido y, después de recorrer en sentido antihorario todos los vértices, el último par debe volver a ser el par inicial. Sean los vértices del polígono: (x1,y1), (x2,y2),…, (xN,yN). La fórmula és la siguiente: Resolviéndolo por el procedimiento conocido, habremos hallado rápidamente el área del polígono irregular. Este método es aplicable a cualquier polígono con cualquier número de lados, tanto en el caso de polígonoscóncavos como en los convexos. Calcular el área bajo la campana de Gauss con cálculo en una variable A la mayoría de los que hemos cursado estudios en los que aparece la campana de Gauss nos han dicho que para calcular la integral entre dicha curva y el eje X, es decir, el área bajo la campana hasta el eje X, debemos usar cálculo en dos variables. Vamos, que no podemos encontrar cuánto vale ese área utilizando solamente cálculo en una variable. Bien, pues eso no es cierto: se puede calcular el ára bajo la campana de Gauss usando simplemente cálculo en una variable. Antes de nada conviente recordar que al hablar de campana de Gauss nos referimos a la gráfica de la función con  números reales. Por comodidad tomaremos la función para  y , es decir, . Nuestro objetivo es confirmar que el valor de la integral es el siguiente: La primera idea podría ser calcularla como integral impropia que es, para lo cual necesitaríamos una primitiva de , pero dicha primitiva no puede expresarse mediante combinaciones de funciones elementales en el sentido de este post, por lo que tenemos que descartar esta opción. La segunda posibilidad es la que ya hemos comentado, calcularla “subiendo” al cálculo en dos variables como se hizo aquí. Pero hoy nosotros no queremos salirnos del cálculo en una variable, por lo que descartamos también dicha opción. Vamos a ver cómo podríamos hacer lo que estamos buscando. Vamos a definir la siguiente función: La idea es calcular la derivada de dicha función  respecto de . Para ello hará falta utilizar el “Teorema Fundamental del Cálculo”+”regla de la cadena” y la fórmula de Leibniz. Podéis encontrar una explicación de estos dos temas en Calcular la derivada de una integral. Voy a calcular la derivada de cada término por separado, para que la cosa no se haga tan pesada, y después sumaré los resultados: Derivada del primer sumando Aquí hace falta TFC+”regla de la cadena”: Derivada del segundo sumando Aquí necesitamos la fórmula de Leibniz: Realizando en el segundo resultado el cambio de variable , obtenemos que este segundo término tiene esta forma: Introduciendo el término  en el primer término (es independiente de ) llegamos a quelas derivadas de cada uno de los sumandos dan el mismo resultado pero con signos distintos, esto es, una es “menos la otra”, por lo que la suma de ellas es nula. Es decir, . Esto significa que la función  es constante, por lo que si calculamos el valor de la misma en un punto entonces tendremos el valor de la función en todo su dominio. Vamos a hacer esto para : Por lo que , valor que también alcanzara si calculamos su límite cuando x tiende a infinito. Pero, por la propia definición de , este límite es precisamente el cuadrado de la integral de la función de Gauss. Entonces: que es el resultado que conocemos de dicha integral. En matemáticas, el particionado del espacio es el proceso de dividir un espacio (normalmente un Espacio euclídeo) en dos o másconjuntos disjuntos (ver también Partición (matemáticas)). En otras palabras, el particionado del espacio divide un espacio en regiones no superpuestas. Cualquier punto en el espacio se encuentra en una, y sólo una, de las regiones. Los sistemas de particionado suelen ser jerárquicos, lo que significa que un espacio (o una región del espacio) está dividida en varias regiones, y después el mismo sistema de particionado se aplica recursivamente a cada una de las regiones creadas. Estas regiones pueden organizarse en una estructura de árbol, llamada un árbol de particionado. La mayor parte de los sistemas de particionado del espacio usan planos (o, en más dimensiones, hiperplanos) para dividir el espacio: los puntos de una de los lados del plano forman una región, y los puntos de la otra forman otra región. Los puntos que se encuentran exactamente en el plano normalmente son asignados arbitrariamente a uno u otro lado. El particionado recursivo emplean planos que de, de esta forma, producen un árbol BSP, una de las formas más comunes de particionado. El particionado del espacio es especialmente importante en los gráficos por computadora, donde se emplean con frecuencia para organizar los objetos en una escena virtual. Almacenando los objetos en una estructura de datos de particionado hace más fácil y rápido realizar ciertas operaciones geométricas — por ejemplo, determinar si dos objetos cercanos están colisionando, o si un objeto está en la trayectoria de un rayo (Ray Tracing). Los sistemas más comunes incluyen:: Árboles BSP Árboles cuaternarios Árboles octales Árboles kd