Guía docente de Estructura de Datos y Algoritmos Geométricos de Sistemas Gráficos (M52/56/5/9)

Esta asignatura optativa forma parte de la especialidad en Visualización, Entornos Inmersivos y Videojuegos. Se pone el foco en trabajar a bajo nivel con estructuras de datos espaciales y algoritmos geométricos para el manejo eficiente de objetos geométricos en 2D y 3D. Los contenidos se pueden categorizar de la siguiente forma:

• Geometría analítica: se introduce al estudiante sobre los conceptos básicos de geometría, geometría diferencial y fundamentos matemáticos básicos. Se estudian los test de inclusión e intersección entre tipos de objetos geométricos y se describen las medidas para el cálculo de complejidad espacial y algorítimica
• Modelos y representaciones: se estudia la geometría digital, modelos de superficies, de volumen, modelos sólidos y geometría fractal, así como algoritmos asociados.
• Geometría computacional: se revisan las estructuras de datos 2D y 3D para la resolución de problemas tipo (convex hul, triangulación, búsqueda, etc.) y para el desarrollo de algoritmos para la resolución de problemas (divide y vencerás, barrido e incremental).

---------

This subject is part of the specialization in Visualisation, Immersive Environments and Video Games. The focus is on low-level work with spatial data structures and geometric algorithms for the efficient handling of 2D and 3D geometric objects. The contents can be categorized as follows:

• Analytical geometry: the student is introduced to the basic concepts of geometry, differential geometry and basic mathematical foundations. Inclusion and intersection tests between types of geometric objects are studied and measures for the calculation of spatial and algorithmic complexity are described.
• Models and representations: digital geometry, surface models, volume models, solid models and fractal geometry are studied, as well as associated algorithms.
• Computational geometry: 2D and 3D data structures for solving typical problems (convex hul, triangulation, search, etc.) and for the development of algorithms for problem-solving (divide and conquer, sweep and incremental) are reviewed.

Se recomienda cursar junto al resto de asignaturas de la especialidad en Visualización, Entornos Inmersivos y Videojuegos.

Conocimientos o contenidos

C03. Comprende y sabe utilizar los fundamentos y métodos matemáticos necesarios para abordar y resolver aplicaciones gráficas, de animación, de visualización, de simulación, de cuadros de mandos, y/o de realidad virtual y aumentada, entre otras.

Habilidades o destrezas

HD04. Sabe diseñar, implementar y evaluar algoritmos gráficos, tanto 2D como 3D, para la representación, digitalización, modelado, visualización tanto realista como expresiva, animación e interacción de modelos con su entorno y su aplicación en interfaces de usuario gráficas.

1. Geometría Analítica.

   • Introducción a los conceptos de geometría.

   • Geometría diferencial.

   • Matemáticas fundamentales para Informática Gráfica (Álgebra Lineal, espacios vectoriales y matrices, espacios afines y parametrización).

   • Test de Inclusión e intersección.

   • Introducción a las medidas de complejidad espacial.

2. Modelos y representaciones.

   • Introducción a la geometría digital.

   • Modelos de superficie y algoritmos.

   • Modelos de volumen y algoritmos.

   • Modelos sólidos y algoritmos.

   • Geometría fractal. Análisis fractal de modelos 3D.

3. Geometría computacional.

   • Introducción a las estructuras de datos espaciales 2D y 3D.

   • Resolución de problemas tipo: convex hull, triangulación, búsqueda, diagrama de Voronoi).

   • Estrategias de solución: divide y vencerás, barrido e incremental).

   • Aplicaciones.

---------

1. Analytical Geometry.
   • Introduction to the concepts of geometry.
   • Differential geometry.
   • Fundamental mathematics for Computer Graphics (Linear Algebra, vector spaces and matrices, affine spaces and parametrization).
   • Inclusion and intersection tests.
   • Introduction to measures of spatial complexity.
2. Models and representations.
   • Introduction to digital geometry.
   • Surface models and algorithms.
   • Volumetric models and algorithms.
   • Solid models and algorithms.
   • Fractal geometry. Fractal analysis of 3D models.
3. Computational geometry.
   • Introduction to 2D and 3D spatial data structures.
   • Problem-solving (convex hull, triangulation, search, Voronoi diagram).
   • Solution strategies (divide-and-conquer, sweeping or incremental techniques).
   • Applications.

El programa práctico consiste en la entrega de una serie de prácticas a lo largo del curso, que están relacionadas con el temario teórico. Las características comunes de las prácticas son:

• Lenguaje de programación C++/QT.
• Especificación para la programación gráfica OpenGL.
• Biblioteca de algoritmos de Geometría Computacional  (CGAL).
• Entorno de programación: Visual Studio o QT Creator.
• Las prácticas son individuales.

Los ejercicios que se proponen para el programa práctico son:

• Práctica 1. Tipos de datos geométricos en 2D. Operaciones.
• Práctica 2. Tipos de datos geométricos en 3D. Operaciones.
• Práctica 3. Trabajando con los triángulos de un modelo 3D.
• Práctica 4. Manejo de estructuras de datos espaciales.
• Práctica 5. Desarrollo de un algoritmo de búsqueda en el espacio 3D.
• Práctica 6. Delaunay y convex hull con CGAL.

---------

The practical program involves the development of exercises throughout the course, which are related to the theoretical syllabus. The common features of the practicals are:

• C++/QT programming language.
• Specification for OpenGL graphical programming.
• Computational Geometry Algorithm Library (CGAL).
• Programming environment: Visual Studio or QT Creator.
• The practices are individual.

The exercises proposed for the practical program are:

• Practice 1. 2D geometric data types. Operations.
• Practice 2. Types of geometric data in 3D. Operations.
• Practice 3. Working with the triangles of a 3D model.
• Practice 4. Handling spatial data structures.
• Practice 5. Development of a search algorithm in 3D space.
• Practice 6. Delaunay and convex hull with CGAL.

• Marschner, Steve, and Peter Shirley. Fundamentals of Computer Graphics. 4th ed. AK Peters/CRC Press, 2018.

• Deitel, Paul, and Harvey Deitel. C++20 for Programmers, 3rd Edition. Pearson, 2020.

• Gallier, Jean. Geometric Methods and Applications For Computer Science and Engineering. Springer Science & Business Media, 2011.

• Peters, James F. Foundations of Computer Vision Computational Geometry, Visual Image Structures and Object Shape Detection. Vol. 124. Springer, 2017.

• Toth, Csaba D., O’Rourke, Joseph and Goodman, Jacob. Handbook of Discrete and Computational Geometry. CRC press, 2017.
• Berg, Mark. Computational Geometry: Algorithms and Applications. 3rd ed. Berlin, 2008.
• Feito, Francisco R., Torres, Juan C., and Ureña, A. Orientation, simplicity, and inclusion test for planar polygons. Computers & Graphics,vol 19 19, no 4, p. 595-600. 1995.
• Segura, Rafael J. and Feito, Francisco R. An algorithm for determining intersection segment-polygon in 3D. Computers & Graphics, vol. 22, no 5, p. 587-592. 1998.

Como apoyo a la enseñanza y aprendizaje de esta asignatura, se usará la Plataforma de Recursos de Apoyo a la Docencia (PRADO) de la Universidad de Granada: https://prado.ugr.es.

Otros enlaces recomendados son:

https://open.gl/

https://www.pbr-book.org/

https://dl.acm.org/

https://diglib.eg.org/

El artículo 18 de la Normativa de Evaluación y Calificación de los Estudiantes de la Universidad de Granada establece que la convocatoria ordinaria estará basada preferentemente en la evaluación continua del estudiante, excepto para quienes se les haya reconocido el derecho de evaluación única final.

Se realizará una evaluación continua del trabajo del estudiante, valorando tanto los conocimientos adquiridos como las competencias alcanzadas.

Modalidad presencial:

Para la evaluación en modalidad presencial se tendrán en cuenta los siguientes sistemas de evaluación, indicándose entre paréntesis el rango del porcentaje con respecto a la calificación final del estudiante.

SE1. Actividades realizadas durante el desarrollo del curso mediante la entrega de ejercicios, trabajos, informes, a través de la plataforma docente (50%)
SE2. Actividades realizadas después de finalizar el curso mediante la entrega de ejercicios, trabajos, informes, a través de la plataforma docente (40%)
SE5. Asistencia y participación activa     (10%)

Se pedirá la entrega en tiempo y forma de las actividades propuestas a través de la plataforma PRADO.

Modalidad virtual:

Para la evaluación en modalidad virtual se tendrán en cuenta los siguientes sistemas de evaluación, indicándose entre paréntesis el rango del porcentaje con respecto a la calificación final del estudiante.

SE1. Actividades realizadas durante el desarrollo del curso mediante la entrega de ejercicios, trabajos, informes, a través de la plataforma docente (50%).

SE2. Actividades realizadas después de finalizar el curso mediante la entrega de ejercicios, trabajos, informes, a través de la plataforma docente (20%).

SE6. Participación activa en foros de debate o de recogida de información  (10%)

SE7. Presentación pública de trabajos o ejercicios sincrónica (20%).

Se pedirá la entrega en tiempo y forma de las actividades propuestas a través de la plataforma PRADO.

El artículo 19 de la Normativa de Evaluación y Calificación de los Estudiantes de la Universidad de Granada establece que los estudiantes que no hayan superado la asignatura en la convocatoria ordinaria dispondrán de una convocatoria extraordinaria. A ella podrán concurrir todos los estudiantes, con independencia de haber seguido o no un proceso de evaluación continua. De esta forma, el estudiante que no haya realizado la evaluación continua tendrá la posibilidad de obtener el 100% de la calificación final.

La evaluación en tal caso consistirá en la realización de una prueba y/o trabajo, y/o las actividades propuestas en la evaluación continua.

El artículo 8 de la Normativa de Evaluación y Calificación de los Estudiantes de la Universidad de Granada establece que podrá acogerse a la evaluación única final cualquier estudiante que no pueda cumplir con el método de evaluación continua por causas justificadas.

Para acogerse a la evaluación única final, el estudiante, en las dos primeras semanas de impartición de la asignatura o en las dos semanas siguientes a su matriculación, si ésta se ha producido con posterioridad al inicio de las clases o por causas sobrevenidas, lo solicitará, a través del procedimiento electrónico, a la Coordinación del Máster, quien dará traslado al profesorado correspondiente, alegando y acreditando las razones que le asisten para no poder seguir el sistema de evaluación continua.

La evaluación en tal caso consistirá en la realización de una prueba y/o trabajo, y/o las actividades propuestas en la evaluación continua.

Siguiendo las indicaciones recogidas en el artículo 15 de la Normativa de Evaluación y de Calificación de la Universidad de Granada sobre la originalidad de los trabajos presentados por los estudiantes, se informa de lo siguiente:

1. La Universidad de Granada fomentará el respeto a la propiedad intelectual y transmitirá a los estudiantes que el plagio es una práctica contraria a los principios que rigen la formación universitaria. Para ello, procederá a reconocer la autoría de los trabajos y su protección, de acuerdo con la propiedad intelectual, según establezca la legislación vigente.

2. El plagio, entendido como la presentación de un trabajo u obra hecho por otra persona como propio o la copia de textos sin citar su procedencia y dándolos como de elaboración propia, conllevará automáticamente la calificación numérica de cero en la asignatura en la que se hubiera detectado, independientemente del resto de las calificaciones que el estudiante hubiera obtenido. Esta consecuencia debe entenderse sin perjuicio de las responsabilidades disciplinarias en las que pudieran incurrir los estudiantes que plagien.

3. Los trabajos y materiales entregados por parte de los estudiantes tendrán que ir firmados con una declaración explícita en la que se asume la originalidad del trabajo, entendida en el sentido de que no ha utilizado fuentes sin citarlas debidamente.