Discussion: Finding highest point on a surface

Dear all,

I'm brain storming about the problem of finding the hill top of a surface. To phrase the problem correctly, for any given untrimmed surface, approaches to find (or approximate) the point on the surface which is closest to a given plane, while the plane is not intersecting the surface at any point.

I have seen this problem solved by Galapagos, genetic solver, evaluating the surface with u and v parameter and maximizing the Z component of the resulting point. This method is fun to watch but would be difficult to set up when you have multiple surfaces and hill tops to find. Scripting a similar logic with VB.net or C#.net would allow multiple instances to be run at the same time.

A standard component called X-tremez find the extremes (highest and lowest) points on a curve. It returns the point with the highest and lowest Z level. It is applicable to curves only, not surface. Could anyone explain the algorithm behind? Is this method mathematical or and approximation. Can a similar logic be written for surface?

An approximate method is to move the plane towards the surface, the first intersection (typically returns a curve) is approximately where the point will locate.

Another approximate method is to place a point very far away, in the direction of the normal of the plane (very large z component), so far that a Surface|Point CP would result in a good approximation. I believe error will be high for a closely placed point, the Surface|Point CP algorithm may also have high error for a point that is so far.

Anyone else have time to give this problem a thought?

We currently have

Curve|Point CP,

Surface|Point CP,

Brep|Point CP,

ListOfPoints|Point CP,

Plane|Point CP. (projected point dist.)

But it would be quite useful to add more CP analysis, even though the result would be an approximation, if mathematical means are not possible. The problem described above sound like a Plane|Surface CP. Other CP methods are also very useful if exist:

Curve|Curve CP

Surface|Surface CP

Replies to This Discussion

Permalink Reply by David Rutten on July 18, 2011 at 12:20pm

1) Galapagos. Yes, very slow and a dedicated algorithm would make far more sense. It is used primarily as a demo-case, since the problem of finding the highest point on a surface is exactly analogous with how the solver works.

2) Curve extremes. In Rhino5 there is a very good algorithm for this that uses some form of Newton-Raphson algorithm. I've been meaning to backport it into Rhino4 because the algorithm I use for Curve Extremes is actually pretty stupid. Like almost every algorithm to do with nurbs evaluation it is an approximation, but the approximation is accurate to double-precision precision. I have no idea how it works and whether it can be extended to surfaces. Big problem; should it also be able to deal with surface trims?

3) Won't work. First of all intersections are very costly and secondly it isn't obvious at what step-size the plane should moved closer towards the surface.

4) This is what I currently do for Curve Extremes. As I mentioned we have a much better algorithm standing by but I need to backport it into Rhino4 C++. Last time I tried I broke the daily Rhino5 build in Seattle and had people yelling at me. There are some optimisations possible here. For example it's possible to use the most extreme control-point to place the far-away point in such a place as to minimize inaccuracy.

I think (4) is the only approach mere mortals like us can hope to implement.

David Rutten

david@mcneel.com

Poprad, Slovakia

Permalink Reply by Victor Leung on July 18, 2011 at 12:36pm

Hi David,

Thanks for the thought, and explaining <2>. I thought <3> might be accomplishable with a binary search method. But yea, intersection are very costly.

I just find a site that explains 8 different way to optimize the result, informative even I don't understand much.

What about Curve|Curve CP and Surface|Surface CP. Seems to be more difficult to accomplish... I guess a sample and measure method combined with some optimized algorithm might give some pretty accurate result in a relatively short amount of calculation time.

Cheers

Victor

Permalink Reply by David Rutten on July 18, 2011 at 3:04pm

Curve-Curve closest point is already available in the Rhino5 SDK, but since it's not exposed in Rhino4 I cannot at present provide it as a component. I either need to make a separate component library that will only work on Rhino5, or maybe add a mechanism that excludes certain components on certain versions.

The easiest solution for now would be to write a VB/C#/Python script for this, and it will just fail on Rhino4.

We also seem to have a Curve-Surface closest point solver, but I wasn't able to find a surface-surface solver. I'll ask around, see what the math-heads in Seattle say.

The site you linked explains a number of generic solver algorithms. None of them guarantee anything beyond local optima. A lot more comes into play when applying these methods to specific problems such as curve-curve cp. The person implementing the algorithm has to add all sorts of smarts to do with curve degree, spans, closed and periodic curves, multiple knots etc.

David Rutten

david@mcneel.com

Poprad, Slovakia

Permalink Reply by David Stasiuk on July 18, 2011 at 3:48pm

Have you considered using Kangaroo? Here I subdivided a surface into a grid and applied to its points a light unary force in the z direction and a more significant force pulling them to the surface as well. Let Kangaroo do its thing, execute a surface cp to adjusted points, and select the one with the highest z value.

Attachments:

surface_high_pt.3dm, 74 KB
surface_high_pt.ghx, 153 KB

Permalink Reply by Victor Leung on July 18, 2011 at 8:41pm

It is a nice idea, but I'm looking for a way to implement the algorithm with the simplicity of using only one battery. This allows other components to run correctly.

Permalink Reply by Caglar on July 18, 2011 at 12:49pm

It made me think how the bounding box algorithm in GH works. It works pretty fast with multiple objects in most cases. Wouldn't the top face (relative to orientation plane) of the bounding box always be intersecting that point?

Permalink Reply by David Rutten on July 18, 2011 at 3:06pm

Not necessarily. It might come close but there's no guarantee. In fact the BoundingBox solver for Breps and Surfaces is not accurate at all. It either uses the control-point collection which tends to result in boxes that are too large or it uses the shading mesh which tends to result in boxes that are too small.

I wrote a better Brep boundingbox algorithm about a year ago but we only put it in Rhino5.

David Rutten

david@mcneel.com

Poprad, Slovakia

Permalink Reply by Victor Leung on July 18, 2011 at 8:45pm

Hi David,

From what you've said it seems shading mesh would somehow be a possible approximation too. Converting the surface or even Brep to a relatively fine mesh is quite fast, manipulating the vertex coordinates in the mesh would be fast too.

Similar to a sample and measure method.

Cheers

Victor

RSS