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

Question

Как часть написания трехмерной игровой библиотеки, я пытаюсь реализовать отрисовку усечения, чтобы избежать рендеринга объектов, находящихся за пределами перспективы камеры. Для этого мне сначала нужно вычислить ограничительную сферу для каждой сетки и посмотреть, сталкивается ли она с любой из шести сторон смотрового усечения. Вот моя настоящее время (очень) наивная реализация вычисления ограничивающей сферы для каждой модели, как написано в 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? Любая помощь или совет будут очень признательны!

UPDATE:

После @ ответ 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 (low.x, lower.y, lower.z) и Vec3 (наивысший.x, самый высокий.y, самый высокий.z).

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

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

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

---

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

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