|
||||||||||||||||||
Add Forum to Favorites | Send Topic To a Friend | View Forum FAQ | Track this topic |
Last Thread Next Thread ![]() |
| Normal Computations for Heightfield Lighting |
|
![]() JWalsh Moderator Member since: 2/4/2002 From: Issaquah, WA, United States |
||||
|
|
||||
| Please let me know your thoughts on this article, I'm very interested in hearing what people's response to this article will be. I hope it has been helpful for all, and gets to those who need it most. Jeromy Walsh Lead Programmer Level-Grind Online Authored Books: [The Complete XNA 3.1] [Programming an MMORPG in C# with XNA] GDNet Tutoring: [C# Workshop] [C++ Workshop] "The question isn't how far, the question is do you possess the constitution, the depth of faith, to go as far as is needed?" -Boondock Saints |
||||
|
||||
![]() Anonymous Poster |
||||
|
||||
| What I normally do is (in your parlance) MWE with unnormalized triangle normals and normalized vectors. I don't think it appears in the screenshots. The intuition is that you want the contribution of each triangle normal to be directly related with the size of the triangle. This is pretty fast, only requiring a per-tri cross, and a per-vert sum and normalization. In this way it is similar to MWA, (like how asin x is approximately x). But the real point is: why would you use a polygon approach to a heightfield anyway? It is probably better to think of a heightfield like an image -- namely, you should take advantage of the regular sampling and alignment! For each sample, we want to compute the x, y and z components separately. Let's say the heightfield is in the xz plane with y pointing up. The y component is always 1. You can compute the x and z components by computing the gradient of the heightfield (e.g. seperate x and z Sobel edge filter). This is almost certainly going to be a better quality than either MWE or MWA in this special case. You can normalize it before you upload it (for slowly changing heightfields) or in the vertex shader (for dynamic heightfields). In fact, if your heights are procedural (including render to vertex texture?), or stored in a float texture on a card that supports vertex textures, then you can perform the normal computation entirely in hardware. I think a better showcase for your MWE/MWA examples would be to use something more complex than a lightfield. For example, water with medium-sized waves shifts around in x and z, so it's harder to use image-based approaches, and the merits of MWE/MWA would show. -Won |
||||
|
||||
![]() Anonymous Poster |
||||
|
||||
| Did you even read his article? It might be best in the future to examine how someone suggests doing something before criticizing their method. If you had, you might have realized that he covered everything you mentioned. |
||||
|
||||
![]() JohnBolton Member since: 4/3/2002 From: Belmont, CA, United States |
||||
|
|
||||
| Averaging vs. Normalizing Strictly speaking, "averaging" is not correct because the result is not a unit vector. For example, if you "average" two perpendicular normals, you get a vector with a length of 0.71. In very smooth terrain, the error is small, but in rough terrain the error is significant. Let's say you have a pyramid-shaped feature (height is 1, distance between the corners is 2). The 6 normals are: ( .58, .58, .58)
(-.58, .58, .58)
(-.58, .58, .58)
(-.58, .58, -.58)
( .58, .58, -.58)
( .58, .58, -.58) The "averaged" normal is (0, .58, 0), but the correct correct normal is (0, 1, 0). However, the way you compute the normals such that the Y value is always 1 mitigates this error quite a bit, because the triangle normals are too long to begin with (though extra-long triangle normals result in errors on smooth terrain).John Bolton Locomotive Games (THQ) Current Project: Destroy All Humans (Wii). IN STORES NOW! |
||||
|
||||
![]() JohnBolton Member since: 4/3/2002 From: Belmont, CA, United States |
||||
|
|
||||
| Here is how I compute terrain normals. It is like your MWE (but weighted by triangle area, because the cross products aren't normalized), and only using the 4 surrounding vertices (instead of 6). As you mentioned in your article, you can simplify the cross-product a lot, and the result here is an extremely simple algorithm: Given 4 adjacent points in a uniform grid with a spacing of 1: A, B, C, D
B
|
C--0--A
|
D and a vertical (Z) scale factor s, the desired normal is: N = cross(A,B) + cross(B,C) + cross(C,D) + cross(D,A)
N = normalize( N ) Most of the terms in the sum of the cross products cancel out and the result is this: Nx = 2 / s * (Cz - Az)
Ny = 2 / s * (Dz - Bz)
Nz = 4 / s2
N = normalize( N ) Since N is normalized in the end, the computation can be further simplified by scaling the vector by s/2 before normalizing: Nx = Cz - Az
Ny = Dz - Bz
Nz = 2 / s
N = normalize( N ) If the spacing between the vertices in the grid is sxy instead of 1, then s = sz / sxyJohn Bolton Locomotive Games (THQ) Current Project: Destroy All Humans (Wii). IN STORES NOW! |
||||
|
||||
![]() JWalsh Moderator Member since: 2/4/2002 From: Issaquah, WA, United States |
||||
|
|
||||
| John, First, thanks for your reply. It's reassuring to know that people are reading the article and that it's stimulating thought and criticism. The best way to explore new ideas is to critique what others have done. So now let's explore your points. Quote: You are correct. If we were to average 2 surface normals which are perpendicular to each other you would get a resultant normal which has a magnitude of 0.7071...and thus, less than 1.0f. The end result, in this case, is that you would have a vertex normal which appears about 20% darker than you might expect. An example of a perpendicular set of such surface normals might be on the edge of a sheer vertical cliff, which suddenly plateaus at the top. And this is assuming a primarily 2d world. But in a real 3D world, such angles (90* or higher) are uncommon along the seem of a two triangles. This is further complicated by the fact that our heightfield never has duplicate points at the same x,z location...so such a sheer cliff can never be 90*. The angle will be offset by a least the distance between vertices on the x,z-plane. With that being said, the lower the angle between the two surface normals the smaller the effect of the "error." More often than not, as indicated by the demo I provided, the difference between normalizing the vertex normal and averaging it is minute. Especially when you consider the performance penalty of normalizing all 512x512, 1024x1024, etc..vertex normals, as opposed to just approximating the values with the averaging algorithm. Quote: I'm not sure what you mean by this. I compute the normals using a standard cross-product, just simplified. Orthogonal vertices as are found on an evenly spaced heightfield always create surface normals with a y of 1.0, no special math necessary. And as the "error" introduced by averaging lies mostly in the y, having y's which are always 1, as you indicated, further reduces the noticeable darkness. Quote: X B X | \ | \ | C-- 0-- A | \ | \ | X-- D-- X The above diagram illustrates the problem with your suggested method. Your method assumes there is only a single triangle between COD, DOA, AOB, and BOC. To put it another way, by taking the cross product of 0Dx0A, for example, you're making the assumption that the heightfield is accurately represented by a plane which passes through each of those points - O, D, and A. In reality, as you can see from my diagram, there could be a seem between OD and OA, such that there are actually two triangles(2 planes) there. Each of these triangles could have drastically different surface normals. By necessity your method simplifies the appearance of the terrain and could in effect cause an artificial "smoothness." Nice comments though, lets keep the discussion going. Any thoughts from anyone else? Jeromy Walsh Lead Programmer Level-Grind Online Authored Books: [The Complete XNA 3.1] [Programming an MMORPG in C# with XNA] GDNet Tutoring: [C# Workshop] [C++ Workshop] "The question isn't how far, the question is do you possess the constitution, the depth of faith, to go as far as is needed?" -Boondock Saints |
||||
|
||||
![]() Basiror Member since: 8/18/2001 From: Germany |
||||
|
|
||||
| Just one question on smoothing groups lets say I write a mesh class and implement smoothing groups and materials can i assume that each smoothing group has its own material group or can the mesh data of a material group overlap with more than 1 smoothing group? |
||||
|
||||
![]() JohnBolton Member since: 4/3/2002 From: Belmont, CA, United States |
|||||||
|
|
|||||||
Quote: 90 degree angles can be common. A 45 degree up-slope followed by a 45 degree down-slope would make a 90 degree angle. My pyramid example above has a 90 degree angle. Quote: I agree that averaging instead of normalizing may be an effective optimization, considering that the error turns out small in the test case. I'm going to try it out. Quote: The lengths of the normals are greater than 1, so they compensate for the error induced by averaging. Quote: I don't consider it a problem, just a different approximation. I bet if you try it out on your test case, the result will be similar to the other methods. One advantage is that it is done in a single pass and you don't have to store normals. Also, if it weren't for the normalization, it would be much faster than using 6 vertices. John Bolton Locomotive Games (THQ) Current Project: Destroy All Humans (Wii). IN STORES NOW! |
|||||||
|
|||||||
![]() JWalsh Moderator Member since: 2/4/2002 From: Issaquah, WA, United States |
||||
|
|
||||
Quote: This is true if your terrain rises at 45* and then descends at 45*, assuming that the connection point is a single vertex or edge. In general, however, even mountains do not peak at a single vertex. Often times they will rise at a steep angle, and then plateau or taper at the top. Or, more often then not, a peek that sharp will be very far away and not close enough to the viewer's vantage point for the lighting to be noticeable. Ultimately it's just a trade-off between level of detail and speed. Quote: Fair enough. As with above, it's all a trade-off between the desired speed and the desired detail. It's not fair for me to say that a slightly inaccurate averaging algorithm is ok, but that an algorithm that ignores certain triangles in not ok - if it produces faster lighting calculations with an acceptable level of detail. So I'll tell you what, I'll go ahead and throw your algorithm into my driver, using the same data - a flowing sinusoid, and see how it compares to the other algorithms, both in terms of speed and precision. Once I get it added, I'll post screenshots for the other readers. If it does well, I will add it to my copy of the article and site you as a source. Thanks again for your time and research! Jeromy Walsh Lead Programmer Level-Grind Online Authored Books: [The Complete XNA 3.1] [Programming an MMORPG in C# with XNA] GDNet Tutoring: [C# Workshop] [C++ Workshop] "The question isn't how far, the question is do you possess the constitution, the depth of faith, to go as far as is needed?" -Boondock Saints |
||||
|
||||
![]() Won Member since: 8/8/2005 From: Boston, MA, United States |
||||
|
|
||||
| I was the first Anonymous Poster. The response from the second provoked me to get a real account here. To whomever: In fact, I read the article first for content and once again looking specifically for the suggestions I gave. I looked at the screenshots in the analysis section, and none of them had the combination of "Normalizing surface normals: off" and "Normalizing vertex normals" which is the combo I suggest. This is something that lives midway between MWE and MWA and combines feature from both. To Jeromy: I'm sorry if my message came off as negative criticism, because it wasn't; I'd be curious to see how this would work with meshes that were more complicated than a standard, regularly sampled heightfield (for which I believe image-based methods are better suited). In addition to JohnBolton's algorithm, (which is actually quite similar in spirit to my two suggestions) would you mind including "Normalizing surface normals: off" and "Normalizing vertex normals" in the analysis? Regarding heightfield tesselation: I tend not to think of this as part of the heightfield per se, but rather an artifact of the sampling. Most of the time, the choice of tesselation is static (e.g. diagonal edges are all the same direction for easy stripping). I wonder what the cost/benefit would be to dynamically adjust the diagonal edges to be in the "most important" direction (whatever that is, I'd have to think about it). Also, if you are dynamically generating heightfields, you may want to consider isometric (hexagonal) heightfields (there was a recent academic paper on this?), which are more efficient in their use of triangles per area. I haven't done either, but now my curiosity is piqued. -W |
||||
|
||||
![]() JWalsh Moderator Member since: 2/4/2002 From: Issaquah, WA, United States |
||||||
|
|
||||||
| Won, Thanks again for your follow-up post. And congratulations on your new account. I hope you find GameDev.net a great place to find answers to your questions, and also a great place to provide them. Quote: ..from my article Quote: As you can see Won, I did touch on the combination you're referring to, and in fact said that if the surfaces were not normalized, that the vertex normals MUST be normalized, otherwise you get a really bad looking terrain. It does, however, seem that I failed to include a screenshot of that combination. To get an idea of performance and appearance for yourself, load up the provided executable and toggle surface normals off and vertex normals on using the '4' and '5' across the top of your keyboard. Quote: No worries, mate. I didn't take offense. People like AP2 are better off just being ignored. Quote: I'm not sure what you mean here. Generally terrain has all of the diagonals aligned to get predictable edges. If you alternate direction, ie. "fishbone" the edges, than you can get some strange things happening at alternating seems. As for dynamically adjusting the diagonal edges for "most important" direction, I'm not sure what that direction would be either, but we would have to ensure the winding order of the triangles remains the same, which is what I beleive largely prevents more complex edge patterns. Quote: Thanks for the tip! I'll definately have to take a look at that. My article and evaluation were more to get empirical evidence of the most efficient and "good looking" methods used today, but if hexagonal heightfields become standard, I'll have to re-write my article. =) Thanks again for your feedback! Anyone out there think I did a good job with the article?! =) Cheers! Jeromy Jeromy Walsh Lead Programmer Level-Grind Online Authored Books: [The Complete XNA 3.1] [Programming an MMORPG in C# with XNA] GDNet Tutoring: [C# Workshop] [C++ Workshop] "The question isn't how far, the question is do you possess the constitution, the depth of faith, to go as far as is needed?" -Boondock Saints |
||||||
|
||||||
![]() Won Member since: 8/8/2005 From: Boston, MA, United States |
||||
|
|
||||
| If you were using indexed triangles to render the heightfield, then dynamic edge selection wouldn't be that bad. In fact, indexed triangles are better than triangle strips; for 2-D manifold meshes, indexed triangles should only require 0.5 vertices per triangle versus triangle strips which require a whole vertex per triangle. Plus, you are hinting to the graphics cards which verts will be reused. To do this effectively, you need to make sure you don't flood your post-transform vertex cache, which means your triangles should be issued in some block ordering rather than row ordering. You can also optimize your vertex buffer for the pre-transform cache by storing the vertices in the same order you access them. New cards have a post transform vertex cache that is a fifo with 24 entries, older ones had 16 entries. For current video cards (at least NV's), I believe element buffers almost always streamed from the host, so it isn't that big of a penalty to dynamically adjust them. But with video cards being the way that they are, maybe it's better to just increase the vertex count. Now, let's say you are looking at one square of the heightfield (four vertices, ABCD clockwise). You can compute what the center height should be by computing the average (A+B+C+D)/4. Now, compute the averages of the two pairs of diagonal vertices, (A+C)/2, (B+D)/2. Choose the edge which corresponds to the diagonal average that is closest to the total average. Arithmetic optimizations should make this comparison quite fast. So, I still believe that normal computation should be independent of the choice of tesselation (in fact, shouldn't terrains be normal mapped nowadays?), but you can use the edge selection technique as a preprocess to MWA/MWE. The fact that the mesh is no longer regular might make things more complex. Image based normal calculation don't have this problem. Another potential performance optimization: looking at your inner loop, you should hoist the "is valid vertex" check outside the loop. Have a special "slow" loop for the boundary (where you need to make the check) and have a fast loop for the interior (where you can externally guarantee all vertices are valid) can make things much faster, particularly for larger meshes. -W |
||||
|
||||
![]() JWalsh Moderator Member since: 2/4/2002 From: Issaquah, WA, United States |
||||
|
|
||||
Quote: After my discussion with John about his proposed method of using only the 4 nearest neighbors to compute the vertex normals, I added it to my demo and ran it. My initial thoughts were that it would look very angular due to the fact that we were ignoring two of the surfaces which contributed to the lighting of the vertex. I was incorrect. Save for the diagonal seem which runs across the sinusoid, the method he proposed looked almost identical to my method of Mean Weighted Equally. In addition, his method ran almost 20 FPS faster! The only noticeable artifact is the seem. Due to the extreme angles along the diagonal there appears to be some "cut-off" at those points. My conclusion: If your terrain is mostly smooth, with few rough edges, and if you're not looking for something as detailed or accurate as Mean Weighted by Angle, then it may be best as a first approach to use John's method, rather than Mean Weighted Equally. I will add John's comments to my personal copy of the article with his permission, and as promised, here are screenshots of his nearest neighbor method and my MWE for your comparison. Cheers! Mean Weighted Equally (6 normals) ![]() Nearest Neighbor (4 normals) ![]() Jeromy Walsh Lead Programmer Level-Grind Online Authored Books: [The Complete XNA 3.1] [Programming an MMORPG in C# with XNA] GDNet Tutoring: [C# Workshop] [C++ Workshop] "The question isn't how far, the question is do you possess the constitution, the depth of faith, to go as far as is needed?" -Boondock Saints |
||||
|
||||
![]() Bourbaki Member since: 8/14/2005 From: Tokyo, Japan |
||||
|
|
||||
| I did quite the same just useing 2 Manifolds in |R^2 http://codemages.sf.net/SphereWorld.png http://codemages.sf.net/SphereWorld2.png http://codemages.sf.net/TorusWorld.png http://codemages.sf.net/TorusWorld2.png http://codemages.sf.net/textures.avi http://codemages.sf.net/textures2.avi http://codemages.sf.net/textures3.avi useing this you can map your lighting functions into several simple bodies and also do displacement mapping and such (ie fluid dynamics) |
||||
|
||||
![]() Winograd Member since: 7/23/2003 From: Pori, Finland |
||||
|
|
||||
| Hi! Like Won, I find it a little strange that one would calculate the normals for the vertices from the polygonal representation of the height field. As it is, the height field is nothing more than a sampled 2d-function. Thus all the information required to find the exact and correct normal for a given vertex is contained in the samples (assuming that vertices and the samples are aligned). Calculating the normals from polygons just seems overly complicated. As we all know there's a wide range of "tools" to calculate the gradient field of a sampled "image". Many of these come from the field of image processing and dsp. These include sobel, and prewitt kernels. I thought I could share some of the code I wrote a while ago for calculating the height field normals. It requires no normalization what so ever, but it uses LUTs for some trigonometric operations (cos(atan(x)) and sin(atan(x))). This is pretty good for platforms where operations such as sqrt, and trig.ops. are extremely expensive. Note also that only few mults are required. This one uses following simplified kernels to find (the rough aproximation of) the gradient: Gx: -1, 0, 1 Gy: -1, 0, +1 The parameters for the C-function, normal, are given from the heightfield samples like this: ** y0 ** x0 ** x2 ** y2 ** and the parameter d is the sampling "distance". #include"normal.h" #include<math.h> #define SIZE 512 #define COEFINT 16 #define COEFFLOAT 16.0f #define MINVAL -16.0f #define MINVALINT -16 static float sin_atan[SIZE]; static float cos_atan[SIZE]; static inline float sinatan(int t) { return sin_atan[t]; } static inline float cosatan(int t) { return cos_atan[t]; } /* Calculates the tangent of the surface (rough aproximation). One substract, one integer division and two bitshifts (assuming that the constant operations gets optimized to such) */ static inline int tangent(int x0,int x2, int d) { /* t will be value suitable for our LUTs. i.e. it will be 0 for -16.0 and 511 for ~+16.0 */ int t = ( (COEFINT*(x2-x0) ) / d )/2; t-=MINVALINT*COEFINT; /* Let's clamp t if it's out of the boundaries. Linear extrapolation would be more accurate. */ if(t<0) t=0; else if(t>=SIZE) t=SIZE-1; return t; } void normal(int x0,int x2,int y0,int y2,int d, vec *nrm) { /* Two tangents of the surface (in fp format). Actually they are averages of the tangents: Xd = ( (x[1]-x[0]) + (x[2]-x[1] ) */ int Xd = tangent(x0,x2,d); int Yd = tangent(y0,y2,d); /* Four lookups, and two float multiplications + one negation. */ nrm->x = -sinatan(Xd); float ytmp = cosatan(Xd); nrm-> y = ytmp * cosatan(Yd); nrm-> z = ytmp * sinatan(Yd); } void initLUTs() { int i; for(i=0;i<SIZE;i++) { sin_atan[i] = sin(atan(((float)i)/COEFFLOAT+MINVAL)); cos_atan[i] = cos(atan(((float)i)/COEFFLOAT+MINVAL)); } } |
||||
|
||||
![]() mike74 Member since: 8/2/2004 |
||||
|
|
||||
| The demos don't work for me since I don't have d3d9.dll. Could you post an OpenGL version? BTW, let me know if you have ideas for improving my desert at http://www.coolgroups.com/desert2. |
||||
|
||||
![]() mike74 Member since: 8/2/2004 |
||||
|
|
||||
| I ran the program on the computer at the library, and all it did was crash. mike http://www.coolgroups.com/ |
||||
|
||||
![]() Wampus Member since: 4/26/2004 |
||||
|
|
||||
| I was getting a problem with the index buffer and had to change it to the following for it to work: Heightfield.cpp, Line 375 // Allocate the index buffer pDevice->CreateIndexBuffer( numIndices * 2/*bytes*/, D3DUSAGE_DYNAMIC, D3DFMT_INDEX16, D3DPOOL_DEFAULT, &m_pIndexBuffer, NULL ); short* pIndices; HRESULT result = m_pIndexBuffer->Lock( 0, 0, (void**)&pIndices, D3DLOCK_DISCARD ); The D3DLOCK_DISCARD flag is only valid for buffers created with D3DUSAGE_DYNAMIC. |
||||
|
||||
![]() Anonymous Poster |
||||
|
||||
| There is another way to calculate the angle between two vectors cross(A, B) = |A||B|sin(theta) dot(A, B) = |A||B|cos(theta) tan(theta) = sin(theta)/cos(theta) tan(theta) = length(cross(A, B))/dot(A, B) (|A||B| cancels) theta = atan2(length(cross(A, B)), dot(A, B)) |
||||
|
||||
![]() Anonymous Poster |
||||
|
||||
| I haven't totally read too much into the replies and article, but I thought I'd mention the need to create hard edges on angles less that 90 degrees and angles greater than 270 (Exact figures should be based on experimentation). Lighting looks pretty bad on terrains at these angles. This might be more expensive, but keeps wierd lighting from appearing when the sun is near a horizon. |
||||
|
||||
![]() Ishraam Member since: 6/22/2004 From: strasbourg, France |
||||
|
|
||||
| I know this article has been here for some time now -and I think no one pointed it out in this thread-, but I have noticed something 'strange' in the code you provide for the MWA method : Have a look :
[...]
D3DXVECTOR3 normal1( height0 - height2, 1.0f, height0 - height1 );
D3DXVec3Normalize( &normal1, &normal1 );
// Get the Magnitude of the normal to the surface and the weights
float normal1Mag = D3DXVec3Length( &normal1 );
[...]
You FIRST normalize normal1, and THEN you ask for its length via D3DXVec3Length... I bet it would always be equal to 1.f . Anyway, thanks for the article, and didn't know the MWA before. |
||||
|
||||
![]() ASL Member since: 8/24/2005 From: Copenhagen, Denmark |
||||
|
|
||||
| Hey all! So many different ways to calculate normals on a heightmap. I just want a good and not way too advanced method to calculate normals on my static heightmap! No waves, no animation, no nothing fancy. So I just have to calculate my normals once. I read through the article and he assumes a lefthand DX system with CW-ordering. What do I have to alter to convert his methods to a righthand opengl-coordinate system? [Edited by - ASL on August 13, 2006 6:07:50 AM] |
||||
|
||||
![]() Anonymous Poster |
||||
|
||||
| Not coherent and fairly outdated. Spends a lot of time talking about historical and background stuff not related to the topic before getting to the details. What's the point on getting all formal using greek letters when you are just telling the reader to do some grade school math? I think overall this style of writing is very frustrating because you hide something that can be explained in essentially 2 sentences under paragraphs of filler. Less is more. Also, the images don't make any sense, what the hell am I looking at??? What kind of lighting model genrates these bands in the middle and black everywhere? |
||||
|
||||
![]() aayudh Member since: 9/21/2007 From: chennai, India |
||||
|
|
||||
| Hi, In the demo you provided, have you observed the triangulation effect/artifact ? What I am saying is that you can nearly see the triangles/quads distinguished by the black lines !! I am seeing the same in my water surface rendering and terrain rendering and I am not quite sure how it forms ? Why does this occur. In my case the normals are sent to the pixel shader and all calculations are done there. Should they not be smooth ? |
||||
|
||||
All times are ET (US)![]() |
Last Thread Next Thread ![]() |
|