Collision-based Partitioning for 3D Virtual World

In 3D virtual world, such as MMOG and 3D internet, massive multiple avatars co-exists in one virtual world. In order to realize “real” virtual world for their players, servers must handle and response their requests quickly. Because quick handles and responses require a lot of CPU resources, most of these systems use multiple servers for one virtual world.
One of problems of systems, in which multiple servers manage one virtual world, is deciding the boundaries of territories for each server. In these systems, interactions among avatars across boundaries become slow caused by physical network interaction among servers.
In this letter, we propose a conceptual method for portioning of 3D virtual world, collision-based partitioning method.
In this method, programmers of a virtual world define a collision-define-function for the world. The function outputs “two positions in the virtual world” and “their strength” from the virtual world status. A system connects two positions as a collision-line with the strength for each output and memory them. For each constant interval, the system decides boundaries for each server to minimize (1) sum of strengths of lines across deciding boundaries and (2) differences of sums of strengths of lines for each territory, by using graph-cutting-algorithm (cutting algorithm is out of this patent).

By: Hiroshi Horii, Toshihiro Takahashi

Published in: RT0904 in 2010


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to .