Introduction

This independent master's dissertation, which spanned four months, initially aimed to develop innovative interactions for particle-based displays (PBDs). An example is leveraging levitating particles to enhance the perceptiveness of mid-air haptics. However, due to physical constraints at the time, the prototype was less effective. Given the timeframe, the project's focus shifted to addressing the initialisation problem of PBDs. Consequently, it concentrated more on technical aspects than on interaction design.

Background

PBDs

In this context, particle-based displays refer to the use of acoustic levitation (ultrasound) to manipulate small particles, creating a variety of rich content. This emerging technology facilitates crafting multimodal experiences in mid-air. By levitating various types of primitives, it allows users to see, hear, and feel the content without the need for any additional devices.

Initialisation Problem

Unlike traditional displays, where the screen is illuminated by pixels, particle-based displays rely on positioning primitives at mid-air target locations before use. We refer to this process as initialisation, an essential stage for particle-based displays, which lays the foundations for subsequent applications. Although existing research has significantly advanced the development of PBDs, initialisation tools that automatically detect and lift levitation primitives remain comparatively unexplored. As a result, the process is often completed by manual placement or ad-hoc implementations, which restricts the practical utility.

Problems to Solve

In a nutshell, the initialisation process has several critical steps:

1. Detection: locate user-placed beads on the ground.
2. Tasking Allocation: assign beads to defined destinations.
3. Moving: levitating each bead to the destination without colliding with each other.

Detection

The detection of beads is based on computer vision, which identifies their locations. This allows the system to create acoustic traps at these points and subsequently move the beads to their intended destinations.

Task Allocation

In this phase, each bead is assigned to a unique target position in the particle-based display, ensuring efficient placement. Optimal allocation minimises bead travel distance, enhancing system efficiency. However, suboptimal allocation can cause longer setup times, resource wastage, and potential system failures. Therefore, choosing the most efficient allocation method is crucial.

Path Planning

Particle-based displays, unlike traditional pixel-illuminated displays, create content by levitating multiple primitives. Essential to this process is maintaining minimum distances between primitives due to the principles of acoustic levitation. Failing to do so can lead to issues like particle convergence or displacement. Therefore, effective path planning to avoid collisions is critical for successful initialisation.

Development

The development of this project is based on OpenMPD, an open-source platform for supporting PBDs.

Improvement of Detection

The current solution employs a Logitech C920 webcam for input and the OpenCV library for image processing. This setup, however, only supports initial bead detection and cannot track their subsequent movements, hindering continuous tracking. Additionally, it depends on basic webcam images and needs manual calibration each time the system starts, which reduces speed and user experience. To address these issues, we integrated an additional tracking method using OptiTrack and its Unity Plugin. This enhancement successfully overcomes the previous limitations, improving continuous tracking and user experience.

The image on the left hand side shows the improved system with OptiTrack, the one on the right hand side shows a screenshot with a Unity client with OptiTrack plugin integrated.

Improvement of Task Allocation

The existing solution assigns beads to destinations using a first-come-first-serve approach, which is inefficient for large quantities of beads as it doesn't consider minimising overall travel distance. To improve this, we introduced two algorithms: a brute force method for scenarios with fewer than 6 beads, and The Hungarian Algorithm for larger bead counts. This approach guarantees optimal matching, ensuring the minimum overall travel distance, while also maintaining efficiency in terms of time complexity.

This figure demonstrates a simple allocation example using two beads. Figure A shows a suboptimal allocation result, which increases the overall travel distance, while Figure B is an optimal matching. The dashed line indicates the trajectory

Introduction of Path Planning

Another important aspect of initialisation is to avoid collisions of beads, otherwise the system will fail. At that date of time, there was no implementation of path planning, so we introduced our own method. We adopted the concept of a potential field, which can be envisioned as a landscape of hills and valleys. The current moving bead can be seen as a ball rolling in this landscape. Its target position represents the deepest valley drawing the bead towards its destination. Conversely, existing particles (obstacles) can be analogised to hills, preventing the bead from getting too close.

Figure A shows a modelled potential field with a 3D scatter plot, each axis corresponds to the axis of the levitator, while the potential is encoded by the colour. The predominant purple hue signifies a negative potential, which pulls the bead into the target position (red dot). Conversely, The colour around the two obstacles (blue dots) is yellow, indicating the high potential to repel surrounding particles. Figure B is a visualisation of the potential field with a fixed Z coordinate (z = 0), which is a ‘slice’ of Figure A, providing a clearer view of the potential field. Figure C employs a hills-and-valleys metaphor: Hills represent the positions of obstacles, repelling approaching particles, while the valley represents the target position, drawing beads into the destination. The red line denotes the moving direction of the particle.

Evaluations

Our in-lab evaluation, comprising 240 trials, indicated a significant enhancement in the initialisation process. The improvements were notable in both the success rate and the completion time, with a maximum improvement of up to four times compared to the original method.

Particle trajectory with collision avoidance for different numbers of obstacles, which shows no particle enters into the collision area of obstacles (represented by the elliptical shape).

Summary

• It is integrated into OpenMPD, a growing standard for particle-based displays.
• It enables the detection with either an RGB camera or a 3D tracking system (OptiTrack), both are available to the OpenMPD community.
• It guarantees the optimal allocation of beads to their respective target positions to minimise overall travel distance.
• It considers the topology of acoustic traps and plans particle movement trajectories to avoid collision with each other.