1

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)
CodeSurgeon
  • 2,435
  • 2
  • 15
  • 36
  • @user3386109 The main reason why I was considering a sphere was because then it is really simple to see if the sphere collides with the sides of the viewing frustum. All you would have to do is a point-plane test. In the hard case when the center of the sphere is outside the frustum, I would just find the shortest distance from the center of the sphere to the plane. If this distance is less than the radius, then that mesh needs to be rendered. Is there a similarly fast way test the box-frustum collision? Either way, I definitely need to implement bounding boxes as well! – CodeSurgeon Jan 08 '17 at 06:01
  • 1
    The best approach may be to load precomputed bounding objects and rotate them to match the mesh's orientation. It's also worth noting that python isn't a very fast language for the kind of number crunching involved with rendering. Using `numpy` is a good optimization, but I'm skeptical about how much it can scale. It may be better to create the engine in C and use python as the scripting language on top. – Aaron3468 Jan 08 '17 at 07:34
  • @Aaron3468 That is probably a reasonable approach for repetitive static geometry. Since in my test scenario, all of the test models use the same mesh data, I can shift the `compute_bounding_volume` function to my `Mesh` class from my `Model` class. All of the classes I wrote for `pyorama.math3d` wrap up `numpy` arrays. All of that code can be found at my [github repo](https://github.com/AnishN/pyorama) page for `pyorama`. I still am inclined to believe that there is something I can do to improve this code besides shifting the burden from runtime to mesh initialization. – CodeSurgeon Jan 08 '17 at 08:10
  • 1
    Iterate over the vertices once and collect the highest and lowest value for each dimension - a bounding box. Use the median value of the highest and lowest value for each dimension - the center of the box. Then get the euclidean distance between the center and each of the 8 corners of the box. Keep the largest distance and the center. You now have a bounding circle with only 1 iteration over the points. – Aaron3468 Jan 08 '17 at 08:43
  • 1
    @Aaron3468 I think you are right. It probably can't get any simpler or faster than that, especially since it only goes once through the vertices! I have went ahead and implemented that and it went up to 25 fps when I calculate the sphere it every frame for each model instead of once at the start. I have added this new code to the question. I will have to probably profile my math3d library and see how bad the bottleneck is there. – CodeSurgeon Jan 08 '17 at 09:07
  • 1
    On a computer 800 times faster than a gameboy, my python emulator only ran about 50% speed... with no audio or video. You're fighting against the grain, but perhaps you'll learn a lot by optimizing this for python :) – Aaron3468 Jan 08 '17 at 09:16

1 Answers1

2

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.

Aaron3468
  • 1,734
  • 16
  • 29