Jump to content
  • Advertisement
Sign in to follow this  
Libe

Sweep selection and frustum culling

This topic is 4566 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, in my app I'd like to let the user to drag a rectangle to select all the triangles inside of it. I thought this was a kind of frustum culling with the frustum restricted to the selection rectangle; so I worked out the frustum give the selection rectangle and I came up with this simple approach: test all the points of a triangle and if a point is inside the frustum select the triangle (I'm using a early exit to speed up a little). Unfortunately this method doesn't deal well with situations like the one below, where 0 points are inside the frustum but the user'd like to select the triangles anyway: Image Hosted by ImageShack.us but works just fine here: Image Hosted by ImageShack.us I'd like to deal with situations like in the 1st image...maybe I should implement some clipping algorithm or maybe a simple way exists? Also, testing 3 points per triangle seems kind of expensive: I'm wondering if there's a better approach to cull a triangle against a frustum...any idea will be greatly appreciated! Thanxs Libe

Share this post


Link to post
Share on other sites
Advertisement
You will also need to test the edges of the polygons, not just vertices. Simply check to see if the line that makes up the edge of the polygon intersects with a plane in your frustum (line to plane intersection test).

And no, there is no better way than to test all of the points of the polygon. It is expensive, which is why you only do it unless you absolutely have to. :) However, for your purposes, testing is only going to be done once, not every frame.

That being said, though, if you can somehow cut down on your test set (using smaller sets of bounding boxes around the model), then you can definitely increase performance.

Share this post


Link to post
Share on other sites
Quote:
Original post by bpoint
You will also need to test the edges of the polygons, not just vertices. Simply check to see if the line that makes up the edge of the polygon intersects with a plane in your frustum (line to plane intersection test).


Thanxs for your reply,

maybe I misunderstood you but I think I should do something like a line in frustum test not just a line to plane intersection test. Or am I wrong?

Libe



Share this post


Link to post
Share on other sites
You could use OpenGL selection mode, which would return anything that was partially or entirely drawn within the selection frustum. However, that might be slower (and less flexible) than the general solution. I think maybe what you want is a simplified separating axis test between the triangles and the frustum, perhaps with a bounding volume hierarchy to accelerate the test. This approach would handle the problem case that you mentioned, and would be relatively inexpensive.

Share this post


Link to post
Share on other sites
A "line in frustum test" basically is a line to plane intersection test for all planes in the frustum. :)

To expand a bit on jyk's reply, OpenGL's selection mode basically works by drawing each polygon in a unique color (an ID), and then tested within a 2D region. It requires you to rerender your scene, but that's probably not too big of a problem. However, since it does bind you to OpenGL, you should consider first if you need to support other graphics APIs or not.

As for the bounding volumes, if you could separate different sections of the model (say, the hat and the face), then you could check which bounding volumes intersect the frustum first, then test all of the polygons within that volume. For example, that particular selection would only need to test the hat, since the face portion does not intersect the frustum at all.

Share this post


Link to post
Share on other sites
Quote:
Original post by bpoint
...OpenGL's selection mode basically works by drawing each polygon in a unique color (an ID), and then tested within a 2D region. ..."


Just to clear up a common misunderstanding. The OpenGL selection mode doesn't work this way. To quote the blue book

"In selection mode, no pixel fragments are produced from rasterization. Instead, if a primitive intersects the clipping volume defined by the viewing frustum and the user-defined clipping planes, this primitive causes a selection hit. (With polygons, no hit occurs if the polygon is culled.)"

However, to the original question:

[Edit - I just read jyk's reply]

Jyk is spot on, implement the separating axis method for your frustum and your pimitives, and you'll be laughing.

For your selection process:

* First test the object's bounding volume against the frustum.
* Now for any object whose bounding volume intersects the frustum, test the primtives (triangles, points whatever) to see which of those intersect your frustum.

There are several techniques you can use for dividing up your mesh to get fast spatial testing, such as KD trees or Octrees (and of course many others)

There is a swathe of information out there for how to do intersection between a number of primitves. One very handy page is this one:"

For some excellent code on the intersection of various primitives, have a look at : http://www.geometrictools.com/Intersection.html

- Phil

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!