🔒 Locked

Distance and Ray queries vs an Implicit Convex Shape

Started by raigan Apr 17, 2012 at 1:47 PM 6 replies 1.9k views

Original Post

146

Apr 17, 2012 at 1:47 PM

I have a convex volume which is defined as the intersection of a set of halfspaces; this representation is new to me (I'm used to having explicit geometry, e.g a boundary representation, to query against) and I'm a bit confused about how I would go about calculating ray intersection and distance-to-point queries for a convex volume formed by halfspaces.

For ray intersection, something that *sort of* works is to calculate the intersection of the ray vs each plane, and then at each intersection check if the intersection point is inside/behind all the other planes. This gives correct results, but seems pretty wasteful/slow; I'm hoping there's a better method someone could suggest.

For distance queries, I'm at even more of a loss: AFAICT all I can calculate from the halfspaces is a bunch of point-to-plane signed distances. For points inside of the convex volume, this works -- the closest point on the surface of the volume is just the point on one of the planes closest to the query point -- but for points outside of the volume this fails.

Specifically, when the query point is in an external voronoi region corresponding to an edge or a vertex of the convex volume, I would like to be able to determine this (so that I can return the edge/vertex as the closest point, rather than the supporting planes)... however I can't see any easy/direct solution for this, without converting to a b-rep.

If anyone has any suggestions, useful links, or even could point out what the correct search terms for this sort of thing are (i.e "implicit convex shape" is probably not the correct jargon for describing a volume formed as the intersection of halfspaces), I would really appreciate it!

thanks,
Raigan

clb

139

clb

Apr 17, 2012 at 2:30 PM

I'm hoping there's a better method someone could suggest.

There is! realtimerendering.com/intersections is a treasure trove. Particularly this code by Eric Haines. The idea is to track the distances the ray intersects the various planes at, and see if the intersection interval turns out to be degenerate or not. As for the closest point to convex polyhedron and detecting the voronoi region, I think either Real-Time Collision Detection or Geometric Tools for Computer Graphics has a method, but I can't remember for certain.

raigan

Author

146

raigan

Apr 17, 2012 at 3:59 PM

Thanks! I have RTCD and GeomTools, and I haven't found exactly what I need yet, however maybe I just need to look a bit harder

The main thing is that the voronoi regions are NOT explicit, they don't exist in the "intersection of halfspaces" representation; however they still need to be taken into account somehow in order for the distance query to return the correct result. AFAICT no one tackles this problem, beyond "convert to boundary representation where voronoi regions/support geometry (verts and edges) are explicitly modelled"

jefferytitan

128

jefferytitan

Apr 19, 2012 at 4:42 AM

I've been working on a CSG raycasting approach, so this seems similar. I raycasted the individual objects, then took the furthest collision, after checking that the objects did indeed overlap (e.g. for objects A and B, A closest point on ray closer than B furthest point on ray, and A furthest point is further than B closest point).

raigan

Author

146

raigan

Apr 19, 2012 at 5:22 PM

@jefferytitan: have you been able to support distance queries (instead of ray intersection queries) with a similar approach?

jefferytitan

128

jefferytitan

Apr 19, 2012 at 10:34 PM

It's not really an area that was relevant to my research, sorry.

clb

139

clb

Apr 20, 2012 at 5:01 AM

Christer Ericson has something about this in his Real-Time Collision Detection book. For the nearest point to convex polyhedron problem, it is suggested to either compute the closest point to each polyhedron face (first enumerate all the faces from your plane-bounded volume representation), or to precompute a Dobkin-Kirkpatrick hierarchy first for the polyhedron and use that for the nearest point query. The naive search takes time linear to the number of faces, assuming you have the faces already enumerated, and the DK hierarchy takes time logN to the number of faces. The naive search can be extended to also report the feature/Voronoi region of the polyhedron closest to the point, perhaps the DK hirerarchy can do that as well.

I know that's not working on the plane-bounded volume representation, but don't know of any way to achieve the test using that.

raigan

Author

146

raigan

Apr 20, 2012 at 1:48 PM

Okay, thanks -- I was hoping to avoid enumeration

I feel like there must be a field of research that's applicable to this problem, I just can't find it -- basically what I've got is a set of planes forming a convex volume/subspace, and a point which is outside that space, and I want to find the point inside the convex space closest to my point... sounds like a pretty basic optimization/constraint-solving problem, projecting the point into the valid convex region using the smallest possible vector.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.