| Правила | Регистрация | Пользователи | Поиск | Сообщения за день | Все разделы прочитаны | Справка по форуму | Файлообменник | |
|
Поиск в этой теме |
|
||||
"Плоскость", "объем" - у Вас анализ 3D или это просто такие термины?
|
||||
|
||||
КИПиА Регистрация: 21.03.2005
Tyumen
Сообщений: 1,352
|
Алгоритм работает одинакво и для 3Д и для 2Д. но нужно либо учесть вырождение объема\плоскости в прямоугольник\прямую, либо в случае "плоского" ограничивающего объема дать ему минимальную разбежку по нулевой оси (т.е. сделать совсем чуть чуть неплоским)
Я использую второй вариант, по "плоской" оси разбиение производится небудет, т.к. она всегда будет минимальной |
|||
|
||||
Цитата:
Пока перевариваю......... Могу предложить тем, кому желательны примеры, задачу: находить (создавать) для всего набора линейных элементов все возможные минимальные замкнутые контуры. Контуры точные, полные и все - в отличие от фирменной BOUNDARY, которая к тому же только штучная. Задача вполне реальное решение имеет. Например, FlashPolygons от Delicad. Offtop: Правда, попробовал сегодня свежезагруженную версию FlashPolygons, и такое ощущение, что они что-то так улучшили, что она еле телепается. Опробовал ее в 2010 на файлах с десятками тысяч элементов, и она строила все контуры считанные секунды. А компьютер был послабее, и был XP. Видимо, они ее оптимизировали Во-вторых, она не видит сплайны и 3D элементы. Пользоваться ей можно бесплатно 20 раз. Предполагаю, что в этой задаче процедуры только самые простые: найти все пересечения всех элементов, и на их основе собрать все замкнутые минимальные контуры. Элементы и их части после разбивания на пересечениях, чьи начальные-конечные точки ни к чему не примыкают, игнорируются. Для упрощения сплайны,трехмерные элементы не рассматриваем. Исходные элементы сохраняются в их исходном состоянии. Допустим, добиваемся, чтобы результат получался на 2-3 десятках тысяч элементов из десятков и сотен сегментов каждый за, максимум, 5-7 секунд. |
||||
|
||||
КИПиА Регистрация: 21.03.2005
Tyumen
Сообщений: 1,352
|
>>Делящие плоскости вертикальные? По осям XZ, YZ?
да (еще XY для 3Д случая), ограничвающий объем тоже "выровнен" по осям - т.н. AABB (Axis-Aligned Bounding Box) При этом ограничивающий объем "левого" и "правого" списка можно почесному пересчитать, а можно рассеч плоскостью исходный. Я не пересчитываю, при этом "хватается" лишнее пустое пространство, но для "среднестатистического" чертежа это ИМХО не критично. критично для очень "разряженного" чертежа Поиск пересечений я сегодня организую, если будет свободная минута, для самого элементарного случая - чертеж из N линий. Из спортивного интереса - посмотреть как влияют параметры "дерева" на время нахождения всех пересечений. А вот искать контуры (насколько понимаю это возня с графами) на данный момент мне не интересно и не по зубам)) update: В #37 забыл упомянуть циферки про расход памяти под всё это дело: чертеж тотже, 21250 примитивов, x86_64 сборка для случая с 500 примитивов в ноде выделено памяти под списки примитивов в нодах: 223912 байт выделено памяти под сами ноды: 22042 байт для случая с 10 примитивов в ноде выделено памяти под списки примитивов в нодах: 223912 байт выделено памяти под сами ноды: 702460 байт Странно что количество под списки не меняется, вроде должно увеличиться. Может глючу в замерах, а может связано с тем что колво примитивов не изменилось и как их не раскладывай по разным спискам - в сумме будет одно и тоже Последний раз редактировалось zamtmn, 17.09.2013 в 09:32. |
|||
|
||||
Цитата:
|
||||
|
||||
КИПиА Регистрация: 21.03.2005
Tyumen
Сообщений: 1,352
|
Вроде сделал поиск пересечений, особо не проверял, но с виду работает правильно, даже если и пропускает несколько пересечений, то на общую картину это не влияет - для замера времени пойдет
Для теста соорудил 2 файла, скриншоты с визуализацией сетки (серым сетка, красным - линии) разбиения прилагаю (для случая с 10 примитивами в ноде) regular.dxf - представляет собой регулярную сетку из крестов образованных 2мя короткими линиями, всего 20000 линий, 10000 пересечений. Это идеальный случай - он отлично пространственно разбивается nonregular.dxf - мешанина из 20000 случайных линий сопоставимых по размерам с габаритами чертежа, кол-во пересечений 11559108. Наихудший случай - в разбивку попадает очень мало линий, они слишком длинные и "кучные" тест прилагаю в виде лога последовательного выполнения 2х команд разделенных "-------------------------------------" для разных условий первая RebuildTree строит "дерево" вторая FindAllIntersections собственно ищет пересечения тест проводил для разбиений до 10,100,1000,10000 примитивов в "ноде" (Max in node entities), последний случай (100000) представляет собой фактическое отсутствие разбиения, все примитивы находятся в корневой "ноде", никакого разбития нет пояснения для вывода команд: Цитата:
Цитата:
Цитата:
|
|||
|
||||
Приложите nonregular.dxf здесь или во всем доступное место.
Чтобы использовать как тестовый для разных методов и программ. И на компьютере с какими характеристиками это делалось? Еще интересно посмотреть, как оптимизация влияет на работу программ на небольших файлах. Допустим, элементов на 1000. Последний раз редактировалось АлексЮстасу, 17.09.2013 в 18:55. |
||||
|
||||
КИПиА Регистрация: 21.03.2005
Tyumen
Сообщений: 1,352
|
>>Чтобы использовать как тестовый для разных методов и программ.
Приложил. Я его взял как наихудший из возможных, в реальности так плох небывает. Для тестов нужно чтото реальнеое. >>И на компьютере с какими характеристиками это делалось? i5-2400, 8Gb, Kubuntu 13.04, x86_64 >>Еще интересно посмотреть, как оптимизация влияет на работу программ на небольших файлах. Допустим, элементов на 1000. Давайте файл, посмотрю |
|||
|
||||
|
||||
|
||||
КИПиА Регистрация: 21.03.2005
Tyumen
Сообщений: 1,352
|
мешанину из 1000 примитивов нужно на компе послабже тестить
файл приложен - 1172 линии, 22067 пересечения, картинка для "разбиения" "по 10" приложена. лог для случаев 10, 100, 1000, 2000(без разбиения) Цитата:
upd: было бы интересно услышать результаты для приложенных файлов полученные штатными ARX средствами на сопоставимом компьютере Последний раз редактировалось zamtmn, 17.09.2013 в 20:51. |
|||
|
||||
Вы делаете пересечения, т.е. разбиваете элементы или только их находите?
Дело в том, что просто поиском пересечений никакие готовые программы не занимаются. Их находят, и что-то с ними делают - разбивают элементы в них, вставляют что-то и пр. Т.е. время затрачивается еще и на это. Если Вы их только находите, то сравнивать скорости программ невозможно. |
||||
|
||||
КИПиА Регистрация: 21.03.2005
Tyumen
Сообщений: 1,352
|
Только нахожу пересечения и получаю информацию какая линия где пересекается, т.е. грубо говоря в каких точках каждую линию нужно резать. Порезат по этой информации линии или вставить туда чтото в принципе несложно, но это другая тема - тут геометрическая оптимизация непоможет
|
|||
|
||||
Цитата:
Цитата:
Запустил этот файл на разбиение в пересечениях штатным инструментом Autocad Map 3D - Drawing cleanup-Break intersections. На неплохой машине, и машине немного похуже. Оба раза прождал минут сорок-пятьдесят - так и закрывал Автокад, не дождавшись. Запустил здешней лисп-программой от VVA - BreakObjects22а. Результат такой же - тоже закрыл Автокад прерыванием работы через час молотьбы. Пока что получается, что Ваша программа и без всякой оптимизации работает с однозначно фантастической скоростью. Либо Автокад тормозит на собственно разбивании, на создании новых элементов. В этих файлах у элементов отрицательные координаты. Если меньший чертеж передвинуть в положительные координаты, то Drawing cleanup-Break intersections сделала все пересечения примерно за 8 секунд. А лисп BreakObjects22а по-прежнему не может завершить обработку. На большем чертеже и Drawing cleanup-Break intersections тоже не может закончить. Как-то непонятно... Тем более, что файлы я перед этим полечил, почистил, перекопировал содержимое в новый файл на основе штатного шаблона. Последний раз редактировалось АлексЮстасу, 18.09.2013 в 05:12. |
||||
|
||||
Moderator
LISP, C# (ACAD 200[9,12,13,14]) Регистрация: 25.08.2003
С.-Петербург
Сообщений: 39,833
|
АлексЮстасу, не путай нахождение пересечений и выполнений операций с примитивами. Первое может занимать во много раз меньше времени, чем второе.
__________________
Моя библиотека lisp-функций --- Обращение ко мне - на "ты". Все, что сказано - личное мнение. |
|||
|
||||
КИПиА Регистрация: 21.03.2005
Tyumen
Сообщений: 1,352
|
Приделал установку примитива "точка" в найденных точках пересечения, в выводе появился параметр Placing points - соответственно время затраченное на расстановку точек.
Результат для regular.dxf: Цитата:
Цитата:
|
|||
|
||||
Регистрация: 18.12.2010
Сообщений: 5,051
|
"Процесс автоматически грохается сторожем памяти на этапе расстановки точек" - поэтому я и говорю, что надо использовать Пространственную БД.
1. Пространственный индекс - то же дерево или лучше 2. SQL позволяет выполнять выборку нужных объектов 3. Сервер БД сам заморачивается с памятью Нефиг изобретать велосипед, когда есть готовое решение... |
|||
|
||||
КИПиА Регистрация: 21.03.2005
Tyumen
Сообщений: 1,352
|
>>Нефиг изобретать велосипед, когда есть готовое решение...
Я неспорю что это всё есть, но пожалуйста озвучте циферки результатов. Иначе это не готовое решение а "чтото там есть" и "вроде как для этого и задумывалось". Свои поделки я никому не навязываю как готовое решение, просто мне это интересно. update: Приделал резалку по точкам пересечения. результаты для nonregular2.dxf с коментариями к новым параметрам: Цитата:
Последний раз редактировалось zamtmn, 18.09.2013 в 15:37. |
|||
|
||||
Такие чисто геометрические процессы, как разбивать пересечения, создавать контуры, находить попавшее в контуры и пр. больше всего нужны для первичной подготовки данных. Еще сугубо графических - линий, блоков, текстов и пр. В том числе для сбора и подготовки сырья для наполнения пространственных БД. Которую технологично делать в голых CADах или в них же, но дополненных для подготовки данных для этих пространственных БД. В такие БД нельзя же загружать неподготовленное соответствующим образом сырье - без топологической коррекции и пр. Поэтому программки типа разбивания пересечений и пр. нужны в первую очередь еще на уровне собственно CADов.
Против возможностей самих пространственных БД совершенно ничего не имею! Прямо наоборот. Все, кто просил примеры и конкретные задачи, куда-то испарились У Вас там в сумме и полсекунды не набирается. Время на отрисовку на экране как-то влияет? Или Вы обрабатываете не загруженные файлы? На чем у Вас написано? В целом же как-то несравнимо у Вас все быстро и без оптимизаций. |
||||
|
||||
КИПиА Регистрация: 21.03.2005
Tyumen
Сообщений: 1,352
|
Функция разбиения сырая, но не неоптимизированная. Там отсутствуют проверки на всякие закрытые слои, обрабатывается вся модель, а не выбранные примитивы... и прочие "мелочи". Поиск пересечений оптимизировать наврятли получится, разве что обнаружится какойнибудь глобальный косяк в алгоритме. Время создания-изменения примитивов возрастет раза в полтора-два после заворачивания в undo\redo. Наверно можно будет выиграть несколько процентов "подтасовывая" данные приготавливаемые к последующей нарезке - но кординально оптимизировать там нечего
Написано на паскале, в виде команды для самодельной кад программы, тоже написанной на паскале. Обрабатывается загруженный файл, во время обработки никаких отрисовок не происходит, программа "повисает" на время выполнения команды. |
|||
|
||||
|
||||
|
Опции темы | Поиск в этой теме |
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Документация Проектировщику на Torrents | DEM | Разное | 262 | 24.02.2024 17:19 |
Жилые и общественные здания: краткий справочник инженера-конструктора. Под ред. Ю.А. Дыховичного и В.И. Колчунова. 2011 (Впечатления и отзывы). | Armin | Поиск литературы, чертежей, моделей и прочих материалов | 19 | 22.03.2018 15:41 |
Порекомендуйте литературу для повышения квалификации(грунты, геотехника) | acid | Поиск литературы, чертежей, моделей и прочих материалов | 6 | 13.05.2015 22:14 |
Случайный эксцентриситет | p_sh | Прочее. Архитектура и строительство | 14 | 22.07.2009 11:32 |
Защита от распространения большого числа dwg | E.D. | AutoCAD | 24 | 21.11.2008 09:02 |