🔒 Locked

Tri/Quad surface

Started by janta Jun 28, 2006 at 9:52 AM 1 reply 1k views

Original Post

Jun 28, 2006 at 9:52 AM

Hi GDNet. My problem is the following: I have a number of tris and quad in my scene that are used as occluders. I want to select a subset of them every frame (or every 60 frame) and one relevant criteria to do so is to compute their surface when projected on the screen. The more surface an occluder covers, the better. Practically, I am given 3 or 4 two-dimension points A,B,C(,D) that have no particular reason to form a screen aligned tri/quad What would you advise to sort these primitives in order to select only, say, the 5 best of them ? At first I thought I could calculate the exact surface, which is mathematically speaking quite easy but a little bit too computationally expensive as it implies square roots. Then I tried another approach that is to calculate the area of the AABB of the quad or triangle. while this is much more efficient, it introducies sometimes very bad approximations of the area. In particular, when a primitive is viewed at a very low angle, this approach tend to give ugly results:


                        A
  .---------------------+--.
  |                        |
  |                        + B
  |                        |
  |                        | --> Axis Aligned Bounding Box: Bad approx of ABCD area !
  |                        |
  |                        |
C +                        |
  .-+----------------------.
    D

but sometimes it is good:


     A
  .--+---------------------.
  |                        |
  |                        + B
  |                        |
  |                        | --> Pretty good approx
  |                        |
  |                        |
C +                        |
  .---------------------+--.
                        D

Would someone have a better approach to suggest ? Like including another factor (at the time of writing this, I just thought of using the view angle as another factor, that could be an idea... Another issue is the same bounding box can be a very good approx for a quad and a very wrong one for a triangle:


     A
  .--+---------------------.
  |                        |
  |                        + B
  |                        |
  |                        | --> Pretty good approx of ABCD
  |                        |
  |                        |
C +                        |
  .---------------------+--.
                        D


     A
  .--+---------------------.
  |                        |
  |                        + B
  |                        |
  |                        | --> Pretty bad approx of ABC
  |                        |
  |                        |
C +                        |
  .------------------------.

I thought of halving the area in case of a triangle but in a lot of cases that would be quite unfair. Thanks for reading Cheers, Janta

Figgles

Jun 30, 2006 at 7:27 PM

Hmm, I am definitely not an expert on the subject of occlusion culling, but I would suggest that if you had to pick the "best" 5, I would guess that the closest to the camera would be ones with the most area on screen (and thus occlude more pixels -- at least, with a perspective projection). Distance involves square roots, so it would be easier to use squared distances.
The problem you are refering to with the AABB's is quite common actually. You could try OBB's, but they take longer time to compute.

As far as slow performance...
If you are using OpenGL or Direct3D, you might look into occlusion queries for hardware acceleration; but be warned, they are a double edged knife: syncing with GPU can be slow if # there is a small number of primitives, where the cost of syncing with GPU is NOT amortized over a larger set.

I hope that helps some or gives you ideas to solve your problem.

nmi

Jul 1, 2006 at 8:12 AM

Quote:
Original post by janta
... and one relevant criteria to do so is to compute their surface when projected on the screen. The more surface an occluder covers, the better.

...

At first I thought I could calculate the exact surface, which is mathematically speaking quite easy but a little bit too computationally expensive as it implies square roots.

You can do it without square root for a triangle. See equations (16) and (17):
http://mathworld.wolfram.com/TriangleArea.html

Basically 5 additions/subtractions and 3 multiplications:
(signed) Area = 0.5 * ( (xc-xb) * (ya-yc) + (xa-xc) * (yb-yc) )

Topic Locked

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