Show us yer programming projects!

Coders forum. Discuss techniques, swap code snippets, ask for help etc. relating to all forms of software development.
Post Reply
User avatar
pogo
Sheepie Whore
Sheepie Whore
Posts: 14180
Joined: Tue Sep 10, 2002 8:28 pm 0
Yahoo Messenger: BrassSparrow
Location: County Durham

Re: Show us yer programming projects!

Post by pogo »

PaulCunningham wrote:There's no 'magnitudes harder' if you don't need to consider rotations. You simply scale your world geom so your ellipse becomes a unit sphere.
Yes, you could, but I don't think anyone would call doing ellipsoids without rotation realistic. You can get away with it for spheres if they have no friction, and it's easier to ignore as a sphere looks the same when rotated, but it would just look odd for ellipsoids. And even then there are multiple problems. Your collision response cannot take place in this scaled space, so you need to scale everything back if you want a bounce and not just a hit-test. You have to scale the world multiple times, once for each ellipsoid with different geometry or [fixed] rotation. And if there are any spheres or circles in your world they become ellipsoids, so you have the same ellipsoid-sphere problem you were scaling to avoid.

The problem is while polygon-polygon intersection problems (and so hit-tests) can be solved with linear equations, and polygon-sphere or sphere-sphere need quadratic equations, ellipsoid-sphere, ellipsoid-ellipsoid, ellipsoid sphere (and annoyingly cylinder-edge) problems result in quartic equations. They are in my book magnitudes harder, as although solvable algebraically the solution is far more difficult and subject to far worse problems with rounding/fp errors. When I had to include cylinders in a physics engine they had realistic physics when rolling on a flat surface but when colliding with another object used a prismatic approximation.
..based on the same principal and uses sweep tests so you don't have to use sub division if you don't want to.
I prefer subdivision in cases like this. First if you have a complex or detailed world then you need to do sweep tests against each surface you might collide with, and decide which one you hit first. Second doing a sweep test for the end collision is harder: the points where it hits lie on a circle, so you have to do a ray-circle test and solve a quadratic. None of this is too difficult but it's a lot of extra logic and code when all you need to do is change the time by 1/2, 1/4, 1/8, ... and re-run your hit-test code to determine when the collision happened as precisely as you need. For a single object the difference in performance is not an issue.
User avatar
teamonkey
Sheepie Whore
Sheepie Whore
Posts: 12082
Joined: Thu Jun 13, 2002 1:07 am 0
XBL Gamertag: itsthetaste
PSN: teamonkey_ca
Contact:

Re: Show us yer programming projects!

Post by teamonkey »

pogo wrote:Second doing a sweep test for the end collision is harder: the points where it hits lie on a circle, so you have to do a ray-circle test and solve a quadratic.
No you don't. When performing your collision test you pad out each collision surface by the radius of the ball. Then you model the ball as a point and the swept circle becomes a simple line segment intersection test.
User avatar
gumboot
Baaaaaaa!
Baaaaaaa!
Posts: 7652
Joined: Sun Aug 26, 2007 3:42 am 0
Location: trumpstain!

Re: Show us yer programming projects!

Post by gumboot »

teamonkey wrote:No you don't. When performing your collision test you pad out each collision surface by the radius of the ball. Then you model the ball as a point and the swept circle becomes a simple line segment intersection test.
While both of these statements may be true, they can't be simultaneously true in the same universe.

If you pad a rectangle such that you end up with a larger rectangle then the distance from the true corner to the padded corner is r*sqrt(2.0), but the point should be able to pass within as little as r of that corner without colliding.

So if you pad your rectangle correctly, with rounded edges, then you're no longer doing a simple line segment intersection test at the corner.
User avatar
korruptor
Baaaaaa!
Baaaaaa!
Posts: 4291
Joined: Sun Sep 22, 2002 10:35 am 0
Location: Under The Northern Lights
Contact:

Re: Show us yer programming projects!

Post by korruptor »

Or, you don't round the edges, and everything is fine. :D
"Don't go into a trance boys..." :: DJ Mixes
User avatar
zip accident
Sheepie Whore
Sheepie Whore
Posts: 13928
Joined: Sun Feb 20, 2005 1:58 pm 0
Location: Bristol, UK

Re: Show us yer programming projects!

Post by zip accident »

korruptor wrote:Or, you don't round the edges, and everything is fine. :D
That is an interesting definition of "everything".
"My way is the way of not fighting":- the book of Enter the Dragon.
User avatar
teamonkey
Sheepie Whore
Sheepie Whore
Posts: 12082
Joined: Thu Jun 13, 2002 1:07 am 0
XBL Gamertag: itsthetaste
PSN: teamonkey_ca
Contact:

Re: Show us yer programming projects!

Post by teamonkey »

gumboot wrote:
teamonkey wrote:No you don't. When performing your collision test you pad out each collision surface by the radius of the ball. Then you model the ball as a point and the swept circle becomes a simple line segment intersection test.
While both of these statements may be true, they can't be simultaneously true in the same universe.

If you pad a rectangle such that you end up with a larger rectangle then the distance from the true corner to the padded corner is r*sqrt(2.0), but the point should be able to pass within as little as r of that corner without colliding.

So if you pad your rectangle correctly, with rounded edges, then you're no longer doing a simple line segment intersection test at the corner.
The way I did it was to make your line intersection test tell you if your ball velocity line segment just misses the wall line segment. korruptor checks if s and t are both in the range 0-1 and returns -1 on fail, but if, say, s is a little bit less than 0 or greater than 1 then you can do an additional very simple corner check. In fact, I think you can get rid of the /div bit then s and t are returned in useful distance units instead of normalised to between 0 and 1.

I did this utterly shit paint picture:
Image

There's only a small square area (each side the radius of the ball) on each corner. The line intersection test can tell you if you've collided in that square. A line-circle test within that square is trivial.
User avatar
korruptor
Baaaaaa!
Baaaaaa!
Posts: 4291
Joined: Sun Sep 22, 2002 10:35 am 0
Location: Under The Northern Lights
Contact:

Re: Show us yer programming projects!

Post by korruptor »

zip accident wrote:
korruptor wrote:Or, you don't round the edges, and everything is fine. :D
That is an interesting definition of "everything".
It's Arkanoid man.
"Don't go into a trance boys..." :: DJ Mixes
User avatar
gumboot
Baaaaaaa!
Baaaaaaa!
Posts: 7652
Joined: Sun Aug 26, 2007 3:42 am 0
Location: trumpstain!

Re: Show us yer programming projects!

Post by gumboot »

Well, I remember what I did, now... (I actually have my old code, but because I used complex data types to implement what I worked out on paper, the principle is obfuscated).

During the line segment test, if you miss but pass within r of the end of the line (according to a rectangular range test, equivalent to teamonkey's enlarged box), then proceed with the following test on the nearest endpoint (corner) of that line segment:
  1. Centre the problem on the starting position of the ball.
  2. Rotate the problem so that the path of the ball is directly along the X axis.
  3. Test that the new Y position of the corner is within r of the X axis (would there ever be a collision on this path, at any point in the past or future?) and bail out as appropriate. [actually this is unneccessary because of the precondition of this test, so just assert() it]
  4. Test that the new X position of the corner is positive (are we heading towards it?) and bail out as appropriate.
  5. Given a right-angled triangle with an hypoteneuse r, and another side the length of the Y value of the corner, find the length of the third side.
  6. Subtract the length of the third side from the X position of the corner. This is the point along the path at which the ball first touches the corner. Scale it appropriately to convert it into time to determine when the collision will occur.
  7. Rearrange your arithmetic to clear out all the ugly, unnecessary bits and defer the ugly, necessary bits until after you've determined that this is the collision that you care about.
Obviously r is the radius of the ball.

Although I haven't looked closely. I assume the discussion is already past this stage in solving the problem.

There are potentially simpler principles you could start with to get to the same solution, but in theory you can get to the same solution from all of them so long as you rearrange and optimise your arithmetic competently. I just did it that way because it was the first solution that came to mind.
User avatar
Devlin
Baaaaa!
Baaaaa!
Posts: 1380
Joined: Tue Aug 02, 2005 10:53 pm 0
XBL Gamertag: Anarkhis
Location: Bradford, Sacred Sod of God's Own County
Contact:

Re: Show us yer programming projects!

Post by Devlin »

Currently working on an old sidebar gadget I made for vista/win7, the original version I wrote leaked memory like stupid.
I've rewritten it twice, and managed to get it to a state where it still leaks memory, but fairly slowly.

I don't know what i'm doing wrong, it's written in javascript(the standard for the gadgets on cursory source-noseying)

You can get it from Here if you want to have a look-see.

If you don't have Vista/Win7(or the sidebar) you can load it in IE or Firefox.

If you come up with a solution, please post here!
User avatar
koogy
Baaa!
Baaa!
Posts: 475
Joined: Thu Aug 31, 2006 11:16 am 0

Re: Show us yer programming projects!

Post by koogy »

> http://www.devlsoft.co.uk/dl/OtaClock.gadget.zip

The requested URL /dl/OtaClock.gadget.zip was not found on this server.
User avatar
Devlin
Baaaaa!
Baaaaa!
Posts: 1380
Joined: Tue Aug 02, 2005 10:53 pm 0
XBL Gamertag: Anarkhis
Location: Bradford, Sacred Sod of God's Own County
Contact:

Re: Show us yer programming projects!

Post by Devlin »

Oof. I pulled them off the site because I just couldn't get them working properly at all.

These were horribly broken. Can't change the link but i'll attach it here.

Javascript makes me wanna go emo ~

This version doesn't leak memory, BUT it only semi-works as well. My code skills suck ass.
Attachments
OtaClock.gadget.zip
(14.93 KiB) Downloaded 25 times
User avatar
beerman
Baaaaa!
Baaaaa!
Posts: 1305
Joined: Wed Dec 24, 2003 11:22 pm 0
Location: The Beercave
Contact:

Re: Show us yer programming projects!

Post by beerman »

First mentioned this a fair few pages back, but I finally put together a build of that arena shooter I've been working on.
's called Gun Bastard :twisted:
"even had I suspected then the truly horrifying suffering and amazing loss of life that would be caused by our well-meaning enterprise... I'd have done it anyway. Only more so."
Lagertron for Android It's Robotron at the pub!
My stuff
User avatar
oddbob0
Baaaaa!
Baaaaa!
Posts: 1727
Joined: Mon Mar 01, 2004 7:43 pm 0
Location: Liverpool

Re: Show us yer programming projects!

Post by oddbob0 »

About fucking time :D
\m/
User avatar
oddbob0
Baaaaa!
Baaaaa!
Posts: 1727
Joined: Mon Mar 01, 2004 7:43 pm 0
Location: Liverpool

Re: Show us yer programming projects!

Post by oddbob0 »

Coming on nice so far! Needs a bit of balancing with the power meter (and some visible scoring, obv) as once you're powered up it's well hard to snuff it. So far though, great progress!

Keep gooooing.
\m/
User avatar
beerman
Baaaaa!
Baaaaa!
Posts: 1305
Joined: Wed Dec 24, 2003 11:22 pm 0
Location: The Beercave
Contact:

Re: Show us yer programming projects!

Post by beerman »

Thanks, dude.
Go a ways to go before I catch up with the eyeball-fucking lunacy you've been kicking out lately, but it's coming along :D

Haven't quite found the balance yet with the power meter. Earlier versions had a constant power drain, but when it got too low it made you annoyingly weak, and that's just no fun.

Current thinking is I want to add a Halo-style delayed recharge up to about 50% power, and then anything above that sends the weapon system into overdrive and you become a black-winged, plasma-spewing avatar of Death :twisted:
"even had I suspected then the truly horrifying suffering and amazing loss of life that would be caused by our well-meaning enterprise... I'd have done it anyway. Only more so."
Lagertron for Android It's Robotron at the pub!
My stuff
Post Reply