This talk will highlight the evolution of the object culling system used in the Frostbite engine over the years and why we decide to rewrite a system for BATTLEFIELD 3 that had worked well for 4 shipping titles. The new culling system is developed using a data oriented design that favors simple data layouts which enables very efficient computation using pipelined vector instructions. Concrete examples of how code is developed with this approach and the implications and benefits compared to traditional tree-based systems will be given.
7. Requirements for new system
âșBetter scaling
âșDestruction
âșReal-time editing
âșSimpler code
âșUniïŹcation of sub-systems
Tuesday, March 8, 2011
9. What doesnât work well on these systems?
âșNon-local data
âșBranches
âșSwitching between register types (LHS)
âșTree based structures are usually branch heavy
âșData is the most important thing to address
Tuesday, March 8, 2011
10. What does work well on these systems?
âșLocal data
âș(SIMD) Computing power
âșParallelism
Tuesday, March 8, 2011
11. The new culling
âșOur worlds usually has max ~15000 objects
âșFirst try was to just use parallel brute force
âș3x times faster than the old culling
âș1/5 code size
âșEasier to optimize even further
Tuesday, March 8, 2011
12. The new culling
âșLinear arrays scale great
âșPredictable data
âșFew branches
âșUses the computing power
Tuesday, March 8, 2011
14. Performance numbers (no occlusion)
15000 Spheres
Platform 1 Job 4 Jobs
Xbox 360 1.55 ms (2.10 ms / 4) = 0.52
x86 (Core i7, 2.66 GHz) 1.0 ms (1.30 ms / 4) = 0.32
Playstation 3 0.85 ms ((0.95 ms / 4) = 0.23
Playstation 3 (SPA) 0.63 ms (0.75 ms / 4) = 0.18
Tuesday, March 8, 2011
15. Details of the new culling
âșImprove performance with a simple grid
âșReally an AABB assigned to a âcellâ with spheres
âșSeparate grids for
âș
âș Rendering: Static
âș Rendering: Dynamic
âș Physics: Static
âș Physics: Dynamic
Tuesday, March 8, 2011
16. Data layout
EntityGridCell Block
Block* Pointer Pointer Pointer positions x, y, z, r x, y, z, r âŠ
u8 Count Count Count entityInfo handle, Handle, âŠ
u32 Total Count transformData ⊠⊠âŠ
struct TransformData
{
half rotation[4];
half minAabb[3];
half pad[1];
half maxAabb[3];
half scale[3];
};
Tuesday, March 8, 2011
17. Adding objects
âą Pre-allocated array that we can grab data from
AtomicAdd(âŠ) to âallocâ new block
4k 4k âŠ
EntityGridCell
Block* Pointer Pointer Pointer
u8 Count Count Count
u32 Total Count
Tuesday, March 8, 2011
19. Removing objects
âșUse the âswap trickâ
âșData doesnât need to be sorted
âșJust swap with the last entry and decrease the count
Tuesday, March 8, 2011
20. Rendering culling
âą Letâs look at what the rendering expects
struct EntityRenderCullInfo
{
Handle entity; // handle to the entity
u16 visibleViews; // bits of which frustums that was visible
u16 classId; // type of mesh
float screenArea; // at which screen area entity should be culled
};
Tuesday, March 8, 2011
21. Culling code
while (1)
{
uint blockIter = interlockedIncrement(currentBlockIndex) - 1;
Â
if (blockIter >= blockCount) break;
Â
u32 masks[EntityGridCell::Block::MaxCount] = {}, frustumMask = 1;
Â
block = gridCell->blocks[blockIter];
Â
foreach (frustum in frustums, frustumMask <<= 1)
{
for (i = 0; i < gridCell->blockCounts[blockIter]; ++i)
{
u32 inside = intersect(frustum, block->postition[i]);
masks[i] |= frustumMask & inside;
}
}
Â
for (i = 0; i < gridCell->blockCounts[blockIter]; ++i)
{
// ïŹlter list here (if masks[i] is zero it should be skipped)
// ...
}
}
Tuesday, March 8, 2011
22. Intersection Code
bool intersect(const Plane* frustumPlanes, Vec4 pos)
{
ïŹoat radius = pos.w;
if (distance(frustumPlanes[Frustum::Far], pos) > radius)
return false;
if (distance(frustumPlanes[Frustum::Near], pos) > radius)
return false;
if (distance(frustumPlanes[Frustum::Right], pos) > radius)
return false;
if (distance(frustumPlanes[Frustum::Left], pos) > radius)
return false;
if (distance(frustumPlanes[Frustum::Upper], pos) > radius)
return false;
if (distance(frustumPlanes[Frustum::Lower], pos) > radius)
return false;
Â
return true;
}
Tuesday, March 8, 2011
25. Intersection Code
LHS!
bool intersect(const Plane* frustumPlanes, Vec4 pos) Float branch!
{
float radius = pos.w;
if (distance(frustumPlanes[Frustum::Far], pos) > radius)
return So what do the consoles
false;
think?
if (distance(frustumPlanes[Frustum::Near], pos) > radius)
LHS! return false;
if (distance(frustumPlanes[Frustum::Right], pos) >Float branch!
:(
radius)
return false;
if (distance(frustumPlanes[Frustum::Left], pos) > radius)
return false;
if (distance(frustumPlanes[Frustum::Upper], pos) > radius)
LHS! return false;
if (distance(frustumPlanes[Frustum::Lower], pos) > radius)
return false; Float branch!
return true;
} LHS! Float branch!
Tuesday, March 8, 2011
26. Intersection Code
bool intersect(const Plane* frustumPlanes, Vec4 pos)
{
float radius = pos.w;
if (distance(frustumPlanes[Frustum::Far], pos) > radius)
return false;
if (distance(frustumPlanes[Frustum::Near], pos) > radius)
return false;
if (distance(frustumPlanes[Frustum::Right], pos) > radius)
return false;
if (distance(frustumPlanes[Frustum::Left], pos) > radius)
return false;
if (distance(frustumPlanes[Frustum::Upper], pos) > radius)
return false;
if (distance(frustumPlanes[Frustum::Lower], pos) > radius)
return false;
return true;
}
Tuesday, March 8, 2011
27. Intersection Code
âșHow can we improve this?
âșDot products are not very SIMD friendly
âșUsually need to shuffle data around to get result
âș(x0 * x1 + y0 * y1 + z0 * z1 + w0 * w1)
Tuesday, March 8, 2011
28. Intersection Code
âșRearrange the data from AoS to SoA
Vec 0 X0 Y0 Z0 W0 VecX X0 X1 X2 X3
Vec 1 X1 Y1 Z1 W1 VecY Y0 Y1 Y2 Y3
Vec 2 X2 Y2 Z2 W2 VecZ Z0 Z1 Z2 Z3
Vec 3 X3 Y3 Z3 W3 VecW W0 W1 W2 W3
âșNow we only need 3 instructions for 4 dots!
Tuesday, March 8, 2011
30. New intersection code
âșTwo frustum vs Sphere intersections per loop
âș4 * 3 dot products with 9 instructions
âșLoop over all frustums and merge the result
Tuesday, March 8, 2011
34. New intersection code (4/4)
// Compare against radius
dotA_0123 = vecCmpGTMask(dotA_0123, posA_rrrr);
dotB_0123 = vecCmpGTMask(dotB_0123, posB_rrrr);
dotA45B45 = vecCmpGTMask(dotA45B45, posAB_rrrr);
Vec dotA45 = vecInsert<VecMask::_0011>(dotA45B45, zero);
Vec dotB45 = vecInsert<VecMask::_0011>(zero, dotA45B45);
// collect the results
Vec resA = vecOrx(dotA_0123);
Vec resB = vecOrx(dotB_0123);
resA = vecOr(resA, vecOrx(dotA45));
resB = vecOr(resB, vecOrx(dotB45));
// resA = inside or outside of frustum for point A, resB for point B
Vec rA = vecNotMask(resA);
Vec rB = vecNotMask(resB);
masksCurrent[0] |= frustumMask & rA;
masksCurrent[1] |= frustumMask & rB;
Tuesday, March 8, 2011
35. SPU Pipelining Assembler (SPA)
âșLike VCL (for PS2) but for PS3 SPU
âșCan give you that extra boost if needed
âșDoes software pipelining for you
âșGives about 35% speed boost in the culling
âșNot really that different from using intrinsics
âșAnd coding assembler is fun :)
Tuesday, March 8, 2011
40. Project AABB to screen space
âșCalculate the area of the AABB in screen space
âșIf area is smaller than setting just skip it
âșDue to FOV taking distance doesnât work
Tuesday, March 8, 2011
41. Software Occlusion
âșUsed in Frostbite for 3 years
âșCross platform
âșArtist made occluders
âșTerrain
Tuesday, March 8, 2011
42. Why Software Occlusion?
âșWant to remove CPU time not just GPU
âșCull as early as possible
âșGPU queries troublesome as lagging behind CPU
âșMust support destruction
âșEasy for artists to control
Tuesday, March 8, 2011
43. Software Occlusion
âșSo how does it work?
âșRender PS1 style geometry to a zbuffer using
software rendering
âșThe zbuffer is 256 x 114 ïŹoat
Tuesday, March 8, 2011
51. Occluder triangles
Rasterize Triangles
Input
16 Triangles 16 Triangles 16 Triangles 16 Triangles
256 x 114 zbuffer 256 x 114 zbuffer 256 x 114 zbuffer
Job 0 Job 1 Merge step
<Todo: Fix Colors>
Tuesday, March 8, 2011
52. z-buffer testing
âșCalculate screen space AABB for object
âșGet single distance value
âșTest the square against the z-buffer
Tuesday, March 8, 2011
53. Conclusion
âșAccurate and high performance culling is essential
âșReduces pressure on low-level systems/rendering
âșItâs all about data
âșSimple data often means simple code
âșUnderstanding your target hardware
Tuesday, March 8, 2011
54. Thanks to
âșAndreas Fredriksson (@deplinenoise)
âșChristina Coffin (@christinacoffin)
âșJohan Andersson (@repi)
âșStephen Hill (@self_shadow)
âșSteven Tovey (@nonchaotic)
âșHalldor Fannar
âșEvelyn Donis
Tuesday, March 8, 2011