pouët.net

Go to bottom

How to do dot balls?

category: code [glöplog]
(after looking at my code) ...oh yeah, you also have to calculate only half of the "Ball", because the other half is just an X,Y coord swap again.
Not sure what exactly you are looking for JAC, but maybe this will help you?

http://mikro.naprvyraz.sk/docs/Coding/1/3D-ROTAT.TXT

Code for 12, 9 and 6 muls rotations - of course with even less muls if you only rotate 2 axis.
4 muls should do it per dot, and about 8-16 dots have to be rotated. the rest is offsetting and mirroring and scaling.
Cant 'sphere mapping' be used if all point rotate at the same speed along the y axis?
(The map can include perspective projection.)

This reduce the per pixel operation, per quadrant, to:

...
if(source[x>>3]&(x&7F)) screen[sphere_map[x]] = WHITE;
...

I think you need 8K of memory to plot any organization of 0 to 16K pixels. And you have the possibility to do scrolling text/animated shapes.

And since you can do back/front rendering you can do 'multitexturing' and get cheap transparency/blending fx .
Even adding another layer that rotate independently and get blended in one pass is doable.

So all the math is filling the spherical projection map.

I think 4 simple instruction per pixel would be the average cost (no mull, or even an add in the inner loop)
The mapping method look like this.

The random points are simply filled using:
for(int i=0; i<total; i++) point[i] = rnd();
(I use 3 instructions to implement rnd(), and it much better then rand()) - no mul used or fancy trig.
note: to reduce pixel density I do point[i] = rnd() & rnd();

4 instructions per pixel rendered - no mul.

But I have a sqrt() and a cos() in the init code. 4:36 for the "sphere mapping". actually its even more simpler. Rule of thumb on oldschool platforms: the simpler the faster!

lda sinetableNrZ,x
sta spritecoordXNrQ

lda sinetableNrZ,x
sta spritecoordXNrQ

lda sinetableNrZ,x
sta spritecoordXNrQ

...

vblank: x=x+1

You need to use HW acceleration (sprites) so you dont need to plot & erase, only set X coords. One instruction (in 6502 land thats two!) per dot.

"sphere mapping" was mainly in reference to how the dots are stored, as a 2d 'texture' (bitmap)
How they get plotted is what you mention, a single lookup for x.
The difference is that it doesn't process discreet dots, but a map of them.

For a pixel processed here is what is executed:

// Load 8 pixel from the map in r8b, then plot them onscreen.

Pixel1:
test r8b, 1
je Pixel2
movzx eax,word ptr [rdx]
mov dword ptr [r10+rax*4],r9d

Pixel2:
test r8b, 2
je Pixel3
movzx eax,word ptr [rdx+2]
mov dword ptr [r10+rax*4],r9d
...

Its 2 extra instructions are the conditional that handle a simple transparency 'blending'.

The benefit from this method is you have your front / back pixel pre sorted, and rendering allot of dot is cheap. (And you can draw in the bitmap)
In contrast drawing a few dot is very, very wastfull...

I didn't have a 6502 in mind when I mentioned this, I have no idea how to optimize for those little guys.

BTW, the link you posted is impressive.
I benched this on my Q6600 (not a 6502, thats for sure:) and I get ~1.5 billion rotating dots rendered per second.
I added a gaussian blur and got this look. (nicer in motion as you get depth, the back pixel are render a shade darker) I don't know how he did it, but I think that Pet's rotation-code from Roots (TP94) was special.
another old rotate trick is to generate lookup table per frame for every component of the rotation matrix. then you can replace the muls with table lookups, which was faster back then.
yeah, utterly useful for 64kram. how much lookup will take a sin(x)*cos(y) in 8 bit, say 256 entries per sin/cos ?
Who propose to use a sin(x)*cos(y) table?
to generate lookup table per frame for every component of the rotation matrix
Is the idea to do the following for a parallel projection?
sx = matElement00[x] + matmatElement01[y] + matmatElement02[z]
sy = matElement10[x] + matmatElement11[y] + matmatElement12[z]

And you build those 6 tables (256 byte each? for a 256x256x256 world) each frame using a sinCos table and mul function ??

You guess that you would need a load of point to make this beneficial.
to replace the muls of the rotation matrix you need several tables for sin(x)*cos(y) or sin(x)*cos(z) etc. 6 tables 256 byte each wont do.
Other examples of bitmap based dot ball (for high density/gfx)   Ok, not exactly the topic and many days late, but here's the code i used to solve the "dictators problem": distributing many points on a sphere. 4 points=tetrahedron, 6=octaeder, 8 points=square antiprism, 12 points=icosaeder, 24 points=snub cube...

The code is in Blitzmax

Code: 'Alain Brobecker, 2011/07/13 Strict Const NbPoints=999 Const Radius=300 Global scrx#[NbPoints],scry#[NbPoints],scrz#[NbPoints] Global x#[NbPoints],y#[NbPoints],z#[NbPoints] Global newx#[NbPoints],newy#[NbPoints],newz#[NbPoints] Global anglex#=0 Global angley#=0 Global anglez#=0 Global A#,B#,C#,D#,E#,F#,G#,H#,I# Global eyedist#=512.0 Global mindist2# Global j,k '**** Initialise screen Const ScrW=1280 Const ScrH=1024 Graphics ScrW,ScrH,32 HideMouse '**** Initialise 3d shape For k = 0 To NbPoints-1 newx#[k]=Cos(360*k/NbPoints) newy#[k]=Sin(360*k/NbPoints) newz#[k]=1 ' Cos(360*k/2) ' Print "x#=" + x#[k] Next Normalize() '**** '**** Main loop '**** SetClsColor 255,255,255 While Not KeyHit(KEY_ESCAPE) Cls '**** maximize distance between points ' displacement of point A to point B is: ' vector(BA)/BA * (diameter-BA)/diameter For j=0 To NbPoints-1 newx#[j]=x#[j] newy#[j]=y#[j] newz#[j]=z#[j] For k=0 To NbPoints-1 If k<>j Then Local dx#,dy#,dz#,dist# dx#=x#[j]-x#[k] dy#=y#[j]-y#[k] dz#=z#[j]-z#[k] dist#=dx#*dx#+dy#*dy#+dz#*dz# If dist# <> 0 Then dist#=Sqr(dist#) newx#[j]=newx#[j]+dx#/dist#*(2-dist#)/2 newy#[j]=newy#[j]+dy#/dist#*(2-dist#)/2 newz#[j]=newz#[j]+dz#/dist#*(2-dist#)/2 Else newx#[j]=newx#[j]+0.1 newy#[j]=newy#[j]+0.1 newz#[j]=newz#[j]+0.1 EndIf EndIf Next Next Normalize() '**** Rotate and draw points A#=Cos(angley#)*Cos(anglez#); B#=Cos(anglex#)*Sin(anglez#)+Sin(anglex#)*Sin(angley#)*Cos(anglez#); C#=Sin(anglex#)*Sin(anglez#)-Cos(anglex#)*Sin(angley#)*Cos(anglez#); D#=-Cos(angley#)*Sin(anglez#); E#=Cos(anglex#)*Cos(anglez#)-Sin(anglex#)*Sin(angley#)*Sin(anglez#); F#=Sin(anglex#)*Cos(anglez#)+Cos(anglex#)*Sin(angley#)*Sin(anglez#); G#=Sin(angley#); H#=-Sin(anglex#)*Cos(angley#); I#=Cos(anglex#)*Cos(angley#); SetColor 0,0,0 For k = 0 To NbPoints-1 Local xx#,yy#,zz# xx#=x#[k]*Radius yy#=y#[k]*Radius zz#=z#[k]*Radius scrz#[k]=G#*xx#+H#*yy#+I#*zz# scrx#[k]=ScrW/2+(A#*xx#+B#*yy#+C#*zz#)*eyedist#/(eyedist#+scrz#[k]) scry#[k]=ScrH/2+(D#*xx#+E#*yy#+F#*zz#)*eyedist#/(eyedist#+scrz#[k]) DrawRect scrx#[k]-2,scry#[k]-2,5,5 Next anglex#=anglex# angley#=angley#+0.5 anglez#=anglez# Flip Wend FlushKeys End '**** Normalize points, ie put them back on the unit sphere Function Normalize() Local dist# For k = 0 To NbPoints-1 dist#=newx#[k]*newx#[k]+newy#[k]*newy#[k]+newz#[k]*newz#[k] If dist#<>0 Then dist#=Sqr(dist#) x#[k]=newx#[k]/dist# y#[k]=newy#[k]/dist# z#[k]=newz#[k]/dist# Else x#[k]=Cos(2*Pi/NbPoints) y#[k]=Sin(2*Pi/NbPoints) z#[k]=0 EndIf Next End Function

The thing jmagic mentioned is the "FastRot" here: http://www.codercorner.com/Oldies.htm
Was it really 1.5Billion per sec? That's too much! Well, I didn't tried dotball yet but the fastrot I tried in C++, it works great, though I rotate the Armadillo points (170000 points) from stanford model rep, at 170fps. That's much better from my old engine that rotate 50fps I think in this computer. It uses fixed point too, handles projection with (1/z) div LUTs. Anyway, fun experiment, but 1.5Billion not in my dreams..
What I used was more akin to texture mapping a sphere with a parallel projection.
And the dot rate I gave need to be divided by the pixel density.

This method doesn't work on 'point cloud', its very, very limited.
Its the type of algorithm you would use on an 8bit platform.

How did you do the bitmap base dot balls? texture and spheric projection?
is this all code C ?
can i compile it in a normal compiler ?
Yes.
The bitmap implicitly encode the latitude and longitude of the dot.
So the storage requirement is constant no matter how many dots you have, but the cost per active dot can be thought of:
1 bit / overall density(0 to 1)
If the cost per bit >8, its cheaper to just encode the latitude explicitly.

The other data needed is the projection LUT,
Its a scanline offset, 8bit is enough for ball size upto 512xN.
But since its symmetric, you only need a quadrant.

So 4K for a 128x128 projection LUT+ 2K for the dots bit map
(2K represent upto 16K dots at 100% density)

I choose the bit map method because it trivial to fill it with random dots.

Here is the entire function:

// Generate ~4 thousand random dot on the sphere
for(int i=0; i<2048;i++) bitmap[i] = rnd()&rnd();

This get you a 25% distribution of random dot on the sphere.

Thats how all the images I posted where rendered (but with a 16bit LUT)
Y Axis Rotation is done by adding an offset in the projection map.

The inner loop for the scanline can be done like this in C
(render upto 8 dots on screen per iteration)

Code: for(int x=x0; x<x1; x+=8) { unsigned short p = *(unsigned short*)&projectionMap[(((x+delta)&(mapWidth-1))/8)]; p >>= delta; // Blend Detination Color if(p&0x01) buffer[map] = color; if(p&0x02) buffer[map] = color; if(p&0x04) buffer[map] = color; if(p&0x08) buffer[map] = color; if(p&0x10) buffer[map] = color; if(p&0x20) buffer[map] = color; if(p&0x40) buffer[map] = color; if(p&0x80) buffer[map] = color; map += 8; }
take a pen, grab your balls and then add the dots