2

I want to find XY of the center (red) of a convex-hull points (orange circles) set that is a result from collision detection.

enter image description here

Using separating-axis technique, I know for sure that the convex shape (pink) is relatively thin in Z-axis.

In >90% of my use cases, the amount of vertices is not more than 8.

My poor algorithm (AABB) ... MCVE

I tried to implement it by calculating the center point of AABB.
However, when I use it in real Physics simulation, the collision point (red) is not accurate enough for box-stack stability.

Here is the test case (the vertices are extruded in +y and -y to create volume) :-

enter image description here

int main(){
    std::vector<Vec3> hullPoints;
    hullPoints.push_back(Vec3(-0.5,-0.5,-0.1));
    hullPoints.push_back(Vec3(-0.5,-0.5,0.1));
    hullPoints.push_back(Vec3(-0.5,0.5,-0.1));
    hullPoints.push_back(Vec3(-0.5,0.5,0.1));
    hullPoints.push_back(Vec3(0.5,-0.5,-0.2));
    hullPoints.push_back(Vec3(0.5,-0.5,0.2));
    hullPoints.push_back(Vec3(0.5,0.5,-0.2));
    hullPoints.push_back(Vec3(0.5,0.5,0.2));
    //^^^^ INPUT
    Vec3 centerOfHull;// approximate
    Vec3 centerMax=Vec3(-100000,-100000,-100000);
    Vec3 centerMin=Vec3(100000,100000,100000);
    for(unsigned int n=0;n<hullPoints.size();n++){
        Vec3 hullPoint=hullPoints[n];
        for(unsigned int m3=0;m3<3;m3++){
            centerMax[m3]=std::max( centerMax[m3],hullPoint[m3]);
            centerMin[m3]=std::min( centerMin[m3],hullPoint[m3]);
        }
    }
    centerOfHull=centerMax*0.5 + centerMin*0.5;
    std::cout<<"centerOfHull="<< centerOfHull.toString()<<std::endl;
    //it prints (0,0,0)
}

I wish it to return something like Vec3(a value between 0.05 and 0.45, 0, don't care).

References

I want a very fast algorithm that doesn't have to be very accurate.
There are some algorithm in the internet e.g.

  • Skeleton (so unrelated) : Better "centerpoint" than centroid
  • Just average all hull points. Its accuracy is too bad. (e.g. result of my example = Vec3(0,0,0))
    It is even worse for unevenly-distributed vertices e.g.
    enter image description here
  • Generate the whole convex hull (and all faces). It is too slow for unnecessary high precision.

Answers doesn't need to contain any C++ code.
Just a rough suggestion can be very useful.


Appendix (Vec3 library)

It is provided only for MCVE completeness.

#include <vector>
#include <iostream>
#include <string>
struct Vec3{ 
    //modify from https://www.flipcode.com/archives/Faster_Vector_Math_Using_Templates.shtml
    float x, y, z;
    inline Vec3( void ) {}
    inline Vec3( const float x, const float y, const float z )
    { this->x = x; this->y = y; this->z = z; }

    inline Vec3 operator + ( const Vec3& A ) const  { 
        return Vec3( x + A.x, y + A.y, z + A.z );
    }
    inline Vec3 operator *( const float& A ) const   {
        return Vec3( x*A, y*A,z*A); 
    }
    inline float Dot( const Vec3& A ) const    { 
        return A.x*x + A.y*y + A.z*z; 
    }

    inline float& operator[]( int arr)  {
        switch(arr){
            case 0: return x;
            case 1: return y;
            case 2: return z;
        }
        std::cout<<"error"<<std::endl;
        return x;
    }
    std::string toString( ) const    { 
        return "("+std::to_string(x)+","+std::to_string(y)+","+std::to_string(z)+")";
    }
};
javaLover
  • 6,347
  • 2
  • 22
  • 67
  • 1
    Have you tried the usual algorithm for 2d centroid (which you'd want to do in the tangent plane)? https://www.seas.upenn.edu/~sys502/extra_materials/Polygon%20Area%20and%20Centroid.pdf – Gene Oct 17 '19 at 05:58
  • @Gene The link is good for 2D, but kinda hard to apply to 3D. My image might show 2D-like pink prism, but it is usually not axis-align like that. – javaLover Oct 17 '19 at 08:17
  • You said the polygon is thin. The idea is to use Newell's algorithm to compute an "average normal", project points onto this normal direction, take the average as a point on the collision tangent plane. The normal is the plane normal. So you have a full description of the tangent plane. Now project the points onto the tangent plane to get a 2d polygon and take the centroid of it. If you work through the math, it's likely it will simplify so that actually doing all these operations won't necessary. – Gene Oct 17 '19 at 14:32
  • @Gene The idea is to project the pink hull to a X-Y plane (ignore Z), then find center of the X-Y plane, correct?. Although the pink hull is very thin, it is not "uniformly" thin. To my understanding, in the example, the 2D approach will project the hull to `(-1,-1),(-1,1),(1,-1),(1,1)`, then the calculated center will be `(0,0)` which is not quite `Vec3(a value between 0.05 and 0.45, 0,...)` as I wish. – javaLover Oct 18 '19 at 01:18
  • I'm going by your title and may not understand what you're trying to do. You say the problem is in 3d, but the diagram shows a 2d intersection. My take is that in a perfect world, you'd want the centroid of the "thin" 3d collision polytope. That's pretty expensive to compute, so what I suggested was finding a 2d polygon on a reasonably selected plane in 3-space, then find the centroid of that polygon, which is comparatively cheap. The reasonable plane is one with the same normal as the "thin" dimension and passing through the middle of its extent on that normal. – Gene Oct 18 '19 at 20:40
  • @Gene Thank, it is good starting point. I still need to modify the algorithm to make it aware depth somehow. Hmm... – javaLover Oct 19 '19 at 02:57

0 Answers0