🔒 Locked

PVS for constrained Delaunay triangulation

Started by Zakwayda May 30, 2009 at 5:54 PM 6 replies 4k views

Original Post

May 30, 2009 at 5:54 PM

For the AI in my (2-d) game, I'm using a navigation mesh built from a constrained Delaunay triangulation. For each triangle in the mesh, I'm computing a PVS indicating which triangles in the mesh are potentially visible from within that triangle. To determine triangle-to-triangle visibility, I'm traversing each portal sequence in the mesh while maintaining a pair of convex hulls built from all portal endpoints encountered on the left and right, respectively. Since a given portal sequence will only admit a sightline if the left and right sets of portal endpoints are linearly separable, the search can be terminated as soon as the hulls intersect (please correct me if I've got any of this wrong!). Now, I'm wanting to add an additional bit of information for each entry in the PVS: whether the triangle in question will always be fully visible from the source triangle, regardless of the position of the observer. I haven't found any references that discuss this, but here's what I've come up with so far. Given two triangles that do not share any vertices, build lines passing through the left and right endpoints, respectively, of the first and last portals in the portal sequence connecting the triangles. If the two triangles fall between the two lines and the left and right convex hulls are entirely behind the respective lines, the triangles will always be fully visible with respect to one another. Here's a diagram that illustrates this:

When the triangles share one or more vertices, the line(s) must instead be built from the shared vertex and the opposite vertex of the source triangle:

This seems to work, but I don't have any formal proof of its correctness. Can anyone offer any comments on this? Is this a correct way of determining 'full visibility' between two triangles in a constrained Delaunay triangulation?

Dave Eberly

May 31, 2009 at 12:51 PM

For clarification, what do you define as a "portal sequence"? Is this just a triangle strip connecting the two triangles involved in the visibility test? What is a "portal endpoint"?

What do you mean by "a triangle fully visible from another triangle"? For example, consider two triangles (A and B) sharing an edge. If the union of the triangles is a convex quadrilateral, then each point in A can see every point in B, and vice versa. Is B fully visible to A (and vice versa)? What if the union is not a convex quadrilateral? Some points in A can see every point in B, but some points cannot. Is this "not fully visible"?

Zakwayda

May 31, 2009 at 2:26 PM

Thanks for your reply, Dave.

Quote:
For clarification, what do you define as a "portal sequence"? Is this just a triangle strip connecting the two triangles involved in the visibility test? What is a "portal endpoint"?

Here's a revised version of the first diagram to help clarify:

The green lines are portals (unconstrained edges in the CDT). The orange arrows show the sequence of portals connecting triangle A to triangle B. Each portal has a left and right endpoint relative to the direction of graph traversal; these endpoints are circled.

Just for additional reference, the concepts and terminology that I'm using here are pulled mostly from this paper by Seth Teller (specifically sections 3.1 and 3.2).

Quote:
What do you mean by "a triangle fully visible from another triangle"? For example, consider two triangles (A and B) sharing an edge. If the union of the triangles is a convex quadrilateral, then each point in A can see every point in B, and vice versa. Is B fully visible to A (and vice versa)? What if the union is not a convex quadrilateral? Some points in A can see every point in B, but some points cannot. Is this "not fully visible"?

Yes, thanks, that's exactly what I mean by 'fully visible' and 'not fully visible'.

Dave Eberly

Jun 1, 2009 at 1:06 PM

Teller's paper used "portal sequence" regarding cells. I did not see mention of triangulations (constrained Delaunay or otherwise). However, your clarification shows what you intend.

I think what you claim is true, because what you have are two triangles connected by a convex quadrilateral, the union being a convex polygon. By convexity, any point in A can see any point in B (and vice versa).

This reminds of me a post to comp.graphics.algorithms many years ago, where there was a question about full visibility between two line segments. The "top" vertices of the line segments were connected by a polyline and the "bottom" vertices were connected by a polyline. I recall constructing an algorithm that answered whether or not there was full visibility, and this algorithm did not require computing convex hulls. I'll see whether or not a Google search on c.g.a yields anything about the post and my response.

Dave Eberly

Jun 1, 2009 at 1:13 PM

I found the post.

Unfortunately, I had links to some pictures I drew, but I no longer have those pictures at my web site. Hopefully, the text is enough to make clear the algorithm.

Zakwayda

Jun 2, 2009 at 11:02 AM

Quote:
Teller's paper used "portal sequence" regarding cells. I did not see mention of triangulations (constrained Delaunay or otherwise).

Yes, sorry if I was unclear about that. Teller speaks only of cells and portals in the general sense (convex subspaces connected by non-opaque regions of dimension n - 1). I've basically been considering the CDT as a special case of a general cell-portal graph, where all cells are triangles, and all portals are unconstrained edges shared by two triangles.

Quote:
I think what you claim is true, because what you have are two triangles connected by a convex quadrilateral, the union being a convex polygon. By convexity, any point in A can see any point in B (and vice versa).

That's good enough for me :) I haven't been able to come up with any counterexamples, but I just wanted to make sure I wasn't missing anything obvious.

Thanks for your help, and for the link to the CGA thread - I appreciate it.

Gl_Terminator

Aug 16, 2011 at 6:45 PM

Here is a link for a 2D delaunay triangulation example in C# http://vasilydev.blogspot.com/2011/08/delaunay-triangulation-example-in-c.html

Maze Master

Aug 17, 2011 at 7:02 AM

For closed compact path-connected sets, local convexity implies global convexity.

This means, inspect the boundary of the set with a magnifying glass. If, nomatter where you look, the part of the set you see in the magnifying glass is convex, then the set is globally convex.

If I understand correctly, the method you're using will create sets with no holes, bounded by straight lines, and with the corners having interior angles less than 180 degrees. This means it is locally convex everywhere on the boundary, which means it is globally convex.

Topic Locked

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