Thread: RE: [Algorithms] exploiting convexity in minkowski sum edge vs ed ge case
Brought to you by:
vexxed72
From: Jonathan H. <jhe...@cs...> - 2003-12-29 10:59:37
|
You should read the paper about DEEP by Young J. Kim because it also uses minkowski space walking. I looked at these hill climbing algorithms last year and decided they were not good, because hill climbing is only guaranteed to find the global min (or max) if the space has only one minima. Since the minkowski space has many many local minima which are not the global min, hill climbing is pointless. Unfortunately I don't know of any algorithm that can always find the minimum penetration vector between two intersecting convex polyhedra, other than a brute force search of all FV,EE pairs. John Henckel > -----Original Message----- > From: Pau...@sc... [mailto:Pau...@sc...] > Sent: Thursday, 18 December, 2003 9:46 AM > To: gda...@li... > Subject: RE: [Algorithms] exploiting convexity in minkowski > sum edge vs > edge case > > > > BTW, is by any chance, for each pair of optimal FV and V'F' > faces, V a > > vertex of F' and V' a vertex of F? > > > > In that case you could try testing only edge-edge > combinations that are > > adjacent to both optimal vertex-face and face-vertex faces? > So rather > > than testing any edge-edge combination of edges adjacent to > the faces, > > you choose only the edges that contain an optimal vertex. > > Hmmm, doesn't this rely on the two optimal faces sharing the optimal > vertex? Not sure if > this is true.... > > Cheers, Paul. > > > ********************************************************************** > This email and any files transmitted with it are confidential and > intended solely for the use of the individual or entity to whom they > are addressed. If you have received this email in error please notify > pos...@sc... > > This footnote also confirms that this email message has been checked > for all known viruses. > > ********************************************************************** > SCEE 2003 > > > > ------------------------------------------------------- > This SF.net email is sponsored by: IBM Linux Tutorials. > Become an expert in LINUX or just sharpen your skills. Sign > up for IBM's > Free Linux Tutorials. Learn everything from the bash shell > to sys admin. > Click now! http://ads.osdn.com/?ad_id=1278&alloc_id=3371&op=click > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > |
From: Jonathan H. <jhe...@cs...> - 2004-01-05 10:50:01
|
Paul wrote... > > Well, since I'm using this on convex objects, the local min = > global min > because > the minkowski sum of two convex objects is also convex. The nearest distance (or minimum penetration) vector corresponds to the point on the MS nearest to the origin. You are correct that the MS is convex and thus the local min = global min, if the origin is outside the MS. If the two convex are overlapping, you cannot assume the local min = global min. Although rigid bodies are not supposed to overlap, in my experience they often do, because for instance the objects are traveling at high speeds or the solver is overworked and doesn't compute the contact forces correctly. If collision detection gives the wrong normal in cases of deep penetration, it only makes the problem worse. I forgot to mention something in my last post. Gino's simplex inflation algorithm (see paper on proximity queries at www.win.tue.nl/~gino/solid) is an algorithm to find the minimum penetration depth of two overlapping convex polytopes and it is not brute force. In fact it might work on curved shapes also, like cylinders. I've tried to implement it (twice) and finally gave up because I had problems with tolerances, and found some special cases that didn't work. IMO, the most practical algorithm for penetration depth calculation of two convex shapes is this. 1. precompute the tightest OBB (in local space) of each object. 2. transform both OBB to world space (or one OBB to local space of the other) 3. test all 15 separating axes of the OBB pair (all face normals and all edge cross prod) and pick the one with maximum separation. 4. if the OBB max sep is negative, move the objects apart along the max sep axis until the OBB separation is positive epsilon. 5. run GJK. Since the OBB don't overlap, GJK should always succeed in finding the nearest distance vector. 6. reverse the movement of step 4 (if any) and subtract the distance moved from the result of GJK. This is is fast and reliable. It is not always correct, but when it fails it is still nearly correct. jh |
From: Stephan R. <ke...@so...> - 2003-12-30 07:48:05
|
The subject probably says it all... Essentially the problem I'm trying to solve here is dealing with trees and stuff and the leaf textures. Since I'm not sure how to put this into words, I'm just going to abuse my works web server and put screenshots of the problem on there. http://www.contechelectronics.com/Tree1.jpg - Landscape, no sky http://www.contechelectronics.com/Tree2.jpg - Landscape, sky http://www.contechelectronics.com/Tree3.jpg - Detail shot of problem Each tree is a single mesh, two textures (though I am going to a single texture approach to avoid texture switches). I know the problem is rendering order basically, but while I can control the order I render the trees in, I don't really have much control over the order the individual polys are rendered in. I don't think that trying to start sorting individual polys would be a good thing for performance. :) So, what are my options here to solve this problem??? Thanks!!! :) Stephan |
From: Aras P. <ne...@in...> - 2003-12-30 08:04:29
|
> http://www.contechelectronics.com/Tree3.jpg - Detail shot of problem From this it seems that you only do alpha-testing, and not alpha-blending (or your textures are bad - the color gets blue while the alpha stays opaque for a texel -- don't put the blue color at all; just use alpha). > the individual polys are rendered in. I don't think that trying to start > sorting individual polys would be a good thing for performance. :) Try 2 pass approach: first without blending and with z-writes, with really high alpha-test value (so you draw really opaque parts); second with blending and much lower alpha test. This way, you have correct ordering for opaque parts, and can have some benefit on hardware that has some z-rejection (so you blend only parts that are not opaque). The downside is 2 render passes, of course. Aras Pranckevicius aka NeARAZ http://www.gim.ktu.lt/nesnausk/nearaz/ |
From: Sam M. <sa...@s2...> - 2003-12-30 11:24:45
|
This is how I handle things in Savage, and it looks good. It is probably of interest to note, however, that many games circumvent the problem completely by not doing alpha blending at all (at least on trees and other world props), just alpha test with z writing on. I supplied an option for this in the upcoming patch to our game, which toggles between alpha test only and the 2 pass approach. Enabling alpha blending gives nicer edges on things (giving foliage a softer look), but the game looks fine with it disabled. I found that it is important to tweak the reference value used for alpha testing when switching between the two methods to make them look as similar as possible. The other approach for rendering alpha blended polys, as has been mentioned, is to depth sort them. Though I have not implemented it to compare performance differences, my hunch is that depth sorting polys won't be much faster (maybe even slower?) than using the 2 pass approach on today's hardware, because depth sorting means a lot more texture switching as you traverse the poly list (sorting by depth means you can't sort by texture). I took some screenshots with the alpha blending option on and off: Note that for the most part, the differences are much more subtle than this and usually not very noticeable. I picked foliage in the game where the difference would be most clear. Alpha blending disabled (alpha test func: greater than 0.35): http://milli.vanilli.org/shot00005.jpg 2 pass approach (alpha test func: > 0.6 with depth writing on, then alpha test func <= 0.6 with alpha blending on and depth writing off): http://milli.vanilli.org/shot00006.jpg Sam McGrath Lead Programmer www.s2games.com ----- Original Message ----- From: "Aras Pranckevicius" <ne...@in...> To: <gda...@li...> Sent: Tuesday, December 30, 2003 12:10 AM Subject: Re: [Algorithms] Alpha Blending > > http://www.contechelectronics.com/Tree3.jpg - Detail shot of problem > > From this it seems that you only do alpha-testing, and not alpha-blending > (or your textures are bad - the color gets blue while the alpha stays opaque > for a texel -- don't put the blue color at all; just use alpha). > > > the individual polys are rendered in. I don't think that trying to start > > sorting individual polys would be a good thing for performance. :) > > Try 2 pass approach: first without blending and with z-writes, with really > high alpha-test value (so you draw really opaque parts); second with > blending and much lower alpha test. This way, you have correct ordering for > opaque parts, and can have some benefit on hardware that has some > z-rejection (so you blend only parts that are not opaque). The downside is 2 > render passes, of course. > > > Aras Pranckevicius aka NeARAZ > http://www.gim.ktu.lt/nesnausk/nearaz/ > > > > ------------------------------------------------------- > This SF.net email is sponsored by: IBM Linux Tutorials. > Become an expert in LINUX or just sharpen your skills. Sign up for IBM's > Free Linux Tutorials. Learn everything from the bash shell to sys admin. > Click now! http://ads.osdn.com/?ad_id=1278&alloc_id=3371&op=click > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 |
From: Neil S. <ne...@r0...> - 2003-12-30 12:04:15
|
Another method that can work quite well is to combine alpha test and alpha blend, where you set the alpha test ref value to a smallish value, so that it removes transparent or near-transparent areas. This gives you some blending at the edges of your foliage, while removing most of the horrible halo you get when the draw order is wrong. It's not perfect, but combining this with a decent per-object sort works pretty well, and it's nice and easy too. - Neil. > -----Original Message----- > From: gda...@li... > [mailto:gda...@li...] On > Behalf Of Sam McGrath > Sent: 30 December 2003 11:26 AM > To: gda...@li... > Subject: Re: [Algorithms] Alpha Blending > > This is how I handle things in Savage, and it looks good. It > is probably of interest to note, however, that many games > circumvent the problem completely by not doing alpha blending > at all (at least on trees and other world props), just alpha > test with z writing on. I supplied an option for this in the > upcoming patch to our game, which toggles between alpha test > only and the 2 pass approach. Enabling alpha blending gives > nicer edges on things (giving foliage a softer look), but the > game looks fine with it disabled. I found that it is > important to tweak the reference value used for alpha testing > when switching between the two methods to make them look as > similar as possible. > > The other approach for rendering alpha blended polys, as has > been mentioned, is to depth sort them. Though I have not > implemented it to compare performance differences, my hunch > is that depth sorting polys won't be much faster (maybe even > slower?) than using the 2 pass approach on today's hardware, > because depth sorting means a lot more texture switching as > you traverse the poly list (sorting by depth means you can't > sort by texture). > > I took some screenshots with the alpha blending option on and off: > > Note that for the most part, the differences are much more > subtle than this and usually not very noticeable. I picked > foliage in the game where the difference would be most clear. > > Alpha blending disabled (alpha test func: greater than 0.35): > http://milli.vanilli.org/shot00005.jpg > > 2 pass approach (alpha test func: > 0.6 with depth writing > on, then alpha test func <= 0.6 with alpha blending on and > depth writing off): > http://milli.vanilli.org/shot00006.jpg > > Sam McGrath > Lead Programmer > www.s2games.com > |
From: Jon W. <hp...@mi...> - 2003-12-30 18:54:34
|
> I know the problem is rendering order basically, but while I can control the > order I render the trees in, I don't really have much control over the order > the individual polys are rendered in. I don't think that trying to start > sorting individual polys would be a good thing for performance. :) I agree with other recommendations that using a good alpha test value is important; that the 2-pass method is likely to work reasonably well; and that only doing alpha test (no blend) is better than a poke in the eye with a sharp stick. Your art seems to blend to sky color in the color map. That's often not the right thing to do; the art should smudge the edge color out over the transparent parts of the bitmap, and then only use the alpha to indicate coverage. That way, you will minimize MIP mapping problems, in addition to getting correct blended colors under most circumstances. In addition, you actually do have control over individual polygons, in sevaral ways: For meshes that contain transparent areas, you can sort in the exporter such that all opaque areas are drawn first, and then the transparent (this works when you draw with alpha testing and Z writes). In addition, you can sort polygons such that they are drawn roughly in back-to-front order, no matter what the viewing direction, by building a front/back relation between each pair of polys, and ordering them (it's only possible to make perfect this way if your mesh is convex). You need to turn two-sided polygons into two single-sided polygons, with different draw order, for this to work. Last, you can cut your mesh into smithereens using a BSP cutter, and generate a provably always correct drawing order for every viewing direction. That's probably overkill, but it's certainly possible; assuming you're willing to pay the preprocess cost at export time and the higher polygon count cost. Also, you have to be able to tell up-front which triangles will have transparency, but that's often not a hardship. Thus you can draw each mesh in a correct order; then sort meshes by distance to camera and draw back-to-front. Where trees intersect trees, you have to do something runtime, or eat the difference. Cheers, / h+ |
From: Tom F. <tom...@bl...> - 2003-12-31 00:43:07
|
> pair of polys, and ordering them (it's only possible to make > perfect this > way if your mesh is convex). You need to turn two-sided Untrue! Your mesh does not have to be convex for this to work. It is true that a convex mesh is guaranteed to always work, but there are plenty of objects that work that are not convex. In general doing this is always a good thing. The 2-pass mathod is not perfect, it's just better than any of the other solutions, but reordering your tris offline to get this ordering effect, or as close as you can, will minimise the remaining errors. TomF. > -----Original Message----- > From: gda...@li... > [mailto:gda...@li...] On > Behalf Of Jon Watte > Sent: 30 December 2003 18:53 > To: gda...@li... > Subject: RE: [Algorithms] Alpha Blending > > > > > I know the problem is rendering order basically, but while > I can control > the > > order I render the trees in, I don't really have much > control over the > order > > the individual polys are rendered in. I don't think that > trying to start > > sorting individual polys would be a good thing for performance. :) > > I agree with other recommendations that using a good alpha > test value is > important; that the 2-pass method is likely to work > reasonably well; and > that only doing alpha test (no blend) is better than a poke > in the eye with > a sharp stick. > > Your art seems to blend to sky color in the color map. That's > often not the > right thing to do; the art should smudge the edge color out over the > transparent parts of the bitmap, and then only use the alpha > to indicate > coverage. That way, you will minimize MIP mapping problems, > in addition to > getting correct blended colors under most circumstances. > > In addition, you actually do have control over individual polygons, in > sevaral ways: > > For meshes that contain transparent areas, you can sort in > the exporter such > that all opaque areas are drawn first, and then the > transparent (this works > when you draw with alpha testing and Z writes). In addition, > you can sort > polygons such that they are drawn roughly in back-to-front > order, no matter > what the viewing direction, by building a front/back relation > between each > pair of polys, and ordering them (it's only possible to make > perfect this > way if your mesh is convex). You need to turn two-sided > polygons into two > single-sided polygons, with different draw order, for this to work. > > Last, you can cut your mesh into smithereens using a BSP cutter, and > generate a provably always correct drawing order for every viewing > direction. That's probably overkill, but it's certainly > possible; assuming > you're willing to pay the preprocess cost at export time and > the higher > polygon count cost. Also, you have to be able to tell up-front which > triangles will have transparency, but that's often not a hardship. > > Thus you can draw each mesh in a correct order; then sort > meshes by distance > to camera and draw back-to-front. Where trees intersect > trees, you have to > do something runtime, or eat the difference. > > Cheers, > > / h+ |
From: Jon W. <hp...@mi...> - 2004-01-02 20:16:52
|
> > pair of polys, and ordering them (it's only possible to make > > perfect this > > way if your mesh is convex). You need to turn two-sided > Untrue! Your mesh does not have to be convex for this to work. It is true > that a convex mesh is guaranteed to always work, but there are plenty of > objects that work that are not convex. In general doing this is always a > good thing. The 2-pass mathod is not perfect, it's just better than any of Let me re-phrase that: "To do a perfect job, the mesh has to make sure that no triangle intersects the plane of another triangle". Else, you would have to BSP split that triangle. Clearly, convex meshes follow this rule. Non-convex meshes can still follow this rule -- for example, the mesh you get when you assemble all the fragments from doing the full BSP split will conform to this rule. Also, even if the mesh is non-conforming, as long as the interacting triangles are "far" from each other, and/or "glancing" in relative angle, it's often good enough -- and as you say, it's almost always a win to sort transparent meshes like this as well as possible. Cheers, / h+ |
From: Sergei M. <se...@ha...> - 2004-01-03 14:16:14
|
Hello, And while we are on topic about blending and sorting, I have two questions. Sorting front-to-back is useful for hierarchical z-buffer too, but it is somehow orthogonal property when sorting by shader/VB/textures. 1. Maybe sometimes it is good to do the sort of meshes, then check if there is some mesh(es) that covers much screen space, and draw it/them first (if it is not alpha-tested, to fill the hierarchical zbuffer). 2. The complete sort front-to-back is not what is needed, objects that must be sorted are only those which projection over the screen overlap, i.e. the sorting must be topological. And this will help to minimize the shader change in already sorted by shader sequence (because sorting by only depth will break this order very badly). This one is more about hierarchical z-buffer, not alpha-blended geometry (since in the simple cases of A.B. geometry the number of different shaders will be.. well 1 maybe..?). I know about 'Fill Z-buffer only'-pass approach. But when I'm DIP-limited that one is not an option. Any thoughts? |
From: Tom F. <tom...@bl...> - 2004-01-03 16:22:27
|
Generally I sort by shaders/VB/textures. Then, I (can) do two things front-to-back (or vice versa for alpha-blended stuff). I sort within each group f2b, and I then sort the groups w.r.t. the other groups f2b according to the frontmost object in each group. In practice I just "consider" all objects f2b (usually because I'm trversing octrees or portal systems) and they get added to the groups in that order, and as new groups are required they get added to the group list in that order. Then you draw all the groups. So there's no actual "sort" going on - it's all down to world traversal order. So you never break your groups, and get the best batching possible, but you do still get a lot of early-Z-reject benefits. TomF. -----Original Message----- From: gda...@li... [mailto:gda...@li...]On Behalf Of Sergei Miloikov Sent: 03 January 2004 14:16 To: gda...@li... Subject: Re: [Algorithms] Alpha Blending Hello, And while we are on topic about blending and sorting, I have two questions. Sorting front-to-back is useful for hierarchical z-buffer too, but it is somehow orthogonal property when sorting by shader/VB/textures. 1. Maybe sometimes it is good to do the sort of meshes, then check if there is some mesh(es) that covers much screen space, and draw it/them first (if it is not alpha-tested, to fill the hierarchical zbuffer). 2. The complete sort front-to-back is not what is needed, objects that must be sorted are only those which projection over the screen overlap, i.e. the sorting must be topological. And this will help to minimize the shader change in already sorted by shader sequence (because sorting by only depth will break this order very badly). This one is more about hierarchical z-buffer, not alpha-blended geometry (since in the simple cases of A.B. geometry the number of different shaders will be.. well 1 maybe..?). I know about 'Fill Z-buffer only'-pass approach. But when I'm DIP-limited that one is not an option. Any thoughts? ------------------------------------------------------- This SF.net email is sponsored by: IBM Linux Tutorials. Become an expert in LINUX or just sharpen your skills. Sign up for IBM's Free Linux Tutorials. Learn everything from the bash shell to sys admin. Click now! http://ads.osdn.com/?ad_id=1278&alloc_id=3371&op=click _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=6188 |
From: Jon W. <hp...@mi...> - 2004-01-05 18:28:44
|
> So you never break your groups, and get the best batching possible, but you > do still get a lot of early-Z-reject benefits. If you want early Z reject for pixel shading cost reasons, then you might want to lay down the Z buffer initially, without even writing to the frame buffer. Then, turn it around; only read from the Z buffer, writing to RGB. Presto! Instant zero-overdraw RGB complexity, and some-overdraw Z complexity (depending on how good your initial sort is). Note: when laying down Z, everything is "drawn" with the same texture/pixel shader, so the state switching constrains itself to modelview, and possibly vertex shader (skinning, etc). Cheers, / h+ |
From: Tom F. <tom...@bl...> - 2004-01-03 16:09:04
|
It's not even that restrictive. The plane of triangles can intersect each other quite happily and still be sorted correctly, because the front face can be put into a different place in the sort to the back face (if it exists). For example, a T shape works just fine (even with the serifs! :-) The only case that doesn't ever work is if the line of intersection of the two planes goes through both triangles (just one tri is fine). So if there are any of these in a mesh (there usually are a few) then you can't get it perfect, but you can certainly get it close. Splitting triangles in a BSP stylie fixes it, and you don't need to split a huge number of tris most of the time. You can also get circular sorts, and they're the real killers. Some of them can be resolved by splitting, but others cannot be resolved statically - for example a + shape (made of eight different faces, i.e. post split). Need a dynamic ordering such as a BSP tree to do this perfectly (hmmm... but you can probably collapse a lot of conventional BSP nodes into statically-ordered clumps, which at least makes your tiny BSP batches slightly larger). So you can't get perfect, but you can do a lot better than some random ordering. None of this is that exciting. It used to be crucial for systems without Z buffers, but fortunately we can let the cellphone and PDA guys deal with then these days :-) TomF. -----Original Message----- From: gda...@li... [mailto:gda...@li...]On Behalf Of Jon Watte Sent: 02 January 2004 20:15 To: gda...@li... Subject: RE: [Algorithms] Alpha Blending > > pair of polys, and ordering them (it's only possible to make > > perfect this > > way if your mesh is convex). You need to turn two-sided > Untrue! Your mesh does not have to be convex for this to work. It is true > that a convex mesh is guaranteed to always work, but there are plenty of > objects that work that are not convex. In general doing this is always a > good thing. The 2-pass mathod is not perfect, it's just better than any of Let me re-phrase that: "To do a perfect job, the mesh has to make sure that no triangle intersects the plane of another triangle". Else, you would have to BSP split that triangle. Clearly, convex meshes follow this rule. Non-convex meshes can still follow this rule -- for example, the mesh you get when you assemble all the fragments from doing the full BSP split will conform to this rule. Also, even if the mesh is non-conforming, as long as the interacting triangles are "far" from each other, and/or "glancing" in relative angle, it's often good enough -- and as you say, it's almost always a win to sort transparent meshes like this as well as possible. Cheers, / h+ ------------------------------------------------------- This SF.net email is sponsored by: IBM Linux Tutorials. Become an expert in LINUX or just sharpen your skills. Sign up for IBM's Free Linux Tutorials. Learn everything from the bash shell to sys admin. Click now! http://ads.osdn.com/?ad_id=1278&alloc_id=3371&op=click _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=6188 |
From: Ville M. <wi...@hy...> - 2004-01-03 16:25:20
|
On Sat, 3 Jan 2004, Tom Forsyth wrote: > None of this is that exciting. It used to be crucial for systems without Z > buffers, but fortunately we can let the cellphone and PDA guys deal with > then these days :-) Nah, us cellphone/PDA guys use Z-buffers, just like you do :) Luckily, the key word for rendering on embedded devices is "standardization" (hence OpenGL ES, JSR-184 etc. APIs) so we didn't have to go through the nastiness of proprietary ad hoc solutions :) cheers, -wili Ville Miettinen Head of Visual Research Hybrid Graphics, Ltd. http://www.hybrid.fi |
From: Stephen C. <s.c...@bl...> - 2004-01-03 13:04:28
|
> For meshes that contain transparent areas, you can sort in the exporter such > that all opaque areas are drawn first, and then the transparent (this works > when you draw with alpha testing and Z writes). In addition, you can sort > polygons such that they are drawn roughly in back-to-front order, no matter > what the viewing direction, by building a front/back relation between each > pair of polys, and ordering them (it's only possible to make perfect this > way if your mesh is convex). You need to turn two-sided polygons into two > single-sided polygons, with different draw order, for this to work. Another trick is, instead of splitting the (effectively) double sided transparent polys into duplicates facing each way then sorting them, render them in two passes with the culling set to render them back facing first, then front facing. This is not perfect of course (although it is perfect in the convex mesh case), but it doesnt require the extra storage for the doubling up of the polys. Of course it does require an extra draw call per set of transparent polys, although the amount of actual TnL/pixel work is the same. It also allows a difference in rendering between the front and back faces of the polys; for example on a set of car windows (with camera outside the car), the ones facing out towards the camera can have reflections on, while the ones that can only be seen inside the car through the outward-facing ones can be rendered without reflections. I guess you could get this with the duplicated polys, but then you'd be back to two draw calls per transparent subset anyway... I wasnt aware of the duplicate-polys trick; is there any advantage to it over my 2-pass trick? Can the pre-sorting work in any situations where the back/front facing passes fail? Cheers, Steve. |
From: Tom F. <tom...@bl...> - 2004-01-03 16:22:19
|
In many non-convex cases, the ordering of the back faces is different to the ordering of the front faces. TomF. -----Original Message----- From: gda...@li... [mailto:gda...@li...]On Behalf Of Stephen Clibbery Sent: 03 January 2004 13:05 To: gda...@li... Subject: Re: [Algorithms] Alpha Blending > For meshes that contain transparent areas, you can sort in the exporter such > that all opaque areas are drawn first, and then the transparent (this works > when you draw with alpha testing and Z writes). In addition, you can sort > polygons such that they are drawn roughly in back-to-front order, no matter > what the viewing direction, by building a front/back relation between each > pair of polys, and ordering them (it's only possible to make perfect this > way if your mesh is convex). You need to turn two-sided polygons into two > single-sided polygons, with different draw order, for this to work. Another trick is, instead of splitting the (effectively) double sided transparent polys into duplicates facing each way then sorting them, render them in two passes with the culling set to render them back facing first, then front facing. This is not perfect of course (although it is perfect in the convex mesh case), but it doesnt require the extra storage for the doubling up of the polys. Of course it does require an extra draw call per set of transparent polys, although the amount of actual TnL/pixel work is the same. It also allows a difference in rendering between the front and back faces of the polys; for example on a set of car windows (with camera outside the car), the ones facing out towards the camera can have reflections on, while the ones that can only be seen inside the car through the outward-facing ones can be rendered without reflections. I guess you could get this with the duplicated polys, but then you'd be back to two draw calls per transparent subset anyway... I wasnt aware of the duplicate-polys trick; is there any advantage to it over my 2-pass trick? Can the pre-sorting work in any situations where the back/front facing passes fail? Cheers, Steve. ------------------------------------------------------- This SF.net email is sponsored by: IBM Linux Tutorials. Become an expert in LINUX or just sharpen your skills. Sign up for IBM's Free Linux Tutorials. Learn everything from the bash shell to sys admin. Click now! http://ads.osdn.com/?ad_id=1278&alloc_id=3371&op=click _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=6188 |
From: Stephen C. <s.c...@bl...> - 2004-01-03 16:33:36
|
Oh yeah, I see what you mean. My system is considerably more restrictive in when it works. It's OK as a simple system for convex cases like cars and phone-kiosks though. :) Cheers, Steve. ----- Original Message ----- From: "Tom Forsyth" <tom...@bl...> To: <gda...@li...> Sent: Saturday, January 03, 2004 4:35 PM Subject: RE: [Algorithms] Alpha Blending > In many non-convex cases, the ordering of the back faces is different to the > ordering of the front faces. > > TomF. > > -----Original Message----- > From: gda...@li... > [mailto:gda...@li...]On Behalf Of > Stephen Clibbery > Sent: 03 January 2004 13:05 > To: gda...@li... > Subject: Re: [Algorithms] Alpha Blending > > > > For meshes that contain transparent areas, you can sort in the exporter > such > > that all opaque areas are drawn first, and then the transparent (this > works > > when you draw with alpha testing and Z writes). In addition, you can sort > > polygons such that they are drawn roughly in back-to-front order, no > matter > > what the viewing direction, by building a front/back relation between each > > pair of polys, and ordering them (it's only possible to make perfect this > > way if your mesh is convex). You need to turn two-sided polygons into two > > single-sided polygons, with different draw order, for this to work. > > Another trick is, instead of splitting the (effectively) double sided > transparent polys into duplicates facing each way then sorting them, render > them in two passes with the culling set to render them back facing first, > then front facing. This is not perfect of course (although it is perfect in > the convex mesh case), but it doesnt require the extra storage for the > doubling up of the polys. Of course it does require an extra draw call per > set of transparent polys, although the amount of actual TnL/pixel work is > the same. > > It also allows a difference in rendering between the front and back faces of > the polys; for example on a set of car windows (with camera outside the > car), the ones facing out towards the camera can have reflections on, while > the ones that can only be seen inside the car through the outward-facing > ones can be rendered without reflections. I guess you could get this with > the duplicated polys, but then you'd be back to two draw calls per > transparent subset anyway... > > I wasnt aware of the duplicate-polys trick; is there any advantage to it > over my 2-pass trick? Can the pre-sorting work in any situations where the > back/front facing passes fail? > > Cheers, > Steve. > > > > > ------------------------------------------------------- > This SF.net email is sponsored by: IBM Linux Tutorials. > Become an expert in LINUX or just sharpen your skills. Sign up for IBM's > Free Linux Tutorials. Learn everything from the bash shell to sys admin. > Click now! http://ads.osdn.com/?ad_id=1278&alloc_id=3371&op=click > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > > > ------------------------------------------------------- > This SF.net email is sponsored by: IBM Linux Tutorials. > Become an expert in LINUX or just sharpen your skills. Sign up for IBM's > Free Linux Tutorials. Learn everything from the bash shell to sys admin. > Click now! http://ads.osdn.com/?ad_id=1278&alloc_id=3371&op=click > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 |
From: Alen L. <ale...@cr...> - 2004-01-04 13:25:26
|
> I wasnt aware of the duplicate-polys trick; is there any advantage to it > over my 2-pass trick? Can the pre-sorting work in any situations where the > back/front facing passes fail? Duplication assures that you get correct polygon normals without resorting to complicated solutions like "double-sided-lighting" etc. Btw, anyone knows if it's even possible to do double-sided-lighting correctly with vertex shaders? Alen |
From: Tom F. <tom...@bl...> - 2004-01-04 14:20:53
|
> Btw, anyone knows if it's even possible to do double-sided-lighting > correctly with vertex shaders? I do remember a demo showing it, though now I think about it that may have been specific to the nVidia parts that have some extra cleverness. In general it's not worth the hassle - just duplicate the faces. A lot of the time you'll want different materials on each side anyway. TomF. > -----Original Message----- > From: gda...@li... > [mailto:gda...@li...] On > Behalf Of Alen Ladavac > Sent: 04 January 2004 13:51 > To: gda...@li... > Subject: Re: [Algorithms] Alpha Blending > > > > > I wasnt aware of the duplicate-polys trick; is there any > advantage to it > > over my 2-pass trick? Can the pre-sorting work in any > situations where the > > back/front facing passes fail? > > Duplication assures that you get correct polygon normals > without resorting > to complicated solutions like "double-sided-lighting" etc. > > Btw, anyone knows if it's even possible to do double-sided-lighting > correctly with vertex shaders? > > Alen > > > > ------------------------------------------------------- > This SF.net email is sponsored by: IBM Linux Tutorials. > Become an expert in LINUX or just sharpen your skills. Sign > up for IBM's > Free Linux Tutorials. Learn everything from the bash shell > to sys admin. > Click now! http://ads.osdn.com/?ad_id=1278&alloc_id=3371&op=click > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > |
From: Marco S. <sa...@pl...> - 2004-01-04 14:34:42
|
Alen Ladavac wrote: >Btw, anyone knows if it's even possible to do double-sided-lighting >correctly with vertex shaders? > >Alen > > It's possible to encode extra data per vertex to be evaluated at vertex shader time, but it's just better to double your geometry if you don't alreay have huge vertices. I believe next DirectX release will have something like a only-read integer 'front/back face' register. The current hw should already calc the signed area for each primitive so I don't know why this information wasn't exposed before on the hw shaders side.. ciao, Marco |
From: Jon W. <hp...@mi...> - 2004-01-05 18:28:44
|
> the convex mesh case), but it doesnt require the extra storage for the > doubling up of the polys. Of course it does require an extra draw call per > set of transparent polys, although the amount of actual TnL/pixel work is > the same. Nobody seemed to pick up on this: I don't think that's true. Re-drawing the same mesh in a second buffer call WILL cause a duplication of T&L work, both of bandwidth from AGP -> GPU, and of GPU vertex transform work. > Can the pre-sorting work in any situations where the > back/front facing passes fail? This has been addressed as: "yes" :-) Cheers, / h+ |
From: Stephen C. <s.c...@bl...> - 2004-01-05 19:05:42
|
Agreed, redrawing the same buffer with a second call _will_ give more TnL work than just drawing that same buffer once; however it will give the same TnL work as drawing the duplicated-polys buffer once, since it has half as many polys in, but is drawn twice. Hmm, actually, I suppose it depends on whether the duplication requires duplication of vertices as well as polys (assuming the rendering is indexed). Although, even if the vertices arent duplicated, but the ordering means you can't get good vertex-caching/stripping, it might not be much different after all. But in any case, yes, I think we established that it's a bit too limited in when it works to be generally useful, irrespective of performance concerns... :) Cheers, Steve. ----- Original Message ----- From: "Jon Watte" <hp...@mi...> To: <gda...@li...> Sent: Monday, January 05, 2004 6:27 PM Subject: RE: [Algorithms] Alpha Blending > > > the convex mesh case), but it doesnt require the extra storage for the > > doubling up of the polys. Of course it does require an extra draw call per > > set of transparent polys, although the amount of actual TnL/pixel work is > > the same. > > Nobody seemed to pick up on this: I don't think that's true. Re-drawing the > same mesh in a second buffer call WILL cause a duplication of T&L work, both > of bandwidth from AGP -> GPU, and of GPU vertex transform work. > > > Can the pre-sorting work in any situations where the > > back/front facing passes fail? > > This has been addressed as: "yes" :-) > > Cheers, > > / h+ > > > > ------------------------------------------------------- > This SF.net email is sponsored by: IBM Linux Tutorials. > Become an expert in LINUX or just sharpen your skills. Sign up for IBM's > Free Linux Tutorials. Learn everything from the bash shell to sys admin. > Click now! http://ads.osdn.com/?ad_id=1278&alloc_id=3371&op=click > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 |