如何在八叉树中存储三角形 [英] how to store triangles in an octree
问题描述
我正在为CFD软件进行高速数据计算项目。为此，我构建了一个八叉树并用粒子将其化合。对于碰撞检测，对于每个粒子，我已经计算了它的相邻粒子。为此，我有首先计算粒子所在的八角形立方体，并找出位于相邻26个立方体中的所有粒子。这会处理粒子 - 粒子碰撞。现在我有一个处理粒子网格碰撞的任务，我的网格是基于三角形的。为了达到目的，我需要将三角形存储在八叉树中，并且对于八角形立方体中的每个粒子，我必须找出哪些三角形位于相邻的26个立方体中。并且找到三角形所在的八角形立方体似乎是一项艰巨的任务，因为一个三角形可以位于多个立方体中。所以我们需要沿着它的边缘和它的面检查多个点，以便找到它所在的多维数据集。由于八角形立方体和三角形本身的大小可以变化，人们永远无法确定边缘和三角形面上有多少这样的点被用于检查。
所以请帮帮我。在八叉树中存储三角形并查找其位置（即它所在的八叉树立方体）通常遵循的标准程序是什么？
< blockquote>为什么你同时使用一个统一的网格（我从你的26邻居那里理解这个）和一个同一个任务的八叉树（碰撞检测）？
对于宽相碰撞（粒子 - 网格），你可以有一个宽的八叉树。然后在每个填充的宽八叉树节点中，有一个子八叉树来保持它的三角形（粒子 - 三角形）。
首先检查是否与网格进行了碰撞对象并且如果碰撞，则检查子八叉树的哪个三角形。
因为网格数<<三角形的数量，第一个八叉树将足够小，以便能够在每个帧重建。然后在每个子八叉树中，您可以简单地变换坐标而不是重新构建它。网格旋转了吗？然后旋转八叉树，不要重建它。我假设网格是静态的。对于静态网格物体，您也可以将索引数组缓存为以1步而不是log2（n）步进访问节点。如果网格是动态的（并且粒子是动态的，我假设），那么看看松散的八叉树。这些节点的每个节点的容量都高于正常，因此需要更少的更新。
I am doing High Speed Data Calculation project for a CFD software.For this I have constructed an octree and pupulated it with particles.For collision detection,for each particle ,I have already calculated its neighbouring particles.For this purpose I have first calculated in which octree cube the particle lies and found out all the particles that lie in the neighbouring 26 cubes.This handles particle-particle collision. Now I have a task to handle particle-mesh collision and My mesh is triangle based. For the purpose I need to store the triangle in an octree and for each particle in an octree cube, I have to find out which triangles are lying in the neighbouring 26 cubes.And finding in which octree cube the triangle lies seems a difficult task since a single triangle can lie in more than one cube. so we need to check multiple points along its edges and its face to find out in exacltly which cube it lies. And one can never be sure how many such points along the edge and in the face of the triangle be taken for the purpose of checking since the size of the octree cube and triangle itself can be variable.
So Please help me out in this.what are the standard procedures generally followed for storing a triangle in an octree and finding its location(i.e.in which octree cube it lies)?
Why are you using both a uniform grid (I understand this from your "26 neighbor ..") and an octree at the same for same task (collision detection)?
You could have a broad octree for broadphase collisions (particle - mesh). Then in each broad octree node that is filled, have a sub-octree to hold its triangles (particle - triangle).
First check if collision is made with "mesh object" and if it collides, then check which triangle is that by the sub octree.
Since number of mesh << number of triangles, the first octree would be small enough to be able to re-build at each frame. Then in each sub-octree, you can simply "transform" the coordinates instead of re-building it. Did mesh rotate? Then rotate octree, don't rebuild it. I assumed meshes are static. For static meshes, also you can cache index arrays to access nodes at 1 step instead of log2(n) steps. If meshes are dynamic(and also particles are dynamic I assume), then have a look at "loose octree". These have above normal volumes per node hence it needs less frequent updates.
这篇关于如何在八叉树中存储三角形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
