Point within convex hull of multiple functions

[dougy83]

Hi all,
I'm having trouble figuring out how to find whether a point is within the convex hull of a number of 3D objects defined by functions in 3D space. There can be any number of functions, which don't need to be symmetric. An object is defined by a function describing if a test point is within the object or not. An example for a sphere might be:

bool within(Point3f p)
{
    p = tform * p;                     // tform performs the reverse rotatation, translation and scale on the test point (instead of on the object)
    return (p.x*p.x + p.y*p.y + p.z*p.z) <= 1;    // the transformed test point can then be tested against a radius 1 sphere, at the origin
}

Likewise, the within() function for a solid box would be:

bool within(Point3f p)
{
    p = tform * p;
    return p.x >= 0 && p.x <= 1 && p.y >= 0 && p.y <= 1 && p.z >= 0 && p.z <= 1;
}

So, does anyone know how to determine an equivalent within() function for the convex hull of a combination of these functions?

 

[steveB]

I can see the why you are having trouble . That does not seem like an easy problem. I'll give it some thought today, but can't promise I'll have any good answers.

 

[dougy83]

Thanks Steve, that would be appreciated.

I have thought about using a set of extremal points from each object to guess a bounding hexahedron (which can be iteratively corrected/expanded) for an initial quick outside check. If within the hexahedron, then a check against each object making up the convex hull can be performed. If not within any object, then the hard and slow part of solving the following equation (representing p using a set of extremal points, [v_1, v_2, ..., v_n]) for a number of extremal point sets. For a test point near the hull boundary, this is potentially intractable for an exact answer (but I only need a decent precision).

Another thought might be to build a bounding n-hedron, defined by n planes, such that increasing n will generally improve the accuracy. For an appropriately sorted set of planes, the resulting early-out coarse-to-fine bounds checking might actually be fast to reject obvious external points, and accurate (albeit slow for test points near the actual hull boundary). The planes should be pretty easy to find too.

 

[Pommie]

The way we used to do it was with an initial engulfing sphere test and then a more accurate plane test. You check each plane in the object to see if the point is on the outside of that plane. If the point is on the outside of any plane then no collision has occurred.

Mike.

 

[dougy83]

Thanks, Mike. Yes, the sphere and more-commonly the AABB (axis-aligned bounding box) test are quick for pre-tests; the one having the smaller volume being better.

 

[steveB]

I have a question. I'm assuming you have equations or point definitions for each 3D object, but do you have definitions of the portions of each object that define the convex hull.

 

[dougy83]

No, I would only have the specified within() function for each object. The hull would be built on a union of the rotated/translated/scaled basis objects.

 

[steveB]

Wow, seems difficult without knowing the parts of the surface of each object which defines the convex hull.

It seems to me that if the point is "within" at least one object, it is within the convex hull, but there is one more object that needs to be defined and tested. The volume that is outside all the objects, but within the convex hull is the part that is difficult to define with a "within" function.

I'll keep thinking.

Just out of curiosity, do you know the solution in 2 dimensions?

 

[steveB]

Another question. The individual objects themselves, are they all convex types of objects? In other words, can you have a donut shape, where a point inside the hole of the donut is not inside the object, but is inside the convex hull?

 

[steveB]

Problems like this can sometimes be solved by brainstorming and tossing ideas into the ring for testing. So let me try this.

Here is an initial thought I have that might lead to a solution. Start by defining new objects by pairing every combination of two objects. When you pair two objects, the new object is the convex hull of these two objects. The new objects formed can be a next level in a hierarchy, and these objects at the new hierarchical level could then be paired up in all possible combinations to form new objects for a next hierarchical level.

If you start with 2 objects, you can only pair once and you have only one hierarchy level with one object.

If you start with 3 objects, you have 3 pairs which makes 3 new objects, and the hierarchy can reach any number of levels with each level having only 3 objects.

If you start with more than 3 objects, the hierarchy also can reach any number but each higher level has more and more objects. Four objects makes 6 pairs of objects, which then makes many more ... and so on.

Even though the hierarchy and number of objects grows without limit, there will be some finite level where the objects are eventually covering all, or at least most of the convex hull. For example, 3 spheres will create 3 sets of pairs of spheres connected by a cylinder at the first level. None of these cylinders with balls on the end cover the whole convex space, but at the second level, the convex hull of each of the pair combinations of cylinders with balls on the end, do cover the convex hull space.

Now, why do I suggest this? Because a pairing of two objects might allow a simpler test to see of you are in the convex hull of those two objects only, thus simplifying the problem. If you can find an efficient test for this, you then need to consider combinations and hierarchical levels and figuring out when the level you are at is sufficient to cover the convex space. So eventually you have a level and an object that you feel convers the convex hull space, and this object is defined by a number of "tests" including "within" checks and some new test that figures out if you are within the convex hull of two objects.

This will seem complex and confusing to a human, but this is the kind of thing that a computer can do easily, and it can be coded easily. But the challenge still remains how to efficiently test for the complex hull of two objects, and I'm sure there are some special considerations needed along the way, such as what to do when objects overlap partially, or if 2 objects happen to be exactly the same space, or if one is within another.

I haven't thought it through completely, but it's just brainstorming, so I don't have to. I doubt this will lead to a rigorous solution that is infallible, but it might lead to a practical solution that works a vast majority of the time.

 

[steveB]

As far as testing if a point is within the convex hull of two objects, I don't know an efficient test yet, but here is an observation. A point outside the convex hull of two objects has no line that pierces both exclusive spaces of the two objects.

Note that I talk about "exclusive space" to deal with overlapping objects. Consider objects A and B. Exclusive space for A has within(A)=true and within(B)=false. Exclusive space for B has within(B)=true and within(A)=false.

I can't think of an efficient way to test this condition because you would need to generate many lines and check many points to be sure that no line pierces both exclusive regions. Finding out when points are within the convex hull, might typically be quicker because you will quickly find a line that pierces both regions, but when a point is outside the region, how do you know when to stop checking?

 

[dougy83]

Thanks for the replies, SteveB.

Wow, seems difficult without knowing the parts of the surface of each object which defines the convex hull.

Because just within(p) is available, a grid search with decreasing step size would be used to find points within and on the boundaries of any object. Yes, it is not particularly elegant.

It seems to me that if the point is "within" at least one object, it is within the convex hull, but there is one more object that needs to be defined and tested. The volume that is outside all the objects, but within the convex hull is the part that is difficult to define with a "within" function.

I think this is an important observation because it can be used to speed up the only tractable method we have so far, i.e. the bounding polyhedral approximation; the bounding polyhedron doesn't need to include space containing only points within an object but not in the hull of the extra object you mentioned. e.g. the hull of two offset spheres would become the union of an approximated frustum and the two original spheres.

Just out of curiosity, do you know the solution in 2 dimensions?

I don't know. I assume it's the same as in 3D, but using lines instead of planes.

Another question. The individual objects themselves, are they all convex types of objects? In other words, can you have a donut shape, where a point inside the hole of the donut is not inside the object, but is inside the convex hull?

Objects can be concave, and I guess possibly made of separate parts.

As far as testing if a point is within the convex hull of two objects, I don't know an efficient test yet, but here is an observation. A point outside the convex hull of two objects has no line that pierces both exclusive spaces of the two objects.

I'm not sure if this would provide an efficient solution, as basically many lines would have to be checked, and the intersection between the line and an object have to be tested for every line and (worst case) for every pair of objects. Solving the equation in the first post may be a similar option.

 

[steveB]

Yes, I agree that such a method is not particularly efficient. I mention it only in the hope that it might trigger further ideas for finding an efficient way. I believe that if you can solve the simpler problem of finding out if a point is within the convex hull of two objects, you can efficiently extend the idea to more than 2 objects. If you can't solve the 2-object case, then there is no hope for configurations with more than two objects.

The goal would be to develop a "withinHull" function for any two objects which tells you if you are in the convect hull of those two objects. Part of that function is to check first if the point is withing either object. If not within either object, then a new test checks if the point is within the remaining part of the convex hull. Let's call this new test function "without". Hence for two objects A and B, the point is within the convex hull of A and B if withinHull(A,B)=within(A)+within(B)+without(A,B)=true (where+ means "or").

Before giving up on the line method, let's explore how to make it more efficient. If you can have an estimate of the size of A and B and an estimate of the max distance between these objects. One can develop a scale length for checking lines intersecting with objects. For a test point P that does not test out to be within A or B, pick any direction to form a line. Based on the maximum scale distance, do a binary search in one direction away from P. Hitting an object is tested with within(A) and within(B). If you hit object A or B, then binary search in the other direction to see if you hit the other object. Binary searches are fast. Then if you don't find intersections keep scanning the solid angle 4pi steradians with a grid of sufficient resolution, around the point P.

This is something that can be coded easily, and used until you find something more efficient. Then you can investigate how the withinHull function can be used as "within" functions for the new object withinHull(A,B) which defines a new solid object. These new solid objects can then be combined in pairs again at the next hierarchical level, as I described previously.

 

[misterT]

Start expanding the point to a sphere. If you can check for a "first" collision/intersection with the object, then you can check witch side of the object did the sphere approach.. inside or outside.. This requires you to be able to calculate surface normals that point outwards.

 

[steveB]

I need to make one correction. When using a line test, if you hit one object when projecting the line in one direction, then if you project in the other direction and hit the same object, that is still a point in the convex hull.

The line test is quite general and can be applied without a hierarchical structure. Simply project a line in one direction and if an object is hit then project the other way. Hitting any other object including the same one means you have a point in the convex hull. Objects outside the hull have no lines with this property.

I mention the hierarchical structure because it might be simpler to invent a fast and efficient algorithm for two objects and if so, then the method can be generalized by pairing objects to define new objects which can then be paired again using the same method. This will be efficient because powers of two with pairing can deal with a large number of objects. For example 16 objects requires pairing only 4 times.

 

[dougy83]

Before giving up on the line method, let's explore how to make it more efficient. ... For a test point P that does not test out to be within A or B, pick any direction to form a line. Based on the maximum scale distance, do a binary search in one direction away from P. Hitting an object is tested with within(A) and within(B). If you hit object A or B, then binary search in the other direction to see if you hit the other object. Binary searches are fast. Then if you don't find intersections keep scanning the solid angle 4pi steradians with a grid of sufficient resolution, around the point P.

This will not work if the objects are concave. The hit check on each object would have to be changed to a hit check + an in-hull check for each concave object. Some examples below (hull of cyan objects, red test point).

This is something that can be coded easily, and used until you find something more efficient. Then you can investigate how the withinHull function can be used as "within" functions for the new object withinHull(A,B) which defines a new solid object. These new solid objects can then be combined in pairs again at the next hierarchical level, as I described previously.

I think the hierarchical structure has a negative effect on the efficiency, as described below.

Start expanding the point to a sphere. If you can check for a "first" collision/intersection with the object, then you can check witch side of the object did the sphere approach.. inside or outside.. This requires you to be able to calculate surface normals that point outwards.

I'm not sure what you mean or if this is applicable. How do you mean to expand the point into a sphere? The within() functions only work with test points, not surfaces. You mentioned surface normals; there is no explicit hull, and I don't think the normals of the object at the point->sphere intersection point would tell you whether the point was inside or outside of the hull.

I need to make one correction. When using a line test, if you hit one object when projecting the line in one direction, then if you project in the other direction and hit the same object, that is still a point in the convex hull.

The line test is quite general and can be applied without a hierarchical structure. Simply project a line in one direction and if an object is hit then project the other way. Hitting any other object including the same one means you have a point in the convex hull. Objects outside the hull have no lines with this property.

I mention the hierarchical structure because it might be simpler to invent a fast and efficient algorithm for two objects and if so, then the method can be generalized by pairing objects to define new objects which can then be paired again using the same method. This will be efficient because powers of two with pairing can deal with a large number of objects. For example 16 objects requires pairing only 4 times.

The hierarchical structure provides a neat and simple way to compare aggregate objects, but doesn't reduce the complexity: each comparison of top-tier objects still requires implicit comparisons in all lower tiers. At each tier, the proposed line-intersection algorithm has to be run, in every direction until an intersecting point is found. I think the hierarchy actually increases the workload exponentially. It would be better to use a flat model and just check to see if a line intersects any two objects (or object hulls in the case of concave [or disjoint] objects). This only requires a single effectively-exhaustive search (more with convex objects), rather than many effectively-exhaustive searches.

I don't see how 16 objects only requires 4 pairings; each pairing only adds (globally) one extra object, so for 16 objects, you'd need 15 pairings to join them all, or 14 pairings to end up with two top-tier aggregate objects.

I feel the line intersection method you explained would work and shouldn't be hard to implement. It may be worth a shot. Handling concave objects may make it pretty slow (but faster than the LP solution). I feel the plane checking (bounding polyhedron) method may win in the end. The linear programming method works also, but may be much too slow (solving for single point within 1000 points took ~30ms using a generic LP solver; could be sped up using a less-generic method but not sure how much).

 

[steveB]

So, the concave objects can be handled by the line method. The line will intersect the same object. If using a hierarchical approach, checking the single objects would be the first level (call it level zero).

The hierarchical approach only has a negative approach on efficiency if the line-checking approach is used. As I mentioned, if the line-check approach is used, there is no need for a hierarchical approach. The idea is to find a very efficient method that works for 2 objects (and another for one for single concave objects) and allow that to be expanded to any level. If such an efficient method is not available, then I agree that there is no point to the hierarchy.

For 16 objects, the idea is check 8 pairs, and then form 4 pairs from those 8, and then form 2 pairs from those 4 and then pair the last 2. This is what I mean by 4 pairings. The final pair uses all objects and so would cover the full convex hull. So, in this example, 16 objects are checked individually, then 8 pairs are checked, then 4, then 2 and then 1. So, it's linear with the number of objects and 2N-1 checks are needed for M objects, where N is the next power of two >=M. So, if a method can be found that is 2N-1 times faster or more efficient than the crude line-check method, one can think about this type of approach.

 

[MrAl]

Hi dougy,

Let me see if i understand this problem.

Are you stating that you have a number of 3d objects, and that each and every object has convex hulls.

Second, when you say "convex hull" do you mean a slice of a sphere, where the curved part is spherical and the 'underside' is flat, or could the 'underside' be a spherical surface too? And if it can be spherical, can it be oriented inward only or possibly either inward or outward?

So if it was flat the inner space could be defined as the space between a sphere and a plane, and if curved it could be defined as the space between the intersection of two spheres. If two spheres, one may be oriented outward and one inward, or both inward, or both outward?

When i say "sphere" i mean the shape is defined by the equation for a sphere. When i say "plane" i mean a 2d plane oriented in 3d space, so it can 'cut' the sphere into two sections.

 

[steveB]

Mr Al,

The wiki definition of convex hull is as follows.

In mathematics, the convex hull or convex envelope of a set X of points in the Euclidean plane or Euclidean space is the smallest convex set that contains X. For instance, when X is a bounded subset of the plane, the convex hull may be visualized as the shape formed by a rubber band stretched around X.

Since we are talking about 3d, and not 2d, we might say that the convex hull is defined by a rubber balloon (not inflated) that is stretched around all the 3d objects.

This means that if any of the individual 3d objects has concave portions on its surface, then a point that is outside the object but within the convex volume bounded by the stretched balloon, is still in the convex hull. Also, points that are between different objects, but are within the volume bounded by the balloon, are also in the convex hull.

It seems to me that a useful property of points in the convex hull can also be used as the definition of the convex hull, and it is this property that I suggested be used as an initial test (albeit an inefficient test) to see if the point is within the convex hull. Any point in the convex hull has the property that there exists at least one line that can be extended through that point and that line will hit at least one of the 3D objects in both directions extending away from the point. That is, the point and the line in one direction must have at least one point hitting any object, and the point and the line extending 180 degrees in the other direction must have at least one point hitting any object (the other object can be the same one or a different one). There must be at least one such line for the point to be in the convex hull.

You can see that any point within any object has at least one such line. Also, any point within (as defined by the balloon) the concave parts of an object that has concave portions has at least one such line, and a point between objects and within the "balloon", has at least one such line. Points outside the convex hull have the property that all lines going through it don't hit any of the 3d objects on at least one side of each line.

Notice that a point outside the convex hull has an infinite number of lines to be checked to make sure that none of them hit an object on at least one side. This is what makes the "line check" algorithm inefficient. The question is, "How many lines should be checked to have high confidence that the point is truly outside the convex hull?"

 

[MrAl]

Hello Steve,

Thanks for the links, i'll have to read up a little.

In the mean time, would you say that the rubber sheet stretched out over three points would create a triangular plane surface, and it over 4 points would create a square surface or perhaps two triangular surfaces?
Also, if there was a fourth point (with the three that formed a triangular surface) that was a little lower than the first three points, would the rubber sheet reach down to touch the top of that fourth point or would it stay stretched across the three and remain above the fourth (so the fourth was under the sheet, not part of the surface)?
Also, if the sheet touches one point and then extends toward another point, does the sheet follow some natural curve or does it bend at the required angle (making the surface discontinuous) in order to reach the next point?

Another question, can we derive the equation(s) for the sheet from the points?
And in short, would this be the set of equations of surfaces that make up the entire sheet, or is it one continuous surface (derivatives everywhere)?