# Traveling from BSP leaf to BSP leaf...

###
#1
Members - Reputation: **122**

Posted 18 July 2001 - 04:56 AM

###
#2
Members - Reputation: **122**

Posted 19 July 2001 - 07:18 AM

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?

###
#3
Members - Reputation: **1377**

Posted 19 July 2001 - 10:45 AM

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.

###
#4
Members - Reputation: **122**

Posted 20 July 2001 - 03:15 AM

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...

###
#5
Members - Reputation: **122**

Posted 20 July 2001 - 08:04 AM

###
#6
Members - Reputation: **122**

Posted 20 July 2001 - 11:53 AM

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...

###
#7
Members - Reputation: **122**

Posted 20 July 2001 - 11:58 AM

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

###
#8
Members - Reputation: **122**

Posted 20 July 2001 - 12:09 PM

----------------

-WarMage

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

###
#9
Members - Reputation: **122**

Posted 24 July 2001 - 03:53 AM

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

###
#10
Members - Reputation: **1377**

Posted 30 July 2001 - 05:32 AM

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.

###
#11
Members - Reputation: **122**

Posted 30 July 2001 - 02:58 PM