Home | ContactACS ProjectAlgorithms for Complex Shapes with certified topology and numericsThe ACS project aims at advancing the state of the art in computing with complex shapes. Current technology can cope well with curves in the plane and smooth surfaces in three-dimensional space. We want to address a larger class of shapes, including piecewise smooth surfaces, surfaces with singularities, as well as manifolds of codimension larger than one in moderately high dimension.
TopicsIncreasingly demanding applications of this area, for example in CAD/CAM, computer aided surgery, realistic virtual environments, robotics, and molecular modeling in drug design and structural biology, require efficient and robust methods for computing with complex shapes. Current technology can cope well with curves in the plane and smooth surfaces in three-dimensional space. We deal with a larger class of shapes, including objects with sharp features.
Certified printed circuit layout. Modern CAD/CAM systems require certified and efficient geometry and topology processing.
Topics that ACS addresses are shape approximation (including meshing and shape simplification), shape learning (including reconstruction from sampled data and feature extraction), as well as robust modeling (including CAD operations).
ApproachA unique and ambitious feature of our approach is the guaranteed quality of all data structures and algorithms we plan to develop. Through certified topology and numerics, we will be able to prove that the output is topologically and numerically consistent, according to prespecified criteria. A software prototype, dealing with a restricted class of complex shapes, will demonstrate the feasibility of our techniques in practice.
ObjectivesThe ACS-consortium aims at extending the success of previous European projects CGAL and GALIA, in which it has been involved. Furthermore, the consortium has done pioneering work in the new research area of computational geometry for curves and surfaces in the project ECG. The project ACS consolidates and extends this scientific success.
It pursues this goal by focusing on methods for more general shapes. Our research concerns basic problems in geometric computing, and our line of research so far has produced a steady flow of scientific results enabling us - and the communities involved in geometric computing - to tackle problems involving increasingly complex shapes.
Research programWe aim at developing data structures and algorithms for complex shapes emphasizing: guaranteed quality, efficiency, and feasibility.
Guaranteed quality of shape modeling needs to cover the two closely intertwined aspects of geometric computing: numerical correctness and topological consistency. Efficiency in running time and storage space is the standard measure of good algorithm design. Feasibility means implementable solutions that work well in practice.
Within ACS we develop certified meshing software for industrial and medical applications.
The objectives of guaranteed quality on the one hand and efficiency and feasibility on the other hand are competing. Quite often feasibility in practice is achieved by heuristic solutions that compromise the quality of the results. It is a central distinctive objective of our research proposed to achieve all these goals at the same time.
The most direct way to obtaining certified numerical and topological results is to use exact arithmetic. However, for non-linear objects this may imply prohibitively expensive primitives. Our research concentrates on netting the effect of exact arithmetic without paying its cost, ultimately at speeding up exact computing methods to levels comparable to those of numerical computation. We will also investigate shape-approximation techniques which can work with simpler, more efficient primitives. An alternative approach is to bypass exact computing altogether and aim directly at an approximation of complex shapes. A major means to approximate complex shapes is through meshing (See Figure above). The partners have obtained major results for approximation of smooth surfaces and we aim for significant contributions for more complex shapes in the current project, extending the techniques to handle piecewise smooth surfaces with sharp features.
The geometric software library CGALMany of our basic scientific results have been transfered into mature software, that has found its way into public service and industry. The general purpose geometric software library CGAL is an example of a generic product used by many academic and industrial institutes today, that provides a well-organized, robust and efficient software environment for developing geometric applications.
CGAL has no equivalent counterpart in the world, and it has become a standard in computational geometry. Its impact both in academia and in industry is now becoming tangible, and the company GeometryFactory, one of the partners in the ACS consortium, is commercializing CGAL. The software library CGAL is a unique tool to develop further algorithms for curves, surfaces and more general complex shapes.
ACS software development and CGALThe development of mature software is the main technological objective of ACS. Many scientific results have been turned into CGAL packages, that can be purchased as add-ons to CGAL. In this respect, the role of our industrial partner GeometryFactory includes the assessment, trial, validation and packaging of the software developed in the project, thus guaranteeing a smooth transfer of new technology to application areas in academia, public service and industry.
To ensure interoperability of solutions and to further innovation we will release our mature software under an open source software license. The large community of CGAL users and developers facilitates the transfer and the dissemination of software packages developed in ACS. Reciprocally, ACS helps keeping CGAL at the very state of the art of geometric computing. Therefore, an important impact of ACS is the consolidation of Europe's leading role in this respect, a target that can only be reached if the contributors concert their actions at a European level.
ImpactThe work in geometric computing will bridge the gap between theory and practice by combining dexterity in theory on the one hand and expertise in robust geometric software development on the other. In earlier projects we have turned this type of study into a valid and sound research area.
Therefore, the results of ACS are of utmost relevance to all areas of geometric computing. The sites in the project cooperate with external partners in public services and industry, thereby transferring technology developed in ACS and earlier European projects to concrete situations arising in practice.
Feature extraction, relevant for CAD/CAM applications.
In this way, ACS provides the new techniques for application areas like CAD/CAM (meshing, shape reconstruction, feature extraction) medical imaging and image guided surgery, computer graphics, scientific visualization and virtual reality, robotics (motion and assembly planning), bioinformatics and molecular modeling. The transfer of this new technology from the academic partners to customers in industrial research is an explicit objective of ACS.
[Back to top of page] NavigationACS Home Partners Workshops Publications Software ACS in the news ACS members ACS board EC pages Related projects
NewsCGAL 3.3 released
ACS workshop on
Robust Shape Operations
26-28 September
© 2007 ACS Algorithms for Complex Shapes | Contact us
0 件のコメント:
コメントを投稿