Introduction
In previous sections of this series I mentioned better culling techniques. I wasn't going to touch upon any of these until after the series but it continued to eat away at me until I finally decided to do so. The result was hours and hours of trial and error and a lot of mistakes along the way. Thanks to community contribution in the AppHub forums I was able to get many of my questions answered or at least get pointed in the right direction. I ran into several issues along the way, but eventually came up with a working solution.
I began by simply projecting the view frustrum onto an imaginary plane. In our case, this is going to by the "Y" value of the quadtree's position which marks the lowest point in the terrain. I quickly realized this was more difficult than it seems as I had to account for different rotations and positions of the camera. I had to determine exactly which points where above the plane and which weren't and do so for both the near and far planes. This resulting in an extremely nasty large code block of if-else statements. Depending on the rotation of the camera, this could also result in a 2D shape with anywhere from 3 to 6 sides. But it worked... kind of.
I quickly found that when the camera wasn't facing down, the terrain didn't LOD or render correctly because the point where we start our LOD wasn't visible. In reality this could easily be fixed by specifying a different position for the LOD (such as a player position if the camera was behind the player). So I adjusted my shape by determining the direction of the camera and exactly where a ray cast by the camera (projected on to the plane) would intersect the resulting shape, and I used that position as the point of LOD. Everything normally in the view frustrum rendered perectly...but then I realized there was another issue.
The resulting shape was being determined by finding all the points in which the view frustrum intersect the terrain. If the camera is high in the air and looking at a downward angle, this shape could be a fair distance away from the camera location. The problem now is that, if there were any mountains between the camera location and the resulting intersection they would not be rendered or LODed.
So, I set out to one final round of projecting the view frustrum. This time, I projected the view frustrum as I had before, but I then took the camera position into account. A check is performed to see if the camera is inside the resulting shape (i.e. the camera is looking down or up). If it is, then nothing more needs to be done. If not, it figures out where it needs to place the camera point. It could be replacing the nearest point or it could be inserted between two points depending on whether that would place the closest existing point inside of the shape or not.
Volumes vs Shapes
So, why go through all of this trouble? The answer is pretty simple. Volumes are much more expensive to check intersections against than shapes. Since our view shape is an arbitrary polygon that could contain different point combinations (though always convex), the check isn't quite as simple. The Separating Axis Theorem must be used and this requires multiple axis to be generated for each shape and points to be projected. In my case I am pre-calculating a lot of the axis on each shape so it doesn't have to be done for every intersection test.
It should be noted that when testing I was frustrated by an actual lower performance, however I finally discovered that much of the performance hit was being caused by the debugger. I ran in release mode and toggled between volume culling and shape culling. The result was a > 50% performance increase! So where do we begin? Well, this is going to require several changes to the code we've already written, plus an enormous amount of extra code, so be sure to following along carefully. At the end of this section I'll post a download for the current solution in case you're having trouble or I missed something.
I should also tell you that a lot of trial and error went into developing my projection code. There are likely many places it can be optimized. Additionally, though I attempted to account for every possible camera pitch and rotation, I did not test with any rotations so if you do and find bugs, let me know and I'll work them out. Also note that I'm providing you with the complete code for each object so you may need to modify the Namespaces for it to work properly with your project. I'm now using Tutorial1.Terrain. Replace this with your namespace as necessary.
Bounding Rectangles
We're going to start by creating our bounding rectangle object. You will see some errors after creating this object because it depends on additional objects that we'll create shortly, for now just ignore them. I've chosen to use structs for all of my bounding shapes and done some trickery to avoid creating arrays and garbage collection. It results in more code but not reference type objects. The same will be true for the other objects you'll see later. I don't think I need to explain what a rectangle is, but I will explain how I'm structuring my shapes. All of the shapes are comprised of Vector2 points. These points represent the X and Z coordinates of each point. The Y coordinate is irrelevant since we only care about 2D space when checking intersections. The points are specified in clockwise order. The Axis and Scalars are used for intersection tests.
Open up your Terrain project and add a new folder called Culling. Inside that folder create a new class called Rectangle and replace it with the following code:
using System;
using Microsoft.Xna.Framework;
namespace Tutorial1.Terrain.Culling
{
/// <summary>
/// Axis-Aligned Rectangle
/// </summary>
public struct Rectangle
{
public Vector2 Point1 { get; internal set; }
public Vector2 Point2 { get; internal set; }
public Vector2 Point3 { get; internal set; }
public Vector2 Point4 { get; internal set; }
public int Count { get { return 4; } }
public Vector2 Axis1 { get; internal set; }
public Vector2 Axis2 { get; internal set; }
public int A1Min, A1Max, A2Min, A2Max;
/// <summary>
/// Get the point at the supplied index.
/// </summary>
/// <param name="index"></param>
/// <returns></returns>
public Vector2 this[int index]
{
get
{
switch (index)
{
case 0:
return Point1;
case 1:
return Point2;
case 2:
return Point3;
case 3:
return Point4;
default:
throw new IndexOutOfRangeException("Index Out of Range: Index must be in the range of 0 to 3.");
}
}
}
private Rectangle(Vector2 minimalPoint, Vector2 maximalPoint)
: this()
{
Point1 = minimalPoint;
Point3 = maximalPoint;
Point2 = new Vector2(Point3.X, Point1.Y);
Point4 = new Vector2(Point1.X, Point3.Y);
}
public static Rectangle FromPoints(Vector2 minimalPoint, Vector2 maximalPoint)
{
var shape = new Rectangle(minimalPoint, maximalPoint);
shape.BuildAxis();
return shape;
}
public Vector2 GetAxis(int index)
{
switch (index)
{
case 0: return Axis1;
case 1: return Axis2;
default: throw new ArgumentException("Index must be in the range of 0 to 2");
}
}
public bool Intersects(ViewClipShape shape)
{
return Intersection.Intersects(ref this, ref shape);
}
private void BuildAxis()
{
//Only generating 2 axis since the other axis are parallel.
Axis1 = Point1 - Point4;
Axis2 = Point1 - Point2;
SetScalars();
}
private void SetScalars()
{
Intersection.Project(Axis1, ref this, out A1Min, out A1Max);
Intersection.Project(Axis2, ref this, out A2Min, out A2Max);
}
}
}
Utils Class
There are several calculations we'll need to be doing later, so we're going to use a static Utils class to perform those. Go ahead and add another new class to the Culling folder and call it Utils. Replace it with the following code:
using System;
using Microsoft.Xna.Framework;
namespace Tutorial1.Terrain.Culling
{
public static class Utils
{
public static Vector3 GetDirectionVector(Vector3 point1, Vector3 point2)
{
return new Vector3(point2.X - point1.X, point2.Y - point1.Y, point2.Z - point1.Z);
}
public static Vector3 LinePointFromKnownY(Vector3 point1, Vector3 point2, float y)
{
var direction = GetDirectionVector(point1, point2);
//parameteric equation
//Point1.Y - (direction.Y * t) = knownY
//solve for T
//so --> Point1.Y - knownY = direction.Y * t
//t = (Point1.Y - knownY) / direction.Y
//
//unknown X: Point1.X - (direction.X * t)
//unknown Z: Point1.Z - (direction.Z * t)
var t = (point1.Y - y) / direction.Y;
var x = point1.X - (direction.X * t);
var z = point1.Z - (direction.Z * t);
return new Vector3(x, y, z);
}
public static Vector3 GetLineCenter(Vector3 point1, Vector3 point2)
{
var direction = GetDirectionVector(point1, point2);
var y = point1.Y - (direction.Y * 0.5f);
var x = point1.X - (direction.X * 0.5f);
var z = point1.Z - (direction.Z * 0.5f);
return new Vector3(x, y, z);
}
public static Vector2 GetEdgeNormal(Vector2 point1, Vector2 point2)
{
var edge = point1 - point2;
edge.Normalize();
return new Vector2(edge.Y, -edge.X);
}
public static float LineAngle(Vector2 v1, Vector2 v2)
{
return MathHelper.ToDegrees((float)Math.Abs(Math.Atan2(v2.Y - v1.Y, v2.X - v1.X)));
}
}
}
PlaneIntersectType
We'll be using an enum to determine how our near and far clipping planes intersect the imaginary ground plane. Add a new class to the Culling folder and call it PlaneIntersectType. Replace it with the following code:
namespace Tutorial1.Terrain.Culling
{
public enum PlaneIntersectType
{
Above = 0,
Below = 1,
Intersects = 2
}
}
ClipPlane
The ClipPlane object represents the near and far planes of the view frustrum. These will be used extensively later for our projection. Add a new class to your Culling folder and call it ClipPlane. Replace it with the following code:
using Microsoft.Xna.Framework;
namespace Tutorial1.Terrain.Culling
{
public struct ClipPlane
{
public Vector3 Point1 { get; private set; }
public Vector3 Point2 { get; private set; }
public Vector3 Point3 { get; private set; }
public Vector3 Point4 { get; private set; }
private ClipPlane(Vector3 point1, Vector3 point2, Vector3 point3, Vector3 point4)
: this()
{
Point1 = point1;
Point2 = point2;
Point3 = point3;
Point4 = point4;
}
public static ClipPlane FromPoints(Vector3 point1, Vector3 point2, Vector3 point3, Vector3 point4)
{
return new ClipPlane(point1, point2, point3, point4);
}
public PlaneIntersectType PlaneInsersection(float targetY)
{
if (Point1.Y > targetY && Point2.Y > targetY && Point3.Y > targetY && Point4.Y > targetY)
return PlaneIntersectType.Above;
if (Point1.Y < targetY && Point2.Y < targetY && Point3.Y < targetY && Point4.Y < targetY)
return PlaneIntersectType.Below;
return PlaneIntersectType.Intersects;
}
}
}
ViewClipShape
The ViewClipShape represents our view frustrum as it has been projected onto the imaginary plane. This is the object we will be using to test for intersections against our Rectangle that we created above. Add a new class to your Culling folder and call it ViewClipShape. Replace it with the following code:
using System;
using Microsoft.Xna.Framework;
namespace Tutorial1.Terrain.Culling
{
public struct ViewClipShape
{
public Vector2 Point1 { get; private set; }
public Vector2 Point2 { get; private set; }
public Vector2 Point3 { get; private set; }
public Vector2 Point4 { get; private set; }
public Vector2 Point5 { get; private set; }
public Vector2 Point6 { get; private set; }
private Vector2 Axis1 { get; set; }
private Vector2 Axis2 { get; set; }
private Vector2 Axis3 { get; set; }
private Vector2 Axis4 { get; set; }
private Vector2 Axis5 { get; set; }
private Vector2 Axis6 { get; set; }
public Vector2 ViewPoint { get; internal set; }
public int A1Min, A2Min, A3Min, A4Min, A5Min, A6Min;
public int A1Max, A2Max, A3Max, A4Max, A5Max, A6Max;
public int Count { get; private set; }
public Vector2 this[int index]
{
get
{
switch (index)
{
case 0:
return Point1;
case 1:
return Point2;
case 2:
return Point3;
case 3:
return Point4;
case 4:
return Point5;
case 5:
return Point6;
default:
throw new ArgumentException("Max number of points exceeded.");
}
}
}
private ViewClipShape(Vector2 point1, Vector2 point2, Vector2 point3)
: this()
{
Point1 = point1;
Point2 = point2;
Point3 = point3;
Count = 3;
}
private ViewClipShape(Vector2 point1, Vector2 point2, Vector2 point3, Vector2 point4)
: this(point1, point2, point3)
{
Point4 = point4;
Count = 4;
}
private ViewClipShape(Vector2 point1, Vector2 point2, Vector2 point3, Vector2 point4, Vector2 point5)
: this(point1, point2, point3, point4)
{
Point5 = point5;
Count = 5;
}
private ViewClipShape(Vector2 point1, Vector2 point2, Vector2 point3, Vector2 point4, Vector2 point5, Vector2 point6)
: this(point1, point2, point3, point4, point5)
{
Point6 = point6;
Count = 6;
}
public static ViewClipShape FromPoints(Vector2 point1, Vector2 point2, Vector2 point3)
{
var shape = new ViewClipShape(point1, point2, point3);
shape.BuildAxis();
return shape;
}
public static ViewClipShape FromPoints(Vector2 point1, Vector2 point2, Vector2 point3, Vector2 point4)
{
var shape = new ViewClipShape(point1, point2, point3, point4);
shape.BuildAxis();
return shape;
}
public static ViewClipShape FromPoints(Vector2 point1, Vector2 point2, Vector2 point3, Vector2 point4, Vector2 point5)
{
var shape = new ViewClipShape(point1, point2, point3, point4, point5);
shape.BuildAxis();
return shape;
}
public static ViewClipShape FromPoints(Vector2 point1, Vector2 point2, Vector2 point3, Vector2 point4, Vector2 point5, Vector2 point6)
{
var shape = new ViewClipShape(point1, point2, point3, point4, point5, point6);
shape.BuildAxis();
return shape;
}
public Vector2 GetAxis(int index)
{
if (index < 0 || index > (Count - 1))
throw new ArgumentException("Index must be in the range of 0 to " + (Count - 1));
switch (index)
{
case 0: return Axis1;
case 1: return Axis2;
case 2: return Axis3;
case 3: return Axis4;
case 4: return Axis5;
default: return Axis6;
}
}
private void SetMaxScalar(int index, int value)
{
switch (index)
{
case 0:
A1Max = value;
break;
case 1:
A2Max = value;
break;
case 2:
A3Max = value;
break;
case 3:
A4Max = value;
break;
case 4:
A5Max = value;
break;
case 5:
A6Max = value;
break;
}
}
private void SetMinScalar(int index, int value)
{
switch (index)
{
case 0:
A1Min = value;
break;
case 1:
A2Min = value;
break;
case 2:
A3Min = value;
break;
case 3:
A4Min = value;
break;
case 4:
A5Min = value;
break;
case 5:
A6Min = value;
break;
}
}
public int GetMinScalar(int index)
{
switch(index)
{
case 0: return A1Min;
case 1: return A2Min;
case 2: return A3Min;
case 3: return A4Min;
case 4: return A5Min;
case 5: return A6Min;
}
return -1;
}
public int GetMaxScalar(int index)
{
switch (index)
{
case 0: return A1Max;
case 1: return A2Max;
case 2: return A3Max;
case 3: return A4Max;
case 4: return A5Max;
case 5: return A6Max;
}
return -1;
}
private void BuildAxis()
{
Axis1 = Point1 - Point2;
Axis2 = Point2 - Point3;
switch (Count)
{
case 3:
Axis3 = Point3 - Point1;
break;
case 4:
Axis3 = Point3 - Point4;
Axis4 = Point4 - Point1;
break;
case 5:
Axis3 = Point3 - Point4;
Axis4 = Point4 - Point5;
Axis5 = Point5 - Point1;
break;
case 6:
Axis3 = Point3 - Point4;
Axis4 = Point4 - Point5;
Axis5 = Point5 - Point6;
Axis6 = Point6 - Point1;
break;
}
SetScalars();
}
private void SetScalars()
{
for(var i = 0; i < Count; i++)
{
int min, max;
var axis = GetAxis(i);
Intersection.Project(axis, ref this, out min, out max);
SetMinScalar(i, min);
SetMaxScalar(i, max);
}
}
public Vector2 GetViewPoint(Vector3 cameraPosition)
{
//Move the camera position to the same Y axis as the ViewClipShape
var p1 = new Vector2(cameraPosition.X, cameraPosition.Z);
if (ContainsPoint(p1))
return p1;
//Find the center position of the clip shape
var p2xmin = Point1.X;
var p2xmax = p2xmin;
var p2ymin = Point1.Y;
var p2ymax = p2ymin;
//Closest points to camera location
var p3 = Point1;
var dist1 = Vector2.Distance(p1, Point1);
var dist2 = dist1;
var p4 = p3;
for (var i = 1; i < Count; i++)
{
var current = this[i];
var dist = Vector2.Distance(p1, current);
if (dist <= dist1)
p3 = current;
else if (dist <= dist2)
p4 = current;
if (current.X <= p2xmin)
p2xmin = current.X;
else
if (current.X > p2xmax)
p2xmax = current.X;
if (current.Y <= p2ymin)
p2ymin = current.Y;
else
if (current.Y > p2ymax)
p2ymax = current.Y;
}
//Point 2 is the center of the shape.
//Line 1 is the camera point to the center of the clip shape
var p2 = new Vector2((p2xmin + p2xmax) / 2, (p2ymin + p2ymax) / 2);
//Line 2 is a line drawn between the closest two points to the camera point
//These are denoted by cp1 and cp2.
var numerator = (p4.X - p3.X)*(p1.Y - p3.Y) - (p4.Y - p3.Y) * (p1.X - p3.X);
var denominator = (p4.Y - p3.Y) * (p2.X - p1.X) - (p4.X - p3.X) * (p2.Y - p1.Y);
var ua = numerator / denominator;
var x = p1.X + ua * (p2.X - p1.X);
var y = p1.Y + ua * (p2.Y - p1.Y);
return new Vector2(x, y);
}
public void ReplacePoint(int pointIndex, Vector2 newPoint)
{
switch(pointIndex)
{
case 0:
Point1 = newPoint;
break;
case 1:
Point2 = newPoint;
break;
case 2:
Point3 = newPoint;
break;
case 3:
Point4 = newPoint;
break;
case 4:
Point5 = newPoint;
break;
case 5:
Point6 = newPoint;
break;
}
//rebuild the axis
BuildAxis();
}
public void InsertPointAt(int pointIndex, Vector2 newPoint)
{
if (pointIndex < 0 || pointIndex > 4)
return;
switch(pointIndex)
{
case 0:
Point6 = Point5;
Point5 = Point4;
Point4 = Point3;
Point3 = Point2;
Point2 = Point1;
Point1 = newPoint;
break;
case 1:
Point6 = Point5;
Point5 = Point4;
Point4 = Point3;
Point3 = Point2;
Point2 = newPoint;
break;
case 2:
Point6 = Point5;
Point5 = Point4;
Point4 = Point3;
Point3 = newPoint;
break;
case 3:
Point6 = Point5;
Point5 = Point4;
Point4 = newPoint;
break;
case 4:
Point6 = Point5;
Point5 = newPoint;
break;
case 5:
Point6 = newPoint;
break;
}
Count++;
//rebuild the axis
BuildAxis();
}
/// <summary>
/// Adapted from http://paulbourke.net/geometry/insidepoly/
/// </summary>
/// <param name="point"></param>
/// <returns></returns>
public bool ContainsPoint(Vector2 point)
{
var counter = 0;
int i;
Vector2 p2;
var p1 = this[0];
for (i=1;i<=Count;i++)
{
p2 = this[i % Count];
if (point.Y > Math.Min(p1.Y, p2.Y))
{
if (point.Y <= Math.Max(p1.Y, p2.Y))
{
if (point.X <= Math.Max(p1.X, p2.X))
{
if (p1.Y != p2.Y)
{
float xinters = (point.Y - p1.Y) * (p2.X - p1.X) / (p2.Y - p1.Y) + p1.X;
if (p1.X == p2.X || point.X <= xinters)
counter++;
}
}
}
}
p1 = p2;
}
return counter % 2 != 0;
}
}
}
Intersection Testing
We need code to check for intersections between our shapes so I've created an Intersection class. Add a new class to your Culling folder and call it Intersection. Replace it with the following code:
using Microsoft.Xna.Framework;
namespace Tutorial1.Terrain.Culling
{
internal class Intersection
{
internal static bool Intersects(ref Rectangle shape1, ref ViewClipShape shape2)
{
int min, max;
//Check against rectangle axis
Project(shape1.Axis1, ref shape2, out min, out max);
if (shape1.A1Min > max || shape1.A1Max < min)
return false;
Project(shape1.Axis2, ref shape2, out min, out max);
if (shape1.A2Min > max || shape1.A2Max < min)
return false;
//Check against the viewclipshape axis - thre are at least 3
for (var i = 0; i < shape2.Count; i++)
{
Project(shape2.GetAxis(i), ref shape1, out min, out max);
if (shape2.GetMinScalar(i) > max || shape2.GetMaxScalar(i) < min)
return false;
}
return true;
}
internal static void Project(Vector2 axis, ref Rectangle shape, out int min, out int max)
{
min = GenerateScalar(shape.Point1, ref axis);
max = min;
var current = GenerateScalar(shape.Point2, ref axis);
if (current <= min)
min = current;
else
if (current > max)
max = current;
current = GenerateScalar(shape.Point3, ref axis);
if (current <= min)
min = current;
else
if (current > max)
max = current;
current = GenerateScalar(shape.Point4, ref axis);
if (current <= min)
min = current;
else
if (current > max)
max = current;
}
internal static void Project(Vector2 axis, ref ViewClipShape shape, out int min, out int max)
{
min = GenerateScalar(shape.Point1, ref axis);
max = min;
var current = GenerateScalar(shape.Point2, ref axis);
if (current <= min)
min = current;
else
if (current > max)
max = current;
current = GenerateScalar(shape.Point3, ref axis);
if (current <= min)
min = current;
else
if (current > max)
max = current;
if (shape.Count < 4) return;
current = GenerateScalar(shape.Point4, ref axis);
if (current <= min)
min = current;
else if (current > max)
max = current;
if (shape.Count < 5) return;
current = GenerateScalar(shape.Point5, ref axis);
if (current <= min)
min = current;
else if (current > max)
max = current;
if (shape.Count < 6) return;
current = GenerateScalar(shape.Point6, ref axis);
if (current <= min)
min = current;
else if (current > max)
max = current;
}
/// <summary>
/// Generate scalar value for axis projection - based on George Clingerman's sample
/// </summary>
/// <param name="point">Point to project</param>
/// <param name="axis">Target Axis</param>
/// <returns>Generated Scalar</returns>
internal static int GenerateScalar(Vector2 point, ref Vector2 axis)
{
var numerator = (point.X * axis.X) + (point.Y * axis.Y);
var denominator = (axis.X * axis.X) + (axis.Y * axis.Y);
var divisionResult = numerator / denominator;
return (int)((axis.X * (divisionResult * axis.X)) + (axis.Y * (divisionResult * axis.Y)));
}
}
}
Clipping Frustrum
Last but certainly not least, we have our ClippingFrustrum object. This will be used by our QuadTree to project the bounding frustrum onto our imaginary plane and create our 2D ViewClipShape. This is the class that contains the bulk of the code. It's fairly heavy and probably could be optimized. Though it contains a lot of code, the majority of it are conditional if-else statements so very little of it actually executes at any given iteration. This is important as this is executed every time the terrain is updated. Go ahead and create a new class in the Culling folder and call it ClippingFrustrum. Replace it with the following code:
using System;
using Microsoft.Xna.Framework;
namespace Tutorial1.Terrain.Culling
{
public struct ClippingFrustrum
{
public ClipPlane FarPlane { get; private set; }
public ClipPlane NearPlane { get; private set; }
public Vector3 CameraPosition { get; private set; }
private ClippingFrustrum(Vector3[] frustrumCorners, Vector3 cameraPosition)
: this()
{
FarPlane = ClipPlane.FromPoints(frustrumCorners[4], frustrumCorners[5], frustrumCorners[6], frustrumCorners[7]);
NearPlane = ClipPlane.FromPoints(frustrumCorners[0], frustrumCorners[1], frustrumCorners[2], frustrumCorners[3]);
CameraPosition = cameraPosition;
}
public static ClippingFrustrum FromFrustrumCorners(Vector3[] corners, Vector3 cameraPosition)
{
if (corners.Length != 8)
throw new ArgumentException("Corners must be of length 8");
return new ClippingFrustrum(corners, cameraPosition);
}
/// <summary>
/// Project the clipping frustrum onto the target Y position
/// </summary>
/// <param name="targetY">Y position of the target plane</param>
/// <returns>Four Sided Polygon with corners representing the X and Z positions</returns>
public ViewClipShape ProjectToTargetY(float targetY)
{
var nearIntersectType = NearPlane.PlaneInsersection(targetY);
var farIntersectType = FarPlane.PlaneInsersection(targetY);
ViewClipShape shape;
//Target plane not in view frustrum. Setting a single point at the near plane center.
if (nearIntersectType == farIntersectType
&& nearIntersectType != PlaneIntersectType.Intersects
&& farIntersectType != PlaneIntersectType.Intersects)
{
var singlePoint = new Vector2(CameraPosition.X, CameraPosition.Z);
shape = ViewClipShape.FromPoints(singlePoint, singlePoint, singlePoint);
shape.ViewPoint = singlePoint;
return shape;
}
//Target plane slices between clipping planes with no intersection.
if (nearIntersectType != farIntersectType
&& nearIntersectType != PlaneIntersectType.Intersects
&& farIntersectType != PlaneIntersectType.Intersects)
{
shape = FromNoIntersection(NearPlane, FarPlane, targetY);
}
else if (farIntersectType == PlaneIntersectType.Intersects)
{
//Far clipping plane intersects target plane
shape = FromKnownIntersection(FarPlane, NearPlane, targetY);
}
else
{
//Near clipping plane intersects target plane
shape = FromKnownIntersection(NearPlane, FarPlane, targetY);
}
//Now we need to determine whether we need to insert the camera position
var cam = new Vector2(CameraPosition.X, CameraPosition.Z);
if (!shape.ContainsPoint(cam))
{
AddCameraPosition(ref shape);
}
shape.ViewPoint = cam;
return shape;
}
private void AddCameraPosition(ref ViewClipShape inputShape)
{
var cam = new Vector2(CameraPosition.X, CameraPosition.Z);
var closest = 0;
var closeDist = Vector2.Distance(cam, inputShape.Point1);
//find closest point
for (var i = 1; i < inputShape.Count; i++)
{
var dist = Vector2.Distance(cam, inputShape[i]);
if (dist <= closeDist)
closest = i;
}
//Find the adjacent points
int adj1, adj2;
if (closest == 0)
{
adj1 = inputShape.Count - 1;
adj2 = closest + 1;
}
else if (closest == inputShape.Count - 1)
{
adj1 = closest - 1;
adj2 = 0;
}
else
{
adj1 = closest - 1;
adj2 = closest + 1;
}
var angle1 = Utils.LineAngle(inputShape[closest] - cam, inputShape[adj1] - cam);
var angle2 = Utils.LineAngle(inputShape[closest] - cam, inputShape[adj2] - cam);
if (angle1 < 90 && angle2 < 90)
{
//point will be inside the shape, replace it with camera position
inputShape.ReplacePoint(closest, cam);
}
else
{
//use the angles to determine what points it is between
if (angle1 >= 90)
{
inputShape.InsertPointAt(closest, cam);
}
else
{
inputShape.InsertPointAt(adj2, cam);
}
}
}
/// <summary>
/// Ground does not intersect either plane, but lies between them.
/// </summary>
/// <param name="plane1"></param>
/// <param name="plane2"></param>
/// <param name="targetY"></param>
/// <returns></returns>
private static ViewClipShape FromNoIntersection(ClipPlane plane1, ClipPlane plane2, float targetY)
{
var intersect1 = Utils.LinePointFromKnownY(plane1.Point1, plane2.Point1, targetY);
var intersect2 = Utils.LinePointFromKnownY(plane1.Point2, plane2.Point2, targetY);
var intersect3 = Utils.LinePointFromKnownY(plane1.Point3, plane2.Point3, targetY);
var intersect4 = Utils.LinePointFromKnownY(plane1.Point4, plane2.Point4, targetY);
var point1 = new Vector2(intersect1.X, intersect1.Z);
var point2 = new Vector2(intersect2.X, intersect2.Z);
var point3 = new Vector2(intersect3.X, intersect3.Z);
var point4 = new Vector2(intersect4.X, intersect4.Z);
return ViewClipShape.FromPoints(point1, point2, point3, point4);
}
/// <summary>
/// Use when one plane is known to be intersecting
/// </summary>
/// <param name="plane1">The plane known to be intersecting</param>
/// <param name="plane2">The second plane</param>
/// <param name="targetY">The target Y position of the ground plane</param>
/// <returns></returns>
private static ViewClipShape FromKnownIntersection(ClipPlane plane1, ClipPlane plane2, float targetY)
{
Vector3 intersect1, intersect2, intersect3, intersect4 = Vector3.Zero;
Vector3 intersect5 = Vector3.Zero, intersect6 = Vector3.Zero;
int pointCount;
if (plane1.Point1.Y > targetY) //point 1 is above the plane
{
if (plane1.Point2.Y > targetY) //point 2 is above the plane
{
if (plane1.Point3.Y > targetY) //point 3 is above the plane, point 4 has to be below - points 1, 2 & 3 above
{
intersect1 = Utils.LinePointFromKnownY(plane1.Point1, plane1.Point4, targetY);
intersect2 = Utils.LinePointFromKnownY(plane1.Point3, plane1.Point4, targetY);
pointCount = 3;
#region PLANE 2 PROJECTION
/* PLANE 2 PROJECTION */
if (plane2.Point4.Y > targetY) //plane 2 is completely above the line
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point4, plane1.Point4, targetY);
}
else //point 4 of plane 2 is below the line
{
if (plane2.Point2.Y < targetY) //point 2 of plane 2 is below the line - Down 1, 2, 3 & 4
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point3, plane1.Point3, targetY);
intersect4 = Utils.LinePointFromKnownY(plane2.Point2, plane1.Point1, targetY);
intersect5 = Utils.LinePointFromKnownY(plane2.Point1, plane1.Point1, targetY);
pointCount = 5;
}
else //point 2 of plane 2 is above the line
{
if (plane2.Point3.Y > targetY) //plane 2 point 3 is above the line
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point3, plane2.Point4, targetY);
}
else //plane 2 point 3 is below the line
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point3, plane1.Point3, targetY);
intersect4 = Utils.LinePointFromKnownY(plane2.Point2, plane2.Point3, targetY);
pointCount = 4;
}
if (plane2.Point1.Y > targetY) //plane 2 point 1 is above the line
{
if (pointCount == 4)
intersect5 = Utils.LinePointFromKnownY(plane2.Point1, plane2.Point4, targetY);
else
intersect4 = Utils.LinePointFromKnownY(plane2.Point1, plane2.Point4, targetY);
pointCount++;
}
else //plane 2 point 1 is below the line
{
if (pointCount == 4)
{
intersect5 = Utils.LinePointFromKnownY(plane2.Point2, plane2.Point1, targetY);
intersect6 = Utils.LinePointFromKnownY(plane2.Point1, plane1.Point1, targetY);
}
else
{
intersect4 = Utils.LinePointFromKnownY(plane2.Point2, plane2.Point1, targetY);
intersect5 = Utils.LinePointFromKnownY(plane2.Point1, plane1.Point1, targetY);
}
pointCount += 2;
}
}
}
/* END PLANE 2 PROJECTION */
#endregion
}
else //point 3 is below the target plane
{
if (plane1.Point4.Y > targetY) //point 4 is above the target plane - points 1, 2 & 4 above
{
intersect1 = Utils.LinePointFromKnownY(plane1.Point4, plane1.Point3, targetY);
intersect2 = Utils.LinePointFromKnownY(plane1.Point2, plane1.Point3, targetY);
pointCount = 3;
#region PLANE 2 PROJECTION
/* PLANE 2 PROJECTION */
if (plane2.Point3.Y > targetY) //plane 2 is completely above the line
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point3, plane1.Point3, targetY);
}
else //point 4 of plane 2 is below the line
{
if (plane2.Point1.Y < targetY) //point 2 of plane 2 is below the line - Down 1, 2, 3 & 4
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point2, plane1.Point2, targetY);
intersect4 = Utils.LinePointFromKnownY(plane2.Point1, plane1.Point4, targetY);
intersect5 = Utils.LinePointFromKnownY(plane2.Point4, plane1.Point4, targetY);
pointCount = 5;
}
else //point 2 of plane 2 is above the line
{
if (plane2.Point2.Y > targetY) //plane 2 point 3 is above the line
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point2, plane2.Point3, targetY);
}
else //plane 2 point 3 is below the line
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point2, plane1.Point2, targetY);
intersect4 = Utils.LinePointFromKnownY(plane2.Point1, plane2.Point2, targetY);
pointCount = 4;
}
if (plane2.Point4.Y > targetY) //plane 2 point 1 is above the line
{
if (pointCount == 4)
intersect5 = Utils.LinePointFromKnownY(plane2.Point4, plane2.Point3, targetY);
else
intersect4 = Utils.LinePointFromKnownY(plane2.Point4, plane2.Point3, targetY);
pointCount++;
}
else //plane 2 point 1 is below the line
{
if (pointCount == 4)
{
intersect5 = Utils.LinePointFromKnownY(plane2.Point1, plane2.Point4, targetY);
intersect6 = Utils.LinePointFromKnownY(plane2.Point4, plane1.Point4, targetY);
}
else
{
intersect4 = Utils.LinePointFromKnownY(plane2.Point1, plane2.Point4, targetY);
intersect5 = Utils.LinePointFromKnownY(plane2.Point4, plane1.Point4, targetY);
}
pointCount += 2;
}
}
}
/* END PLANE 2 PROJECTION */
#endregion
}
else //points 3 and 4 are both below the target plane - points 1 & 2 are above
{
intersect1 = Utils.LinePointFromKnownY(plane1.Point1, plane1.Point4, targetY);
intersect2 = Utils.LinePointFromKnownY(plane1.Point2, plane1.Point3, targetY);
#region PLANE 2 PROJECTION
if (plane2.Point2.Y > targetY) //point2 is above
{
if (plane2.Point3.Y > targetY) //point3 is above
{
if (plane2.Point4.Y > targetY) //All four points are above
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point3, plane1.Point3, targetY);
intersect4 = Utils.LinePointFromKnownY(plane2.Point4, plane1.Point4, targetY);
pointCount = 4;
}
else //point4 is below - point1, point2 and point3 are above
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point3, plane1.Point3, targetY);
intersect4 = Utils.LinePointFromKnownY(plane2.Point3, plane2.Point4, targetY);
intersect5 = Utils.LinePointFromKnownY(plane2.Point1, plane2.Point4, targetY);
pointCount = 5;
}
}
else //point3 is below
{
if (plane2.Point4.Y > targetY) //point1, point2, and point4 are above
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point2, plane2.Point3, targetY);
intersect4 = Utils.LinePointFromKnownY(plane2.Point4, plane2.Point3, targetY);
intersect5 = Utils.LinePointFromKnownY(plane2.Point4, plane1.Point4, targetY);
pointCount = 5;
}
else //point4 is below
{
if (plane2.Point1.Y > targetY) //point1 and point2 are above
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point2, plane2.Point3, targetY);
intersect4 = Utils.LinePointFromKnownY(plane2.Point1, plane2.Point4, targetY);
pointCount = 4;
}
else //only point2 is above
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point2, plane2.Point3, targetY);
intersect4 = Utils.LinePointFromKnownY(plane2.Point2, plane2.Point1, targetY);
intersect5 = Utils.LinePointFromKnownY(plane2.Point1, plane1.Point1, targetY);
pointCount = 5;
}
}
}
}
else //Point2 is below
{
if (plane2.Point1.Y > targetY) //only point1 is above
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point2, plane1.Point2, targetY);
intersect4 = Utils.LinePointFromKnownY(plane2.Point1, plane2.Point2, targetY);
intersect5 = Utils.LinePointFromKnownY(plane2.Point1, plane2.Point4, targetY);
pointCount = 5;
}
else //all points are below
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point2, plane1.Point2, targetY);
intersect4 = Utils.LinePointFromKnownY(plane2.Point1, plane1.Point1, targetY);
pointCount = 4;
}
}
#endregion
}
}
}
else //point 2 is below the target plane
{
if (plane1.Point4.Y < targetY) //point 4 is also below the target plane, point 3 must be also - point 1 is above
{
intersect1 = Utils.LinePointFromKnownY(plane1.Point1, plane1.Point4, targetY);
intersect2 = Utils.LinePointFromKnownY(plane1.Point1, plane1.Point2, targetY);
pointCount = 3;
#region PLANE 2 PROJECTION
if (plane2.Point1.Y < targetY) //All of plane 2 is below
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point1, plane1.Point1, targetY);
}
else //point1 is above
{
if (plane2.Point3.Y > targetY) //All of plane 2 is above
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point2, plane1.Point2, targetY);
intersect4 = Utils.LinePointFromKnownY(plane2.Point3, plane1.Point3, targetY);
intersect5 = Utils.LinePointFromKnownY(plane2.Point4, plane1.Point4, targetY);
pointCount = 5;
}
else //point3 is below
{
if (plane2.Point2.Y > targetY) //point2 is above
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point2, plane1.Point2, targetY);
intersect4 = Utils.LinePointFromKnownY(plane2.Point2, plane2.Point3, targetY);
pointCount = 4;
}
else //point2 is below
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point1, plane2.Point2, targetY);
pointCount = 3;
}
if (plane2.Point4.Y > targetY) //point4 is above
{
if (pointCount == 4)
{
intersect5 = Utils.LinePointFromKnownY(plane2.Point4, plane2.Point3, targetY);
intersect6 = Utils.LinePointFromKnownY(plane2.Point4, plane1.Point4, targetY);
pointCount = 6;
}
else //point2 was below
{
intersect4 = Utils.LinePointFromKnownY(plane2.Point4, plane2.Point3, targetY);
intersect5 = Utils.LinePointFromKnownY(plane2.Point4, plane1.Point4, targetY);
pointCount = 5;
}
}
else //point4 is below
{
if (pointCount == 4)
{
intersect5 = Utils.LinePointFromKnownY(plane2.Point1, plane2.Point4, targetY);
pointCount = 5;
}
else //point2 was below, only point1 is above
{
intersect4 = Utils.LinePointFromKnownY(plane2.Point1, plane2.Point4, targetY);
pointCount = 4;
}
}
}
}
#endregion
}
else //point 4 is above the target plane
{
if (plane1.Point3.Y < targetY) //point 3 is below the target plane - 1 & 4 are above
{
intersect1 = Utils.LinePointFromKnownY(plane1.Point4, plane1.Point3, targetY);
intersect2 = Utils.LinePointFromKnownY(plane1.Point1, plane1.Point2, targetY);
#region PLANE 2 PROJECTION
if (plane2.Point1.Y > targetY) //Point1 is above
{
if (plane2.Point2.Y > targetY) //Point2 is above
{
if (plane2.Point3.Y > targetY) //All four points are above
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point2, plane1.Point2, targetY);
intersect4 = Utils.LinePointFromKnownY(plane2.Point3, plane1.Point3, targetY);
pointCount = 4;
}
else //Point3 is below - Point4, Point1 and Point2 are above
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point2, plane1.Point2, targetY);
intersect4 = Utils.LinePointFromKnownY(plane2.Point2, plane2.Point3, targetY);
intersect5 = Utils.LinePointFromKnownY(plane2.Point4, plane2.Point3, targetY);
pointCount = 5;
}
}
else //Point2 is below
{
if (plane2.Point3.Y > targetY) //Point4, Point1, and Point3 are above
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point1, plane2.Point2, targetY);
intersect4 = Utils.LinePointFromKnownY(plane2.Point3, plane2.Point2, targetY);
intersect5 = Utils.LinePointFromKnownY(plane2.Point3, plane1.Point3, targetY);
pointCount = 5;
}
else //Point3 is below
{
if (plane2.Point4.Y > targetY) //Point4 and Point1 are above
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point1, plane2.Point2, targetY);
intersect4 = Utils.LinePointFromKnownY(plane2.Point4, plane2.Point3, targetY);
pointCount = 4;
}
else //only Point1 is above
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point1, plane2.Point2, targetY);
intersect4 = Utils.LinePointFromKnownY(plane2.Point1, plane2.Point4, targetY);
intersect5 = Utils.LinePointFromKnownY(plane2.Point4, plane1.Point4, targetY);
pointCount = 5;
}
}
}
}
else //Point1 is below
{
if (plane2.Point4.Y > targetY) //only Point4 is above
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point1, plane1.Point1, targetY);
intersect4 = Utils.LinePointFromKnownY(plane2.Point4, plane2.Point1, targetY);
intersect5 = Utils.LinePointFromKnownY(plane2.Point4, plane2.Point3, targetY);
pointCount = 5;
}
else //all points are below
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point1, plane1.Point1, targetY);
intersect4 = Utils.LinePointFromKnownY(plane2.Point4, plane1.Point4, targetY);
pointCount = 4;
}
}
#endregion
}
else //points 1, 4 & 3 are above
{
intersect1 = Utils.LinePointFromKnownY(plane1.Point3, plane1.Point2, targetY);
intersect2 = Utils.LinePointFromKnownY(plane1.Point1, plane1.Point2, targetY);
pointCount = 3;
#region PLANE 2 PROJECTION
/* PLANE 2 PROJECTION */
if (plane2.Point2.Y > targetY) //plane 2 is completely above the line
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point2, plane1.Point2, targetY);
}
else //point 4 of plane 2 is below the line
{
if (plane2.Point4.Y < targetY) //point 2 of plane 2 is below the line - Down 1, 2, 3 & 4
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point1, plane1.Point1, targetY);
intersect4 = Utils.LinePointFromKnownY(plane2.Point4, plane1.Point3, targetY);
intersect5 = Utils.LinePointFromKnownY(plane2.Point3, plane1.Point3, targetY);
pointCount = 5;
}
else //point 2 of plane 2 is above the line
{
if (plane2.Point1.Y > targetY) //plane 2 point 3 is above the line
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point1, plane2.Point2, targetY);
}
else //plane 2 point 3 is below the line
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point1, plane1.Point1, targetY);
intersect4 = Utils.LinePointFromKnownY(plane2.Point4, plane2.Point1, targetY);
pointCount = 4;
}
if (plane2.Point3.Y > targetY) //plane 2 point 1 is above the line
{
if (pointCount == 4)
intersect5 = Utils.LinePointFromKnownY(plane2.Point3, plane2.Point2, targetY);
else
intersect4 = Utils.LinePointFromKnownY(plane2.Point3, plane2.Point2, targetY);
pointCount++;
}
else //plane 2 point 1 is below the line
{
if (pointCount == 4)
{
intersect5 = Utils.LinePointFromKnownY(plane2.Point4, plane2.Point3, targetY);
intersect6 = Utils.LinePointFromKnownY(plane2.Point3, plane1.Point3, targetY);
}
else
{
intersect4 = Utils.LinePointFromKnownY(plane2.Point4, plane2.Point3, targetY);
intersect5 = Utils.LinePointFromKnownY(plane2.Point3, plane1.Point3, targetY);
}
pointCount += 2;
}
}
}
/* END PLANE 2 PROJECTION */
#endregion
}
}
}
}
else //point 1 is below the target plane
{
if (plane1.Point2.Y > targetY) //point 2 is above the plane
{
if (plane1.Point4.Y > targetY) //points 2 and 4 are above the plane so point 3 must be as well Up 2, 3 & 4
{
intersect1 = Utils.LinePointFromKnownY(plane1.Point2, plane1.Point1, targetY);
intersect2 = Utils.LinePointFromKnownY(plane1.Point4, plane1.Point1, targetY);
pointCount = 3;
#region PLANE 2 PROJECTION
/* PLANE 2 PROJECTION */
if (plane2.Point1.Y > targetY) //plane 2 is completely above the line
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point1, plane1.Point1, targetY);
}
else //point 4 of plane 2 is below the line
{
if (plane2.Point3.Y < targetY) //point 2 of plane 2 is below the line - Down 1, 2, 3 & 4
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point4, plane1.Point4, targetY);
intersect4 = Utils.LinePointFromKnownY(plane2.Point3, plane1.Point2, targetY);
intersect5 = Utils.LinePointFromKnownY(plane2.Point2, plane1.Point2, targetY);
pointCount = 5;
}
else //point 2 of plane 2 is above the line
{
if (plane2.Point4.Y > targetY) //plane 2 point 3 is above the line
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point4, plane2.Point1, targetY);
}
else //plane 2 point 3 is below the line
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point4, plane1.Point4, targetY);
intersect4 = Utils.LinePointFromKnownY(plane2.Point3, plane2.Point4, targetY);
pointCount = 4;
}
if (plane2.Point2.Y > targetY) //plane 2 point 1 is above the line
{
if (pointCount == 4)
intersect5 = Utils.LinePointFromKnownY(plane2.Point2, plane2.Point1, targetY);
else
intersect4 = Utils.LinePointFromKnownY(plane2.Point2, plane2.Point1, targetY);
pointCount++;
}
else //plane 2 point 1 is below the line
{
if (pointCount == 4)
{
intersect5 = Utils.LinePointFromKnownY(plane2.Point3, plane2.Point2, targetY);
intersect6 = Utils.LinePointFromKnownY(plane2.Point2, plane1.Point2, targetY);
}
else
{
intersect4 = Utils.LinePointFromKnownY(plane2.Point3, plane2.Point2, targetY);
intersect5 = Utils.LinePointFromKnownY(plane2.Point2, plane1.Point2, targetY);
}
pointCount += 2;
}
}
}
/* END PLANE 2 PROJECTION */
#endregion
}
else //point 4 is below the plane
{
if (plane1.Point3.Y > targetY) //point 3 is above the plane - Up 2 & 3
{
intersect1 = Utils.LinePointFromKnownY(plane1.Point2, plane1.Point1, targetY);
intersect2 = Utils.LinePointFromKnownY(plane1.Point3, plane1.Point4, targetY);
#region PLANE 2 PROJECTION
if (plane2.Point3.Y > targetY) //Point3 is above
{
if (plane2.Point4.Y > targetY) //Point4 is above
{
if (plane2.Point1.Y > targetY) //All four points are above
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point4, plane1.Point4, targetY);
intersect4 = Utils.LinePointFromKnownY(plane2.Point1, plane1.Point1, targetY);
pointCount = 4;
}
else //Point1 is below - Point2, Point3 and Point4 are above
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point4, plane1.Point4, targetY);
intersect4 = Utils.LinePointFromKnownY(plane2.Point4, plane2.Point1, targetY);
intersect5 = Utils.LinePointFromKnownY(plane2.Point2, plane2.Point1, targetY);
pointCount = 5;
}
}
else //Point4 is below
{
if (plane2.Point1.Y > targetY) //Point2, Point3, and Point1 are above
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point3, plane2.Point4, targetY);
intersect4 = Utils.LinePointFromKnownY(plane2.Point1, plane2.Point4, targetY);
intersect5 = Utils.LinePointFromKnownY(plane2.Point1, plane1.Point1, targetY);
pointCount = 5;
}
else //Point1 is below
{
if (plane2.Point2.Y > targetY) //Point2 and Point3 are above
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point3, plane2.Point4, targetY);
intersect4 = Utils.LinePointFromKnownY(plane2.Point2, plane2.Point1, targetY);
pointCount = 4;
}
else //only Point3 is above
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point3, plane2.Point4, targetY);
intersect4 = Utils.LinePointFromKnownY(plane2.Point3, plane2.Point2, targetY);
intersect5 = Utils.LinePointFromKnownY(plane2.Point2, plane1.Point2, targetY);
pointCount = 5;
}
}
}
}
else //Point3 is below
{
if (plane2.Point2.Y > targetY) //only Point2 is above
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point3, plane1.Point3, targetY);
intersect4 = Utils.LinePointFromKnownY(plane2.Point2, plane2.Point3, targetY);
intersect5 = Utils.LinePointFromKnownY(plane2.Point2, plane2.Point1, targetY);
pointCount = 5;
}
else //all points are below
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point3, plane1.Point3, targetY);
intersect4 = Utils.LinePointFromKnownY(plane2.Point2, plane1.Point2, targetY);
pointCount = 4;
}
}
#endregion
}
else //only point 2 is above the plane - Up 2
{
intersect1 = Utils.LinePointFromKnownY(plane1.Point2, plane1.Point3, targetY);
intersect2 = Utils.LinePointFromKnownY(plane1.Point2, plane1.Point3, targetY);
pointCount = 3;
#region PLANE 2 PROJECTION
if (plane2.Point2.Y < targetY) //All of plane 2 is below
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point2, plane1.Point2, targetY);
}
else //Point2 is above
{
if (plane2.Point4.Y > targetY) //All of plane 2 is above
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point3, plane1.Point3, targetY);
intersect4 = Utils.LinePointFromKnownY(plane2.Point4, plane1.Point4, targetY);
intersect5 = Utils.LinePointFromKnownY(plane2.Point1, plane1.Point1, targetY);
pointCount = 5;
}
else //Point4 is below
{
if (plane2.Point3.Y > targetY) //Point3 is above
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point3, plane1.Point3, targetY);
intersect4 = Utils.LinePointFromKnownY(plane2.Point3, plane2.Point4, targetY);
pointCount = 4;
}
else //Point3 is below
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point2, plane2.Point3, targetY);
pointCount = 3;
}
if (plane2.Point1.Y > targetY) //Point1 is above
{
if (pointCount == 4)
{
intersect5 = Utils.LinePointFromKnownY(plane2.Point1, plane2.Point4, targetY);
intersect6 = Utils.LinePointFromKnownY(plane2.Point1, plane1.Point1, targetY);
pointCount = 6;
}
else //Point3 was below
{
intersect4 = Utils.LinePointFromKnownY(plane2.Point1, plane2.Point4, targetY);
intersect5 = Utils.LinePointFromKnownY(plane2.Point1, plane1.Point1, targetY);
pointCount = 5;
}
}
else //Point1 is below
{
if (pointCount == 4)
{
intersect5 = Utils.LinePointFromKnownY(plane2.Point2, plane2.Point1, targetY);
pointCount = 5;
}
else //Point3 was below, only Point2 is above
{
intersect4 = Utils.LinePointFromKnownY(plane2.Point2, plane2.Point1, targetY);
pointCount = 4;
}
}
}
}
#endregion
}
}
}
else //point 2 is below the line
{
if (plane1.Point3.Y > targetY) //point 3 is above the line
{
if (plane1.Point4.Y > targetY) //points 3 and 4 are above the line - Up 3 & 4
{
intersect1 = Utils.LinePointFromKnownY(plane1.Point3, plane1.Point2, targetY);
intersect2 = Utils.LinePointFromKnownY(plane1.Point4, plane1.Point1, targetY);
#region PLANE 2 PROJECTION
if (plane2.Point4.Y > targetY) //Point4 is above
{
if (plane2.Point1.Y > targetY) //Point1 is above
{
if (plane2.Point2.Y > targetY) //All four points are above
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point1, plane1.Point1, targetY);
intersect4 = Utils.LinePointFromKnownY(plane2.Point2, plane1.Point2, targetY);
pointCount = 4;
}
else //Point2 is below - Point3, Point4 and Point1 are above
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point1, plane1.Point1, targetY);
intersect4 = Utils.LinePointFromKnownY(plane2.Point1, plane2.Point2, targetY);
intersect5 = Utils.LinePointFromKnownY(plane2.Point3, plane2.Point2, targetY);
pointCount = 5;
}
}
else //Point1 is below
{
if (plane2.Point2.Y > targetY) //Point3, Point4, and Point2 are above
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point4, plane2.Point1, targetY);
intersect4 = Utils.LinePointFromKnownY(plane2.Point2, plane2.Point1, targetY);
intersect5 = Utils.LinePointFromKnownY(plane2.Point2, plane1.Point2, targetY);
pointCount = 5;
}
else //Point2 is below
{
if (plane2.Point3.Y > targetY) //Point3 and Point4 are above
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point4, plane2.Point1, targetY);
intersect4 = Utils.LinePointFromKnownY(plane2.Point3, plane2.Point2, targetY);
pointCount = 4;
}
else //only Point4 is above
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point4, plane2.Point1, targetY);
intersect4 = Utils.LinePointFromKnownY(plane2.Point4, plane2.Point3, targetY);
intersect5 = Utils.LinePointFromKnownY(plane2.Point3, plane1.Point3, targetY);
pointCount = 5;
}
}
}
}
else //Point4 is below
{
if (plane2.Point3.Y > targetY) //only Point3 is above
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point4, plane1.Point4, targetY);
intersect4 = Utils.LinePointFromKnownY(plane2.Point3, plane2.Point4, targetY);
intersect5 = Utils.LinePointFromKnownY(plane2.Point3, plane2.Point2, targetY);
pointCount = 5;
}
else //all points are below
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point4, plane1.Point4, targetY);
intersect4 = Utils.LinePointFromKnownY(plane2.Point3, plane1.Point3, targetY);
pointCount = 4;
}
}
#endregion
}
else //only point 3 is above the line - Up 3
{
intersect1 = Utils.LinePointFromKnownY(plane1.Point3, plane1.Point2, targetY);
intersect2 = Utils.LinePointFromKnownY(plane1.Point3, plane1.Point4, targetY);
pointCount = 3;
#region PLANE 2 PROJECTION
if (plane2.Point3.Y < targetY) //All of plane 2 is below
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point3, plane1.Point3, targetY);
}
else //Point3 is above
{
if (plane2.Point1.Y > targetY) //All of plane 2 is above
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point4, plane1.Point4, targetY);
intersect4 = Utils.LinePointFromKnownY(plane2.Point1, plane1.Point1, targetY);
intersect5 = Utils.LinePointFromKnownY(plane2.Point2, plane1.Point2, targetY);
pointCount = 5;
}
else //Point1 is below
{
if (plane2.Point4.Y > targetY) //Point4 is above
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point4, plane1.Point4, targetY);
intersect4 = Utils.LinePointFromKnownY(plane2.Point4, plane2.Point1, targetY);
pointCount = 4;
}
else //Point4 is below
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point3, plane2.Point4, targetY);
pointCount = 3;
}
if (plane2.Point2.Y > targetY) //Point2 is above
{
if (pointCount == 4)
{
intersect5 = Utils.LinePointFromKnownY(plane2.Point2, plane2.Point1, targetY);
intersect6 = Utils.LinePointFromKnownY(plane2.Point2, plane1.Point2, targetY);
pointCount = 6;
}
else //Point4 was below
{
intersect4 = Utils.LinePointFromKnownY(plane2.Point2, plane2.Point1, targetY);
intersect5 = Utils.LinePointFromKnownY(plane2.Point2, plane1.Point2, targetY);
pointCount = 5;
}
}
else //Point2 is below
{
if (pointCount == 4)
{
intersect5 = Utils.LinePointFromKnownY(plane2.Point3, plane2.Point2, targetY);
pointCount = 5;
}
else //Point4 was below, only Point3 is above
{
intersect4 = Utils.LinePointFromKnownY(plane2.Point3, plane2.Point2, targetY);
pointCount = 4;
}
}
}
}
#endregion
}
}
else //points 1, 2 & 3 are all below, Up 4
{
intersect1 = Utils.LinePointFromKnownY(plane1.Point4, plane1.Point3, targetY);
intersect2 = Utils.LinePointFromKnownY(plane1.Point4, plane1.Point1, targetY);
pointCount = 3;
#region PLANE 2 PROJECTION
if (plane2.Point4.Y < targetY) //All of plane 2 is below
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point4, plane1.Point4, targetY);
}
else //Point4 is above
{
if (plane2.Point2.Y > targetY) //All of plane 2 is above
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point1, plane1.Point1, targetY);
intersect4 = Utils.LinePointFromKnownY(plane2.Point2, plane1.Point2, targetY);
intersect5 = Utils.LinePointFromKnownY(plane2.Point3, plane1.Point3, targetY);
pointCount = 5;
}
else //Point2 is below
{
if (plane2.Point1.Y > targetY) //Point1 is above
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point1, plane1.Point1, targetY);
intersect4 = Utils.LinePointFromKnownY(plane2.Point1, plane2.Point2, targetY);
pointCount = 4;
}
else //Point1 is below
{
intersect3 = Utils.LinePointFromKnownY(plane2.Point4, plane2.Point1, targetY);
pointCount = 3;
}
if (plane2.Point3.Y > targetY) //Point3 is above
{
if (pointCount == 4)
{
intersect5 = Utils.LinePointFromKnownY(plane2.Point3, plane2.Point2, targetY);
intersect6 = Utils.LinePointFromKnownY(plane2.Point3, plane1.Point3, targetY);
pointCount = 6;
}
else //Point1 was below
{
intersect4 = Utils.LinePointFromKnownY(plane2.Point3, plane2.Point2, targetY);
intersect5 = Utils.LinePointFromKnownY(plane2.Point3, plane1.Point3, targetY);
pointCount = 5;
}
}
else //Point3 is below
{
if (pointCount == 4)
{
intersect5 = Utils.LinePointFromKnownY(plane2.Point4, plane2.Point3, targetY);
pointCount = 5;
}
else //Point1 was below, only Point4 is above
{
intersect4 = Utils.LinePointFromKnownY(plane2.Point4, plane2.Point3, targetY);
pointCount = 4;
}
}
}
}
#endregion
}
}
}
var point1 = new Vector2(intersect1.X, intersect1.Z);
var point2 = new Vector2(intersect2.X, intersect2.Z);
var point3 = new Vector2(intersect3.X, intersect3.Z);
var point4 = new Vector2(intersect4.X, intersect4.Z);
var point5 = new Vector2(intersect5.X, intersect5.Z);
var point6 = new Vector2(intersect6.X, intersect6.Z);
switch (pointCount)
{
case 3:
return ViewClipShape.FromPoints(point1, point2, point3);
case 4:
return ViewClipShape.FromPoints(point1, point2, point3, point4);
case 5:
return ViewClipShape.FromPoints(point1, point2, point3, point4, point5);
default:
return ViewClipShape.FromPoints(point1, point2, point3, point4, point5, point6);
}
}
}
}
Putting it all Together
Now with all of our culling objects created, all we have left to do is implement the new mechanism into our QuadTree. The first thing we need to do is replace the bounding box we were using in our QuadNode class with our new bounding rectangle. Open your QuadNode.cs file, locate the BoundingBox definition and replace it with the following:
public Culling.Rectangle Bounds { get; private set; }
We're specifying Culling.Rectangle here to avoid confusion with XNA's built in Rectangle class. Next, remove the Contains method that accepts a BoundingFrustrum as a parameter. We want to leave our original Contains method that accepts a point because we'll need it later. Modify your other contains method to look like this:
/// <summary>
/// Returns true if the QuadNode contains a specific point.
/// </summary>
/// <param name="point">Vector2 representing the target point</param>
/// <returns>True if point is contained in the node's bounding rectangle</returns>
public bool Contains(Vector2 point)
{
return (point.X >= Bounds.Point1.X && point.X <= Bounds.Point3.X
&& point.Y >= Bounds.Point1.Y && point.Y <= Bounds.Point3.Y);
}
Now, navigate to the IsInView property and replace it with the following:
public bool IsInView
{
get
{
return Bounds.Intersects(_parentTree.ClipShape);
}
}
Next we need to modify our DeepestNodeWithPoint method. This method current accepts a point as a Vector3. We want to change this so it only accepts a Vector2. Replace the current DeepestNodeWithPoint method with the following:
/// <summary>
/// Get a reference to the deepest node that contains a point.
/// </summary>
/// <param name="point">Vector2 representing the target point</param>
/// <returns>Deepest quad node containing target point</returns>
public QuadNode DeepestNodeWithPoint(Vector2 point)
{
//If the point isn't in this node, return null
if (!Contains(point))
return null;
if (HasChildren)
{
if (ChildTopLeft.Contains(point))
return ChildTopLeft.DeepestNodeWithPoint(point);
if (ChildTopRight.Contains(point))
return ChildTopRight.DeepestNodeWithPoint(point);
if (ChildBottomLeft.Contains(point))
return ChildBottomLeft.DeepestNodeWithPoint(point);
//It's contained in this node and not in the first 3
//children, so has to be in 4th child. No need to check.
return ChildBottomRight.DeepestNodeWithPoint(point);
}
//No children, return this QuadNode
return this;
}
And finally, we need to update the constructor of our QuadNode so it constructs our bounding rectangle instead of the bounding box. Remove the code from the QuadNode constructor that creates the bounding box and replace it with the following code that initializes our bounding rectangle:
var tl = new Vector2(_parentTree.Vertices[VertexTopLeft.Index].Position.X, _parentTree.Vertices[VertexTopLeft.Index].Position.Z);
var br = new Vector2(_parentTree.Vertices[VertexBottomRight.Index].Position.X, _parentTree.Vertices[VertexBottomRight.Index].Position.Z);
Bounds = Culling.Rectangle.FromPoints(tl, br);
The rest of the changes will be made in the QuadTree class. If you haven't already done so, save the changes you've made to QuadNode.cs and open QuadTree.cs. We're going to start by adding a couple of new members to the QuadTree class. We need one member to hold our ViewClipShape for intersection tests, and we're going to add another internal member, an array that holds 8 Vector3 values. We could do this without having the array as a member but then the array would have to be created every update and would generate garbage. The 8 elements of the array represent the near and far corners of the view frustrum. Add the following two members to your QuadTree class:
public ViewClipShape ClipShape;
internal Vector3[] VFCorners = new Vector3[8];
We're going to go ahead and keep our BoundingFrustrum variable so we don't have to reinitialize it every update since we'll still be using it to construct our clipping shape. The only changes we have left to make are to our Update method. Go ahead and navigate to the QuadTree's Update method. First, remove the if statement that checks for camera movement. Next we're going to add the code to initialize our ViewClipShape. Your entire Update method should now look like this:
public void Update(GameTime gameTime)
{
ViewFrustrum.Matrix = View*Projection;
Effect.View = View;
Effect.Projection = Projection;
//Corners 0-3 = near plane clockwise, Corners 4-7 = far plane clockwise
ViewFrustrum.GetCorners(VFCorners);
var clip = ClippingFrustrum.FromFrustrumCorners(VFCorners, CameraPosition);
ClipShape = clip.ProjectToTargetY(_position.Y);
_lastCameraPosition = _cameraPosition;
IndexCount = 0;
_rootNode.Merge();
_rootNode.EnforceMinimumDepth();
_activeNode = _rootNode.DeepestNodeWithPoint(ClipShape.ViewPoint);
if (_activeNode != null)
{
_activeNode.Split();
}
_rootNode.SetActiveVertices();
_buffers.UpdateIndexBuffer(Indices, IndexCount);
_buffers.SwapBuffer();
}
And that's all there is to it. Our terrain is now setup to perform culling using 2D Shapes instead of clipping volumes. In my Game class's Update statement I've also added more keys. Our current keymappings are:
Esc = Exit
W = Toggle Wireframe
D = Toggle Drawing (Draw & Update Terrain or Update Only - for testing Update performance)
Arrow Keys = Move Camera Forward, Back, Left, Right
A = Pitch camera up
Z = Pitch camera down
PgUp = Move camera up
PgDown = Move camera down
C = turn Culling on and off
I've uploaded the updated solution including everything in this part of the series. I strongly encourage you to use it as we will be building the last parts of the series off of this solution. Click Here to download the complete solution through Part 7.
<< Go back to Part 6 Terrain Series Table of Contents Go to Part 8 (Coming Soon) >>