From: broehl@sunee.waterloo.edu (Bernie Roehl) Subject: Re: TECH: My standard is better than your standard. Date: Fri, 10 Jul 1992 14:05:15 GMT Message-ID: Organization: University of Waterloo In article <1992Jul10.022124.27252@u.washington.edu> snowdond@cs.man.ac.uk (Dave Snowdon) writes: >Thats not exactly what I'm proposing :-) The EDB subdivides space hierarchical >ly (I'm thinking of a form of binary space subdivsion, only instead of >dividing so that volumes are equal, you divide space so that the number of >objects is approximately equal). Actually, Dave Stampe and I have been working on something similar to this; we're looking at putting binary space division into rend386. > This means that when I check an object for a collision I only > need check the objects that are in the same subdivision of space. > Also, it only performs collision checking when an object actually moves, > so there is little overhead for static objects. Right. >Now, as the number of objects in a world increases, the EDB may find that it >runs out of storage space or processor time. When this happens it subdivides > and passes some of the work onto another processor (here you have the > problem of finding a free processor etc How about solving this problem ahead of time, by allocating a process for each node of the binary-space-division tree? In effect, you have an EDB for each subtree (which spreads the load evenly). >I agree that the 'VR station' should cache the appearance of the objects in it >s immediate surroundings (I think this would be essential to keep >net traffic down). So in this case the approach you suggest would work well >for 'you' (the object representing the user) >However consider the other objects in the environment - these may be running >on remote machines. Now each object will have to store the locations and >(at least) a bounding volume for every object in its local area. Right, but if the bounding volumes are spheres you only need to store a location and a radius (four 32-bit values, or 16 bytes) per object in your local area. Stations would have to store a lot more, but ordinary objects just need bounding spheres (or possibly bounding boxes) to do quick tests for collisions. >It must now check against this when any of these objects moves ... One check -- between itself and the moving object. > ... when it moves ... N checks, where N is the number of objects in the environment > or when any other object moves to see if it has entered its local area. I'm not clear on this. When an object enters an area, the environment manager notices this and tells everyone else; same when an object leaves. I shouldn't have to keep track of interactions between other objects, just between me and them. In fact... if every object simply checks against itself whenever any object moves, and sends messages to that object if there's a collision, we solve two problems at once. In other words... whenever an object moves, it sends its new location and orientation to everyone else. Everyone then updates their local, cached copy of the moving object (which they would have to do anyway) and they also check if this moving object has collided with them. If so, they send that object a message. It's not necessary for both objects to "notice" the collision, so long as one of them does. If one object is stationary (relative to the fixed coordinate system) and one is moving, the one that gets bumped into sends a message to the moving one saying "hey, you just hit me at coordinates x,y,z,t". The hit object may also decide to move, or explode, or change shape, or whatever. If two objects are moving at the same time and they collide with one another, there's a two-way exchange of messages. (Same for three or more). >[... an increase in] >network traffic because when an object moves instead of informing a central >entity (which then decides whether to inform other objects) it must broadcast >a message which must be handled by every other object - whether this is >actually an overhead or not will depend on the network. It sort of does, and sort of doesn't. If they're all on an Ethernet, a broadcast is actually cheaper than going through a central host (since going to a central host means sending essentially the same information twice (object to host, host to everyone else). If the host is the hub of a point-to-point network (a "star" topology) then you have no alternative but to send to the host and have it relay the information (since there is no "broadcast" as such). Of course, sending to the hub and having it relay it to everyone else is essentially just a type of broadcasting, except that the host might do some intelligent filtering of the information so that nodes that don't need it don't get it. I would argue, though, that every object must at least keep track of the current location of other objects, so the star topology is just a host- intensive way of implementing broadcasts. Again, the overhead is quiet small; let's (for the moment ) assume that we're using a bounding sphere as desribed above. Assuming 1000 objects in the environment, you might have to use 16k bytes of storage to track them all. Even the smallest of machines can afford that. Now, assume 10 objects are moving at any given instant; that means 30 subtractions and 20 multiplies to do all the rough collision detection. Again, even a small machine can deal with that. The objects whose bounding sphere intersects yours are then subjected to more exacting collision tests, which will depend on the geometric representation for each. If an object passes that final test, you send it an appropriate message. If you receive such a message from another object, you respond to it accordingly. -- Bernie Roehl, University of Waterloo Electrical Engineering Dept Mail: broehl@sunee.waterloo.edu OR broehl@sunee.UWaterloo.ca BangPath: uunet!watmath!sunee!broehl Voice: (519) 885-1211 x 2607 [work]