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).

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