Geometric algorithms for message filtering in decentralized virtual environments

Distributed virtual environments impose a heavy load on the network upon which they reside. Bandwidth is a potential bottleneck because n users imply O(n²) update messages per time unit, which is prohibitive for a large number of users. Efficient message filtering is called for, in both centralized systems, having a central server, and decentralized systems, having no central server. We solve the message filtering problem for decentralized multi-user systems based on geometric virtual worlds, popular in interactive 3D graphics applications. This is achieved by exploiting the visual relevance relationship (based on proximity, visibility and direction criteria) between pairs of users to compute mutually irrelevant regions in user parameter space. These regions are then used as up-date-free regions (UFR's); i.e. no communication between users is required while they are in their respective regions. Geometric algorithms for computing UFR's for the proximity, visibility and direction relevance criteria are described. Our implementation and experimental results show that the message-filtering algorithm is output-sensitive. Use of our algorithms is especially effective where messages are sent through a slow communication network, such as the Internet.