#1536 - pollier - Sun Jan 19, 2003 10:40 pm
Can anyone suggest some very fast methods of positioning sprites on a rotation/scaling background? Rotation goes through 32 different angles and scaling is always constant. (tiles are half as high as normal) My demo is going to be very positioned-sprite-intensive so should I be using 32-bit 8-bit fractional LUTs, or a less accurate alternative, or what assembly routines can you suggest? Oh yes, I'm also going to have to be doing a lot of sprite sorting; could anyone suggest an especially fast algorathim?
...wow, that makes it sound overly complicated for a start...
Thanks!
_________________
(Works for me!)
#1548 - Kay - Mon Jan 20, 2003 12:38 am
Need more informations about sprites (how many, size, ...) to answer first question. LUTs are often more effective than any calculations and code stills clear to understand.
Sorting datas is a special task:
* Quick sort is the simpliest and one of fastest method currently aviaible, but it consumes too many stack memory and code badly miss CPU cache requierement because of nested branches
* Bubble sort is a good way, but it's slow
* Postman sort is the fastest for small/medium amount of datas, but need HUGE amount of memory (not suitable for GBA [data_size*(number_of_word_to_sort^3) + number_of_word_to_sort] bytes :)
* Linear sort is slow, but need no extra memory
For GBA Bubble or Linear sorting are fast enough, since there's only a maximum of 128 objects to sort.
-- Kay
#1551 - Touchstone - Mon Jan 20, 2003 1:09 am
About sorting sprites, you can use a linked list of all the sprites that should be rendered and sort the sprites as you add them to your render-list. Plus, if you have a list of sprites that will never change priority amongst themselves, such as an object composed of several sprites, or an effect with lots of sprites, you can just add the object sprite-list to your render-list and keep that object sprite-list statically sorted. See what I mean?
_________________
You can't beat our meat
#1557 - ampz - Mon Jan 20, 2003 3:08 am
| Kay wrote: |
* Quick sort is the simpliest and one of fastest method currently aviaible, but it consumes too many stack memory and code badly miss CPU cache requierement because of nested branches
|
I was not aware the GBA had any cache? Besides, run the code in internal RAM and cache becomes irrelevant anyway.
#1560 - tepples - Mon Jan 20, 2003 4:27 am
Quicksort can run out of stack space, and it can degrade to bubble sort in the worst case. If you want the best performance in both average and worst case, use heapsort, which is slightly slower than quicksort but still O(n log n) even in the worst case.
If you want something simpler, use Shell sort (insertion sort with decreasing gap size on each pass). Average case O(n^1.25), worst case O(n^1.5), and it's simple enough that I even got a Shell sort working on the 6502 processor in the NES.
For more information about sort algorithms, read "Sort algorithm" from Wikipedia.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#1563 - pollier - Mon Jan 20, 2003 6:48 am
Thanks for all of the input on sorting, I think I've got that figured out now; but could anyone suggest fast methods of positioning sprites on a rotation background? A large number of the sprites will be 64x64 (16 colour, no rotation), although there will only be a few different sprite images used. Would anyone happen to have a LUT-creating program offhand? And what accuracy would you suggest in this case if there are only 32 possible angles?
_________________
(Works for me!)
#1576 - Kay - Mon Jan 20, 2003 1:18 pm
You can create your own LUTs with MSVC++, MSVB or anything else able to do simple maths and sin/cos calculations, even MSAcces or MSExcel.
Considering that rotation/scaling registers use signed 8.8 fixed bit format, it's logic to output LUTs in that format, so you just have to copy the values to IO regs.
-- Kay
For AMPZ, please read:
| Quote: |
| * Quick sort is the simpliest and one of fastest method currently aviaible, but it consumes too many stack memory and code badly breaks CPU pipeline requierement because of nested branches |
I code on to many system a the same time :P
#1582 - ampz - Mon Jan 20, 2003 2:43 pm
You can't use that many 64*64 sprites at the same time because of hardware limitations... So I don't see why code for positioning of the 64*64 sprites would be a problem.
Kay: :)
#3158 - pollier - Wed Feb 19, 2003 6:21 am
Rather than making a new topic, I'll resurface this...
I've solved my issues with the sprites except one thing: I can't get the positioning right. I have my unrotated sprite position, the screen location, and I'm rotating around the center of the screen--so, I need to substract the screen position from the sprites' absolute position, add 1/2 the screen width, and multiply by cos/sin for x/y...and the blasted thing is muddled anyways. I don't think this is a problem with bit shifting, I just have my equation straight.
Could anyone post some code to take my (values are fixed, signed 16-bit) sprite position, screen coordinates, and rotation angle to correctly return the onscreen position of the sprite? I realise that I need s32s but I can implement that easily.
Any help? Thanks.
_________________
(Works for me!)
#3212 - AnthC - Thu Feb 20, 2003 10:15 am
Sure
You need a translation that maps x,y into a new x,y on the rotated screen.
This can be solved by getting the matrix that does the mapping of each point on your unrotated screen and reversing this using a determinant.
since the matrix will probably be 3x3 anyways it shouldn't be too hard to reverse iit.
#3302 - pollier - Sat Feb 22, 2003 3:40 am
argh, I can't get any of this to work; could you post any code samples? I'm really stuck and I'm having trouble with the matricies...thanks for your help...
I've done plenty of working 3d matrix math but now 2d is befuddling me (???)
_________________
(Works for me!)
#4055 - pollier - Mon Mar 17, 2003 6:05 am
yoho, I'm back to working on this little project finally..
I'm very confused about the matricies. I know that
A B
C D
is a matrix I can work with here, but then I need to factor in my X and Y map offsets as well and my sprite coordinates...
...
oof. How do I do this sort of thing?
My alternative question is this: What would the equation be to rotate a given point on the screen around the center of the screen n degrees? Without a squareroot?
_________________
(Works for me!)
#5200 - ShadowHunter - Wed Apr 23, 2003 2:28 am
Hey pollier,
I am working on the same problem you had and was wondering if you still are interested in the solution (your last post was quite a while ago). In case you are, I can write up a sloution and show you some equations that I use.
I would also like to see the equations that did not work for you (I am just curious, because I think I know what went wrong)
_________________
<-ShadowHunter->
#5201 - pollier - Wed Apr 23, 2003 3:02 am
Hi, I haven't touched that project for a while now, but yeah :) I never did figure that out, though I'm pretty sure where I went wrong. Silly me messing up my simple trig. Anyways, whatever I had was deleted out of frustration. I was probably just multiplying x/y by sin/cos ratios for my angles. ouch.
Go ahead, post a solution :)
YES! A topic spanning 4 months!
_________________
(Works for me!)
#5203 - tepples - Wed Apr 23, 2003 4:47 am
| pollier wrote: |
| Anyways, whatever I had was deleted out of frustration. I was probably just multiplying x/y by sin/cos ratios for my angles. ouch. |
The affine matrix associated with each rot/scale background maps the pixel space (the screen) into the world space (the map). If you want to place sprites at a given point in world space, you need to map points from world space into screen space. This involves the inverse of the BG matrix. Inverting a matrix (Gaussian elimination) is slow in the general case, especially on the GBA where division is slow, but if you know what operations you composed to create the BG matrix, you can compose the inverse of each operation in reverse order to create the sprite placement matrix.
If you don't know what I'm talking about, read up on some linear algebra until you get to linear transformations and affine transformations.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#5204 - pollier - Wed Apr 23, 2003 5:02 am
my bg map equation comes straight from the Pern Project methinks, although the typing scheme is a little different...
| Code: |
rBG2X = (scrollX - rotationCenterY*(curSin) - rotationCenterX*(curCos));
rBG2Y = (scrollY - rotationCenterY*(curCos) + rotationCenterX*(curSin)); |
question: why did this equation never work when I replaced scrollX/scrollY with the sprite's position?
[i should try it again now but I've got no time-to-code at the moment]
_________________
(Works for me!)
#5260 - ShadowHunter - Wed Apr 23, 2003 10:52 pm
Hey everybody,
Sorry for the delay. Here are the equations:
s16 rotated_x = ((screen_x*COS[WORLD_ANGLE] - screen_y*SIN[WORLD_ANGLE])>>16)-32;
s16 rotated_y = ((screen_x*SIN[WORLD_ANGLE] + screen_y*COS[WORLD_ANGLE])>>16)-32;
Explanation:
screen_x and screen_y is the position of a sprite on the screen before the background is rotated.
rotated_x and rotated_y is the position of the sprite after rotation of the background is taken into account.
WORLD_ANGLE is the angle of the rotating background.
Now the equations come from labelling a triangle and then increasing it's angle by the WORLD_ANGLE and finding the new opposite and adjacent (rotated_x and rotated_y). From there simple algebra will lead you to my results.
There is one little thing that got me stumbled for a while.
As all of you probably know the position of a sprite on the screen is it's top left corner, but when you rotate the sprite itself, it will rotate around the center. You need to adjust the equations so that the rotated position on the screen is the center of the sprite (not the top left corner).
In other words the sprite has to rotate around the same point as its position (otherwise it will slide on the ground).
You can see that I am subtracting 32 from both equations to adjust the position (my sprite's size is 32 with the seize double flag enabled). I subtract to put the sprite's center at the rotated_x and rotated_y values, then I rotate the sprite itself.
Oh I nearly forgot the equations work only if the background rotates around it's top left corner (i.e. coord(0,0)). If you change the center of background rotation screen_x, screen_y, rotated_x, rotated_y become the distance from the center of background rotation. (simple eh?)
Hope this helps. I will put up some demos on my website later on.
P.S. I am always looking for simpler ways of doing things. If somebody knows a better way, please by all means share!
_________________
<-ShadowHunter->
#5720 - Jason Wilkins - Tue May 06, 2003 10:30 pm
Bubble sort is slow if you give it random data. BUT, it can be a fast algorithm for sorting data which is mostly sorted most of the time. You can also run through a single pass of it once, and end up something that is incrementally better sorted than it was before.
Example, if you did a single pass of bubble sort per frame, then it would be fairly fast and if your sprites never got too much out of order, then it may only take a couple of swaps to get them sorted properly again.
So, bubble sort definitely has its uses. If your data is mostly sorted most of the time then the other sorts add a lot of overhead, and quick sort is pathologically slow in that case.
_________________
http://devkitadv.sourceforge.net
#5732 - tepples - Wed May 07, 2003 5:26 am
| Jason Wilkins wrote: |
| Bubble sort is slow if you give it random data. BUT, it can be a fast algorithm for sorting data which is mostly sorted most of the time. |
Insertion sort is on average at least twice as fast as bubble sort but still O(n) and works just as well on already-sorted data. Shell sort, or several passes of insertion sort with decreasing gap size, is even faster: O(n^1.5) worst case, O(n^1.25) average.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#5733 - Jason Wilkins - Wed May 07, 2003 7:39 am
The only reason insertion sort is faster is because computers tend to be slower at swapping than comparing. For that reason I think of bubble and insertion sorts to be two sides of the same coin.
Anyway, my point was not that one should use bubble sort, but that one should not dismiss it right away because the textbook says it is too slow. There is no one best search or sort, otherwise there would be hardly any point in the textbook going over all of them to arrive at shell and quick sorts.
The 'bubbling' behavior of bubble sort might be exactly what one needs.
Never mind me. I always feel compelled to defend the poor down-trodden bubble sort, mainly because I'm a graphics programmer, and graphics data tends to be mostly sorted and changes incrementally. Use quick sort first, then an insertion sort as long as the perspective changes gradually.
If I was going a sprite engine, my first throught would be to hash them into buckets using a radix sort and then use an insertion sort on each bucket.
_________________
http://devkitadv.sourceforge.net