Optimal 2D placement of virtual objects in physical space for augmented reality applications

Introduction. Research and applied works on the placement of virtual objects in real space most often focus on issues of interactivity, integration of reality and virtuality, physical properties of virtual elements. However, the task of simultaneously free and optimal placement of objects, taking into account their size and the surrounding comfort zone, has not been sufficiently worked out. In the literature, you can find a description of a similar task - about packing in a rectangular container. In our case, the goal is not limited to the greatest possible dense placement. Two conditions should be taken into account: rigid dimensions of the objects (it is forbidden to violate them) and additional areas - comfort zones (it is undesirable to occupy them). The work aims at creating and implementing such a 2D algorithm for placing objects in physical space, which takes into account the above limitations.Materials and Methods. Using a set of numerical methods, the authors applied the previously created 1D algorithm for the placement of objects. Calculations were based on a system of linear equations. In the one-dimensional case, the optimal placement of virtual objects was reduced to a task that did not depend on the type of comfort function. The elements of such a system were the dimensions of objects, the distances between them, as well as the distances to the edge of the embedding area, a comfort zone. The proposed 2D algorithm for optimal placement of virtual objects was implemented in the form of a program code in C# using the well-known Unity game engine. The solution was tested on gadgets in peak load mode for 5, 10, 15, 20, 25, 35, 40, 45, and 50 objects. 1.8 thousand devices were used for experiments. About 77 thousand events were analyzed. To exclude unrepresentative values, each calculation was repeated 10 times, and a z-score was performed for each value. Abnormal events (more than 3 and less than -3) were excluded.Results. In this paper, a 2D placement algorithm that implements filling a rectangular area with virtual objects has been created. Each of the objects had a size and another characteristic - a comfort zone. The authors compiled a flowchart for the implementation of this algorithm in a given two-dimensional left-hand coordinate system. It was shown, in particular, at what stage objects were sorted by length, when their batches were formed, and arrangements were made along two axes. The first axis was horizontal, the second was directed forward from the user (this is the depth vector, or frontal measurement). The 1D-placement algorithm for the generated row provided optimal positioning the objects along X-axis based on the calculated comfort coefficient К. Calculations were made and schemes were drawn up to obtain certain comfort indicators. For each object of the first string, the displacement along Z-axis from the edge of the plane was determined so that the comfort in front was equal to the comfort along X. Starting from the 2nd row, to calculate the displacement, the presence of potential neighbors who were a row higher and had common areas along X with the object being processed, was checked. Each element of the string was set along Z-axis so that its comfort from above was the maximum of the one-sided horizontal comfort in this and the previous strings. The principle of calculating Z coordinate for a string object was presented in the form of a flowchart. The initial data for the implementation of this algorithm were 7 objects with 14 different sizes and 28 comfort zones. After the software implementation, the operation of the described 2D algorithm was tested in practice - in an augmented reality mobile application. Analytical data of user sessions was recorded. The average execution time was calculated. The hypothesis of quadratic dependence that arose during the work was tested on a personal computer. For this purpose, a similar experiment was conducted for a range of [10-10,000] objects. The hypothesis was confirmed. The algorithm can be assigned a complexity of O(n2). To compare the calculation speed, 10 of the most popular models of user devices were utilized. The results were presented in the form of a diagram. The minimum registered execution time was 0.093 ms, the maximum - 0.146 ms. Calculations showed high efficiency of the two-dimensional algorithm. Additionally, the placement schemes for different numbers and parameters of objects were visualized.Discussion and Conclusion. The proposed algorithm of two-dimensional placement enables the user to work with a set of virtual objects with different sizes and comfort zones. Sufficiently high performance and stability are shown. On average, the algorithm is implemented in fractions of a millisecond, even with large batches of objects.