The Datafile PD-CD 3/PDCD_3.iso/utilities/utilsf/graphtext/cga/text0001.txt

Text File | 1995-03-27 | 13.6 KB | 356 lines

A simple data example would be an array of SEG pointers that is
"grown" as needed, in blocks of...say...512 segments at a time.
When you run out of available segments, you simply allocate another
block, and give one up.

Here's some psudo-code for the GetSegment() routine:

SEG *GetSegment( void )
{
   if (there are no available segments)
   {
      GrowReservoir()
   }

   Find an available segment
   Decrease the number of available segments in the reservoir
   Return the segment pointer
}

The segment manager might consist of these routines:

    InitSManager()

        Allocates the default base number of segments for the reservoir
        probably by calling GrowReservoir()

    UninitSManager()

        Frees all memory in use

    ResetSManager()

        Marks all segments in reservoir as "available"

    GetSegment()

        Find an available segment (call GrowReservoir() if none are
        available), mark it as used, and return it's pointer.

    CopySegment()

        A simple memcpy() will do

    GrowReservoir()

        realloc() the reservoir's array of segments in increments of
        some pre-determined number.  Use a #define for this number
        for fine-tuning memory usage.

-------------------------------------------------------------------------------
Q:  "What are some ways to improve the Insertion routine?"
-------------------------------------------------------------------------------

Now, it's your turn.  Let's have some optimizations.  I'd love to see
any code/psudo-code submissions to the FAQ!  Here are some things to
consider:

  1.  Using a Binary-searchable tree instead of a linked list

  2.  Checking entire New segments for fully behind or in-front
      before adding or quitting.

  3.  [this section not complete]

-------------------------------------------------------------------------------
Q:  "What about accuracy?"
-------------------------------------------------------------------------------

Considering the accuracy of splitting two 2D line segments, the
accuracy is perfectly pixel accurate where as a 16-bit z-Buffer is
only partially accurate for a 32-bit world coordinate system.

-------------------------------------------------------------------------------
Q:  "What kind of performance can I expect?"
-------------------------------------------------------------------------------

I can't say, at this time, exactly what sort of performance
improvements to expect over z-Buffer.  It all depends on the
application, the code used for the segment manager, and especially the
insertion routine.  When I have some numbers, I'll include them here.

However, let me explain why I believe you can expect better results
out of s-Buffering than z-Buffering in hardware.  No this dude ain't
nuts, that's right, software that's faster than hardware.  Keep on
readin'. :)

When you're rendering to the s-Buffer, if you're clever about it in
your insertion routine, you can eliminate many segments before they
get into the s-Buffer, so you've just eliminated a segment that your
code would have spent VERY valuable time drawing.  Consider this
example:


                    +----------+    +----------+
                    |4444444444|    |2222222222|
                    |4444444444|    |2222222222|
                 +------------------|2222222222|--+
                 |111111111111111111|2222222222|11|
                 |111111111111111111|2222222222|11|
                 |111111111111111111|2222222222|11|
                 |111111111111111111|2222222222|11|
                 |111111111111111111|2222222222|11|
                 +------------------|2222222222|--+
                    |4444444444|    |2222222222|
                    |4444444444|    |2222222222|
                    |4444444444|    |2222222222|
                    |4444444444|    |2222222222|
                 +--|4444444444|------------------+
                 |33|4444444444|333333333333333333|
                 |33|4444444444|333333333333333333|
                 |33|4444444444|333333333333333333|
                 |33|4444444444|333333333333333333|
                 |33|4444444444|333333333333333333|
                 +--|4444444444|------------------+
                    |4444444444|    |2222222222|
                    |4444444444|    |2222222222|
                    +----------+    +----------+

     [You wouldn't believe how long it took to draw that!]


In the above example, the polygons are numbered.  Notice, I even used
the age-old problem of recursively overlapping polygons.  s-Buffers
handle it intuitively.

There are (roughly) 300 pixels in the above example.  200 of which
overlap.  Using z-Buffering in hardware, you will have to draw 500
pixels, keep in mind that you'll also have to track the z-coords for
each pixel for use with the z-buffer hardware.  But we'll ignore that
fact for now.

So you draw blast out 500 pixels.  This is your lowest-level code.
This is your fastest stuff.

You've just rendered a full-screen of polygons, and 40% of it was for
nothing.  Jeesh! 40%!  What a waste!

Consider s-Buffers.  They immediately find that where you have an
overlap in the example, there is no extra drawing to be done. Granted
this takes a little time (not much, mind you).  But the savings is
40% of screen-space coverage!  You're simply NOT drawing those
pixels!

There are other advantages, too.

s-Buffers allow you to cut your drawing to the significant pixels
ONLY. You draw 300 pixels (without tracking the z-coord along the
way).

Unless the hardware is drawing the stuff for you (which s-Buffers
should be nicely adaptable to -- if the hardware supports scanline
drawing of textures, shades, etc. rather than entire polygons) then
you're still doing the drawing.  The z-Buffer hardware is only helping
you out with your low-level code.  It's only doing something for
you.  It's not reducing the number of pixels you draw, it's just
doing some work for you.

s-Buffers not only reduce your workload by reducing the amount of
screen space coverage you're drawing to, but it does the z-Buffering
for you.  Just like hardware does.  Granted there is overhead for
inserting segments, but nothing compared to the rendering of them to
the screen only to find that they're not viewed.

So, in this example, you see about a 5/3 speed improvement.  It gets
much better as you have more hidden polygons.  But, with z-Buffering,
your performance just plummets with more hidden polys. It's an
inverse non-linear scale to your disadvantage.

-------------------------------------------------------------------------------
Q:  "Yeah, so like, what about memory?"
-------------------------------------------------------------------------------

Since you've written a segment manager (which is, by definition -- a
memory manager) you've got control.  You decide how much memory to
allocate at any one point in time.  The smarter your segment manager
is the better off you'll be.

But there is still the issue of how much memory to store the required
segments in the list.

For simple gouraud shading, here's what I would expect a segment
structure to look like:

typedef struct segment
{

   short  start_x, end_x;       // starting and ending Xs
   short  start_z, end_z;       // starting and ending Zs
   char   start_s, end_s;       // starting and ending shade values
   struct segment *Next;        // linker

} SEG;

I count 14 bytes per segment structure.  This means that if your
average segment is 7 pixels or more (consider this in YOUR
application), then you've saved memory over a 16-bit z-Buffer.

This does NOT include any in-efficiencies in your segment manager or
insertion routine (see the insertion routine questions for details).

You may not be doing simple grayscale gouraud shading.  You might
have colors, too.  Add a byte (or whatever your app requires) for
color.

Then there's the texture mapping information.  This adds to the size,
too -- possibly almost doubling the amount of memory required.  But
in some games (especially Wolfenstien-style games), you can still
find a tremendous memory advantage over z-Buffers since the segments
will most likely be so long.

These are things to consider when using s-Buffers.  If you find that
the s-Buffers will use more memory than z-Buffers, you've got a
decision to make:  Speed or Memory?

-------------------------------------------------------------------------------
Q:  "What are some more possible advantages of s-Buffers?"
-------------------------------------------------------------------------------

As you render the s-Buffer, you'll be rendering the screen top-down,
and each scanline from left to right.  I can't think of any obvious
advantages this offers other than the fact that it makes your
low-level drawing routine a tightly optimized muscle machine.

If you have any cool ideas to make use of this unique feature, please
lemme have 'em!

It would be an easy task to add information to your s-buffer lists
that allows you to determine which scanlines have changed since the
previous render so that your screen updates only contain updates to
the scanlines that have changed.  This will reduce the amount of time
you spend updating the slow RAM on your video card (for PCs).

For more, see the next two sections on Masking and Transparencies.

-------------------------------------------------------------------------------
Q:  "What about masking?"
-------------------------------------------------------------------------------

Many games have dash-board masks or the like.  s-Buffers offer a
clean way to handle this.

You can add a flag to your segment structures that can make it a
masking segment.

This way, you can build a masking s-Buffer, use it as your starting
point when you render, and insert segments into it, not letting them
interfere with the masking segments.  This will remove the need to
perform pixel-by-pixel masking as the image is drawn to the screen.

This will also prevent your low-level drawing routines from having to
render pixels behind the mask.

-------------------------------------------------------------------------------
Q:  "What about transparencies?"
-------------------------------------------------------------------------------

By extending the masking idea a bit further, you can flag certain
segments as transparent.  As you insert segments, any non-transparent
segments that fall behind the transparent ones won't remove the
transparent segments.  Any non-transparent segments that end up
in-front of the transparent ones will clip the transparent segments.

This brings up the problem that some segments now overlap with
transparent segments, making the Insertion routine that much more
complex.

Note that transparencies modify the image behind them.  If these
transparent segments are kept in order of left-right (following their
non-transparent neighbors in back-front order) within the linked-list
for a scanline, as the low-level drawing routine draws the
transparent segments, the non-transparent ones will already have been
drawn, and the transparency modifications will fall into place
nicely.

-------------------------------------------------------------------------------
Q:  "What are the disadvantages?"
-------------------------------------------------------------------------------

If s-Buffers are used to store many small segments, of if you use an
in-efficient Insertion routine, you might find that the memory
requirements will be quite high.  I would expect that this would only
be a concern in a small percentage of the applications out there.

There can be much difficulty in writing insertion routine.

s-Buffers won't work with some implementations of curved surfaces as
a z-Buffer will.




Path: bcc.ac.uk!uknet!EU.net!howland.reston.ans.net!news.sprintlink.net!swcbbs.com!swcbbs!josh.whiting
From: [e-mail] (JOSH WHITING)
Newsgroups: comp.graphics.algorithms
Subject: Converting 3D coords to 2
Message-ID: <[e-mail]>
Date: Sat, 04 Mar 95 23:25:00 -500
Distribution: world
Organization: Software Creations BBS
Reply-To: [e-mail] (JOSH WHITING)
References: <[e-mail]>
X-Newsreader: PCBoard Version 15.21
X-Mailer: PCBoard/UUOUT Version 1.10
Lines: 49

BK>  Hi!  I've been reading this group for a while, but this question
BK>hasn't been asked, how do you convert 3d coords to 2d so you can display
BK>them on the screen.  I want to write some simple 3D polygon routines and
BK>I'm really not in the mood to delve into the realms of Z-Buffering
BK>and texture mapping.  Is there a fast technique for converting 3D coords
BK>to 2D?  What is the equation for such a convertsion?  Thanx in advance
BK>for any help anyone can give me.

    I think this has definately been asked before <g> but here it is:

 ScreenX = X * DVS / (Z+DVS)
 ScreenY = Y * DVS / (Z+DVS)

        DVS is a constant which represents the distance to the view
screen.  I usually choose a value from 100 to 200 for DVS...
   Picture it like this:

   dvs
  |---|
                   _             _
  *\  |            |             |
     \|            | ScreenX     |
      *\           -             |
      |  \                       | X
      |    \                     |
      |      \                   |
      |        \                 |
      -----------*-----          -

  |--------------|
         z

    And the same diagram can be drawn replacing all the Xs with Ys.  It
uses similar triangles if you remeber your algebra classes

    This is the most generic one I know of...  there is the simpler one:

   ScreenX = X/Z
   ScreenY = Y/Z

    but I have not had much success with that one...

  L8r
-Josh Whiting
[e-mail]
---
 þ OLX 2.1 TD þ ..Most taglines are written by losers trying to be cool.