I have a polygon (for simplicity let's say a square) and i have access to their vertex coordenates, i also have a point with a height value associented to it, and a radius from that point in all of it's height (in a few words =) a cylinder), what i want to do is, finding out if the polygon and the cilinder intercept. I tryed equaling the plane funtion to circle funtion of the cylinder but that sometimes will give another funtion and not a value i can compare with. What i want/need is an algorithm to find out if these two intercept! The faster(cpu) the better, but no quick hacks, not work arrounds, it must be above all precise! "Follow the white rabbit." [edited by - White Rabbit on May 18, 2002 6:40:43 PM]

After a quick Google for "intersection polygon cylinder", I found this paper:

http://citeseer.nj.nec.com/cache/papers/cs/851/http:zSzzSzwww.cosy.sbg.ac.atzSz~heldzSzpaperszSzjgt98.pdf/held98erit.pdf.

It''s a bit heavy on the math notation, but if you can read it it''s quite good. Perhaps a bit more searching would reveal a simpler description...

---

codeka.com - Just click it.

Dean Harding: I realise google is a very good tool, and that there are many doc''s online about this, but if this is true why do forums exist?
I''ll tell you why i think they exist, it''s above all to get a personalised answer.
Now like you said this doc you found was to mathy, and i read it and didn''t even answer my question because it only explained one case of polygon and cylinder interception (one that does not consider boundery interception).
What i''m looking for is for someone to explain to me how to do this, someone i can discuss ideas with, a doc doesn''t talk back =).
I''m trying to implement this "box" in a FPS engine i''m making and by what i saw on that document you found, cylinder-polygon interception seams rather (cpu)expensive, so i must discuss this with someone to see if they know a better/faster way of doing this.

There''s not really a lot to discuss though, this is a fairly standard algorithm and there''s not much which can be improved upon...

If you want a more personalized answer, then fine, just wait for one. In my experience, it''s far more rewarding (and usually a lot faster) looking through what others have done before you. In the time since you''ve posted this question, I could probably have found a better paper (like I said, I only spent 2 minutes on this search) and implemented a solution...

---

codeka.com - Just click it.

too mathy? heh, making a fps engine and thinking a doc with some math is bad, what till you start doing culling or any other complex stuff. stick to basics before attempting something beyond your level of programming/math/logic.

i for one would not want to follow a white rabbit that cant help itself. anyhoo, square vs cylinder collision detection:

is bounding box of cylinder intercepting the quad? if not, then nothing more needs to be done. if it is, then you do a more sophisticated check. see google for more info.

also forums are not for personalized answers to questions that can be easily researched. they are designed to help with specific questions and help with explainations on topics troubling you.

you ask for a quick method that does no speed hacks. thus something that is accurate above all else, which means it wont be the "best" method for a realtime game. the whole problem with things being done in realtime is making compromises of quality vs speed.

is this cylinder mathmatically perfect or just another set of polys? do you even need a cylinder or would a simple bound box due? if its a cylinder made up of polys, you could do basic quad to quad intersections.

you cant "equal" functions. learn some algebra before using equations.

some pseudo-code:

if(cylilinder-center-ray hits the quad)    collision = trueelse if(distance from closest point on quads        perimeter is less than cylinder radius)    collision = trueelse    collision = false 

[edited by - 123cs on May 19, 2002 4:42:29 AM]

You''ve probably done right (equaling the equations for the plane and the cylinder), the problem is that you''ll get to types of answers.

One is: they don''t intersect at all, also called no solution. The other is when they do intersect, the problem is that they won''t intersect in just one point, you''ll get an infinity of solutions.

The result will in the latter case be an equation of an ellipse or circle, that would be the other function you were talking about.

Just check if you get no solution otherwise you got one...

/P2

quote:

---

Original post by 123cs
some pseudo-code:

---

Your code only works for infinite-length cylinders, I don''t think that''s what he''s after...

---

codeka.com - Just click it.

quote:

---

Original post by White Rabbit
... a radius from that point in all of it's height (in a few words =) a cylinder),...

---

i think he means an infinite cylinder...



[edited by - 123cs on May 19, 2002 11:11:33 AM]

hmm, i''ve thought about it...you''re right (sorry im not a native english speaker)
but the solution could be extended by first clipping the quads to the upper and lower plane of the cylinder