быстрое грязное приближение центра (список трехмерной вершины), который образует очень мелкую выпуклую оболочку - PullRequest
Новая
       28

быстрое грязное приближение центра (список трехмерной вершины), который образует очень мелкую выпуклую оболочку

2 голосов
/ 17 октября 2019

Я хочу найти XY центра (красного) набора точек выпуклой оболочки (оранжевые круги), который является результатом обнаружения столкновения.

enter image description here

Используя технику разделительной оси, я точно знаю, что выпуклая форма (розовая) относительно тонкая по оси Z .

В> 90% моих случаев использования количество вершин не превышает 8.

Мой плохой алгоритм (AABB) ... MCVE

Я пытался реализовать это, вычисляя центральную точку AABB.
Однако, когда я использую это в реальном физическом моделировании, точка столкновения (красная) не является достаточно точной для стабильности стека коробки.

Вот тестовый пример (вершины выдавливаются в +y и -y для создания объема): -

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)
}

Я хочу, чтобы он возвратил что-то вроде Vec3(a value between 0.05 and 0.45, 0, don't care).

Ссылки

Я хочу очень быстрый алгоритм, который не должен быть очень точным.
В Интернете есть какой-то алгоритм, например

  • Скелет (не связанный): Лучшая "центральная точка", чем центроид
  • Просто усредните все точки корпуса. Его точность очень плохая. (например, результат моего примера = Vec3 (0,0,0))
    Еще хуже для неравномерно распределенных вершин, например,
    enter image description here
  • Генерация целоговыпуклая оболочка (и все грани). Это слишком медленно для ненужной высокой точности.

Ответы не должны содержать никакого кода C ++.
Очень грубое предложение может быть очень полезным.

Приложение (библиотека Vec3)

Предоставляется только для полноты MCVE. 

#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)+")";
    }
};
...