=Paper=
{{Paper
|id=Vol-2744/short32
|storemode=property
|title=Application of Heuristic Modeling in the Development of an Algorithm for Generating a Binary Tree of an Object According to a Technical Drawing (short paper)
|pdfUrl=https://ceur-ws.org/Vol-2744/short32.pdf
|volume=Vol-2744
|authors=Valeriya Tyurina,Marina Lagunova,Maria Smychek
}}
==Application of Heuristic Modeling in the Development of an Algorithm for Generating a Binary Tree of an Object According to a Technical Drawing (short paper)==
https://ceur-ws.org/Vol-2744/short32.pdf
Application of Heuristic Modeling in the Development of
an Algorithm for Generating a Binary Tree of an Object
According to a Technical Drawing*
Valeriya Tyurina[0000-0002-0234-9041], Marina Lagunova[0000-0002-0671-8609],
Maria Smychek[0000-0002-4657-1074]
Nizhny Novgorod State University of Architecture and Civil Engineering,
Nizhny Novgorod, Russia
55555_73@mail.ru, mvlnn@mail.ru, mariasmychek@gmail.com
Abstract. This article presents the problem of developing an algorithm for
automated reading of a drawing of an object, consisting of three types with the
necessary cuts. According to the drawing, a partition of the object into non-
derivative figures should be obtained and boolean operations should be
identified, with the help of which the final composite figure will be constructed
from non-derivative figures. Thus, in the process of solving this problem, a so-
called binary tree of the modeled composite figure will be generated. Moreover,
it is necessary to take into account the multiplicativity of the solution to this
problem and the possibility of choosing optimal solutions. This paper poses a
specific problem, in which non-derivative figures can be got using four form-
building operations available in the arsenal of tools for getting three-dimensional
elements in the Compass 3D geometric modeling system, namely, such
operations as "extrusion", "rotation", "along the trajectory" and "cross-sections".
Keywords: Heuristic Modeling, Reading a Drawing, Form-Building Operations,
Binary Tree, Non-Derivative Figure, Composite Figure, Geometric Modeling.
1 Development of an algorithm for generating a binary tree
according to a technical drawing
1.1 Problem statement and choice of solution method
A three-dimensional geometric model can consist of a number of geometric primitives
that are interconnected in a certain way.
We will name such geometric primitives as non-derivative figures (NF) and
consider them indivisible in the given class of the considered problems [1]. A composite
figure (CF) is constructed from the available geometric primitives.
This article presents the problem of developing an algorithm for automated reading
Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons
License Attribution 4.0 International (CC BY 4.0).
* The work was supported by grant 19-07-01024 from the RFBR.
2 V. Tyurina, M. Lagunova, M. Smychek
of a drawing of an object, consisting of three types with the necessary cuts. According
to the drawing, a partition of the object into non-derivative figures should be obtained
and boolean operations (BO) should be identified, with the help of which the final
composite figure will be constructed from non-derivative figures. Thus, in the process
of solving this problem, a so-called binary tree of the modeled composite figure will
be generated. Moreover, it is necessary to take into account the multiplicativity of the
solution to this problem and the possibility of choosing optimal solutions.
One should note that when setting such a problem, it is necessary to take into
account the method of getting non-derivative figures. It can be either a pre-formed bank
of objects (geometric primitives) available in some geometric modeling system, or a
set of operations for the formation of such primitives. This paper poses a specific
problem, in which non-derivative figures can be got using four form-building
operations (FO) available in the arsenal of tools for getting three-dimensional elements
in the Compass 3D geometric modeling system, namely, such operations as
"extrusion", "rotation", "along the trajectory" and "cross-sections" [2].
The problem of reading a drawing in its general formulation refers to informal
problems, according to the classification of V.S. Polozov. These are such problems, the
general algorithm for solving which is unknown, but in each specific case they can be
solved by a person on the basis of experience and intuition [3]. The problem posed in
this paper has a sufficient number of restrictions and is difficult to formalize. Therefore,
in order to develop an algorithm for solving this problem, the authors decided to apply
the method of heuristic modeling. The general scheme of applying this approach was
described in the papers of V.S. Polozov [1, 3]. The refined scheme for the assigned
problem is shown in Fig. 1.
One can distinguish four levels, each of which carries its own semantic load.
At the first level (A), the developer of the algorithm (the head of the experiment) is
responsible for the initial setting of the problem, works with experts, and makes
decisions on changing and clarifying the problem. At the second level (B), the
developer of the algorithm uses introspection (self-observation), he analyzes his mental
activity when reading the drawing and tries to highlight the basic steps of the algorithm.
Then each step is broken down into stages that are possible for formalization and,
accordingly, further software implementation. At the same level, the project manager
evaluates the work of experts and either makes additions to the developed algorithm
(moves to the third level), or makes changes to the problem statement - clarifies, breaks
down into smaller stages, i.e. returns to the first level. At the third level (C), the
experiment manager forms a problem for the experts, enters the positive results
obtained during the experiment in the problem solution tree, and assesses the readiness
of this tree. The fourth level (D) is an experiment itself, during which experts - people
with different experience in reading drawings: from an entry-level (applicants,
students) to a professional (teachers, designers) - receive detailed explanations on the
problem statement Experts are explained the essence of the experiment, and then each
of them works at the level of introspection, recording in detail all the stages of their
mental activity while reading the drawing, and then presenting the results to the project
manager.
Application of Heuristic Modeling in the Development of an Algorithm for Generating 3
Fig. 1. Scheme of the heuristic modeling method.
2 Conducted heuristic experiment
2.1 Initial data
During the study, the authors of the article conducted several experiments according to
the above scheme. Drawings of three-dimensional objects of varying degrees of
complexity were used as the initial drawings. In this study, the complexity of an object
is understood as the number and degree of its bounding surfaces.
Fig. 2. Example of a composite figure.
4 V. Tyurina, M. Lagunova, M. Smychek
Fig. 3. Composite figure drawing.
Here are some examples of recordings from the stage of introspection of the experiment
leader and experts (for obvious reasons, the recordings of reasoning are given with the
maximum reduction).
2.2. Example 1 (first expert)
1. In the top view, we select a closed contour in the form of a "cross", consisting
of 12 segments, with two axes of symmetry.
2. The front view shows a cut. Its design (namely, half of the frontal cut is aligned
with half of the main view, there is no designation of the trail of the secant
plane) indicates the presence of two planes of symmetry of the surface. It is
clear from the shape of the section projection that the "cross", taken as sketch
1, located in the horizontal plane, must be extruded to a height of 40 mm.
3. We apply the form-building operation "extrusion" to get a non- derivative
figure 1 (extrusion element) (see Figure 4.)
4. In the front view, we select a visible contour located in the frontal plane of the
level closest to the observer, in the shape of a "trapezoid", consisting of 5
segments, one of which is represented by a dash-dotted line. Taking into
account the axis of symmetry, we get a closed contour consisting of 6
segments, taken as sketch 2.
5. From the top and left views, we determine the depth of the contour extrusion
by 40 mm.
6. We apply the form-building operation "extrusion" to get a non- derivative
figure 2 (extrusion element).
7. After making sure that these figures are overlapping, we combine them to get
a composite figure 1 using the boolean operation "combination": NF1 NF2
= CF1.
Application of Heuristic Modeling in the Development of an Algorithm for Generating 5
8. In the top view, we select a circle. Having established a connection with half
of the frontal cut, by the shape of the section projection and the presence of
the center line, we identify the shape of the hole - through cylindrical, i.e. we
get a non-derivative figure 3, cylinder.
9. We apply the operation "cut by extrusion", which implements the boolean
operation "subtraction": CF 1 \ NF 3 = CF 2.
Fig. 4. Binary tree of composite figure.
2.3. Example 2 (second expert)
1. After analyzing the three projections and line types, we reveal the presence of
symmetry, which allow us to analyze parts of the species.
2. After analyzing the front view, we select several closed contours and select
the visible contour located in the frontal plane of the level closest to the
observer. Taking into account the axis of symmetry, we get a closed contour
consisting of 6 segments, we will use it as sketch 1.
3. We apply the form-building operation "extrusion" to get a non- derivative
figure 1 (extrusion element) (see Figure 5).
4. After analyzing the top view, where there are no invisible lines and cuts, we
select 7 closed visible contours on it (one contour in the form of a "cross" - 12
segments, four identical rectangles, a circle in the middle, outline - a
rectangle).
5. Choosing a more complex one, based on the number of segments, that is, a
closed contour in the form of a "cross", we establish a projection link with the
front and left views to test the possibility of "extruding" the contour at a given
distance of 40 and get a non-derivative figure.
6 V. Tyurina, M. Lagunova, M. Smychek
6. We apply the form-building operation "extrusion" to get a non- derivative
figure 2 (extrusion element).
7. We merge non-derivative figure 1 with non-derivative figure 2 using the
boolean operation to obtain a composite figure (CF1).
8. After analyzing the top view, we select a circle. We set a projection
correspondence with the half of the frontal cut to refine the shape of the
through cylindrical hole. We get a non-derivative figure (NF3).
9. We remove the non-derivative figure 3 from the composite figure 1, applying
the boolean operation "subtraction", we get the final composite figure (CF2 -
final).
Fig. 5. Binary tree of composite figure.
2.4. Example 3 (third expert)
1. Analyzing the three views and types of lines, we conclude that there is
symmetry.
2. After analyzing the left view, we select four closed visible contours (one
contour of 8 segments, two identical rectangles, outline - rectangle). We
choose a more complex one, based on the number of segments, that is, a closed
contour of 8 segments.
3. We establish a projection connection with the front and top views to test the
possibility of "extruding" the contour at a given distance of 60 and get a non-
derivative figure (NF1) (see Fig. 6).
4. We apply the form-building operation "extrusion" to get a non- derivative
figure 1 (extrusion element).
Application of Heuristic Modeling in the Development of an Algorithm for Generating 7
5. After analyzing half of the front view, taking into account the presence of
symmetry, we select four closed visible contours (one contour of 6 segments,
two identical right-angled triangles, outline - rectangle). We choose a more
complex one based on the number of segments.
6. We establish a projection link with the left and front views to test the
possibility of "extruding" the contour at a given distance of 40 and get a non-
derivative figure (NF 2).
7. We apply the form-building operation "extrusion" to get a non- derivative
figure 2 (extrusion element).
8. We merge non-derivative figure 1 with non-derivative figure 2 applying the
boolean operation "combination", we get a composite figure (CF1).
9. We look at the circle in the top view and make a projection correspondence
with the half of the frontal cut to refine the shape of the hole. Non-derivative
figure 3 is a through cylindrical hole.
10. We remove the non-derivative figure 3 from the composite figure 1, applying
the boolean operation "subtraction", we get the final composite figure (CF -
final).
Fig. 6. Binary tree of composite figure.
2.5. Example 4 (fourth expert)
1. Analyzing the three views, we conclude that the three sketches in the three
views are projections of a 40x60x40 parallelepiped.
2. Having selected a rectangular contour in the front view (outline), we extrude
it by 40 mm - we get NF1 (parallelepiped - "blank").
3. Analyzing the front view, we identify the "cut" corner that forms the "triangle"
contour, which can act as a sketch to get a triangular prism NF2.
8 V. Tyurina, M. Lagunova, M. Smychek
4. Analyzing the top view, we determine the extrusion depth of NF2 - 15 mm.
5. We subtract the triangular prism NF2 from the “blank” NF1 using Boolean
operation “subtraction”.
6. The number of such triangular prisms is four: NF2, NF3, NF4, NF5:
NF1 \ NF2 = CF1,
CF1 \ NF3 = CF2,
CF2 \ NF4 = CF3,
CF3 \ NF5 = CF4.
7. In the top view, we see a circle and by the presence of the axis of rotation in
other views and the content of the section projection, we understand that a
cylinder is cut, i.e. NF6.
8. We subtract the cylinder NDF6 from the previously obtained composite figure
by applying the boolean operation "subtraction" CF4 \ NF6 = CF5.
Fig. 7. Binary tree of composite figure.
This example shows that experts reason in different ways and one can read the
drawing and create a 3D model in different ways. The minimum number of non-
derivative figures in this case turned out to be three, but the question of rationality
and simplicity of creating a model remains open in this case and requires further
analysis.
Application of Heuristic Modeling in the Development of an Algorithm for Generating 9
The set of non-derived figures coincided in some cases, and in some differed,
but led to an identical binary tree. The last example showed the possibility of
reasoning leading to a complex binary tree, but simpler non-derivative figures from
the point of view of perception (this often turns out to be a decisive factor). During
the study it was confirmed that the complexity of the structure of a binary tree of
an object, compiled by various experts, therefore, the number of non-derivative
figures required to build a model of an object in a geometric modeling system (and,
therefore, the connections between them), does not reflect the complexity of the
object of modeling, which is determined by the number and degree of its bounding
surfaces. One should note once again that the problem solution tree (the basis of an
algorithm that allows automating the process of reading a drawing) at the level of
introspection and when analyzing the data of all experts is expanded and
supplemented with new stages.
Some of the "reasoning" of the participants in the experiment, which look like
"free" judgments, is in fact an important step towards the formalization of mental
acts in the analysis of the drawing. They require further breakdown to identify
specific features and attributes, therefore, it is necessary to analyze drawings of
different levels to identify clarifying factors and model various situations when a
real algorithm is working.
3 Conclusion
During the study it was concluded that it is advisable to continue such heuristic
experiments (their number should be large to obtain a reliable algorithm that works on
real objects. But the experiments already carried out at this stage made it possible to
identify in the participants' reasoning the general key factors in the analysis of the
drawing, which are signs of formative and boolean operations, which are available for
formalization, and, therefore, for software implementation.
References
1. Polozov, V., Budekov, O., Rotkov, S.: Computer-aided design. Mechanical Engineering,
280 p. (1983).
2. KOMPAS-3D. Homepage,
https://kompas.ru/source/info_materials/user-manuals/rukovodstvo-polzovatelya-
kompas-3d.pdf, last accessed 2020/07/10.
3. Kotov, I., Polozov, V., Shirokova, L.: Computer graphics algorithms. Mechanical
Engineering, 231 p. (1977).
4. Zhilina, N., Lagunova, M., Moshkova, T., Romensky, S., Rotkov, S., Smychek, M.,
Tyurina, V.: Synthesis of a parametric structural model of a 3D object. GraphiCon'2017:
27th International conference on computer graphics and vision: Perm State National
Research University, pp. 350-354. Perm (2017).
5. Zhilina, N., Lagunova, M, Moshkova, T., Rotkov, S., Tyurina, V.: Algorithm of
automated construction of object 3D-models on orthogonal projections using Kompas-
3D system. Privolzhsky scientific journal 4 (32), 42-48 (2014).