1
作爲編寫3D遊戲庫的一部分，我試圖實施平截頭體剔除以避免呈現超出攝像機視角範圍的對象。要做到這一點，我首先需要爲每個網格計算一個邊界球，並查看它是否與視錐體的六邊中的任何一邊發生碰撞。這是我目前（非常）天真的執行情況在我的代碼寫在model.py計算每個模型的包圍球：在Python中計算三維網格的邊界球形
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幀調用100個簡單的立方體測試模型非常緩慢，將幀頻從120 fps提升到1 fps！這並不奇怪，因爲我假設這個成對代碼的時間複雜度是O（n^2）。
我的問題是什麼算法是快速和合理簡單的實現，計算（至少）給定一組網格3D點的近似邊界球？我查看了this維基百科頁面，看到有一種算法叫做「裏特邊界球」。然而，這要求我在網格中選擇一些隨機點x，並希望它是近似中心，以便我得到相當緊密的邊界球。有沒有一個快速的方法來選擇一個好的起點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)
@ user3386109我之所以選擇一個球體的主要原因是因爲它很容易看出球體是否與視錐體的兩側相碰撞。你所要做的就是點平面測試。在硬球的情況下，當球體的中心在平截頭體之外時，我會發現從球體中心到平面的最短距離。如果這個距離小於半徑，那麼該網格需要被渲染。是否有類似的快速方式來測試盒式平截頭體碰撞？無論哪種方式，我絕對需要實現邊界框！ – CodeSurgeon
最好的方法可能是加載預先計算的邊界對象並旋轉它們以匹配網格的方向。另外值得一提的是，python並不是一種快速的語言，因爲渲染涉及到數字處理。使用'numpy'是一個很好的優化，但我對它可以擴展的程度持懷疑態度。在C中創建引擎並在頂部使用python作爲腳本語言可能會更好。 – Aaron3468
@ Aaron3468對於重複的靜態幾何來說，這可能是一個合理的方法。由於在我的測試場景中，所有測試模型都使用相同的網格數據，因此我可以將'compute_bounding_volume'函數從我的'Model'類中移動到我的'Mesh'類。我爲'pyorama.math3d'編寫的所有類都包裝了'numpy'數組。所有這些代碼都可以在'pyorama'的[github repo]（https://github.com/AnishN/pyorama）頁面找到。我仍然傾向於認爲，除了將運行時的負擔轉移到網格初始化之外，我還可以做些改進這些代碼。 – CodeSurgeon