Re: a book or tutorial

[Steve Baker <sjbaker1@airmail.net>]

Mads Bondo Dydensborg wrote:
> 
> On Tue, 27 Mar 2001, Steve Baker wrote:
> 
> > Mads Bondo Dydensborg wrote:
> 
> > > In practice, I would say that today you have very little reason to know
> > > about how to scanconvert your own lines using only integer arithmics, etc.
> > > If you are not (somehow) using hardware for this (even in 2d), you are
> > > doing something wrong. (Exceptions are if you are writing a general
> > > purpose library, like Mesa, or the GIMP or something similar).
> >
> > It's like this:
> >
> >   1) You need to know stuff like that.  How to scan convert a line for
> >      example - because it comes up in other context.  Less than a week
> >      ago I needed to check whether two characters in a game could see
> >      each other over a lot of intervening terrain.  I had a height map
> >      of the terrain built - and one way to test for intervisibility was
> >      to walk across the height map using Bresenhams line drawing algorithm
> >      in 3 dimensions. (It turned out that I used a MIPmapping trick and
> >      did it better/faster without that).
> >
> >      So, these old techniques are useful even when you have hardware 3D.
> 
> This is a good example of why I must retract part of my statements. Ok,
> doing a line between to arbitrary points in space may be usefull. OTOH you
> ended up not doing it. So, knowing the algorithm is probably
> usefull.

Yes - and in fact, the way I finally did it relies on some other algorithms
associated with texturing and MIPmapping that people *also* no longer tend to
learn because the hardware does it for them.  But unless you have a 'library'
of these algorithms in your head, you won't stand a chance to spot where one
of them can be re-used in a new situation.

> Knowing how to optimize it for 486 assembler is probably not.

Agreed.

I often wish humans had conscious control of their memories.  I would happily
dump my memories of the complete Z80 instruction set (in hex) if I could
re-use that space to remember some of the more important URL's I use.  :-)

> And, btw. wouldn't the most correct solution be to determine if there are
> any line of sigth with a "cone"?

The rays of light from one player to the other travel in a straight line...
at the scale I'm working on, the two characters can be considered as infinitely
small points compared to the size of the terrain - so all I needed to know
was whether the straight line between the two points ever dipped below the
terrain skin...and even that could be done approximately - the consequences
of an error would not be at all serious.

> Starting from one of the figures
> viewpoints the outline of the cone would be sort of shaped like the other
> figure? Isn't that like casting a light? Couldn't you place a light in one
> of your figures viewpoint, direct it a the center of the other figure, let
> it shine, and see if the other figure received any of the light? Couldn't
> you maybe use hardware for this?

It wouldn't be as efficient as my final algorithm...but that's another story.
 
> And even if you didn't do it like that - if you use a triangle
> representation, couldn't you traverse the triangles between the two
> figures, determing if any intercepted the line between them? Might have
> been an OK solution?

It would be *horribly* expensive - and I didn't need an answer that was
that exact...it was for AI planning.
 
> I am _not_ against learning books, and not against learning to "crawl
> before you walk". I just wish people would finish their games instead of
> optimizing their line drawing routines.

Indeed.  Books like the 'graphics gems' series are WELL worth having as
a source of ancient algorithms that may have new uses.  There is even a
faster line drawing routine that Bresenhams in there!

-- 
Steve Baker   HomeEmail: <sjbaker1@airmail.net>
              WorkEmail: <sjbaker@link.com>
              HomePage : http://web2.airmail.net/sjbaker1
              Projects : http://plib.sourceforge.net
                         http://tuxaqfh.sourceforge.net
                         http://tuxkart.sourceforge.net
                         http://prettypoly.sourceforge.net
                         http://freeglut.sourceforge.net

---------------------------------------------------------------------
To unsubscribe, e-mail: linuxgames-unsubscribe@sunsite.dk
For additional commands, e-mail: linuxgames-help@sunsite.dk