Howdy folks! Here's my problem... I've got a BSP tree defining a 3D space. Each node in the BSP is defined by a solid polygon which cannot be moved through. The leaf nodes also contain a list of "portals" which are the "non-solid" polygons that define the common borders between neighboring leaf nodes. Now, suppose I have a sphere that I want to move from one leaf through a portal to one of its neighboring leaves. I have broken this down into several steps, the first of which is determining at exactly which point in the portal the sphere's origin should pass through. I have 3 basic constraints in determining this location... 1) The point must be contained in the portal. 2) The point must be exactly the sphere's radius above a solid polygon (ie. I want the sphere to stay on the ground) 3) The point must be at least the sphere's radius away from all solid polygons (ie. I don't want the sphere to go through any solid areas of the world) So I'm trying to devise a function that takes as its input a sphere, a polygon (representing the portal), and a BSP tree, and as it's output generates a valid point of entry through the given polygon/portal. This is about the billionth problem I've come across, and my head hurts too much to jump this last hurtle Any hints/code/links would be much appreciated! PS: Maybe I'm taking the wrong approach to the overall problem? If there is an easier way to determine "travelability" through a 3D world, I'm open to suggestions... Edited by - novalis on July 18, 2001 11:57:18 AM

No ideas yet, huh? Well, I had a sort of "brute force" technique in mind which I figured would be relatively easy to implement and effective, but too slow for a finished product. This idea was to create a "bounding polyhedron" around the portal that encompassed the full area the sphere could take up from any point in the portal. That part''s easy, just push the portals edges out by a distance equal to the sphere''s radius, and then turn that 2D polygon into a 3D column whose length is equal to the sphere''s diameter. Next, clip that polyhedron to the BSP. Again, a pretty trivial operation. But even with this brute force technique, I am left with the question of how to determine if the sphere fits into whatever space is left over after the clipping.

So, I guess I''m still stuck... Now I *know* you all had this problem figured out back in kindergarden and are jsut laughing at me behind my back... So fess up... Who''s got the answer?

Long reply here, some random thoughts and some possibly useful information/ideas.

The problem of doing perfect traversal of geometries through arbitrary 3D worlds is obviously complex if you want to do it perfectly in the geometric sense. I suggest you approximate the portals as a rectangles, triangles, or circles, so that its easy to see if the sphere can pass through.

As for avoiding walls on either side of the portal, one approach to avoiding a problem is by forcing the sphere to traverse the portal along a line that is normal to the portal, and make sure there are no objects or walls that interfere with this path. The level designer and artist(s) would have to make sure they follow this interference rule.

I do have some thoughts on the more complex problem, where the portal geometry is arbitrary and you want to treat it as such.

I want to be sure I understand exactly which problem you''re trying to solve right now. I believe you are trying to solve only the first step right now, "determining at exactly which point in the portal the sphere''s origin should pass through." Am I correct?

If my understanding is correct, it sounds like your basic problem at this point isn''t traversing the BSP tree, but just finding out if a sphere can pass through a portal, given by an (arbitrary?) polygon. And if it can pass through, what''s the best point for the center of the sphere to pass through?

Lets just deal with a 2D problem for now. I mean, the sphere could bump into something solid on either side of the portal, but lets not worry about that for now. If that''s part of your step 1, then lets make step 1 two parts, part 1a and 1b. We''re talking about 1a now. The plane of the portal is the plane to work in. The sphere projected into that plane is a circle with the same radius as the sphere. So we''re trying to find out if a circle with a given radius can fit into a polygon on a plane.

Lets also require that the portal polygon be convex. Makes life easier, although it is not required. If the polygon happens to be a rectangle then life is *VERY* easy indeed. But for now lets talk about arbitrary shaped convex portals. This isn''t pretty, if you want to do it exactly right.

Now on to a solution. I would say that the *best* point for the center of the circle to pass through is the point within the convex portal polygon that allows the *largest* circle to pass through. Do you agree? Certainly, if our circle can pass through the portal at all then it can pass through at that point. Now, turns out you can use something called the "medial axis" transform to find this best point. When you generate the medial axis, you''ll end up with a series of vertices in the interior of the polygon. They are connected by lines that both connect to the polygon vertices and to the other interior vertices. For each interior vertex, select *one* medial axis line connecting to a portal vertex. For this interior vertex, the radius of largest circle it allows is equal to the length of the medial axis line times the sine of the angle between the line and either adjacent portal edge. (The angle is the same on both sides of the medial axis line so you only need to do one side.) Find the radius for *every* interior vertex and the when you''ve found them all the interior point representing the *largest* radius is the *best* point for your circle/sphere to go through! For a 4-sided portal you will have one or two interior vertices. For a triangle only one. For any unilateral polygon only one interior vertex. For an n-sided portal you will have n-2 interior vertices. You have to check them all to find the exact best point.

Here is a page with a neat Java applet demonstrating the medial axis transform for convex and concave simple polygons. Click on the Applet button. When you draw the polygon then press the Medial! button in the applet window you will see the series of medial axis lines I mentioned, and all of the interior vertices. You may be able to grab the Java code.

http://www.cim.mcgill.ca/~hlau/medial/

Now what about approximations, so that you don''t have to find the medial axis? Here''s an idea. Tesselate the portal into triangles. Each triangle will have one medial axis center point. Use *these* points instead of the full polygon medial axis points. The points might not be exactly the medial axis points but they might suffice.

There is a beauty to finding the best pass-through point. As long as your portal geometry is fixed, the point is fixed and the maximum radius it allows is fixed. So you can precompute this with the portal information and just store the pass through point along with the maximum allowed radius.

What about the extruded bounding polyhedron? Why not use the best point described above, then place a cube there with an edge length equal to the diameter of the sphere. Then clip the cube with the BSP tree.

I still say you''d only want to allow traversal normal to the portal and force your artists (is it you?) to make sure nothing is on either side right at the portal. To allow an arbitrary path through the portal will require some kind of real-time collision detection....

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

Thank you for that very clear and concise reply Graham! The MAT is completely new to me and will make a valuable addition to my toolbox I think you very accurately grasped the problem I''m facing except for one detail. The portals which I describe are not necessarily (and in fact are very rarely) bounded by solid material, but instead are much more commonly bounded by other portals.

quote:

---

Original post by grhodes_at_work
As for avoiding walls on either side of the portal, one approach to avoiding a problem is by forcing the sphere to traverse the portal along a line that is normal to the portal, and make sure there are no objects or walls that interfere with this path. The level designer and artist(s) would have to make sure they follow this interference rule.

---

The problem with this, is that the portals are generated by the level editor when it builds a BSP tree out of the map. Bear in mind that portals are *not* bounded by solid material... They are merely shared faces between BSP leaves and bear no direct connection to the physical geometry of the map.

quote:

---

I want to be sure I understand exactly which problem you''re trying to solve right now. I believe you are trying to solve only the first step right now, "determining at exactly which point in the portal the sphere''s origin should pass through." Am I correct?

---

Almost correct... That''s my end goal, but many other factors affect the *exact* placement (Does the sphere need to stay on the ground? Is it flying? Is it climbing a wall?) so my ideal algorithm would simply return the set of all *possible* points of passage.

I guess the real crux of my problem is in fact, step 1b as you labeled it. In theory I want to take all the solid geometry in my BSP that is within my sphere''s radius of the portal, and project it onto the portal, then subtract that projected polygon from the portal. What is left is the portion of the portal that my sphere *could* pass through. Then I apply the MAT to what''s left and see if any of the gaps are big enough for the sphere to fit through. Or, more idealy, I could scale the projected polygons before subtracting them from the portal to take the sphere''s radius into account.

Does that make any sense? If not, perhaps I could draw up some diagrams to illustrate the kind of situations I''m talking about...

Ok, I have purchased a paper from the IEEE website which describes an algorithm for determining the MAT of a 3D polyhedral solid. In theory, this sounds like the perfect solution to my problem. If I can precalculate the MAT of the entire map, then I can use the MAT junctions as my A* nodes instead of the BSP leaves. This should provide lightning fast path computations! The only problem is that I am having a little bit of difficulty understanding some of the terminology used in the paper. I''ll have to take some time to sit down and really work through it.

So let me see if I understand thie correctly. The plan is to basically do a BSP for the render engine, and then a negative-space-tree based on Medial Axis Tranform junctions to use in place of the "not-this-node" method used when handing BSP nodes to A*? I have not written a BSP nor used A*, so this question is probably ignominy.

If I am understanding it correctly, then this WOULD be superfast, because you''re handing ONLY the traversable space to the pather, not the non-traversable?

Cool.

-------------------
-WarMage
...the head with two things...

I didn''t quite follow all the terminology you used WarMage, but I think you''ve hit the nail on the head. You''d still have to check each seam from junction of the MAT to the next to see if your bounding sphere could fit along it, but the maximum radius for any given seam is inherently precalculated in the MAT, so that is a simple comparison of two doubles.

Now this solution by itself does not guarantee you''ll get the *shortest* path between two points, but it will come very close.

Oh, well I have that problem solved for you already. Build a struct in your C_MAT_Leaf that is the triangle-list (or vertex list, if deformable) of the seam face, and a bool set by the map tool to tell if this MAT Leaf is abutted to a BSP leaf (IE, non-exitable)

----------------
-WarMage
...de doo doo doo, de da da da. I remember when Sting was God.

Well, I''m pretty much convinced now that a polyhedral MAT is the *only* way to do pathing in 3D, but I''m a bit overwhelmed by some of the math involved in calculating the MAT. Can anybody point me towards a good "I took differential equations 5 years ago" resource online? In particular, I have a system of 3 equations and 4 unknowns I''m trying to solve (the intersection of 3 governors which can be planes, cylinders, or spheres, all with variable radii).

In the immortal words of Mr. Brown... "Good grief!" Please help, I''m being swallowed by math!

I can''t recommend any good online resources off the top of my head as a refresher for math learned long ago. And I haven''t actually written any code to find the MAT (I only know what it is and what it can be used for). But I can offer a clue that may be beneficial. This came up in another thread and it occured to me that it might help here as well.

Consider this. *Vector* equations actually translate into more than one *scalar* equation. A single vector equation in 3-space turns into 3 scalar equations, etc. I haven''t seen the actual set of equations you''re trying to solve, but I think perhaps you may have vector equations there... That may give you enough equations to solve for your 4 unknowns.

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.