Как отсортировать точки против часовой стрелки в трёхмерном пространстве по правилу правой руки имея их координаты и нормаль?

Question

[pogoreli]

Я сейчас пытаюсь написать алгоритм на c#, для открытия 3д моделей и исправления битых файлов. У меня есть 3 массива одинаковой длины- координаты точек, их нормали, и треугольники. В файлах с моделями информация содержится такая информация:

facet normal nx ny nz
outer loop
vertex v1x v1y v1z
vertex v2x v2y v2z
vertex v3x v3y v3z
endloop
endfacet

Это stl файл, но это просто для примера, потому что в других форматах все очень похоже.

Нормаль одна и та же для всех трёх точек, так что она просто дублируется 3 раза.

По стандарту, эти точки должны идти по порядку против часовой стрелки, но на практике не все приложения придерживаются этого правила.

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

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

Может кто нибудь сталкивался с этим, и может помочь составить математическую модель, или алгоритм. Я пишу это на c#, если нужны какие то специфические функции языка, но мне скорее надо просто понять саму последовательность действий, так что формулы или псевдоязык мне очень помогут.

Comments

[Армянское Радио]

Use the векторное произведение, Luke!

[pogoreli]

Я понимаю, что нужно делать что то в таком роде, но cross product между векторами на треугольнике уже даёт нормаль. Мне получается нужна обратная функция? Или что на что мне умножать? Нормаль и координаты у меня есть, но мне их нужно расставить в правильном порядке.

Answer 1

[Ocelot]

Берём два вектора: 1->2 и 1->3, считаем их векторное произведение. Если его направление совпадает с направлением нормали треугольника, значит точки идут в правильном порядке. Если нет, меняем точки 2 и 3 местами.