Open CL 3D Vertex Collision (hit testing) (Composition by dust)

Author: dust
License: MIT
Date: 2010.07.28
Compatibility: 10.6
Categories:
Required plugins:
(none)

so my daughter loves this ipad game "angry birds" its a tower defense type of game in 2d. probably made with something like cocos2d or unity3d with no z depth. so i decided to see if i could wip up something in an evening similar but in unity 3d using forces etc...

well i accomplished that task as unity3d makes things like physics very simple. i began thinking how hard would it really be to do something similar in QC. thinking i would start with a box2d approach and track vertex positions of sprite or something. i dug out some 2d fluid texture maya mel scripts and thought it might be possible to calculate a collision by converting UVs to pixels space and evaluating a hit based on texture data in realtime.

i pondered on this idea for a bit and then said to my self why not just check all the vertex points (xyz) for equivalence using the size of a model as a threshold. so using the handy get component mesh tool, i simply iterated through all my vertex's and conditionally checked x,y,z on each vertex until the two models collided. so this was fairly simple could have been done in java script instead of an iterator. unfortunately the frame rate for comparing two models with a vert count of 420 was only giving me around 30 fps on my machine. which is decent and i was happy with the fps as i could check for collisions and then apply forces based on those collisions etc.

still 30fps with only two low poly count models wasn't cutting it as quartz has all this open cl multi-threaded stuff that was built for this type of thing so i decided open cl was going to be the best way to detect if two models collide in QC.

so at first i thought i would just break down and iterate through two sets of vertexes checking for hits like i did before but after looking at the openCL reference guide and noticing all these sweet matrix and math stuff built in. i figured i could just use a distance function and check for when the models where within the threshold of there respective scales to detect a hit. so this was a different approach to the same problem. the results are similar but by doing this in on two different threads in parallel i was able to get my fps up over 100 at times in just a few lines of code.

so both these patches work for hit testing in 3d with rotations etc.. i still need to do some more testing and get a vertex by vertex comparison made in open cl instead of distance function so that eventually i may be able to do some rudimentary physics calculations with inertia and forces etc..

i don't know if this will help anyone but could be used to make a simple shooter type of game or projectile / target type of thing in 3d with your own models.

PreviewAttachmentSize
vertexCollisions.zip50.45 KB

cybero's picture
Re: Open CL 3D Vertex Collision (hit testing) (Composition ...

Nicely lit spheres. Would like to see it triggering OpenCL Particles, even though the Particle System patch does a fine job.

dust's picture
Re: Open CL 3D Vertex Collision (hit testing) (Composition ...

i had some cl particles in mind while i was making this. haven't got that far yet, need to pull up one of your cl particle patches and take a look, as this sort of hit testing i think could work well in a particle context. i still need to get CL down as i think it could be just as handy if not more so than a JS patch. i'm still getting used to CL, it seems everything is returned in a structure even an "int" etc... maybe i'm doing something wrong. CL doesn't seem as flakey as it was in the past crashing my machine while running the apple default kernel etc.. so needless to say that things seem more stable, i should start using it more often. i'm surprised that most of the cl stuff i have tried from the reference guide work in qc but then some things that work in cuda like using a float as an array don't seem to work only float4's

dust's picture
Re: Open CL 3D Vertex Collision (hit testing) (Composition ...

the spheres have nice lighting until you turn on shadows and go full screen, things get all messed up. thats why the particle system is out side of light patch as the the blend mode gets all messed. you will notice it as well with the vertex displays if you go full screen with shadows on.

gtoledo3's picture
Re: Open CL 3D Vertex Collision (hit testing) (Composition ...

I wonder why it doesn't work on my system? Are you guys on 10.4...

I guess I'll give you the benefit of the doubt, but it's so disturbingly similar conceptually....I'm not in the mood for a flame war.

dust's picture
Re: Open CL 3D Vertex Collision (hit testing) (Composition ...

me either george, flaming isn't really productive. i was honestly hurt the last time we made similar compositions, and my reactions where pretty crass and un called for as you where just being protective of your body paint work and wanted to keep it a little more magical.

then i come along and share a similar composition kind of ruining the trick for you so i totally understood where you where you where coming from. i have learned from that experience and have no intentions of going down that road again. i do think you are providing people with very good material although i don't know how you find the time somedays.

like i said honestly i was concurrently making a hit test patch, and was unaware you had just made a similar 2d version. ironically the body paint petri things where imho, more identical in execution than these patches are even though we are both using conditional logic to perform the test.

no worries my friend no need to flame, as i'm not letting things like that get to me. last year i went through a bad divorce so i wasn't in a very good head space. you shouldn't let similar comps bother you. i mean you wouldn't get mad at TB for chiming in saying hay man i made that java script tester months ago. (where has TB been anyways ?)

i did see your post before i posted this patch and did think of not posting this but thought it may serve the greater good as someone may be able to get some use from it. that is my hopes anyways as that is the only the reason i post comps.

(well except for my illusion i kind of wanted people to trip out watching that)

gtoledo3's picture
Re: Open CL 3D Vertex Collision (hit testing) (Composition ...

No biggie...

The thing about my hit test is that instead of being based on an iterator, you actually place it IN an iterator, and than makes hit tests at each vertex (or whatever), which makes it work in 3 dimensions effectively in SL or Leopard (though I did add in an extra Z coord to my logic for that). To me, that made more sense.

cybero's picture
Re: Open CL 3D Vertex Collision (hit testing) (Composition ...

Interesting that it doesn't work on your system setup, GT. A pity. It works well enough upon mine - 10.6.4 BTW.

The OpenCL collision routine is very interesting, as a matter of interest, does that even load on the Editor stage for you or does it disappear?

I ask in part because when trying to create a novel way of gridding up each spectrum band and demultiplexing the results in OpenCL I got some peculiar "we shall name ourselves" action going on with the inputs, outputs.

I've seen that happen before, seen the inputs and outputs assume their correct disposition once I've properly declared the __kernel - the changes continued down the line - not rendering at this time BTW , but they still renamed themselves before assuming a rather odd number order - seemed more alphabetical based than numeric based.

Odd.

Also had a similar behaviour down the the line upon some math expression outputs inside of a macro.

Now I ask you , is that normal ?

Or is my machine haunted ?

LOL. :-)

dust's picture
Re: Open CL 3D Vertex Collision (hit testing) (Composition ...

im more or less trying to figure this out so i can do some rigid body types of simulations in QC. although your idea of having the hit tester inside the iterator was a motivation to building a cl kernel as i would really like to fill up a cube with a bunch of spheres all wobbling when they hit each other.

gtoledo3's picture
Re: Open CL 3D Vertex Collision (hit testing) (Composition ...

Just had to restart QC for some reason.

cybero's picture
Re: Open CL 3D Vertex Collision (hit testing) (Composition ...

Porting over from CUDA or other GPU computing transferrable to QC, like command line OpenCL tend to not have __kernel QC specific syntax. IMETD, some porting is trivial, whilst other items can look totally dandy only after a considerable amount of re-organisation & not only at the __kernel declaration.

I find I'm liking OpenCL for image processing & creation, to plain numeric and also to structural inputs.

Noise patterns too, I find worthwhile exploring . I do think that it is pretty endless. Congruency and balance Local Work sizes should be appropriate fractions of global work size and so on. That's when declaring them within the OpenCL kernel.

Mixing structures, best done with a balanced / congruent member count.

dust's picture
Re: Open CL 3D Vertex Collision (hit testing) (Composition ...

we must have the same ghost in our machines. some very peculiar things have been happening to me with CL that do not seem to make since. like changing the name of a global variable Cl is says NO sometimes even if things are properly declared.

or it remembering a previous index count and only populating then new output up till the old index count. like if i was using a index count of 30 but change the model to something with larger count CL will only populate the new output up to the old count, even when not sharing memory space. like when doing something like float4[tid*width+i];

im just telling myself its because i'm still figuring out CL but things like changing a variable name for instance as example changing float hitx to float hit. an the kernel just didn't like that. nothing different than an x. not hit.x but just "hitx" works perfect but "hit" didn't.

i almost gave up because that is just to odd for me as the kernel wants to remember the old variable and not honor the new variable. i was under the impression that the gpu only has texture caching so i don't know how the ghost is getting into my kernels.

some things i guess are just volatile and it gets confusing real quick as sharing the same TID with another reference to that shared memory space will give you garbage as the compiler will just reuse the product from from first reference. i think there are ways to get around things like this by using synchronizations etc..

i think i should take a class in algebra as that will probably help me understand how things work a bit better while working with matrix's. there seems to be whole bunch of letter related matrix transformation things that you need to know and the only number other than the data contained in the matrix is the size if the memory etc...

but then there are all these functions like "dot" that just do the algebra for you. algebra is one of my weaker points as i like to be able to do the math stuff by hand like converting dec to binary or what ever. as i have no problem converting the algebra to machine language but sometimes im like WTF while solving or formulating an a sorting algorithm that is 4 dimensions deep let alone swapping those memory spaces with other 4d structures etc...

i tell you one thing QC makes CL programming awesome as well GL programing awesome as the kernel set up is all handled for you. to me that is worth some of the limitations.

cybero's picture
Re: Open CL 3D Vertex Collision (hit testing) (Composition ...

was that meant for twitter :-) ?

gtoledo3's picture
Re: Open CL 3D Vertex Collision (hit testing) (Composition ...

No, I meant it did work after a restart.

cybero's picture
Re: Open CL 3D Vertex Collision (hit testing) (Composition ...

One of the best sections of that movie. Industrial history. & the ramifications just keep on rolling on ..... & would seem to be heading IBM's way. The law doesn't keep up with what the businesses do.

dust's picture
Java 4 Ever Movie

have you seen this video yet ? pretty funny.

"Java 4 Ever"

man that video (pirate copy video above) kind of scares me. its like a video copying the actual movie, which i assume was its intention but sometimes i can be daft. i will explain why that scares me....

i have a mental disorder that came out in my late 20's. and i started getting paranoid. seeing i was in los angeles and having never met or seen bill gates in person i thought he was following me for a bit as i kept on seeing the actor from that "pirates of silicon movie" out at the night clubs i was promoting. at one time i said holy shit its bill gates and pointed at him and he ran away.

my mind was getting twisted as celebrities are common place in los angeles... they have to eat to.. but i found my self thinking i wonder if that was the real bill gates and the guy in tv is a stunt double. i mean if i was a billionaire i would put someone else on the tv that represented me so i could maintain some sort of anonymity even if the double was in effigy of my true likeness.

this is common in paparazzi situations as i would often see 5 paris hiltons leaving a club in different directions. as a sort of smoke and mirrors that the pirated movie above talks about.

don't tell people you pirate movies. BayTSP got me for seeding a movie while on campus. thankfully it was movie i had affiliations with.

so i can not particularly attribute that movie to sending me down the rabbit hole but was defiantly a contributing factor in retro-spect.

even after all that i still love the whole MAC v MS thing. i used to work a print shop copying things in high school so i know various xerox / press type things fairly well. (will get to the why that is relevant in sec.)

so i took a interactivity class and did a simple tutorial of how to rewire a max patch to a DAW, then went strait to phoneme opcode AI video stuff and skipped everything in between.

so my my professor who actually does brilliant cellular automata surround music things with max that is way beyond my understanding max. (i'm more of a logic type o guy, although he taught me to love and appreciate indeterminacy and random)

so to get on with it the professor gave me hard time with my rewire patch because he said i copied it.

this is not good in the educational system as it has something to with plagiarism and codes of ethics and what not... even though most kids copy wikipedia all the time.

i told him i did a tutorial and copied the rewire network to my head and implemented from the copy i had in memory and that i do not think it should be an issue as most media teacher like open source ( open images ) creative commons etc...

i said how do children learn they imitate. what is imitation ? it is copying ! learning is almost impossible without copying. it is a very rare moment that someone has a truly unique novel and orginal idea and when you have one of those ideas you should thank whom ever your god or alien is. (with the exception of music, as you can make an original tune with same three notes everyone else uses)

so my quote is.

"Microsoft copied Apple and Apple copied Xerox and what does Xerox do ?

"Making Copies" quote from SNL.

i don't think my professor thought it was as funny as i did at the time but i made it through the class and actually went from what is a the buddy object and bang object to some really interesting web cam musical instruments, ASL video to speech patches, even made a pretty neat edge detection proximity sensor thing, i thought blind people could use to hear physical objects etc...

another great quote commonly attributed to Pablo Picaso but maybe its origins are from TS Eliot ?

"Good Artists Borrow, Great Artists Steal"

blah blah rant rant. this is my thread so i can hijack it with crazy stories of myself if i want.

cybero's picture
Re: Java 4 Ever Movie

Quote:

Microsoft copied Apple and Apple copied Xerox and what does Xerox do

er, actually Xerox invited Apple, worked alongside them, so not copied, more used and developed further with full permission & no doubt disclosure.

[Although having said that, maybe we're all arguing / stating from modern apocrypha ].

Also All artists express, Great artists innovate , Good artists originate. No art happens without one seeking to originate & express.

cybero's picture
Re: Java 4 Ever Movie

BTW, the movie's a great parody. Platform Agnosticism Rules - fair enough ? •~

cybero's picture
Re: Open CL 3D Vertex Collision (hit testing) (Composition ...

Quote:

i mean you wouldn't get mad at TB for chiming in saying hay man i made that java script tester months ago. (where has TB been anyways ?)

or the OpenCL_Array or the Various_CI's, etc, etc, Superformula & so on.

Just last heard from tb today via Vimeo. Sounded like he was very busy with other stuff to do.

gtoledo3's picture
Re: Open CL 3D Vertex Collision (hit testing) (Composition ...

It wouldn't make sense, since my method avoided JavaScript.

cybero's picture
Re: Open CL 3D Vertex Collision (hit testing) (Composition ...

but it would make sense if you did so employ another's code, which was what dust was posting about his having done & generally about others so doing [ but not specifically about yourself ] :-) .

gtoledo3's picture
Re: Java 4 Ever Movie

It was definitely parody, but that's about how I felt when I saw the conditional hit test setup in the brief window between waking up and having my coffee. I'm not what one would call a morning person.

I really enjoyed this movie back when it came out (I was in elementary school...this was '89, right?). We had Apple computers in my school's computer lab, and I also really thought Steve Jobs was "the man".

Back in those days, all of the stuff that consisted of plain text was in a certain place that was pretty easy to find, and I don't think there were any kinds of user security levels that would keep you from changing stuff. So in the school computer lab I would hack the games to give pretty ridiculous prompts at certain intervals, especially on the game that helped you type better - the insults would get progressively more insulting as you mastered typing. Good times...

cybero's picture
Re: Java 4 Ever Movie

Startup Sound manipulation hacks, writing your own programs, hacking graphics, etc ... happy days for many who had computing on their heuristic menu.

& of course, how to bring it down ...

gtoledo3's picture
Re: Java 4 Ever Movie

Also, I think that for some reason even though we used Apple at the lab, I believe that there were a large contingent among the Catholic nuns at my elementary school who thought that Jobs and Apple were bad somehow, but had no specific proof, which just made me think that he must be awesome. I think it might have had something to do with that $666.66 computer price.

dust's picture
Re: Java 4 Ever Movie

apple has a really cool program in my state for schools. i mean as long as i can remember the computers where always macs. once i grew up and moved out west steve jobs put together a laptop initiative program that gives every grade schooler child rich or poor a laptop which i think is amazing. the program is still running. i can remember going into a brand new apple store in california with boss, and there was this giant billboard behind the genius bar that had a yellow school bus from some maine public school district. i can remember telling my boss that was the school i went to, which was a far stretch.

dust's picture
Re: Java 4 Ever Movie

there you go getting all technical cybero. yes i know it was joint effort by both parties but doesn't sound the same when your like MS copied Mac and Xerox Invented Apple. xerox was actually responsible for a whole lot of other amazing things as well. like the ethernet etc..

is it just a rumor or is it true that apple fly's a pirate flag at headquarters ? i mean we all know steves favorite movie for a while was pirates of the Caribbean and you see the flag in the movie but i have always wondered if it was real ?

has anybody got a chance to listen to the iWoz audio books. its actually pretty interesting to here the whole story from woz's point of view.

usefuldesign.au's picture
Re: Open CL 3D Vertex Collision (hit testing) (Composition ...

Hey I liked your hit test GT thanks for Leopardising it for me. If I was to say to myself, gee I wonder if this could be done in JS or OpenCL to use in conjunction with particles or for a speed bump and started trying some code, I really can't see the harm in that. I mean people have posted hit-test stuff in the past (I'm pretty sure here or the list I've seen GUI type hit-testing) and there's the stock patch you already acknowledged.

Maybe it's the thing of not acknowledging you had 'got there first' (king of the mountain ;-) ) that's annoying to you? Not starting anything, I just don't get it, it's not like someone is ripping your work and profiting from it in terms of glory or coin.

usefuldesign.au's picture
Re: Java 4 Ever Movie

cybero wrote:
Startup Sound manipulation hacks,
We had a Lab of Mac II the first colour Macs in the Faculty architecture was in shared with other depts. I'd started a architecture magazine with others which became a broad cultural arts magazine in the early days of DTP.

I knew the memory address of the "Welcome to Macintosh" message in the Mac splash screen. I asked my collegue for a 20char message for our friends. So "F.<| Off You SEAP* idiots" became the greeting at start-up the next morning.

Lab staff sought me out the next day to me after complaints and I had to change back to "Welcome to Macintosh" before they hauled me before the Faculty board for "hacking" — which in those days was a scary word!

*The SEAP students were using this hugely expensive and exclusive Apple lab to print out cocktail recipes and the like to the free A3 laser printer and being Socio_something_something_Planning students, didn't have a creative urge to save themselves and used to disrupt our work flow with general noisy bs so it seemed reasonable provocation at the time ;)

usefuldesign.au's picture
Re: Java 4 Ever Movie

That was hilarious, Dust. I loved the parody of the incidental music, esp at the start. Incidental music has become more stock than period art direction in Hollywood even a movies lighting and camera setups are more original than incidental music these days. Which is kinda weird given how open you'd imagine the implicit limitations would be —it's like have all the producers in Hollywood had frontal lobotomies in the last decade when it comes to sound production.

I know a sound composer who has moved into sound mixing (more the sound effects) because it's more creative particularly in an animated movie where everything must be invented as it were.

gtoledo3's picture
Re: Open CL 3D Vertex Collision (hit testing) (Composition ...

You misunderstand; I guess it's an inside joke of history between dust and I.

usefuldesign.au's picture
Re: Open CL 3D Vertex Collision (hit testing) (Composition ...

Okay you were joking then…

I remember that incident, I was saying to dust 'cool it man, george isn't like that kind of a dude' before you got back online to sort it between you two.

dust's picture
Re: Java 4 Ever Movie

haha we know you Australian school boy's are notorious hackers. i thought about doing something like that at the collaborative media on my campus.

i used to hang out there alot before i had a kid as they have network render farms and mega core pro macs and what not. the strange thing is that it is a collaborative lab hence the name but no one ever collaborates they sit in there cubicles like little photoshop final cut robots.

so i thought it would be funny to take vade's screen grab patch and my apple script patch and switch out the real photoshop or final cut doc icon with a custom QB app.

so when someone went to launch what they thought was photoshop the app would take a screen shot freeze it an melt it or something, turn on a video camera then display some weird message about IT watching you or something. i thought that might have been funny at the time. although i have a different view point after actually being vnc hacked at my home.

At&t freaked me out the other day sending me letter about some hacker group compromising there servers by sending fake 3g ipad requests to sniff IME sim card numbers or something like as att was auto populating or something and they exploited this thing. i was a bit worried as i couldn't log into my account. so i called them but i was an idiot and spelled my name wrong when i signed up.