Задача такая: дана триангулированная поверхность , требуется переразбить её так, чтоб получить поверхность, представленную четырёхугольниками. Подскажите алгоритм или полезную ссылку

А>Задача такая: дана триангулированная поверхность , требуется переразбить её так, чтоб получить поверхность, представленную четырёхугольниками. Подскажите алгоритм или полезную ссылку

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

Здравствуйте, WinterMute, Вы писали:


WM>Какие требования к четырёхугольнику (это должен быть квадрат, прямоугольник, что нибудь еще?). Если нет никаких дополнительных требований, добавь к каждому треугольнику точку совпадающую с одной из вершин.

Это должен быть приблизительный прямоугольник. "Приблизительный" — то есть возможно некоторое отклонение от идеального прямоугольника, но относительно незначительное.

А допускается ли погрешность?
И если да, то какая?

Здравствуйте, Chez, Вы писали:

C>А допускается ли погрешность?
C>И если да, то какая?

Погрешность в отклонении четырёхугольников от прямоугольников — где-то в пределах 10% . Исходная поверхность и получившаяся в результате переразбиения должны совпадать с максимально возможной точностью.

А>Погрешность в отклонении четырёхугольников от прямоугольников — где-то в пределах 10% .
Если 10% — в количествнном (а не качественном) отношении, то я могу предложить кое-что в общих словах

А>Исходная поверхность и получившаяся в результате переразбиения должны совпадать с максимально возможной точностью.
Максимаьную точность можно достугнуть за счёт кол-ва результирующих прямоугольников. Но это также увеличит кол-во данных, требующихся для описания поверхности

1) Завести коэф-т погрешности N
2) Объединить соседние треугольники, лежащие в одной плоскости (в одной плоскости с учётом погрешности N) — в полигоны. Чем больше N, тем больше треугольников сольются в полигоны. Если по уму, то это долго — и заслуживает отдельной темы, хотя решения есть
3) Разбить каждый из получившихся полигонов

Здравствуйте, Chez, Вы писали:

А>>Погрешность в отклонении четырёхугольников от прямоугольников — где-то в пределах 10% .
C>Если 10% — в количествнном (а не качественном) отношении, то я могу предложить кое-что в общих словах

А>>Исходная поверхность и получившаяся в результате переразбиения должны совпадать с максимально возможной точностью.
C>Максимаьную точность можно достугнуть за счёт кол-ва результирующих прямоугольников. Но это также увеличит кол-во данных, требующихся для описания поверхности

C>1) Завести коэф-т погрешности N
C>2) Объединить соседние треугольники, лежащие в одной плоскости (в одной плоскости с учётом погрешности N) — в полигоны. Чем больше N, тем больше треугольников сольются в полигоны.
Если по уму, то это долго — и заслуживает отдельной темы, хотя решения есть
C>3) Разбить каждый из получившихся полигонов

угу, в итоге предполагается получить смешанную картину с треугольниками и четырёхугольниками. и пункт
4) Думать, что делать с оставшимися треугольниками

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

У меня данные собраны в массив треугольников, каждый из которых "знает" примыкающих к нему соседей. Но боюсь, что простой перебор этого массива и объединение с первым попавшимя соседом, удовлетворяющим условию погрешности — не самый эффективный выход.

А>угу, в итоге предполагается получить смешанную картину с треугольниками и четырёхугольниками. и пункт
А>4) Думать, что делать с оставшимися треугольниками

А>А вот возможно ли (и как??) свести к минимуму количество оставшихся после переразбиения треугольников? (имеется в виду, не увеличивая коэффициент погрешности).
Если треугольники разбиваются на четырёхугольники в достаточно большом количестве последних, то можно попробовать "притянуть за уши" координаты вершин прямоугольников, лежащих на одной и той же грани — т.е. просто соединить их.

А>У меня данные собраны в массив треугольников, каждый из которых "знает" примыкающих к нему соседей. Но боюсь, что простой перебор этого массива и объединение с первым попавшимя соседом, удовлетворяющим условию погрешности — не самый эффективный выход.

Вообще, если делать по этой схеме, то вместо одной погрешности может набраться добрый десяток коэффициентов, которые, возможно, придётся подбирать эксперементально для каждой поверхности...

C>Если треугольники разбиваются на четырёхугольники в достаточно большом количестве последних, то можно попробовать "притянуть за уши" координаты вершин прямоугольников, лежащих на одной и той же грани — т.е. просто соединить их.

я хотел написать

C>Если полигоны разбиваются на четырёхугольники в достаточно большом количестве последних, то можно попробовать "притянуть за уши" координаты вершин прямоугольников, лежащих на одной и той же грани — т.е. просто соединить их.

Заданная поверхность это поверхность функции? Т.е. каждой паре (x,y) соответствует только один z?

Если да, то можно сделать так:

Плоскость X,Y разбиваешь сеткой M*N, для каждого узла сетки вычисляешь координату Z, по четырём соседним узлам строишь прямоугольник. Правда, получившиеся четырёхугольники будут прямоугольниками только в проекции X,Y, не знаю, устроит тебя это или нет.

Какие еще проблемы: Придётся перебирать все полигоны, чтобы вычислить, с каким именно пересекается вертикальная прямая проведённая из узла новой решётки, это долго. Если время критично, придётся сортировать все полигоны по х,y координатам, или придумывать что то еще. Как выяснить принадлежит ли точка на плоскости треугольнику надеюсь знаешь (если нет, поищи по форуму, такой вопрос уже был).

Здравствуйте, WinterMute, Вы писали:

WM>Заданная поверхность это поверхность функции? Т.е. каждой паре (x,y) соответствует только один z?

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

WM>Если да, то можно сделать так:

WM>Плоскость X,Y разбиваешь сеткой M*N, для каждого узла сетки вычисляешь координату Z, по четырём соседним узлам строишь прямоугольник. Правда, получившиеся четырёхугольники будут прямоугольниками только в проекции X,Y, не знаю, устроит тебя это или нет.

Для поверхности с небольшой кривизной это, в принципе, несущественно. Приблизительно они останутся прямоугольниками. Но, думаю, если проекционная сетка однородная можно сделать вот что:
сравнить отношение (расстояние от вертикали, соединяющей узел сетки с поверхностью)/(такое же расстояние в соседних узлах). Если это отношение больше или меньше определённой допустимой величины, оно укажет на резкое изменение кривизны, и сетку в этой области можно сделать помельче. Если в этой идее есть за что покритиковать — не поленитесь плииз.

А>Для поверхности с небольшой кривизной это, в принципе, несущественно. Приблизительно они останутся прямоугольниками. Но, думаю, если проекционная сетка однородная можно сделать вот что:
А>сравнить отношение (расстояние от вертикали, соединяющей узел сетки с поверхностью)/(такое же расстояние в соседних узлах). Если это отношение больше или меньше определённой допустимой величины, оно укажет на резкое изменение кривизны, и сетку в этой области можно сделать помельче.

Критиковать нечего, можно только добавить: 1) cравнивать высоты узлов нужно парами, т.е: четырёхугольник ABCD это почти прямоугольник если есть две пары похожих соседних высот. Уменьшать размер сетки в области, где изменения слишком велики, лучше всего разбивая текущий прямоугольник на 4/9/16/... частей.

Здравствуйте, Аноним, Вы писали:

А>Задача такая: дана триангулированная поверхность , требуется переразбить её так, чтоб получить поверхность, представленную четырёхугольниками. Подскажите алгоритм или полезную ссылку

Возьмём правильный тетраэдр. Можно эту поверхность (пусть и без нижней грани) прежставить прямоугольниками? ИМХО только очень большим количеством (> 50).

Далее, четырёхугольник на плоскости и четырёхугольник в пространстве это не одно и то же. Что такое погрешность в 10%? Не ясно как эти 10% применять к перекручениванию (как стирку) плоского четырёхугольника
Вполне очевидно, что придётся использовать четырёхугольники не все вершины которых лежат в одной плоскости.

Короче я представляю себе что-то такое.


Тут довольно большое значение имеет и нап начальной триангуляции. Какая она?

(сорри за вчерашнюю анонимность)

Здравствуйте, adontz, Вы писали:

A>Далее, четырёхугольник на плоскости и четырёхугольник в пространстве это не одно и то же. Что такое погрешность в 10%? Не ясно как эти 10% применять к перекручениванию (как стирку) плоского четырёхугольника

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

A>Вполне очевидно, что придётся использовать четырёхугольники не все вершины которых лежат в одной плоскости.

Как раз этого нало избежать.

A>Тут довольно большое значение имеет и нап начальной триангуляции. Какая она?

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

Здравствуйте, Cub, Вы писали:

A>>Вполне очевидно, что придётся использовать четырёхугольники не все вершины которых лежат в одной плоскости.
Cub>Как раз этого нало избежать.

Возвращаемся к проблеме тетраэдра. Нельзя(!) поверхность тетраэдра разбить на невырожденные четырёхугольники.

Здравствуйте, Cub, Вы писали:

Cub>(сорри за вчерашнюю анонимность)

Cub>Здравствуйте, adontz, Вы писали:

A>>Далее, четырёхугольник на плоскости и четырёхугольник в пространстве это не одно и то же. Что такое погрешность в 10%? Не ясно как эти 10% применять к перекручениванию (как стирку) плоского четырёхугольника

Cub>погрешность в означает не принадлежность вершин одной плоскости в пределах 10%, а то, что четырёхугольник ВСЕ вершины которого лежат в одной плоскости, может иметь углы, не являющиеся прямыми. Но получить вытянутянутый параллелограмм или бесформенную трапецию весьма нежелательно.

A>>Вполне очевидно, что придётся использовать четырёхугольники не все вершины которых лежат в одной плоскости.

Cub>Как раз этого нало избежать.

A>>Тут довольно большое значение имеет и нап начальной триангуляции. Какая она?

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

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

Здравствуйте, adontz, Вы писали:

A>Возвращаемся к проблеме тетраэдра. Нельзя(!) поверхность тетраэдра разбить на невырожденные четырёхугольники.

1) Поверхность тетраэдра разбивается на невырожденные четырёхугольники, но при этом происходит некоторое изменение первоначальной формы. В частности, вершины могут оказаться "срезанными", а сам срез будет представлен несколькими четырёхугольниками.

2) Как уже говорилось, получение смешанной картины из 3- и 4-угольников допустимо — так, например, если поверхность обладает какими-либо сложными элементами с резко меняющейся кривизной, трудно обойтись полигонами, близкими к прямоугольнику. Вопрос в том, как переразбить её таким образом, чтоб число треугольников было МИНИМАЛЬНО.