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
}
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;
}
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.Wow, seems difficult without knowing the parts of the surface of each object which defines the convex hull.
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.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 don't know. I assume it's the same as in 3D, but using lines instead of planes.Just out of curiosity, do you know the solution in 2 dimensions?
Objects can be concave, and I guess possibly made of separate parts.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?
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.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.
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).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.
I think the hierarchical structure has a negative effect on the efficiency, as described below.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'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.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.
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 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.
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.
We use cookies and similar technologies for the following purposes:
Do you accept cookies and these technologies?
We use cookies and similar technologies for the following purposes:
Do you accept cookies and these technologies?