You can subscribe to this list here.
2000 
_{Jan}

_{Feb}

_{Mar}

_{Apr}

_{May}

_{Jun}

_{Jul}
(390) 
_{Aug}
(767) 
_{Sep}
(940) 
_{Oct}
(964) 
_{Nov}
(819) 
_{Dec}
(762) 

2001 
_{Jan}
(680) 
_{Feb}
(1075) 
_{Mar}
(954) 
_{Apr}
(595) 
_{May}
(725) 
_{Jun}
(868) 
_{Jul}
(678) 
_{Aug}
(785) 
_{Sep}
(410) 
_{Oct}
(395) 
_{Nov}
(374) 
_{Dec}
(419) 
2002 
_{Jan}
(699) 
_{Feb}
(501) 
_{Mar}
(311) 
_{Apr}
(334) 
_{May}
(501) 
_{Jun}
(507) 
_{Jul}
(441) 
_{Aug}
(395) 
_{Sep}
(540) 
_{Oct}
(416) 
_{Nov}
(369) 
_{Dec}
(373) 
2003 
_{Jan}
(514) 
_{Feb}
(488) 
_{Mar}
(396) 
_{Apr}
(624) 
_{May}
(590) 
_{Jun}
(562) 
_{Jul}
(546) 
_{Aug}
(463) 
_{Sep}
(389) 
_{Oct}
(399) 
_{Nov}
(333) 
_{Dec}
(449) 
2004 
_{Jan}
(317) 
_{Feb}
(395) 
_{Mar}
(136) 
_{Apr}
(338) 
_{May}
(488) 
_{Jun}
(306) 
_{Jul}
(266) 
_{Aug}
(424) 
_{Sep}
(502) 
_{Oct}
(170) 
_{Nov}
(170) 
_{Dec}
(134) 
2005 
_{Jan}
(249) 
_{Feb}
(109) 
_{Mar}
(119) 
_{Apr}
(282) 
_{May}
(82) 
_{Jun}
(113) 
_{Jul}
(56) 
_{Aug}
(160) 
_{Sep}
(89) 
_{Oct}
(98) 
_{Nov}
(237) 
_{Dec}
(297) 
2006 
_{Jan}
(151) 
_{Feb}
(250) 
_{Mar}
(222) 
_{Apr}
(147) 
_{May}
(266) 
_{Jun}
(313) 
_{Jul}
(367) 
_{Aug}
(135) 
_{Sep}
(108) 
_{Oct}
(110) 
_{Nov}
(220) 
_{Dec}
(47) 
2007 
_{Jan}
(133) 
_{Feb}
(144) 
_{Mar}
(247) 
_{Apr}
(191) 
_{May}
(191) 
_{Jun}
(171) 
_{Jul}
(160) 
_{Aug}
(51) 
_{Sep}
(125) 
_{Oct}
(115) 
_{Nov}
(78) 
_{Dec}
(67) 
2008 
_{Jan}
(165) 
_{Feb}
(37) 
_{Mar}
(130) 
_{Apr}
(111) 
_{May}
(91) 
_{Jun}
(142) 
_{Jul}
(54) 
_{Aug}
(104) 
_{Sep}
(89) 
_{Oct}
(87) 
_{Nov}
(44) 
_{Dec}
(54) 
2009 
_{Jan}
(283) 
_{Feb}
(113) 
_{Mar}
(154) 
_{Apr}
(395) 
_{May}
(62) 
_{Jun}
(48) 
_{Jul}
(52) 
_{Aug}
(54) 
_{Sep}
(131) 
_{Oct}
(29) 
_{Nov}
(32) 
_{Dec}
(37) 
2010 
_{Jan}
(34) 
_{Feb}
(36) 
_{Mar}
(40) 
_{Apr}
(23) 
_{May}
(38) 
_{Jun}
(34) 
_{Jul}
(36) 
_{Aug}
(27) 
_{Sep}
(9) 
_{Oct}
(18) 
_{Nov}
(25) 
_{Dec}

2011 
_{Jan}
(1) 
_{Feb}
(14) 
_{Mar}
(1) 
_{Apr}
(5) 
_{May}
(1) 
_{Jun}

_{Jul}

_{Aug}
(37) 
_{Sep}
(6) 
_{Oct}
(2) 
_{Nov}

_{Dec}

2012 
_{Jan}

_{Feb}
(7) 
_{Mar}

_{Apr}
(4) 
_{May}

_{Jun}
(3) 
_{Jul}

_{Aug}

_{Sep}
(1) 
_{Oct}

_{Nov}

_{Dec}
(10) 
2013 
_{Jan}

_{Feb}
(1) 
_{Mar}
(7) 
_{Apr}
(2) 
_{May}

_{Jun}

_{Jul}
(9) 
_{Aug}

_{Sep}

_{Oct}

_{Nov}

_{Dec}

2014 
_{Jan}
(14) 
_{Feb}

_{Mar}
(2) 
_{Apr}

_{May}
(10) 
_{Jun}

_{Jul}

_{Aug}

_{Sep}

_{Oct}

_{Nov}

_{Dec}

S  M  T  W  T  F  S 






1
(3) 
2
(1) 
3
(4) 
4
(8) 
5
(24) 
6
(13) 
7

8

9

10

11
(1) 
12
(5) 
13
(5) 
14
(1) 
15
(8) 
16
(3) 
17

18

19

20

21
(7) 
22
(3) 
23
(5) 
24

25
(13) 
26
(3) 
27

28

29

30
(1) 
From: Tom Forsyth <tom.gdalgo@ee...>  20060930 06:18:42

I finally got around to writing up this algorithm. The paper itself is = here: http://www.eelpi.gotdns.org/papers/fast_vert_cache_opt.html ...and my rather less formal blog entry is here: http://www.eelpi.gotdns.org/blog.wiki.html If there's anything that needs clarifying, just ask and I'll add it to whichever is appropriate. I'd like to get hold of some of the meshes = used in the other papers referenced and do an actual applestoapples. > You won't normally get anything like a Hilbert=20 > curve, which seems to be more ideal, at least judging from > the papers out there. Curiously, you can get something surprisingly close, and the = experimental cache simulation results say that it's very close. I was pleasantly surprisied at how well this fairly dumb (but fast!) algorithm did. > Speaking of which, I was asking SungEui Yoon about his research on=20 > cacheoblivious mesh layouts, http://gamma.cs.unc.edu/COL/. Code=20 > (noncommercial use only, sigh) is at=20 Oops  I missed this reference, sorry Eric. I'll have a read of it and = see if my paper needs updating to include a comparison with these numbers. = At the very least I should mention them. Frankly, *all* of the papers so = far are so close to being perfect that people probably don't care about the slight difference in results. We're really not vertexprocessing bound = at the moment (maybe trisetupbound  that's a different problem), so = fussing over a few percent here and there might just be us geeks indulging our inappropriate optimisation fetishes :) TomF. > Original Message > From: gdalgorithmslistbounces@...=20 > [mailto:gdalgorithmslistbounces@...] On=20 > Behalf Of Eric Haines > Sent: 11 September 2006 08:57 > To: Game Development Algorithms > Subject: Re: [Algorithms] Triangle strips still useful? >=20 >=20 > First, now that this thread has calmed down, thanks very much to=20 > everyone answering my question. I'll do my best to sum things=20 > up in the=20 > book, though I'll probably have to leave out some of the subtleties=20 > discussed here. >=20 > Tom Forsyth wrote about his greedy algorithm (full post at bottom): > > Yes. There's a vertex>triangle map, and obviously there's a=20 > triangle>vertex map (indices), but there's no lookahead >=20 > Interesting, I was thinking more along the lines of a=20 > triangle>triangle=20 > neighbor list and labelling the vertices as to when they were last=20 > placed in the cache. Starting with an unprocessed triangle,=20 > examine its=20 > neighbors and choose the one (if any) whose third (nonshared) vertex=20 > has the highest vertex label number (i.e. whose third vertex=20 > was put in=20 > the cache latest). Then update the vertex label numbers, and put the=20 > other neighbors on a stack for possible processing later (when a=20 > triangle has no neighbors that have not already been processed).=20 > Continue with the new triangle you just added, checking its=20 > neighbors,=20 > etc. Of course, I haven't coded it up... >=20 > Whatever the case, it seems to me that a greedy approach will=20 > probably=20 > give a backandforth pattern on a regular grid of triangles, right?=20 > That is, lefttoright along one row, then right to left on the next,=20 > and so on. You won't normally get anything like a Hilbert=20 > curve, which=20 > seems to be more ideal, at least judging from the papers out=20 > there. That=20 > said, it's way easier to code such methods vs. the more involved=20 > algorithms out there. >=20 > Speaking of which, I was asking SungEui Yoon about his research on=20 > cacheoblivious mesh layouts, http://gamma.cs.unc.edu/COL/. Code=20 > (noncommercial use only, sigh) is at=20 > http://gamma.cs.unc.edu/COL/OpenCCL/. I thought I'd pass on=20 > this tidbit,=20 > in case it's of interest. >=20 > I wrote him: Have you compared it with the D3DXOptimizeFaces function=20 > provided by Microsoft in DirectX? >=20 > His reply: >=20 > Yes. The cache miss ratio of our cacheoblivious layout was=20 > around 10%=20 > higher than that of D3DXOptimizeFaces when we set a cache=20 > size 16 during=20 > rendering the bunny. But, if we set cache size 8 or 64, our=20 > cacheoblivious layout showed a better cache miss ratio. (Hoppe=20 > mentioned that D3DXOptimizeFaces was optimized at cache sizes=20 > 12 or 16.) >=20 > But, for very irregular models such as power plant model, our layout=20 > showed better performance even at cache size 16. Probably, the method=20 > employed in the D3DXOptimizeFaces is not that good for such types of=20 > models. >=20 > You can check out some detail info about comparison at page 6=20 > and 7 of=20 > http://gamma.cs.unc.edu/COL/meshlayoutsblockbasedcaches.pdf >=20 >  >=20 > Eric >=20 >=20 > Tom Forsyth wrote: > > Yes. There's a vertex>triangle map, and obviously there's a > > triangle>vertex map (indices), but there's no lookahead =20 > at each stage, > > the algorithm looks at the history of which triangles it=20 > already added, the > > adjacency info, and then decides on the next triangle to=20 > add, and that's it > >  it never backtracks or changes its mind. So fundamentally=20 > the algorithm is > > O(n) (ignoring the effects of CPU data caches on the adjacency map). > > > > TomF. > > > > > > Original Message > > From: gdalgorithmslistbounces@... > > [mailto:gdalgorithmslistbounces@...] On=20 > Behalf Of Matt J > > Sent: 05 September 2006 12:15 > > To: Game Development Algorithms > > Subject: Re: [Algorithms] Triangle strips still useful? > > > > > > Hi Tom, > > > > When you say nonlookahead, do you mean your reordering the=20 > indices based > > soley on data from an adjacency buffer? > > > > Thanks, > > > > Matthew > > > > > > In practice, I've found the simple greedy nonlookahead=20 > reorderer I did for=20 > > the big G gets you within 10% of either Hoppe or the=20 > Hilbert stuff, works > > for a large range of cache sizes and types, and is really=20 > fast to run (no > > lookahead!), which gets quite important now we're looking=20 > at millionpoly=20 > > meshes and the like. Once you throw in the randomness of=20 > realworld meshes > > > > > >=20 >  >  > > Using Tomcat but need to do more? Need to support web=20 > services, security? > > Get stuff done quickly with preintegrated technology to=20 > make your job easier > > Download IBM WebSphere Application Server v.1.0.1 based on=20 > Apache Geronimo > >=20 > http://sel.asus.falkag.net/sel?cmd=3Dlnk&kid=3D120709&bid=3D263057&; dat=3D121642 > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 > > =20 = Using Tomcat but need to do more? Need to support web services, = security? Get stuff done quickly with preintegrated technology to make your job easier Download IBM WebSphere Application Server v.1.0.1 based on Apache = Geronimo http://sel.asus.falkag.net/sel?cmd=3Dlnk&kid=3D120709&bid=3D263057&dat=3D= 121642 _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 
From: Matt J <mjohnson2005@gm...>  20060926 16:44:42

Well, or because that there is no tangent or bitangent that is directing the vector in the shader. replicate the vertices. However, objectspace bumpmapping has the added pain > that you actually need to move the texture coordinates to some unoccupied > part of the map, because no two triangles can refer to the same place on > the > texture. Now, it def. is an interesting problem to solve, but for him, the NV Mesh tool he was using was supposed to handle the cases and duplicate the correct coordinates. So then, what would cause it not to work with a DUDV map? My guess was that if he was using it as a simple offset in texture coordinates ala refraction simulation, those offsets would be incorrect on mirrored edges.. so if he scales the dx by the tangent (+1,0,0), dy by the bitangent (0, +, 0) (after being transformed into tangent space), those offsets should have the correct sign :) I see you use raycasting, so I assume you mean parrallax or steep parallax.. In that case, he is transforming the eye in tangent space, so it is doubtful he has this problem. But if he is using DUDV maps for refractive/reflective surfaces, perhaps this is the issue. I never heard of DUDV maps until now, but the code I saw that uses it doesn't seem to take into account such mirroring. All it does is blindly offset the texture coordinates. So yeah, gotta love that "magic". Im not sure what model would look like that has both mirrored texture coordinates and refraction needs. Maybe a car with a glass window, symmetrical around the middle, or a pool or fountain, also symmetrical about the window. Or just the surface of a car, that will use a reflective map if its a glossy metal. Like all those racing games. Also, I don't know why anyone cares whether you drop Granny's name or not. No doubt the tool is useful and could help save a company money. It seems appropiate to mention a tool that you spend all day working on and solves the exact problem mentioned. At my company, we are funded primarily through research grants, so we can afford a bit of time to learn or spin our own solution. At other companies, you need a solution yesterday. Matthew Once you've done that though, the raycasting process should deal > with keeping the seam smooth. > Whereas using the same bit of texture multiple times is perfectly acceptable > with tangentspace bumpmapping  the problem at the seam vertices is that > the tangent vectors need to point in different directions. However, now > you > have the problem that once you've duplicated the vertices, how do you make > sure that the normal and tangent vectors (and thus the shading) are smooth > across that seam? There's a lot of heuristics involved. As others have said, you can just manually split the mesh. But that just > solves the "where do I split" problem. That's actually the easy bit to > figure out! It doesn't solve the question of "how do I ensure the join is > smooth"  in fact it makes it slightly harder because it obscures useful > info, i.e. that this seam is a mirrorseam. And it's quite important, > because on humans the seam is in visible places (e.g. the middle of the > face). > > > TomF. 
From: Tom Forsyth <tom.gdalgo@ee...>  20060926 05:55:48

The objectspace and tangentspace issues are somewhat different. The problem along the mirrored seam has the same solution though  you need = to replicate the vertices. However, objectspace bumpmapping has the added = pain that you actually need to move the texture coordinates to some = unoccupied part of the map, because no two triangles can refer to the same place on = the texture. Once you've done that though, the raycasting process should = deal with keeping the seam smooth. Whereas using the same bit of texture multiple times is perfectly = acceptable with tangentspace bumpmapping  the problem at the seam vertices is = that the tangent vectors need to point in different directions. However, now = you have the problem that once you've duplicated the vertices, how do you = make sure that the normal and tangent vectors (and thus the shading) are = smooth across that seam? There's a lot of heuristics involved. As others have said, you can just manually split the mesh. But that just solves the "where do I split" problem. That's actually the easy bit to figure out! It doesn't solve the question of "how do I ensure the join = is smooth"  in fact it makes it slightly harder because it obscures useful info, i.e. that this seam is a mirrorseam. And it's quite important, because on humans the seam is in visible places (e.g. the middle of the face). TomF. Original Message From: gdalgorithmslistbounces@... [mailto:gdalgorithmslistbounces@...] On Behalf Of = Matt J Sent: 25 September 2006 13:13 To: Game Development Algorithms Subject: Re: [Algorithms] Tangent Space DUDV This actually has been a subject of confusion for me myself because I = havent had much experience with the art tools (or much of anything) , but = since someone else brought it up..=20 Are these assumptions correct: 1. This is only an issue if the mesh has a set of texture coordinates = that is duplicated, but in a different order (clockwise vs. = counterclockwise) or if two disjoint pieces of the mesh overlap the same area covered by = the same bump map texture.=20 2. This is an issue in both object space and tangent space bump mapping Perhaps here is an alternative method to handle this: Since the tangent/bitangent calculation initially calculates all the = vectors based on the orientation of the mesh, all it has to do is cache these texture coordinates. If it comes across the reverse of one of the axises = of the texture coordinates, you could theortically encode a 2bit value = that indicates whether to flip the tangent or bitangent (no need for z, if = its negative you flip it in the shader) before doing the lighting.=20 Then, if you have say a pervertex color, you could pass it along in the alpha and reduce the alpha to 6bits. Or if you had some other info you passed pervertex, you can probably stuff it there. In fact, this might = work fairly well for perpixel specularity exponent, or the exponents passed = in anisotropic lighting.. if you can accept some precision loss.=20 Matthew > I do hope im not missing something really obvious :) Far from it  this is a tricky problem, and the solution is somewhat = fiddly. The good news is that you can do this with code rather than changing = art. You need to do a postprocess on your mesh and introduce a seam down the mirrored edge. Along that seam, you replicate the vertices  they will = have the same positions, normals and UVs, but the tangent vectors will be=20 mirrored. So the problems, easiest to hardest: Replicating vertices Finding which vertices need to be replicated like this Ensuring continuous normals across the seam, even though the tangents=20 aren't continuous Creating exactly the right number of copies  the answer is not always = 2 It's all perfectly possible, but it's very fiddly code, and lots of = people get it wrong, or have incomplete heuristics. I think I've rewritten=20 Gthing's code for this about four or five times coping with curious = little cases (e.g. you can get more than two sets at each vertex  you can get = four or six different tangent spaces even though they all share the same = normal)=20 There's an article "Triangle Mesh Tangent Space Calculation" by Martin Mittring in ShaderX4 where he states the problems quite nicely, and also gives some code to solve some of them. However, it doesn't solve things=20 completely and doesn't ensure smooth normals over mirrored seams, which = is quite important. My advice, somewhat inevitably, is to buy an existing solution if you = can :) TomF. 
From: Matt J <mjohnson2005@gm...>  20060926 00:21:43

We don't know that :) Okay I thought about it some more, and even with duplicated vertices, the thing is that bump mapping works because it always offsets the normal in the direction of the tangent or bitangent, and those vectors are passed for every vertex. For the texture displacement to work, it must be displacing in the direction of the eye vector. But this isn't displacement mapping, this is simulation of refraction by offseting dx, dy, right?? Well, dx / dy will always be in the direction of the original normal map, calculated originally by subtracing texture coordinates. Well, even if you do duplicate the vertices and such, you are still reusing image map data. But in the spots where mirroring occured, this is why you must flip either the tangent or bitangent vector, as Tom has said, so that the tangent space transformation is correct for the lighting vectors. However, if your simply offseting texture coordinates by Dx, Dy, it has to be in the direction of the tangent vectors.. because they may be mirrored in some vertices and not mirrored in others. So, I believe if you scale <Dx, 0, 0> and <0, Dy, 0> by the tangent, bitangent vectors, which are <+1,0,0> and <0,+1,0> in tangent space, then the texture offset should now offset in the correct direction. By the way, I may be wrong :) Anyone here think that could be it? Matthew Relax a bit, you won't starve if you don't promote the gthing on a post > or another.. > > Nils > > 
From: Nils Pipenbrinck <n.pipenbrinck@cu...>  20060925 22:23:16

Tom Forsyth wrote: > My advice, somewhat inevitably, is to buy an existing solution if you can > :) Tom, your expertise is appreciated for sure, but you stress the gthing a bit to far to my taste.. How many weeks do we have to wait until we are adviced to buy the gthing to get a rotating cube on the screen (to stress the ongoing ads we read here every other day a little)? Relax a bit, you won't starve if you don't promote the gthing on a post or another.. Nils 
From: Ignacio Castano <icastano@nv...>  20060925 21:46:18

Oscar, MeshMender duplicates vertices along the seams according to user suplied = thresholds and can preserve the original normals. I've used it in the pas= t and it worked fine for me. Unless I'm missing something it should work = the same way for both DUDV and regular normal maps. Maybe there's a bug in MeshMender and not all cases are handled correctly= , if that's the case, it would help if you could provide a simple example= =20that shows the problem.=20 Let me know if there's anything else I can do to help you and feel free t= o contact me privately. Thanks!  Ignacio Casta=F1o castano@...  Oscar Forth <oscar@...> wrote: > Im working on a game that is using tangent space DUDV mapping. I run m= y > meshes through NVMeshMender to generate my Tangents and bitangents. Bu= t i > have run into a problem. Basically where texture coordinates are > "mirrored" im getting a total failure of the bump mapping effect. In > hindsight It does make sense that this would happen as the DUDV map is = now > mirrored as well. After doing some google research i discovered that > NVMeshMender does fix this problem, with Dot3 maps at least. AS long a= s i > use the MeshMender generated normals (which is a bit of a pain in itsel= f).=20 > Only problem is that this solution does not seem to work for DUDV mappi= ng.=20 > I am completely lost as to why, though. Does anybody know a way i can = keep > DUDV mapping working across these mirrored tex coordinates or am i just= > going to have to admit to the art department that i "missed" something = and > they need to chage their texture UVs on a LOT of meshes? >=20 > Obviously i'd rather not have to ask the art department to do that as t= hey > are unlikely to have the time to do it. So a programmatic solution wou= ld > be great if anyone knows one. >=20 > I do hope im not missing something really obvious :) =  This email message is for the sole use of the intended recipient(s) and m= ay contain confidential information. Any unauthorized review, use, disclosure or di= stribution is prohibited. If you are not the intended recipient, please contact the= =20sender by reply email and destroy all copies of the original message. =  
From: Alen Ladavac <alenlml@cr...>  20060925 21:30:27

> You need to do a postprocess on your mesh and introduce a seam down the > mirrored edge. Along that seam, you replicate the vertices  they will have > the same positions, normals and UVs, but the tangent vectors will be > mirrored. Not to ruin Tom's perfectly reasonable advice ;) , but if you are really pressed, your artists can also do this manually where they notice problems. They simply need to unweld the vertices along that seam so the tangent space generator is able to generate two sets of different tangents. We've been planning to do this fix in our code for a long time, but the artists seem to consider this relatively easy to fix manually wherever it matters, and they don't bother us much with that issue. Note: I'm talking about tangent space normal mapping. But if I understood your problem correctly, it should be the same thing. Note 2: By unwelding you'll get nonsmooth normals (as Tom mentioned), but most of the time we find such edges to be sharp anyway. HTH, Alen 
From: Matt J <mjohnson2005@gm...>  20060925 21:27:03

Hmm, I thought this through, and obviously a solution for the wrong problem, because the problem is mirroring of vertices that are shared. That makes more sense. Here is a reference article describing the problem: http://developer.nvidia.com/object/gdc_tspacereal.html Matthew Perhaps here is an alternative method to handle this: > 
From: Matt J <mjohnson2005@gm...>  20060925 20:13:09

This actually has been a subject of confusion for me myself because I havent had much experience with the art tools (or much of anything), but since someone else brought it up.. Are these assumptions correct: 1. This is only an issue if the mesh has a set of texture coordinates that is duplicated, but in a different order (clockwise vs. counterclockwise) or if two disjoint pieces of the mesh overlap the same area covered by the same bump map texture. 2. This is an issue in both object space and tangent space bump mapping Perhaps here is an alternative method to handle this: Since the tangent/bitangent calculation initially calculates all the vectors based on the orientation of the mesh, all it has to do is cache these texture coordinates. If it comes across the reverse of one of the axises of the texture coordinates, you could theortically encode a 2bit value that indicates whether to flip the tangent or bitangent (no need for z, if its negative you flip it in the shader) before doing the lighting. Then, if you have say a pervertex color, you could pass it along in the alpha and reduce the alpha to 6bits. Or if you had some other info you passed pervertex, you can probably stuff it there. In fact, this might work fairly well for perpixel specularity exponent, or the exponents passed in anisotropic lighting.. if you can accept some precision loss. Matthew > I do hope im not missing something really obvious :) > > Far from it  this is a tricky problem, and the solution is somewhat > fiddly. > The good news is that you can do this with code rather than changing art. > You need to do a postprocess on your mesh and introduce a seam down the > mirrored edge. Along that seam, you replicate the vertices  they will > have > the same positions, normals and UVs, but the tangent vectors will be > mirrored. So the problems, easiest to hardest: > > Replicating vertices > > Finding which vertices need to be replicated like this > > Ensuring continuous normals across the seam, even though the tangents > aren't continuous > > Creating exactly the right number of copies  the answer is not always 2 > > It's all perfectly possible, but it's very fiddly code, and lots of people > get it wrong, or have incomplete heuristics. I think I've rewritten > Gthing's code for this about four or five times coping with curious > little > cases (e.g. you can get more than two sets at each vertex  you can get > four > or six different tangent spaces even though they all share the same > normal) > > There's an article "Triangle Mesh Tangent Space Calculation" by Martin > Mittring in ShaderX4 where he states the problems quite nicely, and also > gives some code to solve some of them. However, it doesn't solve things > completely and doesn't ensure smooth normals over mirrored seams, which is > quite important. > > My advice, somewhat inevitably, is to buy an existing solution if you can > :) > > > TomF. > 
From: Matt J <mjohnson2005@gm...>  20060925 18:37:39

Umm, quick correction, the other comment should read where i & 2 == true should be next to the +y plane.. but whatever, you get the idea... You know, Im not so sure I like these types of octrees anymore. I think Im going to switch to loose octrees. It is just better, all around, to know that an object is guaranteed to be in one damn octant :/ Which would be true even down to the leaf nodes or individual triangle if I simply made sure the smallest octant no smaller than the volume of the cube formed by the largest axis of any one triangle in the static geometry (assuming an overlap of k = 0.5). Also, a moving object that belonged attached to one level of the octree could move from neighbor to neighbor without having to worry about overlap, which means it could stay on that same level of the octree and not have to suddenly be relocated to a parent node. Matthew if ( triangle fully on +x plane of current octree) > rejectionBitmask[i] = 0x2A // where i & 1 == true, > that is, 1,3,5,7: 10101010; // 0x2A > else > rejectionBitmask[i] = 0x6C // where i & 2 == true: > that is, 2,3,5,6: 01101100; // 0x6C > > if ( triangle fully on +y plane) > rejectionBitmask[i] = ... > // etc > > // build childBoxes > .. > 
From: Matt J <mjohnson2005@gm...>  20060925 18:23:21

I think I see what your saying. Considering that a triangle will rarely overlap a cube (maybe, only 20% of the time?), even a child one, given the depth bounds or triangle bounds and such, the best thing to do would be to do a trivial rejection first pass that looks at the current octree node and does plane tests against the projection of the whole triangle on the planes formed by the axises of that current octree cube. Then, I'd have to build a bitmask that would remember which child nodes I "culled" from any kind of testing. If you look at each axis and this fact, let's say that there is 80% chance that it will be fully contained in just one of the child cube's. So, there is a 80% chance that 3 axis tests total will yield a complete reduction to one octree. And among that remaining 20%, there is probably yet another 80% of the chance that it would at least reduce it to four cubes... And so on..... Psuedo: buildOctree(.....) { if (triangleCount < 50 or depth >= 5) { // exit condition, copy triangles to leaf nodes .... return; } // do initial plane tests against triangles...... .... for (int i=0; i < triangles.size(); ++i) { if ( triangle fully on +x plane of current octree) rejectionBitmask[i] = 0x2A // where i & 1 == true, that is, 1,3,5,7: 10101010; // 0x2A else rejectionBitmask[i] = 0x6C // where i & 2 == true: that is, 2,3,5,6: 01101100; // 0x6C if ( triangle fully on +y plane) rejectionBitmask[i] = ... // etc // build childBoxes .. .. // build acceptances bitmask for (int j = 0; j < 8; j++) { if (rejectionBitmask[i] & (1 << j)) continue; // octree node trivially rejected already, so do not test against children octrees // do collision test on octree node and update acceptance bitmask if (triangles[i].intersectsBox(childBox[j])) acceptanceBitmask[i] = (1 << j); } } // recursive routine for (int i = 0; i < 8; ++i) { if (acceptanceBitmask[i] & (1 << i)) { // build reduced list of triangles based on what child these triangles belong too // pass down reduced triangle list to child octree buildOctree(..........) } } This may be faster than doing eight seperate triangle  cube tests individually. The key is pulling the trivial rejection out of the inner loop of 8 .. a basic optimization strategy... :) At the expense of some additional memory, though :( Matthew If you are using an axis aligned box, then surely quick rejection on each > axis would be even more effective  at least in a reasonable proportion of > cases  and that has the enormous benefit that once you know you are > entirely in one side, then a simple 2D test on the remaining axes will tell > you which octants are intersected. > > Of course you still need the other cases for when it doesn't all sit > nicely on one side of one axes, however statistically speaking, for random > triangles, you would expect 25% to get quick rejection in each axes, which > with 3 axes means overall 57.8% would get a quick rejection in one of the > three axes. > 
From: Tom Forsyth <tom.gdalgo@ee...>  20060925 17:28:49

> I do hope im not missing something really obvious :) Far from it  this is a tricky problem, and the solution is somewhat = fiddly. The good news is that you can do this with code rather than changing = art. You need to do a postprocess on your mesh and introduce a seam down the mirrored edge. Along that seam, you replicate the vertices  they will = have the same positions, normals and UVs, but the tangent vectors will be mirrored. So the problems, easiest to hardest: Replicating vertices Finding which vertices need to be replicated like this Ensuring continuous normals across the seam, even though the tangents aren't continuous Creating exactly the right number of copies  the answer is not always = 2 It's all perfectly possible, but it's very fiddly code, and lots of = people get it wrong, or have incomplete heuristics. I think I've rewritten Gthing's code for this about four or five times coping with curious = little cases (e.g. you can get more than two sets at each vertex  you can get = four or six different tangent spaces even though they all share the same = normal) There's an article "Triangle Mesh Tangent Space Calculation" by Martin Mittring in ShaderX4 where he states the problems quite nicely, and also gives some code to solve some of them. However, it doesn't solve things completely and doesn't ensure smooth normals over mirrored seams, which = is quite important. My advice, somewhat inevitably, is to buy an existing solution if you = can :) TomF. Original Message From: gdalgorithmslistbounces@... [mailto:gdalgorithmslistbounces@...] On Behalf Of = Oscar Forth Sent: 25 September 2006 09:01 To: gdalgorithmslist@... Subject: [Algorithms] Tangent Space DUDV Im working on a game that is using tangent space DUDV mapping. I run my meshes through NVMeshMender to generate my Tangents and bitangents. But = i have run into a problem. Basically where texture coordinates are = "mirrored" im getting a total failure of the bump mapping effect. In hindsight It = does make sense that this would happen as the DUDV map is now mirrored as = well. After doing some google research i discovered that NVMeshMender does fix this problem, with Dot3 maps at least. AS long as i use the MeshMender generated normals (which is a bit of a pain in itself). Only problem is that this solution does not seem to work for DUDV mapping. I am = completely lost as to why, though. Does anybody know a way i can keep DUDV mapping working across these mirrored tex coordinates or am i just going to have = to admit to the art department that i "missed" something and they need to = chage their texture UVs on a LOT of meshes? Obviously i'd rather not have to ask the art department to do that as = they are unlikely to have the time to do it. So a programmatic solution = would be great if anyone knows one. I do hope im not missing something really obvious :) Cheers for any info! Oscar 
From: Jon Watte <hplus@mi...>  20060925 17:21:11

Joshua Barczak wrote: > If you assume that it intersects the root box, then it should be > enough to just test the triangle against the three seperating planes > on the interior of the cube. If you know, for each of these three > planes, whether the triangle is on the positive side, negative side, > or both, you should be able to build a lookup table that will tell > you which cells the triangle intersects. That is not sufficient. You can build a triangle that is on both sides of all of the planes, but is not in all eight octants. In fact, you can't make a triangle be in all eight octants at the same time :) Cheers, / h+ 
From: Joshua Barczak <jbarczak@at...>  20060925 16:20:42

I realized after posting this that it isn't very precise. If the triangle cuts more than one of the planes, you can't always determine exactly which voxels it intersects. =20 =20 ________________________________ From: gdalgorithmslistbounces@... [mailto:gdalgorithmslistbounces@...] On Behalf Of Joshua Barczak Sent: Monday, September 25, 2006 10:59 AM To: Game Development Algorithms Subject: Re: [Algorithms] Octree octant classify If you assume that it intersects the root box, then it should be enough to just test the triangle against the three seperating planes on the interior of the cube. If you know, for each of these three planes, whether the triangle is on the positive side, negative side, or both, you should be able to build a lookup table that will tell you which cells the triangle intersects. For example, if the triangle is on the negative side of all three planes, then it must only intersect the lowerleft subcube. =20 JB ________________________________ From: gdalgorithmslistbounces@... [mailto:gdalgorithmslistbounces@...] On Behalf Of Robert Dibley Sent: Monday, September 25, 2006 4:48 AM To: 'Game Development Algorithms' Subject: Re: [Algorithms] Octree octant classify If you are using an axis aligned box, then surely quick rejection on each axis would be even more effective  at least in a reasonable proportion of cases  and that has the enormous benefit that once you know you are entirely in one side, then a simple 2D test on the remaining axes will tell you which octants are intersected. =20 Of course you still need the other cases for when it doesn't all sit nicely on one side of one axes, however statistically speaking, for random triangles, you would expect 25% to get quick rejection in each axes, which with 3 axes means overall 57.8% would get a quick rejection in one of the three axes. ________________________________ From: gdalgorithmslistbounces@... [mailto:gdalgorithmslistbounces@...] On Behalf Of Matt J Sent: 23 September 2006 21:56 To: Game Development Algorithms Subject: Re: [Algorithms] Octree octant classify =09 =09 Part of the trivial rejection phase of the TriBox routine does #2. =09 The seperating axis test does #1 as well. But you give me an idea. It would seem to be more advantage to reorder the routine so the trivial rejection occurs in a different order, in this context. In other words, #1, #2, then the edgeaxis tests. That should give good performance. =09 Matthew =09 =09 The octants need to: =09 1) intersect the plane of the triangle 2) intersect the aabb of the triangle=20 =09 Both of those are cheap tests, but may not be sufficient to get 100% accuracy. Once you have identified octants that fulfill both these tests, you can do trianglebox tests for each of them. Or, it may be faster to just accept some slop, and pass down vertices you don't necessarily have to. =09 Btw: In actuality, I think a worstcase triangle can actually pass through seven of the eight octants, but not through all eight (because=20 at least one octant must be culled by the plane of the triangle, if that plane doesn't pass through the center of the cube  and if so, more than one will be culled.). =09 Cheers, =09 / h+ =09 =09 Matt J wrote: > Given a triangle inside a cube, which is subdivided 8 times (i.e. an > octree), is there any optimal (clean) way of classifying which of the > octants one specific triangle intersects.=20 > > The current approach is to check for a triangle and cube collision for > each octant (i.e. all 8), and then assign a bitflag, i.e. flag &=3D (1 > << n) where n is the octant # from 0...7=20 > > I thought about seperating axis test against the min, max of each > triangle edge u0, u1, or u2 (axises from the center) of the cube, but > I think that would not work because it wouldnt tell me which specific=20 > octants it intersected the cube, because that info would be lost in > the projection. Im thinking another approach might have something to > do with intersecting the triangle edges with the planes of the cubes=20 > formed by the axises from the center. Any ideas? > > Thanks, > > Matthew >  > >  =20 > Take Surveys. Earn Cash. Influence the Future of IT > Join SourceForge.net's Techsay panel and you'll get the chance to share your > opinions on IT & business topics through brief surveys  and earn cash=20 > http://www.techsay.com/default.php?page=3Djoin.php&p=3Dsourceforge&CID=3D= DEVDE V >  > > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 =09 =09   Take Surveys. Earn Cash. Influence the Future of IT Join SourceForge.net 's Techsay panel and you'll get the chance to share your opinions on IT & business topics through brief surveys  and earn cash =09 http://www.techsay.com/default.php?page=3Djoin.php&p=3Dsourceforge&CID=3D= DEVDE V _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... =09 https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: =09 http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 =09 =20  Matt Johnson http://otowngraphics.blogspot.com=20 
From: Oscar Forth <oscar@aw...>  20060925 16:01:17

Im working on a game that is using tangent space DUDV mapping. I run my = meshes through NVMeshMender to generate my Tangents and bitangents. But = i have run into a problem. Basically where texture coordinates are = "mirrored" im getting a total failure of the bump mapping effect. In = hindsight It does make sense that this would happen as the DUDV map is = now mirrored as well. After doing some google research i discovered = that NVMeshMender does fix this problem, with Dot3 maps at least. AS = long as i use the MeshMender generated normals (which is a bit of a pain = in itself). Only problem is that this solution does not seem to work = for DUDV mapping. I am completely lost as to why, though. Does anybody = know a way i can keep DUDV mapping working across these mirrored tex = coordinates or am i just going to have to admit to the art department = that i "missed" something and they need to chage their texture UVs on a = LOT of meshes? Obviously i'd rather not have to ask the art department to do that as = they are unlikely to have the time to do it. So a programmatic solution = would be great if anyone knows one. I do hope im not missing something really obvious :) Cheers for any info! Oscar 
From: Joshua Barczak <jbarczak@at...>  20060925 14:52:46

If you assume that it intersects the root box, then it should be enough to just test the triangle against the three seperating planes on the interior of the cube. If you know, for each of these three planes, whether the triangle is on the positive side, negative side, or both, you should be able to build a lookup table that will tell you which cells the triangle intersects. For example, if the triangle is on the negative side of all three planes, then it must only intersect the lowerleft subcube. =20 JB ________________________________ From: gdalgorithmslistbounces@... [mailto:gdalgorithmslistbounces@...] On Behalf Of Robert Dibley Sent: Monday, September 25, 2006 4:48 AM To: 'Game Development Algorithms' Subject: Re: [Algorithms] Octree octant classify If you are using an axis aligned box, then surely quick rejection on each axis would be even more effective  at least in a reasonable proportion of cases  and that has the enormous benefit that once you know you are entirely in one side, then a simple 2D test on the remaining axes will tell you which octants are intersected. =20 Of course you still need the other cases for when it doesn't all sit nicely on one side of one axes, however statistically speaking, for random triangles, you would expect 25% to get quick rejection in each axes, which with 3 axes means overall 57.8% would get a quick rejection in one of the three axes. ________________________________ From: gdalgorithmslistbounces@... [mailto:gdalgorithmslistbounces@...] On Behalf Of Matt J Sent: 23 September 2006 21:56 To: Game Development Algorithms Subject: Re: [Algorithms] Octree octant classify =09 =09 Part of the trivial rejection phase of the TriBox routine does #2. =09 The seperating axis test does #1 as well. But you give me an idea. It would seem to be more advantage to reorder the routine so the trivial rejection occurs in a different order, in this context. In other words, #1, #2, then the edgeaxis tests. That should give good performance. =09 Matthew =09 =09 The octants need to: =09 1) intersect the plane of the triangle 2) intersect the aabb of the triangle=20 =09 Both of those are cheap tests, but may not be sufficient to get 100% accuracy. Once you have identified octants that fulfill both these tests, you can do trianglebox tests for each of them. Or, it may be faster to just accept some slop, and pass down vertices you don't necessarily have to. =09 Btw: In actuality, I think a worstcase triangle can actually pass through seven of the eight octants, but not through all eight (because=20 at least one octant must be culled by the plane of the triangle, if that plane doesn't pass through the center of the cube  and if so, more than one will be culled.). =09 Cheers, =09 / h+ =09 =09 Matt J wrote: > Given a triangle inside a cube, which is subdivided 8 times (i.e. an > octree), is there any optimal (clean) way of classifying which of the > octants one specific triangle intersects.=20 > > The current approach is to check for a triangle and cube collision for > each octant (i.e. all 8), and then assign a bitflag, i.e. flag &=3D (1 > << n) where n is the octant # from 0...7=20 > > I thought about seperating axis test against the min, max of each > triangle edge u0, u1, or u2 (axises from the center) of the cube, but > I think that would not work because it wouldnt tell me which specific=20 > octants it intersected the cube, because that info would be lost in > the projection. Im thinking another approach might have something to > do with intersecting the triangle edges with the planes of the cubes=20 > formed by the axises from the center. Any ideas? > > Thanks, > > Matthew >  > >  =20 > Take Surveys. Earn Cash. Influence the Future of IT > Join SourceForge.net's Techsay panel and you'll get the chance to share your > opinions on IT & business topics through brief surveys  and earn cash=20 > http://www.techsay.com/default.php?page=3Djoin.php&p=3Dsourceforge&CID=3D= DEVDE V >  > > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 =09 =09   Take Surveys. Earn Cash. Influence the Future of IT Join SourceForge.net 's Techsay panel and you'll get the chance to share your opinions on IT & business topics through brief surveys  and earn cash =09 http://www.techsay.com/default.php?page=3Djoin.php&p=3Dsourceforge&CID=3D= DEVDE V _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... =09 https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: =09 http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 =09 =20  Matt Johnson http://otowngraphics.blogspot.com=20 
From: Robert Dibley <blimey.rob@go...>  20060925 08:47:51

If you are using an axis aligned box, then surely quick rejection on each axis would be even more effective  at least in a reasonable proportion of cases  and that has the enormous benefit that once you know you are entirely in one side, then a simple 2D test on the remaining axes will tell you which octants are intersected. Of course you still need the other cases for when it doesn't all sit nicely on one side of one axes, however statistically speaking, for random triangles, you would expect 25% to get quick rejection in each axes, which with 3 axes means overall 57.8% would get a quick rejection in one of the three axes. _____ From: gdalgorithmslistbounces@... [mailto:gdalgorithmslistbounces@...] On Behalf Of Matt J Sent: 23 September 2006 21:56 To: Game Development Algorithms Subject: Re: [Algorithms] Octree octant classify Part of the trivial rejection phase of the TriBox routine does #2. The seperating axis test does #1 as well. But you give me an idea. It would seem to be more advantage to reorder the routine so the trivial rejection occurs in a different order, in this context. In other words, #1, #2, then the edgeaxis tests. That should give good performance. Matthew The octants need to: 1) intersect the plane of the triangle 2) intersect the aabb of the triangle Both of those are cheap tests, but may not be sufficient to get 100% accuracy. Once you have identified octants that fulfill both these tests, you can do trianglebox tests for each of them. Or, it may be faster to just accept some slop, and pass down vertices you don't necessarily have to. Btw: In actuality, I think a worstcase triangle can actually pass through seven of the eight octants, but not through all eight (because at least one octant must be culled by the plane of the triangle, if that plane doesn't pass through the center of the cube  and if so, more than one will be culled.). Cheers, / h+ Matt J wrote: > Given a triangle inside a cube, which is subdivided 8 times (i.e. an > octree), is there any optimal (clean) way of classifying which of the > octants one specific triangle intersects. > > The current approach is to check for a triangle and cube collision for > each octant (i.e. all 8), and then assign a bitflag, i.e. flag &= (1 > << n) where n is the octant # from 0...7 > > I thought about seperating axis test against the min, max of each > triangle edge u0, u1, or u2 (axises from the center) of the cube, but > I think that would not work because it wouldnt tell me which specific > octants it intersected the cube, because that info would be lost in > the projection. Im thinking another approach might have something to > do with intersecting the triangle edges with the planes of the cubes > formed by the axises from the center. Any ideas? > > Thanks, > > Matthew >  > >  > Take Surveys. Earn Cash. Influence the Future of IT > Join SourceForge.net's Techsay panel and you'll get the chance to share your > opinions on IT & business topics through brief surveys  and earn cash > http://www.techsay.com/default.php?page=join.php <http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV>; &p=sourceforge&CID=DEVDEV >  > > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188  Take Surveys. Earn Cash. Influence the Future of IT Join SourceForge.net 's Techsay panel and you'll get the chance to share your opinions on IT & business topics through brief surveys  and earn cash http://www.techsay.com/default.php?page=join.php <http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV>; &p=sourceforge&CID=DEVDEV _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=6188   Matt Johnson http://otowngraphics.blogspot.com 
From: Matt J <mjohnson2005@gm...>  20060923 20:55:39

Part of the trivial rejection phase of the TriBox routine does #2. The seperating axis test does #1 as well. But you give me an idea. It would seem to be more advantage to reorder the routine so the trivial rejection occurs in a different order, in this context. In other words, #1, #2, then the edgeaxis tests. That should give good performance. Matthew The octants need to: > > 1) intersect the plane of the triangle > 2) intersect the aabb of the triangle > > Both of those are cheap tests, but may not be sufficient to get 100% > accuracy. Once you have identified octants that fulfill both these > tests, you can do trianglebox tests for each of them. Or, it may be > faster to just accept some slop, and pass down vertices you don't > necessarily have to. > > Btw: In actuality, I think a worstcase triangle can actually pass > through seven of the eight octants, but not through all eight (because > at least one octant must be culled by the plane of the triangle, if that > plane doesn't pass through the center of the cube  and if so, more > than one will be culled.). > > Cheers, > > / h+ > > > Matt J wrote: > > Given a triangle inside a cube, which is subdivided 8 times (i.e. an > > octree), is there any optimal (clean) way of classifying which of the > > octants one specific triangle intersects. > > > > The current approach is to check for a triangle and cube collision for > > each octant (i.e. all 8), and then assign a bitflag, i.e. flag &= (1 > > << n) where n is the octant # from 0...7 > > > > I thought about seperating axis test against the min, max of each > > triangle edge u0, u1, or u2 (axises from the center) of the cube, but > > I think that would not work because it wouldnt tell me which specific > > octants it intersected the cube, because that info would be lost in > > the projection. Im thinking another approach might have something to > > do with intersecting the triangle edges with the planes of the cubes > > formed by the axises from the center. Any ideas? > > > > Thanks, > > > > Matthew > >  > > > > >  > > Take Surveys. Earn Cash. Influence the Future of IT > > Join SourceForge.net's Techsay panel and you'll get the chance to share > your > > opinions on IT & business topics through brief surveys  and earn cash > > > http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV > >  > > > > _______________________________________________ > > GDAlgorithmslist mailing list > > GDAlgorithmslist@... > > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > > Archives: > > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > >  > Take Surveys. Earn Cash. Influence the Future of IT > Join SourceForge.net's Techsay panel and you'll get the chance to share > your > opinions on IT & business topics through brief surveys  and earn cash > http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 >   Matt Johnson http://otowngraphics.blogspot.com 
From: Jon Watte <hplus@mi...>  20060923 19:55:23

The octants need to: 1) intersect the plane of the triangle 2) intersect the aabb of the triangle Both of those are cheap tests, but may not be sufficient to get 100% accuracy. Once you have identified octants that fulfill both these tests, you can do trianglebox tests for each of them. Or, it may be faster to just accept some slop, and pass down vertices you don't necessarily have to. Btw: In actuality, I think a worstcase triangle can actually pass through seven of the eight octants, but not through all eight (because at least one octant must be culled by the plane of the triangle, if that plane doesn't pass through the center of the cube  and if so, more than one will be culled.). Cheers, / h+ Matt J wrote: > Given a triangle inside a cube, which is subdivided 8 times (i.e. an > octree), is there any optimal (clean) way of classifying which of the > octants one specific triangle intersects. > > The current approach is to check for a triangle and cube collision for > each octant (i.e. all 8), and then assign a bitflag, i.e. flag &= (1 > << n) where n is the octant # from 0...7 > > I thought about seperating axis test against the min, max of each > triangle edge u0, u1, or u2 (axises from the center) of the cube, but > I think that would not work because it wouldnt tell me which specific > octants it intersected the cube, because that info would be lost in > the projection. Im thinking another approach might have something to > do with intersecting the triangle edges with the planes of the cubes > formed by the axises from the center. Any ideas? > > Thanks, > > Matthew >  > >  > Take Surveys. Earn Cash. Influence the Future of IT > Join SourceForge.net's Techsay panel and you'll get the chance to share your > opinions on IT & business topics through brief surveys  and earn cash > http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV >  > > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 
From: Matt J <mjohnson2005@gm...>  20060923 19:16:37

Quick correction, I meant flag = (1 << n). The idea is the triangle could belong to multiple octants that it overlaps, and I only want the leaf nodes of the Octree to contain the actual vertex info, so have to know how to classify which octants the vertices belong to so I can pass the reduced vertex list down the tree when doing the octree building routine. M Given a triangle inside a cube, which is subdivided 8 times (i.e. an > octree), is there any optimal (clean) way of classifying which of the > octants one specific triangle intersects. > > The current approach is to check for a triangle and cube collision for > each octant (i.e. all 8), and then assign a bitflag, i.e. flag &= (1 << n) > where n is the octant # from 0...7 > > I thought about seperating axis test against the min, max of each triangle > edge u0, u1, or u2 (axises from the center) of the cube, but I think that > would not work because it wouldnt tell me which specific octants it > intersected the cube, because that info would be lost in the projection. Im > thinking another approach might have something to do with intersecting the > triangle edges with the planes of the cubes formed by the axises from the > center. Any ideas? > > Thanks, > > Matthew   Matt Johnson http://otowngraphics.blogspot.com 
From: Matt J <mjohnson2005@gm...>  20060923 19:10:51

Given a triangle inside a cube, which is subdivided 8 times (i.e. an octree), is there any optimal (clean) way of classifying which of the octants one specific triangle intersects. The current approach is to check for a triangle and cube collision for each octant (i.e. all 8), and then assign a bitflag, i.e. flag &= (1 << n) where n is the octant # from 0...7 I thought about seperating axis test against the min, max of each triangle edge u0, u1, or u2 (axises from the center) of the cube, but I think that would not work because it wouldnt tell me which specific octants it intersected the cube, because that info would be lost in the projection. Im thinking another approach might have something to do with intersecting the triangle edges with the planes of the cubes formed by the axises from the center. Any ideas? Thanks, Matthew 
From: Wolfgang Engel <wolfgang.engel@gm...>  20060923 03:52:08

Yes you are right :) ... I hope it helps anyway. Original Message From: gdalgorithmslistbounces@... [mailto:gdalgorithmslistbounces@...] On Behalf Of Jon Watte Sent: Friday, September 22, 2006 11:14 AM To: Game Development Algorithms Subject: Re: [Algorithms] prioritizing shadow map resolution Wolfgang Engel wrote: > grey. For example we have three lights with an RGB of (100, 100, 100), > (125, 125, 125) and (255, 0, 0), this is calculated like this > > C=max(R  G, G  B, R B); > > So the chromacity factor C of light 1 is 100, of light 2 is 125 and of > light > 3 is 255. I don't get it. Isn't the "chromacity" of light 1 and 2 both 0 ? And I assume the formula actually uses the abs() of its individual differences? Cheers, / h+  Take Surveys. Earn Cash. Influence the Future of IT Join SourceForge.net's Techsay panel and you'll get the chance to share your opinions on IT & business topics through brief surveys  and earn cash http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=6188 
From: Jon Watte <hplus@mi...>  20060922 18:14:04

Wolfgang Engel wrote: > grey. For example we have three lights with an RGB of (100, 100, 100), (125, > 125, 125) and (255, 0, 0), this is calculated like this > > C=max(R  G, G  B, R B); > > So the chromacity factor C of light 1 is 100, of light 2 is 125 and of light > 3 is 255. I don't get it. Isn't the "chromacity" of light 1 and 2 both 0 ? And I assume the formula actually uses the abs() of its individual differences? Cheers, / h+ 
From: Wolfgang Engel <wolfgang.engel@gm...>  20060922 03:28:25

<<< ... for prioritizing shadow map resolution per light <<< This is interesting. Why do you want to change shadow map resolution per light?=20 I could imagine an approach in which you use a texture atlas with 32 or = 64 256x256 or smaller render targets that cache shadows dynamically. You = just need to pick the lights that get shadows attached to them. So what you = would is a few parameters that help you to pick the right light. This might = follow the same rules you choose to pick a light in a light manager: You might use three important factors, the intensity of the light, the chromacity of the light, and the distance of the light to our geometry. Lights need to be sorted by a function of the three factors. What = function to use is usually a case of trial and error. Chromacity represents the = bias in color of a light. A light with high chromacity will be further away = from grey. For example we have three lights with an RGB of (100, 100, 100), = (125, 125, 125) and (255, 0, 0), this is calculated like this =A0 C=3Dmax(R  G, G  B, R B); =A0 So the chromacity factor C of light 1 is 100, of light 2 is 125 and of = light 3 is 255. So the red light is the light with the highest chromacity = factor. The intensity factor of a light is=20 =A0 I =3D R + G + B =A0 To calculate a light factor for every light, we use =A0 L =3D c1 * C + c2 * I =A0 Good values for c1 and c2 are 0.7 and 0.3. Then all lights are sorted according to this factor. Original Message From: gdalgorithmslistbounces@... [mailto:gdalgorithmslistbounces@...] On Behalf Of = dave Sent: Thursday, September 21, 2006 3:56 PM To: GDAlgorithmslist@... Subject: [Algorithms] prioritizing shadow map resolution In our scenes, we can have an arbitrary number of lights, most with shadows, in view at the same time. Our camera can also swing around relatively quickly as well. I have our shadow mapping up and running, = and now I am trying to determine a good metric(s) for prioritizing shadow = map resolution per light given that they all can't have large shadow maps. What metrics are people finding useful for point and spot lights ? dave = Take Surveys. Earn Cash. Influence the Future of IT Join = SourceForge.net's Techsay panel and you'll get the chance to share your opinions on IT & business topics through brief surveys  and earn cash http://www.techsay.com/default.php?page=3Djoin.php&p=3Dsourceforge&CID=3D= DEVDEV _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 
From: Tom Forsyth <tom.gdalgo@ee...>  20060922 03:27:13

There's two issues here. One is how you allocate shadowbuffers to give a consistent quality *in screen pixels*. That's very difficult. I have a = bunch of stuff on this subject ("Practical Shadows" and "Extremely Practical Shadows" http://www.eelpi.gotdns.org/papers/papers.html), and so do many others  techniques like TSM and PSM and Cascaded shadowmaps and and so = on. The archives of this list should be a rich source of confusion and = bickering :) If you mean "yeah, but I've solved all that" and you want to decide = which lights deserve a higher screenpixel quality than others, then hmmm.... = my advice is not to do that. Just as with texture resolution, a consistent value is usually less objectionable than having some high and some low. TomF. > Original Message > From: gdalgorithmslistbounces@...=20 > [mailto:gdalgorithmslistbounces@...] On=20 > Behalf Of dave > Sent: 21 September 2006 15:56 > To: GDAlgorithmslist@... > Subject: [Algorithms] prioritizing shadow map resolution >=20 >=20 > In our scenes, we can have an arbitrary number of lights, most with > shadows, in view at the same time. Our camera can also swing around > relatively quickly as well. I have our shadow mapping up and running, > and now I am trying to determine a good metric(s) for prioritizing > shadow map resolution per light given that they all can't have large > shadow maps. What metrics are people finding useful for point and > spot lights ? >=20 > dave 