MS-DOS 3D engine

3DOMS, the 3-Dimensional Object Management System, is a 3D engine for MS-DOS featuring flat-shaded triangles and a scene hierarchy, with rendering via camera distance object sorting.

Objects are defined as abstract forms, and these are then instantiated in a scene graph using a position and an orientation.

Numbers are fixed point, with 8 bits after the point. Every co-ordinate is a 32-bit double word in 24.8 format, from the corners of faces to the positions of objects, and angles are bytes, with 256 steps to a turn.

The tester

The demo at the top is the tester, TESTER.ASM. It makes one form, a box with a fin on its side, and four boxes that share it. The boxes sit on a turntable, which turns until Esc is pressed.

The 3D system is kept in its own file, and the tester includes it at the top:

.MODEL small
.STACK 1024
.386

JUMPS



;-------- The 3D system.

.CODE

INCLUDE 3DOMS.INC

The code to make the scene:

    ;  Put the scene in front of the camera.
  mov ah, 10h
  mov si, offset _view
  mov es, _universe
  int 3Dh
  jc tester_error

    ;  Make the turntable in the universe.
  mov ah, 1Bh
  mov si, offset _origin
  mov es, _universe
  int 3Dh
  jc tester_error
  mov _turntable, ax

    ;  Make the box form, with the body and the fin as its two shapes.
  mov ah, 1Ch
  mov si, offset _origin
  int 3Dh
  jc tester_error
  mov _form, ax

  mov ah, 1Dh
  mov si, offset _bodycentre
  mov es, _form
  int 3Dh
  jc tester_error
  mov es, ax
  mov si, offset _body
  mov cx, 12
  call tester_faces
  jc tester_error
  ...

    ;  Make the four boxes on the turntable, move each one to its place and
    ; give it the box form.
  mov si, offset _boxes
  mov cx, 4
tester_box:
  push si
  mov ah, 1Bh
  mov si, offset _origin
  mov es, _turntable
  int 3Dh
  pop si
  jc tester_error
  mov es, ax
  mov ah, 10h
  int 3Dh
  jc tester_error
  mov ah, 11h
  mov bx, _form
  int 3Dh
  jc tester_error
  add si, 16
  loop tester_box

The camera is at the origin, so the first thing the tester does is move the universe, and everything in it, 144 units in front of it. The turntable is an object in the universe, and the four boxes are objects in the turntable, so turning the turntable turns all four. The boxes' own positions spread them out on it. The scene's data:

  ;  The centers of the body and the fin.  The body and the fin touch at
  ; x = 16, and the centers are 8 either side of it, so whichever is nearer
  ; the camera is always drawn last.
_bodycentre	dd 0800h, 0, 0
_fincentre	dd 1800h, 0, 0

  ;  The universe: position, angles and rotation order.  It puts the scene
  ; 144 units in front of the camera.
_view		dd 0, 0, 9000h
		db 00h, 00h, 00h, RORDER_XYZ

  ;  The turntable: position, angles and rotation order.  The angles go up a
  ; little each frame.
_turn		dd 0, 0, 0
_turn_rx	db 20h
_turn_ry	db 00h
_turn_rz	db 00h
		db RORDER_ZYX

  ;  The four boxes: position, angles and rotation order.
_boxes		dd -2000h, -2000h, -0C00h
		db 00h, 00h, 00h, RORDER_XYZ
		...

  ;  The body: 12 faces, two on each side, each in a different grey from the
  ; standard palette.  Each face is its colour and then its three corners.
_body		db 1Fh
		dd -1000h, 1000h, -2000h,  1000h, 1000h, -2000h,  1000h, -1000h, -2000h
		db 1Eh
		dd 1000h, -1000h, -2000h,  -1000h, -1000h, -2000h,  -1000h, 1000h, -2000h
		...

The body is a box 32 units across and 64 long, and each of its faces is a different grey, colours 14h to 1Fh of the standard palette. The fin is a 16-unit cube on the side of the body, in the reds and yellows from 28h to 2Ch. The side of the fin that's against the body can never be seen, so it has no faces.

The body's centre isn't in the middle of the body. It's 8 units along, as far from where the body and the fin touch as the fin's centre is on the other side, which is what keeps them in the right order. Why is in placing centres.

Each frame, the tester adds 1, 2 and 4 to the turntable's angles and hands them to function 10h, then renders the universe into a buffer:

tester_loop:
    ;  Clear the buffer to stripes of colours 1 and 0.
  mov es, _buffer
  xor di, di
  mov cx, 16000
  mov eax, 00010001h
  cld
  rep stosd

    ;  Turn the turntable a little more each frame.
  add _turn_rx, 1
  add _turn_ry, 2
  add _turn_rz, 4
  mov ah, 10h
  mov si, offset _turn
  mov es, _turntable
  int 3Dh
  jc tester_error

    ;  Render the universe into the buffer.
  push ds
  mov ah, 20h
  mov es, _buffer
  mov ds, _universe
  int 3Dh
  pop ds
  jc tester_error

    ;  Wait for the vertical retrace, then copy the buffer to the screen.
  mov dx, 03DAh
tester_retrace:
  in al, dx
  test al, 08h
  jz tester_retrace
  push ds
  mov ds, _buffer
  xor si, si
  mov ax, 0A000h
  mov es, ax
  xor di, di
  mov cx, 16000
  rep movsd
  pop ds

    ;  Carry on until Esc is let go.
  in al, 60h
  cmp al, 81h
  jne tester_loop

Clearing the buffer to stripes of colours 1 and 0 makes the blue background, and the finished frame is copied to the screen after the vertical retrace. Port 60h holds the scan code of the last key that went down or up, so the tester just watches it for Esc being let go.

The heap

Everything in a scene lives on a heap of 32-byte cells, which 3DOMS asks DOS for when you log on. It asks for the most cells the program wants, and if DOS doesn't have that many, for whatever is left, as long as that's at least the minimum. Then it marks every cell free and makes the first one the universe.

A cell is two paragraphs, so it can be addressed by a segment on its own, with every field at a fixed offset from 0. Structures are passed around as segments in registers, and each one starts with the same few fields:

_MAGIC		equ 0000h	;  (B) Magic - indicates type of structure.
_NUM		equ 0001h	;  (B) Number of child structures.
_PTR		equ 0002h	;  (W) Segment of first child in linked list.
_NEXT		equ 0004h	;  (W) Segment of next structure in list, or 0.
_PARENT		equ 0006h	;  (W) Segment of parent structure.
_CENTRE		equ 0008h	;  (W) Segment of center point.

The cells form a tree, with the universe at the top. Each structure points down to its first child with _PTR and counts its children in _NUM, and the children are a list joined by _NEXT, with 0 at the end. Every child points back up to its parent with _PARENT, and new children go at the front of the list. Forms are the one exception: they hang off no parent, and objects point at them instead.

The first byte, the magic, says what's in the cell: P, F, S, M, O or U for a point, face, shape, form, object or universe, 0 for a free cell, and FFh for a cell that has been taken but not filled in yet.

Taking a cell is a walk from the start of the heap to the first magic of 0. The cell is cleared to zeros and marked as taken, and the count of free cells goes down by one. Each create function knows how many cells it can need, two for an object, form or shape and four for a face, and checks there are that many free before it starts, so nothing is ever left half made.

Every segment that's passed in is checked before it's used. It has to be inside the heap, on a cell boundary, and hold the right kind of structure:

int3D_checkcell:
  push ax
  push ds
  cmp ax, _3doms_heapseg
  jb int3D_checkcell_bad
  cmp ax, _3doms_heapend
  jae int3D_checkcell_bad
  mov ds, ax
  sub ax, _3doms_heapseg
  test al, 01h
  jnz int3D_checkcell_bad
  cmp ds: [_MAGIC], dl
  jne int3D_checkcell_bad
  pop ds
  pop ax
  clc
  ret
int3D_checkcell_bad:
  pop ds
  pop ax
  stc
  ret

So passing a shape where a form is expected, or any old number, gets an error back instead of a corrupted heap. Every list is also walked with its count, so a broken list can't send anything round in circles.

Deleting frees cells by setting their magic back to 0. An object can only be deleted once it's empty, and a form only once no objects are using it, and then everything in it goes too: its shapes, their faces and centres, and its points. That's done in two passes over the form, the first only checking, so that none of it is freed unless all of it can be. Function 00h says how big the heap is and how many cells are free.

Scene format

A scene is a tree of structures, one to a cell. The documentation at the top of the file draws it like this:

  Point <- Face <- Shape <- FORM <- Object <- Object ... <- UNIVERSE

Points, faces, shapes and forms describe what something looks like, and objects say where it is. The documentation explains it with planes:

  Shapes and faces are constants - if you want to have more than one plane
flying around, as long as all the planes look the same, they can all use the
same shapes and faces.  A form is basically a descriptor for a linked list of
shapes, and it keeps the list of points its faces use.  When you create a new
object, you give it a form, which will be used when the object is drawn.

That's how the tester draws four boxes from one form. The tester's whole scene takes 55 cells:

Here are the structures from the top of the tree down.

Universe

There's only one universe, the heap's first cell, made when you log on. It holds the objects at the top of the scene, and it's where rendering starts. It has a position and angles like an object, which place the whole scene in front of the camera.

U_MAGIC		equ 0000h	;  (B) Magic byte.
U_NUM		equ 0001h	;  (B) Number of objects in it.
U_PTR		equ 0002h	;  (W) Segment of first object in linked list.
U_X		equ 0010h	;  (D) Transformations.
U_Y		equ 0014h
U_Z		equ 0018h
U_RX		equ 001Ch	;  (B) Rotation about the axes.
U_RY		equ 001Dh
U_RZ		equ 001Eh
U_RORDER	equ 001Fh	;  (B) Order of rotations.

Object

An object puts a form into the scene, with a position, three angles and a rotation order. How the angles and the order are used is in rotation. Objects can also hold other objects, which move and turn with them. As the documentation puts it, "A plane may be an object with the body as its form, holding some wheel and flap objects, as the wheels and flaps are not fixed in position on the plane."

O_MAGIC		equ 0000h	;  (B) Magic byte.
O_NUM		equ 0001h	;  (B) Number of objects inside it.
O_PTR		equ 0002h	;  (W) Segment of first object in linked list.
O_NEXT		equ 0004h	;  (W) Segment of next object, or 0 if none.
O_PARENT	equ 0006h	;  (W) Segment of object or universe it's in.
O_CENTRE	equ 0008h	;  (W) Segment of center point.
O_FORM		equ 000Ah	;  (W) Segment of form, or 0 if none.
O_LEVEL		equ 000Ch	;  (B) How deep it is - 1 if in the universe.
O_X		equ 0010h	;  (D) Transformations.
O_Y		equ 0014h
O_Z		equ 0018h
O_RX		equ 001Ch	;  (B) Rotation about the axes.
O_RY		equ 001Dh
O_RZ		equ 001Eh
O_RORDER	equ 001Fh	;  (B) Order of rotations.

The centre is what the object is sorted by, against the other things in the object it's in, and function 12h moves it. The level counts how deep it is, so objects can be put inside each other 8 deep and no further. Objects are made, moved and deleted with functions 1Bh, 10h and 18h. A new object has no form until function 11h gives it one.

Form

A form is a list of shapes, with a centre. When an object is drawn, its form is sorted by the form's centre against the objects inside it. A form also keeps the list of points its faces use, and counts the objects using it, so it can't be deleted while it's still in the scene.

M_MAGIC		equ 0000h	;  (B) Magic byte.
M_NUM		equ 0001h	;  (B) Number of shapes in form.
M_PTR		equ 0002h	;  (W) Segment of first shape in linked list.
M_CENTRE	equ 0008h	;  (W) Segment of center point.
M_NUMPTS	equ 000Ah	;  (B) Number of points in form.
M_PTS		equ 000Bh	;  (W) Segment of first point in linked list.
M_USERS		equ 000Dh	;  (W) Number of objects which use this form.

Forms are made and deleted with functions 1Ch and 19h.

Shape

A shape is a list of faces with a centre. It has to be convex, so that leaving out the faces that face away is all it takes to draw it properly. Anything that isn't convex is split into several shapes, like the tester's body and fin, and the centres are there so the shapes can be drawn from the furthest forward. Where to put them is in placing centres.

S_MAGIC		equ 0000h	;  (B) Magic byte.
S_NUM		equ 0001h	;  (B) Number of faces.
S_PTR		equ 0002h	;  (W) Segment of first face in linked list.
S_NEXT		equ 0004h	;  (W) Segment of next shape, or 0 if none.
S_PARENT	equ 0006h	;  (W) Segment of parent form.
S_CENTRE	equ 0008h	;  (W) Segment of center point.

Shapes are made with function 1Dh.

Face

Faces are always triangles, "To avoid any programming difficulties on my part and to make rendering as fast as possible". A face is a colour and the three points at its corners. Seen from the front, the corners go anticlockwise.

F_MAGIC		equ 0000h	;  (B) Magic byte.
F_NEXT		equ 0004h	;  (W) Segment of next face, or 0 if none.
F_PARENT	equ 0006h	;  (W) Segment of parent shape.
F_COL		equ 0008h	;  (B) Colour of face (palette index).
F_P1		equ 000Ah	;  (W) Segments of corner points.
F_P2		equ 000Ch
F_P3		equ 000Eh

Faces are made with function 1Eh.

Point

Points are managed behind the scenes. A face's corners are given as co-ordinates when it's made, and each one is looked up in the form's list of points. A new point is only made if it isn't there already, so the corner of a box is one point shared by all the faces that meet there:

int3D_findpoint_loop:
  mov ds, ax
  mov edx, cs: [si]
  cmp edx, ds: [P_X]
  jne int3D_findpoint_next
  mov edx, cs: [si+4]
  cmp edx, ds: [P_Y]
  jne int3D_findpoint_next
  mov edx, cs: [si+8]
  cmp edx, ds: [P_Z]
  je int3D_findpoint_end
int3D_findpoint_next:
  mov ax, ds: [P_NEXT]
  loop int3D_findpoint_loop

That's why the tester's body only needs 8 points for its 12 faces. As the documentation says, "A point shared between many faces has all its calculations done once per form, not once per face." Each point keeps where it went on the screen the last time its form was drawn, ready for the faces to use:

P_MAGIC		equ 0000h	;  (B) Magic byte.
P_OFF		equ 0001h	;  (B) 1 if it couldn't be put on the screen.
P_NEXT		equ 0004h	;  (W) Segment of next point in form, or 0.
P_PARENT	equ 0006h	;  (W) Segment of form, shape or object.
P_X		equ 000Ch	;  (D) Co-ordinates.
P_Y		equ 0010h
P_Z		equ 0014h
P_SX		equ 0018h	;  (W) Where it went on the screen.
P_SY		equ 001Ah

The centres of objects, forms and shapes are points too, each in a cell of its own.

Maths

There are no general maths routines. Each operation is written out where it's needed, mostly in the rotations, the projection and the triangle filler.

Number formats

Every number with a fraction has 8 bits after the point, so 100h is 1.0. What changes is how many bits there are in front of the point, depending on where the number is kept:

A point goes through them in order as it's drawn:

1. It's loaded into ESI, EDI and EBP as x, y and z.
2. It's rotated by its object's angles. Each multiply by an 8.8 sine or cosine makes a 64-bit product with 16 bits after the point, which is shifted straight back to 24.8.
3. The object's position is added, 24.8 to 24.8. Then the same again for the object it's in, and so on up to the universe.
4. It's projected, which is a multiply and a divide, and comes out in whole pixels.
5. From there on, the cross product and the edges of each triangle are whole numbers.

The co-ordinates are kept under 32768.0 so that nothing can overflow on the way. Even 8 objects deep, with every position as far out as it can go, a point stays well inside 32 bits.

Adding

Fixed-point numbers with the same number of bits after the point add and subtract like plain integers. The corners and the positions are both 24.8, so moving a point is just an ADD for each co-ordinate:

  add esi, dword ptr _3doms_tstack[bx]
  add edi, dword ptr _3doms_tstack[bx+4]
  add ebp, dword ptr _3doms_tstack[bx+8]

Multiplying

A 24.8 co-ordinate times an 8.8 sine or cosine gives a 64-bit product in EDX:EAX with 16 bits after the point. Shifting it right by 8 brings it back to 24.8. Rather than doing a 64-bit shift, mov al, dl copies the low byte of EDX over the bottom byte of EAX, which is about to be thrown away anyway, and ror eax, 8 rotates it round to the top. That leaves bits 8 to 39 of the product in EAX, which is the 24.8 answer:

  mov eax, _3doms_cos[bx]
  imul ecx
  mov al, dl
  ror eax, 8

Dividing

Division is used for perspective. The 24.8 co-ordinate is multiplied by the eye distance, 128.0, which leaves a 64-bit product in EDX:EAX with 16 bits after the point. That's just what IDIV divides, so nothing is lost in between. Dividing by the 24.8 depth takes 8 of those bits off again, and an arithmetic shift right by 8 drops the rest, leaving whole pixels:

  mov ecx, SCR2EYE
  mov eax, esi
  imul ecx
  idiv ebp
  sar eax, 8

A divide that overflows stops the machine, so the point is checked first. How is in projection.

Rotation

Each rotation is the usual pair of multiplies and an add or subtract for each co-ordinate, each multiply done as above. The angle is a byte, so it's turned into an offset in the sine table by shifting it left by 2, since each entry is 4 bytes. An angle of 0 doesn't change anything, so it's skipped:

int3D_rotate_x:
  or al, al
  jz int3D_rotate_x_end
  push bx
  push ecx
  push edx
    ;  Calculate offset in sine table.
  xor bx, bx
  mov bl, al
  shl bx, 2

    ;  NY = Y*cos(AL)-Z*sin(AL)
  mov ecx, edi
  mov eax, _3doms_cos[bx]
  imul ecx
  mov al, dl
  ror eax, 8
  mov edi, eax
  mov eax, _3doms_sin[bx]
  imul ebp
  mov al, dl
  ror eax, 8
  sub edi, eax
  ...

The y and z rotations are copies of it with the axes changed. Objects and the universe each turn about all three axes, in the order their rotation order byte gives. It's the bottom three bits: bit 0 means start with y, bit 1 means start with z, and bit 2 swaps the other two round, so RORDER_ZYX is 110b. Bits 0 and 1 can't both be set, which leaves six orders, and function 10h won't take any other.

Sines and cosines

Sines are 8.8 values, where 100h means 1, but each one is stored as a 32-bit double word, so it can be multiplied straight against a 24.8 co-ordinate in a 32-bit register. The cosine table doesn't need space of its own: a cosine is the sine 90 degrees on, so the cosine table starts 64 entries into the sine table, which carries on for another 256:

_3doms_sin	dd 000000000h, 000000006h, 00000000Ch, 000000012h  ;  0 deg
		dd 000000019h, 00000001Fh, 000000025h, 00000002Bh
		dd 000000032h, 000000038h, 00000003Eh, 000000044h
		...
_3doms_cos	dd 000000100h, 000000100h, 0000000FFh, 0000000FFh  ;  90 deg
		dd 0000000FFh, 0000000FEh, 0000000FDh, 0000000FCh
		...

Distances

Sorting needs to know how far things are from the camera. The distance itself would need a square root, but the distance squared puts things in the same order, and it's three multiplies and two adds. Each square is a 64-bit product, so the total is kept as 64 bits too, in ECX:ESI, with ADD for the low halves and ADC for the high halves:

    ;  Distance squared = x*x + y*y + z*z, into ECX:ESI.
  mov eax, esi
  imul eax
  mov esi, eax
  mov ecx, edx
  mov eax, edi
  imul eax
  add esi, eax
  adc ecx, edx
  mov eax, ebp
  imul eax
  add esi, eax
  adc ecx, edx

Cross product

Whether a face is towards you or away comes from the cross product of two of its edges on the screen. Only the z part is needed, which is two multiplies and a subtract, and only its sign matters. The screen co-ordinates are sign-extended to 32 bits first, so the products can't overflow however big the triangle is:

  movsx eax, _tri_x2
  movsx ecx, _tri_x1
  sub eax, ecx
  movsx ecx, _tri_y3
  movsx edx, _tri_y2
  sub ecx, edx
  imul eax, ecx
  ...

How it's used is in faces that face away.

Interpolating

On each row, the triangle filler works out where an edge is. That's the edge's change in x, times how far down the edge the row is, divided by the edge's height. The multiply makes a 64-bit product, so the divide always fits:

  movsx eax, _tri_x3
  movsx ecx, _tri_x1
  sub eax, ecx
  movsx ecx, _tri_y
  movsx esi, _tri_y1
  sub ecx, esi
  imul ecx
  movsx ecx, _tri_y3
  sub ecx, esi
  idiv ecx
  movsx ecx, _tri_x1
  add eax, ecx
  mov ebx, eax

Rendering

Function 20h draws the universe as if it were an object, and everything follows from that:

1. Drawing an object puts its position and angles on the transformation stack.
2. Its own form and every object in it are put in a list by how far their centres are from the camera, and drawn furthest first. An object in the list is drawn the same way, with everything in it, starting again from step 1.
3. Drawing a form projects every one of its points onto the screen, once.
4. Then its shapes are put in a list by their centres and drawn furthest first.
5. Drawing a shape draws each of its faces. A face is left out if one of its corners couldn't be put on the screen, or if it's facing away.
6. Otherwise it's filled with the face's colour.

The drawing calls itself with plain CALLs, one level for each object, so rendering switches to a 2k stack of 3DOMS's own first. However deep the scene goes, there's always room.

The transformation stack

Each object's position and angles are 16 bytes, and drawing an object copies them onto the transformation stack, on top of those of the object it's in, and so on up to the universe:

  shl bx, 4
  push cs
  pop es
  mov si, O_X
  lea di, _3doms_tstack[bx]
  mov cx, 8
  rep movsw
  inc _3doms_tdepth

A point is then taken through the stack from the top down. At each level it's rotated by the angles and moved by the position, so it starts in its own object's terms and comes out the way the camera sees it:

int3D_transform:
  push bx
  push cx

  mov cx, _3doms_tdepth
  mov bx, cx
  shl bx, 4
  jcxz int3D_transform_end
int3D_transform_level:
  sub bx, 16
  call int3D_rotate
  add esi, dword ptr _3doms_tstack[bx]
  add edi, dword ptr _3doms_tstack[bx+4]
  add ebp, dword ptr _3doms_tstack[bx+8]
  loop int3D_transform_level

int3D_transform_end:
  pop cx
  pop bx
  ret

For one of the tester's boxes, there are three levels: the box's own position, the turntable's angles and the universe's position.

Projection

The camera is at the origin, looking along the z axis, with x to the right and y down the screen. Nothing is moved in front of it for you, which is why the tester moves the universe forward. Projecting is one formula, multiplying by the eye distance and dividing by the depth:

    ;  SX = (scr2eye*X) / Z, from the center of the screen.
  mov ecx, SCR2EYE
  mov eax, esi
  imul ecx
  idiv ebp
  sar eax, 8
  add ax, VIEW_CX
  mov ds: [P_SX], ax

The eye distance is 128.0, so at a depth of 128 one unit across is one pixel. Take a point 16 units right of the centre of the tester's scene, which is 144 units in front of the camera. Its x is 1000h and its depth is 9000h. The multiply makes 800 0000h, the divide by 9000h makes E38h, and the shift leaves 0Eh, so it's drawn 14 pixels right of the centre, in column 174.

Before any of that, the point is checked, and if it fails it's marked as off the screen and any face using it is left out:

• It has to be at least 1.0 in front of the camera. Anything closer, or behind, can't be divided by.
• It can't be more than 16 times as far out to the side, or up or down, as it is in front. That keeps the answer within 2048 pixels of the centre, so the divide can't overflow and the triangle filler always gets numbers it can handle.

    ;  It has to be at least NEAR_Z in front of the camera.
  cmp ebp, NEAR_Z
  jl int3D_project_end

    ;  And no more than 16 times as far to the side, or up or down, as it is
    ; in front, so the divides can't overflow.
  mov eax, esi
  cdq
  xor eax, edx
  sub eax, edx
  shr eax, 4
  cmp eax, ebp
  ja int3D_project_end

Drawing furthest first

There's no depth buffer, so things have to be drawn from the back to the front, with nearer things painted over further ones. The objects in an object can be in front of each other in any order, depending on which way the scene is turned, so the order is worked out again every time the object is drawn.

Each object in it has its centre taken through the transformation stack, with its own position and angles on the top, and its distance squared from the camera goes in the draw list with its segment. The object's own form goes in the same list, by the form's centre.

Then the list is drawn by picking the furthest entry that hasn't been drawn yet, again and again, until there are none left:

int3D_takefurthest_loop:
  cmp si, _3doms_sortptr
  jae int3D_takefurthest_end
  cmp word ptr cs: [si+SORT_SEG], 0
  je int3D_takefurthest_next
  or di, di
  jz int3D_takefurthest_take
  mov edx, cs: [si+SORT_HI]
  cmp edx, ecx
  ja int3D_takefurthest_take
  jb int3D_takefurthest_next
  mov edx, cs: [si+SORT_LO]
  cmp edx, ebx
  jbe int3D_takefurthest_next
int3D_takefurthest_take:
  mov ebx, cs: [si+SORT_LO]
  mov ecx, cs: [si+SORT_HI]
  mov di, si
int3D_takefurthest_next:
  add si, SORT_SIZE
  jmp int3D_takefurthest_loop

The one it finds has its segment set to 0, so it's skipped next time round. That's a selection sort, done as it goes. An object holds at most 127 objects and a form, so it's quick enough, and it needs no room beyond the list itself.

The list is a stack too. Each object's entries go on the end, and when one of them is an object, its own entries go on after them while it's drawn, and come off again when it's finished. A form's shapes are sorted the same way, in a list of their own, so the tester's fins are drawn in front of their bodies or behind them depending on which is nearer.

Sorting within the hierarchy

Things are only ever sorted against the others in the same list: the objects in one object, along with its form, or the shapes in one form. An object is drawn all in one go, with everything inside it, at the place its own centre puts it among the things next to it. Nothing inside it is ever sorted against anything outside it.

For the tester, that means three separate sorts each frame. The universe's list has just the turntable in it. The turntable's list has the four boxes, sorted by their centres. And each box's form has a list of two shapes, the body and the fin. A box's fin is never compared with another box's body: the whole of the further box, fin and all, is drawn before the whole of the nearer one.

That keeps the sorting cheap, since every list is short, and it's right as long as the objects next to each other don't overlap in space. Parts that can come in front of each other should be in the same object, and if an object is built from other objects, its centre decides where all of them go among the things around it.

Placing centres

Two centres are the same distance from the camera anywhere on the plane halfway between them, and one or the other is nearer everywhere else. So which side of that plane the camera is on decides which of the two is drawn first.

That makes it simple to get two parts that touch along a flat side the right way round. Put their centres the same distance either side of where they touch, and the halfway plane is exactly the plane they touch on. From anywhere on the body's side of it, the body is nearer and is drawn last, and from anywhere on the fin's side, the fin is.

In the tester the body and the fin touch at x = 16, so the fin's centre is at 24 and the body's is at 8. With the camera 60 units in front of them at x = 15, just on the body's side, the distances squared are 7² + 60², 3649, to the body's centre and 9² + 60², 3681, to the fin's, so the fin is drawn first and the body over it. Move the camera to x = 17 and the numbers swap round.

If the body's centre were in the middle of the body, at 0, the halfway plane would be at x = 12 instead. From anywhere between 12 and 16 the fin would be drawn last, over the body that's in front of it.

The same goes for objects next to each other in an object, and for an object's form against the objects in it. Centres can be given when things are made, and moved afterwards with function 12h. With more than two parts, each pair has its own halfway plane, so it's best when each pair is separated by theirs, as the tester's four boxes are.

Faces that face away

These are found on the screen, after projecting. The cross product of two edges says which way round the corners go, and a face whose corners don't go anticlockwise is facing away from you, or edge on:

    ;  Calculate cross vector product - if it isn't -ive then the face is
    ; facing away, or edge on - don't draw it.
  movsx eax, _tri_x2
  movsx ecx, _tri_x1
  sub eax, ecx
  movsx ecx, _tri_y3
  movsx edx, _tri_y2
  sub ecx, edx
  imul eax, ecx
  movsx ecx, _tri_x3
  movsx edx, _tri_x2
  sub ecx, edx
  movsx edx, _tri_y2
  movsx esi, _tri_y1
  sub edx, esi
  imul ecx, edx
  sub eax, ecx
  jge int3D_drawface_nodraw

This is why shapes have to be convex. With the far side of a convex shape left out, nothing that's left can overlap, so its faces can be drawn in any order.

Filling triangles

The triangle filler sorts the three corners by y, with three compare-and-swaps. Then it goes down the rows from the first corner to the last, but only the rows that are on the screen. On each row it works out where the long edge is, from the first corner to the last, and where the short edge is, from the first corner to the middle one above the middle corner, and from the middle one to the last below it. The two ends are put in order and clipped to the screen, so a face that goes off the edge is cut off there.

The rows are filled with STOS, four pixels at a time where it can. A row starts with one byte if its length is odd, then one word if what's left isn't a multiple of four, then double words. The commented-out rep stosb at the top is the simple version it replaced:

int3D_hline:
  jcxz int3D_hline_end

;  rep stosb		;  Slow but safe while testing rendering functions.
;  ret

  shr cx, 1
  jnc int3D_hline_nobyte
  stosb
int3D_hline_nobyte:
  jcxz int3D_hline_end
  mov ah, al
  shr cx, 1
  jnc int3D_hline_noword
  stosw
int3D_hline_noword:
  jcxz int3D_hline_end
  push ax
  rol eax, 16
  pop ax
  rep stosd
int3D_hline_end:
  ret

When something is wrong

Every structure is checked as it's drawn, the same as when it's passed in. If one is wrong, rendering stops and returns the error, however deep it was at the time. Rather than each level having to pass the error back up, the stack pointer at the start of drawing is kept, and the error jumps straight back to it:

int3D_drawstart:
  mov _3doms_failsp, sp
  call int3D_drawobject
  clc
  ret

int3D_drawfail:
  mov sp, _3doms_failsp
  stc
  ret

The interface

Everything is done through a software interrupt, INT 3Dh, once the program has logged on. Logging on is a normal call, with the smallest and largest heap the program will accept, in 32-byte cells:

    ;  Log on, asking for a heap of between 8k and 32k.  The universe is the
    ; first cell of the heap.
  mov bx, 0100h
  mov dx, 0400h
  call logon_3doms
  jc tester_nomem
  mov _universe, ax

Logging on returns the heap's segment in AX and its size in CX. The universe is the heap's first cell, so its segment is the heap's segment too. The smallest heap is 16 cells and the largest 7FFFh, the smallest can't be bigger than the largest, and you can only log on once. If DOS hasn't got enough memory, CX says how many cells it could have given. When you're finished, you log off again, which frees the heap and puts the old INT 3Dh vector back:

  call logoff_3doms

In between, each function takes its number in AH, and keeps every register apart from AX and any it returns. Structures are passed and returned as segments. If something goes wrong, the carry flag is set, AX holds an error code, and nothing in the scene has changed:

00h - Info

Gets the version and how full the heap is.

Returns the version in AH and AL, the heap's segment in BX, its size in cells in CX, and the number of free cells in DX.

10h - Move

Gives an object, or the universe, a new position, angles and rotation order. Everything in it moves with it.

Returns with carry clear if it worked.

    ;  Turn the turntable a little more each frame.
  add _turn_rx, 1
  add _turn_ry, 2
  add _turn_rz, 4
  mov ah, 10h
  mov si, offset _turn
  mov es, _turntable
  int 3Dh
  jc tester_error

11h - Change object form

Sets the form an object is drawn with, or with BX set to 0, takes its form away.

Returns the old form in AX, or 0 if it didn't have one.

  mov ah, 11h
  mov bx, _form
  int 3Dh
  jc tester_error

12h - Change centre

Moves the centre of an object, form or shape, which is what it's sorted by when it's drawn.

Returns with carry clear if it worked.

  mov ah, 12h
  mov si, offset _bodycentre
  mov es, _shape
  int 3Dh

18h - Delete object

Takes an object out of the scene and frees it and its centre. It has to be empty, so delete the objects in it first.

Returns the object or universe it was in, in AX.

  mov ah, 18h
  mov es, _object
  int 3Dh

19h - Delete form

Frees a form and everything in it: its shapes, their faces, its points and all the centres. No object can be using it.

Returns with carry clear if it worked.

  mov ah, 19h
  mov es, _form
  int 3Dh

1Bh - Create object

Adds an object to the universe or to another object. It starts at the origin of what it's in, not turned and with no form.

Returns the new object in AX.

    ;  Make the turntable in the universe.
  mov ah, 1Bh
  mov si, offset _origin
  mov es, _universe
  int 3Dh
  jc tester_error
  mov _turntable, ax

1Ch - Create form

Makes a new, empty form.

Returns the new form in AX.

  mov ah, 1Ch
  mov si, offset _origin
  int 3Dh
  jc tester_error
  mov _form, ax

1Dh - Create shape

Adds a shape to a form.

Returns the new shape in AX.

  mov ah, 1Dh
  mov si, offset _fincentre
  mov es, _form
  int 3Dh
  jc tester_error

1Eh - Create face

Adds a face to a shape, sharing any corners that are already points in its form.

Returns the new face in AX.

tester_faces:
  mov al, [si]
  inc si
  mov ah, 1Eh
  int 3Dh
  jc tester_faces_end
  add si, 36
  loop tester_faces
  clc
tester_faces_end:
  ret

20h - Render

Draws the whole scene into a 320x200 buffer, which can be the screen at A000h or any other 64k segment. The buffer isn't cleared first.

Returns with carry set and an error code in AX if it found a bad structure on the way.

    ;  Render the universe into the buffer.
  push ds
  mov ah, 20h
  mov es, _buffer
  mov ds, _universe
  int 3Dh
  pop ds
  jc tester_error

2Ch - Triangle

Fills a triangle in one colour. It's what the faces are drawn with, and it's handy on its own. Anything off the screen is left out.

Returns with carry clear if it worked.

  mov ah, 2Ch
  mov al, 15
  mov bx, 160
  mov cx, 20
  mov si, 20
  mov bp, 180
  mov dx, 300
  mov di, 180
  mov es, _buffer
  int 3Dh

2Dh - Line

Draws a line in one colour, including both ends. Both ends have to be on the screen.

Returns with carry clear if it worked. It steps one pixel at a time along whichever way the line is longer, and keeps an error term for the other way, stepping across when it runs out.

int3D_line_loop:
  mov es: [di], al
  add di, bx
  sub si, dx
  jge int3D_line_noadj
  add si, _line_len
  add di, cx
int3D_line_noadj:
  dec bp
  jnz int3D_line_loop

Inside the handler

Logging on points the INT 3Dh vector at 3DOMS's handler. It turns interrupts back on, so the clock keeps ticking while a scene is drawn, then saves every register and calls the function, which compares AH with each function number in turn:

int3D_intvect:
  sti

  cmp ah, 00h
  je int3D_info

    ;  Every other function keeps all the registers apart from AX.
  push ebx
  push ecx
  push edx
  push esi
  push edi
  push ebp
  push ds
  push es
  cld
  call int3D_function
  pop es
  pop ds
  pop ebp
  pop edi
  pop esi
  pop edx
  pop ecx
  pop ebx
  jc int3D_error
  jmp int3D_end

Errors come back in the carry flag, the way DOS does it. An interrupt handler returns with IRET, which pops the caller's flags off the stack, so to set or clear carry the handler changes bit 0 of the flags where they are on the stack:

int3D_end:
  push bp
  mov bp, sp
  and word ptr ss: [bp+6], 0FFFEh
  pop bp
  iret

Just before the handler is the string "3DOMSv" followed by 0 and 15h, for telling whether 3DOMS is already loaded as a TSR. As it is, it's assembled into the program that uses it.

Limits

The limits on objects and shapes also set the size of the draw list. With every object 127 objects wide and 8 deep, the longest the list can get is 9 levels of 128 entries plus one form's 127 shapes, so it's made that long and can never fill up.

The documentation also plans what comes after flat colours: bitmap textures, RGB colours dithered onto an orthogonal palette, reflections and smooth shading ("for fast computers only!"), light sources and distance fading.