1

作为编写 3D 游戏库的一部分，我正在尝试实现截锥体剔除，以避免渲染相机透视截锥体之外的对象。为此，我首先需要为每个网格计算一个边界球，并查看它是否与视锥体的六个侧面中的任何一个发生碰撞。这是我目前（非常）幼稚的实现，为每个模型计算边界球体，如model.py我的代码中所写：

from pyorama.entity import Entity
from pyorama.math3d.vec3 import Vec3
from pyorama.math3d.mat4 import Mat4
from pyorama.physics.sphere import Sphere
import math
import numpy as np
import itertools as its

class Model(Entity):

    def __init__(self, mesh, texture, transform=Mat4.identity()):
        super(Model, self).__init__()
        self.mesh = mesh
        self.texture = texture
        self.transform = transform

    def compute_bounding_sphere(self):
        vertex_data = self.mesh.vertex_buffer.get_data()
        vertices = []
        for i in range(0, len(vertex_data), 3):
            vertex = Vec3(vertex_data[i: i+3])
            vertices.append(vertex)
        max_pair = None
        max_dist = 0
        for a, b in its.combinations(vertices, 2):
            dist = Vec3.square_distance(a, b)
            if dist > max_dist:
                max_pair = (a, b)
                max_dist = dist
        radius = math.sqrt(max_dist)/2.0
        center = Vec3.lerp(max_pair[0], max_pair[1], 0.5)
        return Sphere(center, radius)

我只是从我的网格中取出成对的点，并使用我找到的最大距离作为我的直径。在每帧 100 个简单的立方体测试模型上调用它非常慢，将我的帧速率从 120 fps 提高到 1 fps！这并不奇怪，因为我假设这个成对代码的时间复杂度是 O(n^2)。

我的问题是，在给定网格中的一组 3D 点的情况下，哪种算法可以快速且相当简单地计算（至少）一个近似边界球？我查看了这个Wikipedia 页面，发现有一种算法叫做“Ritter 的边界球”。但是，这需要我在网格中选择一些随机点 x 并希望它是近似中心，以便我得到一个相当紧凑的边界球。有没有一种快速的方法来选择一个好的起点 x？任何帮助或建议将不胜感激！

更新：

在@Aaron3468 的回答之后，这是我的库中的代码，用于计算边界框和相应的边界球：

from pyorama.entity import Entity
from pyorama.math3d.vec3 import Vec3
from pyorama.math3d.mat4 import Mat4
from pyorama.physics.sphere import Sphere
from pyorama.physics.box import Box
import math
import numpy as np
import itertools as its


class Model(Entity):

    def __init__(self, mesh, texture, transform=Mat4.identity()):
        super(Model, self).__init__()
        self.mesh = mesh
        self.texture = texture
        self.transform = transform

    def compute_bounding_sphere(self):
        box = self.compute_bounding_box()
        a, b = box.min_corner, box.max_corner
        radius = Vec3.distance(a, b)/2.0
        center = Vec3.lerp(a, b, 0.5)
        return Sphere(center, radius)

    def compute_bounding_box(self):
        vertex_data = self.mesh.vertex_buffer.get_data()
        max_corner = Vec3(vertex_data[0:3])
        min_corner = Vec3(vertex_data[0:3])
        for i in range(0, len(vertex_data), 3):
            vertex = Vec3(vertex_data[i: i+3])
            min_corner = Vec3.min_components(vertex, min_corner)
            max_corner = Vec3.max_components(vertex, max_corner)
        return Box(min_corner, max_corner)
4

1 回答 1

2

遍历顶点一次并收集每个维度的最高和最低值。这将创建一个由 Vec3(lowest.x,lowest.y,lowest.z) 和 Vec3(highest.x,highest.y,highest.z) 组成的边界框。

使用每个维度的最高和最低值的中值。这会将盒子的中心创建为 Vec3((lowest.x +highest.x)/2, ...)。

然后得到中心和盒子的8个角中的每一个之间的欧几里得距离。使用最大的距离和你找到的中心来做一个边界圆。

您只对数据集进行了一次迭代，并且对边界圆有了很好的近似！

以这种方式计算的边界圆几乎肯定会比网格更大。要缩小它，您可以将半径设置为距中心最宽尺寸的距离。这种方法确实有砍掉角落里的人脸的风险。

您可以迭代地缩小半径并检查所有点是否都在边界圆中，但是您的性能会比原始算法更差。

于 2017-01-08T09:06:36.270 回答