xmlgraphics-batik-users mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Thomas DeWeese <Thomas.DeWe...@Kodak.com>
Subject Re: detecting shape collision?
Date Thu, 05 Feb 2004 11:09:17 GMT
Baron, Randy {PRG~Basel} wrote:

>   I am _really_ not a java2d expert, but I had a quick idea: maybe you
> could use the paint() method of the objects to 'listen' for overlap.

Hi all,

    The 'easiest' way to check if two shapes overlap is to
construct (or copy preconstructed) java.awt.geom.Area objects
and use the 'Area.intersect(Area)' method, then check if the
result is 'empty'.  This is quite expensive so you should do
all your 'preliminary' testing on the bounding boxes of the
elements (as previously described).  Shape also has an intersects
call that takes a rectangle - that could filter a few more
cases (it may not be cost effective).

    Another possible solution is to render the image to a
1 bit per pixel image, then you can really quite quickly
'bit and' the two 'masks' if any bits stay set then the masks
overlap.  This is probably the 'fastest' for 'screen resolution'
intersection tests.

    As to avoiding the O(N^2) behavior, there are a number of
possible methods, I would create an invisible grid and add
all objects who's bbox intersets a grid to that grid.  Then you
only test for intersections between elements that share a grid
(make sure you don't recheck the same pair from grid to grid).
You could also use a 'quad tree' but I think that would be expensive
to maintain in a dynamic environment.



> That is, when an overlap occurs, I guess some repainting must happen?
> So, maybe you could take advantage of that.  I found one page with some
> useful-looking information: 
> 
> http://java.sun.com/products/jfc/tsc/articles/painting/#smart
> 
> for example:
> 
> "Optimized" Drawing
> The overlapping component issue is more tricky. Even if none of a
> component's immediate siblings overlaps the component, it's always
> possible that a non-ancestor relative (such as a "cousin" or "aunt")
> could overlap it. In such a case the repainting of a single component
> within a complex hierarchy could require a lot of treewalking to ensure
> 'correct' painting occurs. To reduce unnecessary traversal, Swing adds a
> read-only isOptimizedDrawingEnabled property to javax.swing.JComponent: 
> 
>     public boolean isOptimizedDrawingEnabled()
> The settings are:
> 
> 
> true: The component indicates that none of its immediate children
> overlap.
> 
> false: The component makes no guarantees about whether or not its
> immediate children overlap 
> By checking the isOptimizedDrawingEnabled property, Swing can quickly
> narrow its search for overlapping components at repaint time. 
> 
> 
> (sorry--not really Batik related)
> 
> -Randy
> 
> 
> 
> -----Original Message-----
> From: Bibek Sahu [mailto:scorpio@dodds.net] 
> Sent: Wednesday, February 04, 2004 11:03 PM
> To: Batik Users
> Subject: Re: detecting shape collision?
> 
> 
> 
> I don't believe it's in the spec for SVG, though I could be wrong;
> anybody know otherwise?  As near as I can tell, there is no code in
> either Batik or in Java to do precise 2D collision-detection, or deliver
> events upon that.  You asked about checking two objects, not about
> recieving events on an arbitrarily-large number of objects.
> 
> 
> Given that collision events are not in the SVG spec, you could:
> 
> 	(1) use Java3D, which does have collision events.  You would, of
> course, have to write a bit of glue code for it...
> 
> 	(2) come up with a more practical implementation of the check.
> There might even be a Java-based system out there which will fire
> collision events when two Shape objects collide.  I don't know of any,
> but I'm no graphics expert; I'm sure the algorithms have been
> researched, though.  You could find/write an implementation of such an
> algorithm, then write a custom bridge for Batik so you could access it.
> [of course, it'd only work with Batik at that point...]
> 
> Good luck.
> - Bibek
> 
> 
> On Wed, 4 Feb 2004, don undeen wrote:
> 
> 
>>So you're saying that while there isn't code in batik to see if to SVG
> 
> 
>>shapes intersect, I can turn them into java.awt.Shapes, and use code 
>>like jPong.PongObject.collides(shape1, shape2) to see if they collide?
>>
>>that makes sense; I wonder if that will ulitimately be practical for 
>>my system, where I intend to to have LOTs of shapes moving around. For
> 
> 
>>N objects, I have to do (n+(n-1)+(n-2)+...+2+1 (i forget, is that what
> 
> 
>>they'd call "O(log(n))" ?) comparisons every iteration to see if there
> 
> 
>>are any new intersections. I've been able trying to avoid loops like 
>>that where possible.
> 
> 
>>What I really wanted to have was a way to register a "collisionEvent" 
>>with a shape, so that collisions are just "announced" when they occur.
> 
> 
>>Would something like that ever be in the works for SVG?
>>
>>
>>Bibek Sahu <scorpio@dodds.net> wrote:
>>
>>Howdy,
>>
>>On Wed, 4 Feb 2004, don undeen wrote:
>>
>>
>>>Is there any way with batik/java/svg to detect if two svg shapes 
>>>have "collided" or overlap? For example, if you have two circles of 
>>>some radius, and you move them closer together, I'd like an alert to
> 
> 
>>>go up when the edges collide. Or perhaps I'd like to know if two 
>>>lines overlap.
>>
>>In principle, in SVG, the SVGSVGElement methods 'getEnclosureList()', 
>>'getIntersectionList()', 'checkEnclosure()', and 'checkIntersection()'
> 
> 
>>might be useful (though I don't know if they'd be enough)... but in 
>>practice I don't think they're implemented in Batik yet (at least, 
>>that the impression I got from what I've seen on this list).
>>
>>In practice with Batik, you can get the GraphicsNode associated with 
>>an SVGElement, and then use GraphicsNode.getOutline() (or if it's a 
>>ShapeNode, use ShapeNode.getShape()) for both nodes, then check if the
> 
> 
>>returned Shape objects intersect:
>>
>>BridgeContext bc = svgComponent.getUpdateManager().getBridgeContext();
>>
>>SVGElement circle1=...., circle2=....;
>>GraphicsNode g1 = bc.getGraphicsNode(circle1);
>>GraphicsNode g2 = bc.getGraphicsNode(circle2);
>>
>>Shape outline1 = g1.getGlobalTransform().createTransformedShape( 
>>g1.getOutline() ); Shape outline2 = 
>>g2.getGlobalTransform().createTransformedShape( g2.getOutline() );
>>
>>if(outline1.intersects(outline2.getBounds2D()))
>>// the first shape intersects the bounding-box of the second else
>>// blah blah blah
>>
>>
>>Note that it doesn't actually check if the two /shapes/ intersect, and
>>especially with circles this could get to be a problem, but at least
> 
> you now
> 
>>have Shape objects to work with. :-)
>>
>>
>>If you need a method to see if two Shapes collide, Mr. Google is your
>>friend. (e.g.,
> 
> http://www.risrani.com/programs/pong/doc-Pong/jPong/PongObject.htmlhttp:
> //www.risrani.com/programs/pong/doc-Pong/jPong/PongObject.html
> 
>>;-)
>>
>>Good luck!
>>- Bibek
>>
>>
>>
>>>Is there a method to do this that doesn't involve explicitly
> 
> calculating
> 
>>>the areas covered by each of my shapes?
>>>
>>>I'm guessing the answer is "no," but I'd sure like it to be "yes"!
>>>
>>>
>>>
>>>thanks for everything,
>>>
>>>Don Undeen
>>>
>>>
>>>
>>>
>>>---------------------------------
>>>Do you Yahoo!?
>>>Yahoo! SiteBuilder - Free web site building tool. Try it!
>>
>>
>>---------------------------------------------------------------------
>>To unsubscribe, e-mail: batik-users-unsubscribe@xml.apache.org
>>For additional commands, e-mail: batik-users-help@xml.apache.org
>>
>>
>>---------------------------------
>>Do you Yahoo!?
>>Yahoo! SiteBuilder - Free web site building tool. Try it!
> 
> 
> 
> 
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: batik-users-unsubscribe@xml.apache.org
> For additional commands, e-mail: batik-users-help@xml.apache.org
> 
> 
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: batik-users-unsubscribe@xml.apache.org
> For additional commands, e-mail: batik-users-help@xml.apache.org
> 
> 



---------------------------------------------------------------------
To unsubscribe, e-mail: batik-users-unsubscribe@xml.apache.org
For additional commands, e-mail: batik-users-help@xml.apache.org


Mime
View raw message