Last active
June 27, 2022 21:44
-
-
Save JSandusky/25750e06fa945a7df75a199c4ad4ad26 to your computer and use it in GitHub Desktop.
ShadowAtlas / Clustering file
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//**************************************************************************** | |
// | |
// File: LightShadow.cpp | |
// License: MIT | |
// Project: GLVU | |
// | |
//**************************************************************************** | |
#include "LightShadow.h" | |
#include "Renderables.h" | |
#include <atomic> | |
using namespace math; | |
using namespace std; | |
namespace GLVU | |
{ | |
static double atlasSizeTable[] = { | |
1.0 / 2, | |
1.0 / 4, | |
1.0 / 8, | |
1.0 / 16, | |
1.0 / 32, | |
1.0 / 64, | |
1.0 / 128 | |
}; | |
const math::float4 AtlasCellTable::InvalidCell(-1, -1, -1, -1); | |
//**************************************************************************** | |
// | |
// Function: AtlasCellTable::AtlasCellTabe | |
// | |
// Purpose: Constructs and sets up for up to 64x64 units. | |
// | |
//**************************************************************************** | |
AtlasCellTable::AtlasCellTable(int dim) : | |
dim_(dim) | |
{ | |
levels_ = 0; | |
while (dim > 64) | |
{ | |
levels_ += 1; | |
dim /= 2; | |
} | |
cellCount_.resize(levels_ + 1, 0); | |
regions_.resize(levels_ + 1); | |
Clear(); | |
dim = dim_; | |
levelDims_.resize(levels_ + 1); | |
for (int i = 0; i < levels_ + 1; ++i) | |
{ | |
levelDims_[i] = dim; | |
dim /= 2; | |
} | |
} | |
//**************************************************************************** | |
// | |
// Function: AtlasCelLTable::AtlasCellTable | |
// | |
// Purpose: Constructs, and then configures itself to support up to N-levels. | |
// Care should be taken that given params don't result in a level | |
// reaching 0x0 units as there are no safety checks. | |
// | |
//**************************************************************************** | |
AtlasCellTable::AtlasCellTable(int levels, int dim) : | |
dim_(dim), | |
levels_(levels) | |
{ | |
cellCount_.resize(levels_ + 1, 0); | |
regions_.resize(levels_ + 1); | |
Clear(); | |
levelDims_.resize(levels_ + 1); | |
for (int i = 0; i < levels_ + 1; ++i) | |
{ | |
levelDims_[i] = dim; | |
dim /= 2; | |
} | |
} | |
//**************************************************************************** | |
// | |
// Function: AtlasCellTable::GetCell | |
// | |
// Purpose: | |
// | |
// Return: The coordinates of the cell, or the sentinel InvalidCell value. | |
// | |
//**************************************************************************** | |
math::float4 AtlasCellTable::GetCell(int level) | |
{ | |
if (level == -1) | |
return { -1, -1, -1, -1 }; | |
if (cellCount_[level] > 0 || DivideCells(level - 1)) | |
{ | |
auto cell = regions_[level][cellCount_[level] - 1]; | |
cellCount_[level]--; | |
return cell; | |
} | |
else | |
return InvalidCell; | |
} | |
//**************************************************************************** | |
// | |
// Function: AtlasCellTable::CalculateLevel | |
// | |
// Purpose: Calculates subdivision level based on the desired dimensions of the provided tile. | |
// | |
// Return: The level that is appropriate for a given NxN size. | |
// | |
//**************************************************************************** | |
int AtlasCellTable::CalculateLevel(int forSize) const | |
{ | |
for (int i = 0; i < levels_ + 1; ++i) | |
if (levelDims_[i] == forSize) | |
return i; | |
return -1; | |
} | |
//**************************************************************************** | |
// | |
// Function: AtlasCellTable::Clear | |
// | |
// Purpose: Wipes all data and resets to a single full cell. | |
// | |
//**************************************************************************** | |
void AtlasCellTable::Clear() | |
{ | |
cellCount_[0] = 1; | |
regions_[0][0] = float4 { 0.0f, 0.0f, 1.0f, 1.0f }; | |
for (int i = 1; i < levels_ + 1; ++i) | |
cellCount_[i] = 0; | |
} | |
//**************************************************************************** | |
// | |
// Function: AtlasCellTable::ToViewport | |
// | |
// Purpose: Converts UV coordinates into meaningful { START, DIM } viewport | |
// coordinates that other code uses. | |
// | |
// Return: UV mapped to viewport. | |
// | |
//**************************************************************************** | |
math::uint4 AtlasCellTable::ToViewport(math::float4 value) const | |
{ | |
return uint4(value.x * dim_, value.y * dim_, value.Width() * dim_, value.Height() * dim_); | |
} | |
//**************************************************************************** | |
// | |
// Function: AtlasCellTable::Divide | |
// | |
// Purpose: Slices the given rectangle and writes it into the output. | |
// | |
// Why is this unused? | |
// | |
//**************************************************************************** | |
void AtlasCellTable::Divide(float4 rect, float4* output) | |
{ | |
const float width = (rect.z - rect.x); | |
const float height = (rect.w - rect.y); | |
const float halfWidth = (rect.z - rect.x) / 2.0f; | |
const float halfHeight = (rect.w - rect.y) / 2.0f; | |
output[0] = float4 { rect.x, rect.y, rect.x + halfWidth, rect.y + halfHeight }; // 0, 0 -> 0.5, 0.5 | |
output[1] = float4 { rect.x + halfWidth, rect.y, rect.x + width, rect.y + halfHeight }; // 0.5, 0, -> 1.0, 0.5 | |
output[2] = float4 { rect.x, rect.y + halfHeight, rect.x + halfWidth, rect.y + height }; // 0, 0.5 -> 0.5, 1.0 | |
output[3] = float4 { rect.x + halfWidth, rect.y + halfHeight, rect.x + width, rect.y + height }; // 0.5, 0.05 -> 1, 1 | |
} | |
//**************************************************************************** | |
// | |
// Function: AtlasCellTable::SplitCells | |
// | |
// Purpose: Chops up the cells at a given level. | |
// | |
//**************************************************************************** | |
void AtlasCellTable::SplitCells(int size) | |
{ | |
float4 rect = regions_[size][cellCount_[size] - 1]; | |
const float width = (rect.z - rect.x); | |
const float height = (rect.w - rect.y); | |
const float halfWidth = (rect.z - rect.x) / 2.0f; | |
const float halfHeight = (rect.w - rect.y) / 2.0f; | |
cellCount_[size + 1] = 4; | |
cellCount_[size]--; | |
/// |---------| 1,1 | |
// | C | D | | |
/// |----|----| | |
// | A | B | | |
/// 0,0 |---------| | |
// allocation order is D, C, B, A | |
regions_[size + 1][0] = float4 { rect.x, rect.y, rect.x + halfWidth, rect.y + halfHeight }; // 0, 0 -> 0.5, 0.5 | |
regions_[size + 1][1] = float4 { rect.x + halfWidth, rect.y, rect.x + width, rect.y + halfHeight }; // 0.5, 0, -> 1.0, 0.5 | |
regions_[size + 1][2] = float4 { rect.x, rect.y + halfHeight, rect.x + halfWidth, rect.y + height }; // 0, 0.5 -> 0.5, 1.0 | |
regions_[size + 1][3] = float4 { rect.x + halfWidth, rect.y + halfHeight, rect.x + width, rect.y + height }; // 0.5, 0.05 -> 1, 1 | |
} | |
//**************************************************************************** | |
// | |
// Function: AtlasCellTable::DivideCells | |
// | |
// Purpose: Tries to divide a given level into 4 cells, will divide | |
// up the tree as necessary in an attempt to acquire cells. | |
// | |
// Return: True if we were able to, false if division failed. | |
// If failed then there's no room. | |
// | |
//**************************************************************************** | |
bool AtlasCellTable::DivideCells(int level) | |
{ | |
if (level < 0 || level > levels_) | |
return false; | |
if (cellCount_[level] > 0) | |
{ | |
// do we have a cell on our level we can divide? | |
SplitCells(level); | |
return true; | |
} | |
else if (DivideCells(level - 1)) | |
{ | |
// try to go up a level and divide from there | |
SplitCells(level); | |
return true; | |
} | |
else | |
return false; | |
} | |
//**************************************************************************** | |
// | |
// Function: QuadTreeAllocator::QuadTreeAllocator | |
// | |
// Purpose: Constructs and initializes for a given set of dimensions. | |
// | |
//**************************************************************************** | |
QuadTreeAllocator::QuadTreeAllocator(uint32_t width, uint32_t height) : | |
width_(width), | |
height_(height) | |
{ | |
root_ = new Cell(); | |
root_->coords_ = math::uint4::FromPosSize(0, 0, width, height); | |
root_->Free(); | |
} | |
//**************************************************************************** | |
// | |
// Function: QuadTreeAllocator::~QuadTreeAllocator | |
// | |
// Purpose: Deletes the root cell, and thus the entire tree. | |
// | |
//**************************************************************************** | |
QuadTreeAllocator::~QuadTreeAllocator() | |
{ | |
delete root_; | |
root_ = nullptr; | |
} | |
//**************************************************************************** | |
// | |
// Function: QuadTreeAllocator::GetCell | |
// | |
// Purpose: Grabs a cell from the quad-tree with the appropriate dimensions | |
// | |
// Return: Viewport coordinates or -1,-1,-1,-1 if unable to acquire a cell. | |
// | |
//**************************************************************************** | |
math::uint4 QuadTreeAllocator::GetCell(Cell* cell, uint32_t dim, uintptr_t datum) | |
{ | |
// This cell the right size and not taken? | |
// cell is bigger or equal, but half of it would be too small | |
if (cell->Width() >= dim && (cell->Width()/2) < dim && !cell->taken_ && !cell->AnyTaken()) | |
{ | |
cell->taken_ = true; | |
if (datum) | |
{ | |
// if we have a datum then mark so we can try to preserve. | |
auto& found = datumTable_.find(datum); | |
if (found != datumTable_.end()) | |
found->second.first += 1; | |
else | |
datumTable_.insert(make_pair(datum, make_pair(1, cell))); | |
} | |
return cell->ToViewport(); | |
} | |
// if our cell is larger than our size, then continue | |
if (cell->Width() > dim) | |
{ | |
// can we and do we need to divide? | |
if (cell->children_ == nullptr && cell->Width() > 1) | |
cell->Divide(); | |
if (cell->children_) | |
{ | |
for (int i = 0; i < 4; ++i) | |
{ | |
if (cell->children_[i].taken_) | |
continue; | |
auto ret = GetCell(&cell->children_[i], dim, datum); | |
if (ret.Width() > 0) // did we get something valid? | |
return ret; | |
} | |
} | |
} | |
// Return a sentinel for invaid cell, zero sized. | |
return uint4(-1, -1, -1, -1); | |
} | |
//**************************************************************************** | |
// | |
// Function: QuadTreeAllocator::GetCell | |
// | |
// Purpose: Base call for attempting to acquire a cell, | |
// first checks the datum value for whether a cell has been | |
// requested to be used as a sticky. | |
// | |
//**************************************************************************** | |
math::uint4 QuadTreeAllocator::GetCell(uint32_t dim, uintptr_t datum) | |
{ | |
if (datum) | |
{ | |
// if we have a datum then check it | |
auto& found = datumTable_.find(datum); | |
if (found != datumTable_.end()) | |
{ | |
// is our current cell still a good choice? | |
auto foundWidth = found->second.second->Width(); | |
if (foundWidth >= dim && (foundWidth / 2) < dim) | |
{ | |
found->second.first += 1; | |
found->second.second->taken_ = true; | |
return found->second.second->ToViewport(); | |
} | |
// not the same size, free the cell we found. | |
found->second.second->taken_ = false; | |
datumTable_.erase(found); | |
} | |
} | |
return GetCell(root_, dim, datum); | |
} | |
//**************************************************************************** | |
// | |
// Function: QuadTreeAllocator::QuadTreeAllocator | |
// | |
// Purpose: Constructs and initializes for a given set of dimensions. | |
// | |
//**************************************************************************** | |
void QuadTreeAllocator::ProcessUpdate() | |
{ | |
// Check and see if anything has expired. | |
vector<uint32_t> toRemove; | |
for (auto& rec : datumTable_) | |
{ | |
// anyone that's at 0 should be cleaned since it wasn't marked with a +1 again | |
if (rec.second.first <= 0) | |
toRemove.push_back(rec.first); | |
rec.second.first -= 1; // now mark everything down as having been through a cycle. | |
} | |
// remove everything we need to | |
for (auto r : toRemove) | |
datumTable_.erase(r); | |
// Free everything indiscriminately (mark them taken again soon). | |
root_->Free(); | |
// mark anyone left in the table as taken so that others can't take it. | |
for (auto& rec : datumTable_) | |
rec.second.second->taken_ = true; | |
} | |
//**************************************************************************** | |
// | |
// Function: QuadTreeAllocator::ReturnCell | |
// | |
// Purpose: Returns the cell associated to a datum back to the allocator. | |
// | |
//**************************************************************************** | |
void QuadTreeAllocator::ReturnCell(uintptr_t datum) | |
{ | |
auto& found = datumTable_.find(datum); | |
if (found != datumTable_.end()) | |
{ | |
found->second.second->taken_ = false; | |
datumTable_.erase(found); | |
} | |
} | |
//**************************************************************************** | |
// | |
// Function: QuadTreeAllocator::Cell::AnyTaken | |
// | |
// Purpose: Checks if this cell or any of its' children are marked as taken. | |
// | |
// Return: True, if taken. | |
// | |
//**************************************************************************** | |
bool QuadTreeAllocator::Cell::AnyTaken() const | |
{ | |
if (children_) | |
{ | |
if (children_[0].AnyTaken() || | |
children_[1].AnyTaken() || | |
children_[2].AnyTaken() || | |
children_[3].AnyTaken()) | |
return true; | |
} | |
return taken_; | |
} | |
//**************************************************************************** | |
// | |
// Function: QuadTreeAllocator::CollectRects | |
// | |
// Purpose: Recurses through the tree collecting the rectangles of everything | |
// that isn't claimed, this can be used to gather the minimum number | |
// of clear rects for something like vkCmdClearAttachments. | |
// | |
//**************************************************************************** | |
void QuadTreeAllocator::CollectRects(Cell* cell, vector<uint4>& holder) | |
{ | |
if (cell->AnyTaken()) | |
{ | |
if (cell->children_) | |
{ | |
if (!cell->children_[0].taken_) | |
CollectRects(&cell->children_[0], holder); | |
if (!cell->children_[1].taken_) | |
CollectRects(&cell->children_[1], holder); | |
if (!cell->children_[2].taken_) | |
CollectRects(&cell->children_[2], holder); | |
if (!cell->children_[3].taken_) | |
CollectRects(&cell->children_[3], holder); | |
} | |
} | |
else | |
holder.push_back(cell->ToViewport()); | |
} | |
//**************************************************************************** | |
// | |
// Function: QuadTreeAllocator::CollectRects | |
// | |
// Purpose: Public wrapper around the recursive rect collector. | |
// | |
//**************************************************************************** | |
void QuadTreeAllocator::CollectRects(vector<uint4>& holder) | |
{ | |
CollectRects(root_, holder); | |
} | |
//**************************************************************************** | |
// | |
// Function: QuadTreeAllocator::Clear | |
// | |
// Purpose: Resets state of the quad-tree allocator so that everything is clear. | |
// | |
//**************************************************************************** | |
void QuadTreeAllocator::Clear() | |
{ | |
root_->Clear(); | |
datumTable_.clear(); | |
} | |
//**************************************************************************** | |
// | |
// Function: RenderTargetAtlas::RenderTargetAtlas | |
// | |
// Purpose: Construct and setup the textures + FBOs. | |
// | |
//**************************************************************************** | |
RenderTargetAtlas::RenderTargetAtlas(GraphicsDevice* device, TextureFormat format, uint32_t dim, bool withDepth) : | |
dim_(dim), | |
atlasTable_(dim, dim) | |
{ | |
TextureTraits t = { }; | |
t.width_ = dim; | |
t.height_ = dim; | |
t.kind_ = Texture2D; | |
t.format_ = format; | |
t.colorAttachment_ = !IsDepth(format); | |
t.depthAttachment_ = IsDepth(format); | |
t.mips_ = 1; | |
shadowAtlas_ = device->CreateTexture(t); | |
if (withDepth) | |
{ | |
t.format_ = TEX_DEPTH; | |
t.colorAttachment_ = false; | |
t.depthAttachment_ = true; | |
auto depthTex = device->CreateTexture(t); | |
shadowFBO_ = device->CreateFrameBuffer({ shadowAtlas_, depthTex }); | |
} | |
else | |
shadowFBO_ = device->CreateFrameBuffer({ shadowAtlas_ }); | |
} | |
//**************************************************************************** | |
// | |
// Function: RenderTargetAtlas::GetShadowRect | |
// | |
// Purpose: Acquires a UV cell that's dim-by-dim units. | |
// | |
// Return: The UV-coords of the cell, or InvalidCell sentinel value | |
// | |
//**************************************************************************** | |
float4 RenderTargetAtlas::GetShadowRect(uint32_t dim) | |
{ | |
auto c = atlasTable_.GetCell(dim); | |
return float4(c.x / (float)atlasTable_.width_, c.y / (float)atlasTable_.height_, c.z / (float)atlasTable_.width_, c.w / (float)atlasTable_.height_); | |
//return atlasTable_.GetArea(dim); | |
} | |
//**************************************************************************** | |
// | |
// Function: LightTiler::LightTiler | |
// | |
// Purpose: Constructs buffers for Tiled/Clustered lighting methods. | |
// Actual scheme is arbitrary, and could be: | |
// | |
// XY: Forward-tiled | |
// XZ: Just Cause 2 | |
// XYZ: clustered | |
// | |
// Because the light recording is done on the CPU here the tests | |
// are crude AABB tests that will cause a lot of false positives. | |
// | |
//**************************************************************************** | |
struct ClusterInfo { | |
float3 minVec; | |
float pad0; | |
float3 maxVec; | |
float pad1; | |
uint3 tiles; | |
int pad2; | |
}; | |
LightTiler::LightTiler(GraphicsDevice* device, uint3 cells, uint32_t lightsPerCell) : | |
lightsPerCell_(lightsPerCell), | |
tileDim_(cells), | |
device_(device) | |
{ | |
maxLights_ = (uint32_t)floorf(device->GetGPUFeatures().maxUBOSize_ / sizeof(LightData)); | |
cellsUBO_ = device->CreateShaderStorageBuffer(); | |
cellsUBO_->SetStride(sizeof(uint4)); | |
cellsUBO_->SetSize(sizeof(uint4) * CellCount()); | |
lightsUBO_ = device->CreateShaderStorageBuffer(); | |
lightsUBO_->SetStride(sizeof(LightData)); | |
lightsUBO_->SetSize(sizeof(LightData) * maxLights_); | |
lightIndexesUBO_ = device->CreateShaderStorageBuffer(); | |
lightIndexesUBO_->SetStride(sizeof(unsigned)); | |
lightIndexesUBO_->SetSize(sizeof(unsigned) * lightsPerCell_ * CellCount()); | |
clusterInfo_ = device->CreateUniformBuffer(); | |
clusterInfo_->SetSize(sizeof(ClusterInfo)); | |
} | |
//**************************************************************************** | |
// | |
// Function: LightTiler::BuildLightTables | |
// | |
// Purpose: Constructs buffers for Tiled/Clustered lighting methods. | |
// Actual scheme is arbitrary, and could be: | |
// | |
// XY: Forward-tiled | |
// XZ: Just Cause 2 | |
// XYZ: clustered | |
// | |
// Because the light recording is done on the CPU here the tests | |
// are crude AABB tests that will cause a lot of false positives. | |
// | |
//**************************************************************************** | |
uint32_t LightTiler::BuildLightTables(Camera* camera, const vector< shared_ptr<Light> >& lights) | |
{ | |
auto proj = camera->GetViewProjection(); | |
const float zStep = 1.0f / tileDim_.z; | |
const float yStep = 1.0f / tileDim_.y; | |
const float xStep = 1.0f / tileDim_.x; | |
vector<uint4> lightCounts(CellCount(), { 0, 0, 0, 0 }); | |
vector<uint32_t> lightIndices(CellCount() * lightsPerCell_); | |
vector<LightData> lightRawData; | |
uint32_t hitCt = 0; | |
for (auto& l : lights) | |
{ | |
LightData d; | |
d.lightMat = l->GetShadowMatrix(0); | |
d.lightPos = float4(l->GetPosition(), l->GetKind()); | |
d.lightDir = float4(l->GetDirection(), l->GetRadius()); | |
d.color = l->GetColor(); | |
d.shadowMapCoords[0] = l->GetShadowDomain(0); | |
d.shadowMapCoords[1] = l->GetShadowDomain(1); | |
d.fov = l->GetFOV(); | |
d.castShadows = l->IsShadowCasting() ? 1.0f : 0.0f; | |
d.goboIndex = 0.0f; | |
d.rampIndex = 0.0f; | |
lightRawData.push_back(d); | |
} | |
auto frus = camera->GetFrustum(); | |
auto viewMat = frus.ViewProjMatrix(); | |
float viewRange = frus.FarPlaneDistance() - frus.NearPlaneDistance(); | |
for (unsigned lightIndex = 0; lightIndex < lights.size() && lightIndex < maxLights_; ++lightIndex) | |
{ | |
auto& l = lights[lightIndex]; | |
auto aabb = l->GetBounds(); | |
if (!frus.IsInsideFast(aabb)) | |
continue; | |
float4 pts[8]; | |
for (int i = 0; i < 8; ++i) | |
pts[i] = viewMat.Mul(POINT_TO_FLOAT4(aabb.CornerPoint(i))); | |
for (int i = 0; i < 8; ++i) | |
{ | |
auto invW = 1.0f / pts[i].w; | |
pts[i].x *= invW; | |
pts[i].y *= invW; | |
} | |
auto minPt = pts[0]; | |
auto maxPt = pts[0]; | |
for (int i = 1; i < 8; ++i) | |
{ | |
minPt = minPt.Min(pts[i]); | |
maxPt = maxPt.Max(pts[i]); | |
} | |
int zStartIndex = toSliceZ(minPt.z, frus.NearPlaneDistance(), frus.FarPlaneDistance()); | |
int zEndIndex = toSliceZ(maxPt.z, frus.NearPlaneDistance(), frus.FarPlaneDistance()); | |
int yStartIndex = (int)floorf((minPt.y*0.5f+0.5f) * (float)tileDim_.y); | |
int yEndIndex = (int)ceilf( (maxPt.y*0.5f+0.5f) * (float)tileDim_.y); | |
int xStartIndex = (int)floorf((minPt.x*0.5f+0.5f) * (float)tileDim_.x); | |
int xEndIndex = (int)ceilf( (maxPt.x*0.5f+0.5f) * (float)tileDim_.x); | |
// Now cull the light | |
if ((zStartIndex < 0 && zEndIndex < 0) || (zStartIndex >= (int)tileDim_.z && zEndIndex >= (int)tileDim_.z)) | |
continue; | |
if ((yStartIndex < 0 && yEndIndex < 0) || (yStartIndex >= (int)tileDim_.y && yEndIndex >= (int)tileDim_.y)) | |
continue; | |
if ((xStartIndex < 0 && xEndIndex < 0) || (xStartIndex >= (int)tileDim_.x && xEndIndex >= (int)tileDim_.x)) | |
continue; | |
zStartIndex = math::Clamp<int>(zStartIndex, 0, tileDim_.z - 1); | |
zEndIndex = Clamp<int>(zEndIndex, 0, tileDim_.z - 1); | |
yStartIndex = Clamp<int>(yStartIndex, 0, tileDim_.y - 1); | |
yEndIndex = Clamp<int>(yEndIndex, 0, tileDim_.y - 1); | |
xStartIndex = Clamp<int>(xStartIndex, 0, tileDim_.x - 1); | |
xEndIndex = Clamp<int>(xEndIndex, 0, tileDim_.x - 1); | |
for (auto z = zStartIndex; z <= zEndIndex; ++z) | |
{ | |
for (auto y = yStartIndex; y <= yEndIndex; ++y) | |
{ | |
for (auto x = xStartIndex; x <= xEndIndex; ++x) | |
{ | |
auto clusterID = x + y * tileDim_.x + z * tileDim_.x * tileDim_.y; | |
lightIndices[clusterID * lightsPerCell_ + lightCounts[clusterID].x % lightsPerCell_] = lightIndex; | |
lightCounts[clusterID].x += 1; | |
++hitCt; | |
} | |
} | |
} | |
} | |
cellsUBO_->SetData(lightCounts.data(), sizeof(uint4) * lightCounts.size()); | |
lightsUBO_->SetData(lightRawData.data(), sizeof(LightData) * lightRawData.size()); | |
lightIndexesUBO_->SetData(lightIndices.data(), sizeof(uint32_t) * lightIndices.size()); | |
transform_.SetIdentity(); | |
return hitCt; | |
} | |
AABB LightTiler::ComputeFroxelBounds(Camera* camera, float x, float y, float z) const | |
{ | |
auto frus = camera->GetFrustum(); | |
frus.SetKind(FrustumSpaceD3D, FrustumLeftHanded); | |
const float froxelWidthInClipSpace = 2.0f / tileDim_.x; | |
const float froxelHeightInClipSpace = 2.0f / tileDim_.y; | |
const float froxelDepth = 1.0f / tileDim_.z; | |
float3 steps = float3(1,1,1) / float3(tileDim_.x, tileDim_.y, tileDim_.z); | |
float xFracStart = x*froxelWidthInClipSpace - 1; | |
float xFracEnd = (x+1)*froxelWidthInClipSpace - 1; | |
float yFracStart = y*froxelHeightInClipSpace - 1; | |
float yFracEnd = (y+1) * froxelHeightInClipSpace - 1; | |
float zFracStart = z * froxelDepth; | |
float zFracEnd = (z + 1) * froxelDepth; | |
AABB bnds; | |
bnds.SetNegativeInfinity(); | |
bnds.Enclose(frus.PointInside(xFracStart, yFracStart, zFracStart)); | |
bnds.Enclose(frus.PointInside(xFracStart, yFracStart, zFracEnd)); | |
bnds.Enclose(frus.PointInside(xFracStart, yFracEnd, zFracStart)); | |
bnds.Enclose(frus.PointInside(xFracStart, yFracEnd, zFracEnd)); | |
bnds.Enclose(frus.PointInside(xFracEnd, yFracStart, zFracStart)); | |
bnds.Enclose(frus.PointInside(xFracEnd, yFracStart, zFracEnd)); | |
bnds.Enclose(frus.PointInside(xFracEnd, yFracEnd, zFracStart)); | |
bnds.Enclose(frus.PointInside(xFracEnd, yFracEnd, zFracEnd)); | |
return bnds; | |
} | |
//**************************************************************************** | |
// | |
// Function: LightTiler::BuildLightTables_Radial | |
// | |
// Purpose: For VR we can use spherical-coordinates in order to do both eyes at once. | |
// Assumes the light-list provided contains. | |
// | |
// WARNING: Camera[0] needs to be a "control" "head" camera for frustum info | |
// and the head position. Only actually supports up to 3 cameras, | |
// doesn't currently work in a CAVE setting. | |
// | |
//**************************************************************************** | |
#pragma optimize("", off) | |
uint32_t LightTiler::BuildLightTables_Radial(Camera** cameras, int camCt, const std::vector< std::shared_ptr<Light> >& lights) | |
{ | |
const float zStep = 1.0f / tileDim_.z; | |
const float yStep = 1.0f / tileDim_.y; | |
const float xStep = 1.0f / tileDim_.x; | |
vector<uint4> lightCounts(CellCount(), { 0, 0, 0, 0 }); | |
vector<uint32_t> lightIndices(CellCount() * lightsPerCell_); | |
vector<LightData> lightRawData; | |
uint32_t hitCt = 0; | |
for (auto& l : lights) | |
{ | |
LightData d; | |
d.lightMat = l->GetShadowMatrix(0); | |
d.lightPos = float4(l->GetPosition(), l->GetKind()); | |
d.lightDir = float4(l->GetDirection(), l->GetRadius()); | |
d.color = l->GetColor(); | |
d.shadowMapCoords[0] = l->GetShadowDomain(0); | |
d.shadowMapCoords[1] = l->GetShadowDomain(1); | |
d.fov = l->GetFOV(); | |
d.castShadows = l->IsShadowCasting() ? 1.0f : 0.0f; | |
d.goboIndex = 0.0f; | |
d.rampIndex = 0.0f; | |
lightRawData.push_back(d); | |
} | |
Camera* headCam = nullptr, *leftEye = nullptr, *rightEye = nullptr; | |
for (int i = 0; i < camCt; ++i) | |
{ | |
if (cameras[i]->GetNature() == Camera::Default) | |
headCam = cameras[i]; | |
else if (cameras[i]->GetNature() == Camera::LeftEye) | |
leftEye = cameras[i]; | |
else if (cameras[i]->GetNature() == Camera::RightEye) | |
rightEye = cameras[i]; | |
} | |
leftEye = leftEye == nullptr ? headCam : leftEye; | |
rightEye = rightEye == nullptr ? headCam : rightEye; | |
const auto frus = headCam->GetFrustum(); | |
const float3 minVec = leftEye->GetFrustum().Edge(0).Dir().Normalized(); // bottom left edge | |
const float3 maxVec = rightEye->GetFrustum().Edge(11).Dir().Normalized(); // bottom right edge | |
float3 viewRight, viewFore; | |
ClusterInfo info; | |
info.minVec = minVec; | |
info.maxVec = maxVec; | |
info.tiles = tileDim_; | |
clusterInfo_->SetData(&info, sizeof(info)); | |
float3x3 sphereSpaceTransform = float3x3::RotateFromTo(float3(0.0f, 0.0f, 1.0f), minVec); | |
const auto totalAngle = maxVec.ToSphericalCoordinates() - minVec.ToSphericalCoordinates(); | |
for (unsigned lightIndex = 0; lightIndex < lights.size() && lightIndex < maxLights_; ++lightIndex) | |
{ | |
auto& l = lights[lightIndex]; | |
auto aabb = l->GetBounds(); | |
float3 pts[8]; | |
for (int i = 0; i < 8; ++i) | |
pts[i] = (aabb.CornerPoint(i) - headCam->GetPosition()).ToSphericalCoordinates(); | |
auto minPt = pts[0]; | |
auto maxPt = pts[0]; | |
for (int i = 1; i < 8; ++i) | |
{ | |
minPt = minPt.Min(pts[i]); | |
maxPt = maxPt.Max(pts[i]); | |
} | |
int zStartIndex = toSliceZ(minPt.z, frus.NearPlaneDistance(), frus.FarPlaneDistance()); | |
int zEndIndex = toSliceZ(maxPt.z, frus.NearPlaneDistance(), frus.FarPlaneDistance()); | |
int yStartIndex = (int)floorf(math::InvLerp(minVec.y, maxVec.y, minPt.x) * tileDim_.x); | |
int yEndIndex = (int)ceilf(math::InvLerp(minVec.y, maxVec.y, maxPt.x) * tileDim_.x); | |
int xStartIndex = (int)floorf(math::InvLerp(minVec.x, maxVec.x, minPt.x) * tileDim_.x); | |
int xEndIndex = (int)ceilf(math::InvLerp(minVec.x, maxVec.x, maxPt.x) * tileDim_.x); | |
// Now cull the light, casts aren't optional | |
if ((zStartIndex < 0 && zEndIndex < 0) || (zStartIndex >= (int)tileDim_.z && zEndIndex >= (int)tileDim_.z)) | |
continue; | |
if ((yStartIndex < 0 && yEndIndex < 0) || (yStartIndex >= (int)tileDim_.y && yEndIndex >= (int)tileDim_.y)) | |
continue; | |
if ((xStartIndex < 0 && xEndIndex < 0) || (xStartIndex >= (int)tileDim_.x && xEndIndex >= (int)tileDim_.x)) | |
continue; | |
zStartIndex = math::Clamp<int>(zStartIndex, 0, tileDim_.z - 1); | |
zEndIndex = Clamp<int>(zEndIndex, 0, tileDim_.z - 1); | |
yStartIndex = Clamp<int>(yStartIndex, 0, tileDim_.y - 1); | |
yEndIndex = Clamp<int>(yEndIndex, 0, tileDim_.y - 1); | |
xStartIndex = Clamp<int>(xStartIndex, 0, tileDim_.x - 1); | |
xEndIndex = Clamp<int>(xEndIndex, 0, tileDim_.x - 1); | |
for (auto z = zStartIndex; z <= zEndIndex; ++z) | |
{ | |
for (auto y = yStartIndex; y <= yEndIndex; ++y) | |
{ | |
for (auto x = xStartIndex; x <= xEndIndex; ++x) | |
{ | |
auto clusterID = x + y * tileDim_.x + z * tileDim_.x * tileDim_.y; | |
lightIndices[clusterID * lightsPerCell_ + lightCounts[clusterID].x % lightsPerCell_] = lightIndex; | |
lightCounts[clusterID].x += 1; | |
++hitCt; | |
} | |
} | |
} | |
} | |
cellsUBO_->SetData(lightCounts.data(), sizeof(uint4)* lightCounts.size()); | |
lightsUBO_->SetData(lightRawData.data(), sizeof(LightData)* lightRawData.size()); | |
lightIndexesUBO_->SetData(lightIndices.data(), sizeof(uint32_t)* lightIndices.size()); | |
transform_ = sphereSpaceTransform; | |
return hitCt; | |
} | |
#pragma optimize("", on) | |
//**************************************************************************** | |
// | |
// Function: LightTiler::BuildLightTables_Brute | |
// | |
// Purpose: Heavyweight AABB intersection for Light -> Froxel associations. | |
// You shouldn't use this. | |
// | |
//**************************************************************************** | |
uint32_t LightTiler::BuildLightTables_Brute(Camera* camera, const std::vector< std::shared_ptr<Light> >& lights) | |
{ | |
vector<uint4> lightCounts(CellCount(), { 0, 0, 0, 0 }); | |
vector<uint32_t> lightIndices(CellCount() * lightsPerCell_); | |
vector<LightData> lightRawData; | |
AABB* froxels = new AABB[CellCount()]; | |
for (int z = 0; z < tileDim_.z; ++z) | |
for (int y = 0; y < tileDim_.y; ++y) | |
for (int x = 0; x < tileDim_.x; ++x) | |
froxels[toIndex(x, y, z)] = ComputeFroxelBounds(camera, x, y, z); | |
uint32_t hitCt = 0; | |
for (uint32_t lightIndex = 0; lightIndex < lights.size(); ++lightIndex) | |
{ | |
auto light = lights[lightIndex]; | |
auto lightBnds = light->GetBounds(); | |
for (int z = 0; z < tileDim_.z; ++z) | |
for (int y = 0; y < tileDim_.y; ++y) | |
for (int x = 0; x < tileDim_.x; ++x) | |
{ | |
auto& froxel = froxels[toIndex(x, y, z)]; | |
if (froxel.Intersects(lightBnds)) | |
{ | |
auto clusterID = x + y * tileDim_.x + z * tileDim_.x * tileDim_.y; | |
lightIndices[clusterID * lightsPerCell_ + lightCounts[clusterID].x % lightsPerCell_] = lightIndex; | |
lightCounts[clusterID].x += 1; | |
++hitCt; | |
++hitCt; | |
} | |
} | |
} | |
cellsUBO_->SetData(lightCounts.data(), sizeof(uint4) * lightCounts.size()); | |
lightsUBO_->SetData(lightRawData.data(), sizeof(LightData) * lightRawData.size()); | |
lightIndexesUBO_->SetData(lightIndices.data(), sizeof(uint32_t) * lightIndices.size()); | |
transform_.SetIdentity(); | |
delete[] froxels; | |
return hitCt; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class SphereTree { | |
bool isLeaf_ = false; // technically redundant but this | |
Sphere sphere_; | |
int dataIndex_ = -1; | |
int flatIndex_ = -1; | |
SphereTree* left_ = nullptr, *right_ = nullptr, *parent_ = nullptr; | |
typedef Vector<Pair<Sphere, int> > IndexedList; | |
typedef Vector< std::tuple<Sphere, int, int> > MappedList; // sphere, data, OG-index | |
// Instead of continuously calculating distances we'll just calculate it once for every combination | |
// and store it in this table | |
struct DistanceTable { | |
int dim; | |
float* data; | |
DistanceTable(int dim) : dim(dim) { | |
data = new float[dim * dim]; | |
} | |
~DistanceTable() { | |
delete[] data; | |
} | |
float Get(int x, int y) { | |
return data[y * dim + x]; | |
} | |
void Set(int x, int y, float v) { | |
// set both combinations because this is a pairing | |
data[y * dim + x] = v; | |
data[x * dim + y] = v; | |
} | |
}; | |
public: | |
~SphereTree() | |
{ | |
if (left_) | |
delete left_; | |
if (right_) | |
delete right_; | |
} | |
// Specified indices for multi-sphere cases, ie. splitting a spotlight into 2 spheres instead of 1 huge sphere | |
static SphereTree* Build(const Vector< Pair<Sphere, int> >& spheres) | |
{ | |
if (spheres.Size() == 0) | |
return 0x0; | |
SphereTree* ret = new SphereTree(); | |
// special case, given only 1 sphere | |
if (spheres.Size() == 1) | |
{ | |
ret->isLeaf_ = true; | |
ret->sphere_ = spheres[0].first_; | |
ret->dataIndex_ = spheres[0].second_; | |
return ret; | |
} | |
MappedList m; | |
m.Reserve(spheres.Size()); | |
int i = 0; | |
for (auto s : spheres) | |
{ | |
m.Push({ | |
s.first_, | |
s.second_, | |
i | |
}); | |
++i; | |
} | |
auto dt = CalculateDistances(m); | |
ret->BuildRecurse(m, *dt); | |
delete dt; | |
return ret; | |
} | |
inline bool IsLeaf() const { return isLeaf_ && dataIndex_ != -1; } | |
inline bool HasValue() const { return dataIndex_ >= 0; } | |
inline bool IsBinary() const { return left_ && right_; } | |
struct CompactionInfo { | |
int dataIndex; | |
int hitIndex; | |
int missIndex; | |
int pad; | |
Vector4 pos_radius; | |
}; | |
// Retrieve data,hit,miss indices w/ pos+radius | |
Vector<CompactionInfo> Compact() | |
{ | |
Vector<CompactionInfo> r; | |
int ct = 0; | |
CalcFlatIndex(ct); | |
BuildCompactRecurse(this, r); | |
return r; | |
} | |
int GetFlatIndex() const { return flatIndex_; } | |
// TESTING FUNCTION: verify our built tree is sane | |
bool Validate() { | |
if (!isLeaf_ && (left_ || right_)) | |
return false; | |
if (left_ && !left_->Validate()) | |
return false; | |
if (right_ && !right_->Validate()) | |
return false; | |
return true; | |
} | |
// Prints GraphViz DOT where: | |
// black connection is the tree hierarchy | |
// green connection is the hit redirection | |
// red connection is the miss redirection | |
String PrintGraphVis() { | |
auto compactInfo = Compact(); | |
String ret = ""; | |
ret += "digraph {\r\n"; | |
PrintRecurse(ret, this); | |
PrintTreeRecurse(ret, this); | |
for (int ii = 0; ii < compactInfo.Size(); ++ii) | |
{ | |
auto n = compactInfo[ii]; | |
if (n.hitIndex != INT_MAX) | |
{ | |
ret += " node_" + String(ii) + | |
" -> " + | |
" node_" + String(n.hitIndex) + " [color = green, constraint = false]\r\n"; | |
} | |
if (n.missIndex != -1) | |
{ | |
ret += " node_" + String(ii) + | |
" -> " + | |
" node_" + String(n.missIndex) + "[color = red, constraint = false]\r\n"; | |
} | |
} | |
ret += "}\r\n"; | |
return ret; | |
} | |
private: | |
#pragma optimize("", off) | |
void BuildCompactRecurse(SphereTree* parent, Vector<CompactionInfo>& hitMissList) | |
{ | |
// special case for root | |
if (parent == this || parent == nullptr) | |
{ | |
hitMissList.Push({ | |
dataIndex_, | |
IsLeaf() ? flatIndex_ : left_->flatIndex_, // hit | |
flatIndex_, // miss | |
0, //pad | |
Vector4(sphere_.center_, sphere_.radius_) | |
}); | |
if (IsBinary()) | |
{ | |
left_->BuildCompactRecurse(this, hitMissList); | |
right_->BuildCompactRecurse(this, hitMissList); | |
} | |
} | |
else | |
{ | |
auto missTarget = FindMiss(); | |
hitMissList.Push({ | |
dataIndex_, // data-id, index of original data-source in list we partitioned | |
IsLeaf() ? (missTarget ? missTarget->flatIndex_ : -1) : left_->flatIndex_, // hit | |
missTarget ? missTarget->flatIndex_ : -1, // miss | |
0, // pad | |
Vector4(sphere_.center_, sphere_.radius_) | |
}); | |
if (IsBinary()) | |
{ | |
left_->BuildCompactRecurse(this, hitMissList); | |
right_->BuildCompactRecurse(this, hitMissList); | |
} | |
} | |
} | |
SphereTree* FindMiss() | |
{ | |
if (parent_ == nullptr) | |
return nullptr; | |
SphereTree* start = this; | |
// if we're left we'll never enter this, thus taking the node to our right | |
// if we're right we'll walk all the way up until we're not the right of our parent | |
// that is our target to skip to, and could be WAYYYY on the other side of the tree | |
while (start && start->parent_ && start->parent_->right_ == start) | |
start = start->parent_; | |
if (start && start->parent_) // could've become the root | |
return start->parent_->right_; | |
return nullptr; | |
} | |
#pragma optimize("", on) | |
void CalcFlatIndex(int& current) | |
{ | |
flatIndex_ = current; | |
++current; | |
if (left_) | |
left_->CalcFlatIndex(current); | |
if (right_) | |
right_->CalcFlatIndex(current); | |
} | |
static DistanceTable* CalculateDistances(const MappedList& l) | |
{ | |
DistanceTable* d = new DistanceTable(l.Size()); | |
for (int i = 0; i < l.Size(); ++i) | |
{ | |
for (int j = 0; j < l.Size(); ++j) | |
{ | |
if (j == i) | |
continue; | |
// not a/b so find out who we're closer to | |
// max distance because, again, radius is serious problem, large radius does bad things | |
// max distance typically results in shorter/broader tree, min distance means taller/narrow tree | |
const float dist = MaxDistance(std::get<0>(l[i]), std::get<0>(l[j])); | |
d->Set(i, j, dist); | |
} | |
} | |
return d; | |
} | |
void BuildRecurse(const MappedList& spheres, DistanceTable& distances) | |
{ | |
if (spheres.Size() == 1) | |
{ | |
sphere_ = std::get<0>(spheres[0]); | |
dataIndex_ = std::get<1>(spheres[0]); | |
isLeaf_ = true; | |
return; | |
} | |
else if (spheres.Size() == 2) // early out for 2 case | |
{ | |
// set us up | |
sphere_.Clear(); | |
sphere_.Merge(std::get<0>(spheres[0])); | |
sphere_.Merge(std::get<0>(spheres[1])); | |
isLeaf_ = false; | |
// setup the leaves | |
left_ = new SphereTree(); | |
left_->parent_ = this; | |
left_->isLeaf_ = true; | |
left_->sphere_ = std::get<0>(spheres[0]); | |
left_->dataIndex_ = std::get<1>(spheres[0]); | |
right_ = new SphereTree(); | |
right_->parent_ = this; | |
right_->isLeaf_ = true; | |
right_->sphere_ = std::get<0>(spheres[1]); | |
right_->dataIndex_ = std::get<1>(spheres[1]); | |
return; | |
} | |
// find farthest apart spheres by their maximum possible distances (opposing sides) | |
// not using centroid or shortest distance because of radius | |
Pair<int, int> farthestIdx; | |
float farthestDistance = FLT_MIN; | |
for (int i = 0; i < spheres.Size(); ++i) | |
{ | |
const auto iIdx = std::get<2>(spheres[i]); | |
for (int j = 0; j < spheres.Size(); ++j) | |
{ | |
if (j == i) | |
continue; | |
const auto jIdx = std::get<2>(spheres[j]); | |
float d = distances.Get(iIdx, jIdx); | |
if (d > farthestDistance) | |
{ | |
farthestDistance = d; | |
farthestIdx = { i, j }; | |
} | |
} | |
} | |
Sphere a = std::get<0>(spheres[farthestIdx.first_]); | |
Sphere b = std::get<0>(spheres[farthestIdx.second_]); | |
MappedList aList; | |
MappedList bList; | |
const auto aIndex = std::get<2>(spheres[farthestIdx.first_]); | |
const auto bIndex = std::get<2>(spheres[farthestIdx.second_]); | |
// partition by maximum possible distance, opposing sides | |
for (size_t i = 0; i < spheres.Size(); ++i) | |
{ | |
// identity check, a/b go in their respective lists | |
if (i == farthestIdx.first_) | |
{ | |
aList.Push(spheres[i]); | |
continue; | |
} | |
else if (i == farthestIdx.second_) | |
{ | |
bList.Push(spheres[i]); | |
continue; | |
} | |
// get precalculated distances to check | |
const auto thisIndex = std::get<2>(spheres[i]); | |
const float aDist = distances.Get(thisIndex, aIndex); | |
const float bDist = distances.Get(thisIndex, bIndex); | |
if (aDist < bDist) | |
aList.Push(spheres[i]); | |
else | |
bList.Push(spheres[i]); | |
} | |
isLeaf_ = false; | |
sphere_.Clear(); | |
sphere_.Merge(a); | |
sphere_.Merge(b); | |
dataIndex_ = -1; | |
if (aList.Size()) // should always be true | |
{ | |
left_ = new SphereTree(); | |
left_->parent_ = this; | |
left_->BuildRecurse(aList, distances); | |
} | |
if (bList.Size()) // should always be true | |
{ | |
right_ = new SphereTree(); | |
right_->parent_ = this; | |
right_->BuildRecurse(bList, distances); | |
} | |
} | |
// max distance between the 2 spheres, centroid distance plus the radii | |
static inline float MaxDistance(Sphere a, Sphere b) | |
{ | |
float d = b.center_.DistanceToPoint(a.center_); | |
return d + a.radius_ + b.radius_; | |
} | |
// shortest distance between the 2 spheres, centroid distance minus the radii | |
static inline float MinDistance(Sphere a, Sphere b) | |
{ | |
float d = b.center_.DistanceToPoint(a.center_); | |
return d - a.radius_ - b.radius_; | |
} | |
void PrintRecurse(String& target, const SphereTree* tree) { | |
target += " node_" + String(tree->GetFlatIndex()); | |
if (tree->IsLeaf()) | |
target += " [color = blue]\r\n"; | |
else | |
target += "\r\n"; | |
if (tree->left_) | |
PrintRecurse(target, tree->left_); | |
if (tree->left_) | |
PrintRecurse(target, tree->right_); | |
}; | |
void PrintTreeRecurse(String& target, SphereTree* tree) | |
{ | |
if (tree->left_) | |
target += " node_" + String(tree->GetFlatIndex()) + " -> " + "node_" + String(tree->left_->GetFlatIndex()) + " [color = black]\r\n"; | |
if (tree->right_) | |
target += " node_" + String(tree->GetFlatIndex()) + " -> " + "node_" + String(tree->right_->GetFlatIndex()) + " [color = black]\r\n"; | |
if (tree->left_) | |
PrintTreeRecurse(target, tree->left_); | |
if (tree->right_) | |
PrintTreeRecurse(target, tree->right_); | |
} | |
}; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment