Index: ps/trunk/source/renderer/ShadowMap.cpp
===================================================================
--- ps/trunk/source/renderer/ShadowMap.cpp (revision 11440)
+++ ps/trunk/source/renderer/ShadowMap.cpp (revision 11441)
@@ -1,681 +1,689 @@
/* Copyright (C) 2012 Wildfire Games.
* This file is part of 0 A.D.
*
* 0 A.D. is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 2 of the License, or
* (at your option) any later version.
*
* 0 A.D. is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with 0 A.D. If not, see .
*/
/*
* Shadow mapping related texture and matrix management
*/
#include "precompiled.h"
#include "gui/GUIutil.h"
#include "lib/bits.h"
#include "lib/ogl.h"
#include "ps/CLogger.h"
#include "ps/Profile.h"
#include "graphics/LightEnv.h"
#include "graphics/ShaderManager.h"
#include "maths/BoundingBoxAligned.h"
#include "maths/MathUtil.h"
#include "maths/Matrix3D.h"
#include "renderer/Renderer.h"
#include "renderer/ShadowMap.h"
///////////////////////////////////////////////////////////////////////////////////////////////////
// ShadowMap implementation
/**
* Struct ShadowMapInternals: Internal data for the ShadowMap implementation
*/
struct ShadowMapInternals
{
// bit depth for the depth texture
int DepthTextureBits;
// the EXT_framebuffer_object framebuffer
GLuint Framebuffer;
// handle of shadow map
GLuint Texture;
// width, height of shadow map
int Width, Height;
// used width, height of shadow map
int EffectiveWidth, EffectiveHeight;
// transform light space into projected light space
// in projected light space, the shadowbound box occupies the [-1..1] cube
// calculated on BeginRender, after the final shadow bounds are known
CMatrix3D LightProjection;
// Transform world space into light space; calculated on SetupFrame
CMatrix3D LightTransform;
// Transform world space into texture space of the shadow map;
// calculated on BeginRender, after the final shadow bounds are known
CMatrix3D TextureMatrix;
// transform light space into world space
CMatrix3D InvLightTransform;
// bounding box of shadowed objects in light space
CBoundingBoxAligned ShadowBound;
// Camera transformed into light space
CCamera LightspaceCamera;
// Some drivers (at least some Intel Mesa ones) appear to handle alpha testing
// incorrectly when the FBO has only a depth attachment.
// When m_ShadowAlphaFix is true, we use DummyTexture to store a useless
// alpha texture which is attached to the FBO as a workaround.
GLuint DummyTexture;
// Copy of renderer's standard view camera, saved between
// BeginRender and EndRender while we replace it with the shadow camera
CCamera SavedViewCamera;
float FilterOffsets[8];
// Helper functions
void CalcShadowMatrices();
void CreateTexture();
};
///////////////////////////////////////////////////////////////////////////////////////////////////
// Construction/Destruction
ShadowMap::ShadowMap()
{
m = new ShadowMapInternals;
m->Framebuffer = 0;
m->Texture = 0;
m->DummyTexture = 0;
m->Width = 0;
m->Height = 0;
m->EffectiveWidth = 0;
m->EffectiveHeight = 0;
m->DepthTextureBits = 0;
// DepthTextureBits: 24/32 are very much faster than 16, on GeForce 4 and FX;
// but they're very much slower on Radeon 9800.
// In both cases, the default (no specified depth) is fast, so we just use
// that by default and hope it's alright. (Otherwise, we'd probably need to
// do some kind of hardware detection to work out what to use.)
// Avoid using uninitialised values in AddShadowedBound if SetupFrame wasn't called first
m->LightTransform.SetIdentity();
}
ShadowMap::~ShadowMap()
{
if (m->Texture)
glDeleteTextures(1, &m->Texture);
if (m->DummyTexture)
glDeleteTextures(1, &m->DummyTexture);
if (m->Framebuffer)
pglDeleteFramebuffersEXT(1, &m->Framebuffer);
delete m;
}
///////////////////////////////////////////////////////////////////////////////////////////////////
// Force the texture/buffer/etc to be recreated, particularly when the renderer's
// size has changed
void ShadowMap::RecreateTexture()
{
if (m->Texture)
glDeleteTextures(1, &m->Texture);
if (m->DummyTexture)
glDeleteTextures(1, &m->DummyTexture);
if (m->Framebuffer)
pglDeleteFramebuffersEXT(1, &m->Framebuffer);
m->Texture = 0;
m->DummyTexture = 0;
m->Framebuffer = 0;
// (Texture will be constructed in next SetupFrame)
}
//////////////////////////////////////////////////////////////////////////////
// SetupFrame: camera and light direction for this frame
void ShadowMap::SetupFrame(const CCamera& camera, const CVector3D& lightdir)
{
if (!m->Texture)
m->CreateTexture();
CVector3D z = lightdir;
CVector3D y;
CVector3D x = camera.m_Orientation.GetIn();
CVector3D eyepos = camera.m_Orientation.GetTranslation();
z.Normalize();
x -= z * z.Dot(x);
if (x.Length() < 0.001)
{
// this is invoked if the camera and light directions almost coincide
// assumption: light direction has a significant Z component
x = CVector3D(1.0, 0.0, 0.0);
x -= z * z.Dot(x);
}
x.Normalize();
y = z.Cross(x);
// X axis perpendicular to light direction, flowing along with view direction
m->LightTransform._11 = x.X;
m->LightTransform._12 = x.Y;
m->LightTransform._13 = x.Z;
// Y axis perpendicular to light and view direction
m->LightTransform._21 = y.X;
m->LightTransform._22 = y.Y;
m->LightTransform._23 = y.Z;
// Z axis is in direction of light
m->LightTransform._31 = z.X;
m->LightTransform._32 = z.Y;
m->LightTransform._33 = z.Z;
// eye is at the origin of the coordinate system
m->LightTransform._14 = -x.Dot(eyepos);
m->LightTransform._24 = -y.Dot(eyepos);
m->LightTransform._34 = -z.Dot(eyepos);
m->LightTransform._41 = 0.0;
m->LightTransform._42 = 0.0;
m->LightTransform._43 = 0.0;
m->LightTransform._44 = 1.0;
m->LightTransform.GetInverse(m->InvLightTransform);
m->ShadowBound.SetEmpty();
//
m->LightspaceCamera = camera;
m->LightspaceCamera.m_Orientation = m->LightTransform * camera.m_Orientation;
m->LightspaceCamera.UpdateFrustum();
}
//////////////////////////////////////////////////////////////////////////////
// AddShadowedBound: add a world-space bounding box to the bounds of shadowed
// objects
void ShadowMap::AddShadowedBound(const CBoundingBoxAligned& bounds)
{
CBoundingBoxAligned lightspacebounds;
bounds.Transform(m->LightTransform, lightspacebounds);
m->ShadowBound += lightspacebounds;
}
///////////////////////////////////////////////////////////////////////////////////////////////////
// CalcShadowMatrices: calculate required matrices for shadow map generation - the light's
// projection and transformation matrices
void ShadowMapInternals::CalcShadowMatrices()
{
CRenderer& renderer = g_Renderer;
-
float minZ = ShadowBound[0].Z;
ShadowBound.IntersectFrustumConservative(LightspaceCamera.GetFrustum());
+ // ShadowBound might have been empty to begin with, producing an empty result
+ if (ShadowBound.IsEmpty())
+ {
+ // no-op
+ LightProjection.SetIdentity();
+ TextureMatrix = LightTransform;
+ return;
+ }
+
// round off the shadow boundaries to sane increments to help reduce swim effect
float boundInc = 16.0f;
ShadowBound[0].X = floor(ShadowBound[0].X / boundInc) * boundInc;
ShadowBound[0].Y = floor(ShadowBound[0].Y / boundInc) * boundInc;
ShadowBound[1].X = ceil(ShadowBound[1].X / boundInc) * boundInc;
ShadowBound[1].Y = ceil(ShadowBound[1].Y / boundInc) * boundInc;
// minimum Z bound must not be clipped too much, because objects that lie outside
// the shadow bounds cannot cast shadows either
// the 2.0 is rather arbitrary: it should be big enough so that we won't accidentally miss
// a shadow generator, and small enough not to affect Z precision
ShadowBound[0].Z = minZ - 2.0;
// Setup orthogonal projection (lightspace -> clip space) for shadowmap rendering
CVector3D scale = ShadowBound[1] - ShadowBound[0];
CVector3D shift = (ShadowBound[1] + ShadowBound[0]) * -0.5;
if (scale.X < 1.0)
scale.X = 1.0;
if (scale.Y < 1.0)
scale.Y = 1.0;
if (scale.Z < 1.0)
scale.Z = 1.0;
scale.X = 2.0 / scale.X;
scale.Y = 2.0 / scale.Y;
scale.Z = 2.0 / scale.Z;
// make sure a given world position falls on a consistent shadowmap texel fractional offset
float offsetX = fmod(ShadowBound[0].X - LightTransform._14, 2.0f/(scale.X*EffectiveWidth));
float offsetY = fmod(ShadowBound[0].Y - LightTransform._24, 2.0f/(scale.Y*EffectiveHeight));
LightProjection.SetZero();
LightProjection._11 = scale.X;
LightProjection._14 = (shift.X + offsetX) * scale.X;
LightProjection._22 = scale.Y;
LightProjection._24 = (shift.Y + offsetY) * scale.Y;
LightProjection._33 = scale.Z;
LightProjection._34 = shift.Z * scale.Z + renderer.m_ShadowZBias;
LightProjection._44 = 1.0;
-
// Calculate texture matrix by creating the clip space to texture coordinate matrix
// and then concatenating all matrices that have been calculated so far
- CMatrix3D lightToTex;
+
float texscalex = scale.X * 0.5f * (float)EffectiveWidth / (float)Width;
float texscaley = scale.Y * 0.5f * (float)EffectiveHeight / (float)Height;
float texscalez = scale.Z * 0.5f;
+ CMatrix3D lightToTex;
lightToTex.SetZero();
lightToTex._11 = texscalex;
lightToTex._14 = (offsetX - ShadowBound[0].X) * texscalex;
lightToTex._22 = texscaley;
lightToTex._24 = (offsetY - ShadowBound[0].Y) * texscaley;
lightToTex._33 = texscalez;
lightToTex._34 = -ShadowBound[0].Z * texscalez;
lightToTex._44 = 1.0;
TextureMatrix = lightToTex * LightTransform;
}
//////////////////////////////////////////////////////////////////////////
// Create the shadow map
void ShadowMapInternals::CreateTexture()
{
// Cleanup
if (Texture)
{
glDeleteTextures(1, &Texture);
Texture = 0;
}
if (DummyTexture)
{
glDeleteTextures(1, &DummyTexture);
DummyTexture = 0;
}
if (Framebuffer)
{
pglDeleteFramebuffersEXT(1, &Framebuffer);
Framebuffer = 0;
}
pglGenFramebuffersEXT(1, &Framebuffer);
if (g_Renderer.m_ShadowMapSize != 0)
{
// non-default option to override the size
Width = Height = g_Renderer.m_ShadowMapSize;
}
else
{
// get shadow map size as next power of two up from view width/height
Width = Height = (int)round_up_to_pow2((unsigned)std::max(g_Renderer.GetWidth(), g_Renderer.GetHeight()));
}
// Clamp to the maximum texture size
Width = std::min(Width, (int)ogl_max_tex_size);
Height = std::min(Height, (int)ogl_max_tex_size);
// Since we're using a framebuffer object, the whole texture is available
EffectiveWidth = Width;
EffectiveHeight = Height;
const char* formatname;
switch(DepthTextureBits)
{
case 16: formatname = "DEPTH_COMPONENT16"; break;
case 24: formatname = "DEPTH_COMPONENT24"; break;
case 32: formatname = "DEPTH_COMPONENT32"; break;
default: formatname = "DEPTH_COMPONENT"; break;
}
LOGMESSAGE(L"Creating shadow texture (size %dx%d) (format = %hs)",
Width, Height, formatname);
if (g_Renderer.m_Options.m_ShadowAlphaFix)
{
glGenTextures(1, &DummyTexture);
g_Renderer.BindTexture(0, DummyTexture);
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_S, GL_CLAMP_TO_EDGE);
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_T, GL_CLAMP_TO_EDGE);
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_NEAREST);
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_NEAREST);
glTexImage2D(GL_TEXTURE_2D, 0, GL_RGBA, Width, Height, 0, GL_RGBA, GL_UNSIGNED_BYTE, NULL);
}
glGenTextures(1, &Texture);
g_Renderer.BindTexture(0, Texture);
GLenum format;
#if CONFIG2_GLES
format = GL_DEPTH_COMPONENT;
#else
switch (DepthTextureBits)
{
case 16: format = GL_DEPTH_COMPONENT16; break;
case 24: format = GL_DEPTH_COMPONENT24; break;
case 32: format = GL_DEPTH_COMPONENT32; break;
default: format = GL_DEPTH_COMPONENT; break;
}
#endif
glTexImage2D(GL_TEXTURE_2D, 0, format, Width, Height, 0, GL_DEPTH_COMPONENT, GL_UNSIGNED_SHORT, NULL);
// GLES requires type == UNSIGNED_SHORT or UNSIGNED_INT
// set texture parameters
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_S, GL_CLAMP_TO_EDGE);
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_T, GL_CLAMP_TO_EDGE);
#if CONFIG2_GLES
// GLES doesn't do depth comparisons, so treat it as a
// basic unfiltered depth texture
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_NEAREST);
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_NEAREST);
#else
// Enable automatic depth comparisons
glTexParameteri(GL_TEXTURE_2D, GL_DEPTH_TEXTURE_MODE, GL_INTENSITY);
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_COMPARE_MODE, GL_COMPARE_R_TO_TEXTURE);
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_COMPARE_FUNC, GL_LEQUAL);
// Use GL_LINEAR to trigger automatic PCF on some devices
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_LINEAR);
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_LINEAR);
#endif
ogl_WarnIfError();
// bind to framebuffer object
glBindTexture(GL_TEXTURE_2D, 0);
pglBindFramebufferEXT(GL_FRAMEBUFFER_EXT, Framebuffer);
pglFramebufferTexture2DEXT(GL_FRAMEBUFFER_EXT, GL_DEPTH_ATTACHMENT_EXT, GL_TEXTURE_2D, Texture, 0);
if (g_Renderer.m_Options.m_ShadowAlphaFix)
{
pglFramebufferTexture2DEXT(GL_FRAMEBUFFER_EXT, GL_COLOR_ATTACHMENT0_EXT, GL_TEXTURE_2D, DummyTexture, 0);
}
else
{
#if CONFIG2_GLES
#warning TODO: figure out whether the glDrawBuffer/glReadBuffer stuff is needed, since it is not supported by GLES
#else
glDrawBuffer(GL_NONE);
#endif
}
#if !CONFIG2_GLES
glReadBuffer(GL_NONE);
#endif
ogl_WarnIfError();
GLenum status = pglCheckFramebufferStatusEXT(GL_FRAMEBUFFER_EXT);
pglBindFramebufferEXT(GL_FRAMEBUFFER_EXT, 0);
if (status != GL_FRAMEBUFFER_COMPLETE_EXT)
{
LOGWARNING(L"Framebuffer object incomplete: 0x%04X", status);
// Disable shadow rendering (but let the user try again if they want)
g_Renderer.m_Options.m_Shadows = false;
}
FilterOffsets[0] = -0.4f/Width;
FilterOffsets[1] = 1.0f/Height;
FilterOffsets[2] = -1.0f/Width;
FilterOffsets[3] = -0.4f/Height;
FilterOffsets[4] = 0.4f/Width;
FilterOffsets[5] = -1.0f/Height;
FilterOffsets[6] = 1.0f/Width;
FilterOffsets[7] = 0.4f/Height;
}
///////////////////////////////////////////////////////////////////////////////////////////////////
// Set up to render into shadow map texture
void ShadowMap::BeginRender()
{
// HACK HACK: this depends in non-obvious ways on the behaviour of the caller
// Calc remaining shadow matrices
m->CalcShadowMatrices();
{
PROFILE("bind framebuffer");
glBindTexture(GL_TEXTURE_2D, 0);
pglBindFramebufferEXT(GL_FRAMEBUFFER_EXT, m->Framebuffer);
}
// clear buffers
{
PROFILE("clear depth texture");
// In case we used m_ShadowAlphaFix, we ought to clear the unused
// color buffer too, else Mali 400 drivers get confused.
// Might as well clear stencil too for completeness.
glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT | GL_STENCIL_BUFFER_BIT);
glColorMask(0,0,0,0);
}
// setup viewport
glViewport(0, 0, m->EffectiveWidth, m->EffectiveHeight);
m->SavedViewCamera = g_Renderer.GetViewCamera();
CCamera c = m->SavedViewCamera;
c.SetProjection(m->LightProjection);
c.GetOrientation() = m->InvLightTransform;
g_Renderer.SetViewCamera(c);
#if !CONFIG2_GLES
glMatrixMode(GL_PROJECTION);
glLoadMatrixf(&m->LightProjection._11);
glMatrixMode(GL_MODELVIEW);
glLoadMatrixf(&m->LightTransform._11);
#endif
glEnable(GL_SCISSOR_TEST);
glScissor(1,1, m->EffectiveWidth-2, m->EffectiveHeight-2);
}
///////////////////////////////////////////////////////////////////////////////////////////////////
// Finish rendering into shadow map texture
void ShadowMap::EndRender()
{
glDisable(GL_SCISSOR_TEST);
g_Renderer.SetViewCamera(m->SavedViewCamera);
{
PROFILE("unbind framebuffer");
pglBindFramebufferEXT(GL_FRAMEBUFFER_EXT, 0);
}
glViewport(0, 0, g_Renderer.GetWidth(), g_Renderer.GetHeight());
glColorMask(1,1,1,1);
}
///////////////////////////////////////////////////////////////////////////////////////////////////
// Retrieve the texture handle and texture matrix for shadowing
GLuint ShadowMap::GetTexture() const
{
return m->Texture;
}
const CMatrix3D& ShadowMap::GetTextureMatrix() const
{
return m->TextureMatrix;
}
///////////////////////////////////////////////////////////////////////////////////////////////////
// Depth texture bits
int ShadowMap::GetDepthTextureBits() const
{
return m->DepthTextureBits;
}
void ShadowMap::SetDepthTextureBits(int bits)
{
if (bits != m->DepthTextureBits)
{
if (m->Texture)
{
glDeleteTextures(1, &m->Texture);
m->Texture = 0;
}
m->Width = m->Height = 0;
m->DepthTextureBits = bits;
}
}
const float* ShadowMap::GetFilterOffsets() const
{
return m->FilterOffsets;
}
//////////////////////////////////////////////////////////////////////////////
void ShadowMap::RenderDebugBounds()
{
CShaderTechniquePtr shaderTech = g_Renderer.GetShaderManager().LoadEffect("gui_solid");
shaderTech->BeginPass();
CShaderProgramPtr shader = shaderTech->GetShader();
glDepthMask(0);
glDisable(GL_CULL_FACE);
// Render shadow bound
shader->Uniform("transform", g_Renderer.GetViewCamera().GetViewProjection() * m->InvLightTransform);
glEnable(GL_BLEND);
glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
shader->Uniform("color", 0.0f, 0.0f, 1.0f, 0.25f);
m->ShadowBound.Render(shader);
glDisable(GL_BLEND);
shader->Uniform("color", 0.0f, 0.0f, 1.0f, 1.0f);
m->ShadowBound.RenderOutline(shader);
// Draw a funny line/triangle direction indicator thing for unknown reasons
float shadowLineVerts[] = {
0.0, 0.0, 0.0,
0.0, 0.0, 50.0,
0.0, 0.0, 50.0,
50.0, 0.0, 50.0,
50.0, 0.0, 50.0,
0.0, 50.0, 50.0,
0.0, 50.0, 50.0,
0.0, 0.0, 50.0
};
shader->VertexPointer(3, GL_FLOAT, 0, shadowLineVerts);
shader->AssertPointersBound();
glDrawArrays(GL_LINES, 0, 8);
shaderTech->EndPass();
#if 0
CMatrix3D InvTexTransform;
m->TextureMatrix.GetInverse(InvTexTransform);
// Render representative texture rectangle
glPushMatrix();
glMultMatrixf(&InvTexTransform._11);
glEnable(GL_BLEND);
glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
glColor4ub(255,0,0,64);
glBegin(GL_QUADS);
glVertex3f(0.0, 0.0, 0.0);
glVertex3f(1.0, 0.0, 0.0);
glVertex3f(1.0, 1.0, 0.0);
glVertex3f(0.0, 1.0, 0.0);
glEnd();
glDisable(GL_BLEND);
glPolygonMode(GL_FRONT_AND_BACK, GL_LINE);
glColor3ub(255,0,0);
glBegin(GL_QUADS);
glVertex3f(0.0, 0.0, 0.0);
glVertex3f(1.0, 0.0, 0.0);
glVertex3f(1.0, 1.0, 0.0);
glVertex3f(0.0, 1.0, 0.0);
glEnd();
glPolygonMode(GL_FRONT_AND_BACK, GL_FILL);
glPopMatrix();
#endif
glEnable(GL_CULL_FACE);
glDepthMask(1);
}
void ShadowMap::RenderDebugTexture()
{
glDepthMask(0);
glDisable(GL_DEPTH_TEST);
#if !CONFIG2_GLES
g_Renderer.BindTexture(0, m->Texture);
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_COMPARE_MODE, GL_NONE);
#endif
CShaderTechniquePtr texTech = g_Renderer.GetShaderManager().LoadEffect("gui_basic");
texTech->BeginPass();
CShaderProgramPtr texShader = texTech->GetShader();
texShader->Uniform("transform", GetDefaultGuiMatrix());
texShader->BindTexture("tex", m->Texture);
float s = 256.f;
float boxVerts[] = {
0,0, 0,s, s,0,
s,0, 0,s, s,s
};
float boxUV[] = {
0,0, 0,1, 1,0,
1,0, 0,1, 1,1
};
texShader->VertexPointer(2, GL_FLOAT, 0, boxVerts);
texShader->TexCoordPointer(GL_TEXTURE0, 2, GL_FLOAT, 0, boxUV);
texShader->AssertPointersBound();
glDrawArrays(GL_TRIANGLES, 0, 6);
texTech->EndPass();
#if !CONFIG2_GLES
g_Renderer.BindTexture(0, m->Texture);
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_COMPARE_MODE, GL_COMPARE_R_TO_TEXTURE);
#endif
glEnable(GL_DEPTH_TEST);
glDepthMask(1);
}
Index: ps/trunk/source/maths/BoundingBoxAligned.h
===================================================================
--- ps/trunk/source/maths/BoundingBoxAligned.h (revision 11440)
+++ ps/trunk/source/maths/BoundingBoxAligned.h (revision 11441)
@@ -1,155 +1,156 @@
/* Copyright (C) 2011 Wildfire Games.
* This file is part of 0 A.D.
*
* 0 A.D. is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 2 of the License, or
* (at your option) any later version.
*
* 0 A.D. is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with 0 A.D. If not, see .
*/
/*
* Axis-aligned bounding box
*/
#ifndef INCLUDED_BOUND
#define INCLUDED_BOUND
// necessary includes
#include "Vector3D.h"
#include "graphics/ShaderProgram.h"
class CFrustum;
class CMatrix3D;
class CBoundingBoxOriented;
///////////////////////////////////////////////////////////////////////////////
// basic axis aligned bounding box (AABB) class
class CBoundingBoxAligned
{
public:
CBoundingBoxAligned() { SetEmpty(); }
CBoundingBoxAligned(const CVector3D& min, const CVector3D& max) {
m_Data[0] = min;
m_Data[1] = max;
}
/**
* Transforms these bounds according to the specified transformation matrix @p m, and writes the axis-aligned bounds
* of that result to @p result.
*/
void Transform(const CMatrix3D& m, CBoundingBoxAligned& result) const;
/**
* Transform these bounds using the matrix @p transform, and write out the result as an oriented (i.e. non-axis-aligned) box.
* The difference with @ref Transform(const CMatrix3D&, CBoundingBoxAligned&) is that that method is equivalent to first
* computing this result, and then from that taking the axis-aligned bounding boxes again.
*/
void Transform(const CMatrix3D& m, CBoundingBoxOriented& result) const;
CVector3D& operator[](int index) { return m_Data[index]; }
const CVector3D& operator[](int index) const { return m_Data[index]; }
void SetEmpty();
bool IsEmpty() const;
void Extend(const CVector3D& min, const CVector3D& max)
{
if (min.X < m_Data[0].X) m_Data[0].X = min.X;
if (min.Y < m_Data[0].Y) m_Data[0].Y = min.Y;
if (min.Z < m_Data[0].Z) m_Data[0].Z = min.Z;
if (max.X > m_Data[1].X) m_Data[1].X = max.X;
if (max.Y > m_Data[1].Y) m_Data[1].Y = max.Y;
if (max.Z > m_Data[1].Z) m_Data[1].Z = max.Z;
}
// operator+=: extend this bound to include given bound
CBoundingBoxAligned& operator+=(const CBoundingBoxAligned& b)
{
Extend(b.m_Data[0], b.m_Data[1]);
return *this;
}
// operator+=: extend this bound to include given point
CBoundingBoxAligned& operator+=(const CVector3D& pt)
{
Extend(pt, pt);
return *this;
}
/**
* Check if a given ray intersects this AABB.
* See also Real-Time Rendering, Third Edition by T. Akenine-Moller, p. 741--742.
*
* @param[in] origin Origin of the ray.
* @param[in] dir Direction vector of the ray, defining the positive direction of the ray. Must be of unit length.
* @param[out] tmin,tmax distance in the positive direction from the origin of the ray to the entry and exit points in
* the bounding box. If the origin is inside the box, then this is counted as an intersection and one of @p tMin and @p tMax may be negative.
*
* @return true if the ray originating in @p origin and with unit direction vector @p dir intersects this AABB, false otherwise.
*/
bool RayIntersect(const CVector3D& origin, const CVector3D& dir, float& tmin, float& tmax) const;
// return the volume of this bounding box
float GetVolume() const
{
CVector3D v = m_Data[1] - m_Data[0];
return (std::max(v.X, 0.0f) * std::max(v.Y, 0.0f) * std::max(v.Z, 0.0f));
}
// return the centre of this bounding box
void GetCentre(CVector3D& centre) const
{
centre = (m_Data[0] + m_Data[1]) * 0.5f;
}
/**
* Expand the bounding box by the given amount in every direction.
*/
void Expand(float amount);
/**
* IntersectFrustumConservative: Approximate the intersection of this bounds object
* with the given frustum. The bounds object is overwritten with the results.
*
* The approximation is conservative in the sense that the result will always contain
* the actual intersection, but it may be larger than the intersection itself.
* The result will always be fully contained within the original bounds.
*
* @note While not in the spirit of this function's purpose, a no-op would be a correct
* implementation of this function.
+ * @note If this bound is empty, the result is the empty bound.
*
* @param frustum the frustum to intersect with
*/
void IntersectFrustumConservative(const CFrustum& frustum);
/**
* Render: Render the surfaces of the bound object as triangles.
*/
void Render(CShaderProgramPtr& shader) const;
/**
* Render: Render the outline of the bound object as lines.
*/
void RenderOutline(CShaderProgramPtr& shader) const;
private:
// Holds the minimal and maximal coordinate points in m_Data[0] and m_Data[1], respectively.
CVector3D m_Data[2];
public:
static const CBoundingBoxAligned EMPTY;
};
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#endif
Index: ps/trunk/source/maths/tests/test_Brush.h
===================================================================
--- ps/trunk/source/maths/tests/test_Brush.h (nonexistent)
+++ ps/trunk/source/maths/tests/test_Brush.h (revision 11441)
@@ -0,0 +1,183 @@
+/* Copyright (C) 2012 Wildfire Games.
+ * This file is part of 0 A.D.
+ *
+ * 0 A.D. is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * 0 A.D. is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with 0 A.D. If not, see .
+ */
+
+#include "lib/self_test.h"
+
+#include "maths/Brush.h"
+#include "maths/BoundingBoxAligned.h"
+#include "graphics/Frustum.h"
+
+class TestBrush : public CxxTest::TestSuite
+{
+public:
+ void setUp()
+ {
+ CxxTest::setAbortTestOnFail(true);
+ }
+
+ void tearDown()
+ {
+
+ }
+
+ void test_slice_empty_brush()
+ {
+ // verifies that the result of slicing an empty bound with a plane yields an empty bound
+ CBrush brush;
+ CPlane plane(CVector4D(0, 0, -1, 0.5f)); // can be anything, really
+
+ CBrush result;
+ brush.Slice(plane, result);
+ TS_ASSERT(brush.IsEmpty());
+ }
+
+ void test_slice_plane_simple()
+ {
+ // slice a 1x1x1 cube vertically down the middle at z = 0.5, with the plane normal pointing towards the negative
+ // end of the Z axis (i.e., anything with Z lower than 0.5 is considered 'in front of' the plane and is kept)
+ CPlane plane(CVector4D(0, 0, -1, 0.5f));
+ CBrush brush(CBoundingBoxAligned(CVector3D(0,0,0), CVector3D(1,1,1)));
+
+ CBrush result;
+ brush.Slice(plane, result);
+
+ // verify that the resulting brush consists of exactly our 8 expected, unique vertices
+ TS_ASSERT_EQUALS(8, result.GetVertices().size());
+ size_t LBF = GetUniqueVertexIndex(result, CVector3D(0, 0, 0)); // left-bottom-front <=> XYZ
+ size_t RBF = GetUniqueVertexIndex(result, CVector3D(1, 0, 0)); // right-bottom-front
+ size_t RBB = GetUniqueVertexIndex(result, CVector3D(1, 0, 0.5f)); // right-bottom-back
+ size_t LBB = GetUniqueVertexIndex(result, CVector3D(0, 0, 0.5f)); // etc.
+ size_t LTF = GetUniqueVertexIndex(result, CVector3D(0, 1, 0));
+ size_t RTF = GetUniqueVertexIndex(result, CVector3D(1, 1, 0));
+ size_t RTB = GetUniqueVertexIndex(result, CVector3D(1, 1, 0.5f));
+ size_t LTB = GetUniqueVertexIndex(result, CVector3D(0, 1, 0.5f));
+
+ // verify that the brush contains the six expected planes (one of which is the slicing plane)
+ VerifyFacePresent(result, 5, LBF, RBF, RBB, LBB, LBF); // bottom face
+ VerifyFacePresent(result, 5, LTF, RTF, RTB, LTB, LTF); // top face
+ VerifyFacePresent(result, 5, LBF, LBB, LTB, LTF, LBF); // left face
+ VerifyFacePresent(result, 5, RBF, RBB, RTB, RTF, RBF); // right face
+ VerifyFacePresent(result, 5, LBF, RBF, RTF, LTF, LBF); // front face
+ VerifyFacePresent(result, 5, LBB, RBB, RTB, LTB, LBB); // back face
+ }
+
+ void test_slice_plane_behind_brush()
+ {
+ // slice the (0,0,0) to (1,1,1) cube by the plane z = 1.5, with the plane normal pointing towards the negative
+ // end of the Z axis (i.e. the entire cube is 'in front of' the plane and should be kept)
+ CPlane plane(CVector4D(0, 0, -1, 1.5f));
+ CBrush brush(CBoundingBoxAligned(CVector3D(0,0,0), CVector3D(1,1,1)));
+
+ CBrush result;
+ brush.Slice(plane, result);
+
+ // verify that the resulting brush consists of exactly our 8 expected, unique vertices
+ TS_ASSERT_EQUALS(8, result.GetVertices().size());
+ size_t LBF = GetUniqueVertexIndex(result, CVector3D(0, 0, 0)); // left-bottom-front <=> XYZ
+ size_t RBF = GetUniqueVertexIndex(result, CVector3D(1, 0, 0)); // right-bottom-front
+ size_t RBB = GetUniqueVertexIndex(result, CVector3D(1, 0, 1)); // right-bottom-back
+ size_t LBB = GetUniqueVertexIndex(result, CVector3D(0, 0, 1)); // etc.
+ size_t LTF = GetUniqueVertexIndex(result, CVector3D(0, 1, 0));
+ size_t RTF = GetUniqueVertexIndex(result, CVector3D(1, 1, 0));
+ size_t RTB = GetUniqueVertexIndex(result, CVector3D(1, 1, 1));
+ size_t LTB = GetUniqueVertexIndex(result, CVector3D(0, 1, 1));
+
+ // verify that the brush contains the six expected planes (one of which is the slicing plane)
+ VerifyFacePresent(result, 5, LBF, RBF, RBB, LBB, LBF); // bottom face
+ VerifyFacePresent(result, 5, LTF, RTF, RTB, LTB, LTF); // top face
+ VerifyFacePresent(result, 5, LBF, LBB, LTB, LTF, LBF); // left face
+ VerifyFacePresent(result, 5, RBF, RBB, RTB, RTF, RBF); // right face
+ VerifyFacePresent(result, 5, LBF, RBF, RTF, LTF, LBF); // front face
+ VerifyFacePresent(result, 5, LBB, RBB, RTB, LTB, LBB); // back face
+ }
+
+ void test_slice_plane_in_front_of_brush()
+ {
+ // slices the (0,0,0) to (1,1,1) cube by the plane z = -0.5, with the plane normal pointing towards the negative
+ // end of the Z axis (i.e. the entire cube is 'behind' the plane and should be cut away)
+ CPlane plane(CVector4D(0, 0, -1, -0.5f));
+ CBrush brush(CBoundingBoxAligned(CVector3D(0,0,0), CVector3D(1,1,1)));
+
+ CBrush result;
+ brush.Slice(plane, result);
+
+ TS_ASSERT_EQUALS(0, result.GetVertices().size());
+
+ std::vector > faces;
+ result.GetFaces(faces);
+
+ TS_ASSERT_EQUALS(0, faces.size());
+ }
+
+private:
+ size_t GetUniqueVertexIndex(const CBrush& brush, const CVector3D& vertex, float eps = 1e-6f)
+ {
+ std::vector vertices = brush.GetVertices();
+
+ for (size_t i = 0; i < vertices.size(); ++i)
+ {
+ const CVector3D& v = vertices[i];
+ if (fabs(v.X - vertex.X) < eps
+ && fabs(v.Y - vertex.Y) < eps
+ && fabs(v.Z - vertex.Z) < eps)
+ return i;
+ }
+
+ TS_FAIL("Vertex not found in brush");
+ return ~0u;
+ }
+
+ void VerifyFacePresent(const CBrush& brush, int count, ...)
+ {
+ std::vector face;
+
+ va_list args;
+ va_start(args, count);
+ for (int x = 0; x < count; ++x)
+ face.push_back(va_arg(args, size_t));
+ va_end(args);
+
+ if (face.size() == 0)
+ return;
+
+ std::vector > faces;
+ brush.GetFaces(faces);
+
+ // the brush is free to use any starting vertex along the face, and to use any winding order, so have 'face'
+ // cycle through various starting values and see if any of them (or their reverse) matches one found in the brush.
+
+ for (size_t c = 0; c < face.size() - 1; ++c)
+ {
+ std::vector >::iterator it1 = std::find(faces.begin(), faces.end(), face);
+ if (it1 != faces.end())
+ return;
+
+ // no match, try the reverse
+ std::vector faceReverse = face;
+ std::reverse(faceReverse.begin(), faceReverse.end());
+ std::vector >::iterator it2 = std::find(faces.begin(), faces.end(), faceReverse);
+ if (it2 != faces.end())
+ return;
+
+ // no match, cycle it
+ face.erase(face.begin());
+ face.push_back(face[0]);
+ }
+
+ TS_FAIL("Face not found in brush");
+ }
+};
Index: ps/trunk/source/maths/tests/test_Bound.h
===================================================================
--- ps/trunk/source/maths/tests/test_Bound.h (revision 11440)
+++ ps/trunk/source/maths/tests/test_Bound.h (revision 11441)
@@ -1,57 +1,71 @@
-/* Copyright (C) 2009 Wildfire Games.
+/* Copyright (C) 2012 Wildfire Games.
* This file is part of 0 A.D.
*
* 0 A.D. is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 2 of the License, or
* (at your option) any later version.
*
* 0 A.D. is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with 0 A.D. If not, see .
*/
#include "lib/self_test.h"
#include "maths/BoundingBoxAligned.h"
+#include "maths/BoundingBoxOriented.h"
class TestBound : public CxxTest::TestSuite
{
public:
- void test_empty()
+ void test_empty_aabb()
{
CBoundingBoxAligned bound;
TS_ASSERT(bound.IsEmpty());
bound += CVector3D(1, 2, 3);
TS_ASSERT(! bound.IsEmpty());
bound.SetEmpty();
TS_ASSERT(bound.IsEmpty());
}
+ void test_empty_obb()
+ {
+ CBoundingBoxOriented bound;
+ TS_ASSERT(bound.IsEmpty());
+ bound.m_Basis[0] = CVector3D(1,0,0);
+ bound.m_Basis[1] = CVector3D(0,1,0);
+ bound.m_Basis[2] = CVector3D(0,0,1);
+ bound.m_HalfSizes = CVector3D(1,2,3);
+ TS_ASSERT(!bound.IsEmpty());
+ bound.SetEmpty();
+ TS_ASSERT(bound.IsEmpty());
+ }
+
void test_extend_vector()
{
CBoundingBoxAligned bound;
CVector3D v (1, 2, 3);
bound += v;
CVector3D centre;
bound.GetCentre(centre);
TS_ASSERT_EQUALS(centre, v);
}
void test_extend_bound()
{
CBoundingBoxAligned bound;
CVector3D v (1, 2, 3);
CBoundingBoxAligned b (v, v);
bound += b;
CVector3D centre;
bound.GetCentre(centre);
TS_ASSERT_EQUALS(centre, v);
}
};
Index: ps/trunk/source/maths/Brush.cpp
===================================================================
--- ps/trunk/source/maths/Brush.cpp (revision 11440)
+++ ps/trunk/source/maths/Brush.cpp (revision 11441)
@@ -1,306 +1,416 @@
-/* Copyright (C) 2009 Wildfire Games.
+/* Copyright (C) 2012 Wildfire Games.
* This file is part of 0 A.D.
*
* 0 A.D. is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 2 of the License, or
* (at your option) any later version.
*
* 0 A.D. is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with 0 A.D. If not, see .
*/
/*
* Implementation of CBrush, a class representing a convex object
*/
#include "precompiled.h"
#include "lib/ogl.h"
#include
#include "Brush.h"
#include "BoundingBoxAligned.h"
#include "graphics/Frustum.h"
///////////////////////////////////////////////////////////////////////////////
// Convert the given bounds into a brush
CBrush::CBrush(const CBoundingBoxAligned& bounds)
{
m_Vertices.resize(8);
for(size_t i = 0; i < 8; ++i)
{
- m_Vertices[i][0] = bounds[(i & 1) ? 1 : 0][0];
- m_Vertices[i][1] = bounds[(i & 2) ? 1 : 0][1];
- m_Vertices[i][2] = bounds[(i & 4) ? 1 : 0][2];
+ m_Vertices[i][0] = bounds[(i & 1) ? 1 : 0][0]; // X
+ m_Vertices[i][1] = bounds[(i & 2) ? 1 : 0][1]; // Y
+ m_Vertices[i][2] = bounds[(i & 4) ? 1 : 0][2]; // Z
}
+ // construct cube face indices, 5 vertex indices per face (start vertex included twice)
+
m_Faces.resize(30);
m_Faces[0] = 0; m_Faces[1] = 1; m_Faces[2] = 3; m_Faces[3] = 2; m_Faces[4] = 0; // Z = min
m_Faces[5] = 4; m_Faces[6] = 5; m_Faces[7] = 7; m_Faces[8] = 6; m_Faces[9] = 4; // Z = max
m_Faces[10] = 0; m_Faces[11] = 2; m_Faces[12] = 6; m_Faces[13] = 4; m_Faces[14] = 0; // X = min
m_Faces[15] = 1; m_Faces[16] = 3; m_Faces[17] = 7; m_Faces[18] = 5; m_Faces[19] = 1; // X = max
m_Faces[20] = 0; m_Faces[21] = 1; m_Faces[22] = 5; m_Faces[23] = 4; m_Faces[24] = 0; // Y = min
m_Faces[25] = 2; m_Faces[26] = 3; m_Faces[27] = 7; m_Faces[28] = 6; m_Faces[29] = 2; // Y = max
}
///////////////////////////////////////////////////////////////////////////////
// Calculate bounds of this brush
void CBrush::Bounds(CBoundingBoxAligned& result) const
{
result.SetEmpty();
for(size_t i = 0; i < m_Vertices.size(); ++i)
result += m_Vertices[i];
}
///////////////////////////////////////////////////////////////////////////////
// Cut the brush according to a given plane
-struct SliceVertexInfo {
- float d; // distance
- size_t res; // index in result brush (or no_vertex if cut away)
-};
-struct NewVertexInfo {
- size_t v1, v2; // adjacent vertices in original brush
- size_t res; // index in result brush
+/// Holds information about what happens to a single vertex in a brush during a slicing operation.
+struct SliceOpVertexInfo
+{
+ float planeDist; ///< Signed distance from this vertex to the slicing plane.
+ size_t resIdx; ///< Index of this vertex in the resulting brush (or NO_VERTEX if cut away)
+};
- size_t neighb1, neighb2; // index into newv
+/// Holds information about a newly introduced vertex on an edge in a brush as the result of a slicing operation.
+struct SliceOpNewVertexInfo
+{
+ /// Indices of adjacent edge vertices in original brush
+ size_t edgeIdx1, edgeIdx2;
+ /// Index of newly introduced vertex in resulting brush
+ size_t resIdx;
+
+ /**
+ * Index into SliceOpInfo.nvInfo; hold the indices of this new vertex's direct neighbours in the slicing plane face,
+ * with no consistent winding direction around the face for either field (e.g., the neighb1 of X can point back to
+ * X with either its neighb1 or neighb2).
+ */
+ size_t neighbIdx1, neighbIdx2;
};
-struct SliceInfo {
- std::vector v;
- std::vector newv;
- size_t thisFaceNewVertex; // index into newv
- const CBrush* original;
+/// Holds support information during a CBrush/CPlane slicing operation.
+struct SliceOpInfo
+{
CBrush* result;
+ const CBrush* original;
+
+ /**
+ * Holds information about what happens to each vertex in the original brush after the slice operation.
+ * Same size as m_Vertices of the brush getting sliced.
+ */
+ std::vector ovInfo;
+
+ /// Holds information about newly inserted vertices during a slice operation.
+ std::vector nvInfo;
+
+ /**
+ * Indices into nvInfo; during the execution of the slicing algorithm, holds the previously inserted new vertex on
+ * one of the edges of the face that's currently being evaluated for slice points, or NO_VERTEX if no such vertex
+ * exists.
+ */
+ size_t thisFaceNewVertexIdx;
};
struct CBrush::Helper
{
- static size_t SliceNewVertex(SliceInfo& si, size_t v1, size_t v2);
+ /**
+ * Creates a new vertex between the given two vertices (indexed into the original brush).
+ * Returns the index of the new vertex in the resulting brush.
+ */
+ static size_t SliceNewVertex(SliceOpInfo& sliceInfo, size_t v1, size_t v2);
};
-// create a new vertex between the given two vertices (index into original brush)
-// returns the index of the new vertex in the resulting brush
-size_t CBrush::Helper::SliceNewVertex(SliceInfo& si, size_t v1, size_t v2)
+size_t CBrush::Helper::SliceNewVertex(SliceOpInfo& sliceOp, size_t edgeIdx1, size_t edgeIdx2)
{
+ // check if a new vertex has already been inserted on this edge
size_t idx;
-
- for(idx = 0; idx < si.newv.size(); ++idx)
+ for(idx = 0; idx < sliceOp.nvInfo.size(); ++idx)
{
- if ((si.newv[idx].v1 == v1 && si.newv[idx].v2 == v2) ||
- (si.newv[idx].v1 == v2 && si.newv[idx].v2 == v1))
+ if ((sliceOp.nvInfo[idx].edgeIdx1 == edgeIdx1 && sliceOp.nvInfo[idx].edgeIdx2 == edgeIdx2) ||
+ (sliceOp.nvInfo[idx].edgeIdx1 == edgeIdx2 && sliceOp.nvInfo[idx].edgeIdx2 == edgeIdx1))
break;
}
- if (idx >= si.newv.size())
+ if (idx >= sliceOp.nvInfo.size())
{
- NewVertexInfo nvi;
- CVector3D newpos;
- float inv = 1.0 / (si.v[v1].d - si.v[v2].d);
+ // no previously inserted new vertex found on this edge; insert a new one
+ SliceOpNewVertexInfo nvi;
+ CVector3D newPos;
+
+ // interpolate between the two vertices based on their distance from the plane
+ float inv = 1.0 / (sliceOp.ovInfo[edgeIdx1].planeDist - sliceOp.ovInfo[edgeIdx2].planeDist);
+ newPos = sliceOp.original->m_Vertices[edgeIdx2] * ( sliceOp.ovInfo[edgeIdx1].planeDist * inv) +
+ sliceOp.original->m_Vertices[edgeIdx1] * (-sliceOp.ovInfo[edgeIdx2].planeDist * inv);
+
+ nvi.edgeIdx1 = edgeIdx1;
+ nvi.edgeIdx2 = edgeIdx2;
+ nvi.resIdx = sliceOp.result->m_Vertices.size();
+ nvi.neighbIdx1 = NO_VERTEX;
+ nvi.neighbIdx2 = NO_VERTEX;
- newpos = si.original->m_Vertices[v2]*(si.v[v1].d*inv) +
- si.original->m_Vertices[v1]*(-si.v[v2].d*inv);
-
- nvi.v1 = v1;
- nvi.v2 = v2;
- nvi.res = si.result->m_Vertices.size();
- nvi.neighb1 = no_vertex;
- nvi.neighb2 = no_vertex;
- si.result->m_Vertices.push_back(newpos);
- si.newv.push_back(nvi);
+ sliceOp.result->m_Vertices.push_back(newPos);
+ sliceOp.nvInfo.push_back(nvi);
}
- if (si.thisFaceNewVertex != no_vertex)
+ // at this point, 'idx' is the index into nvInfo of the vertex inserted onto the edge
+
+ if (sliceOp.thisFaceNewVertexIdx != NO_VERTEX)
{
- if (si.newv[si.thisFaceNewVertex].neighb1 == no_vertex)
- si.newv[si.thisFaceNewVertex].neighb1 = idx;
+ // a vertex has been previously inserted onto another edge of this face; link them together as neighbours
+ // (using whichever one of the neighbIdx1 or -2 links is still available)
+
+ if (sliceOp.nvInfo[sliceOp.thisFaceNewVertexIdx].neighbIdx1 == NO_VERTEX)
+ sliceOp.nvInfo[sliceOp.thisFaceNewVertexIdx].neighbIdx1 = idx;
else
- si.newv[si.thisFaceNewVertex].neighb2 = idx;
+ sliceOp.nvInfo[sliceOp.thisFaceNewVertexIdx].neighbIdx2 = idx;
- if (si.newv[idx].neighb1 == no_vertex)
- si.newv[idx].neighb1 = si.thisFaceNewVertex;
+ if (sliceOp.nvInfo[idx].neighbIdx1 == NO_VERTEX)
+ sliceOp.nvInfo[idx].neighbIdx1 = sliceOp.thisFaceNewVertexIdx;
else
- si.newv[idx].neighb2 = si.thisFaceNewVertex;
+ sliceOp.nvInfo[idx].neighbIdx2 = sliceOp.thisFaceNewVertexIdx;
- si.thisFaceNewVertex = no_vertex;
+ // a plane should slice a face only in two locations, so reset for the next face
+ sliceOp.thisFaceNewVertexIdx = NO_VERTEX;
}
else
{
- si.thisFaceNewVertex = idx;
+ // store the index of the inserted vertex on this edge, so that we can retrieve it when the plane slices
+ // this face again in another edge
+ sliceOp.thisFaceNewVertexIdx = idx;
}
- return si.newv[idx].res;
+ return sliceOp.nvInfo[idx].resIdx;
}
void CBrush::Slice(const CPlane& plane, CBrush& result) const
{
ENSURE(&result != this);
- SliceInfo si;
+ SliceOpInfo sliceOp;
- si.original = this;
- si.result = &result;
- si.thisFaceNewVertex = no_vertex;
- si.newv.reserve(m_Vertices.size() / 2);
+ sliceOp.original = this;
+ sliceOp.result = &result;
+ sliceOp.thisFaceNewVertexIdx = NO_VERTEX;
+ sliceOp.ovInfo.resize(m_Vertices.size());
+ sliceOp.nvInfo.reserve(m_Vertices.size() / 2);
result.m_Vertices.resize(0); // clear any left-overs
result.m_Faces.resize(0);
result.m_Vertices.reserve(m_Vertices.size() + 2);
result.m_Faces.reserve(m_Faces.size() + 5);
- // Classify and copy vertices
- si.v.resize(m_Vertices.size());
-
+ // Copy vertices that weren't sliced away by the plane to the resulting brush.
for(size_t i = 0; i < m_Vertices.size(); ++i)
{
- si.v[i].d = plane.DistanceToPlane(m_Vertices[i]);
- if (si.v[i].d >= 0.0)
+ const CVector3D& vtx = m_Vertices[i]; // current vertex
+ SliceOpVertexInfo& vtxInfo = sliceOp.ovInfo[i]; // slicing operation info about current vertex
+
+ vtxInfo.planeDist = plane.DistanceToPlane(vtx);
+ if (vtxInfo.planeDist >= 0.0)
{
- si.v[i].res = result.m_Vertices.size();
- result.m_Vertices.push_back(m_Vertices[i]);
+ // positive side of the plane; not sliced away
+ vtxInfo.resIdx = result.m_Vertices.size();
+ result.m_Vertices.push_back(vtx);
}
else
{
- si.v[i].res = no_vertex;
+ // other side of the plane; sliced away
+ vtxInfo.resIdx = NO_VERTEX;
}
}
- // Transfer faces
- size_t firstInFace = no_vertex; // in original brush
- size_t startInResultFaceArray = ~0u;
+ // Transfer faces. (Recall how faces are specified; see CBrush::m_Faces). The idea is to examine each face separately,
+ // and see where its edges cross the slicing plane (meaning that exactly one of the vertices of that edge was cut away).
+ // On those edges, new vertices are introduced where the edge intersects the plane, and the resulting brush's m_Faces
+ // array is updated to refer to the newly inserted vertices instead of the original one that got cut away.
+
+ size_t currentFaceStartIdx = NO_VERTEX; // index of the first vertex of the current face in the original brush
+ size_t resultFaceStartIdx = NO_VERTEX; // index of the first vertex of the current face in the resulting brush
for(size_t i = 0; i < m_Faces.size(); ++i)
{
- if (firstInFace == no_vertex)
+ if (currentFaceStartIdx == NO_VERTEX)
{
- ENSURE(si.thisFaceNewVertex == no_vertex);
+ // starting a new face
+ ENSURE(sliceOp.thisFaceNewVertexIdx == NO_VERTEX);
- firstInFace = m_Faces[i];
- startInResultFaceArray = result.m_Faces.size();
+ currentFaceStartIdx = m_Faces[i];
+ resultFaceStartIdx = result.m_Faces.size();
continue;
}
- size_t prev = m_Faces[i-1];
- size_t cur = m_Faces[i];
+ size_t prevIdx = m_Faces[i-1]; // index of previous vertex in this face list
+ size_t curIdx = m_Faces[i]; // index of current vertex in this face list
- if (si.v[prev].res == no_vertex)
+ if (sliceOp.ovInfo[prevIdx].resIdx == NO_VERTEX)
{
- if (si.v[cur].res != no_vertex)
+ // previous face vertex got sliced away by the plane; see if the edge (prev,current) crosses the slicing plane
+ if (sliceOp.ovInfo[curIdx].resIdx != NO_VERTEX)
{
- // re-entering the front side of the plane
- result.m_Faces.push_back(Helper::SliceNewVertex(si, prev, cur));
- result.m_Faces.push_back(si.v[cur].res);
+ // re-entering the front side of the plane; insert vertex on intersection of plane and (prev,current) edge
+ result.m_Faces.push_back(Helper::SliceNewVertex(sliceOp, prevIdx, curIdx));
+ result.m_Faces.push_back(sliceOp.ovInfo[curIdx].resIdx);
}
}
else
{
- if (si.v[cur].res != no_vertex)
+ // previous face vertex didn't get sliced away; see if the edge (prev,current) crosses the slicing plane
+ if (sliceOp.ovInfo[curIdx].resIdx != NO_VERTEX)
{
- // perfectly normal edge
- result.m_Faces.push_back(si.v[cur].res);
+ // perfectly normal edge; doesn't cross the plane
+ result.m_Faces.push_back(sliceOp.ovInfo[curIdx].resIdx);
}
else
{
- // leaving the front side of the plane
- result.m_Faces.push_back(Helper::SliceNewVertex(si, prev, cur));
+ // leaving the front side of the plane; insert vertex on intersection of plane and edge (prev, current)
+ result.m_Faces.push_back(Helper::SliceNewVertex(sliceOp, prevIdx, curIdx));
}
}
- if (cur == firstInFace)
+ // if we're back at the first vertex of the current face, then we've completed the face
+ if (curIdx == currentFaceStartIdx)
{
- if (result.m_Faces.size() > startInResultFaceArray)
- result.m_Faces.push_back(result.m_Faces[startInResultFaceArray]);
- firstInFace = no_vertex; // start a new face
+ // close the index loop
+ if (result.m_Faces.size() > resultFaceStartIdx)
+ result.m_Faces.push_back(result.m_Faces[resultFaceStartIdx]);
+
+ currentFaceStartIdx = NO_VERTEX; // start a new face
}
}
- ENSURE(firstInFace == no_vertex);
+ ENSURE(currentFaceStartIdx == NO_VERTEX);
- // Create the face that lies in the slicing plane
- if (si.newv.size())
+ // Create the face that lies in the slicing plane. Remember, all the intersections of the slicing plane with face
+ // edges of the brush have been stored in sliceOp.nvInfo by the SliceNewVertex function, and refer to their direct
+ // neighbours in the slicing plane face using the neighbIdx1 and neighbIdx2 fields (in no consistent winding order).
+
+ if (sliceOp.nvInfo.size())
{
- size_t prev = 0;
+ // push the starting vertex
+ result.m_Faces.push_back(sliceOp.nvInfo[0].resIdx);
+
+ // At this point, there is no consistent winding order in the neighbX fields, so at each vertex we need to figure
+ // out whether neighb1 or neighb2 points 'onwards' along the face, according to an initially chosen winding direction.
+ // (or, equivalently, which one points back to the one we were just at). At each vertex, we then set neighb1 to be the
+ // one to point onwards, deleting any pointers which we no longer need to complete the trace.
+
size_t idx;
+ size_t prev = 0;
- result.m_Faces.push_back(si.newv[0].res);
- idx = si.newv[0].neighb2;
- si.newv[0].neighb2 = no_vertex;
+ idx = sliceOp.nvInfo[0].neighbIdx2; // pick arbitrary starting direction
+ sliceOp.nvInfo[0].neighbIdx2 = NO_VERTEX;
while(idx != 0)
{
- ENSURE(idx < si.newv.size());
- if (idx >= si.newv.size())
+ ENSURE(idx < sliceOp.nvInfo.size());
+ if (idx >= sliceOp.nvInfo.size())
break;
- if (si.newv[idx].neighb1 == prev)
+ if (sliceOp.nvInfo[idx].neighbIdx1 == prev)
{
- si.newv[idx].neighb1 = si.newv[idx].neighb2;
- si.newv[idx].neighb2 = no_vertex;
+ // neighb1 is pointing the wrong way; we want to normalize it to point onwards in the direction
+ // we initially chose, so swap it with neighb2 and delete neighb2 (no longer needed)
+ sliceOp.nvInfo[idx].neighbIdx1 = sliceOp.nvInfo[idx].neighbIdx2;
+ sliceOp.nvInfo[idx].neighbIdx2 = NO_VERTEX;
}
else
{
- ENSURE(si.newv[idx].neighb2 == prev);
-
- si.newv[idx].neighb2 = no_vertex;
+ // neighb1 isn't pointing to the previous vertex, so neighb2 must be (otherwise a pair of vertices failed to
+ // get paired properly during face/plane slicing).
+ ENSURE(sliceOp.nvInfo[idx].neighbIdx2 == prev);
+ sliceOp.nvInfo[idx].neighbIdx2 = NO_VERTEX;
}
- result.m_Faces.push_back(si.newv[idx].res);
+ result.m_Faces.push_back(sliceOp.nvInfo[idx].resIdx);
+ // move to next vertex; neighb1 has been normalized to point onward
prev = idx;
- idx = si.newv[idx].neighb1;
- si.newv[prev].neighb1 = no_vertex;
+ idx = sliceOp.nvInfo[idx].neighbIdx1;
+ sliceOp.nvInfo[prev].neighbIdx1 = NO_VERTEX; // no longer needed, we've moved on
}
- result.m_Faces.push_back(si.newv[0].res);
+ // push starting vertex again to close the shape
+ result.m_Faces.push_back(sliceOp.nvInfo[0].resIdx);
}
}
+
///////////////////////////////////////////////////////////////////////////////
// Intersect with frustum by repeated slicing
void CBrush::Intersect(const CFrustum& frustum, CBrush& result) const
{
ENSURE(&result != this);
if (!frustum.GetNumPlanes())
{
result = *this;
return;
}
CBrush buf;
const CBrush* prev = this;
CBrush* next;
+ // Repeatedly slice this brush with each plane of the frustum, alternating between 'result' and 'buf' to
+ // save intermediate results. Set up the starting brush so that the final version always ends up in 'result'.
+
if (frustum.GetNumPlanes() & 1)
next = &result;
else
next = &buf;
for(size_t i = 0; i < frustum.GetNumPlanes(); ++i)
{
prev->Slice(frustum[i], *next);
prev = next;
if (prev == &buf)
next = &result;
else
next = &buf;
}
ENSURE(prev == &result);
+}
+std::vector CBrush::GetVertices() const
+{
+ return m_Vertices;
+}
+
+void CBrush::GetFaces(std::vector >& out) const
+{
+ // split the back-to-back faces into separate face vectors, so that they're in a
+ // user-friendlier format than the back-to-back vertex index array
+ // i.e. split 'x--xy------yz----z' into 'x--x', 'y-------y', 'z---z'
+
+ size_t faceStartIdx = 0;
+ while (faceStartIdx < m_Faces.size())
+ {
+ // start new face
+ std::vector singleFace;
+ singleFace.push_back(m_Faces[faceStartIdx]);
+
+ // step over all the values in the face until we hit the starting value again (which closes the face)
+ size_t j = faceStartIdx + 1;
+ while (j < m_Faces.size() && m_Faces[j] != m_Faces[faceStartIdx])
+ {
+ singleFace.push_back(m_Faces[j]);
+ j++;
+ }
+
+ // each face must be closed by the same value that started it
+ ENSURE(m_Faces[faceStartIdx] == m_Faces[j]);
+
+ singleFace.push_back(m_Faces[j]);
+ out.push_back(singleFace);
+
+ faceStartIdx = j + 1;
+ }
}
\ No newline at end of file
Index: ps/trunk/source/maths/BoundingBoxAligned.cpp
===================================================================
--- ps/trunk/source/maths/BoundingBoxAligned.cpp (revision 11440)
+++ ps/trunk/source/maths/BoundingBoxAligned.cpp (revision 11441)
@@ -1,302 +1,308 @@
-/* Copyright (C) 2011 Wildfire Games.
+/* Copyright (C) 2012 Wildfire Games.
* This file is part of 0 A.D.
*
* 0 A.D. is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 2 of the License, or
* (at your option) any later version.
*
* 0 A.D. is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with 0 A.D. If not, see .
*/
/*
* Axis-aligned bounding box
*/
#include "precompiled.h"
#include "BoundingBoxAligned.h"
#include "lib/ogl.h"
#include
#include "graphics/Frustum.h"
#include "maths/BoundingBoxOriented.h"
#include "maths/Brush.h"
#include "maths/Matrix3D.h"
const CBoundingBoxAligned CBoundingBoxAligned::EMPTY = CBoundingBoxAligned(); // initializes to an empty bound
///////////////////////////////////////////////////////////////////////////////
// RayIntersect: intersect ray with this bound; return true
// if ray hits (and store entry and exit times), or false
// otherwise
// note: incoming ray direction must be normalised
bool CBoundingBoxAligned::RayIntersect(const CVector3D& origin,const CVector3D& dir,
float& tmin,float& tmax) const
{
float t1,t2;
float tnear,tfar;
if (dir[0]==0) {
if (origin[0]m_Data[1][0])
return false;
else {
tnear=(float) -FLT_MAX;
tfar=(float) FLT_MAX;
}
} else {
t1=(m_Data[0][0]-origin[0])/dir[0];
t2=(m_Data[1][0]-origin[0])/dir[0];
if (dir[0]<0) {
tnear = t2;
tfar = t1;
} else {
tnear = t1;
tfar = t2;
}
if (tfar<0)
return false;
}
if (dir[1]==0 && (origin[1]m_Data[1][1]))
return false;
else {
t1=(m_Data[0][1]-origin[1])/dir[1];
t2=(m_Data[1][1]-origin[1])/dir[1];
if (dir[1]<0) {
if (t2>tnear)
tnear = t2;
if (t1tnear)
tnear = t1;
if (t2tfar || tfar<0)
return false;
}
if (dir[2]==0 && (origin[2]m_Data[1][2]))
return false;
else {
t1=(m_Data[0][2]-origin[2])/dir[2];
t2=(m_Data[1][2]-origin[2])/dir[2];
if (dir[2]<0) {
if (t2>tnear)
tnear = t2;
if (t1tnear)
tnear = t1;
if (t2tfar || tfar<0)
return false;
}
tmin=tnear;
tmax=tfar;
return true;
}
///////////////////////////////////////////////////////////////////////////////
// SetEmpty: initialise this bound as empty
void CBoundingBoxAligned::SetEmpty()
{
m_Data[0]=CVector3D( FLT_MAX, FLT_MAX, FLT_MAX);
m_Data[1]=CVector3D(-FLT_MAX,-FLT_MAX,-FLT_MAX);
}
///////////////////////////////////////////////////////////////////////////////
// IsEmpty: tests whether this bound is empty
bool CBoundingBoxAligned::IsEmpty() const
{
return (m_Data[0].X == FLT_MAX && m_Data[0].Y == FLT_MAX && m_Data[0].Z == FLT_MAX
&& m_Data[1].X == -FLT_MAX && m_Data[1].Y == -FLT_MAX && m_Data[1].Z == -FLT_MAX);
}
///////////////////////////////////////////////////////////////////////////////
// Transform: transform this bound by given matrix; return transformed bound
// in 'result' parameter - slightly modified version of code in Graphic Gems
// (can't remember which one it was, though)
void CBoundingBoxAligned::Transform(const CMatrix3D& m, CBoundingBoxAligned& result) const
{
ENSURE(this!=&result);
for (int i=0;i<3;++i) {
// handle translation
result[0][i]=result[1][i]=m(i,3);
// Now find the extreme points by considering the product of the
// min and max with each component of matrix
for(int j=0;j<3;j++) {
float a=m(i,j)*m_Data[0][j];
float b=m(i,j)*m_Data[1][j];
if (a data;
#define ADD_FACE(x, y, z) \
ADD_PT(0, 0, x, y, z); ADD_PT(1, 0, x, y, z); ADD_PT(1, 1, x, y, z); \
ADD_PT(1, 1, x, y, z); ADD_PT(0, 1, x, y, z); ADD_PT(0, 0, x, y, z);
#define ADD_PT(u_, v_, x, y, z) \
STMT(int u = u_; int v = v_; \
data.push_back(u); \
data.push_back(v); \
data.push_back(m_Data[x].X); \
data.push_back(m_Data[y].Y); \
data.push_back(m_Data[z].Z); \
)
ADD_FACE(u, v, 0);
ADD_FACE(0, u, v);
ADD_FACE(u, 0, 1-v);
ADD_FACE(u, 1-v, 1);
ADD_FACE(1, u, 1-v);
ADD_FACE(u, 1, v);
#undef ADD_FACE
shader->TexCoordPointer(GL_TEXTURE0, 2, GL_FLOAT, 5*sizeof(float), &data[0]);
shader->VertexPointer(3, GL_FLOAT, 5*sizeof(float), &data[2]);
shader->AssertPointersBound();
glDrawArrays(GL_TRIANGLES, 0, 6*6);
}
void CBoundingBoxAligned::RenderOutline(CShaderProgramPtr& shader) const
{
std::vector data;
#define ADD_FACE(x, y, z) \
ADD_PT(0, 0, x, y, z); ADD_PT(1, 0, x, y, z); \
ADD_PT(1, 0, x, y, z); ADD_PT(1, 1, x, y, z); \
ADD_PT(1, 1, x, y, z); ADD_PT(0, 1, x, y, z); \
ADD_PT(0, 1, x, y, z); ADD_PT(0, 0, x, y, z);
#define ADD_PT(u_, v_, x, y, z) \
STMT(int u = u_; int v = v_; \
data.push_back(u); \
data.push_back(v); \
data.push_back(m_Data[x].X); \
data.push_back(m_Data[y].Y); \
data.push_back(m_Data[z].Z); \
)
ADD_FACE(u, v, 0);
ADD_FACE(0, u, v);
ADD_FACE(u, 0, 1-v);
ADD_FACE(u, 1-v, 1);
ADD_FACE(1, u, 1-v);
ADD_FACE(u, 1, v);
#undef ADD_FACE
shader->TexCoordPointer(GL_TEXTURE0, 2, GL_FLOAT, 5*sizeof(float), &data[0]);
shader->VertexPointer(3, GL_FLOAT, 5*sizeof(float), &data[2]);
shader->AssertPointersBound();
glDrawArrays(GL_LINES, 0, 6*8);
}
Index: ps/trunk/source/maths/Brush.h
===================================================================
--- ps/trunk/source/maths/Brush.h (revision 11440)
+++ ps/trunk/source/maths/Brush.h (revision 11441)
@@ -1,90 +1,115 @@
-/* Copyright (C) 2009 Wildfire Games.
+/* Copyright (C) 2012 Wildfire Games.
* This file is part of 0 A.D.
*
* 0 A.D. is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 2 of the License, or
* (at your option) any later version.
*
* 0 A.D. is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with 0 A.D. If not, see .
*/
/*
* CBrush, a class representing a convex object
*/
#ifndef maths_brush_h
#define maths_brush_h
#include "Vector3D.h"
class CBoundingBoxAligned;
class CFrustum;
class CPlane;
/**
* Class CBrush: Represents a convex object, supports some CSG operations.
*/
class CBrush
{
+ friend class TestBrush;
+
public:
CBrush() { }
/**
* CBrush: Construct a brush from a bounds object.
*
* @param bounds the CBoundingBoxAligned object to construct the brush from.
*/
CBrush(const CBoundingBoxAligned& bounds);
/**
* IsEmpty: Returns whether the brush is empty.
*
* @return @c true if the brush is empty, @c false otherwise
*/
bool IsEmpty() const { return m_Vertices.size() == 0; }
/**
* Bounds: Calculate the axis-aligned bounding box for this brush.
*
* @param result the resulting bounding box is stored here
*/
void Bounds(CBoundingBoxAligned& result) const;
/**
- * Slice: Cut the object along the given plane, resulting in a smaller (or even empty)
- * brush representing the part of the object that lies in front of the plane.
+ * Slice: Cut the object along the given plane, resulting in a smaller (or even empty) brush representing
+ * the part of the object that lies in front of the plane (as defined by the positive direction of its
+ * normal vector).
*
* @param plane the slicing plane
* @param result the resulting brush is stored here
*/
void Slice(const CPlane& plane, CBrush& result) const;
/**
* Intersect: Intersect the brush with the given frustum.
*
* @param frustum the frustum to intersect with
* @param result the resulting brush is stored here
*/
void Intersect(const CFrustum& frustum, CBrush& result) const;
private:
- static const size_t no_vertex = ~0u;
+
+ /**
+ * Returns a copy of the vertices in this brush. Intended for testing purposes; you should not need to use
+ * this method directly.
+ */
+ std::vector GetVertices() const;
+
+ /**
+ * Writes a vector of the faces in this brush to @p out. Each face is itself a vector, listing the vertex indices
+ * that make up the face, starting and ending with the same index. Intended for testing purposes; you should not
+ * need to use this method directly.
+ */
+ void GetFaces(std::vector >& out) const;
+
+private:
+ static const size_t NO_VERTEX = ~0u;
typedef std::vector Vertices;
typedef std::vector FaceIndices;
+ /// Collection of unique vertices that make up this shape.
Vertices m_Vertices;
+
+ /**
+ * Holds the face definitions of this brush. Each face is a sequence of indices into m_Vertices that starts and ends with
+ * the same vertex index, completing a loop through all the vertices that make up the face. This vector holds all the face
+ * sequences back-to-back, thus looking something like 'x---xy--------yz--z' in the general case.
+ */
FaceIndices m_Faces;
struct Helper;
};
#endif // maths_brush_h