标签: computational-geometry

由于这里发现的Bloomenthal,我一直在使用一种较老的隐式曲面算法,基本上是基于四面体的算法.这种方法效果很好,但有一个缺点.由于它使用固定网格,因此根据所选的网格大小,它会浪费多边形或忽略细节.

所以我的问题是,我有哪些改进方案？是否有任何可自由使用的(源或良好描述)隐式曲面算法,它们更适应模型的曲率？我遗失的任何选项？

到目前为止,我找到了一篇看起来很有前景的论文,对其他人的建议将不胜感激.

我有一个使用3D网格表示的简单游戏,例如:

Blocks grid[10][10][10];

游戏中的人用点和视线向量表示:

double x,y,z, dx,dy,dz;

我用3个嵌套for循环绘制网格:

for(...) for(...) for(...)
   draw(grid[i][j][k]);

显而易见的问题是,当网格的大小增加到数百个时,fps会急剧下降.凭借一些直觉,我意识到:

• 不需要渲染由网格中的其他块隐藏的块
• 不在人的视野范围内的块也不需要渲染(即,在人的背后的块)

我的问题是,给定一个grid[][][],一个人的x,y,z,和视觉载体dx,dy,dz,我怎么能弄清楚哪些块需要渲染的,哪些不是？

我搜索了很多主题并遇到了很多主题,比如'易用的几何库'.

我正在寻找除此之外的东西.我打算编写用于处理3D数据的复杂应用程序(比如说像blender,3ds max,maya或houdini).我正在寻找可用于我的项目的最佳可用几何库(它可以是免费的或商业的).我不在乎它是否易于使用或者它是否复杂.

在这个库的顶部,我想构建这个应用程序的基本功能(如建模,布尔操作,triangulaton,纹理,retopologing工具等).

关键是:

• 它应该很快
• 它应该是可扩展的(从长远来看 - 如果它不提供某些功能 - 它应该是进一步开发的良好基础)
• 它应该允许处理大多数几何类型(三角形,多边形,退化元素)
• 它应该有很多实现的算法来处理这个几何
• 如果可以处理NURBS,Bezier曲线,点云,体素等,那将会很棒.

当然,这可能不是一个单独的图书馆.但是,如果这些库能够无缝地协同工作,那将会很棒.

我知道有增强:几何,CGAL,OpenMesh和PCL.还有其他选择吗？

我有一组2D点,没有组织,我想找到这个集合的"轮廓"(不是凸包).我不能使用alpha形状,因为我有一个速度目标(在普通计算机上不到10毫秒).我的第一种方法是计算网格并找到轮廓正方形(正方形,其中空方块作为邻居).所以我认为我有效地缩减了我的点数(大致从22000到3000).但是我仍然需要改进这个新的集合.

我的问题是:如何在绿点中找到真实的轮廓点？

我在3D空间中有一组点(其中100万,可能更多,如10或1亿)形成一个球体(它们填充球体 - 它们不仅仅在表面上)我希望建立将每个球体连接到其第一个邻居的四面体...寻找四面体化,到目前为止,我发现的只有:

• 用于网格化的算法,但据我所知,它们填充空白空间,而我的点是固定的.
• 用于表面观察的算法,这是非常无关紧要的
• 用于3D图像观察的算法(在医学领域,大多数情况下):更接近但不完全诀窍.

我怎样才能做到这一点？

2014-08-09首先,感谢大家的建议!我是 - 现在仍然是 - 在假期,只是路过来检查是否有人回答......我并没有失望!!!! :-)我想我会首先尝试CGAL,并会从那里看到.我在O(n2)的同一组点上进行了其他数据计算,我预计它将持续大约1周,所以几个小时就不会那么糟糕.分钟将是梦想成真!

假设我在6维空间中给出了一个点云,我可以根据需要进行密集.这些点变成位于低维多面体的表面上(即点矢量(x1,x2,... x6)看起来是共面的).

我想找到这个未知多面体的顶点,我当前的尝试通过Python中的scipy接口使用qhull算法.在开始时,我只会得到错误消息,显然是由较低维度输入和/或许多退化点引起的.我尝试了几种蛮力方法来消除退化点,但不是很成功,所以最后,我想所有这些点都必须位于凸壳上.

这个问题非常有用,因为它建议通过主成分分析减少尺寸.如果我将点投影到4D超平面,则qhull算法运行时没有错误(对于任何更高的维度,它不会运行).

from scipy.spatial import ConvexHull
from sklearn.decomposition import PCA

model = PCA(n_components=4).fit(initial_points)
proj_points = model.transform(initial_points)
hull = ConvexHull(proj_points, qhull_options = "Qx")

上述问题的答案提到,在计算出投影点的凸包后,需要将单纯形变换回来.但是qhull输出只包含索引,为什么这些索引与初始点的索引不匹配？

现在我的问题是我不知道使用哪种精度来实际获得正确的顶点.无论我对点云的密集程度如何,所获得的顶点随着精度的不同而不同.例如,对于(10000,6)数组中的初始点,我得到(其中E0.03是其工作的最大值):

hull1 = ConvexHull(proj_points, qhull_options = "Qx, E0.03")
print len(hull1.vertices)
print hull1.vertices

5
[ 437 2116 3978 7519 9381]

并将其绘制在轴0,1,2(其中蓝点代表初始点云的选择)的某些(非信息丰富的)投影中:

但是为了获得更高的精度(当然),我会得到一个不同的集合:

hull2 = ConvexHull(proj_points, qhull_options = "Qx, E0.003")
print len(hull2.vertices)
print hull2.vertices

29
[  74   75  436  437  756 1117 2116 2366 2618 2937 3297 3615 3616 3978 3979
 4340 4561 4657 4659 4924 …

我正在制作一个图像处理项目,而且我已经陷入了项目的一个步骤.这是情况;

这是我的面具:

我想要检测可以适合这个蒙版的最大尺寸矩形.

我正在为我的项目使用MATLAB.你知道实现这个目标的任何快速方法吗？任何代码示例,方法或技术都会很棒.

编辑1:以下两种算法适用于大量案例.但是在一些困难的情况下,他们都给出了错误的结果.我在我的项目中使用了它们.

我有一堆2D点.你可以在左边的图片上看到它们.它们形成一些带有几个兔子耳朵的戒指.我的目标是找到大的内循环/椭圆,你可以在右侧看到.

什么样的算法对这种情况有用.

我尝试了RANSAC算法的一种变体(取5个随机点,形成一个椭圆,确定一个分数并重复).我以某种方式设计了评分函数,椭圆内部的点得到了很多负点,并且在外面指向,但非常接近得到很多积极点.但结果并不乐观.算法找到了环,但我得到了一些环的随机椭圆,而不是我想要的大内椭圆.

那里有什么好的策略吗？

我正在尝试从以下方法中找到一种更有效的方法来确定一个点属于哪个六角形：

1. 点数组-出于争论的考虑，为10000点。
2. 六边形的中心点数组，大约为1000个六边形。
3. 每个点将恰好属于一个六边形，一些（大多数）六边形将为空。
4. 六边形形成一个完美的网格，一个六边形的点从左上角开始（它将与整个区域的边缘重叠）。

我当前的解决方案有效，但是n * (m log m)我认为在哪里n=length(points)和都比较慢m=length(hexagons)。

我怀疑我可以做得比这好得多，想到的一种解决方案是根据点和六边形到任意点（也许是中间，也许是一个角）的距离对它们（仅一次）进行排序，然后遍历这些点在六边形的一个子集上，从第一个六边形开始，该第一个六边形的到该点的距离> =，到最后一个匹配的六边形。类似地，一旦（点->参照点）和（六边形中心->参照点）之间的距离差大于六边形的“半径”，我们可以停止查看六边形。从理论上讲，由于我们知道每个点都将属于一个六角形，所以我什至不必考虑这种可能性。

我的问题是：是否有很多做比这更好的办法？就复杂性而言，我认为最坏的情况会稍微好一些，n * m但平均情况应该很好，大概在的范围内n * 20（例如，我们只需要查看每个点20个六边形）。以下是我目前效率不高的解决方案，以供参考。

points.forEach((p) => {
  p.hex = _.sortBy(hexes, (hex) => {
    const xDist = Math.abs(hex.middle.x - p.x);
    const yDist = Math.abs(hex.middle.y - p.y);
    return Math.sqrt((xDist * xDist) + (yDist * yDist));
  })[0];
});

我正在使用 C++ 和OpenEXR读取 TiledExr 文件，如下所示

std::vector<double> TiledExrDepthMapExtractor::extractDepthMap(const char* filePath,
    int& width, int& height, ProgressFunc& progressCallback, ErrorFunc& errorCallback)
{
    // Do some stuff then...
    return pixelVector;
}

这是从 C# 调用的

public class ExrDepthMapExtractor : IDepthMapExtractor
{
    public RawDepthMap GetDepthMap(string filePath)
    {
        return ExtractRawDepthMap(filePath, Callbacks.ProgressCallback, Callbacks.ErrorCallback);
    }

    private unsafe RawDepthMap ExtractRawDepthMap(string filePath,
        Callbacks.ProgressFunc progressCallback, Callbacks.ErrorFunc errorCallback)
    {
        using (InternalExtractRawDepthMapWrapper(filePath, out RawDepthMap rdm, progressCallback, errorCallback))
        {
            rdm.Source = filePath;
            return rdm;
        }
    }

    private unsafe PixelVectorSafeHandle InternalExtractRawDepthMapWrapper(
        string filePath, out RawDepthMap rdm, …