Как найти точки, находящиеся внутри границы 3D

Question

В настоящее время я работаю над проектом на Android, основанным на Java. Я использую OpenGL-ES 3.0.

В моем проекте у меня есть большой сложный трехмерный объект (человеческая голова) с 100000 + вершинами и 400000 + треугольниками. Вершины объекта хранятся в массиве. Объект можно вращать относительно его центра тяжести.

Я пытаюсь реализовать функцию, в которой пользователь выбирает набор точек на голове, и линия рисуется, соединяющая каждую точку (вроде как «соединение точек»). Другими словами, пользователь выбирает точки на голове (p1, p2, p3 ... pn), и выбранные точки изменят цвет. Затем, выбирая последнюю точку (pn), выполняется алгоритм вычисления всех вершин, лежащих между каждой точкой (например, p1 и p2). Затем эти вершины изменят цвет, поэтому пользователь видит линию (или близкую к линии) между каждой выбранной ими точкой.

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

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

Моя идея состояла в том, чтобы взять среднюю точку p1 и p2, установить ее как центр эллипсоида и повернуть/растянуть размеры эллипсоида так, чтобы одна ось проходила от p1 до p2, а другая - некоторое большое значение. В принципе, это будет выглядеть как сплющенная шарообразная форма (что-то вроде красной кровяной клетки) и положить один конец шара на p1, а противоположный конец на p2. Затем я мог бы запустить алгоритм, который я уже закодировал, чтобы найти все точки внутри этого эллипсоида. Затем я могу изменить цвет этих точек, и пользователь может видеть линию между каждой выбранной ими точкой.

Есть ли у кого-нибудь какие-либо замечания в отношении этой техники? Есть ли другие способы достичь желаемого результата?

Answer 1

Чтобы проверить, если точка прикосновения или находится внутри эллипсоида:

• Перевести мир -x, -y, -z (х, у и г будучи эллипса центра) такой, что (0 , 0, 0) становится новым центром эллипсоида.
• Вращайте мир так, чтобы эллипсоид составлял 0 градусов.
• Увеличьте мир на 1/a, 1/b и 1/c (a, b и c - длина 3 эллиптических осей).
• если sqroot (a^2 + b^2 + c^2) < = 1, то точка лежит внутри сферы.