RE: [Algorithms] Prism problems...

[Gino v. d. B. <gva...@pl...>]

When it comes to speed and robustness I would put my money on (1) =
construct separating-axes tests for all pairs of simple polytopes =
(prisms, OBBs, AABBs, triangles). The problem with this approach is that =
if the number of primitive types is large you will spend a lot of time =
coding, testing, and debugging. Furthermore, if you need contact =
information, then a SAT is not very helpful. (2) I know several Convex =
Hull approaches (Cameron's explicit Minkowski sum, Lin-Canny, =
Chung-Wang, V-Clip, SWIFT, to name a few). These approaches are usually =
far less robust than a SAT en slower for the object complexities that =
you are interested in. (3) If you need a single magic solution "that =
rules them all", try GJK. You can argue whether GJK is simple, but it =
surely is the most powerful approach to collision detection of convex =
shapes. So, my 2 cents worth would be: Try (1) if the number of =
primitive types is small (fewer than, say, 5), and have low-complexity =
(fewer than 5 edge directions and face orientations), otherwise, invest =
some time in discovering GJK.

Gino van den Bergen
www.dtecta.com
    =20


-----Original Message-----
From:	gda...@li... on behalf of Diogo =
de Andrade
Sent:	Tue 11/15/2005 8:55 PM
To:	gda...@li...
Cc:=09
Subject:	[Algorithms] Prism problems...
Hey all.
=20
Continuing my ongoing saga on creating a 3rd person action title in an
insanely short time, I have a piece of advice to ask you.
I'm still trying to automate the building a navigation mesh for the AI's
in my game (not using it for player anymore, though). I have limited
success with my raycasting approach, if I use lots of samples per
triangle (in the order of 500 per tri). Well, with 10000 tris up-facing
tris in the whole scene, and with subdivisioning of the "ground" mesh, I
have more than 25M rays being cast. Even using some optimizations, this
still takes about 10 mins to calculate, and it misses some stuff
sometime, which makes the enemies walk through walls and stuff like
that.
So, I wanted to make this better, and, following the suggestion of Jon
Watte, and use a triangular prism per tri, instead of 500 rays. Well, I
searched the net all over, my library, and still couldn't find an
explanation on the best way to do Prism/OBB, Prism/AABB and Prism/Tri
intersection test (I don't need intersection points, or any other of
that sort of thing, just an yes or no answer will do). So, I have to
roll my own, but before I leap into it (which already sounds like a
terrible ordeal), I understand there are several approaches to this
problem:
=20
1)       SAT test. While I understand it in concept, I still have some
problem understanding which are the candidate planes, how to extract
them and all that. So this one is very hard for me at the moment.
2)       Convex Hull approach: treat the prism as a convex hull.
Apparently I can find on the net more information on convex hull
construction and testing than SAT tests, so although this seems pretty
hard by itself, it's also better documented, I think.
3)       Some magic/simple solution that I can't think of and someone
did. This would be probably the best, but I guess that's just wishful
thinking.
=20
So, which of the solutions is faster/more robust/easier to implement?=20
Of course, if someone has a Prism/OBB and Prism/Triangle routine
somewhere on the hard drive, I would appreciate that even more (call me
lazy with a short development time), but considering the lack of info I
found on the net, I guess not many people need this kind of algorithm,
so it probably nobody has it/wants to give it away. :-)
=20
Well, thanks in advance for helping me with another simple problem.
=20
Diogo de Andrade
Spellcaster Studios
 <mailto:dio...@sp...>
dio...@sp...
 <http://www.spellcasterstudios.com> www.spellcasterstudios.com
=20
=20