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