Method of area partition in virtual environment

Details Method of area partition in virtual environment Method of area partition in virtual environment

2001-09-28

2004-02-17

Zimmerman, Mark (Department: 2671)

Computer graphics processing and selective visual display system

Computer graphics processing

Three-dimension

C345S502000, C345S505000

Reexamination Certificate

active

06693632

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to a method of area partition in 3D virtual environment. In particular, it relates to a virtual environment partition method that can reduce the number of subareas adjacent to each subarea and the number of subareas an object crosses after the partition.
2. Related Art
In a virtual environment (e.g. virtual communities and multiple user online games), a larger environment is usually divided into several smaller groups for the convenience of assigning a server or a multicast group to each of the small groups. Therefore, one has to properly divide areas in order to obtain an optimal dividing scheme. Such a partition has to cover the whole space. The obtained subareas have to closely connect one another. The partition method has to have fixed logic rules for fast operations. In order to avoid delay when an object crosses different subareas, the information for adjacent subareas is often loaded in advance. Therefore, the number of adjacent subareas of each subarea after the partition should be as few as possible. Furthermore, when an object crosses certain subareas, the system has to compute all data in the subareas at the same time. Accordingly, the number of subareas an object can cross should also be as few as possible. This can facilitate computations and lower the burden of operations.
For example, conventional virtual environments are 2D (Two Dimensions). The most simplistic partition method is to divide the virtual environment into lattices. That is, a simple 2D coordinate system is used. The number of subareas for each subarea is 8 and the largest number of subareas an object can cross is 4. Therefore, in a virtual environment divided in this way, the data of the subareas adjacent to the subarea where the object is located have to be loaded in advance. This can facilitate processing when the object moves to one of the adjacent subareas. When an object crosses several subareas, the data of these subareas have to be processed at the same time. In this case, there are at most 4 subareas.
To reduce the load in operations, some designers have proposed using interposed lattices or hexagons. In these methods, the number of adjacent subareas of a subarea is 6 and the largest number of subareas an object can possibly cross is 3. Obviously, these methods can improve the problem of large loads in the aforementioned simplistic partition method.
Current virtual environments have been developed into 3D (Three Dimensions). The partition method uses the simplest lattice cubes, as shown in FIG.
1
. Each subarea is recorded using two 3D coordinates (the diagonal points
11
,
12
in the drawing). Whether an object falls in this subarea is determined by a logical condition (comparing the coordinates of the object with the two diagonal points). The number of subareas of each subarea is
26
and the largest number of subareas an object can possibly cross is 8 (such as the object
21
in the drawing). Processing in such an environment is indeed a large burden. However, no efficient solution to this problem is currently available.
SUMMARY OF THE INVENTION
In light of the foregoing problems, the invention provides a method of area partition in virtual environment. After the partition, the number of subareas adjacent to each subarea and the number of subareas an object can possibly cross are reduced, thus lowering the complexity and load in calculations.
According to the disclosed method, 3D virtual environment is first divided into a plurality of sheet-like areas along one of the dimensions. Then each sheet-like area is divided into a plurality of stripe-like areas along another dimension and the stripe-like areas of different sheet-like areas are interposed. Finally, each stripe-like area is divided into a plurality of subareas and the subareas of adjacent stripe-like areas (including the ones from the same and different sheet-like areas) are interposed. This method can reduce the number of adjacent subareas of each subarea and the number of subareas an object can possibly cross. Therefore, the invention can effectively lower the burden of operations performed by the system.


REFERENCES:
patent: 6304266 (2001-10-01), Li

Affiliated with

Also associated with

Rating

Method of area partition in virtual environment does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method of area partition in virtual environment, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of area partition in virtual environment will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3306348