View Full Version : Vector and polygon intersection

enunes

02-28-2009, 08:44 PM

Hi,

given a point and a vector (a line), can you give me possible solutions on checking what polygons intersect that line?

Could you point me to an easy solution (if any) and a "proper" way to do that?

I suppose this has something to do with ray casting or whatever?

thanks in advance! :)

scratt

02-28-2009, 09:01 PM

If you whack "Ray Polygon Intersection" into Google you will get a lot of information..

Typically the best way to get your viewing ray is to use gluUnProject twice. Once set at your farz, and then again at your nearz. The resulting delta (obtained from farz - nearz) is your viewing ray. Otherwise you can just use any arbitrary ray if you are doing something other than 'picking', like say collision detection or ray tracing.

Here is what I think is quite a nice explanation of the maths..

http://www.lighthouse3d.com/opengl/maths/index.php?raytriint

There are two or three simple, but good, libraries out there on Sourceforge which wrap all this maths in quite neat libraries if you are looking for full blown collision detection or ray tracing solutions.

Or you could roll your own...

enunes

03-01-2009, 01:20 AM

Hi,

thanks for the quick input!

I had tried a few searches but had not found anything that would clearly talk about a solution. Maybe i tried bad searches then.

At a first glance at that link, it seems to be exactly what i was looking for, thanks for it! I will probably write my own one to learn a bit more on that subject.

I just don't get what you mean by using gluUnProject twice. I am currently using it, but i am using it only once, isn't it enough to get a vector (ray)? Would there be a difference as i know the starting point and just need the ending point? I haven't got who are nearZ and farZ.

:)

scratt

03-01-2009, 02:18 AM

No worries..

Normally if you are picking then you unproject the mouse x, y coordinate on the screen close to you, and also far away from you..

This gives you a direction vector.

WIthout giving the ray dimensions in length the maths won't work for creating it..

If you have one end of the ray already, then I guess you don't need to do both...

Brolingstanz

03-01-2009, 03:08 AM

... And in the context of selection, clipping the ray to the frustum will ensure that only those objects visible in the current view will be considered. This generalizes nicely for both perspective and ortho views too ;)

enunes

03-02-2009, 12:08 AM

Hi again,

Reading that and other materials over the net, i have faced the solution by approximating every object with a bounding sphere and, if the ray hits the sphere, then check if any part of the enclosed object was hit. I suppose this is a reasonable solution, would it be?

Even though i'm pretty sure that would work, i'm still not sure about it:

1) My models are drawn via vertex arrays. I load them from a custom file and reprocess them somewhat like the TriangleMesh example on Superbible 4th. Sorry if it's a dumb question but, am i supposed to read the vertex array itself and rebuild each triangle to intersection test against the ray?

2) My models can have lots of triangles. Depending on the object, for a bounding sphere to bound it all, it would have lots of "empty" space, and then it would more likely not to hit the object even hitting the sphere (I would be setting the radius of the bouding sphere by the most far vertice from the center of the object). That sounds like big overhead to me, is it really how it's supposed to work?

3) modus, I dont get much what you mean by clipping the ray to the frustum. I mean, when i click 'the nothing', the output z value from unproject is the farZ on the frustum. Isnt that an already "clipped ray"? Could you elaborate that a little more?

Thanks again for both answers, I guess I'm starting to get it better now! :)

satan

03-02-2009, 06:10 AM

1) Yes.

2) Yes, but the center of the bounding sphere is not necessarily the same as the center of your object. You can also use multiple spheres to get a better fit or use bounding boxes. Bounding geometry testing is just a way to find possible intersections. After finding a bounding geometry intersection you have to do triangle intersection tests to test if your object is really hit.

3) Your camera position is outside the frustum. So it is not a good starting point for your pick ray as there may be objects between your camera position and the near plane. By creating the ray like scratt described in his first post you are actually clipping your ray to your frustum. But you can use your camera position as your starting point as long as you only test it against objects inside your frustum.

enunes

03-02-2009, 04:23 PM

Hi,

thanks for the answers, satan.

I will do the bounding spheres trick and possibly use the idea of multiple bounding spheres. I will take spheres over boxes because they seem to be easier to work with and will just do for my needs.

Now for last: For testing intersection, i have come across the suggestion on partitioning the model with BSP trees. Following that, i could easily discard several objects that would definately not be being hit by the ray. That would be used on looking for whole models (bounding spheres) hits, aswell as, after hitting a sphere, looking for which triangle was (if any) hit.

I have implemented binary trees before but no BSP trees. I suppose it should be like implementing a standard binary tree and a buildBSP() method or something like that.

So, finally:

1) Is this solution really worth it or not? If so, is it worth implementing BSP tree for searching BOTH model hits and then specific triangle hits (as described in paragraph 4)?

2) It seems to me that i would have to rebuild the BSP tree at each frame depending on objects and "camera" position: again sounds like big overhead! Reading the arrays, building the triangles and sorting them to the tree? Is that how it's supposed to work?

3) It just came to my mind a possible solution as sorting the vertex arrays as a Heap structure, would this be an employed solution by any chance?

Thanks in advance! Sorry if it's somewhat confuse, i tend to have a brainstorm while writing.

ZbuffeR

03-03-2009, 02:21 AM

1) For me it is easier to work with axis-aligned octree partitioning instead of BSP.

This page discuss BSP collision : http://www.devmaster.net/articles/quake3collision/

But is is "paragraph 4" ?

2) bsptree/octree only works well for static geometry. But if you only do scale/rotate/translate on your model, it counts as static geometry. Just apply reversed transformations on the ray to test against it.

3) What ? You just confused me :)

PS: octree scales better than BSP when the triangle count increases.

Powered by vBulletin® Version 4.2.3 Copyright © 2017 vBulletin Solutions, Inc. All rights reserved.