Print Story A Eureka Moment
Logic & Maths
By codemonkey uk (Thu Oct 02, 2008 at 03:00:32 PM EST) (all tags)
Related to this.  Today, at lunch time, I was messing about with World Canon, and bumped once again into a problem with the algorithm I use to drill down into the hierarchy.  The problem is superficially straight forward, given a triangle determine if a point is inside it.  However, IEEE throws you a curve-ball occasionally, and a point sat on, or close to an edge or vertex can fall through the cracks.  In the past I have used a combination of epsilon values, nasty work-arounds and generally avoiding situations that cause this to be a problem.

I had spent some time - quite a lot of time - when I first wrote that code, researching the problem and found neither prior art addressing the issue or a solution of my own that I was happy with.

This afternoon, whilst working on a totally unrelated piece of code (new game project, Wii/PS2/PSP, very cool licence), I had a Eureka moment...  

This evening after work I implemented the new algorithm.  It is very simple, it works perfectly, and is more efficient than multiple containment tests.  I have created a lovely single page document describing it, here:


< Scargills in better suits? | sounds like the people upstairs are teaching their dog to bark to "carmen" >
A Eureka Moment | 10 comments (10 topical, 0 hidden) | Trackback
In The US by dev trash (2.00 / 0) #1 Thu Oct 02, 2008 at 03:49:25 PM EST
That code would belong to your employer.  They own your thoughts here in teh states

Not PS3!? by ucblockhead (2.00 / 0) #2 Thu Oct 02, 2008 at 06:24:48 PM EST
Oh well...tell me when you have something to brag about on the PSP.

BTW: I was playing XCom:Apocalypse last week.  Yay Steam!
[ucblockhead is] useless and subhuman

Heh - cute by gazbo (4.00 / 1) #3 Thu Oct 02, 2008 at 11:48:59 PM EST
From your summary I was waiting for some horrible bit-level shenanigans involving magic numbers and a detailed knowledge of IEEE specs.  I think your solution may be simpler than that.

I recommend always assuming 7th normal form where items in a text column are not allowed to rhyme.

That's what I was expecting by Breaker (2.00 / 0) #4 Fri Oct 03, 2008 at 12:18:31 AM EST
But that was a pretty good explanation and a very simple algorithm.

Daft questionfor codemonkey - when I used to do graphics programming everything was stored as int's then divided by 100 at the point of use (this was back in the x386 days, BTW when floating point stuff was slow).  Is that approach no longer feasible?

[ Parent ]
reply by codemonkey uk (4.00 / 1) #5 Fri Oct 03, 2008 at 12:34:28 AM EST
What you describe is adhoc fixed-point arithmetic, and it does have some application in specific sub domains within game programming (unreal engine sends angles over the network in a fixed point format, some of the older portable hardware platforms have limited hardware support for floating point), but for the vast majority of problems using the hardware native floating point unit is vastly superior to implementing fixed-point maths in software.

Keep in mind that modern GPU pipelines operate on floating point values, and the better graphics cards (including Xbox360) even support floating point framebuffers.

--- Thad ---
Almost as Smart As you.

[ Parent ]
Interesting. by Breaker (2.00 / 0) #6 Fri Oct 03, 2008 at 12:53:57 AM EST
Thanks for the reply.  Last time I did any serious graphic work the graphics card would do you frambuffers and that was about it - I'd overlooked the "new" GPU stuff.

[ Parent ]
good old mode 0x13 by codemonkey uk (2.00 / 0) #7 Fri Oct 03, 2008 at 01:02:29 AM EST
those were the days...

--- Thad ---
Almost as Smart As you.
[ Parent ]
Int 10 by Breaker (2.00 / 0) #10 Fri Oct 03, 2008 at 05:47:15 AM EST

Great days!

[ Parent ]
Good job, but always beware by johnny (2.00 / 0) #8 Fri Oct 03, 2008 at 02:37:27 AM EST

The Floating-Point Error.
Buy my books, dammit!
Nice. by wiredog (2.00 / 0) #9 Fri Oct 03, 2008 at 04:58:52 AM EST

Earth First!
(We can strip mine the rest later.)

A Eureka Moment | 10 comments (10 topical, 0 hidden) | Trackback