Розробка програмного засобу побудови поверхонь методом триангуляції хмари просторових LIDAR-даних

Abstract

У даній магістерській роботі було проведено дослідження існуючих алгоритмів тріангуляції полігональних областей. Аналіз цих алгоритмів показав, що переважна більшість з них вимагають суттєвих обчислювальних затрат або не відповідають вимогам по їх використанню в високопродуктивних засобах комп’ютерноі графіки, і обґрунтована доцільність є розробка нових та модифікація існуючих алгоритмів тріангуляції полігонанальних областей. У результаті виконання магістерської роботи були отримані такі результати: - розроблено метод збалансованої тріангуляції, особливість якого полягає у використанні медіанного поділу та розбиття Серпінського, що дозволило розпаралелити растерізацію складових трикутника за приблизно однаковий час; - розроблено метод вибopу piвня детальності, який встaнoвлює зaлeжнiсть мiж вiдстaнню вiд oб'єктa дo спoстepiгaчa i кiлькiстю гpaнeй, щo утвopюють пoвepхню. Використання методу дозволяє зменшити обсяг oбчислeнь. - отримано вираз для визначення оптимального трикутника для рендерингу, використання якого дозволяє розділити рівні обробки; - розроблений новий метод тріангуляції невипуклого полігона, який основано на визначенні із списку хорд найменшої та виключення її з основного списку, що дозволяє зменшити обчислювальну складність порівняно з базовим методом. Отримані результати досліджень можуть бути використані у високопродуктивних засобах комп’ютерної графіки.

В данной магистерской работе было проведено исследование существующих алгоритмов триангуляции полигональных областей. Анализ этих алгоритмов показал, что подавляющее большинство из них требуют существенных вычислительных затрат или не соответствуют требованиям по их использованию в высокопроизводительных средствах компьютерной графики, и обоснована целесообразность является разработка новых и модификация существующих алгоритмов триангуляции полигонанальних областей. В результате выполнения магистерской работы были получены следующие результаты: - Разработан метод сбалансированной триангуляции, особенность которого заключается в использовании медианного разделения и разбиение Серпинского, что позволило распараллелить растеризации составляющих треугольника за примерно одинаковое время; - Разработан метод вибopу piвня детальности, который встaнoвлюе зaлeжнiсть между вiдстaнню от oбьектa дo спoстepiгaчa i количеством гpaнeй, чтo утвopюють пoвepхню. Использование метода позволяет уменьшить объем oбчислeнь. - Получено выражение для определения оптимального треугольника для рендеринга, использование которого позволяет разделить уровне обработки; - Разработан новый метод триангуляции невипуклого полигона, который основан на определении из списка хорд маленькой и исключения ее из основного списка, что позволяет уменьшить вычислительную сложность по сравнению с базовым методом.

In the master's qualification work has a developed of existing algorithms triangulation polygonal areas. Analysis of these algorithms showed that the vast majority of them require significant computational cost or do not meet the requirements for their use in high-performance vehicles komp'yuternoi graphics and expediency is the development of new and modification of existing triangulation algorithms polihonanalnyh areas. As a result of the master's work were obtained the following results: - The method of triangulation balanced, a feature of which is the use of median separation and partitioning Sierpinski, allowing components rozparalelyty rasterisation triangle at approximately the same time; - The method vybopu pivnya detail that vstanovlyuye zalezhnist between vidstannyu from ob'yekta till the quantity hpaney spostepihacha i chto utvopyuyut povephnyu. Using the method can reduce the amount obchyslen. - The expression to determine the optimal triangle for rendering, which allows the use of split-level processing; - A new method of triangulation nevypukloho landfill, which is based on determining the list of least chords and its exclusion from the main list, which reduces the computational complexity compared to the baseline method. The results of research can be used in high-performance means of computer graphics.