Mesh Clipping

Up until now I’d used the Clipper library  to clip my meshes to a given landscape tile. Typically this would be regions of trees, rivers, roads etc – any object which was going to transit between two or more tiles would need to be clipped into its tile-bound chunks.

This library is an excellent resource but has the following limitations

  • It deals with int values only
  • It eliminates colinear vertexes
  • It doesnt have any IOC features for constructing new vertexes – they are just simple two dimensional points, or IOC features for accessing existing vertexes, which all have to be converted to 2D points for passing into the algorithm.

I wanted to have a better solution for my meshes so built one myself – with the limitation that it clips an indexed set of vertexes against a bounding rectangle. They key part of the algorithm determines, for any triangle in a mesh, whether

  1. It is wholly external to the bounding rectangle
  2. It is wholle encompassed by the bounding rectangle. (I ignore the case where the bounding rectangle is contained in the triangle)
  3. It has one vertex outside the bounding rectangle
  4. It has two vertexes outside the bounding rectangle

These five cases are the only ones that can exist. Additionally there is the special case that a corner of the bounding rectangle may be encompassed by the triangle.

These cases are shown below with the dotted lines indicating the new geometry required by the clipping algorithm

TriangleClippingCases

The code to deal with these cases and a set of unit tests that test for them are

using System;

using System.Collections.Generic;

using SharpDX;

namespace RTC5.Extensions

{

/// <summary>

/// Clip a mesh to a regular rectangular polygon

/// </summary>

public class SimpleClipper

{

/// <summary>

/// Clip the passed list to the passed boundary

/// </summary>

/// <typeparam name="T">The type of vertex class or struct that this is clipping</typeparam>

/// <param name="boundaryBottom">Bottom of the clip boundary</param>

/// <param name="boundaryLeft">Left of the clip boundary</param>

/// <param name="boundaryRight">Right of the clip boundary</param>

/// <param name="boundaryTop">Top of the clip boundary</param>

/// <param name="meshIndexes">List of indexes into the meshVertexes that form triangles</param>

/// <param name="meshVertexes">The list of vertexes to be clipped</param>

/// <param name="clippedVertexes">List of the vertexes clipped</param>

/// <param name="clippedIndexes">List of the indexes generated which render the clippedVertexes as triangles</param>

/// <param name="positionAccessor">When called, must return the Vector3 position of the meshVertex at the passed index position</param>

/// <param name="vertexConstructor">When called, must return a new instance of T located at the passed Position, which will be within a triangle formed by the int[3] indexes into the meshVertex list</param>

/// <returns></returns>

public void ClipMeshToBoundary<T>(

float boundaryBottom,

float boundaryLeft,

float boundaryTop,

float boundaryRight,

List<T> meshVertexes,

List<int> meshIndexes,

Func<int, Vector3> positionAccessor,

Func<int[], Vector3, T> vertexConstructor,

out List<T> clippedVertexes,

out List<int> clippedIndexes

)

{

// all the locations we've added to the output list. We only deal with the X and Z coordinates. Storing a list here eliminates the need for the T to have

// equivilency operators.

List<Vector2> appliedLocations = new List<Vector2>();

clippedVertexes = new List<T>();

clippedIndexes = new List<int>();

Vector3 bottomLeft = new Vector3(boundaryLeft, 0, boundaryBottom);

Vector3 bottomRight = new Vector3(boundaryRight, 0, boundaryBottom);

Vector3 topLeft = new Vector3(boundaryLeft, 0, boundaryTop);

Vector3 topRight = new Vector3(boundaryRight, 0, boundaryTop);

// Basic method here is to walk each of the Vertexes indicated by the indexes, in the order defined in the triangles and test each vertex. Add them to the

// AppliedLocations if the fall within the boundary, if they dont already exist.

for (int indexCount = 0; indexCount < meshIndexes.Count - 1; indexCount += 3)

{

int index1 = meshIndexes[indexCount];

int index2 = meshIndexes[indexCount + 1];

int index3 = meshIndexes[indexCount + 2];

Vector3 point1 = positionAccessor(index1);

Vector3 point2 = positionAccessor(index2);

Vector3 point3 = positionAccessor(index3);

bool point1Inside = Geometry.Contains(point1, boundaryBottom, boundaryLeft, boundaryTop, boundaryRight);

bool point2Inside = Geometry.Contains(point2, boundaryBottom, boundaryLeft, boundaryTop, boundaryRight);

bool point3Inside = Geometry.Contains(point3, boundaryBottom, boundaryLeft, boundaryTop, boundaryRight);

List<int> additionalTriangleIndexes = new List<int>(4);

// If whole triangle lies outside the box, move on.

if (!point1Inside &&

!point2Inside &&

!point3Inside)

{

continue;

}

// If the whole triangle is inside the box, add them and move on.

if (point1Inside &&

point2Inside &&

point3Inside)

{

clippedIndexes.Add(addPoint<T>(point1, meshVertexes[index1], appliedLocations, clippedVertexes));

clippedIndexes.Add(addPoint<T>(point2, meshVertexes[index2], appliedLocations, clippedVertexes));

clippedIndexes.Add(addPoint<T>(point3, meshVertexes[index3], appliedLocations, clippedVertexes));

continue;

}

// Interrogate the triangle and return a list of indexes where the first one is known to be in the boundary.

List<int> triangleIndexes = createIndexListInWindingOrder(index1, index2, index3, point1Inside, point2Inside, point3Inside);

// List of vertex indexes that apply to this particualr triangle - this will include indexes to newly created geometry.

List<int> disruptedTriangleIndexes = new List<int>();

int pointsOutsideCount = 0;

Vector3 cornerInTriangle = new Vector3();

bool cornerEmbedded = false;

// Special case - the corner of the tile is within the triangle.

if (Geometry.PointInTriangleBarycentricMethod(point1, point2, point3, bottomLeft))

{

cornerInTriangle = bottomLeft;

cornerEmbedded = true;

}

else if (Geometry.PointInTriangleBarycentricMethod(point1, point2, point3, topLeft))

{

cornerInTriangle = topLeft;

cornerEmbedded = true;

}

else if (Geometry.PointInTriangleBarycentricMethod(point1, point2, point3, topRight))

{

cornerInTriangle = topRight;

cornerEmbedded = true;

}

else if (Geometry.PointInTriangleBarycentricMethod(point1, point2, point3, topLeft))

{

cornerInTriangle = topLeft;

cornerEmbedded = true;

}



// Walk the index stack

for (int indexPointer = 0; indexPointer < triangleIndexes.Count; indexPointer++)

{

// Deal with circularity

int thisIndex = triangleIndexes[indexPointer];

int nextIndex = triangleIndexes[0];

if (indexPointer < triangleIndexes.Count - 1)

{

nextIndex = triangleIndexes[indexPointer + 1];

}

Vector3 thisPosition = positionAccessor(thisIndex);

Vector3 nextPosition = positionAccessor(nextIndex);

// Case 1 : This vertex and the next one are within the boundaries

if (Geometry.Contains(thisPosition, boundaryBottom, boundaryLeft, boundaryTop, boundaryRight) &&

Geometry.Contains(nextPosition, boundaryBottom, boundaryLeft, boundaryTop, boundaryRight))

{

disruptedTriangleIndexes.Add(addPoint<T>(thisPosition, meshVertexes[thisIndex], appliedLocations, clippedVertexes));

}

// Case 2 : This vertex is in the boundary but the next one isnt

else if (

Geometry.Contains(thisPosition, boundaryBottom, boundaryLeft, boundaryTop, boundaryRight) &&

!Geometry.Contains(nextPosition, boundaryBottom, boundaryLeft, boundaryTop, boundaryRight))

{

pointsOutsideCount++;

disruptedTriangleIndexes.Add(addPoint<T>(thisPosition, meshVertexes[thisIndex], appliedLocations, clippedVertexes));

// Manufacture the exit vertex

Nullable<Vector3> exitPoint = Geometry.DetermineIntersectWithBoundary(bottomLeft, bottomRight, topLeft, topRight, thisPosition, nextPosition);

if (!exitPoint.HasValue)

{

throw new Exception("Unexpected non-intersection with hull");

}

T exitVertex = vertexConstructor(new int[] { index1, index2, index3 }, exitPoint.Value);

disruptedTriangleIndexes.Add(addPoint<T>(exitPoint.Value, exitVertex, appliedLocations, clippedVertexes));

// If we embed a corner, we need to add a further point.

if (cornerEmbedded)

{

T cornerVertex = vertexConstructor(new int[] { index1, index2, index3 }, cornerInTriangle);

disruptedTriangleIndexes.Add(addPoint<T>(cornerInTriangle, cornerVertex, appliedLocations, clippedVertexes));

}

}

// Case 3 : This vertex is outside, and the next vertex is inside

else if (

!Geometry.Contains(thisPosition, boundaryBottom, boundaryLeft, boundaryTop, boundaryRight) &&

Geometry.Contains(nextPosition, boundaryBottom, boundaryLeft, boundaryTop, boundaryRight))

{

pointsOutsideCount++;

// We have already had an exit vertex created by the exiting line (i.e. the prior case 2)

// Manufacture a reentrant vertex

Nullable<Vector3> entryPoint = Geometry.DetermineIntersectWithBoundary(bottomLeft, bottomRight, topLeft, topRight, thisPosition, nextPosition);

if (!entryPoint.HasValue)

{

throw new Exception("Unexpected non-intersection with hull");

}

T entryVertex = vertexConstructor(new int[] { index1, index2, index3 }, entryPoint.Value);

disruptedTriangleIndexes.Add(addPoint<T>(entryPoint.Value, entryVertex, appliedLocations, clippedVertexes));

}

}



// Add the newly created geometry indexes to the output list as a set of triangle indexes.

if (disruptedTriangleIndexes.Count == 3)

{

clippedIndexes.AddRange(disruptedTriangleIndexes);

}

else if (disruptedTriangleIndexes.Count == 4)

{

clippedIndexes.Add(disruptedTriangleIndexes[0]);

clippedIndexes.Add(disruptedTriangleIndexes[1]);

clippedIndexes.Add(disruptedTriangleIndexes[2]);

clippedIndexes.Add(disruptedTriangleIndexes[2]);

clippedIndexes.Add(disruptedTriangleIndexes[3]);

clippedIndexes.Add(disruptedTriangleIndexes[0]);

}

else if (disruptedTriangleIndexes.Count == 5)

{

clippedIndexes.Add(disruptedTriangleIndexes[0]);

clippedIndexes.Add(disruptedTriangleIndexes[1]);

clippedIndexes.Add(disruptedTriangleIndexes[2]);

clippedIndexes.Add(disruptedTriangleIndexes[2]);

clippedIndexes.Add(disruptedTriangleIndexes[3]);

clippedIndexes.Add(disruptedTriangleIndexes[4]);

clippedIndexes.Add(disruptedTriangleIndexes[0]);

clippedIndexes.Add(disruptedTriangleIndexes[2]);

clippedIndexes.Add(disruptedTriangleIndexes[4]);

}





}

}

/// <summary>

/// Create a stack of indxes in winding order, with the first one known to be inside the triangle

/// </summary>

/// <param name="index1"></param>

/// <param name="index2"></param>

/// <param name="index3"></param>

/// <param name="point1Inside"></param>

/// <param name="point2Inside"></param>

/// <param name="point3Inside"></param>

/// <returns></returns>

private List<int> createIndexListInWindingOrder(

int index1,

int index2,

int index3,

bool point1Inside,

bool point2Inside,

bool point3Inside)

{

// Indexes in winding order. The first index is known to be within the boundary.

List<int> indexes = new List<int>();

if (point1Inside)

{

indexes.Add(index1);

indexes.Add(index2);

indexes.Add(index3);

}

else if (point2Inside)

{

indexes.Add(index2);

indexes.Add(index3);

indexes.Add(index1);

}

else if (point3Inside)

{

indexes.Add(index3);

indexes.Add(index1);

indexes.Add(index2);

}

else

{

throw new Exception("Unexpected state - no indexes inside boundary");

}

return indexes;

}

/// <summary>

/// Add the passed vertex to the output list. If the vertex is already in the output list, this doesnt add it again.

/// </summary>

/// <typeparam name="T"></typeparam>

/// <param name="point1">The Position of the vertex</param>

/// <param name="vertex">The vertex to add</param>

/// <param name="appliedLocations">The list of 2D Position that are alreayd in the output list</param>

/// <param name="clippedVertexes">The output list to add the vertex to</param>

/// <returns>The index to the newly added or existing vertex</returns>

private int addPoint<T>(Vector3 point1, T vertex, List<Vector2> appliedLocations, List<T> clippedVertexes)

{

Vector2 appliedLocation = new Vector2(point1.X, point1.Z);

if (!appliedLocations.Contains(appliedLocation))

{

appliedLocations.Add(appliedLocation);

clippedVertexes.Add(vertex);

}

return appliedLocations.IndexOf(appliedLocation);

}

}

}

Unit tests showing the calling syntax are;

using System;

using Microsoft.VisualStudio.TestTools.UnitTesting;

using RTC5.Extensions;

using SharpDX;

using System.Collections.Generic;

using System.Linq;



namespace RTC5.Extensions.Tests

{

[TestClass]

public class SimpleClipper_Tests

{

/// <summary>

/// top point of triangle outside

/// </summary>

[TestMethod]

public void SimpleClipper_ClipToBoundary_Vector3_MultiTriangleMesh()

{

List<Vector3> mesh = new List<Vector3>();

mesh.Add(new Vector3(5, 0, 5));

mesh.Add(new Vector3(5, 0, 8));

mesh.Add(new Vector3(8, 0, 5));

mesh.Add(new Vector3(8, 0, 8));

mesh.Add(new Vector3(12, 0, 5));

mesh.Add(new Vector3(12, 0, 8));

List<int> indexes = new List<int>();

indexes.AddRange(new int[] { 0, 1, 3 });

indexes.AddRange(new int[] { 0, 3, 2 });

indexes.AddRange(new int[] { 2, 3, 5 });

indexes.AddRange(new int[] { 2, 5, 4 });

List<Vector3> clippedVertexes;

List<int> clippedIndexes;

SimpleClipper clipper = new SimpleClipper();

clipper.ClipMeshToBoundary<Vector3>(0, 0, 10, 10, mesh, indexes,

positionAccessor: (int index) => mesh[index],

vertexConstructor: (int[] triangleIndexes, Vector3 position) => createInterpolatedPoint(

mesh[triangleIndexes[0]],

mesh[triangleIndexes[1]],

mesh[triangleIndexes[2]],

position

),

clippedVertexes: out clippedVertexes,

clippedIndexes: out clippedIndexes);

Assert.IsTrue(clippedVertexes.Count == 7);

Assert.IsTrue(clippedIndexes.Count == 15);

Assert.IsTrue(clippedVertexes[clippedIndexes[0]] == new Vector3(5, 0, 5));

Assert.IsTrue(clippedVertexes[clippedIndexes[1]] == new Vector3(5, 0, 8));

Assert.IsTrue(clippedVertexes[clippedIndexes[2]] == new Vector3(8, 0, 8));

Assert.IsTrue(clippedVertexes[clippedIndexes[3]] == new Vector3(5, 0, 5));

Assert.IsTrue(clippedVertexes[clippedIndexes[4]] == new Vector3(8, 0, 8));

Assert.IsTrue(clippedVertexes[clippedIndexes[5]] == new Vector3(8, 0, 5));

Assert.IsTrue(clippedVertexes[clippedIndexes[6]] == new Vector3(8, 0, 5));

Assert.IsTrue(clippedVertexes[clippedIndexes[7]] == new Vector3(8, 0, 8));

Assert.IsTrue(clippedVertexes[clippedIndexes[8]] == new Vector3(10, 0, 8));

Assert.IsTrue(clippedVertexes[clippedIndexes[9]] == new Vector3(10, 0, 8));

Assert.IsTrue(clippedVertexes[clippedIndexes[10]] == new Vector3(10, 0, 6.5f));

Assert.IsTrue(clippedVertexes[clippedIndexes[11]] == new Vector3(8, 0, 5));

Assert.IsTrue(clippedVertexes[clippedIndexes[12]] == new Vector3(8, 0, 5));

Assert.IsTrue(clippedVertexes[clippedIndexes[13]] == new Vector3(10, 0, 6.5f));

Assert.IsTrue(clippedVertexes[clippedIndexes[14]] == new Vector3(10, 0, 5));

}

/// <summary>

/// top point of triangle outside

/// </summary>

[TestMethod]

public void SimpleClipper_ClipToBoundary_Vector3_TwoPointsOutsideEmbeddedCorner()

{

List<Vector3> mesh = new List<Vector3>();

mesh.Add(new Vector3(-5, 0, 2));

mesh.Add(new Vector3(2, 0, 2));

mesh.Add(new Vector3(2, 0, -5));

List<int> indexes = new List<int>();

indexes.AddRange(new int[] { 0, 1, 2 });

List<Vector3> clippedVertexes;

List<int> clippedIndexes;

SimpleClipper clipper = new SimpleClipper();

clipper.ClipMeshToBoundary<Vector3>(0, 0, 10, 10, mesh, indexes,

positionAccessor: (int index) => mesh[index],

vertexConstructor: (int[] triangleIndexes, Vector3 position) => createInterpolatedPoint(

mesh[triangleIndexes[0]],

mesh[triangleIndexes[1]],

mesh[triangleIndexes[2]],

position

),

clippedVertexes: out clippedVertexes,

clippedIndexes: out clippedIndexes);

Assert.IsTrue(clippedVertexes.Count == 4);

Assert.IsTrue(clippedIndexes.Count == 6);

Assert.IsTrue(clippedVertexes[clippedIndexes[0]] == new Vector3(2, 0, 2));

Assert.IsTrue(clippedVertexes[clippedIndexes[1]] == new Vector3(2, 0, 0));

Assert.IsTrue(clippedVertexes[clippedIndexes[2]] == new Vector3(0, 0, 0));

Assert.IsTrue(clippedVertexes[clippedIndexes[3]] == new Vector3(0, 0, 0));

Assert.IsTrue(clippedVertexes[clippedIndexes[4]] == new Vector3(0, 0, 2));

Assert.IsTrue(clippedVertexes[clippedIndexes[5]] == new Vector3(2, 0, 2));



}

/// <summary>

/// top point of triangle outside

/// </summary>

[TestMethod]

public void SimpleClipper_ClipToBoundary_Vector3_OnePointOutsideEmbeddedCorner()

{

List<Vector3> mesh = new List<Vector3>();

mesh.Add(new Vector3(2, 0, 2));

mesh.Add(new Vector3(-2, 0, 12));

mesh.Add(new Vector3(8, 0, 8));

List<int> indexes = new List<int>();

indexes.AddRange(new int[] { 0, 1, 2 });

List<Vector3> clippedVertexes;

List<int> clippedIndexes;

SimpleClipper clipper = new SimpleClipper();

clipper.ClipMeshToBoundary<Vector3>(0, 0, 10, 10, mesh, indexes,

positionAccessor: (int index) => mesh[index],

vertexConstructor: (int[] triangleIndexes, Vector3 position) => createInterpolatedPoint(

mesh[triangleIndexes[0]],

mesh[triangleIndexes[1]],

mesh[triangleIndexes[2]],

position

),

clippedVertexes: out clippedVertexes,

clippedIndexes: out clippedIndexes);

Assert.IsTrue(clippedVertexes.Count == 5);

Assert.IsTrue(clippedIndexes.Count == 9);

Assert.IsTrue(clippedVertexes[clippedIndexes[0]] == new Vector3(2, 0, 2));

Assert.IsTrue(clippedVertexes[clippedIndexes[1]] == new Vector3(0, 0, 7));

Assert.IsTrue(clippedVertexes[clippedIndexes[2]] == new Vector3(0, 0, 10));

Assert.IsTrue(clippedVertexes[clippedIndexes[3]] == new Vector3(0, 0, 10));

Assert.IsTrue(clippedVertexes[clippedIndexes[4]] == new Vector3(3, 0, 10));

Assert.IsTrue(clippedVertexes[clippedIndexes[5]] == new Vector3(8, 0, 8));

Assert.IsTrue(clippedVertexes[clippedIndexes[6]] == new Vector3(2, 0, 2));

Assert.IsTrue(clippedVertexes[clippedIndexes[7]] == new Vector3(0, 0, 10));

Assert.IsTrue(clippedVertexes[clippedIndexes[8]] == new Vector3(8, 0, 8));



}

/// <summary>

/// top point of triangle outside

/// </summary>

[TestMethod]

public void SimpleClipper_ClipToBoundary_Vector3_TwoPointsOutside()

{

List<Vector3> mesh = new List<Vector3>();

mesh.Add(new Vector3(8, 0, 2));

mesh.Add(new Vector3(12, 0, 8));

mesh.Add(new Vector3(12, 0, 2));

List<int> indexes = new List<int>();

indexes.AddRange(new int[] { 0, 1, 2 });

List<Vector3> clippedVertexes;

List<int> clippedIndexes;

SimpleClipper clipper = new SimpleClipper();

clipper.ClipMeshToBoundary<Vector3>(0, 0, 10, 10, mesh, indexes,

positionAccessor: (int index) => mesh[index],

vertexConstructor: (int[] triangleIndexes, Vector3 position) => createInterpolatedPoint(

mesh[triangleIndexes[0]],

mesh[triangleIndexes[1]],

mesh[triangleIndexes[2]],

position

),

clippedVertexes: out clippedVertexes,

clippedIndexes: out clippedIndexes);

Assert.IsTrue(clippedVertexes.Count == 3);

Assert.IsTrue(clippedIndexes.Count == 3);

Assert.IsTrue(clippedVertexes[clippedIndexes[0]] == new Vector3(8, 0, 2));

Assert.IsTrue(clippedVertexes[clippedIndexes[1]] == new Vector3(10, 0, 5));

Assert.IsTrue(clippedVertexes[clippedIndexes[2]] == new Vector3(10, 0, 2));



}

/// <summary>

/// top point of triangle outside

/// </summary>

[TestMethod]

public void SimpleClipper_ClipToBoundary_Vector3_Point1Outside()

{

List<Vector3> mesh = new List<Vector3>();

mesh.Add(new Vector3(-2, 0, 2));

mesh.Add(new Vector3(2, 0, 6));

mesh.Add(new Vector3(2, 0, 2));

List<int> indexes = new List<int>();

indexes.AddRange(new int[] { 0, 1, 2 });

List<Vector3> clippedVertexes;

List<int> clippedIndexes;

SimpleClipper clipper = new SimpleClipper();

clipper.ClipMeshToBoundary<Vector3>(0, 0, 10, 10, mesh, indexes,

positionAccessor: (int index) => mesh[index],

vertexConstructor: (int[] triangleIndexes, Vector3 position) => createInterpolatedPoint(

mesh[triangleIndexes[0]],

mesh[triangleIndexes[1]],

mesh[triangleIndexes[2]],

position

),

clippedVertexes: out clippedVertexes,

clippedIndexes: out clippedIndexes);

Assert.IsTrue(clippedVertexes.Count == 4);

Assert.IsTrue(clippedIndexes.Count == 6);

Assert.IsTrue(clippedVertexes[clippedIndexes[0]] == new Vector3(2, 0, 6));

Assert.IsTrue(clippedVertexes[clippedIndexes[1]] == new Vector3(2, 0, 2));

Assert.IsTrue(clippedVertexes[clippedIndexes[2]] == new Vector3(0, 0, 2));

Assert.IsTrue(clippedVertexes[clippedIndexes[3]] == new Vector3(0, 0, 2));

Assert.IsTrue(clippedVertexes[clippedIndexes[4]] == new Vector3(0, 0, 4));

Assert.IsTrue(clippedVertexes[clippedIndexes[5]] == new Vector3(2, 0, 6));

}





/// <summary>

/// left point of triangle outside

/// </summary>

[TestMethod]

public void SimpleClipper_ClipToBoundary_Vector3_Point2Outside()

{

List<Vector3> mesh = new List<Vector3>();

mesh.Add(new Vector3(3, 0, 8));

mesh.Add(new Vector3(5, 0, 12));

mesh.Add(new Vector3(7, 0, 8));

List<int> indexes = new List<int>();

indexes.AddRange(new int[] { 0, 1, 2 });

List<Vector3> clippedVertexes;

List<int> clippedIndexes;

SimpleClipper clipper = new SimpleClipper();

clipper.ClipMeshToBoundary<Vector3>(0, 0, 10, 10, mesh, indexes,

positionAccessor: (int index) => mesh[index],

vertexConstructor: (int[] triangleIndexes, Vector3 position) => createInterpolatedPoint(

mesh[triangleIndexes[0]],

mesh[triangleIndexes[1]],

mesh[triangleIndexes[2]],

position

),

clippedVertexes: out clippedVertexes,

clippedIndexes: out clippedIndexes);

Assert.IsTrue(clippedVertexes.Count == 4);

Assert.IsTrue(clippedIndexes.Count == 6);

Assert.IsTrue(clippedVertexes[clippedIndexes[0]] == new Vector3(3, 0, 8));

Assert.IsTrue(clippedVertexes[clippedIndexes[1]] == new Vector3(4, 0, 10));

Assert.IsTrue(clippedVertexes[clippedIndexes[2]] == new Vector3(6, 0, 10));

Assert.IsTrue(clippedVertexes[clippedIndexes[3]] == new Vector3(6, 0, 10));

Assert.IsTrue(clippedVertexes[clippedIndexes[4]] == new Vector3(7, 0, 8));

Assert.IsTrue(clippedVertexes[clippedIndexes[5]] == new Vector3(3, 0, 8));

}





/// <summary>

/// right point of triangle outside

/// </summary>

[TestMethod]

public void SimpleClipper_ClipToBoundary_Vector3_Point3Outside()

{

List<Vector3> mesh = new List<Vector3>();

mesh.Add(new Vector3(8, 0, 2));

mesh.Add(new Vector3(8, 0, 8));

mesh.Add(new Vector3(12, 0,2));

List<int> indexes = new List<int>();

indexes.AddRange(new int[] { 0, 1, 2 });

List<Vector3> clippedVertexes;

List<int> clippedIndexes;

SimpleClipper clipper = new SimpleClipper();

clipper.ClipMeshToBoundary<Vector3>(0, 0, 10, 10, mesh, indexes,

positionAccessor: (int index) => mesh[index],

vertexConstructor: (int[] triangleIndexes, Vector3 position) => createInterpolatedPoint(

mesh[triangleIndexes[0]],

mesh[triangleIndexes[1]],

mesh[triangleIndexes[2]],

position

),

clippedVertexes: out clippedVertexes,

clippedIndexes: out clippedIndexes);

Assert.IsTrue(clippedVertexes.Count == 4);

Assert.IsTrue(clippedIndexes.Count == 6);

Assert.IsTrue(clippedVertexes[clippedIndexes[0]] == new Vector3(8, 0, 2));

Assert.IsTrue(clippedVertexes[clippedIndexes[1]] == new Vector3(8, 0, 8));

Assert.IsTrue(clippedVertexes[clippedIndexes[2]] == new Vector3(10, 0, 5));

Assert.IsTrue(clippedVertexes[clippedIndexes[3]] == new Vector3(10, 0, 5));

Assert.IsTrue(clippedVertexes[clippedIndexes[4]] == new Vector3(10, 0, 2));

Assert.IsTrue(clippedVertexes[clippedIndexes[5]] == new Vector3(8, 0, 2));

}





[TestMethod]

public void SimpleClipper_ClipToBoundary_Vector3_AllOutside()

{

List<Vector3> mesh = new List<Vector3>();

mesh.Add(new Vector3(5, 0, 8));

mesh.Add(new Vector3(11, 0, 15));

mesh.Add(new Vector3(15, 0, 9));

mesh.Add(new Vector3(11, 0, 3));

List<int> indexes = new List<int>();

indexes.AddRange(new int[] { 0, 1, 3 });

indexes.AddRange(new int[] { 1, 2, 3 });

List<Vector3> clippedVertexes;

List<int> clippedIndexes;

SimpleClipper clipper = new SimpleClipper();

clipper.ClipMeshToBoundary<Vector3>(100, 100, 110, 110, mesh, indexes,

positionAccessor: (int index) => mesh[index],

vertexConstructor: (int[] triangleIndexes, Vector3 position) => createInterpolatedPoint(

mesh[triangleIndexes[0]],

mesh[triangleIndexes[1]],

mesh[triangleIndexes[2]],

position

),

clippedVertexes: out clippedVertexes,

clippedIndexes: out clippedIndexes);

Assert.IsTrue(clippedVertexes.Count == 0);

}

[TestMethod]

public void SimpleClipper_ClipToBoundary_Vector3_AllInside()

{

List<Vector3> mesh = new List<Vector3>();

mesh.Add(new Vector3(5, 0, 8));

mesh.Add(new Vector3(11, 0, 15));

mesh.Add(new Vector3(15, 0, 9));

mesh.Add(new Vector3(11, 0, 3));

List<int> indexes = new List<int>();

indexes.AddRange(new int[] { 0, 1, 3 });

indexes.AddRange(new int[] { 1, 2, 3 });

List<Vector3> clippedVertexes;

List<int> clippedIndexes;

SimpleClipper clipper = new SimpleClipper();

clipper.ClipMeshToBoundary<Vector3>(-100, -100, 100, 100, mesh, indexes,

positionAccessor: (int index) => mesh[index],

vertexConstructor: (int[] triangleIndexes, Vector3 position) => createInterpolatedPoint(

mesh[triangleIndexes[0]],

mesh[triangleIndexes[1]],

mesh[triangleIndexes[2]],

position

),

clippedVertexes: out clippedVertexes,

clippedIndexes: out clippedIndexes);

Assert.IsTrue(clippedVertexes.Count == 4);

Assert.IsTrue(mesh.Contains(clippedVertexes[0]));

Assert.IsTrue(mesh.Contains(clippedVertexes[1]));

Assert.IsTrue(mesh.Contains(clippedVertexes[2]));

Assert.IsTrue(mesh.Contains(clippedVertexes[3]));

Assert.IsTrue(indexes.Contains(clippedIndexes[0]));

Assert.IsTrue(indexes.Contains(clippedIndexes[1]));

Assert.IsTrue(indexes.Contains(clippedIndexes[2]));

Assert.IsTrue(indexes.Contains(clippedIndexes[3]));

Assert.IsTrue(indexes.Contains(clippedIndexes[4]));

Assert.IsTrue(indexes.Contains(clippedIndexes[5]));



}

private Vector3 createInterpolatedPoint(Vector3 vector1, Vector3 vector2, Vector3 vector3, Vector3 position)

{

float height = Geometry.GetInterpolatedValue(position, vector1, vector2, vector3, vector1.Y, vector2.Y, vector3.Y);

return new Vector3(position.X, height, position.Z);

}

}

}