How to get 3D models from projections axonométricas

In this article we present a computational method for solving the problem of the interpretation of a 3D scene from an oblique of the same projection. Although this problem had been treated so far using techniques based on SAT or CSPs, here we propose a method based on a specific type of propositional formulas multi-valued. Our method can be competitive with SAT because the obtained formulae are more compact than those obtained with classical logic.

In this article we present a computational method for solving the problem of the interpretation of a 3D scene from an oblique of the same projection. Although this problem had been treated so far using techniques based on SAT or CSPs, here we propose a method based on a specific type of propositional formulas multi-valued. Our method can be competitive with SAT because the obtained formulae are more compact than those obtained with classical logic...

In the departments of computer science and industrial engineering of the University of Lleida and the of graphical expression in the engineering of the Polytechnic University of Catalonia has been studied a new method, based on propositional logic multivalued, to interpret and understand poliédricos objects consisting of vertices triédicos drawings. The objective is to obtain 3D models from projections axonométricas.

The spatial interpretation of drawing lines is a topic studied by the communities of machine vision and structural geometry. They develop algorithms to automate the collection of 3D models from 2D drawings such that, as with human vision, capable of rejecting impossible images.

In this work will head off of the system of labelling of Huffman [1] and Clowes [2], which assigns to each line or edge of an oblique R representation a label denoting whether the edge is convex, concave or border or occlusion. The system assigns a tag of type + to those edges which are convex and that faces present in the edge are visible in the representation R; It is assigned a tag of type - to those edges which are concave and that faces present in the edge are visible in the representation R; and a tag of type (‡fl), is assigned to those edges which is only visible to one side of which concur on the ridge. The latter will be the border edges and the faces that concur in the edge presented occlusion.

On the other hand, depending on the number of edges that meet at a vertex and its position in the representation, the system of Huffman and Clowes classifies joints at the vertices. Joints can be of four types: L, and T and F. In addition, as the edges that meet at a vertex have label, these four types of links give rise to a catalog that is composed of 18 unions representing all the unions that are physically realizable in a polyhedral 3D scene. If an oblique projection is supported by a consistent labelling of the edges with the unions of the catalogue of Huffman and Clowes, then we can get a 3D model. On the other hand, if the labelling is inconsistent, the projection corresponds to a physically unrealizable 3D polyhedral object. However, it should be mentioned that the set of projections possible axonométricas with the catalogue of Huffman and Clowes is not complete, in the sense that it [3] extensions that make valid certain projections with the Huffman and Clowes catalogue are not valid have been studied.

In this paper we propose the resolution of the problem through its reduction to the problem of the first of the MV-fórmulas

Given an oblique R of a 3D object representation, our method starts by represent R and the restrictions of the unions by a formula (f) of the propositional logic multivalued, so R corresponds to a 3D object if and only ifF is satisfactible (i.e., is not contradictory). Then determines the first of F using MV-Satz [4], which is a first that incorporates artificial intelligence techniques. Finally, if F is satisfactible, build a correct labelling of the 3D object from the logical model of F which has derived MV-Satz.

In this paper we propose the resolution of the problem through its reduction to the problem of the first of the MV-fórmulas. The MV-fórmulas are a few formulas that generalize the conjunctive normal forms (FNCs) of classical propositional logic. They differ in that regard a set of values of truth that can hold more than two values and that we can use literal multivaluados that are satisfied by more than a different interpretation for your variable. In addition, they assume the existence of a total order among elements of the set of truth values. This order helps more compact way to express some literal multivaluados.

Definition 1. A set of truth-values T is a finite set {i1, i2, …in} values among which there is a total order. A literal multi-valued is an expression of the form s:p, where S is a subset of T and p is a propositional variable. If S is of the form {i} or of the form ≠i = {j | i ≥ j} either in the way Øi = {j | j ≤i} then we say that s:p is a MV-literal. A MV-cláusula is a disjunction of literals-MV and a MV-fórmula is a portmanteau of MV-cláusulas.

Definition 2. A performance is a function of the set of propositional variables to the set of truth values. An interpretation satisfies an MV-literal S: p if the value assigned to p is in S, satisfies a MV-cláusula if it satisfies at least one of its MV-literals and satisfies a MV-fórmula if it satisfies all their MV-cláusulas.

Figure 1. Projections of three-dimensional objects axonométricas.

The problem of interpretation of three-dimensional figures that we consider here is based on the original problem treated by Huffman and Clowes, although it is possible to consider small variations of the same can also be resolved using our method. The problem is based on the following principles:

1. The two-dimensional drawing is a projection aerial of a Union of three-dimensional objects. Three-dimensional objects are poliédricos objects, where each vertex is the intersection of exactly three planes. Figure 1 shows projections valid axonométricas of two poliédricos objects.

2. Each line of the drawing represents an edge of one of the polyhedra. It is uncertain shadows, hidden lines, and areas of color change.

A particular interpretation of the drawing gets to label all the edges of the same in a consistent manner. This labelling reports on whether the edges are concave or convex either if they are edges connecting two sides of which only one is visible in the oblique projection.

After considering the different ways in which we can form vertices triédricos and different points of view from where it can be observed, Huffman and Clowes extracted the catalogue of 18 possible vertices that may appear in an oblique projection (see Figure 2). Within a vertex, its edges we numbered starting with which is in its upper left position, and moving in the sense of the hands of the clock.

We believe that as we are given the total set of vertices (V) and edges (A) of the object oblique projection. Each edge is described by its two vertices (v1 and v2) and two numbers (v1i and v2i) indicate, within the two vertices, two edges are actually fused into one. For each vertex, we have a label indicating its type, between the four different types (L, and T, F). From the graph (V, in), build a MV-fórmula in the following way:

Figure 2. Huffman-Clowes catalogue of valid labels for vertices triédricos edges.

1. The set of values of truth, T, is a set with the six first natural numbers {1,2,3,4,5,6}. For each of the four types of vertices, each truth value represents one of the different ways in which that vertex may be labeled. Note in Figure 2, that at most we need six IDs valid for any type of vertex labelled.

2. The set of propositional variables, Var, is the set {v | v in V}. Each variable represents a distinct oblique projection vertex.

3. The MV-cláusulas of the formula set is the Union of different sets of MV-cláusulas. An interpretation that satisfies the formula will give us a valid labelling for the vertices of the projection. The MV-cláusulas ensure that assigned to a vertex labeling is consistent with its neighboring vertices, according to the catalogue of Figure 2. As the complete specification of the clauses is very long, we here simply to describe a particular subset of them. Consider the case where we want to ensure that the labelling for a vertex v1, which is of type F, is consistent with the of the vertex v2, which is of type and, because they are connected through a common edge in the positions of the v1i and the vertices v1 and v2 v2i edgesrespectively. We will have a different set of three MV-cláusulas, depending on the positions of the edge in the two vertices (v1i and v2i). These are the possible cases:

The problem of interpretation of three-dimensional figures that we consider here is based on the original problem treated by Huffman and Clowes

One of the examples show that given a projection that does not correspond to a physically realisable 3D object, this method detects that there is a consistent labelling

Figure 3. Example of inconsistent labelling for a projection of an impossible object.

Below to illustrate the operation of our method, we will describe the process of searching for labelling for two examples. In the first we see that given a projection that does not correspond to a 3D object physically realisable, our method detects that there is a consistent labelling. In the second, we assume a projection aerial that corresponds to two possible situations. One of them the projection corresponds to a single object and the other corresponds to two objects. This second example we show that our method is also used to find all possible interpretations of a same projection.

In the first example we start with a projection which initially are only tagged the edges of the border, i.e., those that come together in a vertex where one of the faces is not visible. Figure 3a show the screening with the initial tagging. From this initial labelling, our method will determine unique for this example labels that are consistent with the catalog of possible vertices. For example, in the vertex type and that it was more to the right of the projection can see that due to the initial labelling only label the three edges that converge at that vertex is through a convex edge (+). The repeated application of this process of spread of restrictions finally leads to the situation that we see in Figure 3b. The problem is that this final labelling is not consistent. This is due to a vertex (vertex with question mark) is not a possible of our catalog vertex and therefore our method tells us that this projection does not correspond to a 3D object.

In the second example, we see in Figure 4, we also assume a border initially labelled by their edges projection. However, there are two edges (edges a and b) that initially not label of border because admit another possible labelling. In the upper part of Figure 4 show the screening with labelling that determines our method from the initial tagging. The edges a and b are not determine as they support two possible labelled. At this point our method decides as complete labelling by choosing values possible and consistent with the catalogue for edges a and b. A first choice determines the edges a and b as concave which leads him to a complete and consistent labelling. This labelling interprets the projection as the projection of a single 3D object. The second choice determines the edges a and b as border which also leads him to a complete and consistent labelling. In this case, this labelling interprets the projection as the projection of two 3D objects.

Figure 4. Example of labelling of scene with two possible interpretations.

The procedure devised by Waltz [5], based on CSPs, is capable of labeling "typical" scenes with a linear average time in the total number of edges of the scene. However, we know that in the worst case, some scenes, the resolution of this problem can not be carry out with polynomial time [6]. Our aim in the future is to study the performance of our method for typical scenes and compare it with other existing labelling methods

[1] D.A. Huffman, "Impossible objects as nonsense senteces", B. Meltzer and D. Michie Ed., Machine Intelligence 6, Edinburgh University Press, 295-323, Edinburg, 1971.

[2] Moniteur belge Clowes, "On seeing things", Artificial Intelligence 2: 79-116, 1971.

[3] C. Ansótegui et al, "Resolution methods for many-valued CNF formulas", SAT Conference, 2002

[4] T. Kanade, "to theory of Origami world", Artificial Intelligence 64: 147-160, 1980.

[5] D.Waltz, "Understanding line-drawings of scenes with shadows", in: The Psychology of Computer Vision, McGraw-Hill, 19-91, 1975

[6] L.M. Kirousis, C.H. Papadimitriou, "The complexity of recognizing polyhedral scenes", Journal of Computer and System Sciences 37: 14 - 38, 1988.