| View previous topic :: View next topic |
| Author |
Message |
gamerChad
Joined: 13 Aug 2005
Posts: 21
Location: Cydonia, Mars
|
 Posted: Sat May 13, 2006 11:29 pm Post subject: Code offering, and API portability |
 |
|
Hi. I just noticed this project, and found it interesting since I've messed with this sorta thing a while ago.
I also noticed that you have some LGPL'd rotozooming and circle drawing code, and it sounds like you want to ditch that for something with a more favorable license. I just might be able to help there. I have a rotate function that I wrote, originally in C#, and ported to D. As for the zooming part, you'd be on your own there. For circle drawing, I might have some C# code laying around that does just that. So let me know if you are still looking for these functions.
I also have a function that does pixel-perfect collision detection. Now I know you have that already, but you might want to give mine a try. My algorithm compares 32 pixels at a time by using the whole width of a (32 bit) register and collision map of bits packed into an integer array. I believe it works correctly as I've tested it for all of the cases I can think of, but I've never benchmarked it against other pixel-perfect routines, so I'd be interested in seeing how that works out.
Now about that API portability. It seems that Arc is heavily dependent on SDL and maybe OpenGL. Are there any plans to change that, such as making it easy to code alternative dependencies? Maybe I'm mistaken? |
|
| Back to top |
|
 |
clayasaurus
Joined: 21 May 2004
Posts: 857
|
| Posted: Sun May 14, 2006 9:39 pm Post subject: |
|
|
Yes this code would be welcomed. Zooming really isn't that big of a deal, I'd rather be 100? zlib/png licensed.
Right now Arc is heavily dependent on OpenGL and SDL although a lot of things are already abstracted. If a GLFW or similar toolkit becomes D native, I'll add support for that and abstract as necessary. Unless Microsoft really shafts up OpenGL support and I need to use Direct3D, I don't imagine why I should abstract the OpenGL code, as it'll work on every platform. |
|
| Back to top |
|
|
gamerChad
Joined: 13 Aug 2005
Posts: 21
Location: Cydonia, Mars
|
| Posted: Mon May 15, 2006 4:16 pm Post subject: |
|
|
Not sure how to get this to you, so I'm going to try posting it.
Note that in the collision code, I have the beginning of a way to find out exactly where a collision occured, if it occured. I consider that part incomplete though. If it were to be completed it should somehow yield a number of points where the two collision maps are overlapping. The interface for that could probably use some work, but for normal pixel-perfect collision detection you shouldn't have to worry about it at all.
Collision code:
| Code: |
/*
Copyright (c) 2006 Chad Joan
This software is provided 'as-is', without any express or implied warranty. In no event will the
authors be held liable for any damages arising from the use of this software.
Permission is granted to anyone to use this software for any purpose, including commercial
applications, and to alter it and redistribute it freely, subject to the following restrictions:
1. The origin of this software must not be misrepresented; you must not claim that you wrote the
original software. If you use this software in a product, an acknowledgment in the product
documentation would be appreciated but is not required.
2. Altered source versions must be plainly marked as such, and must not be misrepresented as
being the original software.
3. This notice may not be removed or altered from any source distribution.
*/
/* As a convention, I have made the bits map straight into a standard coordinate plane,
rather than being flipped around in each integer. So the leftmost bit in a collision map is in
the leftmost bit of the leftmost 32 bit integer. This saves me A LOT of confusion when actually
checking for collisions.
*/
private
{
import derelict.sdl.sdl;
debug{ import std.stdio; }
}
public class CollisionMap
{
public Uint32[] Map;
public int WidthAsIntegers;
public int WidthAsBits;
public int Height;
this(SDL_Surface* surface)
{
// Width/height in bits is representative of the surface's width/height.
WidthAsBits = surface.w;
Height = surface.h;
// Divide width by 32, rounding up the result.
WidthAsIntegers = WidthAsBits >> 5;
if ( (WidthAsIntegers << 5) < WidthAsBits )
WidthAsIntegers++;
// Result is used in creating the array of integers
Map.length = WidthAsIntegers * Height;
// Fill the array with boolean collision bits.
ubyte* pixel = cast(ubyte *)surface.pixels;
version( LittleEndian )
{
pixel += 3;
}
Uint32 bitselect = 0x80000000; // 2^31 or a 0 int with the leftmost bit set to 1
Uint32 mapIndex = 0;
Map[mapIndex] = 0;
for ( int y = 0; y < Height; y++ )
{
Map[mapIndex] = 0;
for ( int x = 0; x < WidthAsBits; x++ )
{
/* Note the importance of sequence.
- The End of Integer Test must happen between the setting or ignoring of the bit and
the selecting of the bit, otherwise Map[mapIndex] cannot be ORed with 2^31 at
every 32nd + 1 bit (because it will select the 33rd bit, which does not exist).
- The End of Integer Test (EoIT) must happen before the bit select in the loop, otherwise, whenever
dealing with a width that is a multiple of 32, it will try to set Map[length] to 0 and cause
an array index out of bounds error. Because having EoIT at the beginning of the loop also makes
it impossible to be executed at the end of every row, it means that when the row is finished the
next integer can ALWAYS be selected, which is easier than using a conditional.
- pixel += 4 must come after the bit setting/ignoring in the loop, otherwise it will never reach
the first pixel and it will get pixel data from an address outside of the surface.
*/
// End of Integer Test: It's reached the end of the integer, select the first bit of
// next integer and set that integer to 0
if ( bitselect == 0 )
{
bitselect = 0x80000000;
mapIndex++;
Map[mapIndex] = 0;
}
// If the byte is ?100 transparent, assume it is open space and therefore noncollidable.
if ( *pixel > 0 )
Map[mapIndex] |= bitselect; // OR in the appropriate bit
// Add 4 to only check the alpha bytes in the pixel data
pixel += 4;
// Select the next bit, by bitshifting right one
bitselect >>>= 1;
}
// Whenever a row is finished, move to the next integer.
bitselect = 0x80000000;
mapIndex++;
}
}
}
public int CollisionX;
public int CollisionY;
public bool recordCollisionCoordinates = false;
public bool CheckCollision( int X1, int Y1, CollisionMap ColMap1,
int X2, int Y2, CollisionMap ColMap2 )
{
// If the Y-coord of one object is beneath the bottom of the other object, collision is not possible
// Think LowerEdgeOfCM1 = Y1 + ColMap1Height, and also LowerEdgeOfCM2 = Y2+ColMap2Height
if ( Y2 > Y1 + ColMap1.Height || Y1 > Y2 + ColMap2.Height )
return false;
// If the X-coord of one object is to the right of the right edge of the other object, collision is impossible
// Think RightEdgeOfCM1 = Y1 + ColMap1Height, and also RightEdgeOfCM2 = Y2+ColMap2Height
if ( X1 + ColMap1.WidthAsBits < X2 || X2 + ColMap2.WidthAsBits < X1 )
return false;
// Now we know a collision of some type might occur, and we can start checking the different cases and
// create a rectangle representing the overlap area.
// Drawings were made in Courier New font.
/* Case 1: Case 2: Case 3:
* c2______ c2_____ c2_________
* | c1__|____ | c1__|__ | c1__ |
* | | | | | | | | | | | |
* |___|___| | | |___|__| |___|___|__|
* |________| |______| |___|
*
* Case 4: Case 5: Case 6:
* c1_______ c1____ c1__
* c2__|____ | c2__|__ | c2__|___|__
* | | | | | | | | | | | |
* | |____|___| |___|__| | | |___| |
* |________| |_____| |__________|
*
* Case 7: Case 8: Case 9:
* c2_______ c2____ c2___
* c1__|____ | c1__|__ | c1_|____|__
* | | | | | | | | | | | |
* | |____|___| |___|__| | | |____| |
* |________| |_____| |__________|
*
* Case 10: Case 11: Case 12:
* c1______ c1_____ c1_________
* | c2__|____ | c2__|__ | c2___ |
* | | | | | | | | | | | |
* |___|___| | | |___|__| |__|____|__|
* |________| |______| |____|
*
* Case 13: Case 14:
* c2___________ c1___________
* | c1_____ | | c2_____ |
* | | | | | | | |
* | |______| | | |______| |
* |____________| |____________|
*/
// Possibly save cycles by storing these into integers, instead of looking them up from the
// class every time.
int ColMap1Width = ColMap1.WidthAsIntegers;
int ColMap1Height = ColMap1.Height;
int ColMap2Width = ColMap2.WidthAsIntegers;
int ColMap2Height = ColMap2.Height;
// cindices will be set to upper left integers of the overlapping rectangle within the collision mappings.
int c1index;
int c2index;
int Yoffset;
int yIterations;
if ( Y2 <= Y1 ) // Cases 1, 2, 3, 7, 8, 9, & 13
{
// Y Offset from upper-left-most point, measured in bits
Yoffset = Y1 - Y2;
if (ColMap2Height >= Yoffset + ColMap1Height)
yIterations = ColMap1Height; // Cases 2, 8, & 13
else
yIterations = ColMap2Height - Yoffset; // Cases 1, 3, 7, & 9
c1index = 0;
c2index = ColMap2Width * Yoffset;
}
else // Cases 4, 5, 6, 10, 11, 12, & 14
{
// Y Offset from upper-left-most point, measured in bits
Yoffset = Y2 - Y1;
if (ColMap1Height >= Yoffset + ColMap2Height)
yIterations = ColMap2Height; // Cases 5, 11, & 14
else
yIterations = ColMap1Height - Yoffset; // Cases 4, 6, 10, & 12
c1index = ColMap1Width * Yoffset;
c2index = 0;
}
int Xoffset;
Uint32 BitOffset;
int c1ExtraWidth;
int c2ExtraWidth;
int xIterations;
Uint32[] Map1;
Uint32[] Map2;
if ( X2 <= X1 ) // Cases 1, 2, 3, 4, 5, 6, & 13
{
// X Offset from upper-left-most point, measured in bits
Xoffset = X1 - X2;
// Get the amount to offset the bits on c1's integers for a valid comparison.
BitOffset = Xoffset;
BitOffset -= ((Xoffset >> 5) << 5); //Subtract by multiple of 32 that represents integers not checked.
// BitOffset should now be a number between 0 and 31 inclusive.
// It is now prudent to measure Xoffset in integers rather than bits, for the following calculations.
Xoffset >>= 5; // Let the bitshift round it down, this makes the calculations include leftmost integer.
if (ColMap2Width > Xoffset + ColMap1Width)
{ // Cases 3, 6, & 13
xIterations = ColMap1Width;
c1ExtraWidth = 0;
c2ExtraWidth = ColMap2Width - Xoffset - ColMap1Width;
}
else
{ // Cases 1, 2, 4, & 5
xIterations = ColMap2Width - Xoffset;
c1ExtraWidth = ColMap1Width - xIterations;
c2ExtraWidth = ColMap2Width - xIterations;
}
// c1index += 0; - this operation is meaningless, so don't do it
c2index += Xoffset;
// These save a few variable lookups each time through the loop below.
Map1 = ColMap1.Map;
Map2 = ColMap2.Map;
}
else // Cases 7, 8, 9, 10, 11, 12, & 14
{
// X Offset from upper-left-most point, measured in bits
Xoffset = X2 - X1;
// Get the amount to offset the bits on c1's integers for a valid comparison.
BitOffset = Xoffset;
BitOffset -= ((Xoffset >> 5) << 5); //Subtract by multiple of 32 that represents integers not checked.
// BitOffset should now be a number between 0 and 31 inclusive.
// It is now prudent to measure Xoffset in integers rather than bits, for the following calculations.
Xoffset >>= 5; // Let the bitshift round it down, this makes the calculations include leftmost integer.
if (ColMap1Width > Xoffset + ColMap2Width)
{ // Cases 9, 12, & 14
xIterations = ColMap2Width;
c1ExtraWidth = ColMap1Width - Xoffset - ColMap2Width;
c2ExtraWidth = 0;
}
else
{ // Cases 7, 8, 10 & 11
xIterations = ColMap1Width - Xoffset;
c1ExtraWidth = ColMap1Width - xIterations;
c2ExtraWidth = ColMap2Width - xIterations;
}
c1index += Xoffset;
// c2index += 0; - this operation is meaningless, so don't do it
/* Notice the variable switching. That is because, during the pixel perfect loop below,
ORing in carry bits from the previous integer is only possible if the rightmost collision
map is being bitshifted.
*/
int temp = c1index;
c1index = c2index;
c2index = temp;
temp = c1ExtraWidth;
c1ExtraWidth = c2ExtraWidth;
c2ExtraWidth = temp;
ColMap2Width = ColMap1Width;
// These save a few variable lookups each time through the loop below.
Map2 = ColMap1.Map;
Map1 = ColMap2.Map;
}
// Now that we have set up the overlapping rectangle, we can do the actual pixel checking within that rectangle.
Uint32 AdjustedBits;
Uint32 CarryBits;
Uint32 CarryMask = 1; // This is ANDed with the collision data to reveal only
// the carry bits
for ( int i = 0; i < BitOffset; i++ )
CarryMask <<= 1;
CarryMask--;
int BitOnset = 32 - BitOffset; // The carry bits are shifted left by this much to
// position them correctly in the next calculation.
Uint32 CollisionData = 0; // Stores position of collision in the event a collision happens.
debug
{
writefln( "C1coords = (",X1,",",Y1,")" );
writefln( "C2coords = (",X2,",",Y2,")" );
writefln( "BifOffset = ", BitOffset );
writefln( "xIterations = ", xIterations );
writefln( "c1ExtraWidth = ", c1ExtraWidth );
writefln( "c2ExtraWidth = ", c2ExtraWidth );
writefln( "c1index = ", c1index );
writefln( "c2index = ", c2index );
writefln( "CarryMask = ", CarryMask );
}
// The x and y are used outside the scope of the for-loop, so declare them outside that scope.
Uint32 x;
Uint32 y;
for ( y = 0; y < yIterations; y++ )
{
CarryBits = 0;
x = 0;
for ( x = 0; x < xIterations; x++ )
//while ( x < xIterations )
{
AdjustedBits = Map1[c1index] >>> BitOffset; // Shift right for correct positioning
AdjustedBits |= CarryBits; // OR in carry bits from previous integer
CarryBits = Map1[c1index] & CarryMask; // Store the bits that will be shifted away.
CarryBits <<= BitOnset; // Shift the bits into the right position for the next calculations.
// A logical AND of the two integers. If any 2 bits reside on the same pixel,
// they will cause the result to be greater than 0. Then we know a collision has occured.
CollisionData = AdjustedBits & Map2[c2index];
if ( CollisionData > 0 )
goto CollisionOccured;
c1index++;
c2index++;
//x++;
}
// The above loop does not account for the carry bits left over after the last iteration.
// This if statement does.
if ( x + Xoffset < ColMap2Width )
{
CollisionData = CarryBits & Map2[c2index];
if ( CollisionData > 0 )
goto CollisionOccured;
}
c1index += c1ExtraWidth;
c2index += c2ExtraWidth;
}
return false;
CollisionOccured:
if ( !recordCollisionCoordinates )
return true;
debug
{
writefln( "x,y = ",x,",",y );
writefln( "ColData = ", CollisionData );
}
// Now get the point of collision! Little bit of binary search used.
uint bs = 16;
uint halfbs = 8;
uint TempColData = CollisionData ;
if ( TempColData == 0x80000000 )
{
bs = 0;
goto skipBinSearch;
}
while ( TempColData != 0x80000000 )
{
TempColData = CollisionData << bs;
TempColData &= 0xffffffff << bs; //incase there is more than 1 bit
if ( TempColData > 0 )
{
if ( TempColData == 0x80000000 )
break;
bs += halfbs;
halfbs >>= 1;
}
else
{
bs -= halfbs;
halfbs >>= 1;
}
}
skipBinSearch:
if ( Y1 > Y2 )
CollisionY = Y1 + y;
else
CollisionY = Y2 + y;
if ( X1 > X2 )
CollisionX = X1;
else
CollisionX = X2;
CollisionX += (x << 5) + bs;
debug
writefln( "Collision coords: (",CollisionX,",",CollisionY,")" );
return true;
}
/* An example of usage.
public void CheckAllCollisions()
{
int length = environment.mobiles.length;
for ( int i1 = 0; i1 < length; i1++ )
{
int i2 = i1+1;
for ( i2; i2 < length; i2++ )
{
Mobile m1 = environment.mobiles[i1];
Mobile m2 = environment.mobiles[i2];
if ( CheckCollision( m1.X, m1.Y, m1.colMap, m2.X, m2.Y, m2.colMap ) )
{
m2.Collisions ~= m1;
m1.Collisions ~= m2;
}
}
}
}*/
// This is just a way to visually see what collision maps look like.
// It is used to verify that they are being constructed properly.
/*
private import std.file;
public void BinaryDump( CollisionMap map )
{
int width;
int height;
int index;
Uint32 contents;
Uint32 bitMask;
char[] writeBuffer = cast(char[])read( "BinDump.txt" );
char[3] lineEnd = "|"~'\n';
int charIndex = writeBuffer.length;
for ( int y = 0 ; y < map.Height; y++ )
{
writeBuffer.length = writeBuffer.length + (map.WidthAsIntegers << 5) + 3;
for ( int x = 0 ; x < map.WidthAsIntegers; x++ )
{
contents = map.Map[index];
bitMask = 0x80000000;
for ( int i = 0 ; i < 32; i++ )
{
if ( (contents & bitMask) > 0 )
writeBuffer[charIndex] = '#';
else
writeBuffer[charIndex] = '_';
bitMask >>>= 1;
charIndex++;
}
index++;
}
writeBuffer[(length-3)..length] = lineEnd;
charIndex = writeBuffer.length;
}
width = map.WidthAsIntegers << 5;
writeBuffer.length = writeBuffer.length + width + 3;
for ( int i = 0 ; i < width; i++ )
{
writeBuffer[charIndex] = '=';
charIndex++;
}
writeBuffer[(length-3)..length] = lineEnd;
write( "BinDump.txt", writeBuffer );
}*/
|
Now for the rotator. Note that it only works with 32 bpp as is, and only has an anti-aliasing mode. I'm not sure if you are supposed to anti-alias the alpha channel, so I did it anyways. I suppose adding 24 bpp support wouldn't be too hard, and making a non-anti-aliasing rotator should be easier than making an anti-aliasing rotator.
I tested it and the SDL rotozoom takes about 2/3 the time to complete, and I bet this can be optimized. One way I can think of is to skip interpolating pixels that we know contain nothing, which would be done in the "y" for loop. I gave a small attempt at that but it wasn't working out, and I have things to work on that I give higher priority. Also the bitsOfAccuracy thing... there may be a way around that, or at the very least I'd suggest that if you are rotating the same image more than a few times, do it once and reuse the bitsOfAccuracy value.
Hope that works for ya.
Anyhow, here's the code:
| Code: |
/*
Copyright (c) 2006 Chad Joan
This software is provided 'as-is', without any express or implied warranty. In no event will the
authors be held liable for any damages arising from the use of this software.
Permission is granted to anyone to use this software for any purpose, including commercial
applications, and to alter it and redistribute it freely, subject to the following restrictions:
1. The origin of this software must not be misrepresented; you must not claim that you wrote the
original software. If you use this software in a product, an acknowledgment in the product
documentation would be appreciated but is not required.
2. Altered source versions must be plainly marked as such, and must not be misrepresented as
being the original software.
3. This notice may not be removed or altered from any source distribution.
*/
private
{
import derelict.sdl.sdl;
import std.math;
}
version ( BigEndian )
{
private const Uint32 rmask = 0xff000000;
private const Uint32 gmask = 0x00ff0000;
private const Uint32 bmask = 0x0000ff00;
private const Uint32 amask = 0x000000ff;
}
else
{
private const Uint32 rmask = 0x000000ff;
private const Uint32 gmask = 0x0000ff00;
private const Uint32 bmask = 0x00ff0000;
private const Uint32 amask = 0xff000000;
}
public SDL_Surface* CreateRotatedSurface( SDL_Surface* sourceSurface, real radians )
{
if ( sourceSurface == null )
throw new Error( "CreateRotatedSurface(): sourceSurface is null" );
int Width = sourceSurface.w;
int Height = sourceSurface.h;
int BitsOfAccuracy;
// how many bits can we dedicate to anti-aliasing
int LargestNumber;
if ( Width > Height )
LargestNumber = Width;
else
LargestNumber = Height;
if ( LargestNumber < 32 ) { BitsOfAccuracy = 13; goto EndBOA; }
if ( LargestNumber < 128 ) { BitsOfAccuracy = 12; goto EndBOA; }
if ( LargestNumber < 512 ) { BitsOfAccuracy = 11; goto EndBOA; }
if ( LargestNumber < 2048 ) { BitsOfAccuracy = 10; goto EndBOA; }
if ( LargestNumber < 8192 ) { BitsOfAccuracy = 9; goto EndBOA; }
if ( LargestNumber < 32768 ) { BitsOfAccuracy = 8; goto EndBOA; }
if ( LargestNumber < 131072 ) { BitsOfAccuracy = 7; goto EndBOA; }
if ( LargestNumber < 524288 ) { BitsOfAccuracy = 6; goto EndBOA; }
if ( LargestNumber < 2097152 ) { BitsOfAccuracy = 5; goto EndBOA; }
if ( LargestNumber < 8388608 ) { BitsOfAccuracy = 4; goto EndBOA; }
if ( LargestNumber < 33554432 ) { BitsOfAccuracy = 3; goto EndBOA; }
if ( LargestNumber < 134217728 ) { BitsOfAccuracy = 2; goto EndBOA; }
if ( LargestNumber < 536870912 ) { BitsOfAccuracy = 1; goto EndBOA; }
BitsOfAccuracy = 0;
EndBOA:
//This will set Units to 2^BitsOfAccuracy
int Units = 1;
for ( int i = 0; i < BitsOfAccuracy; i++ )
Units <<= 1;
//Create the UnitsMinusOne variable for use in logic operations
int UnitsMinusOne = Units - 1;
// compute the sine/cosinse of the radians used to
// rotate this image
int Sine = -cast(int)(sin(radians) * Units);
int Cosine = cast(int)(cos(radians) * Units);
// compute the size of the new surface being created
int X1 = -Height * Sine;
int Y1 = Height * Cosine;
int X2 = Width * Cosine - Height * Sine;
int Y2 = Height * Cosine + Width * Sine;
int X3 = Width * Cosine;
int Y3 = Width * Sine;
// figure out the max/min size of the new surface.
int MinX = Min(0, Min(X1, Min(X2, X3)));
int MinY = Min(0, Min(Y1, Min(Y2, Y3)));
int MaxX = Max(0, Max(X1, Max(X2, X3)));
int MaxY = Max(0, Max(Y1, Max(Y2, Y3)));
int NewWidth = MaxX - MinX;
int NewHeight = MaxY - MinY;
int NewSurface_Width = NewWidth >> BitsOfAccuracy;
int NewSurface_Height = NewHeight >> BitsOfAccuracy;
// Bitshift back from shifted down vars to drop extra bits
NewWidth = NewSurface_Width << BitsOfAccuracy;
NewHeight = NewSurface_Height << BitsOfAccuracy;
SDL_Surface* NewSurface = SDL_CreateRGBSurface
(
SDL_HWSURFACE, //SDL_SRCALPHA is already set due to amask being nonzero
NewSurface_Width, NewSurface_Height, 32,
rmask, gmask, bmask, amask
);
int pitch = sourceSurface.pitch;
ubyte[] oldPixels = cast(ubyte[])sourceSurface.pixels[0..(sourceSurface.pitch*sourceSurface.h)];
ubyte[] newPixels = cast(ubyte[])NewSurface.pixels[0..(NewSurface.pitch*NewSurface.h)];
uint NewIndex = 0;
uint OldIndex00; //(xy)
uint OldIndex01;
uint OldIndex10;
uint OldIndex11;
int R, G, B;
int OldX;
int OldY;
int FlooredOldX;
int FlooredOldY;
int CeilingOldX;
int CeilingOldY;
int Xsplash;
int Ysplash;
int OppXsplash;
int OppYsplash;
int ColorScalar;
int XCosIndex;
int XSinIndex;
int YCosIndex = (MinY * Cosine) >> BitsOfAccuracy;
int YSinIndex = (MinY * Sine) >> BitsOfAccuracy;
int MinXsin = (MinX * Sine) >> BitsOfAccuracy;
MinX = (MinX * Cosine) >> BitsOfAccuracy;
if ( SDL_MUSTLOCK(NewSurface) )
SDL_LockSurface(NewSurface);
int A;
for ( int y = 0; y < NewHeight; y += Units )
{
XCosIndex = MinX;
XSinIndex = MinXsin;
for ( int x = 0; x < NewWidth; x += Units )
{
OldX = XCosIndex + YSinIndex;
OldY = YCosIndex - XSinIndex;
FlooredOldX = OldX & ~UnitsMinusOne;
FlooredOldY = OldY & ~UnitsMinusOne;
Xsplash = OldX - FlooredOldX;
Ysplash = OldY - FlooredOldY;
OppXsplash = Units - Xsplash;
OppYsplash = Units - Ysplash;
FlooredOldX >>= BitsOfAccuracy;
FlooredOldY >>= BitsOfAccuracy;
CeilingOldX = FlooredOldX;
CeilingOldY = FlooredOldY;
CeilingOldX++;
CeilingOldY++;
OldIndex00 = (FlooredOldX << 2) + FlooredOldY * pitch;
OldIndex01 = OldIndex00 + pitch; // y+1
OldIndex10 = OldIndex00 + 4; //x+1
OldIndex11 = OldIndex01 + 4; //(x+1,y+1)
A = 0;
R = 0;
G = 0;
B = 0;
if (0 <= FlooredOldX && FlooredOldX < Width &&
0 <= FlooredOldY && FlooredOldY < Height)
{
ColorScalar = (OppXsplash * OppYsplash) >> BitsOfAccuracy;
A += ColorScalar * oldPixels[OldIndex00]; OldIndex00++;
R += ColorScalar * oldPixels[OldIndex00]; OldIndex00++;
G += ColorScalar * oldPixels[OldIndex00]; OldIndex00++;
B += ColorScalar * oldPixels[OldIndex00];
}
if (0 <= FlooredOldX && FlooredOldX < Width &&
0 <= CeilingOldY && CeilingOldY < Height)
{
ColorScalar = (OppXsplash * Ysplash) >> BitsOfAccuracy;
A += ColorScalar * oldPixels[OldIndex01]; OldIndex01++;
R += ColorScalar * oldPixels[OldIndex01]; OldIndex01++;
G += ColorScalar * oldPixels[OldIndex01]; OldIndex01++;
B += ColorScalar * oldPixels[OldIndex01];
}
if (0 <= CeilingOldX && CeilingOldX < Width &&
0 <= FlooredOldY && FlooredOldY < Height)
{
ColorScalar = (Xsplash * OppYsplash) >> BitsOfAccuracy;
A += ColorScalar * oldPixels[OldIndex10]; OldIndex10++;
R += ColorScalar * oldPixels[OldIndex10]; OldIndex10++;
G += ColorScalar * oldPixels[OldIndex10]; OldIndex10++;
B += ColorScalar * oldPixels[OldIndex10];
}
if (0 <= CeilingOldX && CeilingOldX < Width &&
0 <= CeilingOldY && CeilingOldY < Height )
{
ColorScalar = (Xsplash * Ysplash) >> BitsOfAccuracy;
A += ColorScalar * oldPixels[OldIndex11]; OldIndex11++;
R += ColorScalar * oldPixels[OldIndex11]; OldIndex11++;
G += ColorScalar * oldPixels[OldIndex11]; OldIndex11++;
B += ColorScalar * oldPixels[OldIndex11];
}
A >>= BitsOfAccuracy;
R >>= BitsOfAccuracy;
G >>= BitsOfAccuracy;
B >>= BitsOfAccuracy;
//X = x >> BitsOfAccuracy;
//Y = y >> BitsOfAccuracy;
newPixels[NewIndex] = A; NewIndex++;
newPixels[NewIndex] = R; NewIndex++;
newPixels[NewIndex] = G; NewIndex++;
newPixels[NewIndex] = B; NewIndex++;
XCosIndex += Cosine;
XSinIndex += Sine;
}
YCosIndex += Cosine;
YSinIndex += Sine;
}
if ( SDL_MUSTLOCK(NewSurface) )
SDL_UnlockSurface(NewSurface);
if ( NewSurface == null )
throw new Error( "CreateRotatedSurface(): resulting Surface is null" );
return NewSurface;
}
private int Min( int a, int b )
{
if ( a < b )
return a;
else
return b;
}
private int Max( int a, int b )
{
if ( a > b )
return a;
else
return b;
}
|
|
|
| Back to top |
|
|
clayasaurus
Joined: 21 May 2004
Posts: 857
|
| Posted: Mon May 15, 2006 6:08 pm Post subject: |
|
|
Thanks, I'll put these on the Arc v.2 TODO list  |
|
| Back to top |
|
|
JoeCoder
Joined: 29 Oct 2005
Posts: 294
|
| Posted: Sun May 21, 2006 9:10 pm Post subject: |
|
|
Ok, two disclaimers:
First, I haven't been keeping up with the development of ARC, so if these would be wretched to implement, forget them.
Second, I didn't read through all of the code above, but only skimmed it.
For collision detections, it looks like you're testing every object vesus every other object, which has a complexity of O(n^2). If you sort all of your objects by say their x location using a radix sort O(n) and then only check for collision with objects a few indexes up and down from one another on the sorted list (another O(n)), your total complexity is still O(n). And after this, you can do the advanced per-pixel collision detection on the remaining. By using this axis sorting algorithm, it should allow you to check several orders of magnitude more collisions in the same amount of time.
I have a radix sort I wrote in c++ that would be easy to translate to D. It can sort positive and negative ints and floats in linnear time; usually over ten million per second on any reasonably fast pc. Let me know and you can have it.
And for rotating sprites, why not just put each one on an opengl quad and rotate that? Again, this should be orders of magnitude faster than anything done in software. Remember to see disclaimer #1 |
|
| Back to top |
|
|
Phr00t
Joined: 03 Mar 2006
Posts: 203
|
| Posted: Sun May 21, 2006 9:40 pm Post subject: |
|
|
| Quote: | | Let me know and you can have it. |
Working this slick collision detection into ARC would be great -- I'm just not sure how you would insert and use it?
Have a function fastCollisionCheck(<linked list>,<callback>) function that would take in a linked list of Sprites, and call the callback function (which has arguments for the two sprites in question) when a collision is detected? |
|
| Back to top |
|
|
JoeCoder
Joined: 29 Oct 2005
Posts: 294
|
| Posted: Sun May 21, 2006 11:45 pm Post subject: |
|
|
I've had bad luck with linked lists in most cases myself. Having so many pointers tears up my cache when iterating through a list of 100k objects and maintianing reasonable framerates (yes, I'm an optimization freak).
In the past (C++) I've use something similar to an STL Vector that holds a reference to each object and also maintains a key to sort by. Unlike a Vector, it has constant removal times (instead of linnear) because it simply copies the reference to the last element over whatever element was deleted and decrements the length. I call it "Horde" and I believe Clay already has the source to it that I gave him earlier. I should complete it by translating my radix sort into D and adding it as one of the methods. If you're anxious, here's my entire c++ library as I left it before moving to D. Do whatever you want with it. But if you want, I can go ahead and make a D version, since I'll need to anyway for my own game engine. However, it won't be much use if you're using linked lists for everything.
Off-topic and I can start a new thread if it goes anywhere, but has anyone had any luck with ogg-vorbis support in D? I remember seeing Clay list it somewhere as a planned feature. I currently have support for buffered audio playback using OpenAL in my engine and support for dropping in any type of audio format (wave is currently supported), and I've translated the vorbis_decode that's part of the SDK to D (and it works), but I haven't been able to get random access reads from a vorbis file. </hijack thread>
Edit: Actually, I'm pretty sure you can use quicksort and mergesort on linked lists, but without random access, they'll probably be slower. |
|
| Back to top |
|
|
clayasaurus
Joined: 21 May 2004
Posts: 857
|
| Posted: Mon May 22, 2006 11:03 am Post subject: |
|
|
| JoeCoder wrote: |
For collision detections, it looks like you're testing every object vesus every other object, which has a complexity of O(n^2). If you sort all of your objects by say their x location using a radix sort O(n) and then only check for collision with objects a few indexes up and down from one another on the sorted list (another O(n)), your total complexity is still O(n). And after this, you can do the advanced per-pixel collision detection on the remaining. By using this axis sorting algorithm, it should allow you to check several orders of magnitude more collisions in the same amount of time.
|
That sounds good, I'll add it to the Arc v.2 TODO list. The function will probably take an inout array or linkedlist (for phr00t  ) of Sprites, quickly sort them and then perform collision checks on all of them and somehow give a way for the user to handle the collisions appropriately.
My question would be, would I have to compute how many indexes up/down I would have to check or would this be a constant, and/or how would I get this number?
| Quote: |
I have a radix sort I wrote in c++ that would be easy to translate to D. It can sort positive and negative ints and floats in linnear time; usually over ten million per second on any reasonably fast pc. Let me know and you can have it.
|
Sounds nice, yes I would be interested and it probably is in your C++ lib you linked already.
| Quote: |
And for rotating sprites, why not just put each one on an opengl quad and rotate that? Again, this should be orders of magnitude faster than anything done in software. Remember to see disclaimer #1 |
I won't use the software rotation for a real time application. My problem is with perpixel collision and rotation. For perpixel collision I use a collision map, and in order to make I collision map I have to extract which pixels are transparent and which pixels are not. I get the pixels from the SDL_Surface* that I load my image into.
In order to rotate a perpixel collision, I would have to get the transparent and solid pixels after it has been rotated so that I can make a collision map with it.
To get these values, I use software rotation on my SDL_Surface *. If there is a faster way to do this with OpenGL, please tell me. |
|
| Back to top |
|
|
JoeCoder
Joined: 29 Oct 2005
Posts: 294
|
| Posted: Mon May 22, 2006 2:45 pm Post subject: |
|
|
I've never implemented axis-sorting before, but I think if you calculate a radius for every object (sprite), you can go up and down the array for each item and stop once you arrive at one that has a greater x distance than that radius. This ends up doing some checking multiple times, but it's the only foolproof way I know of; and that should still be minimal as long as your sprite density is low.
As for your collision detection, I don't know a better way to do that in OpenGL (hardware occlusion query?), but you could write an algoithm that traces your unrotated sprite and returns an array of points. You could then rotate that as necessary and perform a point-inside-polygon test for both objects against one another.
The tracing would be the hardest part, but it's been done before in 3D with the marching cubes algorithm. I don't know much more about it.
I think I'm going to spend the afternoon trying to get seeking working with ogg-vorbis in D, and maybe port radix if I get frustrated with that. I'll be on AIM if you want to discuss this more. |
|
| Back to top |
|
|
clayasaurus
Joined: 21 May 2004
Posts: 857
|
| Posted: Mon May 22, 2006 5:27 pm Post subject: |
|
|
What do you mean by, 'greater x distance then the radius' ?
Your collision detection solution sounds pretty good, and instead of 'tracing' i could just get the points from the pixels on the sprite. However, a 'point inside polygon' wouldn't work, because my polygons are just squares. I'd have to check and see if the points touch eachother, much like I do now. |
|
| Back to top |
|
|
JoeCoder
Joined: 29 Oct 2005
Posts: 294
|
| Posted: Mon May 22, 2006 5:42 pm Post subject: |
|
|
Suppose you have your sorted list of sprites with the following sample data:
| Code: | Name : A B C D E
X-pos : 1 3 4 7 8
Radius: 5 2 3 1 1 |
Sprite A would need to check for collisions with B and C, since it's radius extends 5 units to the left and right, and B and C with positions 3 and 4 are within that range.
B will check for collisions with A and C since 3-2 exends us lefward to position 1 where A is and C is within the range of 3+2.
C checks collision with B and D, D checks with E, and E checks with D. It could be even faster if these redundant checks could be removed.
For the per-pixel collision, tracing would still be faster than marking every pixel as a point, since it would leave you with far fewer points. And if every pixel is a point, that's not a nice polygon that outlines your sprite and makes the point-in-polygon algorithm fail. But like I said, I don't know an algorithm to trace a sprite.
Finally, I haven't been able to get anywhere with ogg vorbis seeking. My frustrations and code are all availible in the derelict forum. I'm going to work on adding radix sort to horde now.
Edit: Know of any other multimedia libraries under an lgpl or bsd type license that will let me decode vorbis with seeking? |
|
| Back to top |
|
|
clayasaurus
Joined: 21 May 2004
Posts: 857
|
| Posted: Tue May 23, 2006 7:19 am Post subject: |
|
|
For sorting, would it be possible to sort by both X and Y to remove some redundance? Or if there was some way to combine X and Y values into one structure and sort those? Also, I do plan on removing redundant checks like if B is checked with A then I won't check A with B again.
I understand now what you mean now by tracing. Definitely possible to do, might be a little challange to do with a complete but minimal outline. I like it, though, because I can get rid of the perpixel gap, and perpixel collision will be much cheaper memory and perhaps processing wise.
Sorry, I can't help you with OpenAL as I do not know a whole lot about it. |
|
| Back to top |
|
|
JoeCoder
Joined: 29 Oct 2005
Posts: 294
|
| Posted: Tue May 23, 2006 10:36 am Post subject: |
|
|
You can sort by both x and y, but you'll just have to make two passes unless you can figure out a better way on your own. I'd recommend using axis sort (single or double) to remove ~95? of your checks, then a distance check (compare against distance squared to remove the need for sqrt()); or your box check, and then the per-pixel stuff. But you probably had it figured out that way anyway.
Good news: I've got my radix sort most of the way ported to D. It's still coming back with some inaccuracies in the results when sorting large numbers, but I'm able to sort about 14 million objects per second by any key, regardless of object size. I tried the built in array.sort, but was only able to get about 2 million per second and the results weren't sorted, but maybe I did something wrong. array.sort seems to be O(n*ln(n)), verses O(n) for radix, but should probably still be faster for sorting small arrays < 100-1000.
When it's complete, using it should be as easy as this:
| Code: | Horde!(MySpriteClass) sprites = new Horde!(MySpriteClass);
for (int i=0; i<100000; i++)
sprites.add(new MySpriteClass);
// other stuff
sprites.sort(sprites[0].x); // use the x location as a key
|
FYI, I do have openal working perfectly, but openal takes buffers of data that have to come from somewhere, and since I want more than just wave file support, that's why I need seeking in ogg vorbis, to allow me to send just a few buffers at a time instead of a whole 50MB decompressed file.
I need to submit my additions to OpenAL that I used to make it work back to Derelict, but I was looking at the Bindings version of OpenAL, and it looks like they've gone further than I have by adding alut and mac support. Why is it that Bindings and Derelict both exist to accomplish the same purpose? |
|
| Back to top |
|
|
clayasaurus
Joined: 21 May 2004
Posts: 857
|
| Posted: Tue May 23, 2006 8:29 pm Post subject: |
|
|
Bindings and Derelict accomplish slightly different purposes, derelict loads the libraries at runtime through dll's or .so's and for bindings you must provide a static library to the compiler. See http://derelict.dsource.org/ for more details.
Radix sort sounds promising, can't wait to see it in action  |
|
| Back to top |
|
|
JoeCoder
Joined: 29 Oct 2005
Posts: 294
|
| Posted: Sat May 27, 2006 12:06 am Post subject: |
|
|
Well, bad news and good news. Bad news is I miscounted my zeroes and was only sorting 1.4 million objects per second, rather than 14 million. The good news is that I was able to optimize it back up to about 8 million per second (p4, 2.8ghz), when sorting by 4-byte keys. Longs and doubles take twice as long.
The complete core library from my engine, including the above, is available here. I think you've seen most of it before. Let me know if you have any questions or find bugs.
BTW, I was able to get ogg vorbis working with seeking and it looks like I'll have an ideal solution when I combine that with buffered playback /w OpenAL. Perhaps I could help when it comes time to add audio support to Arc? |
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
Powered by phpBB © 2001, 2005 phpBB Group
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
