标签: aabb

我的应用程序:我正在尝试旋转图像(使用OpenCV和Python)

目前我开发了以下代码,用于旋转输入图像,用黑色边框填充它,给我A.我想要的是B - 旋转图像中最大可能区域裁剪窗口.我称之为轴对齐的边界框.

这与旋转和裁剪基本相同,但是我无法得到关于该问题的答案.此外,该答案显然仅对方形图像有效.我的图像是矩形的.

代码给A:

import cv2
import numpy as np


def getTranslationMatrix2d(dx, dy):
    """
    Returns a numpy affine transformation matrix for a 2D translation of
    (dx, dy)
    """
    return np.matrix([[1, 0, dx], [0, 1, dy], [0, 0, 1]])


def rotateImage(image, angle):
    """
    Rotates the given image about it's centre
    """

    image_size = (image.shape[1], image.shape[0])
    image_center = tuple(np.array(image_size) / 2)

    rot_mat = np.vstack([cv2.getRotationMatrix2D(image_center, angle, 1.0), [0, 0, 1]])
    trans_mat = np.identity(3)

    w2 = image_size[0] * 0.5
    h2 …

嗨,我正在用Java制作体素游戏,在研究我需要学习的所有不同的东西时,我注意到很多游戏都使用AABB进行碰撞检测.然后我记得在Minecraft中也看到了AABB.但是,当我谷歌AABB是什么时,它只提出了其他人的代码,或者历史书中的某些组织.Stackoverflow,什么是AABB？

当我第一次加载对象时,我使用max和min(x,y,z)点计算初始AABB.但这是在物体空间中,物体在世界各地移动,更重要的是旋转.

每次翻译/旋转对象时,如何重新计算新的AABB？基本上每一帧都会发生这种情况,每帧重新计算新的AABB会是一次非常密集的操作吗？如果是这样,那会有什么选择呢？

我知道AABB会使我的碰撞检测不太准确,但实现碰撞检测代码比OBB更容易,我想一次采取这一步骤.

从以下答案中获得一些见解后,这是我当前的代码:

typedef struct sAxisAlignedBoundingBox {
    Vector3D bounds[8];
    Vector3D max, min;
} AxisAlignedBoundingBox;

void drawAxisAlignedBoundingBox(AxisAlignedBoundingBox box) {
    glPushAttrib(GL_LIGHTING_BIT | GL_POLYGON_BIT);

    glEnable(GL_COLOR_MATERIAL);
    glDisable(GL_LIGHTING);

    glColor3f(1.0f, 1.0f, 0.0f);

    glBegin(GL_LINE_LOOP);
        glVertex3f(box.bounds[0].x, box.bounds[0].y, box.bounds[0].z);
        glVertex3f(box.bounds[1].x, box.bounds[1].y, box.bounds[1].z);
        glVertex3f(box.bounds[2].x, box.bounds[2].y, box.bounds[2].z);
        glVertex3f(box.bounds[3].x, box.bounds[3].y, box.bounds[3].z);
    glEnd();

    glBegin(GL_LINE_LOOP);
        glVertex3f(box.bounds[4].x, box.bounds[4].y, box.bounds[4].z);
        glVertex3f(box.bounds[5].x, box.bounds[5].y, box.bounds[5].z);
        glVertex3f(box.bounds[6].x, box.bounds[6].y, box.bounds[6].z);
        glVertex3f(box.bounds[7].x, box.bounds[7].y, box.bounds[7].z);
    glEnd();

    glBegin(GL_LINE_LOOP);
        glVertex3f(box.bounds[0].x, box.bounds[0].y, box.bounds[0].z);
        glVertex3f(box.bounds[5].x, box.bounds[5].y, box.bounds[5].z);
        glVertex3f(box.bounds[6].x, box.bounds[6].y, box.bounds[6].z);
        glVertex3f(box.bounds[1].x, box.bounds[1].y, box.bounds[1].z);
    glEnd();

    glBegin(GL_LINE_LOOP);
        glVertex3f(box.bounds[4].x, box.bounds[4].y, box.bounds[4].z);
        glVertex3f(box.bounds[7].x, box.bounds[7].y, box.bounds[7].z);
        glVertex3f(box.bounds[2].x, box.bounds[2].y, box.bounds[2].z);
        glVertex3f(box.bounds[3].x, …

我有一个由对象空间中心点和半径表示的球体.球体被转换为世界空间,其变换矩阵可以包括尺度,旋转和平移.我需要在世界空间中为球体构建一个轴对齐的边界框,但我不知道该怎么做.

这是我目前的方法,适用于某些情况:

public void computeBoundingBox() {
    // center is the middle of the sphere
    // averagePosition is the middle of the AABB
    // getObjToWorldTransform() is a matrix from obj to world space
    getObjToWorldTransform().rightMultiply(center, averagePosition);

    Point3 onSphere = new Point3(center);
    onSphere.scaleAdd(radius, new Vector3(1, 1, 1));
    getObjToWorldTransform().rightMultiply(onSphere);

    // but how do you know that the transformed radius is uniform?
    double transformedRadius = onSphere.distance(averagePosition);

    // maxBound is the upper limit of the AABB
    maxBound.set(averagePosition);
    maxBound.scaleAdd(transformedRadius, new Vector3(1, 1, 1));

    // minBound is the …

你好。

在过去的一个月里，我一直在从各种来源收集信息，但没有找到适合我的特定问题的想法。所以这里是问题的表述：

给定一个缓冲区几何形式的网格（顶点坐标和顶点索引的 32 位数组 + 附加数组，例如顶点法线、uvs 或切线），计算围绕网格的均匀点网格的有符号距离函数 (SDF)几何学。

更具体地说，我打算在 Maxon 的 Cinema4D 或 Blender 等 3D 引擎中创建类似于 MetaBall 对象的东西。我已经成功地为所有几何图元实现了距离函数，但是任意网格 SDF 需要我实现一种蛮力方法 - 测试每个网格点的每个网格三角形的距离 - 当然，对于复杂的，这变得非常慢网格。

现在，我回想起来，这些问题中的大多数都需要构建一个树状结构，例如八叉树、KD 树、BSP 树或 AABB 树。然后我发现了一些关于所谓的快速扫描算法 （用于求解 Eikonal 方程）的文章，该算法首先需要用 0 填充位于边界（在我的情况下为网格，或最接近网格）的网格点其余的值较大（Infinity），然后迭代求解非线性双曲边值问题（Gauss-Seidel）。我还在CGAL 库中找到了网格 SDF 方法的开源实现。或者，我也考虑过使用一些着色器库（如 GLSL），也许尝试使用 GPU 构建树，但我从未在 JS 或 TS 项目中使用过着色器。

我一直坚持的步骤不仅仅是选择最好的选择，而且实际上实际上至少有效地使用了这些方法中的一种。例如：

• 如果我想实现Fast-Marching Method，我必须遍历所有三角形，然后为每个三角形遍历所有网格点 Gijk，并使用类似于 Marching Cubes 查找表的东西来查找网格单元交叉点（但使用更多选项），我会为相交的单元格顶点插入接近 0 的值。我有一种感觉，这会花费不必要的时间，并且被证明不适合实时更新。

• 我设法在 Unity 中找到了一些Ray Marching SDF计算的例子。此外，由于我从未尝试过直接在 GPU 上计算任何内容，因此我不知道例如并行计算的限制实际上是什么，我也不了解此类计算是如何进行的。我可以并行计算到每个三角形的距离，然后对每个网格点 Gijk 的所有距离进行快速排序吗？如果是这样，我如何将它包含到 TypeScript 项目中？

• 假设我围绕网格中的所有三角形构建了一个AABB 树（应该是 O(n …

你能推荐我吗......

• 要么是经过验证的AABB树的轻量级C/C++实现？
• 或者,另一种有效的数据结构,以及轻量级的C/C++实现,以解决大量三维光线交叉的问题？

"大数字"表示光线和三角形都有几个100k.

我知道AABB树是CGAL库的一部分,可能是像Bullet这样的游戏物理库.但是,我不希望在我的项目中增加一个巨大的额外库.理想情况下,我想使用一个小型浮点型模板化头文件实现.只要它在我的项目中轻松集成,我也会选择一堆CPP文件.依赖boost是可以的.

是的,我用Google搜索,但没有成功.

我应该提一下,我的应用程序上下文是网格处理,而不是渲染.简而言之,我将参考网格的拓扑结构从3D扫描转移到网格的几何体.我正在从顶点和参考网格的法线向3D扫描拍摄光线,我需要通过扫描恢复这些光线的交叉点.

编辑

几个答案/评论指向最近邻数据结构.我已经创建了一个关于使用最近邻方法逼近光线网格交叉点时出现的问题的小图.最近邻方法可以用作在许多情况下起作用的启发式方法,但我不相信它们实际上是系统地解决问题,就像AABB树一样.

我在3d空间中有成千上万个OOBB(面向对象的边界框),它包含简单的细长3d网格.他们紧紧地挤在一起.

我想拍摄光线并找出哪些OOBB被击中.由于我需要执行的光线交叉测试的数量(数百万),对所有OOBB的暴力方法是不够的.

最初我认为使用某种空间分区系统来快速缩小潜在结果会很容易,但像BVH或KDTrees这样的系统依赖于AABB(轴对齐边界框)来加速查询,在我的情况下,那些效率非常低(因为我所包含的网格的对角线性质使得我的紧密堆积的OOBB具有大致相同的AABB).

我在RAPID库中读到了OBBTrees,但看起来它们是从上到下构建的(从多边形汤开始并细分为逐渐变小的OOBB组以形成树),而不是自下而上(从大量OOBB开始)并从他们建立一个树).

有没有其他数据结构可以用来加速交叉口测试？

这是我的OOBB图片.正如你所看到的,它们是紧密的,如果你可以想象它们的AABB会是什么样子,你会发现它们重叠到基于AABB的树不会真正提高性能的程度(因为几乎所有这些都是会被群体中心的射线击中.

值得注意的是,我需要查询所有被光线击中的OOBB,而不仅仅是第一个/最近的一个.

我正在寻找三角形和 AABB 之间相交的实际表面积。目前，我正在使用 Tomas Akenine-M\xc3\xb6ller\ 的 AABB-三角形相交测试，效果非常好 - 但我还需要更多信息来提高我正在开发的实时三角形到体素引擎的渲染质量。

其基本应用将使我能够找出原始模型中的哪个三角形在给定体素中占据最多空间。这使我能够将从模型创建的结果体素与原始三角形 ID 相关联，不仅是为了颜色准确性，而且是为了持久性。

到目前为止，我想到的方法是取三角形和 AABB 的所有交点，将它们成对分组。一旦您拥有所有对，您就可以很容易地找到与实际位于 AABB 之外的对相关的第三个点。然后简单地获取 3 个向量的集合并用它们构造三角形。获取完整的原始三角形的面积，并减去构造的三角形的面积。如果三角形不“主要位于 AABB 内部”，则可以构造 AABB 内部的三角形并将它们加在一起，忽略总面积。我不确定如果三角形在与 AABB 相交时形成非三角形，该怎么办。以下是我提出的一些作为 2D 表示的情况（可能还有更多）：\n

我真的很怀疑我的想法的可行性，所以我愿意接受任何建议。鉴于我的特定问题不需要实际区域，如果有人可能有更好的解决方案，请告诉我。

谢谢。

当我的AABB物理引擎解析一个交叉点时,它通过找到穿透力较小的轴来实现,然后"推出"该轴上的实体.

考虑到"向左跳跃"的例子:

• 如果velocityX大于velocityY,则AABB将实体推出Y轴,有效地停止跳跃(结果:玩家在半空中停止).
• 如果velocityX小于velocitY(图中未显示),则程序按预期工作,因为AABB将实体推出X轴.

我怎么解决这个问题？

源代码:

public void Update()
    {
        Position += Velocity;
        Velocity += World.Gravity;

        List<SSSPBody> toCheck = World.SpatialHash.GetNearbyItems(this);

        for (int i = 0; i < toCheck.Count; i++)
        {
            SSSPBody body = toCheck[i];
            body.Test.Color = Color.White;

            if (body != this && body.Static)
            {                   
                float left = (body.CornerMin.X - CornerMax.X);
                float right = (body.CornerMax.X - CornerMin.X);
                float top = (body.CornerMin.Y - CornerMax.Y);
                float bottom = (body.CornerMax.Y - CornerMin.Y);

                if (SSSPUtils.AABBIsOverlapping(this, body))
                {
                    body.Test.Color = Color.Yellow;

                    Vector2 overlapVector = SSSPUtils.AABBGetOverlapVector(left, right, …

我目前正在尝试提高使用 box2d 物理（实际上是 box2dlights）的游戏的性能。

我有一种方法可以在已知区域内进行多次（假设大约 16 到 64 次）光线投射。我想知道在第一步中对该区域进行 AABB 查询以检查光线投射是否可以报告某些内容是否是个好主意。如果没有，我可以跳过光线投射。但是如果 AABB 查询找到了一些东西，我必须进行光线投射并且查询是多余的。与光线投射（尤其是在 box2d 中）相比，AABB 查询的速度有多快？如果我可以依次跳过一些光线投射，那么做一个经常是多余的 AABB 查询是个好主意吗？