Clipping bobs

[roondar]

I'm (very, very) slowly busy building a 'game engine' from the ground up (in 68000 assembly). Mostly as a way of having a goal apart from learning how the Amiga chipset works'. It's been a lot of fun and a lot of trial and error

So far I've managed to create screens/play around with copperlists, place hardware sprites, read/write to disk, drawing tiles and generally play about with the blitter to draw in various modes (cookie cut, NOT, XOR, vertical flip, line mode, with and without 'Blitter Nasty', etc).

However, I'm a bit stuck when it comes to clipping bobs to the screen. I do have a sollution, but it feels like my method is rather slow.

What I do now is check the coordinates of the bob vs screen boundaries and then alter modulos, pointers and shifts so that the bob fits. However, this is not exactly fast to do and I need to check the boundaries for every bob I want to draw.

So, I was wondering:

How would you efficiently clip bobs to the screen?
How do other games deal with negative x/y coordinates & clipping?

I've tried searching Google & EAB but couldn't find answers, hence the new thread

[Apollo]

You could work f.ex. with the blitmask BLTAFWM & BLTALWM. This brings a bit of calculating for the correct position in display memory and the mask. Or, what I did in the past, use a bitmap which 'adds' the width of your biggest bob to the left and the right of your display window (using display modulos BPLxMOD), and just don't care about what gets drawn there. But, this only works if you don't want to scroll your display along the x axis.
For the vertical axis you could add y lines to your display memory (so the bob can move upwards out of the display). The bottom is easy as well, add the Y size of lines to your display memory or calculate the correct number of lines for you BLTSIZE (f.ex. blitter would only blit one line if the bob is visibler only on the last line if display window).
This is for a "static" display window, no scrolling. Things get a bit more complicated when scrolling is involved.

[NorthWay]

Depending on how you want your engine to work you have a few options.
- do proper clipping. saves blitter cycles.
- make the virtual screen bigger than what you see so that whatever size your bob is then it will not go outside the memory set aside.

I suspect you want proper clipping though as when you get to scrolling with wraparound display buffers you will need to split and possibly clip bobs too. (I.e. at the "wrong" spot it could take 4 blits to show your bob.)

[roondar]

Hmm, I hadn't thought about extra requirements for clipping when you're scrolling!

Seems like properly clipping is the way to go then (if only to remain future proof). Which means I get to look into making my clipping algorithm work as fast as I can make it. Should've known there are no silver bullets when it comes to blitting

I admit I did kind of forget that clipping takes time, but usually makes bobs smaller as well so you do save some cycles as well.

[Mrs Beanbag]

when you're doing vertical wrap-around scrolling you have to clip at the join and draw the bob on both sides! i actually don't know how efficient my bob clipping routine is since i haven't looked at it for ages, it maybe worth revisiting it now... but iirc it does work by offsetting pointers &c like you suggested, although to simplify things it only needs to do that on a per-word basis, in other words it can only clip to the nearest 16 pixels horizontally.

[roondar]

Originally Posted by Mrs Beanbag

when you're doing vertical wrap-around scrolling you have to clip at the join and draw the bob on both sides! i actually don't know how efficient my bob clipping routine is since i haven't looked at it for ages, it maybe worth revisiting it now... but iirc it does work by offsetting pointers &c like you suggested, although to simplify things it only needs to do that on a per-word basis, in other words it can only clip to the nearest 16 pixels horizontally.

I suppose you then use a scroll buffer which is 32 pixels wider than normal (16 each side) to accomodate the extra pixels from the clipped bobs?

It does seem like a good method though, saves updating the blitter masks and you don't need to add as many pixels on the side.

[thellier]

Hello

This is a generic clipping function using rectangles
Note that the screen got an x y position as the game take place inside a big level map


/*=================================================================*/
BOOL RectInScreen(struct GM_Rect *screen,struct GM_Rect *sprite)
{
WORD sprite_xmax,sprite_ymax,screen_xmax,screen_ymax,cut;

if(sprite==screen) return(TRUE);

sprite_xmax =sprite->x+sprite->w-1;
sprite_ymax =sprite->y+sprite->h-1;
screen_xmax =screen->x+screen->w-1;
screen_ymax =screen->y+screen->h-1;

if(sprite_xmax < screen->x) return(FALSE);
if(sprite_ymax < screen->y) return(FALSE);
if(screen_xmax < sprite->x) return(FALSE);
if(screen_ymax < sprite->y) return(FALSE);

if(sprite->x < screen->x)
{cut=screen->x - sprite->x; sprite->x+=cut; sprite->w-=cut; }
if(sprite->y < screen->y)
{cut=screen->y - sprite->y; sprite->y+=cut; sprite->h-=cut; }
if(screen_xmax < sprite_xmax)
{cut=sprite_xmax - screen_xmax; sprite->w-=cut; }
if(screen_ymax < sprite_ymax)
{cut=sprite_ymax - screen_ymax; sprite->h-=cut; }

return(TRUE);
}

[Codetapper]

But always consider if it's even worth the hassle. If you're drawing a lot of small bobs (eg. 16 or 32 pixels wide for example), you're potentially doing a hell of a lot of comparisons on every single object before you even get to the drawing phase.

In those cases, an extra 32 pixels of space on either side of the screen buffer is much easier and then you can forget about horizontal clipping altogether and use a shorter and faster blitter routine.

[Samurai_Crow]

The built-in BOB functions in Graphics.library use Layers.library and do their own clipping, don't they?

[roondar]

Originally Posted by Codetapper

But always consider if it's even worth the hassle. If you're drawing a lot of small bobs (eg. 16 or 32 pixels wide for example), you're potentially doing a hell of a lot of comparisons on every single object before you even get to the drawing phase.

In those cases, an extra 32 pixels of space on either side of the screen buffer is much easier and then you can forget about horizontal clipping altogether and use a shorter and faster blitter routine.

That might actually be a great way of doing things! I could either break up bigger bobs into 32 pixel wide ones or only do clipping on bigger bobs. Assuming I even need bobs > 32 pixels wide that is.

That said I do believe I'd have to do the comparing anyway if I were to create a scrolling game (after all, I'd need to know if an object needs to be drawn on screen at all or not). Maybe clipping is always needed in scrolling games?

For what I'm trying now it might work though, my first effort will probably only feature scrolling in the title/intro elements and no scrolling in game.

Originally Posted by Samurai_Crow

The built-in BOB functions in Graphics.library use Layers.library and do their own clipping, don't they?

Ah yes, I suppose they do. However, I'm not using them so they won't help me much

[Codetapper]

Originally Posted by roondar

That said I do believe I'd have to do the comparing anyway if I were to create a scrolling game (after all, I'd need to know if an object needs to be drawn on screen at all or not). Maybe clipping is always needed in scrolling games?

Another alternative is a combination of the two ideas. Don't clip to the pixel level horizontally, but clip to the nearest word.

Consider a case where your screen is 320 wide, but the buffer is 352 pixels wide, and you are drawing a massive object at x=319. The slow way works out that there's only 1 visible pixel, so you have to stuff around with first and last word masks to only draw that single pixel - or simply work out that you can draw 1 word wide, so draw it (and part of the right buffer will be overwritten). As long as you clean up the buffer afterwards, you can safely do this and it's a lot simpler code to deal with words than pixels.

[roondar]

Originally Posted by Codetapper

Another alternative is a combination of the two ideas. Don't clip to the pixel level horizontally, but clip to the nearest word.

Consider a case where your screen is 320 wide, but the buffer is 352 pixels wide, and you are drawing a massive object at x=319. The slow way works out that there's only 1 visible pixel, so you have to stuff around with first and last word masks to only draw that single pixel - or simply work out that you can draw 1 word wide, so draw it (and part of the right buffer will be overwritten). As long as you clean up the buffer afterwards, you can safely do this and it's a lot simpler code to deal with words than pixels.

Ah, that seems to be a very good compromise between memory/time used and complexity. I think this is what Mrs. Beanbag was suggesting earlier, but I didn't realise how it would work at that moment.

I think I'll have a go at clipping this way instead of my slower 'pixel perfect' way.

Thanks for the help!
(that goes for everyone of course )

[ReadOnlyCat]

Since you have to do on/off screen testing anyway I would side step the issue by making sure the list of bobs is sorted horizontally (and vertically). Then split the list in three categories of objects: off screen, clipped, on screen.

Only the objects in the clipping category actually require clipping tests, you can ignore the off screen ones and draw the on screen ones without any further testing.

If the objects respective positions only change slightly each frame the sorting can be made very fast by selecting a proper algorithm.

[roondar]

Originally Posted by ReadOnlyCat

Since you have to do on/off screen testing anyway I would side step the issue by making sure the list of bobs is sorted horizontally (and vertically). Then split the list in three categories of objects: off screen, clipped, on screen.

Only the objects in the clipping category actually require clipping tests, you can ignore the off screen ones and draw the on screen ones without any further testing.

If the objects respective positions only change slightly each frame the sorting can be made very fast by selecting a proper algorithm.

Hmm, interesting idea. Reminds me of C64 sprite multiplexers.

Anyway, I do wonder how this would save time though. It seems to me that both this as well as a non-sorted approach need to check the coordinates of every object against screen boundaries (otherwise the sort can't know when to add an object to the non-clipped/clipped/off-screen lists).

I suppose you could skip the actual clipping this way in some cases. The question is, does that cost more time than sorting would if it would need to swap items. I honestly don't know.

Maybe something to try down the line, I'm sure I have an insertion sort routine lying about somewhere

[hooverphonique]

if they are sorted, you don't need to check all bobs. you could e.g. do a binary search for screen boundary coordinates, and know that all bobs in between in the list are on-screen.

[roondar]

Well, yes of course you could.

But, to guarantee a sorted list, surely you need to call the sorting routine every frame to deal with moved bobs (after all, if a bob moves you can't guarantee the list is sorted anymore).

My point was that while searching an array after sorting is definitely quicker than searching an array that isn't sorted, you still need to do (at least) all comparisons during sorting that you'd otherwise have to do during clipping.

After all, sorting routines usually have a best case order of N for sorted arrays.

Or am I missing something here?

[ReadOnlyCat]

Originally Posted by roondar

[...] I do wonder how this would save time though. It seems to me that both this as well as a non-sorted approach need to check the coordinates of every object against screen boundaries (otherwise the sort can't know when to add an object to the non-clipped/clipped/off-screen lists).

The point of the sorting is to avoid that.
Since the list is sorted, you examine the objects for clipping first and after you encounter the first one which left coordinate is on screen you know all the remaining ones are not clipped.

Of course you also need to take the right border (and up/down) into account but that is a simple variation of the principle.

Originally Posted by roondar

I suppose you could skip the actual clipping this way in some cases. The question is, does that cost more time than sorting would if it would need to swap items. I honestly don't know.

You swap pointers, not items. And you can also side step sorting by doing it only when necessary: at insertion or when objects move (bubble sort is almost O(n) when list is mostly sorted, but there probably are better ones).

Clustering helps too: use two lists, one for left half of the screen, other for right side and sort them separately. This reduces sort time and to pass objects from one list to the next you only need a few tests.

[roondar]

Originally Posted by ReadOnlyCat

The point of the sorting is to avoid that.
Since the list is sorted, you examine the objects for clipping first and after you encounter the first one which left coordinate is on screen you know all the remaining ones are not clipped.

Of course you also need to take the right border (and up/down) into account but that is a simple variation of the principle.



You swap pointers, not items. And you can also side step sorting by doing it only when necessary: at insertion or when objects move (bubble sort is almost O(n) when list is mostly sorted, but there probably are better ones).

Clustering helps too: use two lists, one for left half of the screen, other for right side and sort them separately. This reduces sort time and to pass objects from one list to the next you only need a few tests.

Actually, I do realize that you'd swap pointers. I said items because, frankly, it's so logical to me you'd swap pointers to save on copy costs I kinda forgot to write it in my post

Anyway, I feel I've not been clear about what I mean. Your idea (especially the last one) is quite good, when I say I'm not sure about the relative speed I'm looking at what I'd think to be an average case: (nearly) all bobs on/near screen moving every frame. In those scenario's you'd have to check and potentially update the lists for nearly all objects - either by sorting from scratch, or by directly altering the lists as you iterate bobs.

What I was wondering is wether the (slightly) more complex code required to do this is actually going to be faster than a regular 'clip every near/on screen bob' approach. Purely because clipping is only something like 8 compares/branches and 4 adds (2 compares + 1 add per edge) per bob in the worst case.

So in essence, I'd agree that the algorithm makes sense.

However, I've regularly seen more complex algorithms that do less iterations perform worse than simpler algorithms that do more and am not sure how much extra work your algorithms would end up doing for the cases where it does need to do something. Thats the essence of my uncertainty.

You have given me some ideas to think though and I may try out your suggestion - if only to know if it works

(as an aside, I'd never use bubble sort - personally I use insertion sort for sets I know to be nearly sorted or staying close to sorted between sorts - it's really good for those situations, performing at O(N) for sorted sets and close to that for sets with a few items out of place)

[thellier]

Hello

>Purely because clipping is only something like 8 compares/branches and 4 adds (2 compares + 1 add per edge) per bob in the worst case.
In the worst case but lots of (say) ennemies will be out of screen in a single direction
For exemple a XenonII kind of game with ennemies that come from upside will mostly clip them out against ymin

In fact the the most frequent "clip it out" test must be the first

Alain