Not logged in, Join Here! or Log In Below:  
News Articles Search    

Submitted by Daniel Trstenjak, posted on March 20, 2002

Image Description, by Daniel Trstenjak

this is the first version of DCollide, a framework for the collision detection in VRML. DCollide uses sphere-hierarchies for the collision detection. The spheres you can in the picture represent the object in the 5th level of the hierarchy.

The whole collision detection algorithm is implemented in java. So the framework theoretical could be used with any browser which supports java and vrml.

Unfortunately there are some problems, so the usability is restricted to the combination of Internet Explorer 5.x and the vrml-plugin cortona. For other combinations I can't guarantee that it will work.

cu Daniel Trstenjak

Image of the Day Gallery


Message Center / Reader Comments: ( To Participate in the Discussion, Join the Community )
Archive Notice: This thread is old and no longer active. It is here for reference purposes. This thread was created on an older version of the flipcode forums, before the site closed in 2005. Please keep that in mind as you view this thread, as many of the topics and opinions may be outdated.

March 20, 2002, 12:24 PM

vrml rocks! =)

Hailed Guardian

March 20, 2002, 12:40 PM

cool stuff...


March 20, 2002, 01:07 PM

Sure ....... ok not really :)

This was part of a project at my university.
I will better not mention the other projects .....

cu Daniel


March 20, 2002, 01:15 PM

Very cool! How do you find the speed in Java? I don't have that browser/plug-in combo.

I would love to see an implementation of sphere tree collision detection -- especially the computation of the tree. I read the paper, and it seemed nice and mathy.


March 20, 2002, 01:45 PM

I haven't read the paper (perhaps I should?), but I thought of making lots of spheres myself once, and decided against it because the angle of the collision surface would be completely out... (small particle hitting front of droid could bounce in just about any direction, as could droid hitting spikey surface)

Is there some means of correcting this or is it just a pure yes/no detection system?


March 20, 2002, 02:07 PM

Nah, the angle is there. I use spheres and swept sphere volumes in my physics engine rather extensively. There are several ways to do this, the most straightforward is to take the penetration point and calculate the plane that is tangent to the sphere at that point. That's for colliding a particle with a sphere or a sphere swept volume. Process edges and faces similarly, voila you have collision response.



March 20, 2002, 02:14 PM

Maybe I'm missing something... But where is the link for the paper you speak about ? I'm very interested for this paper.

And yeah, it rocks ! I'm working on a sphere tree collision too and this one looks good.


March 20, 2002, 02:14 PM

Yes it is only a yes/no collision detection system.
But you could expand the system.

Then the sphere-hierarchies
would be used for the rough calculation.

The accurate calculation, like the angle, could be
calculated with the triangles which are inside of
the terminal spheres.

cu Daniel


March 20, 2002, 02:30 PM

The computation of the sphere-hierarchy is done with
an octree.

First of all I triangulate all the objects of the R2D2.
Then I create a cube which contains the R2D2.
The diagonal of this cube is the diameter of the
first sphere.

Then I devide the cube and control if one of the
triangles of the R2D2 is inside of one of the
devided cubes. If this is true then I again take
the diagonal of the cube and create a sphere.

This can be done until any deepness. Which means
that you devide the cubes again.

But there are some limiting factors, like the
computation period and the memory.

cu Daniel


March 20, 2002, 03:29 PM

R2D2 powa

(nice work on java/vrml)


March 20, 2002, 04:42 PM

diese abbildungen geben mir ein steifes.

Neil Edelman

March 20, 2002, 04:50 PM

R2D2 in bubble-wrap.


March 20, 2002, 05:00 PM

Oh, your dick is neutrum?


March 20, 2002, 05:00 PM

One question:



March 20, 2002, 05:08 PM

I will be the first(?) to say that
"Macromedia Shockwave 3D is way better than vrml!"

Other than that, your framework looks quite fine.

Leon Rauis

March 20, 2002, 05:10 PM

I might be wrong, but I would imagine spheres because they
are mathematically 'nice'.

Meaning they are easy to represent, convex, and
collision/intersection tests with them are straightforward
and not too computationally expensive.

That and maybe they convey some underlying sexual frustration
common to nerds since they are oh so round. :)


March 20, 2002, 07:44 PM

... and you'll hopefully be the last.

Why? 'Cause it ain't helping anyone to start flamewars about "this is better than that".

The guy used VRML, so be it, you don't have to like it :)

Spheres are nice for collision checking, but just exactly how accurate are they? Or do you get a variable accuracy depending on thresholds? (should be doable since you're using an octree already)


March 20, 2002, 08:37 PM

Hey, nice iotd,
Unfortunatly I don't have ie 5, and my connection is junk, but I wanted to make a comment even if I haven't *really* seen it.

I like the ideas for sphere collision detection, sounds like it should work well for a decent fairly accurate method to... hmm, detect collision :)

The comment is, would you want to add an option later to support not *real* distance but manhattan distance (that's what I've heard it called as anyway, something to do with how many *blocks* away something is, not as the crow flies). This may speed up the whole thing alot more without sacrificing too much accuracy.

As for the "bad angle" detection couldn't you just assign an angle to the sphere (another property, optional) and check the angle to angle collision as usual from there? Sounds like maybe an idea anyway, (keep it optional incase the geometry is close to spherical, as the dome above (iotd) )

Good luck on this and any future projects.



March 20, 2002, 10:18 PM

Manhattan distance is pretty much useless in coldet.. luckily you can check squared Euclidean distance (A-B)dot(A-B) = |A-B|^2 instead of actual Euclidean distance to detect whether a collision has occurred or not..



March 20, 2002, 10:28 PM

About as accurate as a round thing devoid of friction can get. You use the spheres for initial rejection tests, then do the rest on a triangle basis.

He's not using an octree, by the way.


March 20, 2002, 10:29 PM

Will this framework work with C3PO models???
And what about skeleton linked meshes???
Are the spheres static or it will adapt on mesh update?


March 21, 2002, 12:59 AM

Nice work.

Do you have to apply the spheres to the model yourself or do you create them algorithmically?


March 21, 2002, 01:49 AM

uhmm, more balls than polygons ;-)


March 21, 2002, 04:04 AM

Oh, btw, he _is_ using an octree :)

"The computation of the sphere-hierarchy is done with
an octree."

Read his replies :)


March 21, 2002, 05:24 AM



March 21, 2002, 05:42 AM

Looks great, unfortunately the Demonstrators didnt work with my IE 5.5.

But this would complement Java3d I hope. Did a project in Java3d once, and It fell because of the crappy collision detection J3d had. So this is probably welcome out here.


March 21, 2002, 05:46 AM

Very cool!

We still use VRML97 at work as there still isn't a better web-based 3D implementation that works well with Java.


March 21, 2002, 05:57 AM

Nice pic, but isn't this method of collision detection VERY expensive? (computationally). Sorry if I'm repeating someone else...

( de broccoli ligt op het dak )


March 21, 2002, 06:05 AM

Tristan - Do you know of any 3d volume with an intersection-check quicker than a sphere ?

So when it's built as a tree I guess this is about as fast as it comes...

(de rapen zijn gaar)


March 21, 2002, 06:09 AM

(L.e.Denninger): No, I don't, but I bet checking for a ray-triangle intersection is faster than multpile spheres? Unless, of course, the model is made up of veeeery many triangles.

( de uitgeputte fiets dronk een schaapje wol. oke, genoeg )

This thread contains 42 messages.
First Previous ( To view more messages, select a page: 0 1 ... out of 1) Next Last
Hosting by Solid Eight Studios, maker of PhotoTangler Collage Maker.