HK1090720B - Method and system for manipulating a digital representation of a three-dimensional object - Google Patents

Description

Method and system for manipulating a digital representation of a three-dimensional object

Technical Field

The present invention relates to manipulating digital representations of three-dimensional objects. The invention relates in particular to computer-implemented manipulation of a three-dimensional virtual building block model by means of two-dimensional cursor movements, the virtual building block model comprising a plurality of virtual building blocks, each virtual building block comprising a number of connecting elements for connecting a virtual building block to other virtual building blocks according to a set of connection rules.

Background

The task of computer-aided modeling of virtual reality is to create models of physical objects, manipulate the models, and further process the models of physical objects in a computer system.

From a first point of view, the modeling of virtual reality is an interesting topic, since it makes it possible to visualize concepts before they are actually realized in the real world. Given that the virtual reality model is easily modified, a significant amount of time can be saved in the process of developing and improving physical objects as compared to implementing the same process in the real world. The simple task of coloring an object in the real world can easily take hours, while a computer can color a model with a new color in milliseconds or seconds.

From a second point of view, virtual reality modeling is interesting because it makes it possible to create models of objects present in the real world, as well as to visualize and manipulate the models by means of a computer. Thus, the object model may be stored for different purposes, e.g. for advanced documentation purposes.

Although there are a large number of possible applications for computer-aided virtual reality modeling, one particular application is the use of virtual reality modeling for entertainment or education.

Different types of modeling concepts for physical construction toy sets are also known. In particular, the idea of using a modular or semi-modular concept is very popular. Typically, these concepts provide a set of prefabricated elements that can be interconnected with each other in some predetermined manner according to the modules of the prefabricated elements. An example of such a construction toy set is a plastic toy construction element known as LEGO.

When manipulating a representation of a three-dimensional (3D) object or scene on a computer, it is often a problem that the positioning, selection or movement of the object in 3D is performed by means of an input device operating in two dimensions, e.g. a two-dimensional (2D) movement of a computer mouse over a mouse pad. In addition, the display area of the computer is also two-dimensional. In particular, each selected location on the 2D display area of the computer screen corresponds to a plurality of locations within the 3D space, the 3D space having a projection into the 2D display area corresponding to the selected 2D location. The problem is to determine one of the locations that may meet the user's intent.

Although considerable effort has been expended in developing computer interface devices that are better suited for manipulating objects in 3D computer images, such tools have not been widely used, particularly in connection with computer systems for home entertainment, education, and the like.

Known construction games that position virtual building blocks are typically limited in the freedom of movement and rotation of objects or the way they are connected to other objects.

Us patent 6,426,745 describes a method of mouse-manipulating 3D graphical objects, where movement in 3D is achieved by constraining movement to a plane or a direction at a certain moment, whereby 3D movement is achieved with a series of constrained movements, for example a series of movements in the X-direction, then in the y-direction, and finally in the Z-direction in a 3D coordinate system.

A problem with the above prior art systems is that the placement of building blocks in a 3D scene and their connection to the 3D structure with a conventional user interface is a cumbersome process that requires a high level of skill and training. This is a problem, especially in the recreational and educational environment of children and teenagers, because children often do not yet develop adequate motor skills or the resistance required to perform lengthy maneuvering procedures. Thus, they may quickly lose interest in the virtual construction game.

Disclosure of Invention

The above and other problems are solved by a computer implemented method of manipulating a three-dimensional virtual building block model by means of two-dimensional cursor movements, the virtual building block model comprising a plurality of virtual building blocks, each virtual building block comprising a number of connecting elements for connecting a virtual building block with other virtual building blocks according to a set of connection rules, the method comprising:

-providing a number of said virtual building blocks in a three-dimensional coordinate system for a digital representation of a structure;

-positioning the two-dimensional projection of the first virtual building block to be connected to the structure by means of a cursor movement in a two-dimensional computer display area representing the projection of the structure, resulting in two-dimensional position coordinates;

-determining a number of three-dimensional candidate positions of the first virtual building block in a three-dimensional coordinate system from the two-dimensional position coordinates; and

-selecting one of the candidate locations based on a connection rule and a set of predetermined location rating rules; and

-connecting a first building block to the structure at the selected candidate position.

Thus, an efficient method for manipulating a digital representation of a three-dimensional object is provided, which transforms (resolve) positions in a 2D display area to corresponding 3D positions in a way that is intuitive for the user, thus making it easy for the user to manipulate the 3D virtual structure. The user may simply position a new building block in the 2D screen area, thus fixing the coordinates of the new building block in both directions only. An appropriate one of a plurality of possible 3D positions that are 2D compliant for placement is then automatically determined based on a number of connection rules and a set of position ranking rules.

In particular, by selecting one of a number of candidate locations according to a set of predetermined location ranking rules, the process results in positioning the building block at a location in the 3D scene that is likely to meet the user's intent.

A further advantage is that positions which do not comply with the connection rules for the connection element are rejected. For example, a construction system may have a large variety of different connection elements, such as protrusions of different shapes and/or sizes and different types of holes for engaging with a respective one of the protrusions.

Assuming that a new building block is placed at a candidate 3D position that corresponds to a 2D placement, the 2D placement of the new building block on the computer screen is correctly translated to a 3D position in the 3D model by selecting a candidate connection element that is close to the connection element on the new building block and by checking whether a valid connection with the candidate connection element is possible. Furthermore, 2D to 3D transitions according to a set of connection rules, which may lead to invalid connections, e.g. connection of protrusions with different types of holes, are avoided.

Therefore, the virtual building block type game has the advantages that the virtual building block type components are consistent with the physical limits of the corresponding physical building groups, and therefore the educational value of the virtual building game is improved. In particular, the virtual build may then be transformed into a physical model by building the physical model with the same type of building blocks.

A further advantage is that the method provides a large freedom of movement and connection. For example, the building blocks may be positioned and connected in any orientation. In particular, it is possible to connect to other building blocks both in the horizontal and in the vertical plane. Furthermore, even if the building blocks are rotated, for example around a vertical or horizontal axis, they can be positioned correctly.

Preferably, the positioning of the graphical representation is controlled by control commands received from a user via a suitable input device, such as a pointing device. For example, pointing may be performed as a standard cursor manipulation technique, such as a "drag and drop" operation, a "click-drag-drop" operation, and other similar operations.

In a preferred embodiment, the step of determining a number of three-dimensional candidate positions further comprises determining a number of candidate positions of the first virtual building block in a three-dimensional coordinate system. By rotating the first building block to obtain candidate positions for the rotated building block, the user-controlled 2D position is translated into a 3D placement and orientation in three dimensions, thereby determining all six degrees of freedom for placement in the 3D scene based on only a single cursor control in the 2D screen area. When the rotation of the first building block is limited to a predetermined spatial angle around the user selected orientation, confusing rotations such as a full flipping of the building block are avoided, thereby avoiding confusion (disarrassment) of the user. In this embodiment, more orientations can be obtained by allowing the user to select the orientation of the virtual building block.

In a preferred embodiment, the method further comprises:

-determining a number of candidate connecting elements of the structure, each candidate connecting element having a projection in a two-dimensional display area within a predetermined neighborhood around the projection of the connecting element of the first virtual building block;

-selecting one of said candidate connection elements based on the connection rule and the set of predetermined position ranking rules; and

-connecting the first virtual building block with the structure via at least one selected candidate connecting element if the connection between the first virtual building block and the structure is valid according to the set of connection rules.

Thus, a computationally efficient method of detecting candidate positions is provided, since the detection depends only on the position and properties of the individual connection elements. Furthermore, an efficient selection mechanism is provided for selecting the 3D position that is most likely to meet the user's intent.

Particularly advantageous connection element hierarchies are provided when the hierarchy contains one or more of the following hierarchy rules:

-ranking the candidate connection elements with respect to their distance to the virtual camera position;

-discarding candidate connection elements not visible from the current virtual camera position; and

-ranking the candidate connecting elements with respect to the distance of their two-dimensional projection to the two-dimensional projection of the respective connecting element of the first virtual building block.

In particular, a reliable 3D positioning is obtained when the grading rule is based on a combination of distances to the virtual camera position and on the respective distances of their two-dimensional projections from the two-dimensional projections of the respective connecting elements of the first virtual building block.

In a preferred embodiment, for each virtual building block, the digital representation of the structure comprises a number of regular grids corresponding to at least one surface of the virtual building block, each regular grid comprising a number of grid points, each grid point representing a connecting element. Thus, a systematized framework is provided which allows for a correct translation of the 3D position and a correct interconnection of a large number of different building blocks, even if the building blocks have a large number of connecting elements, even different types of connecting elements.

Preferably, the predetermined neighborhood around the projection of the connecting element of the first virtual building block has a linear dimension, such as a diameter, corresponding to the distance between adjacent grid points of the respective regular grid. Thus, a user-controlled precise and fine placement is provided that results in a 3D resolution and predictable, transparent building block connections to the user.

Further preferred embodiments are disclosed in the dependent claims.

The present invention may be implemented in numerous ways, including as a method as described above and in the following, a data processing system, and other product means, each of which yields one or more of the benefits and advantages described in connection with the first-mentioned method, and each of which has one or more preferred embodiments corresponding to the preferred embodiments described in connection with the first-mentioned method.

Note that the features of the methods described above and below may be implemented in software and may be implemented in a data processing system or other processing device by executing computer-executable instructions. The instructions may be program code means loaded in a memory, such as a RAM, from a storage medium or from another computer via a computer network. Alternatively, the features may be implemented by hardwired circuitry, rather than by software or in combination with software.

The invention also relates to a computer program comprising program code means for performing all the steps of the method described above and in the following when said program is run on a computer. The computer program may be embodied as a computer-readable storage medium, the data signal as a carrier wave, and the like.

The invention further relates to a computer program product comprising program code means stored on a computer readable medium for performing the method of the above and below when said computer program is run on a computer.

Drawings

The present invention will now be described more fully hereinafter with reference to the accompanying drawings, in which:

FIGS. 1a-b illustrate a data processing system for generating and manipulating computer-readable models of geometric objects;

FIG. 2 shows a graphical user interface of a virtual building block system;

FIGS. 3a-d illustrate examples of building blocks and their connecting elements;

FIGS. 4a-b illustrate embodiments of digital representations of physical building blocks;

FIG. 4c illustrates an example of a volume element around a connection point;

FIG. 5 shows a flow diagram of a process of positioning a building block in a 3D scene and connecting it to the structure of building blocks already present in the scene;

FIGS. 6a-b illustrate an example of positioning a new building block on top of a previously placed building block;

FIGS. 7a-b illustrate two positions of a building block due to slightly different 2D placements of graphical representations on a screen;

FIG. 8 shows a flow diagram of an embodiment of a connectivity verification subroutine for a new building block in a trial 3D placement;

FIGS. 9a-b illustrate the attachment of building blocks that include rotation.

Detailed Description

FIGS. 1a-b illustrate a data processing system for generating and manipulating computer-readable models of geometric objects;

FIG. 1a is a schematic diagram of an example computer system. The computer system comprises a suitably programmed computer 101, for example a personal computer, the computer 101 comprising a display 120, a keyboard 121 and a computer mouse 122 and/or another pointing device, such as a touch pad, a trackball, a light pen, a touch screen, etc.

A computer system, generally designated 101, is adapted to facilitate the design, storage, manipulation, and sharing of virtual building block models. Computer system 101 may be used as a stand-alone system or as a client in a client/server system.

FIG. 1b shows a block diagram of a data processing system for generating and manipulating a computer-readable virtual building block model. The computer 101 includes a memory 102, which may be implemented in part as volatile storage and in part as non-volatile storage, such as Random Access Memory (RAM) and a hard disk. The memory has stored thereon a model code interpreter 107, a model code generator 108, a UI event handler 109, and a modeling application 110, each of which is executable by the central processing unit 103. Furthermore, the memory has stored therein model data 111, i.e. a set of data structures representing a digital representation of a physical object, e.g. a virtual building block model. An example of a data format for storing virtual building block models is disclosed in us patent 6,389,375.

The code interpreter 107 is adapted to read and interpret the code defining the model, i.e. the code representing the data structure of the building blocks of the model. In a preferred embodiment, the code interpreter is adapted to read the model and convert such model into a known picture format for display on a computer display.

The UI event handler 109 is adapted to translate user interaction with the user interface into appropriate user commands recognizable by the code generator 108. A set of possible and identifiable commands may include: obtaining a building block from a library of elements, placing a building block for connection to another building block, separating building blocks, discarding building blocks, manipulating a building block or a set of building blocks, for example, by initiating a rotation or the like, and the like. Each command may be associated with a respective set of parameters, such as cursor coordinates relative to a display coordinate system, type of building block, and the like.

The code interpreter 108 is adapted to modify the data structure of the model in response to a user's command. As a simultaneous or subsequent task, a code interpreter may be executed that represents the results of the code generator.

The modeling application 110 is adapted to control storage, files, user interfaces, and the like.

The user 105 is able to interact with the computer system 101 by means of a user interface 106, the user interface 106 preferably comprising a graphical user interface displayed on a computer screen, and one or more input devices such as a keyboard and/or a pointing device.

To load, store, or transfer models, geometry descriptions, or other data, a computer system includes input/output units (I/O) 104. The input/output unit may serve as an interface to different types of storage media and different types of computer networks, e.g. the internet. Further, input/output units (I/O)104 may be used, for example, to interactively exchange models with other users.

Data exchange between the memory 102, the Central Processing Unit (CPU)103, the User Interface (UI)106, and the input/output unit 104 is realized by means of a data bus 112.

Figure 2 shows a graphical user interface of a virtual building block system.

The user interface comprises a display area 201 for displaying a 3D scene view of a 3D structure 203 having a chassis 202 and a number of interconnected virtual building blocks 204. The scene is displayed from a predetermined viewpoint. In the following, this viewpoint is also referred to as the (virtual) camera position, since it corresponds to a position from which the camera records an image corresponding to the actual structure of the graphical image shown in the display area.

Each building block 204 corresponds to an active element in the graphical user interface, which may be activated, for example, by clicking with a computer mouse, to select the building block. In one embodiment, the selected virtual building block changes appearance. For example, the selected building block may change color, texture, etc.; this block may be highlighted by displaying a bounding box or the like around the selected block. The user can manipulate the selected building block, for example, to change its properties, such as its color, delete it, perform copy and paste operations, drag and drop it to a different location, and the like.

The user interface also includes a options panel (palette panel)205, the options panel 205 including a number of different building blocks 206 that can be selected by the user. For example, a user may click on one of the building blocks 206 with a mouse to select a building block and drag the selected building block into the display area 201 to attach it to the structure 203 or to the chassis 202.

The user interface also includes a menu bar 207 containing a number of menu buttons 208 for activating various functions or tools. For example, the toolbar may include a rotating tool for changing the position of the virtual camera, allowing the user to view the build area from different directions. The menu bar may further include a zoom tool for zooming in and out of the 3D scene. Other examples of tools include option panel tools for selecting different option panels 205, where each option panel includes different combinations of building blocks, coloring tools for coloring portions of the structure, eraser tools for erasing building blocks, and the like.

The menu bar 207 may further provide standard functions such as a function for saving a model, a function for opening a previously saved model, a function for printing a model image, a help function, and the like.

Fig. 3a-d illustrate examples of building blocks and their connecting elements.

FIG. 3a shows a perspective view of a building block 301. The upper surface 302 of the building block 301 is provided with 8 protrusions 303a-h which can engage with corresponding holes in another building block, for example in the bottom surface of another building block. Accordingly, the building block assembly 301 includes a base (not shown) with a corresponding aperture. The building block 301 also includes a side 304 that does not include any connecting elements.

In general, the connecting elements may be grouped into different kinds of connecting elements, such as connectors, receptacles, and mixing elements. A linkage is a connecting element that can be received by a receiver of another building block to provide a connection between the building blocks. For example, the connector may be received between portions of another component, inserted into an eye, and the like. A receiver is a connecting element that can receive a connecting member of another modular component. The mixing elements are parts that can act both as connecting elements and as receiving elements, which usually depend on the type of cooperating connecting elements of another building block.

FIG. 3b shows a perspective view of the building block assembly 310 from the bottom. The building block assembly 310 has a top surface and a bottom surface that are non-rectangular. The bottom surface includes corresponding raised apertures 311, 312, and 313 for receiving one or more other building blocks, such as building block 301 of FIG. 3 a. The eyelet is defined by a rim 314, by a secondary pin 315, and corners 316 and 317. Thus, the properties of all of the above elements determine the connection properties of the bottom surface of the building block 310.

FIG. 3c illustrates a building block assembly 320 connected to a building block assembly 321 to form a combined building block assembly. The building block 320 includes a projection 322 on an upper surface thereof, the projection 322 being received in a corresponding aperture of another building block. However, as illustrated in fig. 3c, other types of connections may also be implemented. The gaps 323 between the protrusions act as receptacles for other connecting elements, such as the sides 324 of the building block 321. For physical building blocks, this property is determined by the size of the gap and the size of the building block 321, i.e., its lateral width 325. However, in the digital representation, these attributes are represented by the corresponding attributes of the connection points on a regular grid, as set forth in more detail below.

FIG. 3d shows two building blocks 331 and 332. The modular component 331 is brick-shaped with 4 protrusions 333 on its upper surface and 4 corresponding holes on its bottom surface (not shown). Brick 332 is an example of a modular assembly having surfaces that include planes that are not orthogonal to each other. In particular, the building block assembly 332 has a chamfer 334. In the present position, as is illustrated in fig. 3d, the building blocks 331 and 332 are not connected, since there are no connecting elements bonded to each other in the position shown.

It should be understood that the above-described building blocks are merely examples of possible building blocks.

FIGS. 4a-c illustrate one embodiment of a digital representation of a physical building block. The digital representation of the physical building block includes a data structure stored in computer memory, where the digital representation represents an attribute of the building block. According to this embodiment, the connecting elements of the building blocks may differ in kind (nature), shape, connection properties, etc. However, their position on the building block follows a set of rules.

The building block has a number of planes associated with it, such as the plane defined by the bounding box surface of the building block. The connecting elements of the building block assembly lie in these planes such that each connecting element has an axis associated therewith. The axes of all connecting elements in the same plane correspond to respective grid points, so-called nodes, of a regular grid, for example an orthogonal grid, and the spacing between adjacent grid points is fixed. Preferably, the planes associated with the building blocks are parallel to each other in pairs, such as by defining a set of horizontal planes corresponding to the upper and lower surfaces of the building blocks and a number of vertical planes corresponding to the sides of the building blocks. Preferably, the spacing between adjacent grid points is the same in all horizontal planes. In one embodiment, the spacing between adjacent grid points in the vertical plane is not equal to the spacing between adjacent grid points in the horizontal plane.

FIGS. 4a-b schematically illustrate how an embodiment of a data structure describes properties of the building block 301 of FIG. 3 a. In FIGS. 4a-b, a building block 301 and its corresponding orthogonal grids 405 and 406 on its top and bottom surfaces, respectively, are shown. FIG. 4a shows a perspective view of a building block and FIG. 4b shows a top view of a building block. In fig. 4a-b, the grid on the side of the building block 301 is not shown. Some instances of building blocks, such as building block 301, do not have any connecting elements on some faces, such as on the sides. Other examples of building blocks may have connecting elements on all sides.

Orthogonal grids are also referred to as connectivity grids and grid points are also referred to as connection points. The connection points are illustrated by circles as exemplified by circles 407 a-k. Thus, connection points 407a-h correspond to protrusions 303a-h, respectively. Since the sides 304 are free of any connecting elements, there is no need to define any connecting grid for them. In an alternative embodiment, a connection grid may be defined for the side surface that contains only dummy receptors, i.e. receptors that are neither connected nor rejected to other connecting elements.

The digital representation of the building block is described relative to an internal right hand coordinate system 408. It will be appreciated that the choice of the coordinate system, in particular the location of its origin and the orientation of the coordinate axes, may be chosen according to any suitable convention. Thus, in a corresponding data structure, the position and orientation of a building block in a 3D scene may be represented by the origin coordinates of coordinate system 408 relative to an external coordinate system, such as the coordinate system of another building block or a global "world" coordinate system, and the orientation of the coordinate axes.

As can be seen from fig. 4a, representing the connecting elements of a building block by means of connecting points placed in a regular grid imposes certain constraints on the physical placement of the connecting elements on the physical building block. The grid 405 is located in the plane of the upper surface of the building block from which the projection 303 extends.

In the example of fig. 4a-b, grid points are placed in a square grid, where each square has a size of 5 x 5 arbitrary Length Units (LU). Thus, in this geometry, the connecting elements are also placed on a corresponding square grid, and the spacing between the connecting elements in the plane of the building blocks is a multiple of 10 LU. In the example of fig. 4, the upper and lower surfaces of the modular blocks are rectangular with dimensions of 20LU by 40LU and the spatial distance between adjacent connecting elements is 10 LU. On the other hand, in the vertical direction, the spatial distance of the connecting elements is 12 LU.

The location of the connection point is defined relative to the internal coordinate system 408 of the building block. Each grid point also has a direction associated with it, indicating in which direction the connecting element can be engaged with the corresponding connecting element. The direction of the grid points is perpendicular to the plane and points outside the bounding box, i.e. outside the plane of the drawing in fig. 4 b.

In one embodiment, for each connection point, the data structure representing the grid of connection points comprises: coordinates of the connection points relative to the coordinate system 408, orientation of the connection elements, and connection type.

In one embodiment, the data structures representing a building block include a building block ID (identifier), a data structure describing the position, orientation, and size of the bounding box of the building block, and a number of data structures describing the individual grids and their corresponding connection points. The data structure representing a grid of connection points includes:

coordinates of grid points used as origin of the local grid coordinate system with respect to coordinate system 408. In the example of grid 405, grid point 307i is taken as the origin with coordinates P₀(-5, 12, -15) in LU.

-the direction of the connecting element. In the example of grid 405, this is (0, 1, 0), i.e., the Y-axis direction of coordinate system 408.

The number of grid points in the X and Z directions. In the example of grid 405, n are each_x9 and n_z＝5。

-n_x*n_zAn array of data structures, each comprising connection attributes of a respective connection point. The data structure for each grid point includes the connection type of the connection point, e.g., "eyelet", "edge", "bump", etc.

In one embodiment, each connection point also has a volume element associated with it, defining a neighborhood around the connection point.

Figure 4c illustrates an example of a volume element around a connection point. In one embodiment, each connection point has a sphere associated with it, with its center located on the connection point. In FIG. 4c, this is illustrated by the connection points 407g and 407j of the connection grid 405 of the building block 301 described above. For connection points 407g and 407j, respective spheres 410g and 410j are shown, respectively. The radius of the sphere is equal to half the distance between adjacent connection points, e.g. 2.5LU in the example of fig. 4 a-b. It should be appreciated that in alternative embodiments, the spheres may be smaller or larger, i.e., they may intersect or there may be gaps between the spherical surfaces of adjacent spheres, thereby allowing sensitivity control with respect to small misplacement positioning methods.

It should also be understood that different types of volume elements may also be used. For example, the volume element may be a cylinder surrounding the connection element, as exemplified by cylinder 410c surrounding connection point 407 c. In this example, the cylinder has a radius of 2.5LU and a height of 5 LU. Other examples of volume elements include cubes, ellipsoids, and the like.

It should also be understood that in some embodiments different types of connecting elements may be associated with different volume elements, such as volume elements of different sizes, e.g. different radii and/or different heights, or even different geometries. In such embodiments, the data structure representing the connection point may further comprise one or more parameters for identifying the type and/or size of the associated volume element.

It should be understood that when the building blocks are graphically represented on a display, such as a computer screen, the bounding volume, coordinate system, volume elements, and grid need not be displayed. Preferably, the graphical representation comprises only a graphical description of the building block itself.

The process of placing new building blocks into a scene containing a 3D structure will be described in more detail below. Reference will be made to fig. 5 and 6 a-b.

FIG. 5 shows a flow chart of a process of positioning a building block in a 3D scene and connecting it to a building block structure already present in the scene.

In step 501, a new building block is placed in the scene, for example by selecting a building block on an option panel and dragging a graphical representation of the building block to a user-selected position in a 2D display area according to mouse movements, wherein the 2D display area represents a 2D projection of a 3D scene. In one embodiment, when the mouse movement is stopped for at least a predetermined time, such as detected by the GUI event handler, the process proceeds to step 503.

FIGS. 6a-b illustrate an example of positioning a new building block on top of a previously placed building block. The new building block 601 is illustrated as having a bounding box 620, with the bounding box 620 having an upper surface 621 and a lower surface 622, each of which includes a number of connection points, generally designated 603, of a connection grid as described above. Similarly, the previously placed building block assembly 602 has a number of connection points, generally designated 604. The grid of connections and connection points of the sides of the building blocks 601 and 602 are not shown in FIG. 6 a. In this example, the 3D scene includes only one previously placed building block 602.

FIG. 6a illustrates a 2D projection of building blocks 601 and 602 seen in a 2D display area 600 of a computer screen, which corresponds to a 2D display coordinate system 630.

FIG. 6b illustrates the relationship between the 2D projection in the display area 600 and the 3D position of the building blocks 601 and 602 in the 3D coordinate system 640. When a new building block 601 is placed on the screen 600, only its coordinates in the 2D coordinate system 630 are determined and any 3D position that produces the projection 601a coincides with this projection, as depicted by the dashed projection line 631. Thus, the placement of the building blocks on the screen controlled by the user does not provide information about a third dimension perpendicular to the display area. In fig. 6b, the projection is a parallel projection, i.e. the projection lines 631 are parallel to each other, corresponding to the virtual camera position 632 being infinitely distant from the projection plane 600.

Referring again to FIG. 5, in step 503, the process determines, for each connection point of the new building block, whether there is a connection point belonging to any building block already present in the scene (or, if present, to the chassis) that has a 2D projection within a predetermined neighborhood of the connection point projection of the new building block. In one embodiment, for each connecting element of a new building block, a circumference is determined within the display area surrounding the connecting element. Similarly, the respective circumferences of the connecting elements already present in the scene are determined. If any of these circumferences overlap with the circumference of the connecting element of the new building block, the corresponding connecting element is selected as a candidate connecting element.

In FIG. 6a, this step is illustrated with the connection point 605 of the new building block 601. Reference numeral 606 designates a circumference surrounding the connecting element 605. Similarly, reference numerals 608, 610 and 612 denote the circumferences of the connecting elements 607, 609 and 611, respectively, of the building block 602, which overlap the circumference 605. Thus, in this example, the connection elements 607, 609 and 611 are determined to be candidate connection elements. It will be appreciated that in this example, further connecting elements may be selected. However, their circumferences are not shown in fig. 6 b.

It should be noted that the circumferences 606, 608, 610 and 612 correspond to the projections of the respective spheres surrounding the connection elements 605, 607, 609 and 611, respectively. It should be appreciated that in alternative embodiments, different types of projections of volume elements may be used in order to determine which connection elements have projections within the vicinity of the connection elements of the new building block. Further examples of volume elements have been described in connection with fig. 4c above. When using a sphere, the determination of the corresponding projection is particularly efficient, since the projection of a sphere is always a circle, independent of the viewpoint.

In a preferred embodiment, the diameter of the circumference corresponds to the spacing between adjacent connection points in each grid.

It should be further appreciated that in some embodiments, the search for candidate connection elements may be limited to a subset of the connection elements of the building blocks already present in the scene, thereby reducing the time required to complete the search and the size of the resulting list of candidate connection elements. For example, the search may be limited to connection elements that have not yet been connected to another connection element. In one embodiment, the search is limited to connecting elements with suitable connection properties, i.e. connecting elements that can be actually connected to the connecting elements of the new building block, as will be described in more detail below.

Step 530 generates a list 520 of candidate connection elements of the building block that already exist in the scene. Thus, the 3D coordinates of the candidate connection elements are known. In one embodiment, each entry in the list 520 includes: the 3D coordinates of candidate connection points of building blocks already present in the scene, an identifier identifying the respective building block, and an identifier and/or coordinates identifying the respective connection element of the new building block.

In step 505, the list 520 of candidate connection elements is sorted by ranking the candidate connection elements according to a predetermined set of ranking rules.

In one embodiment, the candidate connection elements are ranked according to their distance from the virtual camera, i.e. their relative distance from the projection plane corresponding to the display area 600, and according to the 2D distance between the candidate location and the user-selected placement, i.e. the displacement of the projection of the candidate location in the display area from the location of the graphic of the new building block. For example, candidate locations may be grouped higher for connection elements whose location is closer to the camera location, i.e., more likely to correspond to the location desired by the user. Likewise, candidate attachment points for which the displacement from the user-selected position in 3D is high may be diverged lower.

In some embodiments, the ordering is performed according to other criteria in addition to or instead of the above conditions. Examples of such location ranking rules may include one or more of the following:

-relative distance from camera position;

-a displacement from a user selected 2D position;

-the angle of rotation required by the building block to allow connection with a candidate connection element;

visibility detection, e.g. whether a candidate connection element is visible from the current camera position. In some embodiments, candidate connection elements that are not visible from the current camera position are discarded from the list.

In some embodiments, several or all of the above criteria may be applied in combination, for example by defining a cost function of the above conditions, optionally with corresponding weighting factors. In other embodiments, the ranking is first performed according to one of the above rules, e.g. the required 2D displacement. If two or more candidate connection elements have the same rank, they may be distinguished by another rule, such as relative distance from the camera, required rotation, etc.

Thus, ranking of the determined candidate connection elements is complete, and the ordered list 520 corresponds to an ordered list according to the ranking described above. Here, the ordered list 520 includes all candidate connection points that have not been dropped based on the location ranking rule described above.

In step 508, it is determined whether the ordered list 520 is empty. If the list is empty, i.e. no connecting element has a sufficiently small projected distance to the connecting element of the new building block, then the 3D placement is rejected (step 509), i.e. the process terminates; otherwise, processing proceeds to step 510.

If the process terminates by rejecting the 3D placement (step 509), it is preferably indicated to the user, for example by providing a visual indication. For example, a graphical representation of a building block that is moved in response to mouse movement may be displayed in a form that indicates that the building block has not been placed. Only when a 3D placement is found, the graphical representation switches, indicating to the user that the placement has been completed. For example, as long as the 3D placement is not successfully completed, the building blocks may be displayed as transparent and/or with visible bounding boxes and/or blinking and/or any other suitable form.

In step 510, the candidate connection element with the highest ranking is selected and the new building block is placed in the 3D coordinate system such that the coordinates of the selected candidate connection point and the coordinates of the corresponding connection point of the new building block coincide. Therefore, the candidate position according to the highest ranking is selected. It should be understood that the placement is only tentative, i.e. not yet displayed on the computer screen.

In step 511, the process verifies whether the connection complies with a predetermined set of connection rules, e.g., whether the connection elements on these and other connection points of the new building block allow connection with the connection elements of the building block to which the new building block is to be connected. The check of which an embodiment will be described in more detail below will also be referred to as connectivity verification. In a preferred embodiment, the process further verifies whether the new building block is visible from the camera position when connected to the candidate connection element, or whether it is completely obscured by existing structure (obsstruct). If the connection is rejected or the building block will not be visible, then the tentative 3D placement is rejected and the process proceeds to step 512; otherwise, if the process successfully verifies the connection, the process proceeds to step 513.

In step 512, the candidate attachment point for which the connection is rejected is removed from the ordered list 520 and processing returns to step 508, i.e., if present, the next candidate attachment point is selected.

In step 513, i.e. if the connection check is successful, the 3D placement is accepted, i.e. the graphical representation of the structure is updated by "snapping" the new building block at the accepted position and by changing the appearance of the building block. In one embodiment, the user may accept the location, such as by clicking with a mouse on the building block, to complete the placement process. If the user wishes to place a building block at another location, the user can simply move the mouse without clicking on the building block, changing the appearance of the new building block back to the original appearance, and moving the building block to another location in the 2D display area.

The process maintains a set of data structures, each representing a building block placed in a 3D scene, for example as described in connection with FIGS. 4 a-b. When accepting 3D placement of a new building block, the process updates the set of data structures by adding a new instance of the data structure corresponding to the new building block as part of the set of data structures.

FIGS. 7a-b illustrate two positions of the new building block of FIGS. 6a-b resulting from slightly different 2D placements of the graphical representation on the screen. In FIG. 7a, a building block 701 is placed on top of a structure 702. On the other hand, in FIG. 7b, the building block 701 is positioned behind the structure 702 on the chassis 703. Thus, a small adjustment of the 2D position of the new building block allows the user to distinguish between two quite different placements in the 3D scene. FIGS. 7a-b further illustrate the different appearance of the new building block 701 as compared to the building block 704 of structure 702 as it is manipulated by a user.

FIG. 8 shows a flow diagram of an embodiment of a connectivity verification subprocess 511 of a new building block in a tentative 3D placement. Thus, the process verifies whether the new building block can be connected to at least one other building block of the existing structure. This other building block is referred to as the second building block.

In an initial step 801, the process performs conflict detection and visibility checks, i.e. checks if the new building block intersects any other building blocks already present in the scene, and checks if the new building block will be completely occluded by the already existing structure and thus not visible from the current camera position. The collision detection may be performed by any suitable collision detection method, preferably a collision detection method based on the boundary range of the building block. An example of such an algorithm is disclosed in, for example, "3D Game Engine Design" by David h. Likewise, the visibility check may be performed by any suitable method known in the art. If an invalid intersection point is detected, i.e. if the boundary ranges of the building blocks intersect, or if the building block will not be visible from the current camera position, then refusing to place the building block at this position and orientation; otherwise, if the building block will be at least partially visible and if a valid intersection point is detected, i.e. if at least part of the bounding box surfaces intersect but their volumes do not intersect, then the process proceeds to step 802.

In step 802, all connection points of the new building block and the second building block belonging to the detected intersection of the bounding box surfaces are determined. Only those connection points that have not yet been connected need to be considered; these connection points will be referred to as relevant connection points.

In step 803, a first relevant connection point, e.g., an arbitrarily selected connection point, of the new building block is selected.

In step 804, for a selected connection point of a new building block, the process checks whether there are any associated connection points of a second building block having the same coordinates as the selected connection point. In an embodiment where the building blocks are placed in a discrete volume reference grid and all coordinates are multiples of any length unit, an exact match of coordinates may be required. In a continuous or quasi-continuous reference coordinate system, grid points may be required to be consistent within predetermined limits.

If no such matching connection point is found, then the process proceeds to step 814.

In step 814 it is detected whether there are any other relevant connection points within a predetermined proximity of the selected connection point. For example, in an embodiment in which the spacing between two adjacent connecting elements is 10LU, the predetermined neighborhood may be selected as a cube (x + -5 LU, y + -5 LU, z + -5 LU) surrounding the selected connection point located at (x, y, z). If there are any other relevant connection points within the predetermined neighborhood of the selected connection point, then the connection of the two building blocks is rejected (step 811) and the algorithm terminates. Thus, when the connection points in this embodiment are placed on a regular grid, an invalid placement of a building block can be effectively detected: if for one of the relevant connection points of a new building block a mismatch with the relevant connection point of a second building block is found, there is no need to detect the remaining connection points of the new building block, thereby increasing the speed of the detection process.

If no conflicting relevant connection points are found in step 814, the process proceeds to step 809.

If a matching connection point is found in step 804, the process proceeds to step 805, where it is detected whether there are any other relevant connection points within a predetermined neighborhood of the selected connection point, for example within a cube (x ± 5LU, y ± 5LU, z ± 5LU) surrounding the selected connection point located at (x, y, z) as described above. Rejecting the location if another connection point is found within the predetermined proximity (step 811); otherwise, the routine proceeds to step 806.

In alternative embodiments, the above-described constraints may not be desirable. Also, in yet another embodiment, the constraints may be limited to certain connection types.

In step 806, the process detects whether the selected connection point and the detected matching connection point have opposite directions, i.e. whether their associated axes are along the same line but in opposite directions. Thus, only the connecting elements positioned in the relative orientation appropriate for their engagement are accepted.

It should be noted that in alternative embodiments, this limitation may be relaxed, for example by accepting a range of orientations in embodiments in which the connecting element accepts a range of orientations.

If the relative orientation of the connection point is accepted, then the process proceeds to step 807, otherwise, the location is rejected (step 811).

In step 807, the connection types of the selected connection points and the corresponding detected matching connection points are compared. In one embodiment, each connection point has an associated connection type, such as "tab," "eyelet," "edge," "corner," "hinge," "pin," or the like. The process accesses a connection table 813 stored in memory. The connection table includes connectivity types for all pairs of connection types, indicating how a particular pair of connection types affects the connection of two building blocks. For example, each pair of connection types may be associated to a connectivity type of "true", "false", or "null". The connectivity type "true" indicates that the connection is valid and that the corresponding connecting elements are engaged to connect two building blocks, e.g. protrusions in combination with corresponding eyelets. The connectivity type "false" indicates that the connection is not allowed. For example, a connection between the protrusions is not possible: not only do they do not bind to provide a connection, but they even interfere/interfere, making connection impossible. Finally, the connectivity type "null" indicates that there is nothing to block the connection, nor anything to actually connect. For example, eyelets and holes are examples of such. Thus, for a given pair of connection points, the process can retrieve the corresponding connectivity type from the stored connection table 813.

In a following step 808 it is checked whether the connectivity result is "false", i.e. there is no possibility of any valid connections between the respective connection types. If the connectivity result is "false", then the position of the new building block is rejected (step 811), otherwise the connectivity result is stored and the process proceeds to step 809.

In step 809 it is checked whether all relevant connection points of the new building block have been processed. If not, the relevant connection point that has not yet been processed is selected (step 812) and the currently selected connection point is processed by performing the above steps 804, 805, 806, 807 and 808.

If all relevant connection points for the new building block have been processed and the location has not been rejected, then the location is accepted and the process proceeds to step 810. In step 810, it is determined how building blocks are connected based on the stored connectivity results, and their respective data structures are updated accordingly.

Initially, it is checked whether all connectivity results are "null". If so, i.e., if nothing prevents the position of the building block, but no connecting elements actually engage to connect the building block, then the new building block is allowed to be in its current position. In one embodiment, additional algorithms may decide whether a physical building block placed at this location will fall, tilt, etc., based on, for example, a boundary range, and allow or deny this location accordingly.

Otherwise, i.e., if one or more connectivity results are true, the process determines how the building blocks are connected, i.e., whether they are rigidly connected or whether the connection allows relative rotation, translation, and/or the like.

Once the data structure is updated, the sub-process terminates and returns to the overall process of FIG. 5.

FIGS. 9a-b illustrate connections involving rotating building blocks. In some embodiments, the connection point is checked only for the orientation of the new building block visible on the screen, i.e. the orientation selected by the user or the default orientation. When the user wishes to connect a new building block after the building block has been rotated, the orientation may be controlled by an appropriate user interface control, for example by means of a rotation tool which may be selected in a menu of a graphical user interface, by means of keyboard commands, etc. For example, the user may control the orientation of the new building block such that a sequence of discrete orientations is traversed step through (step through), e.g., corresponding to 90 degrees of rotation about different axes. For example, in FIGS. 9a and 9b, building block 901 is connected to structure 902 in a different manner depending on the user-selected orientation of building block 901. In FIG. 9a, a building block 901 is attached to the top of a structure 902. In FIG. 9b, the building block 901 is attached to a protrusion 903 in a structure 902 that lies in a vertical plane.

In an alternative embodiment, automatic reorientation of the building block is allowed. For example, when analyzing candidate locations in steps 510 and 511 of FIG. 5, different rotations of the new building block may be considered as additional candidate locations and analyzed according to the hierarchy implemented and subsequent connectivity verification. For example, when a new building block is to be attached to a hinge at some arbitrary angle, the user does not have to precisely align the new building block to the axis of the hinge. The process will estimate the rotated position and connect a new building block after the rotation. In some embodiments, the automatic redirection is limited to a predetermined spatial angle, e.g., 45 degrees, 30 degrees, etc., thus avoiding large rotations that may confuse the user and lead to unexpected results.

Another advantage of the above process is that the user receives a clear indication of where a new building block will be placed and connected. Moreover, small corrections of the 2D position of new building blocks on the screen controlled by the user are taken into account, thereby providing a fluent and natural workflow impression.

It will be appreciated that variations of the above-described method may be implemented by those skilled in the art within the scope of the present invention. For example, the order of some of the above-described steps may be changed, steps may be combined, etc.

For example, after a new building block has been placed into a 3D scene, the user may launch a search tool to search for similar locations. In one embodiment, the search tool may allow the user to step through all of the positions of the ordered list 520 of FIG. 5, allowing the user to select one of the possible positions.

The term "manipulating" the digital representation of the object is used to represent any user-controlled operation on the digital representation, such as the connection of a new building block, moving an existing building block from one position to another, or any other operation that changes the position of a building block in a 3D scene.

Claims (14)

1. A computer-implemented method of manipulating a three-dimensional virtual building block model by means of two-dimensional cursor movements, the virtual building block model comprising a plurality of virtual building blocks, wherein each virtual building block comprises a number of connecting elements for connecting the virtual building block to another virtual building block according to a set of connecting rules, the method comprising:

-providing a digital representation of a virtual building block model in a three-dimensional coordinate system, wherein the virtual building block model comprises a number of said virtual building blocks;

-positioning a two-dimensional projection of a first virtual building block to be connected to the virtual building block model by means of a cursor movement in a two-dimensional computer display area representing the projection of the virtual building block model, resulting in two-dimensional position coordinates;

-determining a number of three-dimensional candidate positions of the first virtual building block in the three-dimensional coordinate system from the two-dimensional position coordinates;

-selecting one of said candidate locations based on said connection rules and a set of predetermined location ranking rules; and

-connecting the first building block to the virtual building block model at the selected candidate position.

2. The method of claim 1, wherein the step of determining a number of three-dimensional candidate positions further comprises determining a number of candidate orientations of the first virtual building block in the three-dimensional coordinate system.

3. The method of claim 1 or 2, further comprising:

-determining a number of candidate connecting elements of said virtual building block model, wherein each of said candidate connecting elements has a projection within a predetermined neighborhood around the projection of the connecting element of said first virtual building block within said two-dimensional display area;

-selecting one of said candidate connection elements based on said connection rule and said set of predetermined position ranking rules; and

-connecting the first virtual building block with the virtual building block model at least by the selected candidate connecting element if the connection between the first virtual building block and the virtual building block model is valid according to the set of connection rules.

4. The method of claim 3, wherein the step of selecting one of the candidate connection elements further comprises ranking the candidate connection elements, wherein the ranking is performed with respect to their distance from a virtual camera position.

5. The method of claim 3, wherein the step of selecting one of the candidate connection elements further comprises discarding candidate connection elements that are not visible from the current virtual camera position.

6. The method of claim 3, wherein the step of selecting one of the candidate connection elements further comprises ranking the candidate connection elements, wherein the ranking is performed with respect to the distance of their two-dimensional projection from the two-dimensional projection of the corresponding connection element of the first virtual building block.

7. A method as claimed in claim 3, wherein for each virtual building block, the digital representation of the virtual building block model comprises a number of regular grids corresponding to at least one surface of the virtual building block, wherein each regular grid comprises a number of grid points, each grid point representing a connecting element.

8. The method of claim 7, wherein a diameter of a predetermined neighborhood around a projection of a connecting element of the first virtual building block corresponds to a spacing between adjacent grid points of the respective regular grid.

9. The method of any of claims 1-2, wherein the step of determining a number of candidate positions further comprises rotating the first building block to obtain the rotated building block candidate positions.

10. The method of claim 9, wherein the rotation of the first building block is limited to a predetermined spatial angle around a user selected orientation.

11. The method of any of claims 1-2, further comprising receiving a user command to control a user-selected orientation of the first virtual building block.

12. The method of claim 11, wherein the user-selected orientation is limited to one of a set of discrete orientations.

13. The method of any of claims 1-2, wherein the two-dimensional projections are parallel projections.

14. A data processing system for manipulating a three-dimensional virtual building block model by means of two-dimensional cursor movements, the virtual building block model comprising a plurality of virtual building blocks, wherein each virtual building block comprises a number of connecting elements for connecting the virtual building block to another virtual building block according to a set of connecting rules, the data processing system comprising:

-storage means (111) for storing a digital representation of a virtual building block model comprising a number of said virtual building blocks in a three-dimensional coordinate system;

a display device (120);

an input device (122) for receiving user input indicative of cursor movement in a two-dimensional computer display area displayed on the display device representing a projection of the virtual building block model; and

processing means (103) for:

determining two-dimensional position coordinates representing a two-dimensional projection of a first virtual building block to be connected to the virtual building block model from the cursor movement;

determining a number of three-dimensional candidate positions of the first virtual building block in the three-dimensional coordinate system according to the two-dimensional position coordinates;

selecting one of the candidate locations based on the connection rule and a set of predetermined location ranking rules; and

connecting the first building block to the virtual building block model at the selected candidate position.