As part of writing a 3D game library, I am trying to implement frustum culling in order to avoid rendering objects that are outside of the camera perspective frustum. To do this, I first need to calculate a bounding sphere for each mesh and see if it collides with any of the six sides of the viewing frustum. Here is my currently (very) naive implementation of computing the bounding sphere for each model as written in model.py in my code:
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)
I am just taking pairwise points from my mesh and using the largest distance I find as my diameter. Calling this on 100 simple cube test models every frame is extremely slow, driving my frame rate from 120 fps to 1 fps! This is not surprising since I assume the time complexity for this pairwise code is O(n^2).
My question is what algorithm is fast and reasonably simple to implement that computes (at least) an approximate bounding sphere given a set of 3D points from a mesh? I looked at this Wikipedia page and saw there was an algorithm called "Ritter's bounding sphere." However, this requires me to choose some random point x in the mesh and hope that it is the approximate center so that I get a reasonably tight bounding sphere. Is there a fast method for choosing a good starting point x? Any help or advice would be greatly appreciated!
UPDATE:
Following @Aaron3468's answer, here is the code in my library that would calculate the bounding box and the corresponding bounding sphere:
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)
Iterate over the vertices once and collect the highest and lowest value for each dimension. This creates a bounding box made of Vec3(lowest.x, lowest.y, lowest.z) and Vec3(highest.x, highest.y, highest.z).
Use the median value of the highest and lowest value for each dimension. This creates the center of the box as Vec3((lowest.x + highest.x)/2, ...).
Then get the euclidean distance between the center and each of the 8 corners of the box. Use the largest distance, and the center you found to make a bounding circle.
You've only iterated once through the data set and have a good approximation of the bounding circle!
A bounding circle computed this way is almost certainly going to be bigger than the mesh. To shrink it, you can set the radius to the distance along the widest dimension from the center. This approach does risk chopping off faces that are in the corners.
You can iteratively shrink the radius and check that all points are in the bounding circle, but then you approach worse performance than your original algorithm.