Распознать примитивы

[Igors]

Добрый день

Опять вылезла задачка распознать примитивы (в неск др редакции). См аттач. Даны только полигоны и вертексы. Нужно

1) Определить 1 из трех типов объекта (сфера, куб или цилиндр)
2) Найти матрицу (любую которая развернет объект по осям и вернет одинаковые масштабы)

Слухаю Ваши предложения 
Спасибо

[V1KT0P]

1) Определить 1 из трех типов объекта (сфера, куб или цилиндр)
2) Найти матрицу (любую которая развернет объект по осям и вернет одинаковые масштабы)

Слухаю Ваши предложения  

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

1) Берем куб в который вписывается фигура и берем центр( можно и просто центр тяжести взять, одно и то-же получится ). Считаем расстояние от центра до всех точек. Если они одинаковы, то у нас сфера.
2) Тоже самое что и предыдущее, только берем самые дальние точки, если их 8 то у нас куб.
3) Если не подошли два предыдущих то у нас цилиндр.

Да, я слаб в 3D поэтому могу ошибаться =).

добавлено:
Вспомнил что автор просил про разворот и масштаб:
Сфера: Берем любую точку и противоположную ей через центр. Поворачиваем фигуру так, чтоб получившаяся линия легла на одну из координатных линий. Теперь берем плоскость перпендикулярно этой линии и выбираем любую точку на этой плоскости, также берем противоположную точку через центр. Дальше поворачивая вокруг предыдущей координатной линии на градус равный разнице между текущей линией и одной из оставшихся координатных линий. В результате у нас получилась выровненая сфера. А вот масштабировать сферу одно удовольствие.
Куб: С кубом тоже просто. Берем одну точку и противоположную ей через центр, поворачиваем так чтоб линия легла через одну из координатны линий. Как и с сферой берем из плоскости линию и тоже поворачиваем чтоб и она легла на координатную линию. Теперь по всем трем осям поворачиваем куб на 45 градусов и вуаля у нас выровненный куб. Его тоже масштабировать легко.
Цилиндр: Берем самые удаленные точки от центра, должно получиться 2 группы по 4 штуки для обоих оснований. Для каждой группы находим среднюю точку. Эти две средние точки образуют центральную линию в цилиндре. Теперь поворачиваем его так, чтоб она легла на одну из координатных линий. Теперь на одном из оснований берем самую крайнюю точку и ее противоположную через центр и поворачиваем получившуюся линию как это делается в кубе или сфере чтоб она стала параллельна одной из оставшихся координатных линий. Масштабировать тоже вроде не проблема.

Вроде как все, только не пинайте за то что термины неправильные использую я не тридешник =).

[Igors]

1) Берем куб в который вписывается фигура и берем центр( можно и просто центр тяжести взять, одно и то-же получится ). Считаем расстояние от центра до всех точек. Если они одинаковы, то у нас сфера.
2) Тоже самое что и предыдущее, только берем самые дальние точки, если их 8 то у нас куб.
3) Если не подошли два предыдущих то у нас цилиндр.

"Равноудалены" не учитывает что примитив может быть вытянут/сжат по осям. Также "8 точек" выглядит хлопотно/ненадежно. Напр они могут найтись не только для куба.

Сфера: Берем любую точку и противоположную ей через центр. Поворачиваем фигуру так, чтоб п

Что-то сложновато и неясно, где же искомая матрица? Почему бы для начала не найти самую ближнюю и самую дальние точки от центра? Если разница между ними не превышает напр 2%, то сфера имеет равные масштабы по осям, устраивает единичная матрица. Иначе?

Цилиндр: Берем самые удаленные точки от центра, должно получиться 2 группы по 4 штуки для обоих оснований.

Для цилиндра по 4 штуки?

Вообще почему используете только точки (вертексы)?

Вроде как все, только не пинайте за то что термины неправильные использую я не тридешник =).

"Никогда не извиняйтесь за свой плохой английский. Во-первых, это и так видно, а во-вторых, Ваш английский намного лучше их русского" 

[V1KT0P]

"Равноудалены" не учитывает что примитив может быть вытянут/сжат по осям. Также "8 точек" выглядит хлопотно/ненадежно. Напр они могут найтись не только для куба.

Я что-то про это не увидел в описании, а наклонены они тоже могут быть? А сжатие по осям равномерное или с наклоном? Чем подробнее вопрос, тем подробнее ответ.

Что-то сложновато и неясно, где же искомая матрица? Почему бы для начала не найти самую ближнюю и самую дальние точки от центра? Если разница между ними не превышает напр 2%, то сфера имеет равные масштабы по осям, устраивает единичная матрица. Иначе?

Ну смотри во всех случаях одно и тоже:
1) У нас есть линия которая должна лечь на координатную линию. Значит центр линии должен быть в центре координат. Берем длину до центра линии. И смещаем от начала координат на это расстояние. На столько должен будет сдвинута вся фигура. Теперь для того чтоб вторая линия лягла на координатную линию надо всего-то повернуть по двум осям этот объект на угол равный углу между текущей линией и координатной линией.
В общем создать матрицу поворота я думаю не трудно если известны два угла на которые нужно повернуть и точку поворота.

Для цилиндра по 4 штуки?

Да, это я протупил. Тогда просто две группы точек. Из них выбрать одну, для нее найти пару против центра полученной группы. И перпендикулярно им линия с двумя точками. Что-то типа того =)( что-то сегодня вечером думается не очень ).

Вообще почему используете только точки (вертексы)?

Я же написал что не тридешник и по этому не знаю какая именно информация есть, я только понял что как минимум есть набор точек =).

[Igors]

Я что-то про это не увидел в описании, а наклонены они тоже могут быть? А сжатие по осям равномерное или с наклоном?

Так там картинка есть, на ней видно что сфера и цилиндр сплюснуты и все фигуоы повернуты. "Сжатие с наклоном" - наверное Вы имеете ввиду масштаб относительно произвольного центра. Нет, такой задачи не ставится, исходный объект масштабится только относительно своего центра, вот масштабы по каждой из осей могут быть любые. Др словами углы куба остаются прямыми

Чем подробнее вопрос, тем подробнее ответ.

Это Вы по привычке включаете? 

Ну смотри во всех случаях одно и тоже:
1) У нас есть линия которая должна лечь на координатную линию. Значит центр линии должен быть в центре координат. Берем длину до центра линии. И смещаем от начала координат на это расстояние. На столько должен будет сдвинута вся фигура. Теперь для того чтоб вторая линия лягла на координатную линию надо всего-то повернуть по двум осям этот объект на угол равный углу между текущей линией и координатной линией.
В общем создать матрицу поворота я думаю не трудно если известны два угла на которые нужно повернуть и точку поворота.

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

[V1KT0P]

Это Вы по привычке включаете? 

Просто чем больше информации, тем проще находить решение.
Например я так и не понял что есть помимо точек.
Например можно немного поразмыслить вот над чем: для треугольнику сумма всех углов равна 180 градусов, для четырехугольника 360 градусов. Может и для объемных фигур что-то подобное есть и надо просто вычислять какое-то значение по какому-нибудь алгоритму. Тут всего-то надо детектится сферу и куб, а цилиндр сам сдетектится если две предыдущие фигуры не найдены.
Например сфера имеет особенность в том что у нее угол между двумя прямоугольниками не равен нулю и не равен 90 градусов. В то время как у куба либо равен 0 либо 90 градусов. А у цилиндра и то и то. Так что можно хотя-бы по этим показателям детектить тип фигуры. А зная тип фигуры можно уже и матрицу трансформации получить.

[Igors]

Например я так и не понял что есть помимо точек.

Полигоны. На картинке показаны 4-угольники (вид приятнее) но при желании их всегда можно разбить на треугольники. 5-угольники (и более) никогда напрямую не рендерятся (разбиваются на простейшие). Полигон задается массивом индексов, напр {1, 2, 4} - индексы в массиве вертексов, а те уже содержат позицию (x, y, z) и др данные 

Например можно немного поразмыслить вот над чем: для треугольнику сумма всех углов равна 180 градусов, для четырехугольника 360 градусов. Может и для объемных фигур что-то подобное есть и надо просто вычислять какое-то значение по какому-нибудь алгоритму. Тут всего-то надо детектится сферу и куб, а цилиндр сам сдетектится если две предыдущие фигуры не найдены.
Например сфера имеет особенность в том что у нее угол между двумя прямоугольниками не равен нулю и не равен 90 градусов. В то время как у куба либо равен 0 либо 90 градусов. А у цилиндра и то и то. Так что можно хотя-бы по этим показателям детектить тип фигуры. А зная тип фигуры можно уже и матрицу трансформации получить.

Для этого используется термин "топология", опираться на нее обычно не очень хорошо/надежно. Напр на картинке показана сфера с "пупками" которая называют "меридианной". Однако юзверь может создать и "геодезическую" сферу (выглядит как футбольный мяч)

[V1KT0P]

Для этого используется термин "топология", опираться на нее обычно не очень хорошо/надежно. Напр на картинке показана сфера с "пупками" которая называют "меридианной". Однако юзверь может создать и "геодезическую" сферу (выглядит как футбольный мяч)

Что то я не понял в чем проблема с сферой. Берем "центр масс" и для каждого полигона строим нормаль наружу. Для каждой нормали проверяем угол между ею и соседними нормалями. Если они все больше 0 и меньше 90 градусов, это сфера. Если 0 или 90 это куб. Если от 0 до 90 включая 0 и 90 то у нас цилиндр.
Вот как может такой способ дать сбой при сфере или кубе?

[Igors]

Что то я не понял в чем проблема с сферой. Берем "центр масс" и для каждого полигона строим нормаль наружу.

Направление нормали к полигону (внутрь/наружу) задается перечислением вертексов (wind order). Напр треугольники {1, 2, 4} и {1, 4, 2} имеют противоположные нормали

Для каждой нормали проверяем угол между ею и соседними нормалями. Если они все больше 0 и меньше 90 градусов, это сфера. Если 0 или 90 это куб. Если от 0 до 90 включая 0 и 90 то у нас цилиндр.
Вот как может такой способ дать сбой при сфере или кубе?

Возможное решение, но малопривлекательное. Полигон должен знать соседей, построить такие структуры данных - довольно много кода. С др стороны решается только одна подзадача (определить тип), для матрицы мы пока ничего не имеем. Также работает только для идеальных, корректных фигур. Хотя именно так задача и ставилась, все же какой-то "запас прочности" хотелось бы иметь. Взагалi - слабкувато

[ssoft]

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

Можно начинать анализ с любого из примитива и далее расходимся в разные стороны по соседям.
Если направления нормалей с соседями совпадает, то это, скорее всего плоская грань, если нет, то криволинейная поверхность.
Либо просто считаем сколько граней получается и определяем тип фигуры, либо определяем топологию каким-то более сложным способом (придумываем сами).

Например, ребра - кусочные линии, грани (плоские или кривые) определяются замкнутыми контурами, ребра формируются как отрезки с "резким" изменением направления нормалей между смежными гранями.

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

Как-то так, надеюсь, что помог.

[Disa]

Мб кластеризация какими-нибудь классическими методами?
Не обязательно самому понимать какие именно значения должны принимать ,например, нормали или расстояния между вершинами (или другие фичи, которые вероятно могут определять фигуру).

Когда известны фичи, можно построить любой классификатор и обучить его на базовой выборке.

Думаю, после определения типа объекта, определить матрицу намного проще, чем не зная тип.

[Igors]

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

Да, в данном случае именно так поставлена задача - какая из 3, и только линейные (матричные) преобразования

Мб кластеризация какими-нибудь классическими методами?

Как-то это звучит "чересчур фундаментально" . Не исключено что задачка-то совсем простая. У меня такая идейка: разбить (отсортировать) все полигоны по плоскостям в которых они лежат. Кстати формально - тоже кластеризация.

1) Как это сделать? (что должно быть ключом в такой мапе. На всякий случай напоминаю - нормали float и точно никогда не равны)

2) Что дальше, как узнать тип и матрицу?

[Disa]

Как-то это звучит "чересчур фундаментально" . Не исключено что задачка-то совсем простая. У меня такая идейка: разбить (отсортировать) все полигоны по плоскостям в которых они лежат. Кстати формально - тоже кластеризация.

Ну, вероятно - классификатор на большом числе вершин скорее всего не очень быстрый будет.

1) Как это сделать? (что должно быть ключом в такой мапе. На всякий случай напоминаю - нормали float и точно никогда не равны)
2) Что дальше, как узнать тип и матрицу?

Тут нужно будет проверять. У меня была идея, что у всех этих фигу должны отличатся соотношения объема к площади, объема к сумме длин ребер. Возможно еще есть какие-то фичи, нужно подумать. Дальше строим наши классы (одним из методов классификации, по двум параметрам, например k-средних http://rcs.chph.ras.ru/Tutorials/classification.htm#Ch3.5).
Карта будет выглядеть как тип объекта : два числа
Дальше тестируем и по мере тестирования улучшаем выборку.

Когда узнали тип объекта - для сферы - масштабирование любого из радиусов. Радиус можно узнать, например, тупо в лоб посчитать расстояния от середины наиболее удаленных полигонов.

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

[V1KT0P]

1) Как это сделать? (что должно быть ключом в такой мапе. На всякий случай напоминаю - нормали float и точно никогда не равны)

2) Что дальше, как узнать тип и матрицу?

Честно не вижу где проблема реализовать один из предложенных способов.
Вот тебе еще один:
1) Берем векторы нормалей и с некоторой погрешностью пытаемся их разделить на группы(группа это минимум две нормали смотрящие в одно направление с определенной погрешностью). Итого:
  - Нет ни одной группы, значит у нас сфера.
  - Есть шесть групп и ни одной свободной нормали, значит у нас куб.
  - Есть две группы и есть свободные нормали, значит у нас цилиндр.
  - Получилось что-то среднее, если уверены что это точно одна из перечисленных фигур, то выбираем тот тип по параметрам к которой ближе всего( Например шесть групп и парочка свободных нормалей это каличный куб ).

2) Зная тип фигуры для матрицы трансформации нам надо знать все-го четыре ключевые точки:
   - Сфера: Берем одну из самых дальних точек от центра и противоположную ей от центра, получается линия. На перпендикулярной плоскости тоже-самое одна из самых дальних точек от центра и противоположная ей. Получаем четыре ключевые точки, также мы знаем где эти точки должны быть. Итог - имеем матрицу трансформации.
   - Куб: <тут текст один в один как для сферы>.
   - Цилиндр: Берем те две группы полигонов для которых мы выделили нормали. Для каждой находим среднюю точку, получается линия. Для этой линии на перпендикулярной плоскости выбираем самую дальнюю точку и противоположную ей. Имеем четыре ключевых точки, а также мы знаем где эти точки должны быть. Итог - имеем матрицу трансформации.

Или тебе прям таки нужен готовый код для копипасты? Или ты супер быструю реалтаймовую прогу пишешь?

[Igors]

Честно не вижу где проблема реализовать один из предложенных способов.

Есть прекрасная формула

Оптимизм * компетентность = константа

Вот тебе еще один:
1) Берем векторы нормалей и с некоторой погрешностью пытаемся их разделить на группы(группа это минимум две нормали смотрящие в одно направление с определенной погрешностью). Итого:

У простейшего куба (6 полигонов) таких 2 нормалей не найдется - все нормали к полигонам смотрят в разные стороны. А если разбивать на треугольники - то наоборот, найдется и у сферы.

Витя, дальше просто не хочу комментировать - все в том же духе. Бездна самонадеянности, но ничего не продумано тщательно, везде дырки. Это только с первого взгляда 3D кажется простым, но это впечатление обманчиво. Ну напр: сколько вертексов имеет простейший кубик?

Ну, вероятно - классификатор на большом числе вершин скорее всего не очень быстрый будет.

Тут нужно будет проверять. У меня была идея, что у всех этих фигу должны отличатся соотношения объема к площади, объема к сумме длин ребер. Возможно еще есть какие-то фичи, нужно подумать. Дальше строим наши классы (одним из методов классификации, по двум параметрам, например k-средних http://rcs.chph.ras.ru/Tutorials/classification.htm#Ch3.5).
Карта будет выглядеть как тип объекта : два числа
Дальше тестируем и по мере тестирования улучшаем выборку.

О боже - уже и объем, и длины ребер Нельзя ли обойтись более простыми средствами? Каждый полигон лежит в какой-то плоскости, уравнение которой задается 4-мя числами (а, b, c, d). Посчитаем сколько всего таких для фигуры. 6 - куб, и матрица готова. А вот сфера/цилиндр хужее - возможно ложное определение за счет того что полигонное представление неточное. Я пока остановился на варианте "считать донышком цилиндра если 6 (и более) полигонов лежат в одной плоскости".

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