非结构网格编程的兄弟帮个忙

anyone

我说的是颗粒小于网格CELL的情况. 你说的是颗粒总是大于网格CELL的情况, 如果颗粒又是球型那就相你说的那样相对容易了. SPRAY里一般都是颗粒小于网格CELL的. 固体颗粒不了解, 可能说了外行话, 呵呵.
记得你说过100000个颗粒,5000个CELL, 颗粒为什么会大于网格CELL那?

harry

我的颗粒是比cell小，但是当颗粒在cell的面上时（颗粒中心虽然在一个cell内，但体积cell分成好几部分），这个时候要求出这几部分体积用于耦合计算（如果想准确一点，在直角坐标下这个实现没问题，但任意形状的就不行了）。通常球跟球碰，判断都非常成熟，但球跟cell的关系，好像这方面在多相流中讨论比较少，但其他很多专业都在讨论，如果在google搜索 collision detection，一大堆。
讲讲你用box干什么？

anyone

[这个贴子最后由anyone在 2005/11/17 03:40pm 第 1 次编辑]

刚才看错了. 其实球也像BOX一样也是一种简化的几何形状. 对你的问题, "CELL BOX/颗粒"的方法和你"球/CELL顶点"的方法差不多. BOX还有其他用途. 比如判断2个OVERLAP的CELL相交. 有一点, BOX可以做成搜索树, 不知道球好不好做?
至于网格切割问题, 好象有人用LEVEL SET 来做, 不过是针对大颗粒/小CELL的情况.

harry

感觉我们两的思路不一样，我的问题是我有一个球，知道他的坐标，还有一套网格，知道网格每个单元顶点信息，现在要做的就是用什么样的方法能快速确定球（颗粒）处于网格中那个单元

lan2004

这些都是排序问题而已.
也不是很难啊.

harry

我现在的做法是就是刚开始，我把颗粒放在每个网格中，然后计算它在不在这个网格内，在以后的计算中，我就采用附近搜索。这种方法应该说从速度上是不是问题，气固耦合的计算精度也可以（截球问题先不讨论），但是对于结构分区网格（你说的附体网格），提出颗粒附近网格单元的信息有难度，因为你可能会到不同的block中去找这些信息，这需要对网格的拓扑结构非常了解。所以我想采用非结构网格来回避这个问题，但是我又不知非结构网格是否能根据一个网格提取出其临近网格的信息。根据跟你探讨和我以前的思考和讨论，我感觉可以把网格用一系列的box代替，采用一定方法快速找到颗粒在那个box内，然后在根据box和cell的关系，进行进一步的确定。所以我想向你学习bounding box的思想。但我现在就没想通你为什么要计算box相交（不知道液滴的东东，见笑了），在我看来bounding box用来计算液滴和液滴间的碰撞不错，但好像用来确定液滴在网格位置就怪怪的。哎，这个东西要是能当面讨论，几句话就说清楚了。没办法，忍。

harry

下面引用由lan2004在 2005/11/17 05:50pm 发表的内容：
这些都是排序问题而已.
也不是很难啊.

呵呵，说说呀，主要想节约内存和计算时间，如果按常规办法，计算机受不了比如说，1000个颗粒，1000个三维网格，计算时间是10-6秒，那么计算一秒的次数是1000X1000X8X1000000=8e+12次
通常计算这个在程序中不是主要部分，颗粒间的碰撞才是计算大头，希望更多人来探讨。

harry

[这个贴子最后由harry在 2005/11/17 06:27pm 第 1 次编辑]

对于树结构，我的理解就是把颗粒的搜索范围缩小，比如octree，开始用来做非结构化网格，后来有人用它来计算颗粒与颗粒的碰撞，但是对于一些搞颗粒的人，他们很少用这种方法，他们根据一些理论，直接就把颗粒设定在一个固定搜索范围。给我的感觉是对于早期的编程语言如fortran77，应该是后者好一些，但有了f90,c++后，内存可以释放，那么树结构应该有优势，所以我考虑用octree。但是计算颗粒与颗粒碰撞和考虑颗粒在哪个网格内的差别是，
颗粒颗粒碰撞，考虑的是两个球的碰撞（是否相交），那个只要知道两个球心的位置和球的半径，就颗粒判断他们是否相交。
颗粒在网格的位置是，考虑一个球跟一个任意形状的几何体是否相交，如果做简化处理（不考虑切球），就是考虑一个点否在一个几何体内。
应该说上边两个问题很简单，但是当颗粒数太多，网格太多，常规的方法是不行的，别看这两个简单的问题，它是lagrange/euler方法不能向工程推广的症结所在，即使以后计算机高速发展了，如果还要在这个方法上立足，问题也大大的。

anyone

我上一贴说的不是很准确. 不过要细说要打太多字.
简单说一下, 其实我们用的方法没太大区别. 在初始化的时候每个颗粒先找到初始网格, 后面时间步只要搜索临近网格就行了. 我前面说的是找初始网格方法.
因为对任意多边型网格, 判断一个点是不是在网格内部不是很简单的, 至少你要扫描网格所有的面才能确定. 如果不是3角形面, 可能还要把面分成几个3角形来做. 如果要算法稳定, 还需要考虑各种特别情况, 比如点在面上, 点在线上.. 这些计算量加起来再乘上总网格数再乘总颗粒数就不是个小量了. 所以一般前面都会用一些简单算法快速筛选. BOUNDING BOX可以用来做这种筛选. 我猜你用网格点到颗粒的距离来筛选,找到最小距离的点, 再用更精确的算法检测和"最小距离点"共点的所有CELL. 如果用穷尽法, 你这种做法效率应该不错. BOUNDING BOX好处是可以做成树, 树结构可以把搜索范围缩小, 会进一步加速. 我不知道"最小距离点"有没有可能再加速了.
颗粒碰撞对SPRAY液滴其实更难, 而且SPRAY里每个计算"液滴"代表几百几千个实际液滴, 碰撞不可能算准, 所以一般都用最简单方法做, 比如同在一个CELL的液滴就假设他们碰撞. 反正碰撞对大家关心的东西影响不大.
对固体颗粒碰撞检测, 我看到有人单独做一套方形网格专门用来检测, 好象在颗粒大小差不多的情况下, 这种方法效率挺高的, 不知道你是不是也在用?
非结构网格并不复杂. 网格TOPOLOGY涉及NODE/FACE, NODE/CELL, FACE/CELL. 其中只2套关系是基本的, 剩下可以推出来.

anyone

下面引用由lan2004在 2005/11/17 05:50pm 发表的内容：
这些都是排序问题而已.
也不是很难啊.

如果你做过, 那肯定是牛人. 如果没做过, 建议先了解一下再评论.

harry

呵呵，谢谢，这样说就很清楚了
哈哈，你判断一个颗粒在不在网格内的方法跟我差不多，但我不是用距离判断，我是用向量的积（面的法向量与颗粒到面心向量积）来判断，我们组里也有把颗粒投到面上用角度判断，我个人认为，用向量积判断，最快，有几个面就计算几次，并且特别情况可以根据计算结果分析出来。我的穷举法是最笨的那种，不管它用多少时间，他只在程序中用一次。
确实在用box时，当大小颗粒直接比差别很大，小颗粒很多时，box方法很耗时间和内存，因为box的大小的计算是根据最大颗粒直径得到的，但box和neighbour结合后，不但计算量小，而且也不用每步调用这个程序，所以即使用到多尺度上，也没什么问题。但具体上对大规模（几十万颗粒）多尺度问题我不太清楚。
不过看来要用tree的方法和用非结构网格做，很多还要详细考虑，等我做了再向你详细请教。现在得整理已有的东西，不然毕业无望。