News Info News

This news article was originally written in Spanish. It has been automatically translated for your convenience. Reasonable efforts have been made to provide an accurate translation, however, no automated translation is perfect nor is it intended to replace a human translator. The original article in Spanish can be viewed at Cómo obtener modelos 3D a partir de proyecciones axonométricas

How to get 3D models from projections axonométricas

R Béjar (1), a. Cabiscol (1), C. Fernández (1), M. Lopez (2) and f. Manyà (1)
(1) Department of computer science and Industrial Engineering. University of Lleida.

(2) Department of graphical expression in engineering. Universitat Politècnica de Catalunya

15/05/2003
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.

Multi-valued formulas

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.

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

Formal definition of the problem

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.

Encoding using a MV-fórmula

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
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:

Imagen
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
Figure 3. Example of inconsistent labelling for a projection of an impossible object.

Operation

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
Figure 4. Example of labelling of scene with two possible interpretations.

Complexity

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

References

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

Suscríbase a nuestra Newsletter - Ver ejemplo

Password

Select all

Autorizo el envío de newsletters y avisos informativos personalizados de interempresas.net

I authorize the sending of communications from third parties via interempresas.net

He leído y acepto el Legal notice y la Data protection policy

Responsable: Interempresas Media, S.L.U. Purpose: Subscription to our newsletter(s). User account management. Sending emails related to the same or related to similar or associated interests.Retention: for the duration of the relationship with you, or as long as necessary to carry out the specified purposesTransfer: Data may be transferred to other group companies for internal management purposes.Rights: Access, rectification, opposition, deletion, portability, limitation of processing and automated decisions: contact our DPD. If you consider that the processing does not comply with the regulations in force, you may lodge a complaint with the AEPD.More information: Data protection policy

REVISTAS

VÍDEOS DESTACADOS

  • VOLLMER VHybrid 260

    VOLLMER VHybrid 260

  • MonoThread – SFSE y SGF: Roscado con precisión

    MonoThread – SFSE y SGF: Roscado con precisión

TOP PRODUCTS

NEWSLETTERS

  • Newsletter Metal

    17/09/2024

  • Newsletter Metal

    16/09/2024

Highlighted links

Industry LIVEEasyfairs Iberia - MetalMadridAspromec - Asociación de profesionales para la competitividad del mecanizadoNebext - Next Business Exhibitions, S.L. - Advanced Machine ToolsFundación Ficoba

Latest news

Featured companies

OPINIÓN

OTRAS SECCIONES

Services