Source code for finding Parallel edges by vanishing points (PEVP)

August 2014

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, parallel edges are cues. In particular, the parallel-edges algorithm we consider here (PEVP) is aimed at grouping lines of the sketch that depict edges that are thought to be parallel in the 3D model represented by the sketch.

Attached is a C++ implementation of the new PEVP algorithm.

You can download the PEVP code from here.

Although most of the cues are mutually related, we intend to detect every cue using minimal information. For FF 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 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 way of their head and tail vertices. 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 vertex defining the i-th edge

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

Reader must note that the vectorisation of the sketch required by this approach is minimal, since endpoints of different lines that should be perceived by humans as defining a common junction are not necessarily merged in a single vertex. Hence, it may well happen that every edge endpoint defines a different vertex.

The output is a list of groups of lines of the drawing parallel to each other:

· The information is stored in a standard vector of vectors (std::vector <std::vector <long>> ParallelEdges), where ParallelEdges[i][j] contains the number of the j-th edge of the i-th group of parallel edges.

The approach is encapsulated in two classes:

· CCueParallelEdges class is intended to be called from the external application.

· CCueVanishingPoints class is called from CCueParallelEdges, although it can also be directly called from the external application, in case only vanishing points approach is used.

The first class includes two different approaches to detect parallel edges. The first one is our own implementation of the Angular Distribution Graph (ADG) proposed by Lipson and Shpitalni in the following reference:

H Lipson, M Shpitalni. (1996). Optimization-based reconstruction of a 3D object from a single freehand line drawing. Computer-Aided Design, 28(8) 651-663.

The second one is our approach for finding vanishing points, described in:

P. Company, P.A.C. Varley, R. Plumed (2014). An algorithm for grouping lines which converge to vanishing points in perspective sketches of polyhedral. Lecture Notes in Computer Science LNCS 8746, pp. 77-95.

The third approach is automatic, and uses ADG for normalon objects (also known as “Manhattan like” objects or scenes) depicted in parallel projection, and uses Vanishing Points otherwise. This automatic approach considers that a drawing depicts a normalon shape if (a) three and only three prevailing angles exist, and (b) all the edges fit in one of the three main directions.

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.

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

· MainParallelEdges.cpp, and its header MainParallelEdges.h.

Finally, we must highlight that the code was written to enhance readability. Efficiency never was a goal.

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

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

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