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?

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"?

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'.

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.

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.

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.

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