Optimal 2D Placement of Virtual Objects in Physical Space for Augmented Reality Applications

Introduction. A well-known task of augmented reality (AR) applications is the placement of virtual objects in real physical space. A number of studies [1–3] focus on interactivity, the merging of real and virtual spheres. The issues of physical properties of virtual objects are also studied.

The task of such placement of objects, which would be free and optimal at the same time, taking into account not only the geometry of objects, but also comfort zones around them, has not been sufficiently worked out. In [6], the external similarity of this problem and the well-known problem of packing into a rectangular container is noted [5]. However, there is a significant difference. In the case under study, it is not enough to provide the greatest possible dense packaging. When placing virtual objects, it is required to take into account not only their rigid dimensions, which cannot be violated, but also additional areas — comfort zones. It is undesirable to occupy them. These additional areas provide getting closer to the object and performing some actions with it.

Materials and Methods. Earlier [4], the authors defined what a comfortable placement of virtual objects was, and introduced the concept of comfort function k(x). It increases monotonically from 0 to 1 at 0≤x≤1 and is equal to 1 at х>1, where x = X/D, X — distance from the edge of the object to the nearest obstacle, D — size of the comfort zone. For each measurement, the object has two one–way comfort zones D– and D+. Comfort on each side is calculated separately.

It is shown in [6] that the problem of one-dimensional placement of n virtual objects in a free region of space with length L is reduced to a system of linear equations that do not depend on the type of comfort function k(x):

Here,

— distance of the first object from the left edge of the embedding area;

— distance between objects with numbers i and (i – 1);

and — left and right comfort zones, respectively;

l⁽ⁱ⁾ — object size;

,

i = 1,2,…, (n – 1).

Matrix of system (1) is strongly sparse; therefore, it is possible to avoid using not the fastest universal methods, it is easy enough to find a solution. As an example, in the first (n – 1) equalities, it is possible in each i-th equation, to express by , then, substitute this into the last equation and get a linear equation with respect to .

After that, values are sequentially determined from the first equation to the (n – 1)-th. The authors implemented this 1D algorithm for placing objects using numerical methods. It showed high speed and efficiency. This 1D algorithm became the basis for the scientific research described in the presented paper. The authors proposed a 2D algorithm for optimal placement of virtual objects It was implemented in the form of C# programming code using the Unity game engine, which is widely utilized to create augmented reality mobile applications [8]. During the experiment, an algorithm was run on the user's device operating in peak load mode to 5, 10, 15, 20, 25, 35, 40, 45, and 50 objects. The time spent on calculations was measured (in milliseconds). Each calculation was repeated 10 times to avoid abnormal values. In total, 1.8 thousand devices participated in the experiment, about 77 thousand events with the results were collected from them and analyzed.

Filtering anomalies using z-score allowed the authors to identify values that can be defined as outliers [9]. The data was standardized, and a z-score was calculated for each value. Those with a z-score greater than 3 or less than –3 were considered abnormal. They were excluded and focused on typical and representative data.

Research Results. Thus, on X, Z plane there is a rectangular area with width and length It should be filled with a certain number of virtual objects. Each object, in addition to its size (where i — number of the object), is also characterized by comfort zones . Figure 1 shows a block diagram of the described algorithm.

In this work, a left-sided coordinate system is used: X-axis denotes the horizontal placement vector, Z-axis is directed forward from the user and is the depth vector, or frontal measurement [7]. Objects are placed in a horizontal plane (e.g., on the floor, countertop, etc.), therefore, the vertical Y-axis is not considered, and all illustrations assume a top view of the resulting composition.

In the lower left corner of each virtual object, a pivot is denoted. It determines the final coordinates of the object placement. Next, the set of objects is sorted in descending order by — overall length of the objects, taking into account the comfort zones located in front and behind in accordance with the coordinate axis under consideration. After sorting, objects that occupy more space in depth are located farther away from the user (or higher — for the scheme presented in the horizontal projection). A block diagram of the formation of a batch of objects is shown in Figure 2.

Then separate strings, or batches, are formed from the ordered set of objects. Each string includes the minimum number of objects, the sum of the width of which, together with the comfort zones, exceeds the width of the filled region . If, when adding the next object, the calculated occupied width exceeds the horizontal size of the available space inside the rectangle, the batch is considered completed. Thus, each batch can be placed as a line within the region. Rows alternate from left to right and from right to left to mix large and small objects. This can be called a “shuttle run” (Fig. 3).

For the formed row, 1D-placement algorithm is used, which provides for the optimal placement of a number of objects along X-axis based on the calculated comfort coefficient К, which is the same for all objects in the row. For each object of the first string, Z-axis offset from the edge of the plane is determined in such a way that the comfort in front is equal to the comfort along X:

.

Starting from the 2nd row, to calculate Z₊ indent, the presence of potential neighbors from above from the overlying row that have common sections with the current object being processed along X coordinate is checked. At the same time, each object of the placed row is installed along Z-axis in such a way that its comfort from above is the maximum of the one-sided horizontal comfort in this row and the previous rows. The algorithm for calculating Z coordinates is shown in Figure 4.

It can be seen from the flowchart that the indent is calculated similarly for all three possible scenarios:

• indent from the edge of the plane to install the object;
• indent from the neighbor from above;
• in the absence of a neighbor in the previous string, the object closest from all previous strings along Z is taken.

New batches are formed until all objects are assigned a row, or until the physical space runs out.

The initial data for the described algorithm are systematized in Table 1. Objects are sorted by their vertical dimensions.

Table 1 corresponds to Figure 5, which demonstrates the placement of objects.

A gray rectangle is a free area on which objects are placed. Black areas are objects in their overall dimensions. Colored areas, with overlays, are preset comfort zones for each object. As noted above, comfort zones of objects may partially overlap and go beyond the free space, but the approach used allows for a balance so that the comfort of various objects is equally reduced.

Recall that this model includes the concept of comfort function k(x). The resulting system of equations (1) does not depend on it, and hence the optimal placement of objects. But the values of one-sided comfort of objects are determined both by their placement and by the type of function k(x). Here are two examples:

• in the case of linear function k(x), one-sided comforts of objects in the upper row of Figure 5 are equal to 0.6;
• for dependence — value 0.9.

After the software execution of the described 2D algorithm, it was implemented into an augmented reality mobile application, and the analytical data of user sessions was recorded. The authors grouped information for each unique device model, for each number of objects placed in the range [10]. The average execution time was calculated (Fig. 6).

Within the specified range, it is impossible to immediately determine the exact complexity of the algorithm calculation. As can be seen from Figure 6, the data are close to linear and quadratic approximations. Using the residual sum of squares method, a quantitative estimate of both approximations was calculated and values of 0.00035 and 0.00021 were obtained, respectively [10].

The execution time on different user devices was compared, 10 most popular models were selected, and a diagram based on the calculations results was built (Fig. 8).

The minimum registered execution time was 0.093 ms, the maximum — 0.146 ms. For this sample, the correlation between the device model and the execution time was only 0.177. This is a pretty low value.

Calculations have shown the high efficiency of the two-dimensional algorithm. This is due to the splitting of the entire set of objects into separate strings and the use of a fast one-dimensional algorithm in each string, described at the beginning of the article. This algorithm provides solving the problem with less resources and time.

Figure 9 shows additional visualizations of placement schemes for different numbers of objects and their parameters.

Thus, the proposed algorithm of two-dimensional placement provides working with a set of virtual objects. Each of them is characterized by certain sizes and comfort zones. The algorithm is designed to optimally position such objects in a rectangular physical space that recreates the user's environment.

Discussion and Conclusion. For the previously described one-dimensional problem, an effective algorithm for optimal placement of virtual objects is proposed and implemented in the program code. A model of optimal placement was constructed for the two-dimensional case. Based on it, an effective algorithm has been developed, implemented in the program code.

The performance of the algorithm, which was measured by the execution time, was analyzed. It was found that there was no significant correlation between the execution time and the device model. The average time was fractions of a millisecond even for large batches of objects. This indicated a relatively stable performance of the algorithm under various conditions. However, the possible influence of other untested factors cannot be excluded. Further research is needed to fully characterize performance dependences.

The authors outline several areas of future work to improve the performance and adaptability of the algorithm. This is, firstly, the improvement of the solution, which will allow using the full size of objects, when possible, without intersections of comfort zones. Their sizes will be reduced only if absolutely necessary. This should provide for optimal use of space and further improve the interactive user experience.

Secondly, the inclusion of rotation of elements in the algorithm will increase flexibility in their arrangement and make it possible to use space better. In addition, this will allow the algorithm to take into account more different objects, thereby expanding its practical application.

Note that in an augmented reality application, placing three or more objects by the user is a rather time-consuming task. It requires considerable time, and significantly complicates the work.

The proposed technology for placing objects in 2D allows the optimal positioning of virtual content to improve the user experience in augmented reality. Automated location calculation reduces manual work and makes it possible to focus on valid interaction with AR.

Scientific research in this direction involves seamless integration of virtual and physical spaces. The results can be applied in practice by developers of augmented reality glasses who face the problem of rapid intelligent positioning of objects depending on user preferences and context. Moreover, the results of the work may be of interest to:

• engineers working on smart home systems;
• interface designers, for whom it is important to effectively and harmoniously combine controls and information on the screen.

The introduction of fuzzy logic allows developers to adapt the solution to specific tasks and use cases. In future research, it is advisable to study and apply user experience, include additional restrictions on the positioning of objects.