Very Computer

Greetings all!

Well I've decided it's that time for me, like countless other leagues
of programmers, to write my own realtime 3D PC engine.  My goal is to
generate a realtime 3D system that will let me construct and walk
or fly through my own virtual worlds.  Photorealism is not a concern
here, but a high frame rate (minimum 10+ FPS) is.  I'm shooting for
a C++ implementation, "true" 3D (no 2.5D DOOM/Wolf3D-like tricks),
with simple flat-shaded polygons.  From other demos I've seen with
such attributes, quite good speed is attainable with such realism
constraints.

I feel I have a fairly solid handle on the technical and math issues
involved in writing a 3D engine (clipping, matrix transformations,
projections).  However, I do have some questions about optimization.
Since a high frame rate is one of the primary goals, I feel it is
important to address optimization early in the design.

Specifically, the following issues concern me:

1)  Windows or DOS?  I am running Win 3.1, and I do have WinG installed.
I would like full-screen fast graphics -- does this basically rule out
using Windows, or can WinG do the job?  Also, does WinG accelerate all
graphics, or only apps specifically written for some special WinG API?
Where could I find documentation on this API?  Would it be best just
to stick to DOS?

2)  Should I write my own line drawing/polygon filling routines?  The
Windows API, as well as Turbo C for DOS, provide presupplied functions to
draw lines and filled polygons.  It would be nice not having to re-invent
the wheel, but will such presupplied routines be fast enough for a
realtime 3D engine?  I am not sure if the major slowdown would be
the mathematics involved, or if the actual screen updating would also
be a bottleneck.

3)  What, if anything, needs to be recoded in assembly for speed?
Matrix multiplication?  Screen updating?  Could a straight C++
implementation achieve 10+ FPS with flat-shaded polygons?  Where
should I be most careful about making sure code is optmized?

Any other general pitfalls to watch out for would be appreciated.
Thanks in advance.  I'm looking forward to this project.

-Norman

--


   |  |  _      |__    |    |  |   Coordinator for the "Fisher Price PXL 2000"
   |  |   |        |   |    |  |   camcorder mailing list.  Email for info.

I have a partially completed system that renders flat-poly worlds like
you discuss under X11 -- on my 2-66 it reaches very decent frame rates
( 20+ fps ). The whole thing is written in C down to the X11
interface, whereupon it becomes XFree's responsibility -- I don't
think there's much assembler in there though.

I don't clip the polys to view volumes particularly well since X11 is
going to do that anyway, and use GCC with all the optimisations I can
find turned on. I also create HUGE data structures as statically
allocated arrays and stuff, simply to remove memory management
overheads -- the polys are rendered into an array of structures and
then an array of pointers to that array is qsort()ed to depth sort the
polys. They are hidden surface removed by fairly simple math -- the
same stuff also shades polys so they get darker at shallower angles to
the camera ( it looks like there's a light mounted next to the camera
) and loops for stuff like matrix inversion were unrolled and
optimised by some helpful maths bods.

The best thing I can say is that if you design it properly you can
swap out bits later -- start using the built in polys and if that is
too slow, write your own later, the same with sort and maths
algorithms. Finding people to farm bits out to is always good -- if
you know any mathematicians who regard matricies as an interesting
field to play about with, you're onto a winner :-)

 --------------------------------------------+---------------------------------
"It's not a personality.. it's a bulldozer." | Which .INI file do you want to

  FL,HM,BV,PA-- DU,FS,TO,BO- TR+ SP,CA,TC++  +---------------------------------
      AQ,PI+++ #++++ S++ LS+ Hr F653 YB73m   |   No PGP, No HTTP, Just Me !!
 --------------------------------------------+---------------------------------

Your best bet is to use dos, write the main engine in C and write the
polygon draw in pure assembler!

Chris Kirby (Iguana Entertainment Ltd)

I'd seriously just write it in c ..
or c++, as it were.. windows or dos, it shouldnt really matter..
you're only trying to get 10+ fps.. I wrote routines to do z-buffered
gouraud shaded polygons, and it hits over 20fps on a 486 dx/2 80,
so I wouldnt worry too much about it..

As for the 'reinventing the wheel' bit..
well, a lot of standard libs dont use 'fast' polygon generation
they use one that works.. when your average person threw the compiler
together, the emphasis was on getting it to work, and getting most of the
code to work fast, not how many polys a second you can get out of the lib.
therefore, most of them suck.
you're probably better off writing your own polygon routines, but
try the standard ones, they might be fast enough for your purposes..

: 3)  What, if anything, needs to be recoded in assembly for speed?
: Matrix multiplication?  Screen updating?  Could a straight C++
: implementation achieve 10+ FPS with flat-shaded polygons?  Where
: should I be most careful about making sure code is optmized?

The routines I mentioned earlier were written completely in C..
so, I wouldnt be too worried.. standard greater than, less than clipping
would probably be best for you.. save you the hassle of trying to
comprehend the cohen-sutherland algorithm, or some of the more obscure
ones that save you like three clock cycles per minute..

Just let your compiler optimise for you.
go through, rewrite the polygons first if that's not good enough.

if even that isnt working well.. uhmm.. switch to fixed point math,
(though, from what I hear, floating point on anything above a 486/66 is
actually as fast or faster than fixed point)

screen updates, set your compiler on 'optimize the hell out of' and it should
work ok..

Give it a shot.
Latz,
Greg

Quote:> 1)  Windows or DOS?  I am running Win 3.1, and I do have WinG installed.
> I would like full-screen fast graphics -- does this basically rule out
> using Windows, or can WinG do the job?  Also, does WinG accelerate all
> graphics, or only apps specifically written for some special WinG API?
> Where could I find documentation on this API?  Would it be best just
> to stick to DOS?

WinG works fine, however while performance will likely be very near that of DOS, Window
sizes shrink so the overall experience isn't as nice.  If you are using Win95 or WinNT
then you can skip WinG and go straight to CreateDibSection() and BitBlt() (obviating the
need for WING.DLL and/or WING32.DLL).

I believe Chris Hecker had an article on WinG in Game Developer a long time ago.  For a
book on using CreateDibSection() I would recommend Animation Techniques in Win32 by
Nigel Thompson (Microsoft Press).

Quote:> 2)  Should I write my own line drawing/polygon filling routines?  The
> Windows API, as well as Turbo C for DOS, provide presupplied functions to
> draw lines and filled polygons.  It would be nice not having to re-invent
> the wheel, but will such presupplied routines be fast enough for a
> realtime 3D engine?  I am not sure if the major slowdown would be
> the mathematics involved, or if the actual screen updating would also
> be a bottleneck.

The built in Windows primitives are fairly slow.  However, even if you did use them
you'd be stuck flat shading -- anything that requires per pixel calculations such as
Gouraud shading or texture mapping would be rendered impossible going that route.  Not
to mention writing a polygon or triangle rasterizer is a rite of passage all 3D
programmers should have to suffer through at least once. :-)

Quote:> 3)  What, if anything, needs to be recoded in assembly for speed?
> Matrix multiplication?  Screen updating?  Could a straight C++
> implementation achieve 10+ FPS with flat-shaded polygons?  Where
> should I be most careful about making sure code is optmized?

Don't take anyone's word on this.  Measure your performance using a combination of
methods, such as profilers, RDTSC instruction on Pentium, and/or the Zen timer that
Abrash developed.  Look at what's taking the longest time, and work from there.

A straight C++ implementation should easily attain 30+fps on any reasonable
architecture.  If you choose very carefully what you code in assembly (rasterization is
the obvious first candidate) then you should easily be able to write a game that does
60+fps on a P5/75.  However you neglected to mention the type of complexity (# of
polygons, average size of polygons, etc.) and the specific type of computer and graphics
architecture you're targeting.

Brian Hook

Quote:(Norman Lin) writes:
>Well I've decided it's that time for me, like countless other leagues
>of programmers, to write my own realtime 3D PC engine.  

[SNIP]

Quote:>1)  Windows or DOS?  I am running Win 3.1, and I do have WinG
>installed. I would like full-screen fast graphics -- does this
>basically rule out using Windows, or can WinG do the job?  

No chance of getting super-fast graphics with this setup. Either stick
to MS-DOS or switch over to Win95 and use the GDK (which gives you
direct access to the screen).

Quote:>Also, does WinG accelerate all graphics, or only apps specifically
>written for some special WinG API? Where could I find documentation on
>this API?  Would it be best just to stick to DOS?

Yes. But WinG is obsolete now anyway. The GDK's DirectDraw will
accelerate virtually all graphics if the hardware supports it and
emulate everything if it doesn't. You can also change video mode in
Windows and use non-standard modes such as mode-x.

Quote:>2)  Should I write my own line drawing/polygon filling routines?  The
>Windows API, as well as Turbo C for DOS, provide presupplied functions
>to draw lines and filled polygons.  It would be nice not having to
>re-invent the wheel, but will such presupplied routines be fast enough
>for a realtime 3D engine?  I am not sure if the major slowdown would
>be the mathematics involved, or if the actual screen updating would
>also be a bottleneck.

If you're writing for MS-DOS then you should write your own. If you're
writing for Win95 you should check to see if the feature is supported
via hardware acceleration, and use your own if it's not.

Quote:>3)  What, if anything, needs to be recoded in assembly for speed?
>Matrix multiplication?  Screen updating?  Could a straight C++
>implementation achieve 10+ FPS with flat-shaded polygons?  Where
>should I be most careful about making sure code is optmized?

In my own experience screen updating is usually the only thing needing
to be assembly coded. DOOM supposedly had 3 assembly routines, one for
linea texture mapping (vertical and horizontal), the joystick driver
and a third which I can't remember (comms?). Always profile your code
to be sure.

Quote:>Any other general pitfalls to watch out for would be appreciated.
>Thanks in advance.  I'm looking forward to this project.

1) Calculate as much stuff in advance as possible

2) Only do perspective projections on each point once. This is
particularly important for points that are shared by 2+polygons (4+
edges).

3) See if you have enough memory to scan polygon edges once...it speeds
things up considerably when more than one object shares a common edge.

4) Make sure you use unrolled loops. If you wind up using mode-x then
make sure you fill polygons with the "4-pixels/instruction" method.

5) Have fun.

Cheers,

Mark Feldman

[3D STUFF DISCUSSED]

Quote:>>2)  Should I write my own line drawing/polygon filling routines? It would be
>>    nice not having to re-invent the wheel, but will such presupplied
>>    routines be fast enough for a realtime 3D engine?

YES, write your own line drawing/polygon filling routines. But do this a bit
later, make sure that the face hiding, 3d-2d routines are working. The flat
shading is easy, but I garauntee as soon as you get that working you'll be
desperate for a bit of Gouraud shading and texture mapping.

This is a relatively straight forward thing to do, if you have written your
own line drawing/polygoning routines. I found these the hardest thing to write
for my engine.

Quote:>>I am not sure if the major slowdown would be
>>the mathematics involved, or if the actual screen updating would also
>>be a bottleneck.

I've tested my engine with turbo profiler, the majority of my screen output
is assembler (however I haven't optimised them yet) and yet it's my screen
output that's taking up 85% of the processing. It still runs quickly but it
just shows that the screen update will almost always be the slowest thing in
your code (unless you go for some ray tracing/phong shading stuff:))

Quote:>>3)  What, if anything, needs to be recoded in assembly for speed?
>>Matrix multiplication?  Screen updating?  Could a straight C++
>>implementation achieve 10+ FPS with flat-shaded polygons?  Where
>>should I be most careful about making sure code is optmized?

My engine uses purely integers and I've coded it all in C++, since the
compiler will optimise integer variable manipulations extremely well.

I put all of my optimisation into the graphics output, the line drawing and
also the scan conversion of my polygons (since the scan convesion for texture
mapping and gouraud is similar for drawing a plain polygon)

Quote:>>Any other general pitfalls to watch out for would be appreciated.
>>Thanks in advance.  I'm looking forward to this project.

Don't believe all the so called experts :)

Paul

: The best thing I can say is that if you design it properly you can
: swap out bits later -- start using the built in polys and if that is
: too slow, write your own later, the same with sort and maths
: algorithms. Finding people to farm bits out to is always good -- if
: you know any mathematicians who regard matricies as an interesting
: field to play about with, you're onto a winner :-)

I think this is a very good suggestion.
Get the program WORKING first, before you do any OPTIMIZATIONS.

If you work too * the optimizations from the start,
you'll just make your life more difficult.  Whenever you get yourself
an error to debug in your program, you'll start to panic and
wonder what went wrong.  Optimized code is generally much more difficult
to maintain as well as to debug.

Why not just get anything that works first, then put in more neat features.
Optimization should generally be the last step , unless you're really
confident, and know exactly what you're doing.

As a general rule, 10% of your code gets executed 90% of the times.
if you optimize the code that only gets execute 1- 5% of the times,
such as the title screen, you won't get the speed performance
increase you want.  

Patrick Leung

Quote:>Perhaps its better to make your own  functions because
>(at least pascal) most of the programming languages use
>aA thie BIOS function to put pixel onm the screen and that
>function is very slow...The best way is to make your own
>fucntion that puts a pixel directly into the vga memory and
>then create function to draaw lines and fill poligons. I think
>that would be the faster way...

S*the function to plot a pixel.  This just wastes time in your
line/fill/box/sprite routine, with that extra call every pixel.
Plotting a pixel on a CHUNKY screen is trivial, so just do it manually
in all your custom routines.  Why re-calculate the pixel's address for
every pixel when, in most instances, you can just add 1 to the addr.?
-- Assembly language instruction INC DI is much faster than
        LEA     DI,[SCREEN]
        MOV     DX,320
        MUL     DX
        ADD     DI,AX
        ADD     DI,BX
                        (routine assumes the Y coord. is in AX and the X coord. is in BX)

Also, do it to a backbuffer in RAM, and then do a copy at the vertical
retrace if you want smooth, unfluckering, unspliced animating
graphics.  This takes some time.  If you cannot afford to lose this
time, you will have to look at MODE-X double buffering.

Clay

While I agree with what you said, most modern programmers would do this
as:
        shl     eax,06H
        lea     edi,[eax+eax*4+SCREEN]
        add     edi,ebx

And the 386 instruction set amazing?

Quote:>Also, do it to a backbuffer in RAM, and then do a copy at the vertical
>retrace if you want smooth, unfluckering, unspliced animating
>graphics.  This takes some time.  If you cannot afford to lose this
>time, you will have to look at MODE-X double buffering.

Or SVGA w/VBE 2.0+.  

--
Paul Hsieh

What I say and what my company says is not always the same thing

Quote:>I'm using mode 13h and copying the screen from RAM using rep movsd.  I'm
>NOT waiting for the vertical retrace anymore, and it doesn't flicker a bit.  I
>was wondering if that's only because I have a fast video card?  Would this
>definately flicker on slower systems?

You won't see flicker as in the old CGA systems in text mode (ie: snow), but
you might notice shearing along vertical lines and edges moving horizontally
(ie: you can see part of the line drawn further over without the whole line
there). However, in most of the standard Windows modes (StretchDIBits and such)
we're just going to have to live with this, and if your game is running quickly
your users may not notice either.

Dan

Quote:>>Also, do it to a backbuffer in RAM, and then do a copy at the vertical
>>retrace if you want smooth, unfluckering, unspliced animating
>>graphics.  This takes some time.  If you cannot afford to lose this
>>time, you will have to look at MODE-X double buffering.

I'm using mode 13h and copying the screen from RAM using rep movsd.  I'm
NOT waiting for the vertical retrace anymore, and it doesn't flicker a bit.  I
was wondering if that's only because I have a fast video card?  Would this
definately flicker on slower systems?

--Rob

Yes, it will. We tested it.

Cheers,
        Fat Brother.

Fatal Error: Couldn't enter Windows, use Doors.

--
~/.signature