Skip to content

Commit 892405a

Browse files
ProtectedVariableProtectedVariable
committed
optimize Frustum-AABB detection, still is the bottleneck
1 parent 8e3cbe3 commit 892405a

5 files changed

Lines changed: 78 additions & 53 deletions

File tree

‎ICE/Math/include/AABB.h‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -21,6 +21,7 @@ class AABB {
2121
AABB operator+(const AABB& other) const;
2222
AABB unionWith(const AABB& other) const;
2323
Eigen::Vector3f getCenter() const;
24+
Eigen::Vector3f getExtent() const;
2425

2526
const Eigen::Vector3f& getMin() const;
2627

‎ICE/Math/include/ICEMath.h‎

Lines changed: 12 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -24,6 +24,15 @@
2424

2525
namespace ICE {
2626

27+
struct Plane {
28+
Eigen::Vector3f normal;
29+
float distance;
30+
};
31+
32+
struct Frustum {
33+
std::array<Plane, 6> planes; // left, right, top, bottom, near, far
34+
};
35+
2736
Eigen::Matrix4f rotationMatrix(Eigen::Vector3f angles, bool yaw_first = true);
2837
Eigen::Matrix4f translationMatrix(Eigen::Vector3f translation);
2938
Eigen::Matrix4f scaleMatrix(Eigen::Vector3f scale);
@@ -33,8 +42,9 @@ void decomposeMatrix(const Eigen::Matrix4f &M, Eigen::Vector3f &position, Eigen:
3342
Eigen::Vector3f orientation(int face, float x, float y);
3443
int clamp(int x, int a, int b);
3544
std::array<uint8_t *, 6> equirectangularToCubemap(uint8_t *inputPixels, int width, int height, float rotation = 180);
36-
std::array<Eigen::Vector4f, 6> extractFrustumPlanes(const Eigen::Matrix4f &PV);
37-
bool isAABBInFrustum(const std::array<Eigen::Vector4f, 6> &frustum, const AABB &aabb);
45+
Frustum extractFrustumPlanes(const Eigen::Matrix4f &PV);
46+
bool isAABBInFrustum(const Frustum &frustum, const AABB &aabb);
47+
bool isAABBInFrustum(const Frustum &frustum, const Eigen::Vector3f &center, const Eigen::Vector3f &extents);
3848
} // namespace ICE
3949

4050
#endif //ICE_ICEMATH_H

‎ICE/Math/src/AABB.cpp‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -47,6 +47,10 @@ Eigen::Vector3f AABB::getCenter() const {
4747
return (min + max) / 2;
4848
}
4949

50+
Eigen::Vector3f AABB::getExtent() const {
51+
return (max - min) / 2;
52+
}
53+
5054
const Eigen::Vector3f &AABB::getMin() const {
5155
return min;
5256
}

‎ICE/Math/src/ICEMath.cpp‎

Lines changed: 46 additions & 28 deletions
Original file line numberDiff line numberDiff line change
@@ -174,41 +174,59 @@ std::array<uint8_t *, 6> equirectangularToCubemap(uint8_t *inputPixels, int widt
174174
return outputPixels;
175175
}
176176

177-
std::array<Eigen::Vector4f, 6> extractFrustumPlanes(const Eigen::Matrix4f &PV) {
178-
std::array<Eigen::Vector4f, 6> planes;
179-
// Left
180-
planes[0] = {PV(3, 0) + PV(0, 0), PV(3, 1) + PV(0, 1), PV(3, 2) + PV(0, 2), PV(3, 3) + PV(0, 3)};
181-
// Right
182-
planes[1] = {PV(3, 0) - PV(0, 0), PV(3, 1) - PV(0, 1), PV(3, 2) - PV(0, 2), PV(3, 3) - PV(0, 3)};
183-
// Bottom
184-
planes[2] = {PV(3, 0) + PV(1, 0), PV(3, 1) + PV(1, 1), PV(3, 2) + PV(1, 2), PV(3, 3) + PV(1, 3)};
185-
// Top
186-
planes[3] = {PV(3, 0) - PV(1, 0), PV(3, 1) - PV(1, 1), PV(3, 2) - PV(1, 2), PV(3, 3) - PV(1, 3)};
187-
// Near
188-
planes[4] = {PV(3, 0) + PV(2, 0), PV(3, 1) + PV(2, 1), PV(3, 2) + PV(2, 2), PV(3, 3) + PV(2, 3)};
189-
// Far
190-
planes[5] = {PV(3, 0) - PV(2, 0), PV(3, 1) - PV(2, 1), PV(3, 2) - PV(2, 2), PV(3, 3) - PV(2, 3)};
191-
// Normalize planes
192-
for (int i = 0; i < 6; i++) {
193-
float length = sqrt(planes[i](0) * planes[i](0) + planes[i](1) * planes[i](1) + planes[i](2) * planes[i](2));
194-
planes[i](0) /= length;
195-
planes[i](1) /= length;
196-
planes[i](2) /= length;
197-
planes[i](3) /= length;
198-
}
199-
return planes;
177+
Frustum extractFrustumPlanes(const Eigen::Matrix4f &PV) {
178+
Frustum frustum;
179+
auto extract = [](const Eigen::Vector4f &p) {
180+
Plane plane;
181+
182+
Eigen::Vector3f n = p.head<3>();
183+
float length = n.norm();
184+
185+
plane.normal = n / length;
186+
plane.distance = p[3] / length;
187+
188+
return plane;
189+
};
190+
191+
frustum.planes[0] = extract(PV.row(3) + PV.row(0)); // Left
192+
frustum.planes[1] = extract(PV.row(3) - PV.row(0)); // Right
193+
frustum.planes[2] = extract(PV.row(3) + PV.row(1)); // Bottom
194+
frustum.planes[3] = extract(PV.row(3) - PV.row(1)); // Top
195+
frustum.planes[4] = extract(PV.row(3) + PV.row(2)); // Near
196+
frustum.planes[5] = extract(PV.row(3) - PV.row(2)); // Far
197+
198+
return frustum;
200199
}
201200

202-
bool isAABBInFrustum(const std::array<Eigen::Vector4f, 6> &frustum, const AABB &aabb) {
201+
bool isAABBInFrustum(const Frustum &frustum, const AABB &aabb) {
203202
for (int i = 0; i < 6; i++) {
204-
Eigen::Vector3f positive(frustum[i](0) >= 0 ? aabb.getMax().x() : aabb.getMin().x(),
205-
frustum[i](1) >= 0 ? aabb.getMax().y() : aabb.getMin().y(),
206-
frustum[i](2) >= 0 ? aabb.getMax().z() : aabb.getMin().z());
203+
Eigen::Vector3f positive(frustum.planes[i].normal(0) >= 0 ? aabb.getMax().x() : aabb.getMin().x(),
204+
frustum.planes[i].normal(1) >= 0 ? aabb.getMax().y() : aabb.getMin().y(),
205+
frustum.planes[i].normal(2) >= 0 ? aabb.getMax().z() : aabb.getMin().z());
207206

208-
if (frustum[i](0) * positive.x() + frustum[i](1) * positive.y() + frustum[i](2) * positive.z() + frustum[i](3) < 0) {
207+
if (frustum.planes[i].normal(0) * positive.x() + frustum.planes[i].normal(1) * positive.y() + frustum.planes[i].normal(2) * positive.z()
208+
+ frustum.planes[i].distance
209+
< 0) {
209210
return false;
210211
}
211212
}
212213
return true;
213214
}
215+
216+
bool isAABBInFrustum(const Frustum &frustum, const Eigen::Vector3f &center, const Eigen::Vector3f &extents) {
217+
for (int i = 0; i < 6; ++i) {
218+
const Plane &plane = frustum.planes[i];
219+
220+
const Eigen::Vector3f &n = plane.normal;
221+
222+
float r = extents.x() * std::abs(n.x()) + extents.y() * std::abs(n.y()) + extents.z() * std::abs(n.z());
223+
224+
float s = n.dot(center) + plane.distance;
225+
226+
if (s + r < 0.0f)
227+
return false;
228+
}
229+
230+
return true; // At least partially inside
231+
}
214232
} // namespace ICE

‎ICE/System/src/RenderSystem.cpp‎

Lines changed: 15 additions & 23 deletions
Original file line numberDiff line numberDiff line change
@@ -44,6 +44,7 @@ void RenderSystem::update(double delta) {
4444
}
4545

4646
auto frustum = extractFrustumPlanes(proj_mat * view_mat);
47+
Logger::Log(ICE::Logger::DEBUG, "Graphics", "Render Queue Size: %d", m_render_queue.size());
4748
for (const auto &e : m_render_queue) {
4849
auto rc = m_registry->getComponent<RenderComponent>(e);
4950
auto tc = m_registry->getComponent<TransformComponent>(e);
@@ -54,31 +55,22 @@ void RenderSystem::update(double delta) {
5455
continue;
5556

5657
auto model_mat = tc->getWorldMatrix();
57-
58-
// Transform AABB correctly by transforming all 8 corners
59-
auto aabb = m_gpu_bank->getMeshAABB(rc->mesh);
60-
Eigen::Vector3f min_corner = aabb.getMin();
61-
Eigen::Vector3f max_corner = aabb.getMax();
62-
63-
// Generate all 8 corners of the AABB
64-
std::vector<Eigen::Vector3f> transformed_corners;
65-
transformed_corners.reserve(8);
66-
for (int i = 0; i < 8; i++) {
67-
Eigen::Vector3f corner(
68-
(i & 1) ? max_corner.x() : min_corner.x(),
69-
(i & 2) ? max_corner.y() : min_corner.y(),
70-
(i & 4) ? max_corner.z() : min_corner.z()
71-
);
72-
Eigen::Vector4f world_corner = model_mat * Eigen::Vector4f(corner.x(), corner.y(), corner.z(), 1.0);
73-
transformed_corners.push_back(world_corner.head<3>());
74-
}
7558

76-
// Recompute AABB from transformed corners
77-
aabb = AABB(transformed_corners);
78-
if (!isAABBInFrustum(frustum, aabb)) {
79-
continue;
80-
}
59+
auto local_aabb = m_gpu_bank->getMeshAABB(rc->mesh);
60+
Eigen::Vector3f localCenter = local_aabb.getCenter();
61+
Eigen::Vector3f localExtents = local_aabb.getExtent();
8162

63+
Eigen::Matrix3f R = model_mat.block<3, 3>(0, 0);
64+
Eigen::Vector3f T = model_mat.block<3, 1>(0, 3);
65+
66+
Eigen::Vector3f worldCenter = R * localCenter + T;
67+
68+
Eigen::Matrix3f absR = R.cwiseAbs();
69+
Eigen::Vector3f worldExtents = absR * localExtents;
70+
71+
if (!isAABBInFrustum(frustum, worldCenter, worldExtents))
72+
continue;
73+
8274
std::unordered_map<int, Eigen::Matrix4f> bone_matrices;
8375
if (m_registry->entityHasComponent<SkinningComponent>(e)) {
8476
const auto &skinning = m_gpu_bank->getMeshSkinningData(rc->mesh);

0 commit comments

Comments
 (0)