| Computers Forum Index » Computer - Graphics (Algorithms) » The intersection of a plane and a polyhedron |
|
Page 1 of 1 |
|
| Author |
Message |
| Christer Ericson |
 Posted: Sun Jun 05, 2005 9:03 pm |
|
|
|
Guest
|
In article <1117998255.159809.58190@g14g2000cwa.googlegroups.com>,
bilal.sal@gmail.com says...
Quote: [...]
For convace polyhedra this doesn't work (since there may be local
minima for the distance).
For concave polyhedra the algorithm you outlined doesn't
work, period. The reason for that it that the intersection
of a concave polyhedron and a plane can result in multiple
disjoint outlines (polygons).
--
Christer Ericson
http://realtimecollisiondetection.net/ |
|
|
| Back to top |
|
|
|
| Guest |
| Posted: Mon Jun 06, 2005 1:03 am |
|
|
|
|
Yes Christer, you are right. Thanks.
If the polyhedron is convex the algorithm finds only one outline
(polygon) while there maybe others.
Anyway, is there a way to find an intersecting face when the polyhedron
is convex other than testing over all faces? |
|
|
| Back to top |
|
|
|
| John Nagle |
| Posted: Mon Jun 06, 2005 5:05 am |
|
|
|
Guest
|
bilal.sal@gmail.com wrote:
Quote: Yes Christer, you are right. Thanks.
If the polyhedron is convex the algorithm finds only one outline
(polygon) while there maybe others.
Anyway, is there a way to find an intersecting face when the polyhedron
is convex other than testing over all faces?
Yes. And if you do it incrementally from frame to frame,
it's almost constant time. Look into how SOLID does
polyhedron to polyhedron collisions, or read the Lin/Canny papers.
John Nagle
Animats |
|
|
| Back to top |
|
|
|
| John Nagle |
| Posted: Mon Jun 06, 2005 5:06 pm |
|
|
|
Guest
|
bilal.sal@gmail.com wrote:
Quote: Thanks John,
But I'm seeking a sublinear algorithm for my special case, that detects
collisions (and returns an intersecting face), and doesn't test all the
edges/faces and is guaranteed not to be stuck in local minima.
GJK is sublinear. It's roughly O(log N).
Convex polyhedron vs. plane is easy.
1. Pick a vertex on the
polyhedron. Compute which side of the plane it is on and
how far it is from the plane.
2. For its neighboring vertices, do the same.
Move to the vertex which
brings you closer to the plane or is on the other side.
If you find a vertex on the other side, or in the plane,
you're found an intersecting edge, and you're done.
Otherwise, pick the vertex closest to the plane and
repeat step 2.
John Nagle |
|
|
| Back to top |
|
|
|
| Guest |
| Posted: Mon Jun 06, 2005 11:06 pm |
|
|
|
|
John Nagle wrote:
Quote: GJK is sublinear. It's roughly O(log N).
I think GJK algorithm is linear. It's O(n*n) in the first call and then
O(n) in the subsequent calls assuming a phyisically coherent motion.
GJK works on a set of point, but when the topology is avaiable (the
points represent a simple polyhedron) and the polyhedron they represent
is convex, and the motion is coherent, an O(1) average complexity is
achived in Cameron's imporvents over the GJK (yet, the worst case is
O(n) if not O(n*n))... |
|
|
| Back to top |
|
|
|
| Guest |
| Posted: Mon Jun 06, 2005 11:06 pm |
|
|
|
|
Quote: Wouldn't it be helpful to sort all vertices in advance with respect
to signed distances from the plane ?
Then use only those which have neighbours with changing sign for
finding the intersections?
Best regards --Gernot Hoffmann
Thank you very much Gernot,
You have right: this requires V (always), while I did it in E (worst
case), and since E = V + F - 2 Euler formula, your algorithm performs
better in worst case. |
|
|
| Back to top |
|
|
|
| Gino van den Bergen |
| Posted: Tue Jun 07, 2005 9:29 am |
|
|
|
Guest
|
bilal.sal@gmail.com wrote:
Quote: John Nagle wrote:
GJK is sublinear. It's roughly O(log N).
I think GJK algorithm is linear. It's O(n*n) in the first call and then
O(n) in the subsequent calls assuming a phyisically coherent motion.
GJK works on a set of point, but when the topology is avaiable (the
points represent a simple polyhedron) and the polyhedron they represent
is convex, and the motion is coherent, an O(1) average complexity is
achived in Cameron's imporvents over the GJK (yet, the worst case is
O(n) if not O(n*n))...
Without preprocessing, GJK indeed runs in linear time, due to the
linear-time support-point computation. The number of iterations is
insensitive to N for larger N, so stating that a single-shot GJK would
take O(N^2) is rather pessimistic. GJK can be made O(log N) by applying
a Dobkin-Kirkpatrick hierarchy in the support point computation. Since
the mentioned paper by Joukhadar et al. describes a technique for
deformable polyhedra, preprocessing of the convex hull, either for
hill-climbing a la Cameron or for constructing a DK hierarchy, is not
possible. Coherence only affects the number of iterations, so although
you would be able to considerably reduce the number of iterations per
frame in the incremental version, it would still take linear time to
perform a single iteration.
Gino van den Bergen
http://www.dtecta.com |
|
|
| Back to top |
|
|
|
|
