Menu
▾
▴
[Worldforge-all-lists] Re: [WF-Server] Re: Collision detection - Cannon battle at sea. (fwd)
|
From: Rakshasa <rak...@st...> - 2001-01-06 08:11:38
|
Bryce Harrington wrote:
> Arnan's reply...
>
> ---------- Forwarded message ----------
> Date: Thu, 21 Oct 1999 09:07:55 +1000 (EST)
> From: Arnan Mitchell <ar...@bi...>
> Reply-To: Se...@wo...
> To: Se...@wo...
> Subject: [WF-Server] Re: Collision detection - Cannon battle at sea.
>
>
>
>
>> Hmm I`ve been giving this some thought, and must admit I`m coming
round..
>> I`ve got two remaining doubts I think :-
>>
>> 1) You mentioned altering the region bounding box, this could lead
to some
>> very awkward shapes to collide with and is time intensive in itself,
I think
>> we would be better deciding all regions are cubic, or at least have
6 sides
>> whose size does not change. Collision between an entity and a region
is then
>> pretty simple.
>
>
> When I said the 'bounding box changed' I meant just that - the six sided
> box that conatins everything ( container and contents ) changes to
> represent the max and min coordinates of every entity within. This could
> easily change without complicating things. And colliusion between such
> axuially aligner boxes will be triviality itself. Further, many of the
> entities bounding box will actually be thire boundary ( also many not ).
He seems to be talking about axis aligned bounding boxes, who are not
very effective when dealing with objects that often rotate. And mixing
oriented and axis aligned boxes isn't good. The container's bounding box
could be axis aligned to it's inner self, but using oriented bounding
box. It would speed up the container resizing without the need of
rebuilding the bounding box every time the container rotates.
>
>
>> 2) Using regions for everything from walking over a plank to spearing
>> something on your sword is unfeasible. Not only don`t we need to even
>> consider that kind of detail level right now, but regions will be
processing
>> intensive, so we should require them to be as large as possible.. The
>> tradeoff between the extra processing to implement partitioning and
the size
>> of partitions has to be balanced, but imo the above cases result in
far too
>> many partitions, as would using partitions for each table in a room.. A
>> region for each large ship, building etc I`d say was more suitable.
>
>
> Hmm, I suspect that the regions that I am describing will have minimal
> computational requirements. You could always limit the depth of these
> regions ( ie if you have mless than 100 entities within a region, dont
> bother subdividing ) - but only benchmarking will tell.
100 objects being checked against each other is way to many. (n^2-n)/2,
where n is 100 equals to 4950. With 100 objects standing still (+100
moving) we got 14950 checks. That's to many by far. For n=10 it becomes
45. If we got 10 moving objects in a region and 10 standing still, we
have 145 checks. That's 1/10 of the 100 case. But we can live with
that. (Can't we?)
>
> The important point is that these regions should be dynamic ( the change
> size and location according to adapt to the changing environment ) and
> that they remain conceptually relevant - the foundations of a house is
> automatically a region containing everything built on it, selecting and
> moving the foundations would result in the movement of everything within
> that region. ( Note here that the canonball flying through the window is
> not part of this region, but rather the air region around the house -
thus
> it stays still if the house is moved - and these regions intersect ).
Changeing size and location of the region seems too expensive and
complex IMHO. A faster way could be to divide a container into a octree,
dividing and merging a region as needed. (before it reaches 10 objects
if possible)
>
> I think a crude implementation may be in order.
>
>
>> I also think you have said in the past that we would not be using
portals,
>> in fact the sides of the regions in a partitioning scheme are
exactly that.
>
>
> Hmm, not quite - Im asuming that regions can overlap without complication
> .... which seems to me to be very unportal like.
>
> Arnan
>
> PS: Saw code fragment below, but will have to think some more to
rework it
> into my model. [ I'll get back to you ]
>
>
>>
>> Something like this? :-
>>
>> inside region
>>
>> collisionLoop() {
>> for each entity
>> generate movement
>> if collide(entity)
>> resolve collison (for example don`t update location)
If we got the collisions timed (we'll have them if we want accurate
collisions in high speed with small objects) we must/should sort the
collisions according to the time. Resolve the first collision first and
see what impact it makes on the world. (check for new collisions perhaps)
>> }
>>
>> collide(entity) {
>> for each entity
>> collide test with all other entities in region (would be
layered, quick
>> distance test then coarse -> fine collision detection)
This is what bounding box tree's do. Or was this meant as some other way
of culling the number of tests?
>> if no collision continue till done
>>
>> if collision with
>> normal entity
>> return collision
>> region within current
>> return hitRegion.collide(entity)
>> edge of region
>> return myContainerRegion.collide(entity)
>>
>> after collision detection
>> move all entities *wholly* within another region, into that
region (can
>> set flags above if these calcs coincide)
>> }
>
>
> In my model, every entity would have a region and so
>
>
>> I think the above works for most cases I can think of, but is not
intended
>> for sticks, planks on balconies etc etc.. works for cannonball
between ships
>> tho I believe. As I said, the two up/down tree traversal functions are
>> problem 2) above..neither should be allowed to get ridiculously
recursive
>> and using fewer larger regions should do it.
>>
>> fex
>>
>> ====================================================================
>> To unsubscribe from this list, email to
Ser...@wo... from
>> the subscribed address. See http://www.worldforge.org for more details.
>> All work submitted to the Worldforge mailing lists and newsgroups is
covered by
>> the OpenContent (www.opencontent.org) license unless explicitly stated
>> otherwise by the author.
>> ====================================================================
>>
>
>
> ====================================================================
> To unsubscribe from this list, email to
Ser...@wo... from
> the subscribed address. See http://www.worldforge.org for more details.
> All work submitted to the Worldforge mailing lists and newsgroups is
covered by
> the OpenContent (www.opencontent.org) license unless explicitly stated
> otherwise by the author.
> ====================================================================
>
>
> _______________________________________________
> Server mailing list
> Se...@ma...
> http://mail.worldforge.org/lists/listinfo/server
--
Rakshasa (rak...@st...)
Famous last words:
"They couldn't hit an elephant at this ..."
_______________________________________________
Server mailing list
Se...@ma...
http://mail.worldforge.org/lists/listinfo/server
|