Re: Searching algorithm for determining voxels in pyramid

Marco Körner said:

Hello,

I'm working with a optical sensor. This sensor has a pyramidal field
of view. For updating my environmental model, I need to know the
voxels lying within this pyramid.

I know:

- points of a pyramide with square base
- dimensions of each voxel

Does anybody have an idea how to solve this problem analytically?

Let the sensor be at S. "Looking" straight ahead, it can see an arbitrarily
distant point I. Around I are four other points, also arbitrarily distant,
which we will call E1, E2, E3, E4 (such that E1 is opposite E3), and which
form, not the corners, but the mid-points of the edges, of the pyramidal
field. You can choose the arbitrary distance R yourself. It represents the
range of the sensor. But I adopt the convention that E1 is "up" from the
midpoint, E2 is "right", E3 is "down", and E4 is "left":

+--------E1--------+
| V | N
| |
E4 I E2
| |
| |
+--------E3--------+

Imagine your eye is the sensor at S (not shown, because ASCII won't let me
poke my arm out of the monitor to jab you in the eye). If all you can see
is the above rectangle, then it represents an arbitrarily distant
"backplane" to the pyramidal viewfield. V is a Visible Voxel, and N is a
Non-visible Non-entity.

We're about to look at some angles. The baseline for angles is SI, with
lines striking the arbitrarily distant backplane "up" and "right" being
positive angles. Skip to the next paragraph if you understand this! Okay,
I want you to imagine that you are pointing your arm along the line SI.
Now, without moving it left or right, rotate your arm up towards E1.
That's a positive angle. Now move it towards E3. As you pass I, your arm
goes negative. Now point it at I again, and move it right (but not up or
down) towards E2. That's a positive angle, too. But move it left and, as
it passes I and heads towards E4, it goes negative.

A voxel V is within the field of view if it obeys six constraints:

1) Its distance SV from the sensor is < R.
2) Its distance SV from the sensor is >= 0. (i.e. we do not consider points
behind the sensor.)
3) The angle formed by the voxel V, the sensor S, and the arbitrarily
distant point I, i.e. the angle VSI, is less than the angle formed by E1,
S, and I.
4) The angle VSI is less than the angle formed by E2, S, and I.
5) The angle VSI is greater than the angle formed by E3, S, and I.
6) The angle VSI is greater than the angle formed by E4, S, and I.

If you are just detecting whether a given point is within the viewfield,
that's how to do it. But if you want to find ALL such voxels, it's a lot
quicker to start at the backplane (because that gives you sensible
leftrightupdown limits), determine or calculate E1, E2, E3, E4 to give you
those limits, accept all the points with co-ordinates in the range E1y to
E3y and E2x to E4x, and then just lather, rinse and repeat (bringing the
backplane forward by one voxel's depth) until R is 0.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
.

Relevant Pages

  • Re: description of camera design I would like to have
    ... | of wide angle lenses easier. ... |> rear element will end up being placed further away from the sensor. ... What size of sensor are you talking about? ... Leica forgot more about camera ...
    (rec.photo.digital)
  • Re: description of camera design I would like to have
    ... work with telephoto lenses that have a recessed rear element? ... of wide angle lenses easier. ... rear element will end up being placed further away from the sensor. ... how well the sensor deals with greater angle of incidence. ...
    (rec.photo.digital)
  • Re: Light fall off on dSLRs - an experiment
    ... Interesting results and they seem to differ considerably from mine which I have just repeated over a range of angles to get more of a response map with azimuth and elevation angle of the light source relative to the pixels. ... I managed to do this by temporarily fitting a lens to the camera body and then just aligning it so that the light source was exactly on the central focus marker. ... I wonder if this is just due to a different sensor - it is dramatically different from my results which have a much flatter response. ...
    (rec.photo.digital.slr-systems)
  • Re: Stall alarm or sensor and combat manouvers.
    ... airplane with a second epochal invention, the angle of attack ... sensor and aircraft stabilizer. ... It's a stall warning sensor that effectively actuates what is a stick ...
    (rec.aviation.military)
  • Re: description of camera design I would like to have
    ... |> So how well does your stock sensor with its normal flange distance ... |> work with telephoto lenses that have a recessed rear element? ... |> how well the sensor deals with greater angle of incidence. ...
    (rec.photo.digital)