344 lines
11 KiB
C#
344 lines
11 KiB
C#
// Copyright (c) 2014-2015 Robert Rouhani <robert.rouhani@gmail.com> and other contributors (see CONTRIBUTORS file).
|
|
// Licensed under the MIT License - https://raw.github.com/Robmaister/SharpNav/master/LICENSE
|
|
|
|
using System;
|
|
using System.Collections.Generic;
|
|
using System.Runtime.InteropServices;
|
|
|
|
namespace SharpNav
|
|
{
|
|
/// <summary>
|
|
/// A vertex inside a <see cref="PolyMesh"/>.
|
|
/// </summary>
|
|
[StructLayout(LayoutKind.Sequential)]
|
|
public struct PolyVertex : IEquatable<PolyVertex>
|
|
{
|
|
/// <summary>
|
|
/// The X coordinate.
|
|
/// </summary>
|
|
public int X;
|
|
|
|
/// <summary>
|
|
/// The Y coordinate.
|
|
/// </summary>
|
|
public int Y;
|
|
|
|
/// <summary>
|
|
/// The Z coordinate.
|
|
/// </summary>
|
|
public int Z;
|
|
|
|
/// <summary>
|
|
/// Initializes a new instance of the <see cref="PolyVertex"/> struct.
|
|
/// </summary>
|
|
/// <param name="x">The X coordinate.</param>
|
|
/// <param name="y">The Y coordinate.</param>
|
|
/// <param name="z">The Z coordinate.</param>
|
|
public PolyVertex(int x, int y, int z)
|
|
{
|
|
X = x;
|
|
Y = y;
|
|
Z = z;
|
|
}
|
|
|
|
/// <summary>
|
|
/// Calculates the component-wise minimum of two vertices.
|
|
/// </summary>
|
|
/// <param name="a">A vertex.</param>
|
|
/// <param name="b">Another vertex.</param>
|
|
/// <returns>The component-wise minimum of the two vertices.</returns>
|
|
public static PolyVertex ComponentMin(PolyVertex a, PolyVertex b)
|
|
{
|
|
PolyVertex v;
|
|
ComponentMin(ref a, ref b, out v);
|
|
return v;
|
|
}
|
|
|
|
/// <summary>
|
|
/// Calculates the component-wise minimum of two vertices.
|
|
/// </summary>
|
|
/// <param name="a">A vertex.</param>
|
|
/// <param name="b">Another vertex.</param>
|
|
/// <param name="result">The component-wise minimum of the two vertices.</param>
|
|
public static void ComponentMin(ref PolyVertex a, ref PolyVertex b, out PolyVertex result)
|
|
{
|
|
result.X = a.X < b.X ? a.X : b.X;
|
|
result.Y = a.Y < b.Y ? a.Y : b.Y;
|
|
result.Z = a.Z < b.Z ? a.Z : b.Z;
|
|
}
|
|
|
|
/// <summary>
|
|
/// Calculates the component-wise maximum of two vertices.
|
|
/// </summary>
|
|
/// <param name="a">A vertex.</param>
|
|
/// <param name="b">Another vertex.</param>
|
|
/// <returns>The component-wise maximum of the two vertices.</returns>
|
|
public static PolyVertex ComponentMax(PolyVertex a, PolyVertex b)
|
|
{
|
|
PolyVertex v;
|
|
ComponentMax(ref a, ref b, out v);
|
|
return v;
|
|
}
|
|
|
|
/// <summary>
|
|
/// Calculates the component-wise maximum of two vertices.
|
|
/// </summary>
|
|
/// <param name="a">A vertex.</param>
|
|
/// <param name="b">Another vertex.</param>
|
|
/// <param name="result">The component-wise maximum of the two vertices.</param>
|
|
public static void ComponentMax(ref PolyVertex a, ref PolyVertex b, out PolyVertex result)
|
|
{
|
|
result.X = a.X > b.X ? a.X : b.X;
|
|
result.Y = a.Y > b.Y ? a.Y : b.Y;
|
|
result.Z = a.Z > b.Z ? a.Z : b.Z;
|
|
}
|
|
|
|
/// <summary>
|
|
/// Gets the leftness of a triangle formed from 3 contour vertices.
|
|
/// </summary>
|
|
/// <param name="a">The first vertex.</param>
|
|
/// <param name="b">The second vertex.</param>
|
|
/// <param name="c">The third vertex.</param>
|
|
/// <returns>A value indicating the leftness of the triangle.</returns>
|
|
public static bool IsLeft(ref PolyVertex a, ref PolyVertex b, ref PolyVertex c)
|
|
{
|
|
int area;
|
|
Area2D(ref a, ref b, ref c, out area);
|
|
return area < 0;
|
|
}
|
|
|
|
/// <summary>
|
|
/// Gets the leftness (left or on) of a triangle formed from 3 contour vertices.
|
|
/// </summary>
|
|
/// <param name="a">The first vertex.</param>
|
|
/// <param name="b">The second vertex.</param>
|
|
/// <param name="c">The third vertex.</param>
|
|
/// <returns>A value indicating whether the triangle is left or on.</returns>
|
|
public static bool IsLeftOn(ref PolyVertex a, ref PolyVertex b, ref PolyVertex c)
|
|
{
|
|
int area;
|
|
Area2D(ref a, ref b, ref c, out area);
|
|
return area <= 0;
|
|
}
|
|
|
|
/// <summary>
|
|
/// Compares vertex equality in 2D.
|
|
/// </summary>
|
|
/// <param name="a">A vertex.</param>
|
|
/// <param name="b">Another vertex.</param>
|
|
/// <returns>A value indicating whether the X and Z components of both vertices are equal.</returns>
|
|
public static bool Equal2D(ref PolyVertex a, ref PolyVertex b)
|
|
{
|
|
return a.X == b.X && a.Z == b.Z;
|
|
}
|
|
|
|
/// <summary>
|
|
/// True if and only if segments AB and CD intersect, properly or improperly.
|
|
/// </summary>
|
|
/// <param name="a">Point A of segment AB.</param>
|
|
/// <param name="b">Point B of segment AB.</param>
|
|
/// <param name="c">Point C of segment CD.</param>
|
|
/// <param name="d">Point D of segment CD.</param>
|
|
/// <returns>A value indicating whether segments AB and CD intersect.</returns>
|
|
public static bool Intersect(ref PolyVertex a, ref PolyVertex b, ref PolyVertex c, ref PolyVertex d)
|
|
{
|
|
if (IntersectProp(ref a, ref b, ref c, ref d))
|
|
return true;
|
|
else if (IsBetween(ref a, ref b, ref c)
|
|
|| IsBetween(ref a, ref b, ref d)
|
|
|| IsBetween(ref c, ref d, ref a)
|
|
|| IsBetween(ref c, ref d, ref b))
|
|
return true;
|
|
else
|
|
return false;
|
|
}
|
|
|
|
/// <summary>
|
|
/// True if and only if segments AB and CD intersect properly.
|
|
/// </summary>
|
|
/// <remarks>
|
|
/// Proper intersection: A point interior to both segments is shared. Properness determined by strict leftness.
|
|
/// </remarks>
|
|
/// <param name="a">Point A of segment AB.</param>
|
|
/// <param name="b">Point B of segment AB.</param>
|
|
/// <param name="c">Point C of segment CD.</param>
|
|
/// <param name="d">Point D of segment CD.</param>
|
|
/// <returns>A value indicating whether segements AB and CD are intersecting properly.</returns>
|
|
public static bool IntersectProp(ref PolyVertex a, ref PolyVertex b, ref PolyVertex c, ref PolyVertex d)
|
|
{
|
|
//eliminate improper cases
|
|
if (IsCollinear(ref a, ref b, ref c)
|
|
|| IsCollinear(ref a, ref b, ref d)
|
|
|| IsCollinear(ref c, ref d, ref a)
|
|
|| IsCollinear(ref c, ref d, ref b))
|
|
return false;
|
|
|
|
return (!IsLeft(ref a, ref b, ref c) ^ !IsLeft(ref a, ref b, ref d))
|
|
&& (!IsLeft(ref c, ref d, ref a) ^ !IsLeft(ref c, ref d, ref b));
|
|
}
|
|
|
|
/// <summary>
|
|
/// True if and only if A, B, and C are collinear and point C lies on closed segment AB
|
|
/// </summary>
|
|
/// <param name="a">Point A of segment AB.</param>
|
|
/// <param name="b">Point B of segment AB.</param>
|
|
/// <param name="c">Point C.</param>
|
|
/// <returns>A value indicating whether the three points are collinear with C in the middle.</returns>
|
|
public static bool IsBetween(ref PolyVertex a, ref PolyVertex b, ref PolyVertex c)
|
|
{
|
|
if (!IsCollinear(ref a, ref b, ref c))
|
|
return false;
|
|
|
|
if (a.X != b.X)
|
|
return ((a.X <= c.X) && (c.X <= b.X)) || ((a.X >= c.X) && (c.X >= b.X));
|
|
else
|
|
return ((a.Z <= c.Z) && (c.Z <= b.Z)) || ((a.Z >= c.Z) && (c.Z >= b.Z));
|
|
}
|
|
|
|
/// <summary>
|
|
/// True if and only if points A, B, and C are collinear.
|
|
/// </summary>
|
|
/// <param name="a">Point A.</param>
|
|
/// <param name="b">Point B.</param>
|
|
/// <param name="c">Point C.</param>
|
|
/// <returns>A value indicating whether the points are collinear.</returns>
|
|
public static bool IsCollinear(ref PolyVertex a, ref PolyVertex b, ref PolyVertex c)
|
|
{
|
|
int area;
|
|
Area2D(ref a, ref b, ref c, out area);
|
|
return area == 0;
|
|
}
|
|
|
|
/// <summary>
|
|
/// Gets the 2D area of the triangle ABC.
|
|
/// </summary>
|
|
/// <param name="a">Point A of triangle ABC.</param>
|
|
/// <param name="b">Point B of triangle ABC.</param>
|
|
/// <param name="c">Point C of triangle ABC.</param>
|
|
/// <param name="area">The 2D area of the triangle.</param>
|
|
public static void Area2D(ref PolyVertex a, ref PolyVertex b, ref PolyVertex c, out int area)
|
|
{
|
|
area = (b.X - a.X) * (c.Z - a.Z) - (c.X - a.X) * (b.Z - a.Z);
|
|
}
|
|
|
|
/// <summary>
|
|
/// Gets the 2D area of the triangle ABC.
|
|
/// </summary>
|
|
/// <param name="a">Point A of triangle ABC.</param>
|
|
/// <param name="b">Point B of triangle ABC.</param>
|
|
/// <param name="c">Point C of triangle ABC.</param>
|
|
/// <param name="area">The 2D area of the triangle.</param>
|
|
public static void Area2D(ref ContourVertex a, ref ContourVertex b, ref ContourVertex c, out int area)
|
|
{
|
|
area = (b.X - a.X) * (c.Z - a.Z) - (c.X - a.X) * (b.Z - a.Z);
|
|
}
|
|
|
|
/// <summary>
|
|
/// Compares two vertices for equality.
|
|
/// </summary>
|
|
/// <param name="left">A vertex.</param>
|
|
/// <param name="right">Another vertex.</param>
|
|
/// <returns>A value indicating whether the two vertices are equal.</returns>
|
|
public static bool operator ==(PolyVertex left, PolyVertex right)
|
|
{
|
|
return left.Equals(right);
|
|
}
|
|
|
|
/// <summary>
|
|
/// Compares two vertices for inequality.
|
|
/// </summary>
|
|
/// <param name="left">A vertex.</param>
|
|
/// <param name="right">Another vertex.</param>
|
|
/// <returns>A value indicating whether the two vertices are not equal.</returns>
|
|
public static bool operator !=(PolyVertex left, PolyVertex right)
|
|
{
|
|
return !(left == right);
|
|
}
|
|
|
|
/// <summary>
|
|
/// Compares another <see cref="PolyVertex"/> with this instance for equality.
|
|
/// </summary>
|
|
/// <param name="other">The other instance.</param>
|
|
/// <returns>A value indicating whether the two vertices are equal.</returns>
|
|
public bool Equals(PolyVertex other)
|
|
{
|
|
return X == other.X && Y == other.Y && Z == other.Z;
|
|
}
|
|
|
|
/// <summary>
|
|
/// Compares an object with this instance for equality.
|
|
/// </summary>
|
|
/// <param name="obj">An object.</param>
|
|
/// <returns>A value indicating whether the object is equal to this instance.</returns>
|
|
public override bool Equals(object obj)
|
|
{
|
|
PolyVertex? p = obj as PolyVertex?;
|
|
if (p.HasValue)
|
|
return this.Equals(p.Value);
|
|
|
|
return false;
|
|
}
|
|
|
|
/// <summary>
|
|
/// Gets a hash code unique to the contents of this instance.
|
|
/// </summary>
|
|
/// <returns>A hash code.</returns>
|
|
public override int GetHashCode()
|
|
{
|
|
//TODO write a better hashcode
|
|
return X.GetHashCode() ^ Y.GetHashCode() ^ Z.GetHashCode();
|
|
}
|
|
|
|
/// <summary>
|
|
/// Gets a human-readable version of the vertex.
|
|
/// </summary>
|
|
/// <returns>A string.</returns>
|
|
public override string ToString()
|
|
{
|
|
return "(" + X + ", " + Y + ", " + Z + ")";
|
|
}
|
|
|
|
/// <summary>
|
|
/// An implementation of <see cref="IEqualityComparer{T}"/> of <see cref="PolyVertex"/> that allows for the
|
|
/// Y coordinates of two vertices to be within a specified range and still be considered equal.
|
|
/// </summary>
|
|
internal class RoughYEqualityComparer : IEqualityComparer<PolyVertex>
|
|
{
|
|
private const int HashConstX = unchecked((int)0x8da6b343);
|
|
private const int HashConstZ = unchecked((int)0xcb1ab31f);
|
|
|
|
private int epsilonY;
|
|
|
|
/// <summary>
|
|
/// Initializes a new instance of the <see cref="RoughYEqualityComparer"/> class.
|
|
/// </summary>
|
|
/// <param name="epsilonY">The range of Y values in which two vertices are considered equal.</param>
|
|
public RoughYEqualityComparer(int epsilonY)
|
|
{
|
|
this.epsilonY = epsilonY;
|
|
}
|
|
|
|
/// <summary>
|
|
/// Compares two vertices for equality.
|
|
/// </summary>
|
|
/// <param name="left">A vertex.</param>
|
|
/// <param name="right">Another vertex.</param>
|
|
/// <returns>A value indicating whether the two vertices are equal.</returns>
|
|
public bool Equals(PolyVertex left, PolyVertex right)
|
|
{
|
|
return left.X == right.X && (Math.Abs(left.Y - right.Y) <= epsilonY) && left.Z == right.Z;
|
|
}
|
|
|
|
/// <summary>
|
|
/// Gets a unique hash code for the contents of a <see cref="PolyVertex"/> instance.
|
|
/// </summary>
|
|
/// <param name="obj">A vertex.</param>
|
|
/// <returns>A hash code.</returns>
|
|
public int GetHashCode(PolyVertex obj)
|
|
{
|
|
return HashConstX * obj.X + HashConstZ * obj.Z;
|
|
}
|
|
}
|
|
}
|
|
}
|