You might want to consider this method instead of a reciprocal table:

http://swox.com/~tege/divcnst-pldi94.pdf

See the book "Hacker's Delight" for a less opaque way of looking at this
stuff :D

Basically, though, it's a way of generating a table of constants that when
multiplied with another value, is the same as division.

Si

-----Original Message-----
From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On
Behalf Of Thomas Harte
Sent: Thursday, May 29, 2008 4:34 PM
To: sam-users@nvg.ntnu.no
Subject: Re: Attempts at 3d on the Sam?

I have 0.82 from NVG, though I've not strictly speaking been using it  
in that I haven't actually managed to make it do anything. Though  
closer inspection reveals that it offers to build new perspective  
tables rather than promising to implement them in a future version.  
I've also read your DOC files between then and now, albeit painfully  
using a quick 8 line BASIC program.

The firs major difference between my engine and yours is that I don't  
use an 'S' variable. Z is always distance from the viewer, not  
distance from the screen. So my perspective transform is just:

x' = 128 + 128*(x/z)
y' = 96 + 96*(y/z)

x and y range from -32768 to 32767 (well, -128 to 127 in fixed point)  
and z ranges from <whatever value I choose for the near clip plane> to  
32767 (with similar fixed point proviso). I'm not persuaded that any  
less precise system is suitable for displaying multiple objects in the  
same world without resorting to Dead Wild Cat-style perspective cheats  
whereby objects have their own local perspective and then all vertices  
are scaled according to the distance of the object centre.

A quick test of the obvious alternative projection scheme:

z' = 1/z
x' = 128 + 128*x*z'
y' = 96 + 96*y*z'

Makes me think that trying to wring out reciprocals with the same 8.8  
fixed point as elsewhere isn't going to be precise enough. Probably  
the solution is to create a reciprocal table there with a greater  
precision for z. Should only cost 64 kb, and will definitely be  
cheaper than 2000 cycles.

Right now though my focus is on features, not speed. I'm maybe a few  
hundred lines away from having an Elite-class 3d engine - I just need  
to polish off the frustum clipping and that means implementing a 10x10- 
 >20 bit multiplication routine and a 20x10->10 division routine.  
Though I already pretty much have those but they shuffle bytes in a  
way that I can't use at the clipping stage since they're thinking in  
fixed point and this bit of the code isn't (or rather, it's more  
accurate if it doesn't). And I don't think that divide is really  
amenable to anything tablewise in Samworld since I can't really afford  
to drop any accuracy in clipping, obviously.

Did you produce any demos with Open3d that I could just load up and  
view, without having to assemble? I didn't own COMET back in the day,  
don't have a way to transfer disks to disk images anyway, and World of  
Sam lists it as "not yet approved" for distribution.

On 29 May 2008, at 22:27, Tobermory wrote:

> What version of O3D are you looking at?  It looks like I mainly  
> sorted it
> out in v 0.82.
>
> I went through pretty much the same process as you, considering a  
> lookup
> table to be too time-costly if it was too large.  It looks like I  
> made a few
> odd choices as a result of trying to squash a perspective-correcting  
> lookup
> table into a small space though, to its detriment:
>
> There are 128 X values ( -63 to 64) per Z=value, meaning even as  
> close as
> possible to the camera (Z=0) the perspective correction would only be
> accurate to 2-pixel boundaries.  I kept this accuracy for the Z-axis  
> as
> well, so Z runs up to 1024 in steps of 2.  128 entries per X or Y  
> value *
> 512 Z values = 65536 byte table.
>
> Makes sense so far, however this economy meant I couldn't use absolute
> values in the table, just offsets.  So each entry is INT(RealX -
> CorrectedX).
>
> Not sure it's a great system because the size of the lookup table is
> unwieldy.  The small range of values expected by the table meant a  
> lot of
> messing around.  If I was to repeat it I would probably look at  
> using nice
> values in the equation
> NewX = OldX * S / (S + Z)
>
> You could easily make a table for the S/(S+Z) part - S is the  
> perspective
> factor, and so would be unlikely to change frame-by-frame.   
> (Although as the
> table might reasonably be 8-16K, this could be done at runtime,  
> maybe go all
> 'fisheye lens' on one level...).  The largest value here would be 1  
> and only
> if Z=0 is valid, if the view frustum puts the camera at Z=0 then  
> it's not a
> problem.  I'd keep this in 8.8 format, maybe even junk the whole  
> number
> part.  A quick on-paper tally says this might take up 150T-States.
>
> Next step is to work out a fast way of multiplying for the rest of the
> equation and the job's done.  As you will be multiplying by n/256  
> this is a
> reasonable amount of My personal choice here would be to runs for a  
> nice
> table again, but this time for a table of runnable code, not just  
> values.
> Again, that's about another 100-150T-States.  That would be an  
> improvement
> on 2000 cycles you said at the beginning?
>
>
> Howard
>
> -----Original Message-----
> From: [EMAIL PROTECTED] [mailto:owner-sam- 
> [EMAIL PROTECTED] On
> Behalf Of Thomas Harte
> Sent: 27 May 2008 14:16
> To: sam-users@nvg.ntnu.no
> Subject: Re: Attempts at 3d on the Sam?
>
> Just out of interest, having now checked it out - you mention on your
> Open3d disk that you were planning to implement 'perspective tables'.
> Can I enquire as to what form they were intended to take?
>
> I briefly contemplated a lookup table, indexed by 15 bit depth (my
> values are signed, but obviously points with negative z are never
> projected since they never appear) to produce a 2 byte fixed point
> reciprocal value, but it seemed I'd probably need to spend 15 bits on
> the fractional part to get decent precision, putting me in the realm
> of then having to do at least a 16x16 -> 32 multiply and pushing me
> towards the point where throwing 128 kb of RAM at the problem doesn't
> buy a justifiably large speed increase.
>
> On Tue, Apr 8, 2008 at 6:53 PM, Tobermory <[EMAIL PROTECTED]>  
> wrote:
>> Still fascinated by the subject.  After many many wasted hours  
>> fiddling
>> around with routines, I can see that realtime updated 3D on the SAM  
>> is
>> possible, but haven't got the brainpower to finish off my buggy  
>> work...
>>
>> Howard (=Tobermory)
>>
>> -----Original Message-----
>> From: [EMAIL PROTECTED] [mailto:owner-sam- 
>> [EMAIL PROTECTED] On
>> Behalf Of Colin Piggot
>> Sent: 08 April 2008 14:59
>> To: sam-users@nvg.ntnu.no
>> Subject: Re: Attempts at 3d on the Sam?
>>
>> Thomas Harte wrote:
>>> I've just discovered pyz80 and am having a fresh bash at some Sam
>>> projects. As I'm simultaneously working on a Freescape interpreter  
>>> for
>>> the PC, my thoughts have inevitably turned to 3d on the Sam, even if
>>> it means a Freescape-style non-realtime display.
>>
>> Cool!
>>
>>
>>> besides Stratosphere, the F16 demo and that brief gameover bit in
>>> Dyzonium, are there any other playable segments of games that
>>> demonstrate 3d graphics? I know there are some demos with bits of 3d
>>> graphics, but I figure that spending 256 kb on getting the fastest
>>> possible rotating cube isn't a helpful guide.
>>
>> The game over segment of Dyzonium was all precalculated as far as I  
>> can
>> remember, not processed in realtime.
>>
>>
>>> has it been established whether the animated gifs of Chrome featured
>>> on http://www.samcoupe.com/preview.htm represents the speed at
>>> which the game would play on a real, unexpanded Sam?
>>
>> No, I had just made the animated gifs from screens drawn up by some  
>> of my
>> early test routines.
>>
>>
>>> is there any speed advantage to using the ROM routines such as
>>> JDRAW, JPUT and/or JBLITZ? I appreciate that they are more general
>>> case than routines that it makes sense to write for a game, but as I
>>> understand it the ROM is uncontended?
>>
>> The ROM is uncontended, but you would still be faster to write your  
>> own
>> optimised routines, tailored specifically to exactly what you want  
>> to do.
>> With Stratosphere I came up with a whole set of faster line drawing  
>> and
>> clearing routines, which for example took advantage of the  
>> undocumented
>> instructions to split IX and IY into four 8 bit registers, and for
> clearing
>> it just cleared a byte, and didn't worry about nibble pixels.
>>
>>
>>> To be honest, I can imagine that something like Chrome could be done
>>> with a live update since most of the display doesn't change between
>>> most frames (it's just a bunch of vertical strips of colour that  
>>> quite
>>> often change height and occasionally change colour), and the
>>> algorithms that are commonly used to calculate scenes such as that  
>>> in
>>> Chrome make it really cheap to calculate out a minimal list of the
>>> required changes.
>>
>> I had come up with quite a lot of tricks that would have made  
>> Chrome as
> fast
>> as it could. Solid walls 2 pixels wide, so you are dealing with  
>> just byte
>> values and not nibbles, and means walls could be quickly extended/ 
>> shrunk
>> when drawing the next frame. There's a 9 page article about the  
>> work I had
>> done on Chrome in issue 16 of SAM Revival magazine with more info.
>>
>> Colin
>> ======
>> Quazar : Hardware, Software, Spares and Repairs for the Sam Coupe
>> 1995-2008 - Celebrating 14 Years of developing for the Sam Coupe
>> Website: http://www.samcoupe.com/
>>
>>
>>
>> No virus found in this incoming message.
>> Checked by AVG.
>> Version: 7.5.519 / Virus Database: 269.22.9/1364 - Release Date:
> 07/04/2008
>> 18:38
>>
>> No virus found in this outgoing message.
>> Checked by AVG.
>> Version: 7.5.519 / Virus Database: 269.22.9/1364 - Release Date:
> 07/04/2008
>> 18:38
>>
>>
>>
>

Reply via email to