Code - 3D engine: optimization based on the prototype of the 3D Construction Kit.

3D engine: optimization
Alone Coder

   In2016 I abandoned everything and wrote─
sal the new 3D engine that I showed
at the autumn meeting of NedoPC, and now I propose─
I bring it to your attention.
   His idea is to implement something similar to Total
Eclipse, using mostly 8-bit 
calculations. That is, in particular, to do
global rough truncations over entire objects─
there, and clip the vertices already on the screen.
The idea, as usual, was in my head─
ve since1997, but I needed to write
two 3D engines in a regular demo maker
(useless for practical purposes) style
"object shower" to gradually come to
implementations.

                  * * *

   So, since we have a very cool
prototype - 3D Construction Kit, our OS─
the new trump card should be speed (and
through it - for example, the screen area).

   It is important to note that already at the beginning of development
to run a fast program you must have knowledge─
formation, approximately how many passes each─
On average, a long cycle is required. Otherwise op─
optimization can only be done locally, and
We are talking about complex optimization here - not─
a big loss somewhere turns out knowing─
significant gain elsewhere.When
the program is already ready, determine the importance
each procedure is easier. When I optimize─
I tried ZXUnRar and JPEG Viewer (and I opted for them─
mized several times each), I grew─
I worked out this method: to all interested me─
I put in the aisle counters and look,
how many times it was executed. At Screw's
there is a version of Unreal Speccy that allows you to
tomatize such things, but I used
simple code inserts. Or another method
- I add well-known ones somewhere
pause and see how much the number has jumped
bars...
   When I was writing a new 3D engine, I
in general already knew, for example, that filling
pixels take up less than half of the total
time for complex scenes. Therefore the main
acceleration affected calculations and piping. And
Of course, the minimum was done first
working skeleton (based on the model inDelphi ),
on which pieces were gradually replaced.

   Let me draw your attention once again: this is not
a regular 3D engine for dem, where in front of your nose
some object is spinning. This is the engine, rea─
licking "immersion" into the scene. What
There was almost none in Spectrum demos. Then
there are questions about increased accuracy
calculations, clipping, storage and processing
scenes of many objects and several systems─
those coordinates.
   The initial requirements for the engine are:
  - there is not just one object in the scene, there are dozens of them.
And more than half of them are notvisible. 
  - some objects are the same (and copies
should not take up a lot of resources), but some─ 
which are unique. 
  - each object has its own rotation angle
at least around the vertical axis (important 
for enemies and weapons). 
  - the dimensions of the working area should allow
implement a game room. More for now 
no need. 
  - objects can be wire, filled─
rich, textured, mixed - in the future with 
textures and shaders, and this should be done─ 
repent. 
  - the engine must also work on
original 48K, and there should be 
ability to connect additional features 
for 128K and ATM Turbo 2+. 
  - everything should work many times faster than
engine in Total Eclipse. 

   The general design of the engine was assumed to be the same
coy:
  - only rotate with full precision
entire objects. The vertices of the objects rotate 
already in eight bits. The only problem is in the lane 
prospective correction. 
  - there is a ruler of projection scales
objects where neighboring scales differ 
by2times. This allows you to rotate the vertices in 
all scales with fast 8-bit code, and 
at the same time implement fast 8-bit code 
checking the visibility of the polygon. 
  - only volumes are clipped in space
entire projects. Polygons are already truncated into squares─ 
screen speed. There is a maximum time─ 
object measures - "unit cube"(bZxbZxbZ).
If the object is larger, it will stand up immediately 
few problems: it will disappear abruptly 
at the edges of the screen; you won’t be able to turn the ver─ 
tires in the range +-31(if you do not enter 
additional scaling is no longer the same─ 
only for projections of objects, but also for themselves 
objects); there will be polygons the size of bo─ 
more screens that Otri does not support─ 
sovschik from NedoDemo (descendant of the famous 
renderer from Spectrum Expert #2 ). 
  - calculation plane for the vertices of the face─
two screens wide (256dots) 
and the same in height. Everything that didn't fall into 
two screens, “flattened” to the boundaries of this 
area. It can be seen that the geometry resolution at 
this is2pixels, but when drawing─ 
where it shouldn’t be visible - lines and 
ligons between these points are drawn from the floor─ 
noah accuracy. In chunks this is especially not the case 
see. But we need to watch out for errors 
calculations, otherwise the points will jump around 
all sides are 2pixels or more. Because of 
this had to be abandoned several times 
original methods of prospective correction─ 
tions - a couple of options through the correction ta─ 
blitz and a couple of options through the logarithm. 
  - all parametersscreens are customized.You─
water on the screen - a separate module. 

                  * * *

   Let's start with a method for optimizing complex
calculations that I worked on last
a couple of years. Let's take one calculation,
whose role in the overall program we know.

   First we write a calculation diagram. For example:
;# count this and that 
;# count this 
;# rendering like this 
   These will be the stage titles playing
the role of comments.
   Where the formulas are written, we indicate
necessary accuracy of calculations. For example:
dX12=(X2-X1)/H12 (+-6.0 / 6.0 = +-6.8).
This means that we are 6 signed bits
divide by6 unsigned bits, we get signed
fixed point result, where6
bits before the decimal point and8 bits after. From necessity─
my accuracy depends on the methods used.
Wide multiplication-division, which in iso─
Bills are scattered in the press, usually not needed
- enough rough calculations from the table
or for 5-6 passes of the cycle. It also happens
that instead of multiplication, addition is more profitable
cycle - the factors are so small in reality
are used (this was the case in tying the landfill
in The Link).Unfortunately, the required accuracy
often found out from the results of experiments─
ntov, when everything has already been written. For example, in
Wolf 48 was 16-bit math first, 
then it was replaced with 8-bit. Better where─
make a margin for accuracy, but have it on hand
and a radically fast method, with precision
which it will be possible to adjust the effect (and
it happens).

   When calculation methods are selected, look at
how much register is used at what stage─
ditch and how much should be carried at this time
registers for the next steps. For example:
;# lower scanline stack generator 
;(8 registers), carry 7 (U1[1],V1[1], 
;dU13[2],dV13[2],Y) + 2 (dX12[2]) 
;=9 registers - just enough (17) 
   Over the years I have prepared up to
dozens of code options for typical tasks
(scanline, innerloop tmap, multiplication, dele─
nie, etc.), so I know how much registration─
I need it at key stages.
   If there are no registers at some stage
enough, change the calculation scheme or replace
carried registers to memory or stack.

   Only after that do we write between these
code comments. The code will be with the question─
in real characters instead of registers: for example,
with commands likeld a,?1 . Not necessary
implement all stages at once, the main thing is
last stages.
   Each inserted fragment contains
At the end there is a comment with the number of measures. Usually
I take fragments fromaccumulated collection,
this number is already there. Even if the code is but─
first, then count by fours and sevens (or
by fours followed by subtraction of ones─
check) does not take long.

   Then from the end of the program we start defining
divide which specific registers are required:
  - we put registers in the last stage
  - further before this stage we describe
required state of the input registers:
;c=parameter such and such 
;hl'=parameter such and such 
;lx=parameter such and such 
etc.
  - in the stage that stands in front of him, instead─
We use the existing question marks onld
a,c?1, etc. and, if necessary, write ─
ZK for transferring registers between these
in two stages. Sometimes the tail of one stage
cut off along with the head of the next one,
so it turns out to be a negative overhead
for a connection between stages!
  - if problematic plugs appear
or suboptimality (for this not even on─
before replacing all question marks, both─
clearly visible earlier), then we try to rewrite
the last stage with other registers. Otherwise
continue from bottom to top in the same sequence─
details: we fill in the registers, write down
state of the registers, replace the questioner─
new signs in the previous stage and write connections─
ku.
   Suboptimality is, for example, besto─
deftly transferring numbers from register to
register, localPUSH-POP or local
patches, command NEG (usually it can be replaced─
thread with a different order of addition and subtraction
or changing the table), reuse─
tion of numerical constants, etc.
   I highlight them in the source code with a line shift
to the right so you can quickly find
eyes and evaluate how suboptimal the code is─
linen

                  * * *

   Unfortunately, when debugging, sometimes finding out─
It is assumed that at the planning stage it was allowed
error. Then you have to make crutches,
which violate optimality.  But when
the next implementation of the same task is already possible─
It will be important to take this error into account.
   There are several bugs in this engine
predecessors. In addition to the approach itself
clipping, see for example:
  - how the screen is stored (its location
designed for convenient clipping); 
  - how objects rotate and how they rotate─
tires with compensation for forward distortion─ 
(previously you had to rotate the 
every vertex with complete accuracy!); 
  - how sorting is implemented (linear
pigeon-hole sort with minimal transfer 
data and a compromise number of levels 
Z); 
  - how repeating objects are written
directly in code... 
   ...but a new iteration will be needed
writing to allow objects to be sized─
rum is larger than a unit cube. However, games
already doCan. You just need to tie it
engine for NedoLang :)

   The demo program is in the─
lodgement, and its sources are in the archive. Management─
It’s simple - the arrows5678 move the camera
by coordinates, and the mouse rotates it. With the buttonF
you can turn off the floor and ceiling.0 - pause.
There is no check for exiting the core, but
the engine is completely incapable of working outside of it─
counted
   Yes, this is not Total Eclipse yet :)

 A
 B
 B
 G
 D
 E
 F
 Z
 And
 Y
 K
 L
 M
 N
 Oh
 P
 R
 C
 T
 U
 F
 X
 C
 H

   Active zone size #280(x) * #280(y)
* #100 (z). This size is currently set in
floor.asm to display the floor and ceiling.
But it's not just about the field and ceiling - chapters─
It’s clear that with such dimensions there will be no over─
complete calculations. You can only increase it a little─
set height (z). The core can
located anywhere in space
XYZ, because we work with coordinates
relative to the camera.
   For comparison, in the Total Eclipse engine
zone size -8192 *4096 * 8192, but with
this objects can only be placed with sha─
hom in128 units (along the y-axis - in increments of 64):
https://en.wikipedia.org/wiki/Freescape
Maximum object size #3f (from
edge to edge), and on large objects
distortions already appear if you approach
close to him. Accuracy of calculations of vertices relative─
corresponds to+-1 unit, but the polygon size
in 2 units you risk not seeing
8-bit visibility control(VISIBILITY16=
=0).

   Objects are described inЗdmodel.asm . Objects
can contain polygons and lines. Everyone
the object is bound to the rotation procedure -
visibility checks - drawing (via
drawedges.asm and/ordrawfaces.asm ), but─ 
referred specifically to objects of its class. Except
procedures with ready-made objects (in
rotmodel.asm ), there is also a “universal”
ROTVB (inrotate.asm ), which is enough
pass lists of vertices, edges and polygons.
It can only have the coordinates of the vertices
only0 or +-31... However, you can compose─
and completely universal. She will be in
times slower than a ready-made procedure
object. It was supposed to generate process─
fools for objects.

   Inrotate.asm there is also a perspect procedure─
active correction of object verticesdiv8x. On
input it has rotated coordinates ver─
tires, object coordinates on the screen and its
zoom (inline patch), but returns the screen─
new coordinates.

 sortobj.asm - you think this is a procedure
sorting by depth?  :) Actually
There is no separate sorting in the engine at all.
It is half integrated into the additive
object to the list for output(DOOBJ), half─
the fault is in displaying a list of objects(sortobjpop).
And both of these procedures are in this module,
along with checking whether the object is in the ec─
wounds and selecting the desired zoom. Of course
objects are displayed in the wrong order
are added by torus :) Moreover, all procedures
processingobjects (see above) are finished─
with the teamjp sortobjnext, so as not to tra─
thick stack. The fastest cart is used─
possible sorting method for limited
depth range. It's called Pigeonhole
sort (a degenerate case of Radix sort ). He 
works linearly with the number of objects, then
thereO(n), and with a very small coefficient─
ficient. Yes, it happens! :) Objects, co─
corresponding to each depth (now128
depths:SORTLEVELS=128) fall into the section─
list. The lists are still being cleaned small
piece of code at the beginning mainloop. At the end
eventually the cleanup code will also be transferred to
this module.

   The scene itself is now described directly─
exactly the code inmain.asm . This code is generated─
it’s easy to translate, convert it into tables too
no problem.

 rotobj.asm - floor rotation procedure─
high precision, needed to determine the field─
movement of an object on the screen. Called for
all objects, and for half of them invisible─
of all objects there is an exit from the middle─
us. More precisely, it’s not even a procedure, but a poppy─
grewADDCAM_ROT.

 rotmatrix.asm - composition procedure
rotation matrices of object vertices and tables
"serifs" for quick recalculation of vertices.
For each combination of axes,31 are built for─
section, not counting zero, which takes into account signs
just corresponds to the maximum size─
ru object#3f (see above).
 This is a really very fast rotator, with─
based on the LVD rotator in "in─
shaggy bagel" (Mission Highly demo
improbable). You can even turn off the roll, 
so that there is rotation in only two axes.
But this rotator is called only when
when an object is encountered that is not rotated
just like the previous ones.

   The screen buffer is stored in columns.
Now it’s being displayed through the clock for speed─
urgently, but you can finish it until it’s complete
full screen output.  Withdrawal procedure
The buffer on the screen lies indisplay.asm. You can
set it, for example, to motion blur
(NOISECLS=0; 0=clearing, 1=noise, 2=skip
bytes). 
   The engine can be easily converted to another
screen format (chunks or color per dot)
replacing modules drawedges, drawfaces anddisplay. It was supposed to be added as a mini─
mum chunk engine from New View 48K with no─
which by finishing.  See catalog
mars with different settings for this chunk
engine - color/b&w, different textures, sizes
screen, chunk sizes and a couple of filters.
   All the necessary tables are calculated in Basie─
ke. Sources are also included.

   Unfortunately, the engine had to be abandoned
in connection with the NedoLang project. I suggested
it to a couple of demomakers, but so far no one is in favor
didn't take it. So I decided to publish─
write it in the journal in its current form. He's still
still buggy on large objects, but in general
suitable at least for a demomaker─
for cultural purposes and for tearing out pieces of code.

   If anyone is interested in practical
using the engine, write! Let's finish... 
It will be possible to publish the series in parallel 
articles about news in the filling of the engine, as in 
Commodore's newspaper C Hacking. In the meantime, in 
in the next part we will outline some pieces 
codes that exist now... but a warning─ 
I promise - the text will not be for the faint of heart :)