Low quality of intersection algorithms expensiv for industry

In the Workshop on Mathematical Foundations of CAD (Mathematical Sciences Research Institute, Berkeley, CA. June 4-5, 1999.) the consensus was that: “The single greatest cause of poor reliability of CAD systems is lack of topologically consistent surface intersection algorithms.” Tom Peters, Computer Science and Engineering, The University of Connecticut, estimated the cost to be $1 Billion/year. For more information consult:

• Article by R. Farouki "Closing the Gap Between CAD Model and Downstream Applications” in SIAM News 6-1999.

Now a decade later these challenges still remain.

Near singular intersection and non-regular parametrization an intersection challenge

Calculation of intersections is not difficult when the surfaces have a regular parameterization and are not near parallel along intersection curves (transversal intersection). However, if the parameterization is not regular, or if the surfaces intersect in regions where the surfaces are parallel or near parallel, intersection calculation gets challenging. One ambition of the GAIA II project has been to provide more accurate solutions for such intersections than what has been available by exploiting teh potential of approximate implcitization.

After the GAIA-project ended we have stabilized he prototype intersection algorithms.  However, still the time is little early for industrial use as the approach is computational intensive. However, with the introduction of heterogeneous many core CPUs sufficient computational performance will be available for industrial use. Topics now addressed are:

•  Parallelize of approximate implicitization, part of PhD work in (2009-2010).
• Redesign the algorithms to allow recursive subdivision to exploit many core CPUs, part of PhD work in (2009-2011).

Self-intersections are a challenge

Another challenge within CAD has been to avoid self-intersections in the shells of the volume described. These self-intersections are of different types:

• A shell self-intersection is an intersection between different surfaces in the shell of the volume, with the intersection being no part of the adjacency description of the shell.
• An open self-intersection is a self-intersection that occurs inside a parametric surface and the self-intersection curve does not describe a loop in the parameter domain of the surface. These can be found by first subdividing the surface into smaller pieces that themselves do not have closed self-intersection. The pieces can then be intersected.
• A closed self-intersection is a self-intersection that occurs inside a parametric surface, where the intersection curve describes a loop in the parameter domain of the surface.

Isogeometric analysis poses new intersection challenges

Isogeometric analysis replaces the boundary structure type CAD-model, by modelling with trivariate rational spline volumes. Consequently the intersection of trivariate spline volumes will have to be handled. The current examples of isogeometric analysis avoid the intersection challenges by directly creating correct models. However, before the isogeometric analysis can be deployed in industry on large scale better approaches for model creation should be devised.

• Building the model from CAD-models
• Flexible Boolean operations between trivariate spline represented volumes

A component of such functionality will be to be able to intersect trivariate volumes and check that the trivariate volumes do not turn back on themselves (self-intersection).