Thread: RE: [Algorithms] splat an area through a world
Brought to you by:
vexxed72
From: Brian S. <Brian.Smith@RealPage.com> - 2001-05-31 23:35:21
|
Sorry about a "me too" message, but I would like to hear any opinions on the subject as well. Good question. Well, I did have an idea or two pop into my head. Considering individual segments of the extruded shape's path (ie, the extrusion portion from one path-node to it's neighbor), you could just do bounding-volume collision testing (such as testing the shape-segment planes against local world geometry vertices). The BV used could very well be the shape itself. Though calculating precise penetration amounts doesn't sound like much fun. Another idea. Build a silhouette of the shape-segment, using an eyepoint created from the starting pathnode looking at the neighbor node. I'm not familiar with the stencil buffer (or, really, rendering-specific stuff in general), but perhaps you could do a quasi render with depth or stencil checking to see what percentage of the silhouette gets filled in. Sounds slow, but I'm clueless. Being quite the non-guru (anti-guru?) in these matters, I'm sure there's plenty of holes to be punched in those ideas. :-) /Brian -----Original Message----- From: Corrinne Yu [mailto:cor...@ho...] Sent: Thursday, May 31, 2001 5:45 PM To: gda...@li... Subject: [Algorithms] splat an area through a world 1. I have an area, a shape. 2. I want to extrude this area along a line of motion through a sorted world. 3. I don't want my shape-line motion to be stopped if only 1 point, or 1 part of the shape is stopped. I want it to stop only if and when every pixel of the entire shape is blocked by something. 4. I want to know that if any part of this shape area is capable of reaching its final destination unblocked, to return TRUE. That to returns FALSE only if not a single pixel of this area can reach its destination. How do you go about implementing this conditional test? Corrinne Yu _______________________________________________ GDAlgorithms-list mailing list GDA...@li... http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list |
From: Killpack, C. <Ch...@ea...> - 2001-05-31 23:53:22
|
Corrinne, Have you looked at any Motion Planning papers? Recent work by Kenneth Hoff has accelerated the calculation of generalised Voronoi diagrams (by using the gfx accelerator). Here is his original paper (which includes an example of motion planning not too dissimlar to the problem you describe) http://www.cs.unc.edu/~geom/voronoi/ > -----Original Message----- > From: Corrinne Yu [mailto:cor...@ho...] > Sent: Thursday, May 31, 2001 3:45 PM > To: gda...@li... > Subject: [Algorithms] splat an area through a world > > > 1. I have an area, a shape. > 2. I want to extrude this area along a line of motion through a sorted > world. > 3. I don't want my shape-line motion to be stopped if only 1 > point, or 1 > part of the shape is stopped. I want it to stop only if and > when every pixel > of the entire shape is blocked by something. > 4. I want to know that if any part of this shape area is > capable of reaching > its final destination unblocked, to return TRUE. That to > returns FALSE only > if not a single pixel of this area can reach its destination. > > How do you go about implementing this conditional test? > > Corrinne Yu > > > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > |
From: Brian M. <bma...@ra...> - 2001-06-01 07:27:43
|
What you're describing sounds very like beam tracing, except that your rays are all parallel (the line of motion) rather than coming from a common apex and passing through the shape. The original paper: 'Beam Tracing for Polygonal Objects' by P. Heckbert and p Hanrahan is probably worth a look. -Brian. Brian Marshall Rare Limited, Manor Park, Twycross, Warks, England, CV9 3QN Phone: +44(0)1827 883400 email: bma...@ra... -----Original Message----- From: Corrinne Yu [mailto:cor...@ho...] Sent: 31 May 2001 23:45 To: gda...@li... Subject: [Algorithms] splat an area through a world 1. I have an area, a shape. 2. I want to extrude this area along a line of motion through a sorted world. 3. I don't want my shape-line motion to be stopped if only 1 point, or 1 part of the shape is stopped. I want it to stop only if and when every pixel of the entire shape is blocked by something. 4. I want to know that if any part of this shape area is capable of reaching its final destination unblocked, to return TRUE. That to returns FALSE only if not a single pixel of this area can reach its destination. How do you go about implementing this conditional test? Corrinne Yu _______________________________________________ GDAlgorithms-list mailing list GDA...@li... http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list |
From: <Ik...@ga...> - 2001-06-01 09:23:40
|
I am not a algorithm guru (even for reaching great solutions) and my english is not as good as I would like to, but I would like to contribute to this prob... If I have understood the matter, your would like to do something like to lie down a cloth (the shape) over a table full of things (the world or scene) and know if every pixel has fit the contour... Am I right? Well, tracing rays from every vertex of the shape (you said is constructed by polys) and getting the collisions could not work (imho) even subdividing the surface. If there are diferences in the contour of the land, and the shape cannot deform as it wants, you have a cloth or spring type problem. I am not sure if I am helpping (maybe I haven't just undertood the problem). |
From: Jamie F. <jfo...@re...> - 2001-06-01 09:31:17
|
Just a thought, may be entirely irrelevant. If you don't need to make a decision based on the result, you just want to draw something (or not), and the path passes through the camera, you can pull the same trick we were talking about the other day for lensflare, i.e. draw it right at the back with alpha. Now shrink the area down to a pixel, use it to fill the frame buffer alpha channel, use a destination alpha test to determine whether or not to draw. Probably useless for what you want, but fits the description of the problem so far :) Jamie -----Original Message----- From: Corrinne Yu [mailto:cor...@ho...] Sent: 01 June 2001 05:31 To: gda...@li... Subject: Re: [Algorithms] splat an area through a world ----- Original Message ----- From: "Tom Spilman" <tsp...@mo...> To: <gda...@li...> Sent: Thursday, May 31, 2001 10:45 PM Subject: Re: [Algorithms] splat an area through a world > Of the top of my head... projecting a ray thru each vertex of the > triangle. This does assume a non-curving path and that you can quickly do > ray intersection test on the scene ( a bsp would be nice here ) with an > early out if one ray passes thru your destination. Again just because all 3 > rays are blocked doesn't mean that you've met your requirements... you would > need to subdivide and repeat till you reach the minimum resolution. Tom -- That is what I thought you meant. I like the subdivision idea. I early out on each TRUE conditional as soon as I hit any one. -- All FALSE conditionals will end up with tons of very dense baby rays. So now my other task is to prevent FALSE tests to start with as tightly as I can, which is feasible. -- So it comes down to performance issues of the pathological case of a TRUE conditional is not found until really really deep division. I can think more about this on my own. -- As for the low level, I had found something nicer than a bsp for this kind of thing, that's why I am pulling all sorts of things to abuse the heck out of it to see when it breaks in performance computation feasibility. I think it is the kind of thing Paul Nettle would get a kick out of. :) His zero overdraw engine was quite thought provoking, wish he had shipped that code base as a game, he truly deserved to. Thank all of you for all the good answers and thoughts into this matter. Corrinne _______________________________________________ GDAlgorithms-list mailing list GDA...@li... http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list -Virus scanned and cleared ok |
From: Tom F. <to...@mu...> - 2001-06-01 12:12:07
|
I'm not sure whether you want to allow this case or not: \ / Source ----\/---------Dest --------/\----- / \ i.e. where at no single time is the whole area blocked, but no single part of the area can make it through. I notice you're making the path curved, which complicates things. But depending on the accuracy you need, "bending" the world instead (so that the path is now straight) may be a viable alternative, and would probably simplify the problem a lot. For example, you could make a BSP of the occluding objects, and then clip either the path volume or just the projected polygon (depending on which of the two results you want) by this BSP. It's not great to build a BSP per frame of course, but it's the best I can think of right now. Tom Forsyth - Muckyfoot bloke. What's he up to now (and can I have a go)? http://www.fileplanet.com/index.asp?file=60684 > -----Original Message----- > From: Corrinne Yu [mailto:cor...@ho...] > Sent: 31 May 2001 23:45 > To: gda...@li... > Subject: [Algorithms] splat an area through a world > > > 1. I have an area, a shape. > 2. I want to extrude this area along a line of motion through a sorted > world. > 3. I don't want my shape-line motion to be stopped if only 1 > point, or 1 > part of the shape is stopped. I want it to stop only if and > when every pixel > of the entire shape is blocked by something. > 4. I want to know that if any part of this shape area is > capable of reaching > its final destination unblocked, to return TRUE. That to > returns FALSE only > if not a single pixel of this area can reach its destination. > > How do you go about implementing this conditional test? > > Corrinne Yu > > > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > |