3D Collision Mesh (более эффективный расчет столкновений)

Question

Прежде чем вы помечаете это как дубликат. Я бы хотел, чтобы он знал, что да, есть некоторые вопросы с аналогично названными названиями ... Тем не менее, я прочитал их, и они сильно отличаются друг от друга.

Недавно я завершил полную систему обнаружения столкновений в любом месте от наименьшей до самых сложных 3d-сеток. Проблема заключается в том, что он очень неэффективен и очень дорог для игрового процесса в моем движке. В качестве побочного примечания, я полностью составил этот код, без ссылки, просто чтобы увидеть, могу ли я справиться с подобным конфликтом самостоятельно. Извините за беспорядок. Таким образом, без лишнего шума, вот важный код.

package nope; 

import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.List; 

import org.lwjgl.util.vector.Vector3f; 

import net.aionstudios.nightfall.entities.Entity; 
import net.aionstudios.nightfall.renderEngine.model.TexturedModel; 

public class ColliderEntity extends Entity { 

private List<CollisionMesh> entityBounds = new ArrayList<CollisionMesh>(); 
private boolean alertCollisions = false; 

public ColliderEntity(TexturedModel model, Vector3f position, float rotX, float rotY, float rotZ, float scale, BoundingBox entityBounds) { 
    super(model, position, rotX, rotY, rotZ, scale); 
    this.entityBounds.add(entityBounds); 
} 

public List<ColliderEntity> detectImpact(List<ColliderEntity> colliders){ 
    List<ColliderEntity> colE = new ArrayList<ColliderEntity>(); 
    colE.clear(); 
    for (ColliderEntity ce : colliders) { 
     if(ce != this) { 
      Vector3f boundsOffsets = new Vector3f(difference(this.getPosition().x, ce.getPosition().x), difference(this.getPosition().y, ce.getPosition().y), difference(this.getPosition().z, ce.getPosition().z)); 
      boolean xCollide = false; 
      boolean yCollide = false; 
      boolean zCollide = false; 
      for (CollisionMesh b1 : this.getEntityBounds()){ 
       for(MeshPoint mp : b1.getPoints()){ 
        List<Vector3f> points = mp.getConnectionsAndPoint(); 
        for (CollisionMesh b2 : ce.getEntityBounds()) { 
         for(MeshPoint mp2 : b2.getPoints()){ 
          List<Vector3f> points2 = mp2.getConnectionsAndPoint(); 
          for (Vector3f pt : points2){ 
           pt = new Vector3f(pt.x-boundsOffsets.x, pt.y-boundsOffsets.y, pt.z-boundsOffsets.z); 
           for (int i = 1; i < points.size(); i++){ 
            if(!xCollide || !yCollide || !zCollide){ 
             if(points.get(i-1).x > pt.x && pt.x > points.get(i).x) { 
              xCollide = true; 
             } 
             if(points.get(i-1).y > pt.y && pt.y > points.get(i).y) { 
              yCollide = true; 
             } 
             if(points.get(i-1).z > pt.z && pt.z > points.get(i).z) { 
              zCollide = true; 
             } 
            } 
           } 
          } 
          if(!!xCollide || !yCollide || !zCollide){ 
           for (Vector3f pts : points){ 
            pts = new Vector3f(pts.x-boundsOffsets.x, pts.y-boundsOffsets.y, pts.z-boundsOffsets.z); 
            for (int i = 1; i < points2.size(); i++){ 
             if(!xCollide || !yCollide || !zCollide){ 
              if(points2.get(i-1).x > pts.x && pts.x > points2.get(i).x) { 
               xCollide = true; 
              } 
              if(points2.get(i-1).y > pts.y && pts.y > points2.get(i).y) { 
               yCollide = true; 
              } 
              if(points2.get(i-1).z > pts.z && pts.z > points2.get(i).z) { 
               zCollide = true; 
              } 
             } 
            } 
           } 
          } 
          if(xCollide && yCollide && zCollide){ 
           colE.add(ce); 
           if(alertCollisions) { 
            System.out.println("Collision on Entity "+this.toString()+" at: "+this.getPosition().x+" "+this.getPosition().y+" "+this.getPosition().z+" with Entity "+ce.toString()+" at: "+ce.getPosition().x+" "+ce.getPosition().y+" "+ce.getPosition().z); 
           } 
          } 
         } 
        } 
       } 
      } 
     } 
    } 
    return colE; 
} 

private float difference(float x, float x1){ 
    float dx = x - x1; 

    return (float) Math.sqrt(dx * dx); 
} 

public boolean isAlertCollisions() { 
    return alertCollisions; 
} 

public void setAlertCollisions(boolean alertCollisions) { 
    this.alertCollisions = alertCollisions; 
} 

public List<CollisionMesh> getEntityBounds() { 
    return entityBounds; 
} 

public void addEntityBounds(BoundingBox b){ 
    this.entityBounds.add(b); 
} 

public void removeEntityBounds(BoundingBox b){ 
    this.entityBounds.remove(entityBounds); 
} 

} 

Этот класс является сущностью, которая также имеет коллизионную сетку ... И обнаружение удара. Чтобы понять, что здесь происходит, вам понадобится еще больше понимания.

package nope; 

import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.List; 

import org.lwjgl.util.vector.Vector3f; 

public class CollisionMesh { 

private List<MeshPoint> points = new ArrayList<MeshPoint>(); 

public CollisionMesh(MeshPoint[] points){ 
    for(MeshPoint p : points){ 
     this.points.add(p); 
    } 
} 

public List<MeshPoint> getPoints() { 
    return points; 
} 

public void addMeshPoint(MeshPoint point){ 
    for (MeshPoint p : points){ 
     if(point == p){ 
      return; 
     } 
    } 
    points.add(point); 
} 

public void removeMeshPoint(MeshPoint point){ 
    for(MeshPoint p : points){ 
     if(p == point){ 
      points.remove(point); 
      return; 
     } 
    } 
    cleanupMeshPoints(); 
} 

public void cleanupMeshPoints(){ 
    for(MeshPoint p : points){ 
     for(Vector3f pi : p.getConnections()){ 
      boolean connected = false; 
      for(MeshPoint p2 : points){ 
       if(p2.getPoint() == pi){ 
        connected = true; 
       } 
      } 
      if(!connected){ 
       p.getConnections().remove(pi); 
      } 
     } 
    } 
} 

} 

это столкновение сетки, данное collidable сущности, она состоит из отдельных точек сетки, которые также хранятся там соединения. Вот этот класс:

package nope; 

import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.List; 

import org.lwjgl.util.vector.Vector3f; 

public class MeshPoint { 

private Vector3f point; 
private List<Vector3f> connections = new ArrayList<Vector3f>(); 

public MeshPoint(Vector3f point, Vector3f[] connections){ 
    this.point = point; 
    for(Vector3f connection : connections){ 
     this.connections.add(connection); 
    } 
} 

public Vector3f getPoint() { 
    return point; 
} 

public void setPoint(Vector3f point) { 
    this.point = point; 
} 

public List<Vector3f> getConnections() { 
    return connections; 
} 

public List<Vector3f> getConnectionsAndPoint() { 
    List<Vector3f> cp = connections; 
    cp.add(this.point); 
    return cp; 
} 

public void addConnection(Vector3f connection){ 
    for (Vector3f c : connections){ 
     if(c.x == connection.x && c.y == connection.y && c.z == connection.z){ 
      return; 
     } 
    } 
    connections.add(connection); 
} 

public void removeConnection(Vector3f connection){ 
    for (Vector3f c : connections){ 
     if(c.x == connection.x && c.y == connection.y && c.z == connection.z){ 
      connections.remove(connection); 
      return; 
     } 
    } 
} 

} 

связи в сетке, как я думаю, действительно убивают частоту кадров игры. Который, когда объекты, такие же простые, как 2 коробки, имеют коллизии, включаются с шапки фрейма 120 до обычно около 3. Хотя я могу идентифицировать несколько проблем, я не могу думать, что этот код не будет менее сложным, чем в настоящее время. Буду признателен за любую оказанную помощь.

Я знаю, что такой вопрос обычно не принимается, и многие люди, которые приходят сюда, будут искать минимальный и полный пример ... Но действительно не было ничего, что можно было бы сделать, чтобы сделать это меньше чем он есть.

Answer 1

Предложения:

1. detectImpact не менее 6 вложенных циклов. Неудивительно, что производительность будет страдать. Можно ли уменьшить количество гнездования? Если нет, можете ли вы, по крайней мере, предусмотреть, чтобы ваши данные учитывались в этих циклах? (например, не учитывайте все вершины, но только те, которые находятся внутри перекрытия ограничивающих ящиков, и надеемся, что пересечение ограничивающей коробки будет , а не, содержат большинство этих вершин - если они являются вашим обнаружением столкновения, не выполняли надлежащую работу в предыдущие этапы, прежде чем объекты стали настолько «переплетающимися»).

2. detectImpact самый внутренний цикл находится в форме for (int i = 1; i < points.size(); i++). Изменяется ли во время цикла size()? Если нет, то какова точка вызова (виртуального) метода общего интерфейса? Предложение: создайте локальный var для хранения size и используйте его. Еще лучше попытайтесь использовать форму foreach/for-in, она имеет better performance than the "iterating by index" (да, я отметил, что самый внутренний цикл начинается с 1, просто пропустите первый шаг внутри цикла). Поскольку это самый внутренний цикл, каждый бит подсчитывается.

3. Поскольку вершины/ребра/грани вашей сетки редко меняются после построения, рассмотрите возможность использования массивов вместо списков. Да, приятно иметь гибкость самонастраивающихся контейнеров, но ... нет такой вещи, как бесплатный обед, а производительность - это кошелек, за который вы платите за него.
   Возможно, вы можете немного усовершенствовать жизненный цикл ваших объектов с сеткой, чтобы иметь два разных этапа: построение (когда вы добавляете вершины/ребра в сетку - самонастраивающаяся коллекция пригодится здесь) и «замороженная/пост-строительная сцена» (когда вы используете массивы, а не контейнеры).Вы получите как гибкость, так и производительность, и вы будете платить за счет «сложности кода».