Optimization algorithms in package extrema, point-surface

SeMiR's picture

Concerning the two posts
https://dev.opencascade.org/index.php?q=node/975
https://dev.opencascade.org/index.php?q=node/988
I am wondering if there are plans to implement one of those algorithms for the case of projecting a point onto a face.
Maybe there have already been efforts on that? I would be very interested in any intermediate results (also negative ones).

We have run into problems with BRepExtrema_ExtPF and its underlying classes when bspline-surfaces have discontinuous derivatives (for both C0 and C1 surfaces).
In summary, analysing and debugging the code gave us the following:

Extrema_GenExtPS uses math_FunctionSetRoot with Extrema_FuncPSNorm as optimizer. To calculate search directions (both newton direction and gradient direction),
it is necessary that the surface is C2. However, this is not checked, the solver simply calls Adaptor3d_Surface::D2().
Here (and the same with Geom_BSplineSurface::D2()) the documentation says that exceptions would be raised if differentiability was not given, but actually this is not the case!
Thus math_FunctionSetRoot calculates invalid search directions and terminates (successfully, no hint to user!) on a non-optimum.

The new optimization approaches would definitely help us to solve the problems, although I assume that further work will still be necessary to deal with the C0 case:
the PSO-solver needs a deterministic local solver afterwards (which is Newton at the moment) and the global deterministic solver relies on C1 faces at minimum.

Thanks!

Roman Lygin's picture

Derivative continuity

Inherent Extrema issue (including _GenExtPS) is using regular (in parametric space) grid. Definitively this exposes a possible issue of C2-discontinuous subdomain [ai,ai+1; bj,bj+1] at which the Newton-Raphson is invoked. In that case it may diverge or converge to a wrong point indeed, as you mention.

OCC tried (?) to overcome this by oversampling (excessive number of grid lines). A likely better alternative could be to enforce split by C2-continuous intervals. The latter could be achieved for instance by using adaptor's API (e.g. Adaptor3d_Surface::UIntervals()). Within each sub-interval a further split could be to ensure dA < E, where dA is max angle between surface normals (or curve derivatives) and E is angular deflection.

Perhaps this could provide competitive efficiency (correctness and performance) vs new sophisticated algorithms.

Would be interesting to hear OCC team's feedback if they considered this and why disregarded if so.

www.opencascade.com

Copyright 2011-2016
OPEN CASCADE SAS
Contact us