Вычисление ограничивающей сферы для трехмерной сетки в Python

Question

В рамках написания библиотеки 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 до 1 кадра в секунду! Это не удивительно, так как я предполагаю, что временная сложность для этого парного кода равна O(n^2).

Мой вопрос заключается в том, какой алгоритм является быстрым и достаточно простым для реализации, который вычисляет (по крайней мере) приблизительную ограничивающую сферу с учетом набора трехмерных точек из сетки? Я посмотрел на эту страницу в Википедии и увидел, что существует алгоритм под названием "Ограничивающая сфера Риттера". Тем не менее, это требует, чтобы я выбрал некоторую случайную точку 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)

Answer 1

Выполните итерацию по вершинам один раз и соберите самое высокое и самое низкое значение для каждого измерения. Это создает ограничивающий прямоугольник, состоящий из Vec3(наименьший.x, наименьший.y, наименьший.z) и Vec3(наивысший.x, наивысший.y, наивысший.z).

Используйте медианное значение самого высокого и самого низкого значения для каждого измерения. Это создает центр поля как Vec3((наименьшее. Х + наивысшее. Х)/2, ...).

Затем получите евклидово расстояние между центром и каждым из 8 углов коробки. Используйте самое большое расстояние и центр, который вы нашли, чтобы сделать ограничивающий круг.

Вы только один раз перебрали набор данных и получили хорошее приближение к ограничивающему кругу!

---

Ограничительный круг, вычисленный таким образом, почти наверняка будет больше, чем сетка. Чтобы уменьшить его, вы можете установить радиус на расстояние по самому широкому измерению от центра. Этот подход рискует отрубить лица, которые находятся в углах.

Вы можете итеративно уменьшить радиус и проверить, что все точки находятся в ограничивающем круге, но тогда вы приблизитесь к худшей производительности, чем ваш исходный алгоритм.