Построение 2D-полуплоскости с учетом 3 точек, каждый раз выбирая внешнюю нормаль

Редактировать: добавлены ASCII-диаграммы, показывающие параметры относительно полуплоскости

У меня есть класс HalfPlane, который определяет однородное представление полуплоскости в 2D-пространстве так, что любая точка, расположенная в точке с однородной координатой больше 0, находится вне плоскости.

Я использую этот класс для обрезки отрезков для программного рендеринга, а также для проверки столкновения точки и треугольника.

Учитывая две точки на линии границы и точку в полуплоскости, можно найти эту однородную координату, но для ее нахождения сначала требуется найти нормаль, обращенную наружу от линии.

Это текущая реализация для нахождения полуплоскости по заданному отрезку линии и точке внутри полуплоскости, которая предполагает, что нормаль, которую она находит, является обращенной наружу нормалью.

// Hcoord is a Vector3
// Point  is a Vector3 such that w is always 1
// Vector is a Vector3 such that w is always 0
// HalfPlane is an aggregation of Hcoord and a few constructors

// Half-Plane definition
// n = <a, b>:  Outward-facing normal of the half-plane
// C = (x, y):  Point on the boundary line
// d = n dot C: Constant derived from normal form of the boundary line
// [  a ]
// [  b ] = half-plane AB containing P
// [ -d ]
// the dot product of this Hcoord with any Point determines which
// side of the half plane the Point resides

//              ^
//              | n
//   outside    |
// <------------x---------->
//    inside    C

// given an outward-facing normal and a Point on the boundary line
// find -d and construct the half-plane
static Hcoord ConstructHP(const Vector& n, const Point& C)
{
return Hcoord(n.x, n.y, -1.0f * (n.x * C.x + n.y * C.y));
}//     outside
// <-x--------------x->
//   A  inside      B
//        x P

// Given 2 Points on the boundary line and a Point contained within the half-plane
// construct the half-plane. Assume P is not collinear with A and B
static Hcoord ConstructHP(const Point& A, const Point& B, const Point& P)
{
// find vector normal to line AB
// assume [ -dy ] is outwardly-facing normal 'n'
//        [  dx ]
Vector n(A.y - B.y, B.x - A.x);// and construct HalfPlane based on that assumption
Hcoord h(ConstructHP(n, A));

// h dot P should be less than 0
// because P is within the half-plane
if (dot(h, P) > 0)
// if not, invert the half-plane
h = -h;

return h;
}

ConstructHP — это перегруженная вспомогательная функция, вызываемая конструкторами класса HalfPlane, которые принимают одинаковые параметры.

Учитывая, что мне вручают произвольные точки, которые, как предполагается, не коллинеарны, возможно ли выбрать, какая нормаль к полуплоскости будет обращена наружу, без предварительного построения предполагаемой полуплоскости? Если так, то как?

Другими словами, я ищу алгоритм, который строит полуплоскость без необходимости проверять, верна ли полуплоскость, которую я строю, перед ее возвратом.

редактировать: я отклоняю A-P на A-B чтобы найти внешнюю нормаль сейчас. ConstructHP с 3 точками теперь имеет следующую реализацию:

static Hcoord ConstructHP(const Point& A, const Point& B, const Point& P)
{
// find the outward facing normal by
// rejecting A - P onto A - B
// and call outward normal + point constructor
return ConstructHP(Rejection(A - P, A - B), A);
}

static Vector Rejection(const Vector& a, const Vector& b)
{

//                              a dot b
// a2 Rejection(a, b): a2 = a - ------- * b
//                              b dot b
return a - (dot(a, b) / dot(b, b)) * b;
}

0

Решение

Задача ещё не решена.

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]