Translate this page:
Please select your language to translate the article


You can just close the window to don't translate
Library
Your profile

Back to contents

Software systems and computational methods
Reference:

Formation of displacement curves with the identification of their non-working areas

Myasoedova Tatiana Mikhailovna

Senior Lecturer, Department of Engineering Geometry and CAD, Omsk State Technical University

644050, Russia, Omskaya oblast', g. Omsk, pr. Mira, 11

mtm44mtm44@mail.ru
Other publications by this author
 

 

DOI:

10.7256/2454-0714.2020.1.32235

Received:

21-02-2020


Published:

09-04-2020


Abstract: The object of research is the shaping of a family of displacement curves used in designing the path of a tool that processes pocket surfaces. The subject of the study is the working displacement curves in the case of multiply connected areas. Working displacement curves are lines from which non-working sections have been removed. Non-working areas include self-intersecting loops of displacement curves and sections formed when intersecting displacement curves of opposing fronts. The paper presents methods for analyzing and cutting off non-working sections for cases of self-intersection and intersection of displacement curves of opposing fronts. The spatial geometric model of the formation of displacement curves is based on the cyclographic method of displaying space. As a tool for detecting non-working areas for the case of opposing fronts, a method of a testing beam is proposed. In the case of self-intersections of the displacement curves, non-working sections are cut off by the parameter of these lines at the points of self-intersection. The novelty of the study lies in the fact that the obtained mathematical model of the formation of displacement curves for multiply connected regions with contours of complex handicap curves makes it possible to obtain parametric equations of working lines at the output of the computational algorithm in a more reliable and simple way. This greatly simplifies the solution to the problem of automated design of the trajectory of the cutting tool. A comparative assessment of the proposed method of shaping a family of displacement curves with cutting off non-working sections and known methods using the distance function is performed.


Keywords:

Offset Curve, Medial Axis, Medial Axis Transformation, cyclographic mapping, multiply-connected domain, parametric representation of the curve, trimming, shaping, analytical method, curv of complex shap


1. Введение

В CAD/CAM системах расчет траектории режущего инструмента является важной задачей. Карманные поверхности, как правило, обрабатываются по контурно-параллельном траекториям. Для расчета траектории движения инструмента, обрабатывающего эти поверхности, необходимо строить семейство контурно-параллельных линий, т.е. кривых смещения OC (“Offset Curve”) исходного контура карманной поверхности. Семейства OC многосвязных областей образуются, когда область кармана включает в себя острова. Оптимизация семейства OC многосвязных областей сопряжена с анализом OC и удалением нерабочих участков линий семейства OC.Нерабочие участки линий семейства ОС – это линии– шумы. Они формируются как петли самопересечений ОС связных областей (локальные пересечения ОС) и как участки, которые образуются при пересечении встречных фронтов ОС (глобальные пересечения ОС) многосвязных областей (рисунок 1).

0000001

а)

б)

в)

Рисунок 1. Построение семейства ОС для многосвязной области: а) локальные пересечения семейства ОС, б) глобальные пересечения семейства ОС, б) итоговый результат.

Анализ существующих методов оптимизации семейства OC многосвязных областей по критерию отсутствия линии–шумов позволяет выделить следующие основные направления решения задачи оптимизации:

1.1. Анализ и отсечение нерабочих участков линий семейства OC по функции расстояний

Выявление нерабочих участков линий семейства OC сводится к решению полиномиальных уравнений. Если кривая исходного контура многосвязной области имеет порядок выше второго, для отыскания корней приходится решать уравнения высоких степеней, что приводит к не простой вычислительной задаче [1].

1.2. Анализ и отсечение нерабочих участков линий семейства OC с использованием MAв качестве инструмента отсечения

В работах [2-4] задача этого направления решается на плоскости для односвязной области с применением MA(“Medial Axis”). На плоскости каждая точка MA является центром диска максимального радиуса, вписанного в граничный контур. МА в сочетании с функцией радиуса называется “MedialAxisTransformation (MAT). Анализ и отсечение нерабочих участков OC осуществляется с применением сложного математического аппарата, вычислительные алгоритмы не устойчивы и имеют высокую временную сложность. Алгоритмы нахождения МA для области, граница которой состоит из дуг окружностей и отрезков прямых работают стабильно. Однако, если граница области имеет сложную криволинейную форму, поиск МА становится сложной задачей [2-11].

В работе [12] в качестве граничных линий области используются PH-curves (Pythagorean-Hodographcurves). Семейство ОС c шагом d относительно граничных кривых PH определяется по уравнению: 0000002, в котором 0000003 исходный контур, 0000004 функция расстояния по нормали. В работе [13] на основе свойств PH-curves линии семейства ОС представлены как множество рациональных кривых. Представление PH-curves в метрике Минковского вместе с леммой о разложении области делает вычисляемым процесс отсечения линий семейства ОС для многосвязной области с криволинейным контуром. Процедура для получения усеченных линий семейства ОС, то есть ОС без линий-шумов, осуществляется в терминах функции радиуса кривизны PH-curves и MAT. Это позволяет получать семейства ОС в виде рациональных кривых Безье, поскольку единичная нормаль 0000006 имеет рациональную зависимость от параметра кривой t.

В работах [14-16] представлен алгоритм попарного смещения для замкнутых двумерных кривых точечной последовательности для многосвязной области с криволинейным контуром, состоящим из PS-curves (Point-Sequence curves). В этом подходе петли самопересечений и пересечения встречных фронтов удаляются по тесту попарного обнаружения нерабочих участков линий семейства ОС. Алгоритм может работать за линейное время. Однако для предлагаемого алгоритма входными данными являются точечные последовательности. Предложенный алгоритм работает только с классом кривых PS, что ограничивает его возможности.

В работе [15] предложен алгоритм, который может автоматически соединять острова с внешним контуром на ближайшем расстоянии. Но общее время расчета минимального расстояния между двумя кривыми зависит от общего количества кривых, включая контур области и контуры островов. В работе [16] семейства OC всех островов и OC контура области объединяют в единую связную PS-кривую с помощью триангуляции Делоне. Предложенные алгоритмы работают за почти линейное время, но результат работы предложенных алгоритмов представляет собой точечные данные.

Из краткого обзора следует очевидная необходимость в разработке модели формообразования семейства ОС с более простыми алгоритмами отсечения нерабочих участков для многосвязных областей с криволинейными контурами.

2. Постановка задачи

Предложить геометрическую модель формообразования семейства ОС с линейными алгоритмами отсечения их нерабочих участков.

3. Геометрическая модель формообразования семейства OC на основе циклографического метода отображения

3.1. Анализ и отсечение нерабочих участков встречных линий семейств OC контура области и контуров островов

В концепции циклографического метода [17] формообразования семейства ОС получаются путем рассечения α-поверхностей пучком горизонтальных плоскостей вдоль оси z с шагом zj=const. Линии сечений образуют семейства LOC (“LevelOffsetCurves) относительноостровов и контура области, принадлежащих одной плоскости уровня в пучке плоскостей. Семейства ОС образуются путем ортогонального проецирования семейства LOC на плоскость z=0 (рисунок 2). Для определения нерабочих участков линий семейства OCвыполняется анализ семейств LOC контура области и LOC встречных контуров островов. Линии семейства LOC в плоскостях пучка пересекаются в точках 00000007 (рисунок 2а). Точки Aj делят линии семейства LOC на рабочие и нерабочие участки. Линия MAT в циклографической модели –этопространственная кривая, которая образуется в результате попарного пересечения α-поверхностей, построенных по составным контурам области и островов в ней. Линия MAT, α-поверхности, построенные по составным контурам области и островов, образуют в пространстве α-оболочку (рисунок 3а). На α-оболочке формируются рабочие участки линий семейства LOC в плоскостях своего уровня. Если участок линии не попадает на α-оболочку, то он нерабочий. α-оболочка, как геометрический объект, не моделируется, но используется для определения признаков принадлежности ейучастков линий семейства LOC.

0000008

а)

б)

Рисунок 2. Построение семейства ОС для многосвязной области: a) последовательность построения семейства OC; б) формирование LOC.

Точки делят линии семейства LOCна участки. Для анализа и выявления рабочих и нерабочих участков предлагается в качестве инструмента использовать тестирующий луч. Работу тестирующего луча продемонстрируем на примере. Для анализа рассматриваются семейство LOC пересекающихся α-поверхностей контура области и контура острова в каждой плоскости пучка горизонтальных плоскостей (рисунок 3б).

0000009

а)

б)

в)

Рисунок 3. Фрагмент работы тестирующего луча: a) а-оболочка, б) формирование семейств LOC, в) отсечение нерабочего участка линии семейства LOC.

Линии семейств LOCконтура и LOCострова пересекается в точках 1 и 2. Выполним анализ линии семейства LOC острова. Эта линия в точках пересечения разделяется на участки (1-2) и (2-1). Выбрав направление обхода этой линии, например,по часовой стрелке, анализируем участки (1-2) и (2-1). Рассмотрим участок (1-2). Проведем тестирующий луч r1 из любой точки участка (1-2). Луч r1 пересекает линию семейства LOC контура области в одной точке, значит участок (1-2) находится в зоне, ограниченной линией семейства LOCконтура области. Следовательно, участок (1-2) принадлежит α-оболочке и поэтому он является рабочим участком. Рассмотрим участок (2–1). Проведем тестирующий луч r2 из любой точки участка (2-1). Луч r2 пересекает линию семейства LOCконтура области в двух точках. Следовательно, участок (2-1) не находится в зоне, ограниченной линией семейства LOC контура области. Поэтому участок (2-1) не принадлежит α-оболочке. Участок (2-1) – нерабочий и подлежит отсечению.

Анализу подвергаются все возможные пересечения линий семейств LOC встречных фронтов с отсечением нерабочих участков. В общем случае, если тестирующий луч, проведенный из любой точки участка линии семейства LOC, имеет нечетное количество точек пересечения с линией семейства LOC встречного фронта, то участок принадлежит α-оболочке. Следовательно, он рабочий участок. Если тестирующий луч, проведенный из любой точки участка линии семейства LOC, имеет четное количество точек пересечения, либо не имеет пересечений с линией семейства LOC встречного фронта, то участок не принадлежит α-оболочке поэтому он нерабочий участок.

В работе [18] приведен укрупненный алгоритм анализа глобальных пересечений линий семейства ОС.

3.2. Анализ и отсечение петель самопересечения линий семейства LOC.

Петли самопересечения образуются в том случае, когда эволюта, участвующая в формировании α–поверхности, имеет особую точку (рисунок 4а). Точки самопересечения Aj определяются из уравнения 0000010, где ta и tb– значение параметра t i-го сегмента 0000011 контура области или контура острова, где 0000012 (решением указанного векторного уравнения являются два корня ta=a и tb=b. Тогда для устранения петли самопересечения выполняем разбивку линии семейства LOC на три участка с параметрами 0000013. Участок линии семейства LOC с параметром 0000014 отсекается. Рабочий участок линии семейства LOC составляется из двух сегментов 0000015.

0000016

а)

б)

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

В работе [18] подробно описан способ анализа локальных пересечений на основе циклографического метода отображения. Следует отметить, что входными данными предлагаемого алгоритма являются массивы точек контуров области и островов. Дискретное множество точек интерполируется замкнутой кривой линией. Интерполяция может выполняется сегментами кривых Безье третей степени, дробно-рациональными кривыми Безье второй степени, либо по массиву точек строится обвод из сегментов кривых второго порядка [19].

Выходными данными алгоритма являются параметрические уравнения рабочих линий семейств OC:

000100

где параметрические уравнения, 1-го сегмента линии OC первого острова с параметром 000108 в j-ой плоскости уровня:

000101

параметрические уравнения, последнего сегмента линии OC первого острова с параметром 000109 в j-ой плоскости уровня:

000103

параметрические уравнения, первого сегмента линии OC последнего острова с параметром 000110 в j-ой плоскости уровня:

000104

параметрические уравнения, последнего сегмента линии OC последнего острова с параметром 000111 в j-ой плоскости уровня:

000105

параметрические уравнения, 1-го сегмента линии OC контура области с параметром 000112 в j-ой плоскости:

000106

параметрические уравнения, последнего сегмента линии OC контура области с параметром 000113 в j-ой плоскости:

000107

где j– номер плоскости в пучке горизонтальных плоскостей; N=1,2,…– номер острова; n=1,2,… – номер криволинейного сегмента в контуре области или острова; 000115– параметр n-го криволинейного сегмента в контуре N-го острова; tn –параметр n-го криволинейного сегмента области.

4. Обсуждение результатов

Авторами работы выполнено сравнение предложенного метода оптимизации семейств OC по критерию отсутствия нерабочих участков с методом, близким ему по логике выявления этих участков и основанном на функции расстояния [12]. Сравнительный анализ методов показал определенные преимущества предложенного метода. Метод оптимизации с использованием функции расстояния при исходных данных со сложными контурами области и островов ведет к вычислению корней высоких степеней, что ограничивает возможности этого метода. Предложенный авторами метод позволяет решить задачу оптимизации для многосвязных областей с контурами кривых сложной форы. Он позволяет получать на выходе вычислительного алгоритма параметрические уравнения рабочих линий семейств ОС. Это существенно упрощает решение задачи автоматизированного проектирования траектории режущего инструмента.

5. Выводы

Основная проблема предложенного метода оптимизации для семейств ОС – это подготовка исходных данных. В работе для формирования исходных контуров области и островов использованы несколько типов кривых: кривые Безье третей степени, дробно-рациональные кривые Безье второй степени, кривые второго порядка. Очевидно, что использование PH-кривых для формообразования исходных контуров позволит усовершенствовать предложенный метод оптимизации семейств ОС.

References
1. Farouki, R .T. Pythagorean-Hodograph Curves: Algebra and Geometry Inseparable. Berlin: Heidelberg Springer Verlag, 2008. – 732 p.
2. Blum, H. A transformation for extracting new descriptors of shape, in Models for the Perception of Speech and Visual Form. Cambridge: MIT Press, 1967. – 380 p.
3. Persson, H. NC machining of arbitrary shaped pockets. // Computer Aided Design, 1978. – 3(10). – P. 169–174.
4. Lee, D. Medial axis transformation of a planar shape. // IEEE Transactions on Pattern Analysis and Machine Intelligence, 1982. – 4(4). – P. 362–369.
5. Srinivasan, V. and Nackman, L. R. Voronoi diagram for multiply-connected polygonal domains I: Algorithm. // IBM Journal of Research and Development, 1987. – 31(3). – P. 361–372.
6. Choi, H. I., Choi, S. W. and Moon, H. P. New algorithm for medial axis transform of plane domain. // Graphical Models and Image Processing, 1997. – 59 (6). – P. 463–483.
7. Kim, D., Hwang, I. and Park, B. Representing the Voronoi diagram of a simple polygon using rational quadratic Bezier curves. // Computer Aided Design, 1995. – 27(8). – P. 605–614.
8. Held, M. Voronoi diagram and offset curves of curvilinear polygons. // Computer Aided Design, 1998. – 30(4). – P. 287–300.
9. Choi, H. I., Han, C. Y., Moon, H. P., Roh, K. H. and Wee, N. S. Medial axis transform and offset curves by Minkowski Pythagorean hodograph curves. // Computer Aided Design, 1999. – 31(1). – P. 59–72.
10. Held, M., Lukács, G. and Andor, L. Pocket machining based on contour-parallel tool paths generated by means of proximity maps. // Computer Aided Design, 1994. – 26(3). – P. 189–203.
11. Cao, L. and Liu, L. Computation of medial axis and offset curves of curved boundaries in planar domain. // Computer Aided Design, 2008. – 40(4). – P. 465–475.
12. Farouki, R. T. and Nittler, K. M. Efficient high-speed cornering motions based on continuously-variable feedrates. I. Real-time interpolator algorithms. // The International Journal of Advanced Manufacturing, 2016. – 87(9-12). – P. 3557–3568.
13. Kim, H. C. Tool path generation for contour parallel milling with incomplete mesh model. // International Journal of Advanced Manufacturing Technology, 2010. – №48. – P. 443–454.
14. Park, S. C. and Choi, B. K. Uncut free pocketing tool-paths generation using pair-wise offset. // Computer Aided Design, 2001. – №33. – P. 739–746.
15. Wong, T. N., Wong, K. W. NC toolpath generation for arbitrary pockets with islands. // The International Journal of Advanced Manufacturing, 1996. – №12. – P. 174–179.
16. Zhiwei, L., Jianzhong, F. and Wenfeng, G. A robust 2D point-sequence curve offset algorithm with multiple islands for contour-parallel tool path. // Computer Aided Design, 2013. – 45(3). – P. 657–670.
17. Panchuk, K. L. Tsiklograficheskaya nachertatel'naya geometriya : monografiya / K. L. Panchuk, N. V. Kaigorodtseva; Minobrnauki Rossii, OmGTU. – Omsk : Izd-vo OmGTU, 2017. – 232 s.
18. Myasoedova ,T. M. and Panchuk, K. L. Analysis and trimming operations in the problem of spatial formation of a family of offset curves given an area with islands. // Journal of Physics: Conference Series, 2020. – №1441. – pp 012069.
19. Panchuk, K. L., Myasoedova, T .M. and Odinets, M. N . Construction of a discrete planar contour by fractional rational Bezier curves of second order. // Journal of Physics: Conference Series, 2020. – №1441. – pp 012072.