Computational geometry

Computational geometry is a branch of computer science devoted to the design and analysis of efficient algorithms and data structures for computational problems involving discrete geometric objects in 2-, 3-, and even higher-dimensional space. The most common geometric objects are simple, such as points, lines, polygons, planes, and polyhedra, which lie in low dimensional spaces. Computational geometry finds applications in numerous areas of science and engineering while dealing with foundational geometric and algorithmic problems that arise in these areas. These include computer graphics, computer vision and image processing, robotics, computer-aided design and manufacturing, computational fluid-dynamics, and geographic information systems. Triangulations, spatial subdivisions, nearest-neighbours, Voronoi diagrams and their broad applications are focus points of the computational geometry group at IDSIA

References

G. Greiner and K. Hormann. Efficient clipping of arbitrary polygons. ACM Transactions on Graphics, 17(2):71-83, Apr. 1998

K. Hormann and A. Agathos. The point in polygon problem for arbitrary polygons. Computational Geometry. Theory and Applications, 20(3):131-144, Nov. 2001.

Computer graphics

Over several decades computer graphics has evolved from simple line drawing to algorithms, systems, and hardware which enable generating high-quality images and animations that are often indistinguishable from real-world images. The field contributes efficient algorithms and hardware solutions for modelling, representing, simulating, manipulating, and visualizing objects in digital environments. The applications of these techniques include but are not limited to entertainment, visualizations, and physics-based simulations. Our main research topic in this area is efficient image synthesis for novel display devices, such as virtual and augmented reality headsets, as well as novel display design. We combined our expertise in visual perception, computer graphics, and display design to develop new algorithms and hardware that enable efficient reproduction of all visual cues a human observer can experience in the real world.

References

M. Tarini, K. Hormann, P. Cignoni, and C. Montani. PolyCube-Maps. ACM Transactions on Graphics, 23(3):853-860, Aug. 2004.

Computational fabrication

Computational fabrication can be thought of as an extension of computer graphics that goes beyond the creation of visual stimuli and deals with fabricating physical objects exhibiting specific properties using novel digital fabrication tools, such as multi-material 3D printers. Novel techniques deal with the enormous complexity of the object design space as well as the limitations of available hardware and materials. Developed algorithms and hardware find numerous applications in areas such as rapid prototyping, prosthetics, robotics, heritage preservation, metamaterials design, visualization, and education. Our research focuses on developing new methods for fabricating physical objects that exhibit specific appearance, mechanical, and haptic properties.
The research activities in computer graphics and computational fabrication are currently supported by ERC- Starting and SNF grants. The results are regularly published at the top computer graphics venues and journals, e.g., ACM SIGGRAPH and ACM Transactions on Graphics.

Computer vision

The research area of computer vision is concerned with recognizing patterns in images and videos to extract useful high-level information, such as the presence, position, or shape of specific objects. Human and animal visual systems excel at this task, which has eluded artificial systems for a long time. Recent advances in deep learning unlocked applications previously thought to be impossible and demonstrated superhuman image interpretation ability for many challenging tasks. Nowadays, computer vision is a key technology for many fields, including robotics, industrial automation, autonomous driving, biomedicine, digital media, document processing, biometrics, movie production, and remote sensing. IDSIA pioneered computer vision systems based on deep neural networks in most of these fields, winning multiple international competitions, and continues to advance the state of the art with high-profile publications and applied projects. 

Geometry processing

The interdisciplinary research area of geometry processing combines concepts from computer science, applied mathematics, and engineering for the efficient acquisition, reconstruction, optimization, editing, simulation, and fabrication of geometric objects. Applications of geometry processing algorithms can be found in a wide range of areas, including computer graphics, computer aided design, geography, and scientific computing. Moreover, this research field enjoys a significant economic impact as it delivers essential ingredients to produce, for examples, cars, airplanes, movies, and computer games. IDSIA’s main expertise in this field, with a strong record of publications and projects, covers surface reconstruction and parameterization, interactive modelling and compression of dynamic triangle meshes, subdivision methods for curves and surfaces, generalized barycentric coordinates for computer graphics and computational mechanics, as well as additive manufacturing.

References

K. Hormann and G. Greiner. MIPS: An efficient global parametrization method. In P.-J. Laurent, P. Sablonnie, and L. L. Schumaker, editors, Curve and Surface Design: Saint-Malo 1999, Innovations in Applied Mathematics, pages 153-162. Vanderbilt University Press,
Nashville, 2000

N. Dyn, K. Hormann, S.-J. Kim, and D. Levin. Optimizing 3D triangulations using discrete curvature analysis. In T. Lyche and L. L. Schumaker, editors, Mathematical Methods for Curves and Surfaces: Oslo 2000, Innovations in Applied Mathematics, pages 135-146. Vanderbilt University Press, Nashville, 2001.

K. Hormann and M. S. Floater. Mean value coordinates for arbitrary planar polygons. ACM Transactions on Graphics, 25(4):1424-1441, Oct. 2006.

C. Conti and K. Hormann. Polynomial reproduction for univariate subdivision schemes of any arity. Journal of Approximation Theory, 163(4):413-437, Apr. 2011

T. Winkler, J. Drieseberg, M. Alexa, and K. Hormann. Multi-scale geometry interpolation. Computer Graphics Forum, 29(2):309-318, May 2010.