A question about V-Clip algorithm

[aokman]

Hi, everyone.
While I was reading the paper 'V-Clip Fast and robust polyhedral collision detection', I was confused by 'clipping edge' operation.

According to the paper, after clipping an edge with one Voronoi region of another polyhedra's features, if a line segment from the edge is found lying inside the Voronoi region, it also needs to check whether minimal distance between the edge and the feature is lying in the segment or lying outside the segment and inside the edge.

But, I think the latter check is unnecessary. Because, according to the definition of Voronoi region, one feature's Voronoi region is a set in which all points are closer to that feature than any other features. So, if there is a segment from the edge is contained within the Voronoi region of the feature, the minimal distance between them must lie on the segment.

Could anybody show me a counter example and explain why the check is necessary, please?

[FD]

Hi!

I think you misunderstand the algorithm. It doesn't do what you describe. clipEdge subalgorithm actually finds the segment of the edge that is inside the Voronoi Region of the other feature. Nothing else is done in this subalgorithm. To be more precise, it intersects the edge with each border plane of the VR of the other feature and adjusts parametric coordinates of the tail and the head of the _segment_. After all border planes of the VR are processed, we actually know the segment of the edge that is located entirely within the VR, or if the segment turns out to have a negtove length we understand that the edge is entirely outside of the VR.

[aokman]

Hi!

I think you misunderstand the algorithm. It doesn't do what you describe. clipEdge subalgorithm actually finds the segment of the edge that is inside the Voronoi Region of the other feature. Nothing else is done in this subalgorithm. To be more precise, it intersects the edge with each border plane of the VR of the other feature and adjusts parametric coordinates of the tail and the head of the _segment_. After all border planes of the VR are processed, we actually know the segment of the edge that is located entirely within the VR, or if the segment turns out to have a negtove length we understand that the edge is entirely outside of the VR.

Ummm... Maybe I didn't describe my question clearly. I know what 'clipEdge' exactly does. What I can't understand is that 'clipEdge' may result in two cases, intersection case and non-intersection case, when it is intersection case, why I still need to check whether the minimal distance between the edge and the feature is within the segment(This is called 'Post-clipping derivates checks' in the paper).

[aokman]

I think I just misunderstand the definition of Voronoi region...
In the following figure is my current understanding.

.GIF

As shown in the figure, the post-clipping check is necessary.
I'm right this time, yeah?