**Source code for Detecting Vertices
in sketched drawings of polyhedral shapes**

November 2018

We are interested in
creating computer-based tools to help design engineers during the first stage
of the design process, known as conceptual design. Hence, we develop
Sketch-Based Modelling (SBM) systems. Our approach for SBM relies on finding
cues or regularities, which are those sketch properties which
reveal properties of the three-dimensional object depicted in the sketch. In
this context, junctions of sketched drawings are cues which
depict vertices of polyhedral shapes. In particular, the *detecting-vertices* algorithm we consider here (JUNC) is aimed to merge the endpoints of all the edges that share
nodes or vertices of the polyhedral shape (merging into a single vertex all
endpoints that should be perceived by humans as a common junction).

Attached is a C++
implementation of the code of the new JUNC algorithm.

You can download the JUNC
code from here.

Although most of the
cues are mutually related, we intend to detect every cue using minimal
information. The input sketch comprise only discrete strokes, sequences of
points obtained between a pen down and a pen up. For JUNC to work, tips or
endpoints of each segment line need to be previously filtered
by applying some corner detection approach. Some of these known approaches are:

·
IStraw
(implemented by Xiong Y., LaViola J.:*
A shortstraw-based algorithm for corner finding in
sketch-based interfaces. *Computers and Graphics 34(5) (2010), 513–27);

·
Shortstraw (Wolin A., Eoff B., Hammond T.*: Shortstraw: a simple and effective corner finder for
polylines. *SBIM 2008 (2008), 33–40);

·
Sliding strips (proposed by Masood A.,
Sarfraz M*.: Corner detection by sliding rectangles
along planar curves. *Computers and Graphics 31 (2007), 440–48).

Hence, the input to the
code is a 2D drawing, which includes a list of tips of line segments and edges in
the following format:

·
Coordinates
of every vertex are stored in an instance of the POINT2D class. The set of all vertices
is stored in a standard vector (std::vector
<POINT2D>Vertex)

o
VertexCount= number of vertices in the drawing

o
Vertex[i].x= X coordinate of the i-th vertex

o
Vertex[i].y= Y coordinate of the i-th vertex

·
Edges are defined by means of their head and tail vertices, which
correspond with the endpoints of each stroke. The set of all edge heads is
stored in a standard vector (std::vector <long>
EdgeHead) and the set of all edge tails is stored in
another standard vector (std::vector <long> EdgeTail):

o
EdgeCount= number of edges in the line drawing

o
EdgeHead[i]= Head junction defining
the i-th edge

o
EdgeTail[i]= Tail junction defining
the i-th edge

Reader must note that examples
attached (corresponding to the examples of the technical report) have been previously filtered by the IStraw
approach, to find the corners of the strokes which define the endpoints of each
segment line.

The output of the
algorithm is a list of vertices, which depict junctions in the 3D model, and a
list of edges:

·
For
each vertex, the algorithm returns its coordinates and the figure of merit that
estimates how likely a vertex is to be perceived as a
junction by human beings.

·
The
list of edges with their endpoints updated according to the new vertices.

The approach is encapsulated into a main class CueJunctions. Two more files containing auxiliary classes and
operations are required for the approach to work:

·
Tools_Geometry.cpp, and its
corresponding header Tools_Geometry.h.

·
Tools_Vector.cpp, and its
corresponding header Tools_Vector.h.

This approach for
detecting junctions is extensively described in:

Company P., Varley P.A.C., Plumed R. and Camba J.D. (2018).

Detection of vertices in sketched drawings of polyhedral shapes.

CIARP: 23^{rd} Iberoamerican Congress on Pattern Recognition (2018).

To help understanding
how the code works, and in order to offer a test environment too, the following
main file is also provided:

·
Main.cpp.

Finally, we must
highlight that the code was written to make it
readable. Efficiency never was a goal.

**************************************************************************************

The JUNC code is free
software. But if you find it useful for your own research,

please cite our paper:

Company P., Varley P.A.C., Plumed R. and Camba J.D. (2018).

Detection of vertices in sketched drawings of polyhedral shapes.

CIARP: 23^{rd} Iberoamerican Congress on Pattern Recognition (2018).

**************************************************************************************