[help-3dldf] Fwd: Re: button-hole problem

[Laurence Finston]

------ Forwarded message -------


From: "Laurence Finston" <address@hidden>
To: Larry Siebenmann  <address@hidden>
Cc: address@hidden, address@hidden
Date: Sun, 24 Apr 2005 17:13:55 +0200

> Unfortunately, programmers usually have to
> pay attention to degenerate cases -- they are like
> accidents waiting to happen.

I get some pleasure out of it.  It appeals to my sense of pedantry.

> 
>  > occlusion of two polygons
> 
> ??? whazzat?

I mean handling the case where the projection of one polygon occludes the
projection of another, in whole or in part, given a particular focus.
I have implemented this for two polygons, as shown in a sequence of ten images
at the top of the GNU 3DLDF website:
http://www.gnu.org/software/3dldf/LDF.html
It works here, however there are a couple of problems, as you can see from the
images I used as examples for `cnepspng'.  By the way, I discovered some old
code where I used the `-T' option to `dvips', so perhaps it won't be necessary
to use `mogrify', after all.

My idea was to divide the 3D objects in space so that the resulting objects no
longer intersect.  This works to a certain extent.  When outputting a
`Picture', the objects on it can be sorted in three different ways:  by the
maximum z-value of the `Points' belonging to that object, the minimum z-value,
or the mean of these two values.  The z-value is that of the projection of the
`Point', which results from multiplying the world coordinates by the
transformation matrix representing the perspective transformation.  This value
is not output to the file of MetaPost code, since a `Point' projected onto the
x-y plane doesn't have a z-value, and MP has two-dimensional `pairs', not
three-dimensional `Points', but it is proportional to the distance of the
`Point' to `Focus::position'.  In fact, I don't divide the z-value by the
w-coordinate after the transformation, as I do for the x and y-coordinates.  I
programmed this quite a long time ago and I don't remember how it works, but
when I recently tried to perform this division, the z-coordinate always became
0 (actually, its absolute value always became < Point::epsilon).  This
division isn't necessary, anyway, since all I need are the relative distances
of the `Points' from Focus::position.

However, the problem is that while the objects may not intersect, their
projections might, and using the maximum, minimum, or mean z-values doesn't
provide enough information for performing occlusion correctly.  In addition,
the loops I use for comparing the objects on a `Picture' are somewhat
complicated, and I've probably made a couple of mistakes somewhere.  Nobre has
explained that in FEATPOST, he uses the pyramids whose bases are the polygons
and whose points are his equivalent of Focus::position for occlusion.  I
believe the intersections of these polygons can be used to determine which one
is in front, but I'm still trying to figure this out.

> You can ignore it.  But it is helpful to consider
> because the sphere (eye) with opposite points
> identified is a model of projective 2-space RP^2.  One
> in which no particular line at infinity is has privilege
> and in which the compactness of RP^2 is obvious. It is
> natural since God gave your users spherical eyes and a
> preception of projective geometry through them.

Okay, I'll bear this in mind.

>  > it might be useful to just store the center of an
>  > object and a transformation matrix.
> 
> I favor 3-dimensional scenes which one can journey through
> with a computer. 

Of course, `Points', `Paths', or whatever would need to be generated when 
they are needed for a given operation, like showing or outputting.

>  > The "up" direction is determined somehow, I don't
>  > remember how, 
> 
> It is determined by gravity via the inner ear, I
> believe.

For a person, yes, but you can rotate a camera about the axis from the
aperture to the focus (or whatever it's called), it doesn't care.

> Of course this mechanism is switched off sometimes
> for astronauts and athletes.

In traditional perspective drawing, one usually has a ground plane.  There is
no concept of a ground plane when using transformation matrices.  One can use 
the x-z plane if one wants to, but there's no need to.  This is one reason why
the results of setting setting Focuses in 3DLDF might be counter-intuitive.

> Let me try to understand using a model eye or camera.

> Are you, in other words, introducing a new oriented isometric
> coordinate system on 3-space: origin at the center C
> of the eye, the z-axis running from that center out
> through the center of the 'pupil' P? The y-axis
> 'vertical', and the x-axis 'horizontal'.

Yes.  The C++ code makes it possible to use different axes, but since the
results are completely equivalent, I haven't made it possible to access this
functionality interactively (using 1.2.0).

Your description of the technique is entirely correct.

> Occultation is a 
> major problem I won't explain. 

To the best of my knowledge, the standard approaches to occultation use raster
information.  There are good reasons for this.  They are computationally
expensive but straightforward.  My approach is to divide objects and their
projections until they don't intersect.  This requires being able to find
their intersections.  To my dismay, I've discovered that intersection theory
is a non-trivial branch of mathematics, so I may not be able to implement a
complete solution to this problem for all types of curves.

> Also color 
> luminosity texture shadow, reflection, transparency 
> -- gasp. 

I've made a start on luminosity and transparency, which are two sides of the
same coin, and reflection.  Shadows can be implemented as a form of
projection, or by using raster-based rendering techniques.  So I'm in no
danger of running out of things to do.

> If one is to be able to tour through 3D scenes, a
> model of this complexity seems necessary.

Indeed.  As one of the immutable laws of programming states: "There is no free
lunch".

> All this is guesswork.  Is is consistent with *some*
> 3D graphics system?

Yes, as far as I know, all of them.  You have stated the problems very clearly
and accurately, and any canned solutions would be very welcome.

Thanks again.

Laurence