Source code for Finding Perimeters in sketched drawings of polyhedral shapes

September 2017

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, perimeters of sketched drawings of polyhedral shapes are cues. In particular, the finding-perimeters algorithm we consider here (PER) is aimed at finding circuits of lines and junctions (including intersections and T-junctions) of the original line drawing that belong to the contour of the polyhedral shapes depicted by wireframe models of polyhedral objects.

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

You can download the PER code from here.

Although most of the cues are mutually related, we intend to detect every cue using minimal information. For PER to work, the input sketch must have been previously vectorised, so as to convert strokes of the sketch into lines of the line drawing. Hence, the input to the code is a 2D drawing, which includes a list of vertices 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 vertex in the line drawing

o VertexX[i]= X coordinate of the i-th vertex

o VertexY[i]= Y coordinate of the i-th vertex

· Edges are defined by way of their head and tail vertices. The set of all edge heads is stored in a standard vector (std::vector <long> EdgeU) and the set of all edge tails is stored in another standard vector (std::vector <long> EdgeV):

o EdgeCount= number of edges in the line drawing

o EdgeU[i]= Head vertex defining the i-th edge

o EdgeVl[i]= Tail vertex defining the i-th edge

Reader must note that the vectorisation of the sketch required by this approach includes previous merging of 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).

The output of the algorithm is a list of ordered lines and corners that belong to the perimeter:

· The edges that belong to the perimeter are sequentially ordered in PerimeterLines.

· The corners (junctions, intersections or T-junctions) that belong to the perimeter are sequentially ordered in PerimeterCorners. Positive numbers in the list of corners refer to junctions (vertices) of the original line drawing, while negative numbers are pointers to a list of intersections or T-junctions that belong to the perimeter. Note that the distinction between intersections and T-junctions is simple: the intersection becomes a T-junction if it is close to one vertex of the outgoing edge.

· The coordinates of the intersections and T-junctions that belong to the perimeter are saved (list TX), as much as the lines that produce each intersection (list TEdges)

The approach is encapsulated into a main class CCuePerimeter, which shares the same file with some auxiliary classes.

This approach for finding perimeters is extensively described in:

Company P., Varley P.A.C., and Plumed R. (2017).
Perimeter detection in sketched drawings of polyhedral shapes.
STAG: Smart Tools and Applications in Graphics (2017).
A. Giachetti, P. Pingi and F. Stanco (Editors).

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, and its header Main.h.

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

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

The PER code is free software. But if you find it useful for your own research,
please cite our paper:

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