View Full Version : Polygon Intersection Detection

02 February 2004, 07:05 PM

I have coded up a routine to check how many polygons will intersect a ray shot from the mouse cursor (so I can make polygon selection code)

The result from the routine produces the correct answers most of the time, so if the ray intercepts 2 polygons, then 2 is returned.

The problem is that my code has been made to work with triangles and not quads, because I didn't think about quads until after I started to test it.

I only have to work with tri's and quads so ngons is not a problem.

The quads that cause problems are invalid quads that lie on 2 planes
Polygon = Vector(-1,0,-1), Vector(-1,0,1), Vector(1,0,1), Vector(1,50,-1)

The last vertice is too high and no longer lies on the same plane as the first 3.

Casting a ray onto this polygon, will only intercept the first half of the polygon, because im checking only the first 3 points for the intercepting.

The way im doing this is, checking if the ray intercepts the polygons plane. The polygon only has one plane when all 4 vertices are lined up correctly, so I don't have a problem there.

What im asking is, what shall I do to overcome this.

Ive thought about casting two rays, if it dont find the polygon first time, try again on the second plane of the polygon.
The problem is, that essentially the polygon has 4 planes, and i dont know how to figure out the correct 2 planes.

Maybe I havn't thought this through enough yet, but I thought I'll just ask see if anyone has an idea

02 February 2004, 08:23 PM
i'm presuming this is for selections within cinema, the cinema sdk there are routines already there that are pretty fast and utilise ogl, they're in fact the same routines that cinema uses itself to make selections. you have to make a selectionslist first which you do with the SelectionListCreate routine you should check out lib_editortools in the sdk then you should look at the C4DObjectList that's created, and the GetPolyID.

For other stuff the inbuilt raycollider engine is fast enough provided you're not making modifications to the mesh as it will have to rebuild the cache, it actually returns a list of polys in the GeRayColResult pointer that are in the colision nearest to furthest, though normally you use the GetNearestIntersection which only returns the nearest value.

02 February 2004, 09:23 AM
You've already got the triangle code, so jut turn the quad into triangles. You can handle any polygon in a similar way too.

02 February 2004, 11:17 AM
I managed to do it

I simply cast a ray onto the first plane of the quad, if it fails I attempt to cast another ray onto the second half of the quad. If that fails im assuming the ray didn't meet at all. Seems to work fine.

Yea this is for c4d. And currently I do use the GeRayCollider library to do my work, but I also modify the mesh so re-initializing the mesh all the time is taking along time.

So I decided to make my own RayCollider class, and as 3D math isn't my strong point, its been quite a challenge :)
So far the results of my class are faster than GeRayCollider, and even has a few sqrt in there!

The problem im having now is that sometimes the ray don't pick up a polygon, or it picks up the wrong polygon (the polygons at the back)
And it only seems to happen on complicated models like Meg, standard primitives works fine which has confused me some more.
And after many hours experimenting I have come to the conclusion I have problems when the ray is over the edges of the polygons.
Im guessing this is to do with inaccuracies in float datatypes

02 February 2004, 11:46 AM
And after more testing, turns out its to do with the scale of the model.

If I scale the Meg model up, then I don't have any problems (for non c4ders, meg model is a female preset model that comes with c4d)

CGTalk Moderation
01 January 2006, 10:00 AM
This thread has been automatically closed as it remained inactive for 12 months. If you wish to continue the discussion, please create a new thread in the appropriate forum.