I just recently added frustum culling to my voxel game; it worked pretty well at first glance. However, I immediately noticed that the frustum seems to be a little off—being that some voxels near the edge of the window are prematurely cut-off, before completely falling out of visual scope. Here is an image that illustrates my endeavor:
And Here are three classes which will likely be needed to solve this problem.
My FrustumWidget Class:
using System;
using OpenTK;
namespace GameProject.Game.Client.Widgets {
public class FrustumWidget {
private float[] _clipMatrix = new float[ 16 ];
private float[ , ] _frustum = new float[ 6 , 4 ];
const int RIGHT = 0 , LEFT = 1 , BOTTOM = 2 , TOP = 3 , BACK = 4 , FRONT = 5;
private void NormalizePlane( float[ , ] frustum , int side ) {
float magnitude = ( float )Math.Sqrt( ( frustum[ side , 0 ] * frustum[ side , 0 ] ) + ( frustum[ side , 1 ] * frustum[ side , 1 ] )
+ ( frustum[ side , 2 ] * frustum[ side , 2 ] ) );
frustum[ side , 0 ] /= magnitude;
frustum[ side , 1 ] /= magnitude;
frustum[ side , 2 ] /= magnitude;
frustum[ side , 3 ] /= magnitude;
}
public bool SphereInFrustum( float x , float y , float z , float radius ) {
float d = 0;
for( int p = 0; p < 6; p++ ) {
d = _frustum[ p , 0 ] * x + _frustum[ p , 1 ] * y + _frustum[ p , 2 ] * z + _frustum[ p , 3 ];
if( d <= -radius )
{
return false;
}
}
return true;
}
public bool VoxelWithinFrustum( float x1 , float y1 , float z1 , float x2 , float y2 , float z2 ) {
for( int i = 0; i < 6; i++ ) {
if( ( this._frustum[ i , 0 ] * x1 + this._frustum[ i , 1 ] * y1 + this._frustum[ i , 2 ] * z1 + this._frustum[ i, 3 ] <= 0.0F ) &&
( this._frustum[ i , 0 ] * x2 + this._frustum[ i , 1 ] * y1 + this._frustum[ i , 2 ] * z1 + this._frustum[ i , 3 ] <= 0.0F ) &&
( this._frustum[ i , 0 ] * x1 + this._frustum[ i , 1 ] * y2 + this._frustum[ i , 2 ] * z1 + this._frustum[ i , 3 ] <= 0.0F ) &&
( this._frustum[ i , 0 ] * x2 + this._frustum[ i , 1 ] * y2 + this._frustum[ i , 2 ] * z1 + this._frustum[ i , 3 ] <= 0.0F ) &&
( this._frustum[ i , 0 ] * x1 + this._frustum[ i , 1 ] * y1 + this._frustum[ i , 2 ] * z2 + this._frustum[ i , 3 ] <= 0.0F ) &&
( this._frustum[ i , 0 ] * x2 + this._frustum[ i , 1 ] * y1 + this._frustum[ i , 2 ] * z2 + this._frustum[ i , 3 ] <= 0.0F ) &&
( this._frustum[ i , 0 ] * x1 + this._frustum[ i , 1 ] * y2 + this._frustum[ i , 2 ] * z2 + this._frustum[ i , 3 ] <= 0.0F ) &&
( this._frustum[ i , 0 ] * x2 + this._frustum[ i , 1 ] * y2 + this._frustum[ i , 2 ] * z2 + this._frustum[ i , 3 ] <= 0.0F ) ) {
return false;
}
}
return true;
}
public void CalculateFrustum( Matrix4 projectionMatrix , Matrix4 modelViewMatrix ) {
_clipMatrix[ 0 ] = ( modelViewMatrix.M11 * projectionMatrix.M11 ) + ( modelViewMatrix.M12 * projectionMatrix.M21 ) + ( modelViewMatrix.M13 * projectionMatrix.M31 ) + ( modelViewMatrix.M14 * projectionMatrix.M41 );
_clipMatrix[ 1 ] = ( modelViewMatrix.M11 * projectionMatrix.M12 ) + ( modelViewMatrix.M12 * projectionMatrix.M22 ) + ( modelViewMatrix.M13 * projectionMatrix.M32 ) + ( modelViewMatrix.M14 * projectionMatrix.M42 );
_clipMatrix[ 2 ] = ( modelViewMatrix.M11 * projectionMatrix.M13 ) + ( modelViewMatrix.M12 * projectionMatrix.M23 ) + ( modelViewMatrix.M13 * projectionMatrix.M33 ) + ( modelViewMatrix.M14 * projectionMatrix.M43 );
_clipMatrix[ 3 ] = ( modelViewMatrix.M11 * projectionMatrix.M14 ) + ( modelViewMatrix.M12 * projectionMatrix.M24 ) + ( modelViewMatrix.M13 * projectionMatrix.M34 ) + ( modelViewMatrix.M14 * projectionMatrix.M44 );
_clipMatrix[ 4 ] = ( modelViewMatrix.M21 * projectionMatrix.M11 ) + ( modelViewMatrix.M22 * projectionMatrix.M21 ) + ( modelViewMatrix.M23 * projectionMatrix.M31 ) + ( modelViewMatrix.M24 * projectionMatrix.M41 );
_clipMatrix[ 5 ] = ( modelViewMatrix.M21 * projectionMatrix.M12 ) + ( modelViewMatrix.M22 * projectionMatrix.M22 ) + ( modelViewMatrix.M23 * projectionMatrix.M32 ) + ( modelViewMatrix.M24 * projectionMatrix.M42 );
_clipMatrix[ 6 ] = ( modelViewMatrix.M21 * projectionMatrix.M13 ) + ( modelViewMatrix.M22 * projectionMatrix.M23 ) + ( modelViewMatrix.M23 * projectionMatrix.M33 ) + ( modelViewMatrix.M24 * projectionMatrix.M43 );
_clipMatrix[ 7 ] = ( modelViewMatrix.M21 * projectionMatrix.M14 ) + ( modelViewMatrix.M22 * projectionMatrix.M24 ) + ( modelViewMatrix.M23 * projectionMatrix.M34 ) + ( modelViewMatrix.M24 * projectionMatrix.M44 );
_clipMatrix[ 8 ] = ( modelViewMatrix.M31 * projectionMatrix.M11 ) + ( modelViewMatrix.M32 * projectionMatrix.M21 ) + ( modelViewMatrix.M33 * projectionMatrix.M31 ) + ( modelViewMatrix.M34 * projectionMatrix.M41 );
_clipMatrix[ 9 ] = ( modelViewMatrix.M31 * projectionMatrix.M12 ) + ( modelViewMatrix.M32 * projectionMatrix.M22 ) + ( modelViewMatrix.M33 * projectionMatrix.M32 ) + ( modelViewMatrix.M34 * projectionMatrix.M42 );
_clipMatrix[ 10 ] = ( modelViewMatrix.M31 * projectionMatrix.M13 ) + ( modelViewMatrix.M32 * projectionMatrix.M23 ) + ( modelViewMatrix.M33 * projectionMatrix.M33 ) + ( modelViewMatrix.M34 * projectionMatrix.M43 );
_clipMatrix[ 11 ] = ( modelViewMatrix.M31 * projectionMatrix.M14 ) + ( modelViewMatrix.M32 * projectionMatrix.M24 ) + ( modelViewMatrix.M33 * projectionMatrix.M34 ) + ( modelViewMatrix.M34 * projectionMatrix.M44 );
_clipMatrix[ 12 ] = ( modelViewMatrix.M41 * projectionMatrix.M11 ) + ( modelViewMatrix.M42 * projectionMatrix.M21 ) + ( modelViewMatrix.M43 * projectionMatrix.M31 ) + ( modelViewMatrix.M44 * projectionMatrix.M41 );
_clipMatrix[ 13 ] = ( modelViewMatrix.M41 * projectionMatrix.M12 ) + ( modelViewMatrix.M42 * projectionMatrix.M22 ) + ( modelViewMatrix.M43 * projectionMatrix.M32 ) + ( modelViewMatrix.M44 * projectionMatrix.M42 );
_clipMatrix[ 14 ] = ( modelViewMatrix.M41 * projectionMatrix.M13 ) + ( modelViewMatrix.M42 * projectionMatrix.M23 ) + ( modelViewMatrix.M43 * projectionMatrix.M33 ) + ( modelViewMatrix.M44 * projectionMatrix.M43 );
_clipMatrix[ 15 ] = ( modelViewMatrix.M41 * projectionMatrix.M14 ) + ( modelViewMatrix.M42 * projectionMatrix.M24 ) + ( modelViewMatrix.M43 * projectionMatrix.M34 ) + ( modelViewMatrix.M44 * projectionMatrix.M44 );
_frustum[ RIGHT , 0 ] = _clipMatrix[ 3 ] - _clipMatrix[ 0 ];
_frustum[ RIGHT , 1 ] = _clipMatrix[ 7 ] - _clipMatrix[ 4 ];
_frustum[ RIGHT , 2 ] = _clipMatrix[ 11 ] - _clipMatrix[ 8 ];
_frustum[ RIGHT , 3 ] = _clipMatrix[ 15 ] - _clipMatrix[ 12 ];
NormalizePlane( _frustum , RIGHT );
_frustum[ LEFT , 0 ] = _clipMatrix[ 3 ] + _clipMatrix[ 0 ];
_frustum[ LEFT , 1 ] = _clipMatrix[ 7 ] + _clipMatrix[ 4 ];
_frustum[ LEFT , 2 ] = _clipMatrix[ 11 ] + _clipMatrix[ 8 ];
_frustum[ LEFT , 3 ] = _clipMatrix[ 15 ] + _clipMatrix[ 12 ];
NormalizePlane( _frustum , LEFT );
_frustum[ BOTTOM , 0 ] = _clipMatrix[ 3 ] + _clipMatrix[ 1 ];
_frustum[ BOTTOM , 1 ] = _clipMatrix[ 7 ] + _clipMatrix[ 5 ];
_frustum[ BOTTOM , 2 ] = _clipMatrix[ 11 ] + _clipMatrix[ 9 ];
_frustum[ BOTTOM , 3 ] = _clipMatrix[ 15 ] + _clipMatrix[ 13 ];
NormalizePlane( _frustum , BOTTOM );
_frustum[ TOP , 0 ] = _clipMatrix[ 3 ] - _clipMatrix[ 1 ];
_frustum[ TOP , 1 ] = _clipMatrix[ 7 ] - _clipMatrix[ 5 ];
_frustum[ TOP , 2 ] = _clipMatrix[ 11 ] - _clipMatrix[ 9 ];
_frustum[ TOP , 3 ] = _clipMatrix[ 15 ] - _clipMatrix[ 13 ];
NormalizePlane( _frustum , TOP );
_frustum[ BACK , 0 ] = _clipMatrix[ 3 ] - _clipMatrix[ 2 ];
_frustum[ BACK , 1 ] = _clipMatrix[ 7 ] - _clipMatrix[ 6 ];
_frustum[ BACK , 2 ] = _clipMatrix[ 11 ] - _clipMatrix[ 10 ];
_frustum[ BACK , 3 ] = _clipMatrix[ 15 ] - _clipMatrix[ 14 ];
NormalizePlane( _frustum , BACK );
_frustum[ FRONT , 0 ] = _clipMatrix[ 3 ] + _clipMatrix[ 2 ];
_frustum[ FRONT , 1 ] = _clipMatrix[ 7 ] + _clipMatrix[ 6 ];
_frustum[ FRONT , 2 ] = _clipMatrix[ 11 ] + _clipMatrix[ 10 ];
_frustum[ FRONT , 3 ] = _clipMatrix[ 15 ] + _clipMatrix[ 14 ];
NormalizePlane( _frustum , FRONT );
}
}
}
My FirstPersonCameraWidget class:
using System;
using System.Drawing;
using OpenTK;
using GameProject.Game.Framework.OpenTKExtensions;
using OpenTK.Graphics.OpenGL;
using OpenTK.Input;
namespace GameProject.Game.Client.Widgets {
public class FirstPersonCameraWidget {
public Matrix4 CameraMatrix;
public Vector3 Location;
public FrustumWidget Frustum;
public float Pitch;
public float Yaw;
public float MoveSpeed;
public float LookSpeed;
public Vector2 MouseSpeed;
public bool IsLooking;
public float NearZ;
public float FarZ;
public FirstPersonCameraWidget(Vector3 cameraOrigin , float pitch , float yaw , float movementSpeed , float lookSpeed ) {
CameraMatrix = Matrix4.Identity;
this.Location = cameraOrigin;
this.Pitch = pitch;
this.Yaw = yaw;
this.LookSpeed = lookSpeed;
this.MoveSpeed = movementSpeed;
Frustum = new FrustumWidget();
}
public void Update() {
if( IsLooking ) {
// Possible redundant method?
}
}
public void ProcessMovement( KeyboardState keyboardState , FrameEventArgs e ) {
if( keyboardState[ Key.W ] ) {
MoveForward( e );
}
if( keyboardState[ Key.S ] ) {
MoveBackward( e );
}
if( keyboardState[ Key.A ] ) {
StrafeLeft( e );
}
if( keyboardState[ Key.D ] ) {
StrafeRight( e );
}
if( keyboardState[ Key.Space ] ) {
FlyUp( e );
}
if( keyboardState[ Key.LShift ] || keyboardState[ Key.RShift ] ) {
FlyDown( e );
}
}
public void MoveForward( FrameEventArgs e ) {
Location.X += ( float )Math.Cos( Yaw ) * MoveSpeed * ( float )e.Time;
//CameraPosition.Y += ( float )Math.Tan( Pitch ) * MoveSpeed * ( float )e.Time;
Location.Z += ( float )Math.Sin( Yaw ) * MoveSpeed * ( float )e.Time;
}
public void MoveBackward( FrameEventArgs e ) {
Location.X -= ( float )Math.Cos( Yaw ) * MoveSpeed * ( float )e.Time;
//CameraPosition.Y -= ( float )Math.Tan( Pitch ) * MoveSpeed * ( float )e.Time;
Location.Z -= ( float )Math.Sin( Yaw ) * MoveSpeed * ( float )e.Time;
}
public void StrafeLeft( FrameEventArgs e ) {
Location.X -= ( float )Math.Cos( Yaw + Math.PI / 2 ) * MoveSpeed * ( float )e.Time;
Location.Z -= ( float )Math.Sin( Yaw + Math.PI / 2 ) * MoveSpeed * ( float )e.Time;
}
public void StrafeRight( FrameEventArgs e ) {
Location.X += ( float )Math.Cos( Yaw + Math.PI / 2 ) * MoveSpeed * ( float )e.Time;
Location.Z += ( float )Math.Sin( Yaw + Math.PI / 2 ) * MoveSpeed * ( float )e.Time;
}
public void FlyUp( FrameEventArgs e ) {
Location.Y += MoveSpeed * ( float )e.Time;
}
public void FlyDown( FrameEventArgs e ) {
Location.Y -= MoveSpeed * ( float )e.Time;
}
public void LookThrough( GameWindow window , Point mouseLocation , FrameEventArgs e ) {
if( IsLooking ) {
Point windowCenter = new Point( window.Bounds.Left + window.Bounds.Width / 2 , window.Bounds.Top + window.Bounds.Height / 2 );
Vector2 MouseDelta = new Vector2( mouseLocation.X - window.PointToClient( windowCenter ).X , mouseLocation.Y - window.PointToClient( windowCenter ).Y );
System.Windows.Forms.Cursor.Position = windowCenter;
MouseSpeed.X *= LookSpeed;
MouseSpeed.Y *= LookSpeed;
MouseSpeed.X += MouseDelta.X / 40.0f * ( float )e.Time;
MouseSpeed.Y += MouseDelta.Y / 40.0f * ( float )e.Time;
Yaw += MouseSpeed.X;
Pitch -= MouseSpeed.Y;
if( Pitch <= -( ( OpenTKExtensions.HalfPI * 2 ) * 0.5f ) + 0.01f ) {
Pitch = -( ( OpenTKExtensions.HalfPI * 2 ) * 0.5f ) + 0.01f;
}
if( Pitch >= ( ( OpenTKExtensions.HalfPI * 2 ) * 0.5f ) - 0.01f ) {
Pitch = ( ( OpenTKExtensions.HalfPI * 2 ) * 0.5f ) - 0.01f;
}
}
Vector3 LookAtPoint = new Vector3( ( float )Math.Cos( Yaw ) , ( float )Math.Tan( Pitch ) , ( float )Math.Sin( Yaw ) );
CameraMatrix = Matrix4.LookAt( Location , Location + LookAtPoint , Vector3.UnitY );
/**
* Recalculate the Viewport Frustum
*/
Matrix4 projection = new Matrix4();
GL.GetFloat(GetPName.ProjectionMatrix, out projection);
Matrix4 modelview = new Matrix4();
GL.GetFloat(GetPName.ModelviewMatrix, out modelview);
Frustum.CalculateFrustum(projection,modelview);
}
}
}
And Lastly, my GameClient class:
using System;
using System.Collections.Generic;
using System.Drawing;
using System.Threading.Tasks;
using GameProject.Game.Framework.DataStructure;
using GameProject.Game.Framework.Generators;
using GameProject.Game.Framework.Geometry;
using System.Diagnostics;
using GameProject.Game.Framework.OpenGLExtensions;
using OpenTK;
using OpenTK.Graphics;
using OpenTK.Graphics.OpenGL;
using OpenTK.Input;
using GameProject.Game.Client.Widgets;
using QuickFont;
namespace GameProject.Game.Client {
public class GameClient : GameWindow {
/**
* Client Variables
*/
public const String CLIENT_VERSION = "v0.0.1";
public const String GAME_NAME = "Voxelbyte";
public FirstPersonCameraWidget GameCamera;
private Point _mousePosition;
private Point _lastMousePosition;
private bool _centerCursorAfterRelease = false;
/**
* Game Variables
*/
public VoxelWorld World;
public List<GameSelection> SelectionMemory;
public QFont DeveloperText;
public GameClient()
: base( 800 , 600 , GraphicsMode.Default , GAME_NAME ) {
GL.Enable( EnableCap.DepthTest );
GL.ClearColor( 0.3f , 0.3f , 0.3f , 0.0f );
}
protected override void OnLoad( EventArgs e ) {
base.OnLoad( e );
DeveloperText = new QFont( "Resources/Fonts/times.ttf" , 14 , FontStyle.Regular );
//TestFont.Options.UseDefaultBlendFunction = false;
//this.VSync = VSyncMode.On;
SelectionMemory = new List<GameSelection>();
GameCamera = new FirstPersonCameraWidget(
new Vector3( 30.0f , 8.0f , 30.0f ) ,
0.0f ,
0.0f ,
15.0f ,
0.4f );
//this.WindowState = WindowState.Fullscreen;
GL.CullFace( CullFaceMode.Back );
GL.Enable( EnableCap.CullFace );
GL.BlendFunc( BlendingFactorSrc.SrcAlpha , BlendingFactorDest.OneMinusSrcAlpha );
GL.Enable( EnableCap.Blend );
// Generate Map And Log the Time
World = BattleWorldReader.ReadFromImage( "ColoredPyramid.png" );
Stopwatch sw = new Stopwatch();
sw.Start();
World.Rebuild();
sw.Stop();
Console.WriteLine( "World Generation+Optimization took: {0}ms" , sw.ElapsedMilliseconds );
//GLExtensions.EnableWireframe();
}
protected override void OnMouseMove( MouseMoveEventArgs e ) {
base.OnMouseMove( e );
_mousePosition = new Point( e.X , e.Y );
if( e.Mouse.IsButtonDown( MouseButton.Right ) ) {
}
}
protected override void OnMouseDown( MouseButtonEventArgs e ) {
base.OnMouseDown( e );
if( e.Mouse.IsButtonDown( MouseButton.Right ) ) {
Point nativeMouse = System.Windows.Forms.Cursor.Position;
_lastMousePosition = nativeMouse;
Point windowCenter = new Point( Bounds.Left + Bounds.Width / 2 , Bounds.Top + Bounds.Height / 2 );
System.Windows.Forms.Cursor.Position = windowCenter;
GameCamera.IsLooking = true;
this.CursorVisible = false;
}
}
protected override void OnMouseUp( MouseButtonEventArgs e ) {
base.OnMouseUp( e );
if( e.Button == MouseButton.Right ) {
GameCamera.IsLooking = false;
if( !_centerCursorAfterRelease ) {
System.Windows.Forms.Cursor.Position = _lastMousePosition;
}
this.CursorVisible = true;
}
}
protected override void OnRenderFrame( FrameEventArgs e ) {
base.OnRenderFrame( e );
GameCamera.LookThrough( this , _mousePosition , e );
GL.MatrixMode( MatrixMode.Modelview );
GL.Clear( ClearBufferMask.ColorBufferBit | ClearBufferMask.DepthBufferBit );
GL.LoadMatrix( ref GameCamera.CameraMatrix );
//
//
GL.EnableClientState( ArrayCap.VertexArray );
GL.EnableClientState( ArrayCap.TextureCoordArray );
GL.DisableClientState( ArrayCap.ColorArray );
int numberOfVoxelsRendered = 0;
foreach( Voxel voxel in World.Voxels ) {
if( GameCamera.Frustum.VoxelWithinFrustum( voxel.Location.X, voxel.Location.Y, voxel.Location.Z, 1.0f,1.0f,1.0f ) ) {
voxel.Render( GameCamera );
numberOfVoxelsRendered++;
}
}
GL.DisableClientState( ArrayCap.VertexArray );
GL.DisableClientState( ArrayCap.TextureCoordArray );
GL.DisableClientState( ArrayCap.ColorArray );
// Render Dev Hud
RenderDeveloperHud();
//
SwapBuffers();
this.Title = GAME_NAME + " FPS: " + ( int )this.RenderFrequency + " Voxels: " + numberOfVoxelsRendered;
}
private void RenderDeveloperHud() {
QFont.Begin();
GL.PushMatrix();
GL.Translate( 0.0f , 5 , 0f );
DeveloperText.Print( "Voxelbyte" );
GL.Translate( 0f , 30 , 0f );
DeveloperText.Print( "X: " + ( int )GameCamera.Location.X );
GL.Translate( 0f , 24 , 0f );
DeveloperText.Print( "Y: " + ( int )GameCamera.Location.Y );
GL.Translate( 0.0f , 24 , 0f );
DeveloperText.Print( "Z: " + ( int )GameCamera.Location.Z );
GL.PopMatrix();
QFont.End();
}
private void CheckKeyboardInput( FrameEventArgs eventArgs ) {
KeyboardState keyboardState = OpenTK.Input.Keyboard.GetState();
GameCamera.ProcessMovement( keyboardState , eventArgs );
if( keyboardState[ Key.Escape ] ) {
Exit();
}
}
protected override void OnUpdateFrame( FrameEventArgs e ) {
CheckKeyboardInput( e );
}
protected override void OnResize( EventArgs e ) {
base.OnResize( e );
GL.Viewport( ClientRectangle.X , ClientRectangle.Y , ClientRectangle.Width , ClientRectangle.Height );
Matrix4 projection = Matrix4.CreatePerspectiveFieldOfView( ( float )Math.PI / 4 , Width / ( float )Height , 0.1f , 1000.0f );
GL.MatrixMode( MatrixMode.Projection );
GL.LoadMatrix( ref projection );
}
}
}
Anyone know what the deal is here? Because I am stumped.
EDIT:
I just noticed that if I use a different detecting method (SphereInFrustum) everything seems to work perfectly; nothing is clipped prematurely. Here is my new renderloop:
foreach( Voxel voxel in World.Voxels ) {
if( voxel.IsVisible() ) {
if( GameCamera.Frustum.SphereInFrustum(
voxel.Location.X , voxel.Location.Y , voxel.Location.Z , 1.5f ) ) {
voxel.Render( GameCamera );
numberOfVoxelsRendered++;
}
}
}
As you can see I am passing in a sphere radius of 1.5f, and basically pretending all my Voxels are spheres. It works, and there is no premature clipping, however I want to use my VoxelWithinFrustum method. Can anyone spot if I did something wrong with that method? Or if I am using the parameters incorrectly?
