Sign in to follow this  
Magnusart

How can I project an outline of an object onto the ground

Recommended Posts

Magnusart    122
Ok, long post. Please bear with me. Skip the background if you're not interested. Hi, I would like suggestions on how to go about projecting an outline of an object onto the ground. The projection should start from a certain height. I have made an illustration that I hope explains a little: So in this case I get the outline on the ground that describes the object up to the specified height. The example is a simple object but my hope is that this would work for more complex objects as well. =========You can skip this, it's only background============ The reason I need this is for my A* implementation. Right now I have a prototype that works with predefined paths around obstacles (attached to the objects node in a scene graph). Each obstacle have their own path describing how you go around it. What I do is the following: given a start location and an end location, a ray is projected to see if any obstacles are blocking the direct path. If not, no problem, just walk over there. If there is an obstacle blocking, I extract the path that describes how to get around this object. I connect this path with my start position and then do the same for any other obstacles that are blocking my direct path to the end location. After than I connect the goal location to the path of the last obstacle. I now have constructed a graph that I search with A*. This way I can have a lot of obstacles but only need to calculate the path for those obstacles that are actually blocking my way. No grids, just the paths that are needed. If an object is moved, no biggie. The path moves with it. So what I want to do with this is to generate these paths around the obstacles. The height is there because the character is supposed to go underneath obstacles as long as he doesn't hit his head. ;) ============================================================= I envisioned doing it something like this: 1. Given the mesh, collect all vertices from the floor up to this height. 2. Set their y positions to 0. That is flatten them. 3. Collect the vertices that have the farthest distance from the center point. Add these to the path. 4. ??? 5. Profit. Is there any better/standard way to do this? How do I know what vertex should be connected to what neighbor?

Share this post


Link to post
Share on other sites
AnthonyS    132
I'm not sure exactly what you are after, but maybe I can give you some ideas. Have you thought about rendering the scene on the gpu using orthographic projection from above your avatar? You could set the projection plane right above your head and clip at the height of your avatar. Every object could be assigned a unique hue which would make finding the object intersecting your path a matter of a hash table lookup. At the end you'll have a nice little bitmap to work on, which will be much easier computationally.

Share this post


Link to post
Share on other sites
FluxCapacitor    200
AnthonyS's suggestion is probably the easiest: just render a grid at whatever resolution you need. If you really need a polygon, though, you could probably do something like manually clip at the height you need, then project onto your plane and find the (2D) convex hull of the projected vertices.

Share this post


Link to post
Share on other sites
Magnusart    122
Thank you for your swift answers!

I think your suggestions would work. But I can't help but hope there is some simpler way of doing it. Speed is not of the outermost importance, I only need to do it once per loaded obstacle, unless it's morphed in some significant way. So I'd rather go for simplicity.

I just came up with an alternative. I think this would be a fairly quick algorithm as well(?). Tell me what you think of it. Can you see any problems? Remember that I'm using this do build a path that navigates around the object (I expect that I will have to scale it as well). I do not need a perfect outline.



1. In the first step I made a arbitrary flattened topology. Note that there is no actual triangles, just vertices in a list at this point. I just added the lines for clarity.

2. Imagine we draw a circle around our topology.

3. Sort all the vertices in a sorted collection with the angle as our key/index.

4.a Pick a resolution, say 30 degrees. That would mean that we would start out at 0-30 degreed move on to 30-60 degrees and so on.

4.b Find all vertices that are between 0-30. Pick the one that is farthest away from center (largest radius). Add this to a separate collection / make a node of it in our graph. If there is none, skip this interval.

5. Connect the nodes and we have our final path/outline! Profit!

I think I'm going to give this one a go. It makes sense for me. If you wonder why I make all these pictures, it's because it helps me thinking by visualizing it.

/Mangus

Share this post


Link to post
Share on other sites
daftasbrush    252
The "alternative" method you describe is actually determining the "convex hull" mentioned by Flux Capacitor.

There's a load of different methods for doing it, but a quick google should turn up free-to-use downloadable source for several and save you some time.

I'm with "FC"... if you want a polygon...
"Manually" Clip the object data (mesh?) at the required height.

If you're only ever going to be using a horizontal plane, it gets a little easier.
For each vertex in your mesh, determine whether it's above or below the plane.
Add the projected (2d) coords for each "below" to a list.

Then for a "perfect" system run through all the triangles.
For any pair of vertexes on different sides of the plane...
calculate the point of intersection of the line with the plane, and add that to the list.
Then find the convex hull of the whole list.

Share this post


Link to post
Share on other sites
Magnusart    122
daftasabrush: It was late last night so I didn't look up what determining the convex hull actually meant. I mainly thought that rendering a 2D bitmap sounded a bit cumbersome. So you caught me there ;). I'm fairly new at this so I don't know a lot of the terminology for different standard solutions yet.

I could probably have saved myself some thinking by looking it up, but in the end it was satisfying to figure it out myself. At least for a couple of hours ;)

Well, I only need a 2D convex hull/projection, so I'm happy that my "alternative method" and the standard way to go about it is more or less the same. I had thought to go about it much in the same way you describe. I had hoped to be able to skip triangles, but I see now that I need to do that as well to get a good clipping.

I'll do a quick google for some source and see if I can find some code to adapt to my purposes.

Thank you guys for your help.

Share this post


Link to post
Share on other sites
Magnusart    122
Emergent: I use Inkscape. It's an open source vector graphics editor. Works both on Linux (that I'm using) and Windows. It's similar to Adobe Illustrator. I really like this program, whenever I use it I'm amazed at how intuitive it is. Whenever I discover something new I get that "this is how I would have implemented the same tool"-feeling.

It saves natively to svg-file format and you can export to png-file format.

On topic: I discovered that the convex hull problem indeed have a lot of different solutions. I'm going to make a compromise and first use Akl-Toussaint heuristics to eliminate most of the unimportant vertices, then I'm going to use Graham scan to connect the remaining vertices into a convex hull. The fist is that you take four points at the extreme x and y coordinates and eliminate anything inside them. Graham scan is basically the cross product of two vectors. If it's positive it's convex otherwise it concave.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this