Calculate Up Vector of Object on Surface Given Points and Normals

Context

I want to find the up vector an object would have if it were leaning on a surface, given a large amount of points on that surface and their associated surface normals (i.e., an equation that relates the up vector to points on the surface and their associated normals). First, I would like to know how to find this in two dimensions. And it would be great to know how to find this in thre dimensions as well. The reason I want this is to correctly orient a rectangular prism over any given surface(s) in a computer program.

Take the following two-dimensional examples:

NOTE 1: For all examples, the centroid of an object, namely a rectangle, is depicted to be directly above the centroid of the drawn portion of a surface (the actual surface may be much larger; what's depicted is only the surroundings of the centroid of the rectangle).

NOTE 2: All examples only have 4-6 points but in my actual use case, I will be using around 100 points.

Example 1

Here, the up vector of an object on the surface would be parallel with the y-axis because the entire surface is level and parallel with the x-axis, which also implies that their surface normals are all parallel with the y-axis.

Example 2

Here, the up vector of an object on the surface would be approximately 45 degrees clockwise from the y-axis because the surface is not level and the right half is lower than the left half. It would have been approximately 45 degrees counter-clockwise if the left half were lower than the left half and the distance between the halves remained the same.

Example 3

Here, the up vector of an object on the surface would be approximately 45 degrees clockwise from the y-axis because the slope of the surface is constant all-throughout and all points have the same surface normal; therefore, the up vector of the object would be the same as the constant normal. If the surface were slanted the opposite direction, the up vector would be approximately 45 degrees counter-clockwise for the same reasons.

Example 4

Here, the up vector of an object on the surface would be parallel with the y-axis because although none of the normals are parallel with the y-axis (assuming the bottom normal is undefined or not parallel with y-axis), the surface is symmetrical and all the normals "cancel out," resulting in a normal "halfway between" them, which happens to be a normal parallel with the y-axis. It would be the same scenario if the surface were rotated 180 degrees to look like a wedge.

Example 5

Here, the up vector of an object on the surface would be parallel with the y-axis because the middle part of the surface is below and the other parts of the surface and will not be considered since it is too far down to be touched by the object. And since the surface that would be touched by the object is level and has a uniform normal, the the object's up vector will equal that uniform normal, which happens to be parallel to the y-axis.

Example 6

Here, the up vector of an object on the surface would be nearly parallel with the y-axis. This situation is quite similar to the last example; just more complicated. Much of the surface will not be touched and so will not be considered, but the overall (average) normal of the parts that will be touched is nearly parallel with the y-axis.

Example 7

Here, the up vector of an object on the surface would be parallel with the y-axis. This siutation too is similar to examples 5 and 6. Much of the surface will not be touched by the object and so will not be considered. But the overall (average) normal of the parts that would be touched happens to be parallel with the y-axis.

Example 8

Here, the up vector of an object on the surface would be parallel with the y-axis. This situation is a combination of examples 5, 6, and 7 and 4. Not only would the majority of the surface not be considered due to unreachability, the part that is considered is symmetrical and so will "cancel out" to result in an up vector that happens to be parallel with the y-axis.

Summary

So in summary, I noticed the following relationships and continuities with each example:

• Only the parts of the surface that are reachable by the object will be considered; the rest will be neglected.
• Symmetry results in "cancelling out" to some vector parallel with the line of symmetry.
• The up vector appears to be the average of considered normals (correct me if there is more to it).

Based on my observations, the normals need to be filtered somehow to only include normals of positions that are reachable (I am not sure how to determine this) and then averaged to get the up vector of an object lying on the surface.

Note: Please correct me if any thing I say is incorrect; I am here to learn :)

• This should depend on the width of the rectangle, right? The smaller the rectangle, the fewer points it interacts with, so the more closely it hugs the undulations of the surface, while a longer rectangle can bridge more distant points. It looks like you're only really using the point normals to estimate surface reconstruction: positing that there must be a corner in example 2 for the rectangle to pivot on, even though the tip of the corner was not one of your points. Once you have the contact points, the normals at those points no longer matter to the orientation of the rectangle. Commented Feb 11 at 9:37
• Thank you for your response @DMGregory! Assume all points are under the prism and none are too far offset to not be considered just like that. I would need some sort of algorithm to determine which points may obstruct the possibility of other points being touched and based on that find out which ones to filter out and only use the points that will likely be touched. Commented Feb 12 at 2:54
• So maybe the thing to do is figure out which points will likely be touched and from that information, find the up vector of the rectangle/prism that will result in as many of those points being touched as possible? But still idk how to figure out which points will likely be touched. Commented Feb 12 at 2:58
• That sounds like a convex hull. You can add two false points to the set, whose horizontal coordinates are the left and right extremes of the prism, and whose vertical coordinate is the bottom-most of any point. Find the convex hull of that augmented set, and you get only the points that the prism could touch without falling through another one first. Then you just have to decide which way it tips based on where the highest remaining points are. But that doesn't fully account for a case like #2, where the chosen pivot is an implicit point, not one that's explicit in your sample set. Commented Feb 12 at 3:00
• @DMGregory When you had suggested this yesterday, I was unfamiliar with convex hulls but now I have a somewhat decent understanding of how to calculate it. I implemented Chan's algorithm to get the relevant points and it works! But now I have to "decide which way it tips..." How should I do this? A surface reconstruction at the top and get average normal? Find best-fit plane? Someone suggested I find the face with the smallest gradient? What do you think would be an efficient, accurate solution and how would I do it? Commented Feb 13 at 18:11