Collision Detection для геометрий, заданных SupportMapping'ом (комментарии) (6 стр) / Форум / Разработка физики для игр / GameDev.ru

fysx
тебе самому-то удобно в этих кучах x и y разбираться? перегрузи нормально все операторы, тогда формулы внезапно станут контактными и из мешанины символов приобретут смысл. например, твоя функция принадлежности точки отрезку могла выглядеть так(предполагается, что точка лежит на прямой, содержащей отрезок):

public boolean checkPointInSegment(AGVector2D a, AGVector2D b, AGVector2D x)
{
  return (x - a).dot(x - b) < 0;
}

если нужно проверить, принадлежит ли точка x прямой, содержащей отрезок, то будет как-то так(перейду на c++)

template<typename Space>
bool checkPointOnLine(typename Space::Vector linePoint0, typename Space::linePoint1, typename Vector point)
{
  return sqr((linePoint1 - linePoint0).cross(point - linePoint0)) < eps;
}

обрати внимание, что в таком виде для 2д и 3д функция будет одна и та же.

fysx
Постоялец

#76
23:37, 5 дек 2012

Спасибо за наводку, я сначала строил уравнение прямой через а иб потом проверял принадлежит ли она прямой и лежит ли в пределах отрезка. Так намного удобнее.
Хотя так красиво не получится - ява не умеет перегружать операторы

насколько я понимаю cross в 2д это вот это?

public double cross(AGVector2D v){
    return this ._x * v.getY() - this ._y * v.getX();
  }

fysx
Постоялец

#77
23:39, 5 дек 2012

На 3д меня пока не хватит, тут бы с 2д разобраться. да и нужно будет еще много чего делать кроме коллизий)

Suslik
Постоялец

#78
23:43, 5 дек 2012

fysx
> Хотя так красиво не получится - ява не умеет перегружать операторы
это вовсе не обязательно. формулу

  return sqr((linePoint1 - linePoint0).cross(point - linePoint0)) < eps;

вполне можно заменить на

  return sqr(( linePoint1.sub(linePoint0) ).cross( point.sub(linePoint0) )) < eps;

это всё лучше, чем разбираться в каше безликих коэффициентов, количество которых до кучи меняется с размерностью пространства.

fysx
Постоялец

#79
23:45, 5 дек 2012

Ну да это я знаю, сделал. точки находятся, буду искать проблему в реакции на опору.

fysx
Постоялец

#80
23:45, 5 дек 2012

Спасибо за помощь!

WISHMASTER35
Постоялец

#81
19:15, 14 дек 2012

Ссылка на джава апплеты не работает(: Не могу понять про PD вектор. Как найти ближайшую вершину геометрии к началу координат (0,0) ясно. Только не пойму что значит, что вершина задана как разность двух исходных? И что за две исходные? Да и точка и вектор все же разные понятия. Наверно я сильно туплю)

Suslik
Постоялец

#82
19:18, 14 дек 2012

разность минковского двух объектов - тоже объект. ближайшая точка к началу координат этого объекта - и есть pd вектор для двух исходных объектов. точка и вектор - одно и то же.

WISHMASTER35
Постоялец

#83
19:33, 14 дек 2012

Оох. Допустим есть два бокса Безымянный | Collision Detection для геометрий, заданных SupportMapping'ом (комментарии)
Находим разность их позиций и получаем желтый вектор. Потом представляем вершины обеих боксов как вектора(для этого вычитаем из них позиции объектов) и находим вектор(вершину) направление которого больше совпадает с направлением нашего желтого вектора. Так?

Suslik
Постоялец

#84
19:42, 14 дек 2012

WISHMASTER35
> Находим разность их позиций и получаем желтый вектор. Потом представляем
> вершины обеих боксов как вектора(для этого вычитаем из них позиции объектов) и
> находим вектор(вершину) направление которого больше совпадает с направлением
> нашего желтого вектора. Так?
нет. чтобы получить координаты точек разницы минковского, нужно из коодинат каждой точки одного тела в глобальной системе координат вычесть координаты каждой точки другого тела в глобальной системе координат. поточечно это делать очень долго и неэффективно, гораздо продуктивнее пользоваться знанием о том, как связаны support map'ы исходных геометрий и их разность.

WISHMASTER35
Постоялец

#85
19:57, 14 дек 2012

Вот алгоритм определения пересечения 2х боксов.

+ Показать

− Скрыть

    public static boolean findContacts(Box box1, Box box2, List<Contact> contacts) {
        Vector2f[] axis = new Vector2f[] {
            box1.getDirX(),
            box1.getDirY(),
            box2.getDirX(),
            box2.getDirY(),
        };
        
        float[] depth = new float[4];
        if (!intervalIntersect(axis[0], box1, box2, depth, 0)) return false;
        if (!intervalIntersect(axis[1], box1, box2, depth, 1)) return false;
        if (!intervalIntersect(axis[2], box1, box2, depth, 2)) return false;
        if (!intervalIntersect(axis[3], box1, box2, depth, 3)) return false;

        Vector2f nColl = findCollisionPlane(axis, depth);
        

        Vector2f D = Vector2f.sub(box1.getPos(), box2.getPos());
        if (D.dot(nColl) < 0) nColl.mul(-1.0f);

        Vector2f[] points0 = findSupportPoints(box1, nColl);
        Vector2f[] points1 = findSupportPoints(box2, Vector2f.back(nColl));

        return convertSupportPointsToContacts(nColl,
                points0,
                points1,
                contacts);
    }

    private static Vector2f findCollisionPlane(Vector2f[] axes, float[] depth) {
        float dmin = Float.MAX_VALUE;
        Vector2f dir = null;
        for (int i = 0; i < axes.length; i++) {
            float d = depth[i];
            if (d < dmin) {
                dmin = d;
                dir = axes[i].clone();
            }
        }
        return dir;
    }

    private static boolean intervalIntersect(Vector2f axis, Box box0, Box box1, float[] depth, int index) {
        float[] i0 = getInterval(box0, axis);
        float[] i1 = getInterval(box1, axis);
        float min0 = i0[0], max0 = i0[1];
        float min1 = i1[0], max1 = i1[1];

        if (min0 > max1 || min1 > max0) return false;

        float d0 = max1 - min0;
        float d1 = max0 - min1;
        depth[index] = Math.min(d0, d1);
        return true;
    }
    private static float[] getInterval(Box box, Vector2f axis) {
        Vector2f dirX = box.getDirX();
        Vector2f dirY = box.getDirY();
        Vector2f extents = box.getSize().div(2);

        float p = box.getPos().dot(axis);
        float r = Math.abs(dirX.dot(axis)) * extents.x + Math.abs(dirY.dot(axis)) * extents.y;

        return new float[] {
            p - r,
            p + r
        };
    }

    private static float sign(float x) {
        return (x < 0.0f) ? -1.0f : 1.0f;
    }
    private static Vector2f[] findSupportPoints(Box box, Vector2f axis) {
        Vector2f dirX = box.getDirX();
        Vector2f dirY = box.getDirY();
        Vector2f extents = box.getSize().div(2);

        float fx = dirX.dot(axis);
  float fy = dirY.dot(axis);
        extents.x *= sign(fx);
        extents.y *= sign(fy);

        // pos - dirX*sizeX*s0 - dirY*sizeY*s1
  Vector2f supportPointA = box.getPos().sub( Vector2f.mul(dirX, extents.x) ).sub( Vector2f.mul(dirY, extents.y) );
        Vector2f supportPointB = null;
        
        if (Math.abs(fx) == 0) { // dirX == axis
            // p0 + dirX * sizeX * sx
            supportPointB = Vector2f.mul(dirX, extents.x * 2.0f).add(supportPointA);
        }
        if (Math.abs(fy) == 0) {  // dirY == axis
            // p0 + dirY * sizeY * sy
            supportPointB = Vector2f.mul(dirY, extents.y * 2.0f).add(supportPointA);
        }
        
        if(supportPointB == null) {
            return new Vector2f[] {supportPointA};
        } else {
            return new Vector2f[] {supportPointA, supportPointB};
        }
    }

    private static boolean convertSupportPointsToContacts(Vector2f axis, Vector2f[] points0, Vector2f[] points1, List<Contact> contacts) {
        Vector2f perp = new Vector2f(-axis.y, axis.x);
        
        float min0 = points0[0].dot(perp);
        float max0 = min0;
        float min1 = points1[0].dot(perp);
        float max1 = min1;

        if (points0.length == 2) {
            max0 = points0[1].dot(perp);

            if (max0 < min0) {
                float c = min0;
                min0 = max0;
                max0 = c;

                Vector2f T = points0[0];
                points0[0] = points0[1];
                points0[1] = T;
            }
        }

        if (points1.length == 2) {
            max1 = points1[1].dot(perp);

            if (max1 < min1) {
                float c = min1;
                min1 = max1;
                max1 = c;

                Vector2f T = points1[0];
                points1[0] = points1[1];
                points1[1] = T;
            }
        }

        if (min0 > max1 || min1 > max0) return false;

        if (min0 > min1) {
            Vector2f p = projectPointOnSegment(points0[0], points1[0], points1[1]);
            if (p != null) {
                contacts.add(new Contact(points0[0], p));
            }
        } else {
            Vector2f p = projectPointOnSegment(points1[0], points0[0], points0[1]);
            if (p != null) {
                contacts.add(new Contact(p, points1[0]));
            }
        }

        if (max0 != min0 && max1 != min1) {
            if (max0 < max1) {
                Vector2f p = projectPointOnSegment(points0[1], points1[0], points1[1]);
                if (p != null) {
                    contacts.add(new Contact(points0[1], p));
                }
            } else {
                Vector2f p = projectPointOnSegment(points1[1], points0[0], points0[1]);
                if (p != null) {
                    contacts.add(new Contact(p, points1[1]));
                }
            }
        }
        return true;
    }
    
    private static Vector2f projectPointOnSegment(Vector2f point, Vector2f a, Vector2f b) {
        Vector2f E = Vector2f.sub(b, a);
        Vector2f D = Vector2f.sub(point, a);
        float d = D.dot(E) / E.lengthSquared();
        if (d < 0.0f || d > 1) return null;
        return Vector2f.mul(E, d).add(a);
    }

Я так понимаю findCollisionPlane находит этот вектор. А находит она его выбирая вектор с минимальным depth.
А depth в свою очередь находится функцией intervalIntersect, в которой я уже ничего не пойму.
Но функция использует только направления(dirX, dirY) боксов, не очень похоже на твое описание support map'ов.

Suslik
Постоялец

#86
20:17, 14 дек 2012

в том и разница, что я описал общий алгоритм, который работает для произвольных выпуклых геометрий - для боксов, для боксов с закруглёнными краями, для сфер, эллипсов и многоугольников в любых сочетаниях. с боксами всё гораздо проще и для них тот же самый pd вектор можно найти просто из аналитических соображений, используя теорему о разделяющих осях - достаточно перебрать все нормали обоих боксов и найти, на какую из этих осей пересечение проекций боксов минимально. в общем случае, если в столкновении участвуют не обязательно боксы, такую ось сразу указать нельзя, зато можно построить итеративную схему, сходящуюся к нужной оси, о чём я и попытался рассказать.

werasaimon
Постоялец

#87
3:35, 24 фев 2013

а когда точки совпадают то какую из них добовлять

fysx
Постоялец

#88
22:59, 15 апр 2013

Добрый вечер!
Опять разбираюсь в алгоритмах, появилось несколько вопросов. Работает очень некрасиво и медленно - уже руки опускаются.

1. Нужно ли округлять вектор pd о порядка angEps? без округления вносится погрешность и отскоко получается не совсем параллельным.
2. Почему то работает очень медленно уже на трех объектах. алгоритм зацикливатся, приходится ограничивать количество итераций.

+ Показать

− Скрыть

AGVector2D v = new AGVector2D(pd);
    double angEps = 1e-3f;
    double eps = 1e-4f;
    int break1 = 0;
    
    double OAlengthOld = 10000;
    
    while(true){
      v.setPosition(pd);
      int break2 =0;
      while(true){
        //ищем точку S в направлении v геометрии CSO
        AGVector2D S = this.getSupport(inObject, v);
        AGVector2D A = AGGeometryHelper.findCross(
            AGGeometryHelper.calcCoefViaNormal(v, S), 
            AGGeometryHelper.calcCoefViaCenter(pd)
            );
        if(_gl !=null && _invMass > 0){
          /*AGGeometryHelper.drawPoint(A, _gl, new double[] {0, 1, 1, 0});
          AGGeometryHelper.drawPoint(S, _gl, new double[] {0.5, 0.8, 0.2, 0});
          AGGeometryHelper.drawLine(AGGeometryHelper.calcCoefViaNormal(v, S), _gl, new double[] {1, 0, 1, 0});
          AGGeometryHelper.drawLine(AGGeometryHelper.calcCoefViaCenter(pd), _gl, new double[] {1, 1, 1, 0});*/
        }

        if(!A.isSameDirection(pd)){
          _lastDirection.setPosition(v);
          return false;
        }
        if(A.minus(S).getLength()<=eps || break2>5) break;
        else v.setPosition(v.plus(A.minus(S).multiply(eps)).normalize());
        if(A.getLength()>=OAlengthOld)break2++;
        else{
          break2 = 0;
          OAlengthOld = A.getLength();
        }
      }
      if(Math.abs(Math.acos(pd.getAngle(v)))<angEps || break1>5){ 
          break;
      }
      else pd.setPosition(v);

      break1++;
    }

3. Этоот вопрос относится уже больше к алгоритму sequental impulses - почему то при контакте параллельных боксов бокс с массой в люом случае начинает заворачиваться

+ Показать

− Скрыть

AGVector2D contactPoint = contactManifold.getContactPoint();
    AGObject obj1 = contactManifold.getObj1();
    AGObject obj2 = contactManifold.getObj2();
    AGVector2D contactPoint1 = contactPoint.minus(obj1.getPosition());
    AGVector2D contactPoint2 = contactPoint.minus(obj2.getPosition());
    
    double elasticity = (obj1.getRestitution()+obj2.getRestitution())/2.f;
    AGVector2D relativeLinearVelocity = obj1.getLinearVelocity().minus(obj2.getLinearVelocity());
    
    AGVector2D n1 = new AGVector2D(contactManifold.getNormal());
    double w1 =  n1.cross(contactPoint1);
    AGVector2D n2 = contactManifold.getNormal().minus();
    double w2 = -n1.cross(contactPoint2);

    double initialVelocityProjection =
            n1.dot(obj1.getLinearVelocity())
          + w1 * obj1.getAngularVelocity()
          + n2.dot(obj2.getLinearVelocity())
          + w2 * obj2.getAngularVelocity();
    
    double a = n1.dot(obj1.getLinearVelocity()) + n2.dot(obj2.getLinearVelocity())
        + w1 * obj1.getAngularVelocity()
        + w2 * obj2.getAngularVelocity() + 0.9*initialVelocityProjection;

      double b = n1.dot(n1) * obj1.getInvMass() 
          + w1 * w1 * obj1.getInertialMoment() 
          + n2.dot(n2) * obj2.getInvMass()  
          + w2 * w2 * obj2.getInertialMoment();
      
      double velocityProjection = Math.abs(relativeLinearVelocity.dot(n1));
      //double lambda = ((/*velocityProjection-Math.abs*/(contactManifold.getPD())-a) / b);
      double lambda = (/*0.5f*/-a) / b;

      //lambda *= -1;
      if(lambda<0)
        lambda=0;
    Log.e("c","Lambda: "+lambda);
      
      AGVector2D velocityAfterCollision =
        obj1.getLinearVelocity().plus(n1.multiply(lambda * obj1.getInvMass()));
      //Log.e("c", "n1: "+n1);
      
      double angularVelocityAfterCollision = obj1.getAngularVelocity() 
          + (n1.multiply(lambda).cross(contactPoint1)) * obj1.getInertialMoment();
      Log.e("angle", "angle="+angularVelocityAfterCollision+"; c1=("+contactPoint+");n1="+n1+";");
      
      
      AGVector2D velocityAfterCollision2 =
        obj2.getLinearVelocity().plus(n2.multiply(lambda * obj2.getInvMass()));
      
      double angularVelocityAfterCollision2 = obj2.getAngularVelocity()
          + (n2.multiply(lambda).cross(contactPoint2)) * obj2.getInertialMoment();
      
      obj1.setLinearVelocity(velocityAfterCollision);
      obj1.setAngularVelocity(angularVelocityAfterCollision);
      
      obj2.setLinearVelocity(velocityAfterCollision2);
      obj2.setAngularVelocity(angularVelocityAfterCollision2);

4. Вопрос про контакты - при обнаружении точки контакта я создаю читыре контакт менифолда - правильно ли это - ведь при разрешении точки контакта расталкиваются оба тела.

Заранее спасибо за ответы, буду очень благодарен

Suslik
Постоялец

#89
0:51, 16 апр 2013

fysx
> 1. Нужно ли округлять вектор pd о порядка angEps? без округления вносится
> погрешность и отскоко получается не совсем параллельным.
я pd нахожу обычно с точностью до 1e-2f. более точно смысла находить нет - это ж и так погрешность порядка одного градуса, ты не заметишь визуально разницы

> 2. Почему то работает очень медленно уже на трех объектах. алгоритм зацикливатся, приходится ограничивать количество итераций.
ищи ошибку. он в принципе не может зациклиться, так как стоит условие, что если больше нескольких итераций подряд(я беру четыре) не может улучшить результат, то он считается оптимумом. это условие необходимо, если считаются коллижны для многогранников.

Страницы: 1 … 3 4 5 6 7 8 Следующая »

Тема в архиве.

Слотокинг - лучшие игровые автоматы

obzor365.com